Linuxカーネル6.1から6.4におけるスタック拡張の処理に欠陥が見つかり、「Stack Rot」と呼ばれています。仮想メモリ領域の管理を担当するメイプルツリーは、MM書き込みロックを適切に取得せずにノードの置き換えが行われる可能性があり、use-after-freeの問題を引き起こします。特権のないローカルユーザーがこの欠陥を利用してカーネルを侵害し、権限を昇格させる可能性があります。
StackRotはメモリ管理サブシステムで見つかったLinuxカーネルの脆弱性であるため、ほぼすべてのカーネル設定に影響を与え、トリガーに必要な権限は最小限です。ただし、メイプルノードはRCUコールバックを使用して解放され、実際のメモリ解放はRCU猶予期間まで遅延されることに注意が必要です。結果として、この脆弱性の悪用は困難であると考えられています。
私の知る限り、現在のところ、use-after-free-by-RCU（UAFBR）バグを標的とした公開エクスプロイトは存在しません。これは、CONFIG_PREEMPTやCONFIG_SLAB_MERGE_DEFAULT設定が存在しない場合でも、UAFBRバグが悪用可能であることが証明された初めての事例です。特筆すべきは、このエクスプロイトがGoogle kCTF VRPが提供する環境（bzImage_upstream_6.1.25、config）で正常に実証されたことです。
StackRotの脆弱性は、VMAツリー構造が赤黒木からメイプルツリーに変更されたバージョン6.1以降、Linuxカーネルに存在しています。
mmap()システムコールを使用してメモリマッピングを確立するたびに、カーネルは対応する仮想メモリ領域（VMA）を表すためにvm_area_structと呼ばれる構造体を生成します。この構造体には、フラグ、プロパティ、およびマッピングに関連するその他の関連詳細を含むさまざまな情報が格納されます。```c
struct vm_area_struct {
long unsigned int vm_start; /* 0 8 /
long unsigned int vm_end; / 8 8 /
struct mm_struct * vm_mm; / 16 8 /
pgprot_t vm_page_prot; / 24 8 /
long unsigned int vm_flags; / 32 8 /
union {
struct {
struct rb_node rb attribute((aligned(8))); / 40 24 /
/ --- cacheline 1 boundary (64 bytes) --- /
long unsigned int rb_subtree_last; / 64 8 /
} attribute((aligned(8))) shared attribute((aligned(8))); / 40 32 /
struct anon_vma_name * anon_name; / 40 8 /
} attribute((aligned(8))); / 40 32 /
/ --- cacheline 1 boundary (64 bytes) was 8 bytes ago --- /
struct list_head anon_vma_chain; / 72 16 /
struct anon_vma * anon_vma; / 88 8 /
const struct vm_operations_struct * vm_ops; / 96 8 /
long unsigned int vm_pgoff; / 104 8 /
struct file * vm_file; / 112 8 /
void * vm_private_data; / 120 8 /
/ --- cacheline 2 boundary (128 bytes) --- /
atomic_long_t swap_readahead_info; / 128 8 /
struct vm_userfaultfd_ctx vm_userfaultfd_ctx; / 136 0 */
/* size: 136, cachelines: 3, members: 14 */
/* forced alignments: 1 */
/* last cacheline: 8 bytes */
} attribute((aligned(8)));
その後、カーネルがページフォルトやその他のメモリ関連のシステムコールを処理する際、アドレスのみに基づいて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 */
};
上記のように、maple_range_64 構造体はメイプルノードを表します。ピボットに加えて、スロットはノードがリーフノードとして機能する場合は VMA 構造体を参照するために、ノードが内部ノードとして機能する場合は他のメイプルノードを参照するために使用されます。間隔がギャップに対応する場合、スロットには単に NULL 値が含まれます。ピボットポイントとスロットの配置は、以下に示すように視覚化できます：```
Slots -> | 0 | 1 | 2 | ... | 12 | 13 | 14 | 15 |
┬ ┬ ┬ ┬ ┬ ┬ ┬ ┬ ┬
│ │ │ │ │ │ │ │ └─ Implied maximum
│ │ │ │ │ │ │ └─ Pivot 14
│ │ │ │ │ │ └─ Pivot 13
│ │ │ │ │ └─ Pivot 12
│ │ │ │ └─ Pivot 11
│ │ │ └─ Pivot 2
│ │ └─ Pivot 1
│ └─ Pivot 0
└─ Implied minimum
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))) {
// ...
}
// ...
}
通常、スタックVMAとその隣接VMAの間にはギャップが存在します。これはカーネルがstack guardを実施するためです。このシナリオでは、スタックを拡張する際、maple node内のピボット値のみを更新する必要があり、この処理はアトミックに実行できます。ただし、隣接VMAもMAP_GROWSDOWNフラグを持っている場合、stack guardは実施されません。```c int expand_downwards(struct vm_area_struct *vma, unsigned long 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;