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

その後、カーネルがページフォルトやその他のメモリ関連のシステムコールを処理する際、アドレスのみに基づいてVMAを高速に検索する必要があります。以前は、VMAは赤黒木を使用して管理されていました。しかし、Linuxカーネルバージョン6.1以降、メイプルツリーへの移行が行われました。[メイプルツリー][mt]は、重複しない範囲を格納するために最適化された、RCUセーフなBツリーデータ構造です。それにもかかわらず、その複雑な性質はコードベースに複雑さをもたらし、StackRot脆弱性を引き起こします。

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

その中核として、メイプルツリーはメイプルノードで構成されています。ツリーの構造は複雑かもしれませんが、この複雑さはStackRotバグとは無関係であることに注意することが重要です。したがって、この記事全体を通して、メイプルツリーは単一のノード、つまりルートノードのみで構成されていると仮定します。

このルートノードは最大16個の区間を含むことができます。これらの区間は、ギャップを表すか、VMAを指すかのいずれかです。ギャップも区間としてカウントされるため、すべての区間は連続的に接続され、ノード構造内に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 */
};

Regarding concurrent modification, the maple tree imposes a specific
restriction, that is, an exclusive lock must be held by writers (*Rule W*). In
the case of the VMA tree, the exclusive lock corresponds to the MM write lock.
As for readers, two options are available. The first option involves holding
the MM read lock (*Rule A1*), which results in the writer being blocked by the
MM read-write lock. Alternatively, the second option is to enter the RCU
critical section (*Rule A2*). By doing so, the writer is not blocked, and
readers can continue their operations since the maple tree is RCU-safe. While
most existing VMA accesses opt for the first option (i.e., Rule A1), Rule A2 is
employed in a few performance-critical scenarios, such as lockless page faults.

However, there is an additional aspect that requires particular attention,
which pertains to stack expansion. The stack represents a memory area that is
mapped with the MAP_GROWSDOWN flag, indicating automatic expansion when an
address below the region is accessed. In such cases, the start address of the
corresponding VMA is adjusted, as well as the associated interval within the
maple tree. Notably, these adjustments are made without holding the MM write
lock.```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;
}

// ...

その結果、スタック拡張によってギャップを解消できます。このような状況では、メイプルノード内のギャップ間隔を削除する必要があります。メイプルツリーは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イテレーションを見つけることです：
 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コールバック内で発生します。

これには2つの課題があります：(i) 古いノードがいつ解放されるかを判断すること、(ii) 古いノードが解放される前にVMAイテレーションが完了しないようにすることです。

最初の問題は比較的簡単です。カーネルでは、`synchronize_rcu()`関数を使用してRCU grace periodの終了を待機し、既存のすべての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: From UAFBR to UAF](https://assets.kitploit.com/production/public/readmes/28620/6791d2c105f1fc504247b668317c7d23c3141c92456dab2fb2e54f7f70e16e15.png)

### Step 1: From slab UAF to page UAF

UAFがスラブ内で動作しているとします。CONFIG_SLAB_MERGE_DEFAULTが有効で、メイプルノードのスラブがkmalloc-256とマージされる場合、古いノード内の内容は、kmalloc-256から新しい構造体を割り当て、ユーザ空間データで埋めることで制御できます。ただし、CONFIG_SLAB_MERGE_DEFAULTが設定されていない場合は、別のアプローチが必要です。この場合、解放されたノードのページをページアロケータに戻し、新しいページを割り当てて適宜埋めることで古いノードを制御できるようにする必要があります。

VMAツリーにはノードが一つしか含まれないことを思い出してください。したがって、`fork()`/`clone()`を利用することで、複数のVMAツリーと同数のメイプルノードが生成されます。一つのスラブがM個のメイプルノードを含み、M個のノードごとに1つのノードを保持し、他のすべてのノードを`exit()`で解放すると仮定すると、残りのノードはそれぞれのスラブ内で唯一のノードになります。最初は、これらのスラブはCPUのパーシャルリストに存在します。パーシャルリストがその容量に達すると、スラブは対応するNUMAノードのパーシャルリストにフラッシュバックされます。

スラブ内の最後のメイプルノードが解放されると、スラブは空になります。このスラブがNUMAノードのパーシャルリストに存在し、その特定のNUMAノードのパーシャルリストがすでに最大容量である場合、ページは直ちにページアロケータに戻されます。その結果、スラブUAFはページUAFのシナリオに変わります。解放されたページ内の内容は、`msgsnd()`を介してデータを送信することで操作できます。これにより、弾性オブジェクトが割り当てられ、提供されたユーザデータで直接埋められます。```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;
}

// ...

![Step 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/HEAD/exp)から入手できます。詳細については、そのREADMEファイルを参照してください。