KFENCE: Kernel Electric-Fence

KASAN: Kernel Address SANitizer

바로 저번 글에서 다룬 KASAN은 메모리 접근 시마다 __asan_loadN(), __asan_storeN()을 호출해서 올바른 접근인지를 검증했다. 그런데 메모리에 읽고 쓸때마다 함수를 실행한다는 건 오버헤드가 크기 때문에 production 서버에서는 사용하기 어렵다. KFENCE는 모든 메모리 접근을 추적하는 대신 슬랩에서 할당하는 객체들 중 일부 샘플들에 대해서만 메모리 관련 버그를 탐지한다. KFENCE는 KASAN이 탐지할 수 있는 버그의 부분집합 정도만 탐지할 수 있다. [mail] [commit]

KFENCE object pool

객체가 2개일 때의 KFENCE pool (잘못 그린거 아님)

KFENCE는 기본적으로 하나의 객체당 하나의 페이지를 사용한다. 이 방식은 GWP-Asan에서 영감을 받은 것이다. 객체 마다 페이지를 할당하면 내부 단편화가 크긴 하지만, 접근하면 안되는 객체의 페이지 테이블 엔트리를 수정하면 객체에 접근했을 때 페이지 폴트가 나게 해서 탐지할 수 있다. 예를 들어서 해제된 객체에 접근할 수 없도록 PTE를 수정하면, 접근 시에 페이지 폴트가 나므로 use-after-free를 탐지할 수 있다.

그리고 객체와 객체 사이에 guard page를 두어서 버퍼 오버플로를 탐지한다. (guard page가 없으면 두 인접한 객체가 모두 할당된 상태일 때 버퍼 오버플로우를 탐지할 수 없다.) 그리고 guard page를 침범한 경우가 아니라, 객체가 존재하는 페이지 내에서 오버플로우가 발생한 경우 (예를 들어 페이지가 4K, 객체가 64바이트일때 65바이트 이상을 덮어쓴 경우)는 할당 전에 객체에 해당하지 않는 부분에 canary라는 특별한 값을 저장해서해서 해당 값이 바뀌었는지 확인한다. 다만 KFENCE는 canary 값이 덮어씌워진 경우는 탐지할 수 있지만, 읽힌 경우는 탐지할 수 없다. 구현 방식의 한계이다.

위 그림은 KFENCE pool에서 할당할 수 있는 객체가 2개일 때를 그림으로 그린 거다. 모든 객체의 앞뒤에 guard page가 존재해서 size * 2 + 1개의 페이지를 사용할 수도 있지만, 편의상 짝수개의 페이지를 사용하기 위해 처음 앞 2개의 페이지는 guard page로 사용한다. 따라서 (size + 1) * 2만큼의 페이지를 사용한다.

Allocation Sampling

KFENCE는 샘플링 기반으로 작동한다. 다시 말해서 슬랩에서 객체를 할당한다고 KFENCE pool에서 무작정 할당을 하는 게 아니라 일정 주기에 따라 KFENCE pool에서 할당한다.

Sampling Interval

샘플링 주기는 kfence.sample_interval 부트 파라미터로 설정할 수 있다. (밀리초 단위)

kfence allocation gate

/* Gates the allocation, ensuring only one succeeds in a given period. */
atomic_t kfence_allocation_gate = ATOMIC_INIT(1);

얘는 kfence에서 객체를 할당할지 말지를 정하는 atomic integer인데, kfence_allocation_gate의 값이 0인 경우에만 할당할 수 있고, 1 이상인 경우에는 해당 샘플링 주기동안 이미 할당된 경우이므로. 스킵한다.

void __init kfence_init(void)
{
[...]
	queue_delayed_work(system_unbound_wq, &kfence_timer, 0);
[...]
}

kfence_allocation_gate의 값은 할당할 때마다 1씩 증가하며, delayed_work으로 sampling interval마다 주기적으로 0으로 초기화된다. 아, 그리고 kfence는 샘플링 주기가 매우 긴 경우를 위해 static branch를 활용해서 한번 할당 후 다음 주기까지는 branch를 계속 확인하지 않도록 최적화할 수 있다. (CONFIG_KFENCE_STATIC_KEYS)

샘플링 주기가 길면 static branch가 괜찮은 최적화지만 샘플링 주기가 너무 짧으면 오히려 Inter-Process Interrupt로 인한 static branch의 오버헤드가 악영향을 미칠 수 있으니 주의하자.

Allocation

슬랩 할당자를 호출했을 때, kfence_alloc()에서 널포인터가 아닌 객체를 반환한 경우 KFENCE pool에서 할당이 된 것이다.

static __always_inline void *slab_alloc_node(struct kmem_cache *s,
		gfp_t gfpflags, int node, unsigned long addr, size_t orig_size)
{
[...]

	object = kfence_alloc(s, orig_size, gfpflags);
	if (unlikely(object))
		goto out;

[...]
        
out:
	slab_post_alloc_hook(s, objcg, gfpflags, 1, &object, init);

	return object;
}

할당 순서도

kfence_alloc()에서 하는 일은 생각보다 간단하다. 우선 할당할 때는 최대한 많은 allocation을 커버하기 위해 샘플링 주기동안 한 번씩만 할당한다. 그리고 kfence pool이 일정 비율 이상 차면, 이미 kfence pool이 커버중인 호출 경로에서 할당하는 객체는 kfence에서 할당하지 않게 해서 최대한 많은 호출 경로를 커버하고자 한다.

kfence_alloc()이 kfence pool에서 객체를 할당하기로 결정했다면, 객체가 해당하는 페이지의 PTE를 수정해서 페이지에 접근할 수 있도록 하고, 페이지 내의 OOB write를 탐지하기 위해 canary를 초기화한다. 그 후 별도의 자료구조에 할당 시의 stack trace를 저장한 후 할당을 마친다.

Free

static void __slab_free(struct kmem_cache *s, struct slab *slab,
			void *head, void *tail, int cnt,
			unsigned long addr)

{
	void *prior;
	int was_frozen;
	struct slab new;
	unsigned long counters;
	struct kmem_cache_node *n = NULL;
	unsigned long flags;

	stat(s, FREE_SLOWPATH);

	if (kfence_free(head))
		return;
[...]

free도 비슷하게 슬랩 할당자의 free slowpath에서 kfence_free()를 호출해서 해제한다.

해제 순서도

우선 슬랩 캐시에서 SLAB_TYPESAFE_BY_RCU 플래그가 설정된 경우에는 kfence_free()가 호출된 이후라도 grace period가 끝나기 전까지는 객체에 접근할 수 있으므로 rcu_guarded_free()로 grace period가 끝난 이후에 객체를 해제한다.

그리고 kfence_free()로 넘어온 주소가 유효하지 않거나, kfence 객체의 상태가 할당중이 아닌 경우에는 invalid free를 리포트한다.

그리고 조금 뒤에 살펴보겠지만, OOB access로 guard page에 접근해서 page fault가 난 경우에는 KFENCE가 guard page를 unprotect해서 스레드가 실행을 계속할 수 있도록 한다. 이렇게 OOB access를 한 경우에는 객체를 해제할 때 unprotected된 guard page를 다시 protect해준다.

그리고 할당할때 초기화한 canary가 덮어씌워진 경우에도 리포트를 한다. 그리고 객체를 해제한 stack trace를 별도의 자료구조에 저장한 후 객체를 protect해서 free 후에 접근한 경우 page fault가 나도록 해서 use-after-free를 탐지할 수 있게 한다. 그러면 해제도 끝이다.

Page Fault

KFENCE에서 page fault는 kfence_handle_page_fault() 함수가 담당한다.

page fault handling도 매우 간단하다. 우선 page fault가 일어나는 경우는 2가지다. 1) guard page에 접근했거나 2) free 상태인 객체에 접근(use-after-free)했거나다.

두 경우 모두 KFENCE는 버그를 리포트한 후, fault가 발생한 페이지를 unprotect한다. 해당 페이지가 guard page인 경우에는 위에서 살펴봤듯 kfence_free()에서 다시 protect해주고, use-after-free인 경우에는 어차피 use-after-free를 이미 탐지했기 때문에, 객체가 다시 해제 후 할당, 해제 되기 전까지는 unprotect된 상태로 남게 된다.

Thoughts

Q: guard page가 kfence pool의 50% 이상을 차지하는게 비효율적으로 보인다. guard page는 물리적인 페이지 하나만 사용하고 모든 guard page를 같은 페이지로 매핑하면 안될까?

A: 라는 생각이 들어서 어제 구현해봤는데, 작동은 되지만 구현이 생각보다 복잡하고 fragile해져서 이대로 두는게 나을 것 같다. 생각보다 할게 많다. 우선 커널은 가상 주소를 물리 주소로 직접 매핑 하기 때문에, 별도에 가상 주소 공간을 사용해야 한다. 그럼 virt_to_page()처럼 직접 매핑된 주소를 예상하는 매크로가 터져서 슬랩 할당자를 일부 수정해야 한다.

Q: KASAN의 quarantine처럼 해제 후 할당되기 까지의 기간이 있으면 UAF를 잡는데 더 도움이 되지 않을까?

A: quarantine 기능을 명시적으로 구현하지는 않지만 kfence_freelist가 LIFO가 아니라 FIFO로 구현되어있어서 비슷한 효과가 날듯.