First Fit

Reading time: 12 minutes

First Fit

glibcを使用してプログラム内のメモリを解放すると、異なる「ビン」がメモリチャンクを管理するために使用されます。ここでは、一般的な2つのシナリオ：未ソートビンとファストビンについての簡略化された説明を示します。

Unsorted Bins

ファストチャンクでないメモリチャンクを解放すると、それは未ソートビンに入ります。このビンは、新しく解放されたチャンクが前方（「ヘッド」）に追加されるリストのように機能します。新しいメモリチャンクを要求すると、アロケータは未ソートビンの後方（「テイル」）を見て、十分な大きさのチャンクを探します。未ソートビンのチャンクが必要なサイズより大きい場合、それは分割され、前の部分が返され、残りの部分はビンに留まります。

例：

• 300バイト（a）を割り当て、その後250バイト（b）を割り当て、aを解放して再度250バイト（c）を要求します。
• aを解放すると、それは未ソートビンに入ります。
• その後再度250バイトを要求すると、アロケータはテイルにあるaを見つけて分割し、リクエストに合う部分を返し、残りをビンに保持します。
• cは以前のaを指し、aの内容で埋められます。

char *a = malloc(300);
char *b = malloc(250);
free(a);
char *c = malloc(250);

Fastbins

Fastbinsは小さなメモリチャンクに使用されます。未ソートのビンとは異なり、fastbinsは新しいチャンクを先頭に追加し、後入れ先出し（LIFO）の動作を作り出します。小さなメモリチャンクを要求すると、アロケータはfastbinの先頭から取得します。

Example:

char *a = malloc(20);
char *b = malloc(20);
char *c = malloc(20);
char *d = malloc(20);
free(a);
free(b);
free(c);
free(d);
a = malloc(20);   // d
b = malloc(20);   // c
c = malloc(20);   // b
d = malloc(20);   // a

🔥 現代のglibcの考慮事項 (tcache ≥ 2.26)

glibc 2.26以降、各スレッドは自分自身のtcacheを保持し、これは未ソートビンの前に照会されます。したがって、ファーストフィットのシナリオは次の条件を満たす場合にのみ到達されます：

1. リクエストされたサイズが**tcache_maxより大きい**（デフォルトで64ビットの0x420）、または
2. 対応するtcacheビンがすでに満杯または手動で空にされている（7つの要素を割り当てて使用中に保持することによって）。

実際のエクスプロイトでは、通常、次のようなヘルパールーチンを追加します：

// Drain the tcache for a given size
for(int i = 0; i < 7; i++) pool[i] = malloc(0x100);
for(int i = 0; i < 7; i++) free(pool[i]);

tcacheが枯渇すると、その後の解放は未整列ビンに移動し、古典的なファーストフィットの動作（テイルサーチ、ヘッド挿入）が再びトリガーされる可能性があります。

🚩 ファーストフィットを使用したオーバーラップチャンクUAFの作成

以下のフラグメント（glibc 2.38でテスト済み）は、未整列ビンのスプリッタを悪用して2つのオーバーラッピングポインタを作成する方法を示しています。これは、単一の解放を解放後書き込みに変換する強力なプリミティブです。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
setbuf(stdout, NULL);

/* 1. prepare 2 adjacent chunks and free the first one */
char *A = malloc(0x420);   // big enough to bypass tcache
char *B = malloc(0x420);
strcpy(A, "AAAA\n");
free(A);                   // A → unsorted

/* 2. request a *smaller* size to force a split of A */
char *C = malloc(0x400);   // returns lower half of former A

/* 3. The remainder of A is still in the unsorted bin.
Another 0x400-byte malloc will now return the *same*
region pointed to by B – creating a UAF/overlap. */
char *C2 = malloc(0x400);

printf("B  = %p\nC2 = %p (overlaps B)\n", B, C2);

// Arbitrary write in B is immediately visible via C2
memset(B, 'X', 0x10);
fwrite(C2, 1, 0x10, stdout);  // prints Xs
}

Exploitation recipe (common in recent CTFs):

1. ターゲットサイズのtcacheを排出します。
2. チャンクを解放して、未ソートのビンに配置します。
3. わずかに小さいサイズを割り当てます – アロケータが未ソートのチャンクを分割します。
4. 再度割り当てます – 残りの部分が既存の使用中のチャンクと重なります → UAF。
5. 敏感なフィールド（関数ポインタ、FILE vtableなど）を上書きします。

実用的なアプリケーションは、2024 HITCON Quals Setjmp チャレンジに見られ、この正確なプリミティブがUAFから__free_hookの完全制御にピボットするために使用されます。

🛡️ 緩和策と強化

• Safe-linking (glibc ≥ 2.32) は、単一リンクのtcache/fastbinリストのみを保護します。未ソート/小/大ビンは依然として生のポインタを格納しているため、ヒープリークを取得できればファーストフィットに基づく重なりが有効です。
• ヒープポインタの暗号化とMTE (ARM64) は、まだx86-64 glibcには影響しませんが、GLIBC_TUNABLES=glibc.malloc.check=3のようなディストリビューションの強化フラグは、一貫性のないメタデータで中止し、単純なPoCを壊す可能性があります。
• 解放時のtcacheの充填 (2024年にglibc 2.41に提案) は、未ソートの使用をさらに減少させます。一般的なエクスプロイトを開発する際は、今後のリリースを監視してください。

その他の参考文献と例

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Use after free: ユーザーオブジェクトを生成し、それを解放し、解放されたチャンクを取得して書き込むオブジェクトを生成し、以前のユーザーのuser->passwordの位置を上書きします。ユーザーを再利用してパスワードチェックをバイパスします。
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• プログラムはノートを作成することを許可します。ノートには、malloc(8)内のノート情報（呼び出すことができる関数へのポインタを含む）と、ノートの内容を持つ別のmalloc()へのポインタがあります。
• 攻撃は、ノート情報サイズよりも大きなmalloc内容を持つ2つのノート（note0とnote1）を作成し、それらを解放してファーストビン（またはtcache）に入れることです。
• 次に、内容サイズ8の別のノート（note2）を作成します。内容はnote1にあり、チャンクが再利用されるため、関数ポインタをwin関数を指すように変更し、その後Use-After-Freeを使用してnote1を呼び出します。
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• メモリを割り当て、希望の値を書き込み、解放し、再割り当てすることが可能で、以前のデータがまだ存在するため、チャンク内の新しい期待される構造に従って扱われ、値を設定してフラグを取得することが可能になります。
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• この場合、特定のチャンク内に4を書き込む必要があります。これは、すべてを強制的に解放した後でも最初に割り当てられたものです。新しく割り当てられた各チャンクの配列インデックス内の番号が保存されます。次に、4つのチャンク（最初に割り当てられたものを含む）を割り当て、最後のものに4を入れ、解放して最初のものの再割り当てを強制します。これにより、最後に解放されたチャンクが使用され、その中に4が入っています。
• 2024 HITCON Quals Setjmpの書き込み（Quarkslab） – 実用的なファーストフィット/未ソートスプリット重なり攻撃: https://ctftime.org/writeup/39355
• Angstrom CTF 2024 heapify の書き込み – 未ソートビンの分割を悪用してlibcをリークし、重なりを得る: https://hackmd.io/@aneii11/H1S2snV40