musl libc 堆管理器 mallocng 详解 (Part I)
0. 前言
本系列文章是笔者 musl libc 堆管理器 mallocng 的学习笔记。文章数量未定，预计包含堆块结构分析、malloc / free 实现代码、漏洞利用和相关 CTF 题目等内容。
自从 DEF CON CTF Qualifier 2021 出了一道 mallocng 堆题目 mooosl 后，最近一段时间国内各种 CTF 竞赛也涌现了许多类似的题目。趁着这个机会，再加上笔者以前研究过 musl libc 旧版堆管理器，最近抽空研究了一下 mallocng 堆管理器。
说实话，研究 mallocng 还是比较辛苦的，因为官方几乎没有提供任何技术文档，只有几百字的 High-level design 说明。此外，mallocng 源码写得比较粗糙，有些关键字段还是直接通过 hard-encoded 数组索引来引用的。
为此，笔者编写了一个可以解析 mallocng 堆块信息的 GDB 插件 muslheap，有兴趣的师傅可以安装试用：https://github.com/xf1les/muslheap。
1. mallocng 堆管理器
1.1 概述
mallocng 是 musl libc v1.2.1 开始实装的新型堆内存管理器，mallocng 重新设计堆内存的管理方式以及数据结构，增加各种合法性检验，强化了针对 heap overflow、double free 等堆相关漏洞的防御措施。有关 musl libc 的介绍可以参考笔者以前写的《从一次 CTF 出题谈 musl libc 堆漏洞利用 》。
相对于旧版堆管理器（以及它的堂兄弟 glibc 堆管理器 ptmalloc2），mallocng 在各方面上存在着较大的差异，这是因为 mallocng 代码是完全重新编写的。
最大的差异在于内存管理方式：mallocng 管理多个大内存块 group，每个大内存块切割为数个长度固定的小内存块 slot，然后将这些小内存块作为堆块分配给用户（对比： ptmalloc2 堆块都是从一个固定的大内存块 top chunk 按需切割长度不等的小内存块）。
至于堆块管理方式，mallocng 使用一些字段 metadata 用来保存堆块的信息（例如长度大小、是否已释放等）。metadata 分为两种：一部分 metadata 位于堆块上面，这些 metadata 称为 in-band metadata（类似于 ptmalloc2 堆块的 size, prev_size 字段）；除此之外的所有 metadata 则单独储存于一块特殊内存区域，称为 out-of-band metadata。
1.2 group
+-> +-+-+-+-+-+-+-+-+-+-+-+-+ -+ <--+
| | meta | | |
| +-+-+-+-+-+-+-+-+-+-+-+-+ | 0x10 bytes | group header
| | active_idx / pad | | |
| +-+-+-+-+-+-+-+-+-+-+-+-+ -+ <--+
| | |
| + +
| | |
| + slot 0 +
| | |
| + +
| | |
| +-+-+-+-+-+-+-+-+-+-+-+-+ -+
| | | |
| + + |
| | | |
| + slot 1 + | stride
| | | |
| + + |
| | | |
group | +-+-+-+-+-+-+-+-+-+-+-+-+ -+
| . .
| . .
| . .
| . .
| . .
| . .
| . .
| . . .
| . .
| +-+-+-+-+-+-+-+-+-+-+-+-+
| | |
| + +
| | |
| + slot N +
| | |
| + +
| | |
+-> +-+-+-+-+-+-+-+-+-+-+-+-+
group 是一类由 mallocng 管理、用于分配堆块的大内存块。每个 group 被划分为若干个大小相等的小内存块，称为 slot，每个 slot 的地址对齐 16 字节。这里的 slot 就是我们从 malloc 分配得到的堆块了。
slot 的编号称为 index。按照先后顺序，group 上面的 slot 分别编号为0, 1, 2, …, N。一个 group 最多可以拥有 32 个 slot。
slot 的大小称为 stride。每个 stride 对应一个 sizeclass 编号。一共有 48 个 sizeclass，其编号分别为 0 ~ 47，对应 stride 范围为 0x10 ~ 0x1fff0 (MMAP_THRESHOLD)。
| sizeclass | stride | sizeclass | stride | sizeclass | stride | sizeclass | stride |
|---|---|---|---|---|---|---|---|
| 1 | 0x20 | 13 | 0x140 | 25 | 0xaa0 | 37 | 0x5540 |
| 2 | 0x30 | 14 | 0x190 | 26 | 0xcc0 | 38 | 0x6650 |
| 3 | 0x40 | 15 | 0x1f0 | 27 | 0xff0 | 39 | 0x7ff0 |
| 4 | 0x50 | 16 | 0x240 | 28 | 0x1240 | 40 | 0x9240 |
| 5 | 0x60 | 17 | 0x2a0 | 29 | 0x1540 | 41 | 0xaaa0 |
| 6 | 0x70 | 18 | 0x320 | 30 | 0x1990 | 42 | 0xccc0 |
| 7 | 0x80 | 19 | 0x3f0 | 31 | 0x1ff0 | 43 | 0xfff0 |
| 8 | 0x90 | 20 | 0x480 | 32 | 0x2480 | 44 | 0x12480 |
| 9 | 0xa0 | 21 | 0x540 | 33 | 0x2aa0 | 45 | 0x15540 |
| 10 | 0xc0 | 22 | 0x660 | 34 | 0x3320 | 46 | 0x19980 |
| 11 | 0xf0 | 23 | 0x7f0 | 35 | 0x3ff0 | 47 | 0x1fff0 |
若用户请求的内存大小超过MMAP_THRESHOLD，mallocng 直接使用 mmap 分配一个只有一个 slot 的特殊 group（one-slot group）。这类 group 的 sizeclass 编号为特殊值 63。
所有 group 的开头都有一个group header（长度 0x10 byte），mallocng 内部表示为group结构体。
// src/malloc/mallocng/meta.h:17
struct group {
struct meta *meta; <-------------
unsigned char active_idx:5;
char pad[UNIT - sizeof(struct meta *) - 1];
unsigned char storage[];
};
group结构体的开头是 meta 指针。该指针十分重要，它指向的meta结构体保存着 out-of-band metadata。
1.3 meta
meta 结构体储存着 out-of-band metadata，包括 sizeclass、slot 使用状况等。所有的 group 拥有一个且唯一一个 meta。
struct meta {
// 双向链表指针
struct meta *prev, *next;
// group 指针
struct group *mem;
// slot 使用状况
volatile int avail_mask, freed_mask;
// 最后一个 slot 的 index
uintptr_t last_idx:5;
// group 是否能够释放
uintptr_t freeable:1;
// sizeclass
uintptr_t sizeclass:6;
// group MMAP 内存大小
// 若为零，表示 group 不是位于 MMAP 内存
uintptr_t maplen:8*sizeof(uintptr_t)-12;
};
mallocng 主要通过 meta 和 active 双向链表来管理 group。
active 是位于__malloc_context全局结构体中的 meta 双向链表指针数组，其下标为 sizeclass 编号。按照 sizeclass 编号0~47，所有的 meta 结构体都会链接到对应的active双向链表中（sizeclass 编号为 63 的one-slot group除外）。
// src/malloc/mallocng/meta.h:41
struct malloc_context {
<......>
struct meta *active[48]; <----------------
<......>
}
// src/mallocng/malloc.h:40
struct malloc_context ctx = { 0 };
// src/mallocng/glue.h:18
#define ctx __malloc_context
（注：mallocng 中的__malloc_context相当于 ptmalloc2 中的main_arena，记录 mallocng 堆管理器的全局信息）
mallocng 分配堆块时，首先将用户请求的大小转换成对应的 sizeclass，然后按照一定的算法从active链表选择适合的 meta、根据 out-of-band metadata 查找 meta 对应 group 的空闲 slot，最后将 slot 作为堆块分配给用户。
类似于 group 和 slot，每个 meta 都是从一些大内存块 meta_arena 分割出来的小内存块，可以视为一种特殊的 group。
+-> +-+-+-+-+-+-+-+-+-+-+-+-+ -+ <--+
| | check | | |
| +-+-+-+-+-+-+-+-+-+-+-+-+ | |
| | next | | 0x18 bytes | meta_arena header
| +-+-+-+-+-+-+-+-+-+-+-+-+ | |
| | nslots | | |
| +-+-+-+-+-+-+-+-+-+-+-+-+ -+ <--+
| | |
| + +
| | |
| + meta 0 +
| | |
| + +
| | |
| +-+-+-+-+-+-+-+-+-+-+-+-+
| | |
| + +
| | |
| + meta 1 +
| | |
| + +
| | |
| +-+-+-+-+-+-+-+-+-+-+-+-+
| . .
| . .
| . .
| . .
| . .
| . .
| . .
| . . .
| . .
| +-+-+-+-+-+-+-+-+-+-+-+-+
| | |
| + +
| | |
| + meta N +
| | |
| + +
| | |
+-> +-+-+-+-+-+-+-+-+-+-+-+-+
为了防止用户通过堆溢出篡改 meta，meta_arena 所在的内存空间是独立于 group 的。
struct meta_area {
uint64_t check;
struct meta_area *next;
int nslots;
struct meta slots[];
};
1.4 group 和 meta 的内存分布
TBA
1.5. slot
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| meta | <----+ <----- group header
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
. . |
. . |
. . |
. . |
+---------> . . . . . . . . +-+-+-+-+-+-+-+-+ |
| . | 0 |7|I| OFF |---+ | <----- slot header
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
| |///////////////////////////////| | |
| |///////////////////////////////| | |
| |///////////////////////////////| | |
| |///////////(UNUSED)////////////| | |
| |///////////////////////////////| | |
| |///////////////////////////////| | |
| +-> |///////////////+-+-+-+-+-+-+-+-+ | |
| | |///////////////| 0 |R|I| OFF |---|--+ <----- in-band meta
| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ <-+ <----- p
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
slot |[chunk]| | user data |
| | | |
| | | |
| | | |
| | | |
| | | +-+-+-+-+-+-+ -+
| | | | 0 |///////| |
| +-> +-+-+-+-+-+-+-+-+-+-+-+-+///////| |
| |///////////////////////////////| |
| |///////////////////////////////| |
| |///////////(UNUSED)////////////| |
| |///////////////////////////////| | reserved size
| |///////////////////////////+-+-+ |
| |///////////////////////////| 0 | |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | reserved_size | . |
+---------> +-+-+-+-+-+-+-+-+ . . . . . . . . -+
为了方便说明，我们将 user_data 和 in-band meta 这两部分称为 chunk（注意，mallocng 并没有所谓的 chunk ）。
1. chunk
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| meta | <-+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
. . |
. . | (OFF+1)*0x10
. . |
+-> . +-+-+-+-+-+-+-+-+ |
| . | 0 |R|I| OFF |---+ <----- in-band meta (0x4 bytes)
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ <----- p
| | |
| | |
| | |
| | |
| | |
| | |
chunk | | user data |
| | |
| | |
| | |
| | |
| | +-+-+-+-+-+-+
| | | 0 | .
+-> +-+-+-+-+-+-+-+-+-+-+-+-+ . . . .
. .
. .
. .
. +-+-+
. | 0 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| reserved_size | <----- reserved_size (0x4 bytes)
slot -> +-+-+-+-+-+-+-+-+
in-band meta 位于 chunk 头部，长度为 4 bytes，主要用途如下：
- 记录 in-band meta 距离所属 group meta 指针的相对偏移，以便查找 out-of-band metadata
- 记录 slot index
- 指明 slot reserved_size 的保存位置（in-band meta 或者位于 slot 末尾的
reserved_size字段）
一共有 3 个有效字段：R (reserved_size)、I (index)和 OFF (offset)。
0 1 2 3 4 byte
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ <----- in-band meta
| 0 | R | I | OFF |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
R : 第二个字节的前 3 个比特位
I : 第二个字节的后 5 个比特位
OFF: 第三个字节和第四个字节
- R (
reserved_size) ：（见下文 reserved_size 字段部分） - I (
index) ：表示 slot index，即 slot 在 group 中的编号，合法取值范围为[0, 0x1f)。 - OFF（
offset）：表示 slot 距离meta指针（即group结构体）的相对偏移，单位长度为 16 bytes，即：meta_ptr_addr = p - ((OFF+1)*0x10)。合法取值范围为[0, 0xffff]。
in-band meta 第一个字节是 overflow byte，又称为overflow_in_band。根据 mallocng 源码，它有两种特殊用途：
- 保护 in-band meta，防止被堆溢出破坏（作用类似栈中的 canary）
- 标明使用哪个字段作为
meta指针的相对偏移值（OFF或者OFF32字段）
大多数情况下，overflow_in_band 是一个 NULL 字节，此时表示meta指针相对偏移的是OFF字段。
而当 overflow_in_band 不等于 NULL 时，in-band meta 前面 4 字节被视为一个新的字段 OFF32 (offset32)（其位置与前一个 slot 的reserved_size字段重叠），取代原有的OFF字段。相对于长度只有 2 bytes 的OFF字段，4 bytes 长的OFF32字段可以表示更大的相对偏移。
为了区分 overflow_in_band 被破坏的情况（例如堆溢出），若 overflow_in_band 不等于 NULL 时，mallocng 要求满足如下条件，否则报错：
OFF字段值须等于 0OFF32字段值须大于 0xFFFF
(OFF == 0)
(OFF32 > 0xffff)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ <----- in-band meta
| OFF32 | 1 |R|I| 0 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ <----- p
| user data |
. .
. .
. .
事实上很少见 overflow_in_band != NULL。因为整个 mallocng 源码只有aligned_alloc()函数才会分配这种 slot。
user_data 即用户数据区域，malloc() 返回的指针p指向的就是这里。user_data区域的长度等于用户请求的内存大小。user_data 区域后面有一个 NULL 字节，用于检测 user_data 是否发生溢出。
2. reserved_size
reserved_size 字段位于 slot 最后 4 字节的位置。类似于 user_data，mallocng 在 reserved_size 字段前面也设置了一个 NULL 字节，用于检测该字段是否被破坏。
前文提到，mallocng 分配给用户的 slot 都是固定大小的，因此我们需要一个额外字段来记录用户实际可用的长度 nominal size（即user_data区域的长度）。
在 mallocng 中，reserved size 指 user_data区域到 slot 末尾之间的未使用空间(UNUSED)的长度。因此已知p指针、slot 末尾内存地址以及 reserved size，就能计算 slot 的 nominal size，即nominal_size = slot_end - p - reserved_size（slot_end是 slot 末尾指针）。
在 slot 中，一共有两处地方用于记录 reserved size，且 reserved size 的大小决定它的所在位置：
- 位于 slot 末尾的
reserved_size字段（长度为 4 bytes） - 位于 in-band meta 的
R字段（长度只有 3 bits）
当 reserved size 不小于 5 时，它保存于 reserved_size 字段中，此时 R字段为固定值 5。
而当 reserved size 小于 5 时，由于 reserved_size 字段的位置已被 user_data 区域占用，因此只能保存于 R 字段中。由此可知，R字段的合法取值范围为[0, 5]。
举个例子，下图 slot 的 reserved size 为 2 ：
+-+-+-+-+-+-+-+-+
| 0 |2|I| OFF | <----- chunk header
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| |
| |
| |
| |
| |
| user data |
| |
| |
| |
| |
| |
| |
| +-+-+-+-+-+-+-+-+-+-+-+-+ <------ reserved_size
| | 0 | |
+-+-+-+-+-+-+-+-+
3. slot header
+-+-+-+-+-+-+-+-+
| 0 |7|I| OFF |---+ <----- slot header
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
. . |
. . |
. . | (OFF-in-slot : offset to chunk)
. . |
. . |
. +-+-+-+-+-+-+-+-+ | <----- in-band meta
. | 0 |R|I| OFF | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ <-+ <----- p
| |
| user data |
| |
. .
. .
. .
仔细观察上面的 slot 内部结构，可以发现 slot 开头与 chunk 并不是重合的，而是两者之间往往相隔一定的距离。该距离除以 0x10 得到的相对偏移称为 cycle offset。
实际上，chunk 在 slot 中的位置并不是固定的，而是随着 slot 重用，chunk 位置不断变动。slot 每次重新分配给用户，chunk（即 p 指针地址）就会往下移动 0x10 字节。若 chunk 达到 slot 末尾，则返回到 slot 开头重新循环。
因此为了方便调试，mallocng 在 slot 开头设置了一个特殊字段 slot header，用于记录 chunk 的位置。它与 in-band meta 同样拥有 overflow byte 和三个同名字段，但是字段的用途并不一样。
在 slot header 中，OFF字段（又称为 OFF-in-slot）记录了 in-band meta 距离 slot 开头的相对偏移，即 cycle offset。当 slot 开头与 chunk 恰好重合时，slot header 与 in-band meta 的OFF字段刚好都是 0。
此外，slot header 的 I字段与 in-band meta 的相同，都是 slot index。slot header 的R字段是固定值 7，对于 in-band meta 的R字段来说这是个非法值。
在 mallocng 中，负责设置 slot 中 chunk 位置的是enframe函数，相关逻辑如下：
static inline void *enframe(struct meta *g, int idx, size_t n, int ctr)
{
[...]
// slack 是 cycle offset 的最大值
size_t slack = (stride-IB-n)/UNIT;
[...]
// p[-3]即 header 中的 R 和 I 字段，*(uint16_t *)(p-2) 即 header 的 OFF 字段
// 若这个 slot 是首次使用的（此时 R 下和 I 字段为 0），cycle offset 等于全局变量 ctx.mmap_counter
// 否则，cycle offset 等于 slot header 的 OFF 字段值加 1
int off = (p[-3] ? *(uint16_t *)(p-2) + 1 : ctr) & 255;
[...]
// 若 cycle offset 超过 slack，调整 cycle offset
if (off > slack) {
// cycle offset %= C(slack)
// C(slack) 指向下取最接近 slack 的 2 ^ n 值
size_t m = slack;
m |= m>>1; m |= m>>2; m |= m>>4;
off &= m;
// 若 cycle offset 仍然大于 slack，直接减去 slack+1
if (off > slack) off -= slack+1;
assert(off <= slack);
}
if (off) {
// 将 cycle offset 保存在 slot header 的 OFF 字段
// slot header R 字段设为非法值 7，
*(uint16_t *)(p-2) = off;
p[-3] = 7<<5;
// 将 p 指针移动到 chunk 位置
p += UNIT*off;
[...]
}
[...]
// 设置好一些字段后，返回 p
return p;
2. Part II
在接下来的 Part II，笔者准备讲一下 mallocng 的 malloc 和 free 实现。
另外，本文章 Part I 写得比较仓促。如有任何错漏麻烦各位师傅请拍，欢迎联系笔者更正！
Comments