本文为原创文章，转载请注明出处！

title: Linux heap 学习 tags: Heap,pwn,linux

grammar_cjkRuby: true

利用周末的时间，系统的学习了linux 系统的glibc堆分配机制，从中了解了很多以前很模糊的东西。本文打算系统的讲解一下关于堆的分配和使用机制，同时思考可能存在的一些攻击方法。

0x01 Linux 堆概述

在程序运行过程中，动态的进行内存分配。是在内存中的一段连续的空间，由低地址向高地址增长。由堆管理其负责调用分配。

0x1 实现库

目前实现堆管理的库有很多

dlmalloc – General purpose allocator ptmalloc2 – glibc jemalloc – FreeBSD and Firefox tcmalloc – Google libumem – Solaris
主要介绍ptmalloc2 – glibc，ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。

0x2 分配函数

堆内存的分配函数是malloc(n)

1.当 n=0 时，返回当前系统允许的堆的最小内存块。

2.当 n 为负数时，由于在大多数系统上，size_t 是无符号数（这一点非常重要），所以程序就会申请很大的内存空间，但通常来说都会崩溃，因为系统没有那么多的内存可以分配。

malloc是用户层使用的函数，真正分配内存的是系统调用函数 (s)brk 函数以及 mmap, munmap 函数。

在一开始创建堆的时候使用brk函数，直接在数据段的后面申请一段空间（称为arena）

 堆扩展那么当arena空间不够时系统怎么处理？ malloc采取的机制是

1.当调用malloc函数，arena空间不够时，如果申请的大小<128KB(0x20000字节) 直接使用brk分配机制，也就是说直接拓展arena

2.前提一样，如果申请的空间>= 128KB时，直接使用mmap分配机制

测试程序针对第一种情况

针对第二种情况，测试脚本

0x3 释放函数

堆内存释放函数是free(p)，其中p是堆指针，指向的是data部分（不加上head头部）

1.当 p 为空指针时，函数不执行任何操作。

2.当 p 已经被释放之后，再次释放会出现乱七八糟的效果，这其实就是 double free。 除了被禁用 (mallopt) 的情况下，当释放很大的内存空间时，程序会将这些内存空间还给系统，以便于减小程序所使用的内存空间。
在执行释放函数时，会检查该块的前一块是否是空块，如果是将会进行堆块的合并。

0x02 Heap 分配机制

在程序使用堆的时候会调用malloc去申请内存空间，返回的是一个堆块指针，指向堆结构体，当它被释放时会被插入相对应的空闲结块链表。

0x1 堆块结构

堆块结构是一个结构体，具体内容如下

在size的底三位记录了当前的堆块状态和上一个内存地址相邻的堆块的使用状态参数解释

• prevsize

记录上一个堆块（这里指的是内存地址相邻的堆块，而不是链表中的相邻）的大小，当本块的p位（记录上一堆块的使用状态）为1时，prevsize属于上一个堆块，进行内存赋值等操作。反之则表示上一堆块的大小

• size

记录本块大小，该 chunk 的大小，大小必须是 2 * SIZE_SZ 的整数倍。包括header在内的堆块大小，第三位分别为N、M、P

• P

PREV_INUSE，表示前一个chunk是否为allocated

• M I

S_MAPPED，表示当前chunk是否是通过mmap系统调用产生的

• N

NONMAINARENA，表示当前chunk是否是thread arena

• FD

指向链表中前一个堆块的指针，该指针指向的是chunk的head

• BK

指向链表中后一个堆块的指针，该指针也是指向chunk的head，通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理

• FD_nextsize

指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。

• BK_nextsize

指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适chunk 时挨个遍历。

内存对齐堆块申请的时候不一定都是内存对齐的，比如在x86操作系统下申请0x95。那么堆的对齐方式又是如何呢？ 经过实验发现如下规律

同时通过输出size_t，为堆块中的基本单位

分配大小计算

在进行内存申请的时候有许多计算规则，如果想要数量掌握堆的管理机制以及利用方法，那么就必须了解堆块是如何分配其大小的。 首先提几个概念，内存复用、地址对齐。内存复用体现在下一块的prevsize，复用的内存不算在chunk大小上。在计算是首先 size mod2*剩余的数据与sizet进行比较，如果小则直接分配，如果大则直接增加 2*size_t以一个例子为例：

malloc(0x43)

• 在x86环境下 对齐单元为0x8还剩下0x3字节数据，可以利用复用的内存进行扩充。加上头部8字节，一共分配了0x48字节chunk

malloc(0x45)

• 在x86环境下对齐之后还剩0x5字节数据，复用还不行，那么直接增加0x8个字节，一共分配0x50字节chunk

举一个0x64的例子 malloc(0x45)

• 对齐之后还有0x5字节，可以采取复用，最后大小为0x50

malloc(0x49)

• 对齐之后，不可以采取复用，最后大小为0x60

最后补充一点，每一个chunk都要有data段，所以不能只用头和复用段。

bin

当用户释放chunk后，chunk并不会立即回到系统中去，而是有ptmalloc统一进行管理，当再有内存空间申请的请求时，ptmalloc分配器会在空闲的chunk中挑一块给用户。那么维护空闲chunk的结构是链表形式，主要有四种fast bins，small bins，large bins，unsorted bin。在下面的介绍中将一一讲述。

bin的链表中的指针指向的是head头部，并非是数据部分，这点应该格外注意。

0x2 Fast bin

防止经常使用的较小的堆块被合并，降低堆的利用效率。 fastbin总共有10个链表，不同位数操作系统的堆块大小不同

需要注意的几点

• Fastbin的free chunk中p标志位是一直为1的也就是说，fastbin的空闲块总是标识被占用。也是防止被其他块进行合并

• Fastbin 链表是单链表，方便操作

利用fd执行后面的指针

0x3 Small bin

小于512字节的chunk称之为small chunk，small bin就是用于管理small chunk的。采用FIFO的算法

需要注意几点

• smallbin个数是62个参照上图

• 维护的是双向链表

• 当相邻的两个堆块都是free状态时，会发生合并现象

• 与fastbin的大小相冲突，大小冲突的smallbin还会收录堆块吗？答案是会的，不是一次申请的fastbin大小堆块被释放，就有可能放入smallbin里面

• smallbin的来源是？smallbin的来源是unsortedbin，具体会在unsortedbin中讲解
  0x4 Lager bin

large bins 中一共包括 63 个 bin，每个 bin 中的 chunk 的大小不一致，而是处于一定区间范围内。此外，这 63 个 bin 被分成了 6 组，每组 bin 中的 chunk 大小之间的公差一致，具体如下：

需要注意几点

• 合并同smallbin

• 同一个largebin其chunk大小有可能不一样，处于某一范围之内(例如第一个为521~575之间)。在同一个largebin里面chunk的大小是按照从大到小的顺序排放的

• 在横向也有链表相连接如下图

• malloc时，首先确定大小属于哪个largebin。然后将剩余的chunk丢到unsortedbin中，等待分配。

0x5 Unsorted bin

unsorted bin 位于 bin[1]，当释放较小或较大的chunk的时候，如果系统没有将它们添加到对应的bins中，主要来源如

1.当一个较大的 chunk 被分割成两半后，如果剩下的部分大于MINSIZE，就会被放到 unsorted bin 中。

2.释放一个不属于 fast bin 的 chunk，并且该 chunk 不和 top chunk 紧邻时，该 chunk 会被首先放到 unsorted bin 中。关于 top chunk 的解释，请参考下面的介绍。

3.当申请的内存被释放时除了fastbin大小的chunk直接插入链表中外，其他的chunk都被放在unsorted bin里面待分配。

4.unsorted chunk的删除并不使用 unlink ，使用的是下面方法，因此只是改变了chunk的bk块的前项指针，在malloc操作时最后访问的unsorted ，如果没有合适的大小就一个一个的删除，添加到其他链表中，所以这时如果伪造了chunk的bk值，很容易引起崩溃

0x6 Top chunk

0x7 Last remainder

0x8 保护机制

按照free与malloc分类

free

1. free的检查主要是根据本chunk的size检测下一块的inuse位，查看是否有double free的情况发生

2. 检查当前free的chunk是否与fastbin中的第一个chunk相同，相同则报错

3. 根据当前的inuse以及后一块的后一块的inuse判断是否需要合并，如果需要合并则对在链表中的freebin进行unlink操作
   

malloc

1. 从fastbin中取出chunk后，检查size是否属于fastbin

2. 从smallbin中除去chunk后，检查victim->bk->fd == victim

3. 从unsortbin取chunk时，要检查2*sizet<chunk< em="" style="box-sizing: border-box;">size<内存总分配量</chunk<>

4. 从 largebin取chunk时，切分后的chunk要加入unsortedbin,需要检查 unsortedbin的第一个chunk的bk是否指向unsortedbin

5. 如果freebin中有合适大小的堆块那么执行unlink操作

unlink

1. 当需要unlink一个堆块时首先检测大小是否等于后一块的prev_size

2. 接着检查unlink的堆块是否在链表中

下面通过一些代码进行测试

free 会检查double free的情况

free 函数会检查unsorted chunk在链表中的情况

首先执行的是unlink，其次会对unsorted chunk在链表中的情况进行检查

链表释放前会检查当前chunk size 与后一个chunk的prev_size

unlink 后向合并

unlink 前向合并

unlink会检查chunk是否在链表里

free 中的unlink执行双链表检测

前项合并

后向合并

malloc时unsortedbin 不执行unlink

malloc函数会首先搜索smallbin和largebin，当有空闲的unsortedbin时，再搜索unsortedbin，方法是从unsorted的首块开始进行链表的清空（只有malloc会这样拆卸unsorted表）。所以可以用作unsorted attack

malloc时smallbin不执行unlink操作

总结

具体的总结如下，终于可以好好的总结一下了。

1.freefree 操作里面会有子操作unlink，unlink（会进行双向链表检测，检测过后就是赋值操作）。

如果是smallbin chunk直接进行unlink检测 如果是unsorted chunk还需要对其进行unsorted检测

之后会有一个对于链表的操作

2.mallocmalloc里面是不执行unlink操作的，对于smallbin只会检测 p->bk-fd==p对于unsortedbin 不会进行检测，所以会造成unsorted attack攻击

3.all最后就是每次在free list中卸掉链表都需要对所拆链表的size和下一块的prev_size进行比较。这一点不论是free还是malloc都遵循。

文章仅用于普及网络安全知识，提高小伙伴的安全意识的同时介绍常见漏洞的特征等，若读者因此做出危害网络安全的行为后果自负，与合天智汇以及原作者无关，特此声明。