[TOC]

PS：如果您熟悉堆的工作原理，建议您跳过堆的介绍部分，直接看堆溢出原理

堆的工作原理

堆与栈的区别

1、栈 (stack) ，是一种在程序设计时就规定好大小及使用方式的内存，由操作系统自动分配释放，用于存放函数的参数值、局部变量等。栈总是成“线性”变化。栈向低地址空间增长。

2、堆 (heap)，是一种在程序运行时动态分配的内存，由开发人员分配和释放，若开发人员不释放，程序结束时由OS回收，分配方式类似于链表。堆向高地址增长。

下图是经典的32位系统内存布局，暂时我们只需要记住栈和堆的增长方向即可，后面实验部分会用到。

堆的数据结构与管理策略

程序员使用堆只做三件事：

• 申请一定大小的内存
• 使用内存
• 释放内存

堆管理系统响应申请，就意味着要在 “`杂乱无章¹]” 的内存中 “辨识²” 出空闲的内存，“寻找” 一片 “恰当³” 的空闲内存区域，以指针的形式返回给程序。

堆表：堆表一般位于堆区的起始位置，用于索引堆区中所有堆块的重要信息，包括堆块的位置、堆块的大小、空闲还是占用等。堆表的数据结构决定了整个堆区的组织方式，是快速检索空闲块、保证堆分配效率的关键。堆表在设计时可能会考虑采用平衡二叉树等高级数据结构,用于优化查找效率。现代操作系统的堆表往往不止一种数据结构。

堆块：出于性能的考虑，堆区的内存按不同大小组织成块，以堆块为单位进行标识，而不是传统的按字节标识。一个堆块包括两个部分：块首和块身。块首位于一个堆块头部的几个字节，用来标识这个堆块自身的信息，例如，本块的大小、本块空闲还是占用等信息；块身是紧跟在块首后面的部分，也是最终分配给用户使用的数据区。

堆的内存组织如下图：

在 Windows 中，占用态⁴的堆块被使用它的程序索引，而堆表只索引所有 空闲态⁵ 的堆块。

堆表

堆表的实现

在 Windows 中，堆表实现方法两种：空闲双向链表 Free list（简称空表）和快速单向链表 Look aside（简称快表）

空闲双向链表（空表）

堆区一开始的堆表区中有一个128项的指针数组，被称做空表索引（Freelist array）。该数组的每一项包括两个指针，用双向链表组织一条空表,如下图。

空表索引的第二项（free[1]）链接了堆中所有大小为8字节的空闲堆块，之后每个索引项链接的空闲堆块大小递增8字节，例如，free[2]链接大小为16字节的空闲堆块，free[3]链接大小为24字节的空闲堆块，free[127]标识大小为1016字节的空闲堆块。因此有：

空闲堆块的大小＝索引项（ID）×8（字节）

空表索引的第一项（free[0]）所标识的空表相对比较特殊。这条双向链表链接了所有大于等于1024字节的堆块（小于512KB）。这些堆块按照各自的大小在零号空表中升序地依次排列下去.把空闲堆块按照大小的不同链入不同的空表，可以方便堆管理系统高效检索。

快速单向表（快表）

快表是 Windows 用来加速堆块分配而采用的一种堆表。这里之所以把它叫做“快表”是因为这类单向链表中从来不会发生堆块合并,快表也有128条，组织结构与空表类似,只是其中的堆块按照单链表组织。快表总是被初始化为空，而且每条快表最多只有4个结点，故很快就会被填满。

快表结构：

堆中的操作

堆中的操作分为三种：堆块分配，堆块释放，堆块合并。（其中 “分配” 和 “释放” 是在程序提交申请时执行的，而堆块合并是由堆管理系统自动完成）

堆块分配

堆块分配分为三类：

• 快表分配：找到大小匹配的空闲堆块、将其状态修改为占用态、把它从堆表中“卸下”、最后返回一个指向堆块块身的指针给程序使用；
• 普通空表分配： 首先寻找最优的空闲块分配，若失败，则寻找次优的空闲块分配⁶，即最小的能够满足要求的空闲块；
• 零号空表（free[0]）：先从 free[0]反向查找最后一个块（即表中最大块），看能否满足要求，如果能满足要求，再正向搜索最小能够满足要求的空闲堆块进行分配。

堆块释放

释放堆块的操作包括将堆块状态改为空闲，链入相应的堆表。所有的释放块都链入堆表的末尾，分配的时候也先从堆表末尾拿。快表最多只有4项

堆块合并

条件：当堆管理系统发现两个空闲堆块彼此相邻的时候，就会进行堆块合并操作。

堆块合并将两个块从空闲链表中 “卸下”、合并堆块、调整合并后大块的块首信息（如大小等）、将新块重新链入空闲链表。

堆块

根据堆块是否被占用分为占用态堆块和空闲态堆块。

占用态堆块的数据结构如下：

空闲态堆块的数据结构如下：

对比上面两图可知，空闲态堆块和占用态堆块的块首结构基本一致。相对于占用态的堆块来说，空闲态堆块的块首后8个字节存放了两个指针地址，分别指向前驱堆块和后驱堆块。

Self Size：块整体的大小，包括块首和块身

Previous chunk size：前一个块的大小

Segment Index：段索引

Flags：标志位，用于标志块的状态，即空闲态/占用态

Unused bytes：未被使用的字节大小

Tag index(Debug)：

Flink in freelist：（Forward Link）指向下一个节点

Blink in freelist：（Backward Link）指向前一个节点

单链表和双链表

LIST_ENTRY 结构 (ntdef.h)

在堆中漫游

堆分配函数之间的调用关系

Windows 堆分配的 API 调用关系

所有的堆分配函数最终都将使用位于 ntdll.dll 中的 RtlAllocateHeap() 函数进行分配。

堆的调试方法

实验代码

#include <windows.h>
main()
{
	HLOCAL h1,h2,h3,h4,h5,h6;
	HANDLE hp;
	hp = HeapCreate(0,0x1000,0x10000);//Create a heap of specified size
	__asm int 3

	h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,3);
	h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,5);
	h3 = HeapAlloc(hp,HEAP_ZERO_MEMORY,6);
	h4 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
	h5 = HeapAlloc(hp,HEAP_ZERO_MEMORY,19);
	h6 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);
	
	//free block and prevent coaleses
	HeapFree(hp,0,h1); //free to freelist[2] 
	HeapFree(hp,0,h3); //free to freelist[2] 
	HeapFree(hp,0,h5); //free to freelist[4]
	
	HeapFree(hp,0,h4); //coalese h3,h4,h5,link the large block to freelist[8]

	
	return 0;
}

注意：_asm int 3 是中断指令，用来中断程序，因为如果直接加载程序到 Ollydbg ，程序将使用调试态堆管理策略，而调试态堆管理策略和常态堆管理策略有很大不同： （1）调试堆不使用快表，只用空表分配。 （2）所有堆块都被加上了多余的 16 字节尾部用来防止溢出（防止程序溢出而不是堆溢出攻击），这包括 8 个字节的 0xAB 和 8 个字节的 0x00。 （3）块首的标志位不同。

调试

在调试前我们先将我们的调试工具 Ollydbg 设为默认调试器

1. 首先以管理员身份打开 Ollydbg
2. 在菜单栏下找到 选项 –> 选项

3. 在选项的菜单栏中找到杂项，勾选将这份x64dbg设为即时调试器，然后保存

设置完成后，直接进入vc++6.0，编译成功后，我们直接双击运行，如下

单击 “否” ，将自动打开 Ollydbg 并附加上进程，并在断点处停下来。 根据源码可知，中断是发生在HeapCreate函数执行完成后的，HeapCreate执行后会返回堆地址，结果保存在eax中，我们在调试器发现eax值是：0x003A0000

也就是说HeapCreate创建的堆区起始位置在003A0000，即堆表从此位置开始，堆表中依次为段表索引（Segment List）、虚表索引(Virtual Allocation list)、空表使用标识（freelist usage bitmap）和空表索引区。

此处我们只关心堆偏移0x178 处的空表索引区，这个偏移是堆表起始的位置（根据上次我们介绍的堆表结构，堆表包含128的8个字节的flink和blink地址。所以堆表的结束位置在：128*8=1024=0x400,加上偏移，0x178+0x400=0x578）

加上堆基址0x003A0000+0x178=0x003A0178，单击内存1，在内存1中按ctrl+G，输入刚刚计算出的地址，回车，我们来到了这个地址。 如图，这个地址便是free[0]，占8个字节，flink和blink都指向尾块的地址，都是0x003a0688。后面的依次是free[1]、free[2]，依次类推，我们发现free[1]、free[2]…free[127]都指向自身，它们都是空链表。

所以当一个堆刚刚被初始化时，只包含一个空闲态的大块，这个块也叫为"尾块" free[0]指向这个"尾块"

我们转到"尾块"的位置去看看（因为这里只有一个堆块，即free[0]指向的地址，free[0]=0x003a0688）

空闲态的堆块有8个字节的 flink（指向前驱节点） 与 blink（指向后继节点），此处的值均为0x003a0178，这个地址是堆表 free[0] 的地址，实验与理论相符。

实际上，HeapAlloc() 返回的堆地址是指向块身的。在其前面还有8个字节的块首，所以这个堆块起始于0x003a0680。前2个字节为块大小，此处值是0x130, 堆的计算单位是8字节，也就是0x980字节。

注意：堆大小包含块首在内。

堆块分配

堆块要点总结：

• 堆块的大小包括了块首在内，即如果请求32字节，实际会分配的堆块为40字节：8字节块首＋32字节块身；
• 堆块的单位是8字节，不足8字节的部分按8字节分配；
• 初始状态下，快表和空表都为空，不存在精确分配。请求将使用 “次优块” 进行分配（这个“次优块”就是位于偏移 0x0688 处的尾块，见上一节最后一张图）
• 由于次优分配的发生，分配函数会陆续从尾块中切走一些小块，并修改尾块块首中的 size 信息，最后把 freelist[0] 指向新的尾块位置。

内存请求分配情况

在调试器中，我们单步走过第一个HeapAlloc，然后观察内存空间。

tips: 对于我们主动设置的int 3指令，如果调试器忽略异常后仍无法步过的话，可以在下一行代码处右键，选择 “此处设为新的eip”。

按上面的分析，执行完h1 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 3);后，会从0x3a0680地址开始切出一块大小为2个单位（16字节）的空间分配给h1, 新的尾块起始地址则为0x003a0690，flink与blink地址位于0x003a0698和0x003a069c,其值0x003a0178指向freelist[0], freelist[0]则指向新的起始地址0x003a0698，(003a0690+8字节的块首，我们上面有提到过指向块身。)

尾块起始处，如下图，如我们所预期的一样

另外，尾块的大小为0x12e【0x130-2=0x12e个单位（堆的单位，8个字节）】，如上图，也可以验证。 h1所指向的堆块起始位置则是0x003a0680，如上图可知，大小为2个单位

堆表 freelist[0] 处，如下图，如我们所预期的一样

接着，执行h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 5); ，将会从尾块中再切一块大小为2个单位（16字节）的空间给h2，然后freelist[0]指向新的尾块起始地址，新的尾块指针仍指向 freelist[0]，剩下的尾块大小为12e-2=12c个单位。

剩下的依次类推，当执行完h6 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 24);后，堆分配情况如下图所示

剩下的堆大小为 130-2-2-2-2-4-4=120单位，尾块仍指向 freelist[0]（0x003a0178），如下图

到此，堆的分配则执行完了。根据上面的理论可知，堆表中仍只有一个尾块，不存在其它的堆块。

堆块释放

由于前三次释放的堆块在内存中不连续，因此不会发生合并。按照其大小， h1 和 h3 为16字节，则被链入 freelist[2]， h5 为 32字节，则被链入 freelist[4]。

当执行HeapFree(hp, 0, h1)后，h1 会被链入 freelist[2]，所以我们来看看 freelist[2] 的地址； 由于 freelist[0] 的地址为0x003a0178，所以 freelist[2] 的地址为0x003a0188（=0x003a0178 + 2*0x8）

执行前，如下图。freelist[2] 指向自己，还是空表

执行后，根据链表规则freelist[2]会指向h1的地址，如下图，h1则会指向freelist[2]

执行后，原来h1所指向的堆块变为空闲态并指向 freelist[2]。如下图，flink与blink都指向freelist[2]，因为此时freelist[2]链表中就只有一个节点

接着会释放h3，执行HeapFree(hp, 0, h3)，执行完后，h3所指向的堆块会被链入到freelist[2]，并插入到整个链表的末尾。

如下图所示，h3 的 blink（地址0x003a06ac）指向前一个堆块，即原来的h1。h3的flink则指向freelist[2]，因为它是最后一个元素。原来的h1的blink指向freelist[2]，flink指向h3

执行后的freelist[2]（0x003a0188），如下图

形成的链表大概如下：

freelist[2] <---> h1 <---> h3

**注：**h3的flink与freelist[2]的blink未给出。

再下一步，执行HeapFree(hp, 0, h5);，释放h5所在的堆块，并链入freelist[4]

堆块合并

条件：释放两个相邻的空闲块会发生堆块合并操作

步骤：

1. 进行第四步RtlFreeHeap()，释放 h4 后，进行堆块合并
2. 首先将从空表中摘下 h3,h4,h5 三个空闲块
3. 然后重新计算合并后新堆块的大小，2+2+4=8(堆单位：8字节)
4. 最后按照合并后的大小，把新块连入链表 freelist[8]

我们来看看 freelist[8]（0x003a01b8），如下图 可以看到，0x003a06a8已经被链入freelist[8]中了， freelist[2]（003a0188)中也只剩下 h1（003a0688)，因为 h3 在合并时被摘下了， freelist[4]（00ea0198)也指向自身了，因为 h5 在合并时也被摘下来了

进入0x003a06a8，如下图 可以看到，合并只修改了块首的数据，原来的块身基本不变，大小变成了0x0008，空表指针指向0x003a01b8（就是freelist[8])

注意：

• 堆块合并只发生在空表中 因为堆块合并要修改多处指针，比较耗时，所以在强调分配效率的快表中，禁止堆块合并
• 空表中的第一个块不会向前合并，最后一个不会向后合并

快表的使用

实验代码

#include <stdio.h>
#include <windows.h>
void main()
{
	HLOCAL h1,h2,h3,h4;
	HANDLE hp;
	hp = HeapCreate(0, 0,0); //Create a heap of dynamically assigned
	__asm int 3
	h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
	h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
	h3 = HeapAlloc(hp,HEAP_ZERO_MEMORY,16);
	h4 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);
	HeapFree(hp, 0, h1);
	HeapFree(hp, 0, h2);
	HeapFree(hp, 0, h3);
	HeapFree(hp, 0, h4);
    h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,16);
    HeapFree(hp,0,h2);
}

注意：

​ 使用快表后，堆结构会发生变化，最主要的变化是 “尾块” 不在位于堆 0x0688 偏移处了，这个位置被快表霸占。

调试

我们先来看看空表索引区发生了哪些变化，如下图 可以看到，在0x003a0178处变为了003a1ee8，不再是0x003a0688

现在我们来看看快表（0x003a0688），在偏移 ox0688处，如下图 可以看到，堆刚初始化，快表是空的

然后我们将将代码调试到，释放完 h4之后，如下图所示

根据四个堆块大小我们可以知道，h1,h2 将会被插入到 Lookaside[1]中，h3 会被插入到 Lookaside[2]中，h4会被插入到 Lookaside[4]中，快表区状态，如下图 可以看到，003a1ea0是 8字节堆块地址，003a1eb0是16字节堆地址，003a1ec8是24字节堆地址

进入003a1ea0，来看看堆块状态，如下图 紫色框的为下一堆块指针，红色框为堆块状态，ox01表示是 Busy 状态 块首只存指向下一堆块的指针，不存再指向前一堆块的指针。

接着申请 16 字节的空间，系统会从 Lookaside[2]中卸载一个堆块分配给程序，同时修改 Lookaside[2] 表头，如下图

可以看到，Lookaside[2]（0x003a0718)处变为空了。

总结

• 堆的数据结构： 堆块、堆表
• 堆块：包含块首、块身
• 堆表：空闲双向链表（freelist）、快速单向链表(lookaside)
• 占用态的堆块：8字节的块首+块身
• 空闲态的堆块：16字节的块首（多了flink与blink）+块身。空闲态的堆块变为占用态时，flink与blink所在的空间将变为data区。

参考：

• 《0day,软件安全漏洞分析技术》

• 《深入分析 win32 堆结构与管理策略》