关于libc的堆管理和利用的文章可以说是月经贴，在RSS或者论坛时不时就能看到一篇。对于这种情况，我只想说：这个月，该我了 :)

大家都知道在Linux中，或者说glibc中，动态分配/释放内存使用的是malloc/free函数。那么malloc中获得的内存，是从哪来的呢？一个直观想法是可以通过系统调用直接转发给kmalloc，但这样效率太低。用户态的事，尽量在用户态解决。因此，另一个直观想法就是需要时申请一片空间，然后在用户态管理和分配这些空间。

堆分配器的目的和原理是大同小异的，各个不同的堆分配器区别主要体现在分配和管理策略上。

先不看分配策略，malloc中的空间是从何而来的呢？了解的朋友应该都知道是通过brk/mmap系统调用实现。mmap如其名字所言，在进程的虚拟地址空间中创建新的地址映射；可以简单理解为直接向内核分配一定数量的页，POSIX兼容：

在实际的系统中，mmap一般支持多种类型的映射，比如支持直接将文件映射到内存中。

brk在应用层直接使用较少，但却历史悠久。在brk(2)中介绍，其主要作用是修改program break的位置。那么什么是program break呢？传统上一个进程在内存中会分成不同的片段(segments)：

当然现在比以前更加复杂，包含只读数据段(.rodata)、未初始化的数据段(.bss)、mmap数据段、vdso段等。

按照传统的划分，进程动态申请更多内存的方法就是拓展数据段，并对拓展出来的空间进行管理。而program break，实际上就是数据段的末尾。

可以通过下面代码看brk的实际效果(sbrk返回新分配空间的指针)：

第一次返回0x56558000，对应的内存区域如下：

第二次返回0x56558000，对应的内存区域如下：

可以看出sbrk是以页大小(0x1000)进行分配的，值得一提的是，第一次brk(0)调用之后所返回的地址，实际上就是.data段末尾的地址，这时候该地址还是没有映射的。如果两次brk中使用了printf，则结果则会大不相同。

总之，mmap和brk都是通过系统调用向内核申请新的映射(虚拟空间)，brk在内核中可以认为是mmap对应未初始化数据匿名映射的简化实现。

在介绍ptmalloc之前，我想先介绍下dlmalloc，因为ptmalloc很大程度上是基于dlmalloc的。

dlmalloc这名字其实是作者的名字——Doug Lea，这在早期算是一个很受欢迎的堆分配器，在保证内存碎片的情况下也兼顾了分配和释放的速度。我们重点关注dlmalloc算法的核心元素，而不会涉及具体的代码实现。

在dlmalloc和许多其他的堆分配器中，内存的分配和管理都是以块(chunk)为单位进行的，这样更容易进行组织。一个chunk就是一段大小固定的内存空间。

dlmalloc中一个重要的数据结构处理就是Boundary Tag，即边界标签。每个chunk都会在开头和结尾处包含额外标签，比如自身的大小和空闲信息。这样做有两个好处：

当然，现代的实现中为了更加充分利用内存，去掉了使用中的chunk末尾的Tag。因为当chunk在使用中时，这些字段是用不到的。

bin可以理解为集装箱，chunk按照大小组织在同一个bin中进行管理(双链表)。最初版本的dlmalloc包含了128个大小固定的bin，每个bin的大小近似地按照对数进行增长。

小于512的bin都只包含相同大小的chunk，寻找可用chunk采用的是best-fit策略。注意到前面说相邻的free chunk会进行合并，合并后的chunk会视情况放到下一个大bin中；而当分配时如果某个bin没有可用chunk，那么也是会从下一个bin中进行分裂，过程类似于Linux伙伴系统的分配策略。

大于512的bin使用的是另外一种分配策略(malloc_tree_chunk)。

除了这两大核心概念，dlmalloc的实现还考虑了局部性，临界chunk(brk/mmap)和缓存的优化，这里就不展开了。更多细节参考以下资料：

ptmalloc从dlmalloc中fork而来，其名字(pthread-malloc)也预示着其对多线程的支持，在2006年集成到glibc中作为默认堆分配器实现。因此本文所讨论的ptmalloc，更准确地说是glibc中的ptmalloc，而不是最初的版本。

通常系统的堆内存是一段巨大的连续空间，ptmalloc将其分隔为多个不同的空间以优化多线程中的使用。每个这样的空间称之为arena。多个arena的存在可以让多个线程同时在多个arena中分配内存，从而提高运行效率。

值得一提的是，glibc中的malloc实现不需要保证chunk的大小为2的指数。不论每个chunk大小是多少，相邻的空闲chunk都能进行合并。这样进一步减少了内存碎片以及额外的内存开销。

以下的介绍中涉及的代码主要出自glibc-2.27，因为这是ubuntu18.04的默认版本，操作系统默认为64位。所有其他版本可以从这里下载：

ptmalloc的核心算法和dlmalloc类似，宏观地介绍如下：

这就是算法的整体思路。对于多线程场景，主线程堆空间(main arena)同样是通过brk进行增长，而其他线程(per thread arena)则通过mmap进行分配。这也可以理解，因为brk只能增长program break，可内存在多个线程中是共享的，所以只有另寻他处。

与dlmalloc核心元素类似，ptmalloc中有类似的chunk和bin的概念，实现中涉及到的数据结构主要有三个，下文分别介绍。

malloc_chunk结构表示内存中的一个chunk的头部(header)，其定义如下：

不过就像注释所说比较容易让人误解，即误以为这些数据都是保存在每个chunk的头部的，实际上并非如此。

实际上这里也应用了dlmalloc中所提出的Boundary Tag技术，即在chunk头部和尾部包含size等信息(Tag)，方便空闲chunk进行合并。由于free chunk本身是没有内容的，所以利用这个特点来将前一个chunk的Tag保存在free chunk的头部中，而当前free chunk的Tag则顺延，从而减少一个word大小。示例图如下：

也就是说，free chunk和inuse chunk的头部内容并不相同。举例而言，如果前一个chunk空闲，那么mchunk_prev_size就是有意义的，否则只是包含了上一个chunk的用户数据；还有fd、bk指针对于inuse chunk来说也并不存在。

另外，对于Boundary Tag技术而言，这里Tag就是chunk_size本身，由于chunk的大小是8字节对齐的，因此最低log8=3位用不到，就腾出来记录额外信息，这3个bit从高到低分别是：

一个heap指的是一片连续的内存空间，其中包含了许多(可聚结)的malloc_chunk，heap通过mmap进行分配并且起始地址总是HEAP_MAX_SIZE对齐的。heap_info结构描述的就是一个heap：

每个thread arena中最初包含一个heap，当其内存用完后，会继续分配新的heap并加入到thread arena中。新分配的heap与之前的heap很可能不再是内存连续的了。

注：main arena使用brk拓展内存，只有一个heap，因此不存在heap_info。

上面说了一个arena可以包含一个或者多个heap，其中描述arena的数据结构就是malloc_state。

glibc不同版本有些许差异，但核心还是相近的，其中就包含了dlmalloc提到的bin。

main_arena的malloc_state是一个全局变量。

一个chunk的头部是malloc_chunk，根据其所处的位置和状态，大致有以下几种类型：

Allocated Chunk即已经返回给用户使用中的chunk，假设返回给用户的指针值是intprt_t mem，那么有mem = chunk + 8，此时chunk的大小即Boundary Tag保存在chunk + 4。

Free Chunk是用户释放掉的chunk，此时fd和bk指针就有意义了，用来链接到对应bin的双链表中。

Top Chunk是最高的一个chunk，因为位于可用堆地址空间的末端，因此不保存在任何bin中。dlmalloc中将其大小设置为大于任何一个chunk，这样在所有bin都无法满足分配时，就从top chunk中获取；在top chunk的空间也不足的时候才通过系统调用去拓展空间。

Last Remainder Chunk在dlmalloc中是提高局部性分配的一种优化，其本身指向的是最近一次small request分配所分裂(所剩余)的空间。

ptmalloc继承了dlmalloc的Binning特性，不同类别的chunk集装在同一个bin中。在malloc_state中涉及到的bin如下：

每个bin本质上是一个元素为malloc_chunk指针的链表，这里用数组保存了所有的bin。

FastbinsY：包含所有fastbin的数组，其中的chunk称为fastchunk，fastchunk的最大size为80 * SIZE_SZ / 4，32位下是80字节，64位为160字节。

bins：包含了除fastbin以外的所有bin。与dlmalloc一样，小于512字节的bin包含的是同样大小的chunk，bin之间的大小为8字节递增。直接引用注释的说明如下：

各个bin根据其作用不同，也被赋予了不同的名字，下面详细解释。

fastbin的作用是用来保存最近释放的small chunk。因此和其他bin不同的是fastbin为单链表而不是双链表，因为fastbin中的chunk不会从中间进行删除。同时，fastbin使用更快的LIFO处理顺序而不是其他bin中的FIFO。

保存到fastbin中的chunk的in_use位会被保留，也就是说fastchunk不会和相邻的chunk进行自动合并，但是fastbin可以释放所有chunk进行主动合并。

fastbin的数量和CPU位数有关，但本质都是从小到大递增8或16字节(SIZE_SZ * 2)，直至其最大的大小80 * SIZE_SZ / 4。

unsorted bin中保存的是所有其他chunk分裂生下来的chunk以及所有刚释放返回的chunk，不论大小。

这样处理的目的是给这些最近释放的chunk在被进入到对应bin之前一次重新被使用的机会。因此可以把unsorted bin看作是一个队列，进入其中的chunk要么被释放、合并，要么被取出继续使用或者放到其他bin中。

unsorted bin中的chunkNON_MAIN_ARENA总是为0。

unsorted bin只有一个，即bin[1]。

smallbin中保存的是小于MIN_LARGE_SIZE的chunk，即small chunk。前面也说过，小于512字节的每个bin保存的都是相同大小的chunk，并且以8字节大小进行递增。

由于smallbin中chunk大小都是相同的，因此不需要进行排序。每个smallbin都是双链表，从头部加入，从尾部删除(返回给用户)，遵循先进先出的顺序(FIFO)。

smallbin从bin[2]开始，共NSMALLBINS个。

largebin中保存的是大于等于MIN_LARGE_SIZE字节的chunk，与smallbin不一样的是，largebin中的chunk大小在同一个范围，但并不是完全相同的。largebin中的chunk需要按照size从大到小进行排序，所分配和释放的额外开销要大于smallbin。

largebin紧邻着smallbin，每个largebin大小范围根据bin的位置不同而不同，随着大小范围越大，bin的数量也就越少。

对于large chunk而言，在malloc_chunk中除了fd和bk指针，还包含了fd_nextsize和bk_nextsize指针，指向不同大小的chunk。

tcache(per-thread cache)在glibc2.26中引入，进一步提升堆管理性能。

tcache_entry用于链接空闲的chunk，指针直接指向chunk的userdata部分，也就是说复用了指针的含义。

每个线程都会维护一个tcache_prethread_struct，它是整个tcache机制的管理结构，其中包含TCACHE_MAX_BINS个tcache_entry链表。链入其中的chunk大小相同，所以通常也叫做tcache bin。其特性如下：

可以看到其特性和fastbin是非常类似的。释放时在填满tcache之后才进入传统的释放过程，分配时也先从tcache中搜索。

tcache bin一共有64个(TCACHE_MAX_BINS)，其大小范围为：

由于tcache的增加和删除非常简洁，因此速度很快，但另一方面这也意味着缺乏各种安全检查和mitigation，在利用时候也格外方便。

在分析分配和释放的具体流程上，最好的方法其实是阅读源码(RTFSC)，也有的人喜欢看一步步的文字解释。我这里按照自己阅读源码的过程将其简化为伪代码，或许可以更直观一些。

再次声明，所分析的libc版本为2.27

该函数代码近千行，梳理主要逻辑的伪代码如下：

值得一提的是tcache的搜索在_int_malloc之前，优先级最高：

释放逻辑的伪代码如下：

free中这些操作大都是围绕两个目的：

记住这两点，那么其中的许多操作也就比较容易理解了。

另外由于篇幅原因，分析中省略了各种安全相关的assert，因为这和具体的libc版本有关，实际利用布局时需要根据具体的代码进行适配。

漏洞利用的核心是在产生非预期的操作时，通过内存布局实现读写或者控制流劫持。堆漏洞利用也一样，我们的目标是通过小小的漏洞去构造出蝴蝶效应，在代码和数据的有序交互中开辟出一条新的道路。

glibc的漏洞利用已经有很多优秀的资料了，比如：

因此我们主要介绍几个典型，而不深入各个House的细节之中。

Binning是基于双链表而构造的，而在双链表中一个典型操作就是删除某个结点，也就是unlink操作。以fd和bk作为链表指针为例，unlink的实现一般是：

本质是让前后的结点绕过自己而进行连结。这个操作本身没有问题，但是却经常被攻击者滥用。

假设fd和bk的偏移分别为off_fd和off_bk，那么上述操作转换为内存读写是：

如果攻击者可以控制被unlink的chunk中的内容，即FD、BK的值是可控的话，那么就可以构造FD为目的地址x-bk_off，且BK为攻击者控制的地址y。则第3步就可以简化成：

如果x是某个已知会被调用的函数指针地址，那就可以将其覆盖为BK，令BK指向我们的shellcode即可实现控制流劫持。当然这时候BK+fd_off处会被修改，实际构造shellcode可以跳过这几个字节。

其实除了ptmalloc，很多代码中只要有双向链表都会有类似的unlink操作，比如之前安卓内核中的的CVE-2019-2215，所以这类常见的pattern还是值得深入研究的。

堆的单字节溢出在现实中通常更为常见。涉及到堆越界的基本上都和堆的数据结构(头部内容)强相关，所以这里着重讨论gblic的情况。

在可以溢出1字节的情况下，我们可以修改的区域为相邻的下一个chunk的size字段，因为prev_size实际上是在当前chunk的data部分的。溢出的思路有以下几种：

一、 拓展被释放块：当溢出的下一个chunk已经被释放并且存放在unsorted bin中时，通修改一字节将其扩大，这样下一次分配该chunk时后面的块就会被包含从而造成进一步溢出。

二、拓展已分配块：当溢出块的下一块为使用中的块，则需要合理控制溢出的字节，使其被释放时的合并操作能够顺利进行，例如直接加上下一块的大小使其完全被覆盖。

下一次分配对应大小时，即可取得已经被扩大的块，并造成进一步溢出。

三、poison_null_byte：收缩被释放块，使其在之后分裂此块时将无法正确更新后一块的prev_size，导致释放时出现重叠的堆块。常用于null byte溢出中。

通常B2是一个目标结构体，包含我们想要控制的有价值的指针。

四、 house_of_einherjar：同样是null byte溢出，不过覆盖后的下一个块prev_size可以找到前一个合法的块，并与其进行合并。

如果是针对时间紧张的CTF场景，还是要对常见版本的libc利用烂熟于心，比如how2heap命名的那些。当然要想熟悉利用技巧，对于malloc和free的代码实现也需要不断加深理解。

No more house, plz.

漏洞利用的本质是内存布局，而内存布局的本质是通过可控的异常去修改程序本身有限状态机的逻辑，从而达到任意读写/控制流劫持等目的。为此，我们在脑海中就要对所exploit的目标运行流程有清晰的认识，不能有丝毫不确定性，0就是0，1就是1。即便在多任务高并发的场景中，比如内核，其涉及的不确定性本身也是确定的。成功的攻击除了统顾全局，对细节的把握也至关重要。

最后，如果你也对二进制和系统底层感兴趣，欢迎来撩~

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！