First Fit

Reading time: 10 minutes

First Fit

当你在程序中使用 glibc 释放内存时，会使用不同的“bins”来管理内存块。以下是两种常见场景的简化解释：未排序的 bins 和快速 bins。

Unsorted Bins

当你释放一个不是快速块的内存块时，它会进入未排序的 bin。这个 bin 像一个列表，新释放的块会添加到前面（“头”）。当你请求一个新的内存块时，分配器会从未排序的 bin 的后面（“尾”）查看，以找到一个足够大的块。如果未排序的 bin 中的块大于你所需的大小，它会被拆分，前面的部分被返回，剩余的部分留在 bin 中。

示例：

• 你分配 300 字节（a），然后 250 字节（b），然后释放 a 并再次请求 250 字节（c）。
• 当你释放 a 时，它会进入未排序的 bin。
• 如果你再次请求 250 字节，分配器会在尾部找到 a 并将其拆分，返回适合你请求的部分，并将其余部分保留在 bin 中。
• c 将指向之前的 a 并填充 a 的内容。

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

Fastbins

Fastbins用于小内存块。与未排序的bins不同，fastbins将新块添加到头部，形成后进先出（LIFO）行为。如果您请求一个小内存块，分配器将从fastbin的头部提取。

示例：

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，在未排序的 bin 之前进行查询。因此，只有在以下情况下才会达到首次适配场景：

1. 请求的大小 大于 tcache_max（在 64 位系统上默认值为 0x420），或者
2. 相应的 tcache bin 已经满或手动清空（通过分配 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
}

利用方法（在最近的CTF中常见）：

1. 排空 目标大小的 tcache。
2. 释放 一个块，使其进入未排序的桶。
3. 分配 一个稍小的大小 – 分配器将未排序的块拆分。
4. 再次分配 – 剩余部分与现有的使用中块重叠 → UAF。
5. 覆盖敏感字段（函数指针、FILE vtable 等）。

一个实际应用可以在 2024 HITCON Quals Setjmp 挑战中找到，其中使用了这个确切的原语来从 UAF 转向完全控制 __free_hook。

🛡️ 缓解措施与加固

• 安全链接（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. 使用后释放：生成一个用户对象，释放它，生成一个获取已释放块并允许写入的对象，覆盖用户->密码 的位置。重用用户以绕过密码检查
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• 该程序允许创建笔记。一个笔记将包含在 malloc(8) 中的笔记信息（带有可以调用的函数指针）和指向另一个 malloc() 的指针，后者包含笔记的内容。
• 攻击将是创建 2 个笔记（note0 和 note1），其 malloc 内容大于笔记信息大小，然后释放它们以使其进入快速桶（或 tcache）。
• 然后，创建另一个笔记（note2），内容大小为 8。内容将位于 note1 中，因为该块将被重用，我们可以修改函数指针以指向 win 函数，然后使用后释放 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