/* size: 136, cachelines: 3, members: 14 */
    /* forced alignments: 1 */
    /* last cacheline: 8 bytes */

그 후, 커널은 페이지 폴트나 기타 메모리 관련 시스템 호출을 처리할 때 주소만으로 VMA를 빠르게 조회해야 합니다. 이전에는 VMA가 레드-블랙 트리(red-black trees)로 관리되었습니다. 그러나 Linux 커널 버전 6.1부터는 메이플 트리(maple trees)로의 전환이 이루어졌습니다. [메이플 트리][mt]는 겹치지 않는 범위를 저장하도록 최적화된 RCU-안전 B-트리 데이터 구조입니다. 그럼에도 불구하고, 이들의 복잡한 특성은 코드베이스에 복잡성을 더하고 StackRot 취약점을 유발합니다.

 [mt]: https://docs.kernel.org/6.4/core-api/maple_tree.html

핵심적으로, 메이플 트리는 메이플 노드들로 구성됩니다. 트리의 구조는 복잡할 수 있지만, 이러한 복잡성은 StackRot 버그와 아무 관련이 없다는 점에 유의해야 합니다. 따라서 이 글 전체에서는 메이플 트리가 단 하나의 노드, 즉 루트 노드로만 구성되어 있다고 가정합니다.

이 루트 노드는 최대 16개의 구간을 포함할 수 있습니다. 이 구간들은 각각 갭(gap)을 나타내거나 VMA를 가리킬 수 있습니다. 갭도 구간으로 간주되므로 모든 구간은 순차적으로 연결되며, 그 결과 노드 구조 내에는 피벗(pivot)이라고도 알려진 15개의 끝점만 필요합니다. 맨 왼쪽 끝점과 맨 오른쪽 끝점은 부모 노드에서 가져올 수 있으므로 생략된다는 점에 유의하세요.```c
struct maple_range_64 {
        struct maple_pnode *       parent;               /*     0     8 */
        long unsigned int          pivot[15];            /*     8   120 */
        /* --- cacheline 2 boundary (128 bytes) --- */
        union {
                void *             slot[16];             /*   128   128 */
                struct {
                        void *     pad[15];              /*   128   120 */
                        /* --- cacheline 3 boundary (192 bytes) was 56 bytes ago --- */
                        struct maple_metadata meta;      /*   248     2 */
                };                                       /*   128   128 */
        };                                               /*   128   128 */

        /* size: 256, cachelines: 4, members: 3 */
};

동시 수정(concurrent modification)과 관련하여, maple tree는 특정 제약을 부과한다. 즉, 쓰기 작업자는 배타적 잠금 (*Rule W*)을 보유해야 한다. VMA 트리의 경우, 배타적 잠금은 MM 쓰기 잠금에 해당한다. 읽기 작업자에 대해서는 두 가지 옵션이 있다. 첫 번째 옵션은 MM 읽기 잠금 (*Rule A1*)을 보유하는 것으로, 이 경우 MM 읽기-쓰기 잠금에 의해 쓰기 작업자가 차단된다. 두 번째 옵션은 RCU 임계 구역 (*Rule A2*)에 진입하는 것이다. 이렇게 하면 쓰기 작업자가 차단되지 않으며, maple tree가 RCU에 안전하므로 읽기 작업자는 작업을 계속할 수 있다. 대부분의 기존 VMA 접근 방식은 첫 번째 옵션(즉, Rule A1)을 선택하지만, Rule A2는 잠금 없는 페이지 폴트(lockless page faults)와 같은 소수의 성능에 민감한 시나리오에서 사용된다.

그러나 특별한 주의가 필요한 추가적인 측면이 있으며, 이는 스택 확장(stack expansion)에 관한 것이다. 스택은 MAP_GROWSDOWN 플래그로 매핑된 메모리 영역을 나타내며, 이는 영역 아래의 주소에 접근할 때 자동으로 확장됨을 의미한다. 이러한 경우 해당 VMA의 시작 주소와 maple tree 내의 관련 구간도 함께 조정된다. 주목할 점은 이러한 조정이 MM 쓰기 잠금을 보유하지 않은 채 이루어진다는 것이다.```c
static inline
void do_user_addr_fault(struct pt_regs *regs,
                        unsigned long error_code,
                        unsigned long address)
{
	// ...

	if (unlikely(!mmap_read_trylock(mm))) {
		// ...
	}
	// ...
	if (unlikely(expand_stack(vma, address))) {
		// ...
	}

	// ...
}

if (prev) {
	if (!(prev->vm_flags & VM_GROWSDOWN) &&
	    vma_is_accessible(prev) &&
	    (address - prev->vm_end < stack_guard_gap))
		return -ENOMEM;
}

// ...

그 결과, 스택 확장은 갭을 제거할 수 있습니다. 이러한 상황에서는 maple node 내부의
갭 구간을 제거해야 합니다. maple tree는 RCU-safe하므로 노드를 제자리에서
덮어쓰는 것은 불가능합니다. 대신 새 노드가 생성되어 노드 교체가 이루어지며,
이전 노드는 이후 RCU 콜백을 통해 파괴됩니다.```c
static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
{
	// ...

	if ((wr_mas->offset_end - mas->offset <= 1) &&
	    mas_wr_slot_store(wr_mas))           // <-- in-place update
		return;
	else if (mas_wr_node_store(wr_mas))      // <-- node replacement
		return;

	// ...
}

## 수정

저는 6월 15일에 이 취약점을 Linux 커널 보안 팀에 보고했습니다.
그 후, 이 버그를 해결하는 과정은 Linus Torvalds가 주도했습니다.
복잡성 때문에 합의를 얻은 패치 세트를 개발하는 데 거의 2주가 걸렸습니다.

6월 28일, Linux 커널 6.5의 머지 윈도우 기간 동안 해당 수정 사항이
Linus의 트리에 병합되었습니다. Linus는 패치 시리즈를 기술적 관점에서
설명하는 [포괄적인 머지 메시지][fix]를 제공했습니다.

 [fix]: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=9471f1f2f50282b9e8f59198ec6bb738b4ccc009

이 패치들은 이후 안정 커널([6.1.37][6.1], [6.3.11][6.3], [6.4.1][6.4])로
백포트되어 7월 1일에 "Stack Rot" 버그를 효과적으로 해결했습니다.

 [6.1]: https://lore.kernel.org/stable/2023070133-create-stainless-9a8c@gregkh/T/
 [6.3]: https://lore.kernel.org/stable/2023070146-endearing-bounding-d21a@gregkh/T/
 [6.4]: https://lore.kernel.org/stable/2023070140-eldercare-landlord-133c@gregkh/T/

## 익스플로잇

이 익스플로잇은 주로 Google kCTF 챌린지를 대상으로 하며, 특히
CONFIG_PREEMPT와 CONFIG_SLAB_MERGE_DEFAULT가 모두 설정되지 않은 경우를 다룹니다.
StackRot을 익스플로잇하려면 다음 기준을 충족하는 VMA 반복(iteration)을 찾는 것이
가장 중요한 작업입니다:
 1. 반복의 타이밍을 제어할 수 있어야 합니다. 이 제어를 통해 VMA 반복 중에
    RCU 유예 기간(grace period)이 종료되도록 보장할 수 있습니다.
 2. 반복이 VMA 구조체에서 특정 정보를 검색하고 해당 정보를 사용자 공간으로
    반환해야 합니다. 이 기능을 통해 maple 노드의 UAF 취약점을 악용하여
    일부 커널 주소를 유출할 수 있습니다.
 3. 반복이 VMA 구조체의 특정 함수 포인터를 호출해야 합니다. 이 특별한 기능은
    maple 노드의 UAF를 악용하여 커널 모드 프로그램 카운터(PC)를 제어할 수
    있게 해줍니다.

선택된 VMA 반복은 `/proc/[pid]/maps`의 내용을 생성하는 반복입니다.
다음 섹션에서는 이 반복이 위 기준을 어떻게 충족하는지 보여줍니다.

### 0단계: UAFBR에서 UAF로

VMA 반복 중에는 VMA 트리의 루트 노드에 대한 참조가 획득되고, 반복은 해당
슬롯들을 통해 진행됩니다. 따라서 VMA 반복 중에 별도의 CPU에서 다른 스레드의
스택 확장을 트리거하면 노드 교체가 동시에 시작될 수 있습니다. 이 시점에서
이전 노드에 접근하는 것은 RCU에 의한 use-after-free(UAFBR) 상황으로 간주됩니다.
그러나 실제 문제는 RCU 콜백에서 이전 노드가 실제로 해제될 때 발생합니다.

여기에는 두 가지 과제가 있습니다: (i) 이전 노드가 언제 해제되는지 확인하는 것과
(ii) 이전 노드가 해제되기 전에 VMA 반복이 완료되지 않도록 보장하는 것입니다.

첫 번째 질문은 비교적 간단합니다. 커널에서 `synchronize_rcu()` 함수를 사용하여
RCU 유예 기간이 종료될 때까지 대기할 수 있으며, 이를 통해 기존의 모든 RCU
콜백이 호출되었음을 보장할 수 있습니다. 사용자 공간에서는 궁극적으로
`synchronize_rcu()`를 호출하는 시스템 콜을 동일한 목적으로 사용할 수 있습니다.
따라서 그러한 시스템 콜이 종료되면 이전 노드가 해제되었음을 알 수 있습니다.
특히, `membarrier(MEMBARRIER_CMD_GLOBAL, 0, -1)`라는 시스템 콜은 오직
`synchronize_rcu()`만 호출합니다.```c
SYSCALL_DEFINE3(membarrier, int, cmd, unsigned int, flags, int, cpu_id)
{
	// ...

	switch (cmd) {
	// ...
	case MEMBARRIER_CMD_GLOBAL:
		/* MEMBARRIER_CMD_GLOBAL is not compatible with nohz_full. */
		if (tick_nohz_full_enabled())
			return -EINVAL;
		if (num_online_cpus() > 1)
			synchronize_rcu();
		return 0;
	// ...
	}
}

/*
 * Print the dentry name for named mappings, and a
 * special [heap] marker for the heap:
 */
if (file) {
	seq_pad(m, ' ');
	/*
	 * If user named this anon shared memory via
	 * prctl(PR_SET_VMA ..., use the provided name.
	 */
	if (anon_name)
		seq_printf(m, "[anon_shmem:%s]", anon_name->name);
	else
		seq_file_path(m, file, "\n");
	goto done;
}

// ...

이 단계는 다음 그림에 나와 있습니다:

![Step 0: UAFBR에서 UAF로](https://assets.kitploit.com/production/public/readmes/28620/6791d2c105f1fc504247b668317c7d23c3141c92456dab2fb2e54f7f70e16e15.png)

### Step 1: slab UAF에서 page UAF로

이제 slab 내에서 UAF가 동작합니다. CONFIG_SLAB_MERGE_DEFAULT가
활성화되어 있고 maple 노드의 slab이 kmalloc-256과 병합되면,
이전 노드 내의 내용은 kmalloc-256에서 새 구조체를 할당하고
이를 사용자 공간 데이터로 채워 제어할 수 있습니다. 그러나
CONFIG_SLAB_MERGE_DEFAULT가 설정되지 않은 경우에는 대체 접근 방식이 필요합니다.
이 경우, 해제된 노드의 페이지를 페이지 할당자로 반환해야 하며,
새 페이지를 할당하고 그에 따라 채움으로써 이전 노드를 제어할 수
있습니다.

VMA 트리에는 노드가 하나만 포함된다는 점을 기억하십시오. 따라서
`fork()`/`clone()`을 활용하면 여러 VMA 트리와 동일한 수의 maple 노드가
생성됩니다. 하나의 slab이 M개의 maple 노드를 포함한다고 가정할 때, M개
노드 중 하나의 노드를 유지하고 다른 모든 노드는 `exit()`을 통해 해제하면,
나머지 노드들이 각각의 slab 내에서 유일한 노드가 됩니다. 처음에는 이
slab들이 CPU의 partial 목록에 상주합니다. partial 목록이
용량에 도달하면 slab들은 해당 NUMA 노드의 partial 목록으로 다시
플러시됩니다.

slab 내의 마지막 maple 노드가 해제되면 slab은 비어 있게 됩니다. 이
slab이 NUMA 노드의 partial 목록에 있고, 해당 NUMA 노드의 partial 목록이
이미 최대 용량이라면, 페이지는 즉시
페이지 할당자로 반환됩니다. 결과적으로 slab UAF는
page UAF 시나리오로 변환됩니다. 해제된 페이지 내의 내용은
`msgsnd()`를 통해 일부 데이터를 전송하여 조작할 수 있습니다. `msgsnd()`는
elastic 객체를 할당하고 제공된 사용자 데이터로 직접 채웁니다.```c
static void __slab_free(struct kmem_cache *s, struct slab *slab,
			void *head, void *tail, int cnt,
			unsigned long addr)

{
	// ...

	if (unlikely(!new.inuse && n->nr_partial >= s->min_partial))
		goto slab_empty;

	// ...
	return;

slab_empty:
	// ...
	discard_slab(s, slab);
}

if (vma->vm_ops && vma->vm_ops->name) {
	name = vma->vm_ops->name(vma);
	if (name)
		goto done;
}

// ...

![3단계: UAF에서 루트 권한으로](https://assets.kitploit.com/production/public/readmes/28620/d9c03475803bb799f2b594935d118d73f2547ea4dcf5b40c54e1454324575a0f.png)

가젯 구성은 다음과 같습니다:
 1. 스택 피벗: `movq %rbx, %rsi; movq %rbp, %rdi; call
    __x86_indirect_thunk_r13` -> `pushq %rsi; jmp 46(%rsi)` -> `popq %rsp; ret`
    -> `popq %rsp; ret`, 여기서 %rdi, %rbx, %r13은 _처음에_ 사용자 제어 가능한
    데이터를 가리킵니다.
 2. 루트 권한 획득: `popq %rdi; ret` -> `prepare_kernel_cred` -> `popq
    %rdi; ret` -> `movq %rax, (%rdi); ret`, 여기서 %rdi는 _이제_
    스택 상단을 가리키며; `popq %rdi; ret` -> `commit_creds`, 사실상
    `commit_creds(prepare_kernel_cred(&init_task))`를 실행합니다.
 3. 컨테이너 탈출: `popq %rdi; ret` -> `find_task_by_vpid` -> `popq %rdi;
    ret` -> `movq %rax, (%rdi); ret`, 여기서 %rdi는 _이제_ 스택 상단을 가리킵니다;
    `popq %rdi; ret` -> `popq %rsi; ret` -> `switch_task_namespaces`,
    사실상 `switch_task_namespaces(find_task_by_vpid(1),
    &init_nsproxy)`를 수행합니다.
 4. mm 잠금 해제: `popq %rax; ret` -> `movq %rbp, %rdi; call
    __x86_indirect_thunk_rax`, 여기서 %rbp는 원래 seq_file을 가리킵니다;
    `popq %rax; ret` -> `m_stop`, 사실상 `m_stop(seq_file, ..)`를 실행합니다.
 5. 사용자 공간으로 복귀: `swapgs_restore_regs_and_return_to_usermode`를 사용하고,
    `execve()`를 호출하여 셸을 얻습니다.

마지막으로, `nsenter --mount=/proc/1/ns/mnt`를 사용하여 마운트 네임스페이스를 복원하고
`cat /flag/flag`로 플래그를 얻습니다.

### 소스 코드

전체 익스플로잇 소스는 [여기](https://github.com/lrh2000/stackrot/blob/master/exp)에서 확인할 수 있습니다. 자세한 내용은
해당 README 파일을 참조하십시오.