search

4.14 glibc tcache 机制

hashtag
tcache

tcache 全名 thread local caching，它为每个线程创建一个缓存（cache），从而实现无锁的分配算法，有不错的性能提升。libc-2.26 正式提供了该机制，并默认开启，具体可以查看这次 commitarrow-up-right。

hashtag
数据结构

glibc 在编译时使用 USE_TCACHE 条件来开启 tcache 机制，并定义了下面一些东西：

#if USE_TCACHE
/* We want 64 entries.  This is an arbitrary limit, which tunables can reduce.  */
# define TCACHE_MAX_BINS		64
# define MAX_TCACHE_SIZE	tidx2usize (TCACHE_MAX_BINS-1)

/* Only used to pre-fill the tunables.  */
# define tidx2usize(idx)	(((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ)

/* When "x" is from chunksize().  */
# define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)
/* When "x" is a user-provided size.  */
# define usize2tidx(x) csize2tidx (request2size (x))

/* With rounding and alignment, the bins are...
   idx 0   bytes 0..24 (64-bit) or 0..12 (32-bit)
   idx 1   bytes 25..40 or 13..20
   idx 2   bytes 41..56 or 21..28
   etc.  */

/* This is another arbitrary limit, which tunables can change.  Each
   tcache bin will hold at most this number of chunks.  */
# define TCACHE_FILL_COUNT 7
#endif

值得注意的比如每个线程默认使用 64 个单链表结构的 bins，每个 bins 最多存放 7 个 chunk。chunk 的大小在 64 位机器上以 16 字节递增，从 24 到 1032 字节。32 位机器上则是以 8 字节递增，从 12 到 512 字节。所以 tcache bin 只用于存放 non-large 的 chunk。

然后引入了两个新的数据结构，tcache_entry 和 tcache_perthread_struct：

tcache_perthread_struct 包含一个数组 entries，用于放置 64 个 bins，数组 counts 存放每个 bins 中的 chunk 数量。每个被放入相应 bins 中的 chunk 都会在其用户数据中包含一个 tcache_entry（FD指针），指向同 bins 中的下一个 chunk，构成单链表。

tcache 初始化操作如下：

hashtag
使用

触发在 tcache 中放入 chunk 的操作：

  • free 时：在 fastbin 的操作之前进行，如果 chunk size 符合要求，并且对应的 bins 还未装满，则将其放进去。

  • malloc 时：有三个地方会触发。

    • 如果从 fastbin 中成功返回了一个需要的 chunk，那么对应 fastbin 中的其他 chunk 会被放进相应的 tcache bin 中，直到上限。需要注意的是 chunks 在 tcache bin 的顺序和在 fastbin 中的顺序是反过来的。

    • smallbin 中的情况与 fastbin 相似，双链表中的剩余 chunk 会被填充到 tcache bin 中，直到上限。

    • binning code（chunk合并等其他情况）中，每一个符合要求的 chunk 都会优先被放入 tcache，而不是直接返回（除非tcache被装满）。寻找结束后，tcache 会返回其中一个。

触发从 tcache 中取出 chunk 的操作：

  • 在 __libc_malloc() 调用 _int_malloc() 之前，如果 tcache bin 中有符合要求的 chunk，则直接将它返回。

  • bining code 中，如果在 tcache 中放入 chunk 达到上限，则会直接返回最后一个 chunk。

    当然默认情况下没有限制，所以这段代码也不会执行：

  • binning code 结束后，如果没有直接返回（如上），那么如果有至少一个符合要求的 chunk 被找到，则返回最后一个。

另外还需要注意的是 tcache 中的 chunk 不会被合并，无论是相邻 chunk，还是 chunk 和 top chunk。因为这些 chunk 会被标记为 inuse。

hashtag
安全性分析

tcache_put() 和 tcache_get() 分别用于从单链表中放入和取出 chunk：

可以看到注释部分，它假设调用者已经对参数进行了有效性检查，然而由于对 tcache 的操作在 free 和 malloc 中往往都处于很靠前的位置，导致原来的许多有效性检查都被无视了。这样做虽然有利于提升执行效率，但对安全性造成了负面影响。

hashtag
tcache_dup

tcache_dup 与 fastbin_dup 类似，但其实更加简单，因为它并不局限于 fastbin，只要在 tcache chunk 范围内的都可以，而且 double-free 也不再需要考虑 top 的问题，直接 free 两次就可以了。然后我们就可以得到相同的 chunk。

第一次 free 后：

chunk 被放入相应的 tcache bin 中，可以看到该 tcache bin 的 counts 被设为 1，表示有 1 个 chunk，入口为 0x0000555555756260。

第二次 free 后：

counts 变成 2，入口不变，表示 tcache bin 已经有两个 chunk 了，虽然是相同的。

两次 malloc 后：

于是我们得到了两个指向同一块内存区域的指针。

hashtag
tcache_house_of_spirit

tcache 在释放堆块时没有对其前后堆块进行合法性校验，只需要本块对齐（2*SIZE_SZ）就可以将堆块释放到 tcache 中，而在申请时，tcache 对内部大小合适的堆块也是直接分配的，导致常见的 house_of_spirit 可以延伸到 smallbin，而且比以前更加简单。

在栈上构造 fake chunk，大小为 smallbin：

free 掉之后，该 fake chunk 被放进 tcache bin：

最后 malloc 即可将 fake chunk 取出来：

于是我们就在得到了一个在栈上的 chunk。

hashtag
tcache_overlapping_chunks

在 _int_free() 时，libc 完全没有对 chunk 进行检查，所以我们可以直接修改其 size，在 free 时该 chunk 就被放进了不同的 tcache bin。在下一次 malloc 时得到不一样大小的 chunk，造成堆块重叠。

首先我们分配两个 chunk：

然后修改第一个的 size 并将其释放：

可以看到 chunk p1 并没有放到它应该去的 tcache bin 中，而是放到了修改 size 后对应的 tcache bin。

最后将其 malloc 出来：

于是 chunk p2 被 chunk p3 覆盖了。

hashtag
tcache_poisoning

该实例通过破坏 tcache bin 中 chunk 的 fd 指针，将其指向不同的位置，从而改变 tcache_entry 的 next 指针，在 malloc 时在任意位置得到 chunk。而 tcache_get() 函数没有对此做任何的检查。

分配一个 chunk p1 后释放，该 chunk 将被放入相应的 tcache bin，其 fd 指针被清空：

然后修改 fd 指针指向栈上的地址 target：

接下来的第一次 malloc 将 chunk p1 的地方取出：

可以看到 tcache 的 entries 被修改为我们伪造的 fd 地址。

第二次 malloc，虽然 tcache bin 的 counts 为 0，但它并没有做检查，直接在 entries 指向的地方返回了一个 chunk：

于是我们得到了一个在栈上的 chunk。

有趣的是 tcache bin 的 counts 居然产生了整数溢出（0x00-1=0xff）：

看来这个机制仍然存在很多的问题啊。

注：突然发现这个 0xff 在 unsorted bin attack 里有很巧妙的用处，参考章节 3.1.8。

这一节的代码可以在这里arrow-up-right找到。其他的一些情况可以参考章节 3.3.6。

hashtag
CTF 实例

在最近的 CTF 中，已经开始尝试使用 libc-2.26，比如章节 6.1.15、6.1.19 中的例子。

hashtag
CVE-2017-17426

libc-2.26 中的 tcache 机制被发现了安全漏洞，由于 __libc_malloc() 使用 request2size() 来将所请求的分配大小转换为计算块大小，该函数不会进行整数溢出检查。所以如果请求一个非常大的堆块（接近 SIZE_MAX），将会导致整数溢出，从而导致 malloc 错误地返回了 tcache bin 里的堆块。

一个例子：

可以看到在使用 libc-2.26 时，第二次 malloc 返回了第一次 free 的堆块。而在使用 libc-2.27 时返回 NULL，说明该问题已被修复。

hashtag
patch

该漏洞在 libc-2.27 的这次 commitarrow-up-right 中被修复。方法是用更安全的 checked_request2size() 替换 request2size()，以实现对整数溢出的检查：

hashtag
参考资料

Previous4.13 利用 _IO_FILE 结构Next4.15 利用 vsyscall 和 vDSO

Last updated