Kernel Memory Sanitizer (KMSAN)

KMSAN 개요

SPDX 라이선스 식별자: GPL-2.0

저작권 (C) 2022, Google LLC.

Kernel Memory Sanitizer (KMSAN)

KMSAN은 초기화되지 않은 값의 사용을 찾기 위한 동적 오류 검출기입니다. 컴파일러 계측을 기반으로 하며 사용자 공간의 `MemorySanitizer tool`과 매우 유사합니다.

중요한 점은 KMSAN이 프로덕션 사용을 목적으로 하지 않는다는 것입니다. 커널 메모리 사용량을 크게 늘리고 시스템 전체를 느리게 만들기 때문입니다.

빌드, 보고서 해석과 검출 조건

사용법

커널 빌드

KMSAN을 포함한 커널을 빌드하려면 최신 Clang 14.0.6 이상이 필요합니다. Clang 빌드 방법은 `LLVM documentation`을 참조하십시오.

그런 다음 CONFIG_KMSAN을 활성화하여 커널을 구성하고 빌드합니다.

보고서 예

다음은 KMSAN 보고서의 예입니다.

=====================================================
BUG: KMSAN: uninit-value in test_uninit_kmsan_check_memory+0x1be/0x380 [kmsan_test]
 test_uninit_kmsan_check_memory+0x1be/0x380 mm/kmsan/kmsan_test.c:273
 kunit_run_case_internal lib/kunit/test.c:333
 kunit_try_run_case+0x206/0x420 lib/kunit/test.c:374
 kunit_generic_run_threadfn_adapter+0x6d/0xc0 lib/kunit/try-catch.c:28
 kthread+0x721/0x850 kernel/kthread.c:327
 ret_from_fork+0x1f/0x30 ??:?

Uninit was stored to memory at:
 do_uninit_local_array+0xfa/0x110 mm/kmsan/kmsan_test.c:260
 test_uninit_kmsan_check_memory+0x1a2/0x380 mm/kmsan/kmsan_test.c:271
 kunit_run_case_internal lib/kunit/test.c:333
 kunit_try_run_case+0x206/0x420 lib/kunit/test.c:374
 kunit_generic_run_threadfn_adapter+0x6d/0xc0 lib/kunit/try-catch.c:28
 kthread+0x721/0x850 kernel/kthread.c:327
 ret_from_fork+0x1f/0x30 ??:?

Local variable uninit created at:
 do_uninit_local_array+0x4a/0x110 mm/kmsan/kmsan_test.c:256
 test_uninit_kmsan_check_memory+0x1a2/0x380 mm/kmsan/kmsan_test.c:271

Bytes 4-7 of 8 are uninitialized
Memory access of size 8 starts at ffff888083fe3da0

CPU: 0 PID: 6731 Comm: kunit_try_catch Tainted: G    B       E     5.16.0-rc3+ #104
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014
=====================================================

보고서는 지역 변수 `uninit`이 `do_uninit_local_array()`에서 초기화되지 않은 채 생성되었다고 알려 줍니다. 세 번째 스택 추적이 이 변수가 만들어진 위치에 해당합니다.

첫 번째 스택 추적은 초기화되지 않은 값이 `test_uninit_kmsan_check_memory()`에서 사용된 위치를 보여 줍니다. 도구는 지역 변수에서 초기화되지 않은 채 남은 바이트와, 그 값이 사용되기 전에 다른 메모리 위치로 복사된 스택도 함께 표시합니다.

KMSAN은 초기화되지 않은 값 `v`가 다음과 같이 사용될 때 보고합니다.

조건식에서 사용될 때. 예: `if (v) { ... }`.

인덱싱이나 포인터 역참조에 사용될 때. 예: `array[v]` 또는 `*v`.

사용자 공간이나 하드웨어로 복사될 때. 예: `copy_to_user(..., &v, ...)`.

함수 인수로 전달되고 CONFIG_KMSAN_CHECK_PARAM_RETVAL이 활성화되어 있을 때. 자세한 내용은 뒤에서 설명합니다.

사용자 공간이나 하드웨어로 데이터를 복사하는 경우는 보안 문제이며, 이를 제외한 나머지 사례도 C11 표준 관점에서는 정의되지 않은 동작입니다.

계측 비활성화와 지원 범위

계측 비활성화

함수에 `__no_kmsan_checks`를 표시할 수 있습니다. 그러면 KMSAN은 그 함수 안의 초기화되지 않은 값을 무시하고 함수 출력을 초기화된 것으로 표시합니다. 따라서 사용자는 그 함수와 관련된 KMSAN 보고서를 받지 않습니다.

KMSAN이 지원하는 또 다른 함수 속성은 `__no_sanitize_memory`입니다. 이 속성을 함수에 적용하면 KMSAN이 해당 함수를 계측하지 않습니다. 컴파일러가 일부 저수준 코드에 개입하지 않게 해야 할 때 유용합니다. 예를 들어 `noinstr`로 표시한 코드는 암시적으로 `__no_sanitize_memory`를 추가합니다.

하지만 비용이 있습니다. 이런 함수의 스택 할당에는 잘못된 shadow 또는 origin 값이 들어가 false positive를 일으킬 가능성이 큽니다. 계측되지 않은 코드에서 호출된 함수도 매개변수에 잘못된 메타데이터를 받을 수 있습니다.

일반적인 원칙으로 `__no_sanitize_memory`를 명시적으로 사용하지 마십시오.

단일 파일, 예를 들어 main.o에서 KMSAN을 끌 수도 있습니다.

KMSAN_SANITIZE_main.o := n

전체 디렉터리에서 끄려면 Makefile에 다음을 지정합니다.

KMSAN_SANITIZE := n

이는 파일이나 디렉터리의 모든 함수에 `__no_sanitize_memory`를 적용하는 것과 같습니다. KMSAN 때문에 코드가 깨지는 경우, 예를 들어 아주 이른 부팅 단계에서 실행되는 코드가 아니라면 대부분의 사용자는 KMSAN_SANITIZE를 사용할 필요가 없습니다.

`kmsan_disable_current()`와 `kmsan_enable_current()` 호출로 현재 task의 KMSAN 검사를 일시적으로 끌 수도 있습니다. 각 `kmsan_enable_current()` 앞에는 반드시 `kmsan_disable_current()`가 있어야 하며 호출 쌍은 중첩할 수 있습니다. 이 호출은 신중하게 사용하고 영역을 짧게 유지하며 가능한 경우 계측을 끄는 다른 방법을 우선하십시오.

지원

KMSAN이 동작하려면 KMSAN을 지원하는 유일한 컴파일러인 Clang으로 커널을 빌드해야 합니다. 커널 계측 패스는 사용자 공간의 `MemorySanitizer tool`을 기반으로 합니다.

현재 런타임 라이브러리는 x86_64만 지원합니다.

Shadow memory와 값 전파

KMSAN의 동작 방식

KMSAN shadow memory

KMSAN은 커널 메모리의 각 바이트에 메타데이터 바이트, 즉 shadow byte 하나를 연결합니다. 커널 메모리 바이트의 특정 비트가 초기화되지 않았다면 shadow byte의 대응 비트가 설정됩니다. 메모리를 초기화되지 않은 상태로 표시하여 shadow byte를 `0xff`로 만드는 것을 poisoning이라 하고, 초기화된 상태로 표시하여 `0x00`으로 만드는 것을 unpoisoning이라 합니다.

새 변수가 스택에 할당되면 컴파일러가 삽입한 계측 코드가 기본적으로 이를 poison합니다. 즉시 초기화되는 스택 변수는 예외입니다. `__GFP_ZERO` 없이 수행한 새 heap 할당도 poison됩니다.

컴파일러 계측은 코드에서 shadow 값이 사용되는 과정도 추적합니다. 필요할 때 계측 코드는 `mm/kmsan/`의 런타임 라이브러리를 호출해 shadow 값을 유지합니다.

기본형이나 복합형의 shadow 값은 원래 값과 길이가 같은 바이트 배열입니다. 상수 값을 메모리에 쓰면 그 메모리는 unpoison됩니다. 메모리에서 값을 읽으면 shadow memory도 함께 가져와 그 값을 사용하는 모든 연산으로 전파합니다. 하나 이상의 값을 입력으로 받는 각 명령에 대해 컴파일러는 입력 값과 shadow에 따라 결과의 shadow를 계산하는 코드를 생성합니다.

예:

int a = 0xff;  // i.e. 0x000000ff
int b;
int c = a | b;

이 경우 `a`의 shadow는 `0`, `b`의 shadow는 `0xffffffff`, `c`의 shadow는 `0xffffff00`입니다. 따라서 `c`의 상위 3바이트는 초기화되지 않았고 하위 1바이트는 초기화되었습니다.

Origin 추적과 연결

Origin 추적

커널 메모리 4바이트마다 origin도 하나씩 매핑됩니다. origin은 초기화되지 않은 값이 프로그램 실행 중 생성된 지점을 설명합니다. 각 origin은 heap 메모리라면 전체 할당 스택에, 지역 변수라면 초기화되지 않은 변수를 포함한 함수에 연결됩니다.

초기화되지 않은 변수가 stack 또는 heap에 할당되면 새 origin 값이 생성되고 그 변수를 해당 값으로 채웁니다. 메모리에서 값을 읽을 때 origin도 읽어 shadow와 함께 유지합니다. 하나 이상의 값을 입력으로 받는 각 명령에서 결과 origin은 초기화되지 않은 입력 중 하나의 origin입니다. poison된 값을 메모리에 쓰면 origin도 대응 저장소에 기록합니다.

예 1:

int a = 42;
int b;
int c = a + b;

이 경우 함수 진입 시 `b`의 origin이 생성되고, 덧셈 결과를 메모리에 쓰기 직전에 그 origin이 `c`의 origin으로 저장됩니다.

여러 변수가 같은 4바이트 조각에 저장되면 같은 origin 주소를 공유할 수 있습니다. 이 경우 어느 변수에 쓰더라도 모든 변수의 origin이 갱신됩니다. 비트별, 심지어 바이트별 origin 저장도 비용이 지나치게 크므로 이 상황에서는 정밀도를 희생해야 합니다.

예 2:

int combine(short a, short b) {
  union ret_t {
    int i;
    short s[2];
  } ret;
  ret.s[0] = a;
  ret.s[1] = b;
  return ret.i;
}

`a`가 초기화되고 `b`가 초기화되지 않았다면 결과 shadow는 `0xffff0000`이고 결과 origin은 `b`의 origin입니다. `ret.s[0]`도 같은 origin을 갖지만 이 변수는 초기화되어 있으므로 origin이 사용되지는 않습니다.

두 함수 인수가 모두 초기화되지 않았다면 두 번째 인수의 origin만 보존됩니다.

Origin 연결

디버깅을 쉽게 하기 위해 KMSAN은 초기화되지 않은 값을 메모리에 저장할 때마다 새 origin을 만듭니다. 새 origin은 생성 스택과 그 값이 이전에 가졌던 origin을 모두 참조합니다. 이는 메모리 소비를 늘릴 수 있으므로 런타임에서 origin chain 길이를 제한합니다.

Clang 계측 API

Clang 계측 API

Clang 계측 패스는 커널 코드에 `mm/kmsan/nstrumentation.c`에 정의된 함수 호출을 삽입합니다. 이 경로 표기는 원문 그대로 보존했습니다.

Shadow 조작

컴파일러는 각 메모리 접근에 대해 주어진 메모리의 shadow와 origin 주소를 가리키는 포인터 쌍을 반환하는 함수를 호출합니다.

typedef struct {
  void *shadow, *origin;
} shadow_origin_ptr_t

shadow_origin_ptr_t __msan_metadata_ptr_for_load_{1,2,4,8}(void *addr)
shadow_origin_ptr_t __msan_metadata_ptr_for_store_{1,2,4,8}(void *addr)
shadow_origin_ptr_t __msan_metadata_ptr_for_load_n(void *addr, uintptr_t size)
shadow_origin_ptr_t __msan_metadata_ptr_for_store_n(void *addr, uintptr_t size)

함수 이름은 메모리 접근 크기에 따라 달라집니다.

컴파일러는 값을 읽을 때마다 그 shadow와 origin도 메모리에서 읽도록 보장합니다. 값을 메모리에 저장할 때도 메타데이터 포인터를 사용해 shadow와 origin을 함께 저장합니다.

지역 변수 처리

지역 변수에 대한 새 origin 값을 만들고 그 변수의 origin을 새 값으로 설정할 때는 특별한 함수를 사용합니다.

void __msan_poison_alloca(void *addr, uintptr_t size, char *descr)

Task별 데이터 접근

KMSAN은 계측된 모든 함수의 시작 부분에 `__msan_get_context_state()` 호출을 삽입합니다.

kmsan_context_state *__msan_get_context_state(void)

`kmsan_context_state`는 `include/linux/kmsan.h`에 다음과 같이 선언됩니다.

struct kmsan_context_state {
  char param_tls[KMSAN_PARAM_SIZE];
  char retval_tls[KMSAN_RETVAL_SIZE];
  char va_arg_tls[KMSAN_PARAM_SIZE];
  char va_arg_origin_tls[KMSAN_PARAM_SIZE];
  u64 va_arg_overflow_size_tls;
  char param_origin_tls[KMSAN_PARAM_SIZE];
  depot_stack_handle_t retval_origin_tls;
};

KMSAN은 이 구조체를 사용해 계측된 함수 사이에서 매개변수의 shadow와 origin을 전달합니다. CONFIG_KMSAN_CHECK_PARAM_RETVAL이 매개변수를 즉시 검사하는 경우는 예외입니다.

초기화되지 않은 값을 함수로 전달

Clang의 MemorySanitizer 계측에는 값으로 전달되는 함수 매개변수와 함수 반환값을 검사하는 `-fsanitize-memory-param-retval` 옵션이 있습니다.

이 옵션은 기본적으로 활성화되는 CONFIG_KMSAN_CHECK_PARAM_RETVAL이 제어하며, KMSAN이 초기화되지 않은 값을 더 일찍 보고하도록 합니다. 자세한 내용은 `LKML discussion`을 참조하십시오.

LLVM에서 검사가 구현된 방식상 `noundef`로 표시한 매개변수에만 검사가 적용되므로 모든 매개변수가 반드시 검사된다고 보장할 수 없습니다. 따라서 `kmsan_context_state`의 메타데이터 저장소를 없앨 수 없습니다.

문자열 함수

컴파일러는 `memcpy()`, `memmove()`, `memset()` 호출을 다음 함수로 바꿉니다. 데이터 구조를 초기화하거나 복사할 때도 이 함수들이 호출되어 데이터와 함께 shadow와 origin을 복사합니다.

void *__msan_memcpy(void *dst, void *src, uintptr_t n)
void *__msan_memmove(void *dst, void *src, uintptr_t n)
void *__msan_memset(void *dst, int c, uintptr_t n)

오류 보고

컴파일러는 값을 사용할 때마다 shadow 검사를 생성하며 값이 poison되어 있으면 `__msan_warning()`을 호출합니다.

void __msan_warning(u32 origin)

`__msan_warning()`은 KMSAN 런타임이 오류 보고서를 출력하게 합니다.

Inline assembly 계측

KMSAN은 모든 inline assembly 출력에 다음 호출을 삽입합니다.

void __msan_instrument_asm_store(void *addr, uintptr_t size)

이 함수는 해당 메모리 영역을 unpoison합니다.

이 방식은 일부 오류를 가릴 수 있지만 비트 연산과 atomic 연산 등에서 발생하는 많은 false positive를 방지하는 데도 도움이 됩니다.

때로 inline assembly에 전달되는 포인터가 유효한 메모리를 가리키지 않을 수 있습니다. 그런 포인터는 런타임에서 무시합니다.

런타임 상태와 메타데이터 할당

런타임 라이브러리

코드는 `mm/kmsan/`에 있습니다.

Task별 KMSAN 상태

각 task_struct에는 앞서 설명한 KMSAN context와 KMSAN 보고를 금지하는 task별 counter를 보관하는 KMSAN task state가 연결됩니다.

struct kmsan_context {
  ...
  unsigned int depth;
  struct kmsan_context_state cstate;
  ...
}

struct task_struct {
  ...
  struct kmsan_context kmsan;
  ...
}

KMSAN context

커널 task context에서 실행할 때 KMSAN은 `current->kmsan.cstate`에 함수 매개변수와 반환값의 메타데이터를 보관합니다.

커널이 interrupt, softirq 또는 NMI context에서 실행되어 `current`를 사용할 수 없으면 KMSAN은 CPU별 interrupt state로 전환합니다.

DEFINE_PER_CPU(struct kmsan_ctx, kmsan_percpu_ctx);

메타데이터 할당

커널에는 메타데이터를 저장하는 위치가 여러 곳 있습니다.

1. 각 `struct page` 인스턴스는 자신의 shadow page와 origin page를 가리키는 두 포인터를 포함합니다.

struct page {
  ...
  struct page *shadow, *origin;
  ...
};

부팅할 때 커널은 사용 가능한 모든 커널 page마다 shadow page와 origin page를 할당합니다. 이는 커널 주소 공간이 이미 조각난 비교적 늦은 시점에 수행되므로 일반 data page가 metadata page 사이에 임의로 끼어들 수 있습니다.

따라서 일반적으로 연속한 두 memory page의 shadow 또는 origin page가 연속한다고 보장할 수 없습니다. 메모리 접근이 한 memory block의 경계를 넘으면 shadow 또는 origin 접근이 다른 page를 손상하거나 잘못된 값을 읽을 가능성이 있습니다.

실제로 같은 `alloc_pages()` 호출이 반환한 연속 memory page는 연속한 metadata를 갖습니다. 반면 두 page가 서로 다른 할당에 속한다면 metadata page가 조각날 수 있습니다.

커널 data 영역인 `.data`, `.bss` 등과 percpu memory 영역도 metadata 연속성을 보장하지 않습니다.

`__msan_metadata_ptr_for_XXX_YYY()`가 연속하지 않은 metadata를 가진 두 page 사이의 경계에 닿으면 가짜 shadow 또는 origin 영역을 가리키는 포인터를 반환합니다.

char dummy_load_page[PAGE_SIZE] __attribute__((aligned(PAGE_SIZE)));
char dummy_store_page[PAGE_SIZE] __attribute__((aligned(PAGE_SIZE)));

`dummy_load_page`는 0으로 초기화되므로 여기서 읽으면 항상 0을 얻습니다. `dummy_store_page`에 대한 모든 쓰기는 무시됩니다.

2. vmalloc memory와 module에는 실제 memory range, shadow, origin 사이에 직접 매핑이 있습니다. KMSAN은 vmalloc 영역을 4분의 3만큼 줄여 첫 번째 4분의 1만 `vmalloc()`에 제공합니다. 두 번째 4분의 1에는 첫 영역의 shadow memory를 두고 세 번째 영역에는 origin을 둡니다. 네 번째 영역의 작은 부분에는 kernel module용 shadow와 origin을 둡니다. 자세한 내용은 `arch/x86/include/asm/pgtable_64_types.h`를 참조하십시오.

page 배열을 연속한 virtual memory 공간에 매핑할 때 해당 shadow page와 origin page도 마찬가지로 연속한 영역에 매핑합니다.

참고 문헌과 링크

참고 문헌

E. Stepanov, K. Serebryany. `MemorySanitizer: fast detector of uninitialized memory use in C++ <https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/43308.pdf>`_. CGO 2015 논문집.

MemorySanitizer tool: https://clang.llvm.org/docs/MemorySanitizer.html

LLVM documentation: https://llvm.org/docs/GettingStarted.html

LKML discussion: https://lore.kernel.org/all/20220614144853.3693273-1-glider@google.com/