KASAN: Kernel Address SANitizer

최근에 버그의 원인을 찾다가 KASAN을 써볼 일이 생긴 김에 KASAN이 어떻게 동작하는지 정리해보려고 한다. TMI지만 내가 잡으려던 버그는 알고보니 memory corruption 버그가 아니라 KASAN으로 잡지는 못했다. [mail]

Overview

KASAN은 Andrey Ryabinin이 2015년에 머지된 커널을 위한 address sanitizer이다. [mail] [commit] [lwn] address sanitizer는 모든 메모리 접근 명령어에 대해 해당 접근이 유효한지 확인하는 명령어를 삽입해서 메모리 접근의 유효성을 판별한다. KASAN은 커널을 위한 address sanitizer이다. KASAN은 use-after-free, out-of-bounds access 등의 버그를 잡아낼 수 있다. CONFIG_KASAN=y로 활성화할 수 있다. 이 글에서는 KASAN의 동작 원리와 기능을 일부 소개한다.

-fsanitize=kernel-address (gcc > 4.8.2)

KASAN은 메모리 접근 명령어마다 각각 유효성을 확인하는 명령어를 삽입하기 때문에 컴파일러에 크게 의존한다. -fsanitize=kernel-address를 지원하는 4.8.2보다 높은 버전의 gcc가 필요하다.

컴파일러가 -fsanitize=kernel-address 옵션을 지원하면 메모리 접근 명령어마다 __asan_loadN(), __asan_storeN() 함수를 삽입한다. 이때 N은 접근하는 크기에 따라 1, 2, 4, 8, 16 중 하나이다. 이때 삽입하는 함수들을 인라이닝할지 선택할 수 있는데, 인라이닝을 할 경우 속도가 크게 개선되는 대신 커널의 크기가 커진다. CONFIG_KASAN_INLINE=y or CONFIG_KASAN_OUTLINE=y로 인라인 여부를 결정할 수 있다.

Shadow Memory

컴파일러의 도움으로 명령어를 삽입해서 __asan_loadN()/__asan_storeN()으로 메모리 접근을 확인할 수 있다고 해보자. 그런데 어떠한 메모리 접근이 유효한지 확인하려면, 어느 주소에 접근해도 되는지(혹은 안되는지) 알고 있어야 한다. 예를 들어서 할당되지 않은 슬랩 객체는 접근하면 안될 것이고, kmalloc()으로 56바이트를 할당했지만 실제로 64바이트짜리 객체가 할당되었을 때 처음 56바이트는 접근해도 되지만 나머지 8바이트를 접근한다면 out-of-bounds access일 것이다.

KASAN은 이렇듯 "어떤 주소에 접근해도 되는지"에 대한 정보를 shadow memory에 저장한다. shadow memory는 전체 가용 메모리의 1/8을 사용하며, shadow memory 1바이트당 8바이트에 대한 접근 여부를 표현한다.

unsigned long kasan_mem_to_shadow(unsigned long addr)
{
        return (addr >> KASAN_SHADOW_SCALE_SHIFT) + KASAN_SHADOW_OFFSET;
}

위 함수는 kasan이 커널 주소를 해당 주소의 접근 가능 여부를 나타내는 shadow memory의 주소로 변환하는 kasan_mem_to_shadow() 함수이다. 이때 KASAN_SHADOW_SCALE_SHIFT는 3이다. KASAN_SHADOW_OFFSET은 shadow memory의 시작 주소이다. KASAN_SHADOW_OFFSET에 (접근하는 주소) / 8을 더하면 접근하는 주소에 대한 shadow memory의 주소로 변환된다.

위에서 설명했듯 shadow memory는 각 1바이트당 8바이트에 대한 접근 가능 여부를 나타낸다. shadow memory의 값은 메모리의 접근 가능한 범위, 상태 등을 나타낸다.

- 0x00: 8바이트가 모두 접근 가능

- 0x00 < N < 0x08: 처음 N바이트는 접근 가능, 나머지 8-N 바이트는 접근 불가능.

- 0xff: 페이지가 free된 상태

- 0xfe: kmalloc_large()를 위한 redzone

- 0xfc: slub 객체를 위한 redzone

- 0xfb: free된 객체

- 0xf5: 리턴 이후의 스택 사용 감지

- 0xf8: 스코프를 벗어난 스택 사용 감지

Poisoning

KASAN은 shadow memory를 poisoning하는데 kasan_poison_shadow(), kasan_unpoison_shadow() 함수를 사용한다. 슬랩 객체 할당, 페이지 할당 후에 메모리에 접근해도 될 때는 unpoison을, 슬랩 오브젝트 해제, 페이지 해제 후에 메모리에 접근하면 안될 때는 poison한다. 이 두 함수는 shadow memory에 해당 주소에 접근 가능한지 여부를 기록한다.

/*
 * Poisons the shadow memory for 'size' bytes starting from 'addr'.
 * Memory addresses should be aligned to KASAN_SHADOW_SCALE_SIZE.
 */
static void kasan_poison_shadow(const void *address, size_t size, u8 value)
{
	void *shadow_start, *shadow_end;

	shadow_start = kasan_mem_to_shadow(address);
	shadow_end = kasan_mem_to_shadow(address + size);

	memset(shadow_start, value, shadow_end - shadow_start);
}

void kasan_unpoison_shadow(const void *address, size_t size)
{
	kasan_poison_shadow(address, size, 0);

	if (size & KASAN_SHADOW_MASK) {
		u8 *shadow = (u8 *)kasan_mem_to_shadow(address + size);
		*shadow = size & KASAN_SHADOW_MASK;
	}
}

__asan_loadN(), __asan_storeN()

#define DEFINE_ASAN_LOAD_STORE(size)				\
	void __asan_load##size(unsigned long addr)		\
	{							\
		check_memory_region(addr, size, false);		\
	}							\
	EXPORT_SYMBOL(__asan_load##size);			\
	__alias(__asan_load##size)				\
	void __asan_load##size##_noabort(unsigned long);	\
	EXPORT_SYMBOL(__asan_load##size##_noabort);		\
	void __asan_store##size(unsigned long addr)		\
	{							\
		check_memory_region(addr, size, true);		\
	}							\
	EXPORT_SYMBOL(__asan_store##size);			\
	__alias(__asan_store##size)				\
	void __asan_store##size##_noabort(unsigned long);	\
	EXPORT_SYMBOL(__asan_store##size##_noabort)

DEFINE_ASAN_LOAD_STORE(1);
DEFINE_ASAN_LOAD_STORE(2);
DEFINE_ASAN_LOAD_STORE(4);
DEFINE_ASAN_LOAD_STORE(8);
DEFINE_ASAN_LOAD_STORE(16);

void __asan_loadN(unsigned long addr, size_t size)
{
	check_memory_region(addr, size, false);
}
EXPORT_SYMBOL(__asan_loadN);

__alias(__asan_loadN)
void __asan_loadN_noabort(unsigned long, size_t);
EXPORT_SYMBOL(__asan_loadN_noabort);

void __asan_storeN(unsigned long addr, size_t size)
{
	check_memory_region(addr, size, true);
}
EXPORT_SYMBOL(__asan_storeN);

__alias(__asan_storeN)
void __asan_storeN_noabort(unsigned long, size_t);
EXPORT_SYMBOL(__asan_storeN_noabort);

__asan_loadN(), __asan_storeN()은 check_memory_region()의 래퍼 함수이다. 각 메모리에 읽고 쓸 때마다 이 함수들을 호출해서 접근이 유효한지 판별한다.

static __always_inline void check_memory_region(unsigned long addr,
						size_t size, bool write)
{
	struct kasan_access_info info;

	if (unlikely(size == 0))
		return;

	if (unlikely((void *)addr <
		kasan_shadow_to_mem((void *)KASAN_SHADOW_START))) {
		info.access_addr = (void *)addr;
		info.access_size = size;
		info.is_write = write;
		info.ip = _RET_IP_;
		kasan_report_user_access(&info);
		return;
	}

	if (likely(!memory_is_poisoned(addr, size)))
		return;

	kasan_report(addr, size, write, _RET_IP_);
}

check_memory_region()은 커널 영역이 아닌 유저 영역을 접근한 경우 kasan_report_user_access()를 호출하며, 커널 영역이지만 memory_is_poisoned()가 참을 리턴하는 경우, 즉 메모리가 poison된 경우 kasan_report()로 잘못된 접근을 리포트한다.

quarantine

[mail] [commit]

quarantine은 use-after-free를 더 효과적으로 잡기 위한 기능이다. 슬랩 객체를 해제한 경우, KASAN으로 use-after-free를 탐지하려면 해제된 객체는 한동안 할당되지 않아야 한다. 만약 할당과 해제가 매우 빈번하게 일어나는 슬랩 캐시의 경우, 해제되자마자 다시 할당하면  shadow memory를 다시 unpoison하기 때문에 use-after-free를 탐지하기가 어려워진다. 따라서 KASAN은 해제된 객체를 한동안 격리시켜두었다가(?) 나중에 해제한다.

Software tag-based KASAN

[lwn] [mail] [commit]

KASAN은 여러가지 모드가 존재하며 위에서 설명한 방식은 generic KASAN으로, compiler instrumentation을 사용하기 때문에 아키텍처에 의존성 없이 소프트웨어적으로만 작동한다.

이와 달리 Software tag-based방식은 arm64의 TBI (Top Byte Ignore)라는 기능을 활용한 것이다. 아직까지 8바이트 주소 공간은 매우 차고 넘치기 때문에 주소 공간에서 8바이트 모두를 사용하지는 않는데, 이런 점을 활용해 TBI는 MMU가 포인터의 상위 1바이트를 무시하도록 해서 별도의 데이터를 저장할 수 있도록 한다.

Software-based tagging 방식의 KASAN은 top byte에 random한 tag값을 부여하고, 이 tag를 shadow memory에 기록함으로써 메모리 접근마다 top byte의 tag와 shadow memory에 기록된 tag가 일치하는지 확인한다. 또한 이 모드에서는 전체 메모리의 1/8이 아니라 1/16만큼을 shadow memory로 활용하므로 KASAN의 메모리 사용량이 줄어든다.

대신 단점도 있는데, 모든 슬랩 객체가 16바이트 단위로 정렬되어야하며, tag에 1바이트만 사용하므로 태그가 겹칠 수 있다. 다시 말해서 memory corruption이 존재해도 top byte의 tag와 shadow memory의 tag가 우연히 같다면 버그가 발견되지 않을 수 있다. 그리고 아주 약간만 경계를 넘는 out-of-bounds access는 탐지하지 못한다. 태그 하나당 16바이트를 표현하므로 예를 들어 슬랩 객체가 15바이트라면 객체 뒤의 1바이트는 객체에 포함되지는 않지만 태그가 같으므로 탐지할 수 없다.

Hardware tag-based KASAN

[mail] [arm doc about MTE]

software tag 방식은 2018년에 나왔고, 이후에 2019년에 구글이 ARM과 함께 MTE (Memory Tagging Extension)이라는 기능을 발표한 후 2020년에 Hardware tag-based KASAN이 나왔다. Hardware tag 방식은 software 방식과 마찬가지로 TBI 기능을 사용하며, top byte에 랜덤한 태그를 할당하고, 메모리 접근시에 확인한다는 점은 똑같으나 shadow memory와 compiler instrumentation이 아니라 MTE를 사용해서 CPU가 직접 태그가 일치하는지 직접 확인한다고 한다. 아쉽게도 어느 만큼의 메모리를 사용하는지는 자세하게 문서화되어있지 않다. 속도는 하드웨어가 직접 태그를 확인하기 때문에 software tag 보다 훨씬 빠르다.

앞서 말했듯 KASAN은 production에서 돌리기엔 성능 하락과 메모리 사용량 증가가 크다. 그래서 그만큼 테스팅 환경에서는 발견되지 않는 버그를 잡기가 어렵다. Software/Hardware tag 방식의 KASAN 모두 production에서 돌릴 수 있도록 CPU 오버헤드와 메모리 사용량을 줄이는 것이 목표이며, 구글은 안드로이드에서 Hardware tag-based KASAN을 적극적으로 사용할 의지가 있어보인다. [android doc]

Summary

요약하자면 KASAN은 전체 메모리의 1/8을 사용하는 shadow memory에 메모리의 접근 가능 여부를 기록하며(poison/unpoison), compiler instrumentation으로 __asan_loadN(), __asan_storeN()함수를 메모리 접근마다 호출해서 접근이 유효한지 판별한다. 만약 __asan_storeN()을 호출했는데 shadow memory의 값이 0xfb (free된 객체)라면 use-after-free, 0xfc (slub redzone)라면 out-of-bounds access라고 탐지하는 방식이다. 

그리고 use-after-free의 경우 객체가 해제되자마자 다시 할당되면 탐지하기 어렵기 때문에, 일정 기간동안은 다시 할당하지 않고 격리시켜서 (quarantine) uaf의 탐지율을 높인다.

위에서 설명한 KASAN을 generic KASAN이라고 하며,  KASAN은 오버헤드를 줄이기 위한 Software/Hardware tag-based mode를 지원한다. 이 모드들은 메모리 사용량과 CPU 오버헤드를 줄여주는 대신 아주 미미한 out-of-bounds 접근을 탐지할 수가 없고, tag가 겹치는 경우에도 버그를 탐지할 수 없다.

Related Topics

KASAN은 모든 메모리 접근을 확인하는 만큼 성능 저하가 적지 않다. KFENCE (Kernel Electric-Fence)는 슬랩 객체 할당의 일부만 샘플링해서 memory corruption 버그를 잡기 위한 기능으로, 0에 가까운 오버헤드로 버그를 잡아준다. (대신 샘플링 방식이라 버그를 잡으려면 충분한 시간동안 돌려야한다.) [kernel doc]

KCSAN (Kernel Concurrency SANitizer)은 race condition을 잡기 위한 기능이다. 얘는 좀더 높은 버전의 컴파일러가 필요하다. [kernel doc]

KMSAN (Kernel Memory SANitizer)은 uninitialized memory의 사용을 탐지하는 기능인데 아직 mainline에는 없고 리뷰 단계인 기능이다. [github]