evilpan's blog
归档 标签 分类 关于 订阅
evilpan's blog

ptmalloc cheatsheet

evilpan  收录于  类别 Security
     约 4666 字   预计阅读 21 分钟    次阅读  

最近公司被要求参加某网络安全比赛，所以借此机会又重新阅读了 glibc malloc 的最新代码，发现了许多之前未曾深究的细节。故整理成此文，也算是对从前文章的补充了。

前言

几年前已经写过了一篇 ptmalloc 与 glibc 堆漏洞利用，但是一来当时学习仓促，很多内容自己也只是一知半解；二来已经时过境迁，当时的 glibc 距今也更新了不少，而且当时理解的内容太久没有复习又全部还给老师了。因此，本文又重新将其整理一遍，当然不再介绍基础概念，只记录重点以备考试时快速查阅。

数据结构

首先在 arena 中实际上只分成两个 BIN，分别是 fastbinsY 和 bins。而 bins 中包含了常用的 unsorted bin、small bin、large bin，统称为 regular bins。

在 regular bins 数组中，bin_at(0) 不存在，bin_at(1) 为 unsorted bin，小于 MIN_LARGE_SIZE 的为 small bin，大于等于则为 large bin。对于 32/64 位系统来说，该值分别为 0x200/0x400:

c

#define NBINS             128
#define NSMALLBINS         64
#define SMALLBIN_WIDTH MALLOC_ALIGNMENT // -> 0x08/0x10
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ) // -> 0
#define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH) // -> 0x200/0x400

上面说到 unsorted bin 对应 bin_at(1)，但注意不要与 bins[1] 弄混，其实现如下:

c

#define unsorted_chunks(M)          (bin_at (M, 1))
#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))			      \
             - offsetof (struct malloc_chunk, fd))

可以看到 bin_at 对应的 bins 索引是 (i-1) * 2，而且取到地址之后还回退一个偏移。乍看起来很奇怪，但实际上这是写代码的一个小优化，返回的地址会转换为 chunk 指针，但实际上并不是一个正常的块，而只是将其当做一个空闲的头部，只使用其中的 fd/bk 字段，分别指向不同的 bin。假设返回的指针是 P，则有:

text

P->fd = m->bins[(i-1) * 2];
P->bk = m->bins[((i-1) * 2) + 1];

也就是说，bin_at(i) 返回的 chunk， 似 chunk 又非 chunk，本身在 bins 中占两个坑，虽然不能当做真的 chunk 返回给用户使用，但是却正好当做双链表的固定表头。

实际测试一下可能更清楚一些，在 unsorted bin 为空时，有以下属性:

gdb

pwndbg> p *main_arena.bins[0]
$1 = {
  mchunk_prev_size = 94692393318320,
  mchunk_size = 0,
  fd = 0x7f5bfe942cc0 <main_arena+96>,
  bk = 0x7f5bfe942cc0 <main_arena+96>,
  fd_nextsize = 0x7f5bfe942cd0 <main_arena+112>,
  bk_nextsize = 0x7f5bfe942cd0 <main_arena+112>
}

pwndbg> distance main_arena.bins[0] &main_arena.bins[0]
0x7f5bfe942cc0->0x7f5bfe942cd0 is 0x10 bytes (0x2 words)

bin 中的唯一一个 chunk，其 fd 和 bk 都指向自身，而这个 自身，却是 bin 所在位置往前 0x10 字节的地址，即在全局 main_arena 结构体中，.data 段的地址。

下面分别介绍一下各个 bin 中值得一提的特性。

fastbinsY 数组中保存着不同长度的单链表头指针，但实际上数组的大小会比链表总数要略大一些，空出来的可能是留着过年。

c

#define MAX_FAST_SIZE (80 * SIZE_SZ / 4) // 0x50/0xa0

以 32 位程序为例，只用到了 0x10, 0x18, … 0x40 共 7 个 bin，但数组总大小为 11，fastbin 的上限是 0x50 字节；

对于 64 位程序，也是只用到了 0x20, 0x30, …, 0x80 共 7 个 bin，数组大小为 10，理论上最大的 fastbin 可以达到 0xa0 字节；

fastbin 的特性如下:

  • 进入 fastbin 的 chunk，其 in-use 位为 1，因此不参与相邻块的合并；
  • 同一个 bin 中所有的 chunk 大小都相等，因此不需要排序；
  • 由于 fastbin 是按照最小 chunk 对齐大小增长的，因此从 fastbin 中分配的块必然是 exact fit 的，即申请 chunk 大小与 bin 大小完全一致；
  • LIFO，这是为了提升 cache 命中率；

待释放的块 P 进入 fastbin 时，首先获取对应大小 bin 链表头的指针，称为 FP，然后执行以下操作将 P 插入单链表的头部:

c

P->fd = *FB;
*FB = P;

同理，要从 fastbin 取出块时，则直接取出链表头的元素:

c

P = *FP;
*FP = P->fd;

这些指针操作是触发堆漏洞时候构造内存读写原语的重要来源，因此值得重点关注。

  • 只有一个，即 bin_at(1) = bins[0]/bins[1] (fd/bk)；
  • 内部的 chunk 可以是任何大小，且如其名字而言，不进行排序；
  • 双链表，FIFO；
  • 只有一次重新被使用的机会；
  • 对于小请求，大部分情况下要求 exact fit，即尺寸一样才会返回；但如果此时bin 中只剩下一个 chunk 且为 last_remainder 且足够大，会对其进行分割，此时是 best fit；
  • 分割后多出的部分或者遍历时不满足要求的 chunk 会全部放回到各自的 small/large bin 中；
  • 进入 unsorted bin 之前，会先进行前后合并；

待释放的块 P 进入 unsorted bin 时，会插入到 bin 的第一个元素中，如下:

c

bck = unsorted_chunks(av);
fwd = bck->fd;

P->fd = fwd;
P->bk = bck;
if (!in_smallbin_range(size)) {
    p->fd_nextsize = NULL;
    p->bk_nextsize = NULL;
}
bck->fd = p;
fwd->bk = p;

注意这里用到了本节开头提到的双链表 trick，bck 是双链表的头，这里可以看做是一个 chunk (虽然实际上不是)。 因此，上述双链表插入的时候，并没有像 fastbin 一样直接替换表头，而是插在了表头的后面。

既然是 FIFO，而且在插入时候从表头的 fd 插入，那么取出时自然就优先从链表末尾即 bk 拿出了，取出的相关操作如下:

c

while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
    bck = victim->bk;

    /* remove from unsorted list */
    unsorted_chunks (av)->bk = bck;
    bck->fd = unsorted_chunks (av);
}

要说特点，Small Bin 可以说是在这些数据结构中最平平无奇的了，包含了一些似乎大家都有的性质，比如:

  • 双链表，FIFO；
  • 每个 bin 中 chunk 的大小都相同；
  • 从中分配的策略属于 best fit；

事实上，small 和 large bin 中的分配策略都属于 best fit，在 malloc 搜索并处理完 unsoted bin 后会对 SB/LB 进行扫描，选出最合适的取出并根据情况进行切割;而 SB/LB 中的 chunk 可能还是刚刚从 UB 中脱出来的。

但也有一些特别的，由于指定 bin 中的 chunk 大小都相同，所以也可以将其中 chunk 的大小称为 bin 的大小。

  • Small Bin 本应有 NSMALLBINS = 64 个，但 bin_at(0) 不存在，bin_at(1) 是 unsorted bin，因此实际上只有 62 个；
  • 在 64 位程序中；
    • 最小的 small bin 大小为 0x20，最大为 0x3f0；
    • 每个 bin 之间的大小相差 0x10；
  • 在 32 位程序中:
    • 最小的 small bin 大小为 0x10，最大为 0x1f8；
    • 每个 bin 之间的大小相差 0x8；

如果没有失忆的话，应该会发现，small bin 和 fast bin 的大小范围有所重叠。但它们的业务范围不同，前者是 unsorted bin 投胎失败后的去处；而后者则是赵家人优待窗口，释放后可以不通过 unsorted bin 直接进入。

更上层的还有天龙人 tcache，后文会详细介绍。

这里先说出链操作，其实和 unsorted bin 类似，都是双链表的删除操作，取的是链表末尾的 chunk:

c

#define last(b)      ((b)->bk)

idx = smallbin_index (nb);
bin = bin_at (av, idx);
if ((victim = last (bin)) != bin) {
    bck = victim->bk;
    bin->bk = bck;
    bck->fd = bin;
}

入链相对复杂，在于 regular bin 都只能从 unsorted bin 的残羹冷炙中获取生源。但复杂的是算法，数据操作还是很简单的:

c

victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;

victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

bck 是链表头，一个伪 chunk，所以上面的代码本质还是将 victim chunk 插入到链表的头(的下一个位置)。

前文说过，NBINS 一共就 128 个， Small Bin(等等) 占了 64 个，那么剩下来的就是 Large Bin 了。它和其他 bin 相比尽管有一些类似，但更多的是不同。其特性如下:

  • 同一个 bin 中块的大小可以不同，不同大小的块需要经过排序，相同大小的采用 FIFO 顺序进出；
  • bin 中包含两个双链表；
  • 取出时候按照 best fit 的原则获取；
  • 不同的 bin 可以分为 6 组，每组的 bin 之间大小间隔公差不同，见下表；
bin_at bins 间隔 HEX 备注
0-63 64 16 0x10 62 个 Small Bin, [0x20, 0x400)
64-95 32 64 0x40 Large Bin, [0x400, 0xc00)
96-111 16 512 0x200 Large Bin, [0xc00, 0x2c00)
112-119 8 4096 0x1000 Large Bin, [0x2c00, 0xac00)
120-123 4 32768 0x8000 Large Bin, [0xac00, 0x2ac00)
124-125 2 262144 0x40000 Large Bin, [0x2ac00, 0xaac00)
126 1 其他 - Large Bin, [0xaac00, …)

上面备注的 large bin 每组大小区间可能有点不准确，我是按照间隔大小以及文档中所声明的 bin 个数计算的。但分组本身并不很重要，实际计算以 largebin_index_64 宏的结果为准(比如第一组实际上是 64~96)。

largebin 中不同 size 的 chunk 使用 fd_nextsize/bk_nextsize 相连，相同 size 的使用 fd/bk 指针相连，例如下图 bin 中有 7 个 chunk:

largebin

关键点:

  • 链表头的 fd 指向最大的块；bk 指向最小的块；
  • 相同大小的块中，只有第一个块的 fd_nextsize 和 bk_nextsize 指向下一个大小的块，后续块的 fd_nextsize、bk_nextsize 会置零；
  • fd_nextsize/bk_nextsize 属性构成一个循环双链表，从 fd 第一个元素开始 ，fd_nextsize 指向下一个更小的块，最小的块会指向最大的块；注意这个双链表并不包含所有的块；
  • fd/bk 属性也构成一个循环双链表，从表头第一个元素开始 fd 指向下一个 size 小于等于自身 size 的块，串起了所有的块；
  • nextsize 双链表不包含表头，因为表头是个伪 chunk，只有 fd 和 bk 属性；

插入 large bin 的流程伪代码如下:

c

victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;

if (fwd != bck) {
    // 与 bin 中最小的块比较
    if (size < chunksize_nomask(bck->bk)) {
        fwd = bck;
        bck = bck->bk;

        victim->fd_nextsize = fwd->fd;
        victim->bk_nextsize = fwd->fd->bk_nextsize;
        fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
    } else {
        // 从 fwd = bin->bk 即最大的块开始搜索
        while (size < chunksize_nomask (fwd)) {
           fwd = fwd->fd_nextsize;
        }
        /* 此时 fwd 指向能满足申请 size 的最小块 */
        if (size == chunksize_nomask (fwd)) {
            // 如果已经存在对应大小的块，插入对应次级链表的第二个位置
            fwd = fwd->fd;
        } else {
            victim->fd_nextsize = fwd;
            victim->bk_nextsize = fwd->bk_nextsize;
            fwd->bk_nextsize = victim;
            victim->bk_nextsize->fd_nextsize = victim;
        }
        bck = fwd->bk;
    }
} else { // bin 为空
    victim->fd_nextsize = victim->bk_nextsize = victim;
}

victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

代码虽然看起来很复杂，但思路其实很直观，bck 和 fwd 分别表示待插入块所在位置的前后节点，前面一系列操作只是确定其位置，最后执行双链表的插入操作。而对于 fd/bk_nextsize 的操作也和上图中介绍的流程一致，目的还是为了让 chunk 按照大小顺序排好。

删除 large bin 的逻辑也类似:

c

bin = bin_at (av, idx);
victim = first (bin); // victim = 最大的块
victim = victim->bk_nextsize; // victim = 最小的块
while (((size = chunksize (victim)) < nb)) {
    // 从小到大搜索，直至尺寸满足
    victim = victim->bk_nextsize;
}

if (victim != last (bin)
    && chunksize_nomask (victim) == chunksize_nomask (victim->fd)) {
    // 如果相同尺寸的块不止一个，从第二个开始取，防止修改 nextsize 链表
    victim = victim->fd;
}

unlink_chunk (av, victim);

unlink_chunk 就是老版本中的 unlink 宏，现在已经升级为了函数，但操作还是一样的，标准双链表删除，其中针对 largebin 的还执行了 nextsize 双链表的删除操作:

c

unlink_chunk (mstate av, mchunkptr p) {
    mchunkptr fd = p->fd;
    mchunkptr bk = p->bk;
    fd->bk = bk;
    bk->fd = fd;
    /* 确认为 largebin 且 p 在 nextsize 链表中 */
    if (!in_smallbin_range (chunksize_nomask (p)) && p->fd_nextsize != NULL) {
        if (fd->fd_nextsize == NULL) {
            /* 下一个块不在链表中，将其加入 */
            if (p->fd_nextsize == p)
                fd->fd_nextsize = fd->bk_nextsize = fd;
            else {
                fd->fd_nextsize = p->fd_nextsize;
                fd->bk_nextsize = p->bk_nextsize;
                p->fd_nextsize->bk_nextsize = fd;
                p->bk_nextsize->fd_nextsize = fd;
            }
        } else {
            /* 下一个块也在链表中，功成身退 */
            p->fd_nextsize->bk_nextsize = p->bk_nextsize;
            p->bk_nextsize->fd_nextsize = p->fd_nextsize;
        }
    }
}

由前面的逻辑可以推测，如果同样大小的块有不止一个，那么肯定不会删除在 nextsize 双链表中的那个(即第一个)。因此，如果需要从 nextsize 链表中删除，就说明了对应大小的块只有一个。其实这个预设可以简化删除的逻辑，但 unlink 作为通用的函数，不能对传入的 p 做额外预设，因此还是检查了所有情况。

tcache 也是个缓存，本身就是个数组，比 fastbin 快那么一丢丢，但胜在支持的尺寸多。其主要特性如下:

  • 一共有 TCACHE_MAX_BINS = 64 个 tcache bin；
  • 每个 bin 最多只有 TCACHE_FILL_COUNT = 7 个 chunk；
  • bin 之间大小相差 0x10，实际尺寸到索引通过 csize2tidx 计算；
  • 最大的 bin 支持的大小为 0x410，实际用户申请的大小要减去头部和对齐；

其实 tcache 从 2.26 加入 glibc 之后，其结构和代码逻辑都发生了很大的变化。早期什么检查都没有，但每一代都会新增一些校验，导致 tcache 已经不是那么好利用了，所以现在基本上都是先将其填满，然后再去利用常规方法进行利用。

算法

这里简单把堆分配和释放的过程记录下来。在遇到一些细节的时候可以去查看相关代码。

内存的关键分配过程如下:

  1. 如果 tcache 中有合适的块，直接取出返回；
  2. 如果 fastbin 中有合适的块，直接返回；
  3. 如果是小块，则尝试从对应的 smallbin 中取出返回；
  4. 如果是大块，先 malloc_consolidate；
  5. 循环遍历 unsorted bin:
    1. 如果请求的是小块，且 bin 中只有一块 last_remainder，且大小满足，则对其进行切割，然后返回；
    2. 不管要不要，先将当前块从 unsorted bin 中删除；
    3. 如果当前块大小和请求大小完全相等，可直接返回；
    4. 否则将当前块放到对应的 small、large bin 中；
  6. 如果是大块，在 large bin 中搜索最合适的；
  7. 兜底方案，从 top_chunk 中分裂出新的块并返回；

关于 tcache 的横刀夺爱:

  • 在第 2 和 第 3 步，相同大小的其他块也会取出放到对应的 tcache bin 中；
  • 在 5.3 步，并不直接返回，而是先放到 tcache bin 中然后继续遍历；
  • 在 unsorted bin 每次循环的末尾会检查 tcache 有没有拿够，拿够了就放人；

接着看内存释放的过程:

  1. 如果对应的 tcache bin 有空位，直接放进去；
  2. 如果是 fastbin 的大小，放到对应的 fastbin 中；
  3. 尝试合并相邻低地址的块，也称为后向合并(backward)；
  4. 如果相邻高地址的块不是 top chunk，则尝试前向合并(forward)；
    • 否则直接合并然后更新 top chunk，直接返回；
  5. 将合并后的块放到 unsorted bin 中；
  6. 合并后的块大小如果大于某个阈值，则触发 malloc_consolidate；
  7. 如果 top chunk 大于 mp.trim_threshold，则执行 systrim；

其中 malloc_consolidate 在内存分配的时候也遇到过，主要作用是将 fastbin 中的块都清空并归还系统，能与 top chunk 合并的就合并，不能合并的就插入 unsorted bin 的头部。

不管是 malloc_consolidate 还是 systrim，其目的都是为了减少内存碎片，后者的作用是作为 sysmalloc 的逆操作，通过 brk 系统调用将多余的内存还给系统。

后记

本文算是把 ptmalloc 复习了一遍，重新梳理了其中的亿点细节，并编撰成文以备日后参考。其实很多 CTF 比赛还是能够对现实安全研究带来思路的，去享受，去学习，去分享，也许这才是 CTF 的原本价值吧。

版权声明: 自由转载-非商用-非衍生-保持署名 (CC 4.0 BY-SA)
原文地址: https://evilpan.com/2022/07/17/ptmalloc-notes/
微信订阅: 『有价值炮灰』
– TO BE CONTINUED.

更新于 2022-07-17
 Ptmalloc, Dlmalloc, Glibc
 | 主页