操作系统版本： Windows Xp

编译器：Vc6.0

编译模式：Release

前言

在Windows中的申请堆内存的方式有很多，例如：LocalAloc、malloc等

在这些函数实际上内部都是调用RtlAllocateHeap函数进行申请的，在分析对堆的数据结构时，只分析这一个函数就够了

堆表概念

堆表位于堆区的起始位置，用于索引堆区的重要信息，堆表设计时考虑了使用平衡二叉树结构，以提高检索效率，而现代操作系统的对标往往不止一种数据结构

在堆表中有两个重要的数据结构，快表和空表，用于分配、释放、回收堆空间

空表

空表中保存了申请栈空间的地址，以链表（双向链表）的方式保存

空表中保存了128个项，每项都是一个单独的链表，每项包含了8个字节的空间，这8个字节的空间保存了两个地址，分别是链表的起始地址和结束地址

空表不同项保存的空间大小 = 空表项序号 * 8 ，例如：空表[3] = 3 * 8 = 24 字节，在空表[3]链表中的每一项都保存了24字节空间，除0项外，其余同理

0号项除外，0号项保存了所有大于等于1024字节的堆块，小于512KB，按大小升序的方式链接在0项的链表中

当HeapCreate结束后，空表除了0项以外，其余项保存的两个地址均指向自身，代表此项尚未初始化

当在HeapCreate后，使用其返回值（句柄）分配8字节空间后释放，这个8字节空间将从空表的0项切割出8字节空间，释放后将其地址链入空表1项，在释放后空表1项的地址也就不会指向自身了，在次申请8字节空间时将在空表中优先查找

空表链表图式

快表

快表中同样包含128项，每项以单链表方式链接，在初始化时也与空表不同，初始化时的快表每一项都为空，且每项最多包含4个节点，故快表相比空表更容易填满

快表链表图示

堆块操作

堆块操作分为，释放、合并、分配三种，其合并是由堆管理系统完成的，其余都是程序中代码执行的

分配

当分配事件发生后，存在三种分配方式，快表分配、空表分配、0号空表分配

在快表分配时，寻找大小匹配的空闲块，将状态修改为占用态、把它从堆表中“卸下”，最后返回一个指向堆块块身的指针给程序使用

空表分配时，会优先寻找最优的空闲块，如找不到，会寻找最小能满足要求的空闲块

零号空表按大小升序的排列方式，保存了大小不同的堆块，在分配时会在此链表中反向查找最后一个块，也就是最大块，如果能满足需求，则重新正向搜素最小能满足空闲堆块分配

”找零钱”，当空表中无法找到适当的堆块时，会找一个稍大些的堆块进行分配，在分配时将此堆块精确切割为所需大小，将大块堆块剩下的部分重新写入堆块的块首，并链入0号空表

在快表中，只有精确匹配时才会分配，也就不存在“找零钱”的现象

释放

释放堆块时，首先将堆块的状态设置为空闲，后将其链入相应的对表中，释放后的块会被链入对应项中链表的末尾，分配时同样也从链表末尾中取出来

快表中最多保存4项内容

合并

在反复申请释放堆内存后，避免产生内存碎片会出现堆块合并

当堆管理系统发现两个空闲堆块彼此相邻的时候，会将两个堆块合并

堆块合并包括，将两个块从空闲链表中卸下，合并堆块，调整合并后大块的块首信息，将新块重现链入空闲链表

在具体分配和释放时，根据操作内存的大小不同，Windows采取的策略也不同，可以把内存分为3类：

小块：SIZE < 1KB

大块：1KB <= SIZE < 512KB

巨块：SIZE >= 512KB

	分配	释放
小块	首先进行快表分配快表分配失败，使用空表分配空表分配失败，使用堆缓存分配堆缓存分配失败，0号空表分配0号空表分配失败，进行内存紧缩后再次尝试仍无法分配返回NULL	优先链入快表（只能链入4个空闲块）若快表填满，链入空表
大块	首先使用堆缓存分配若堆缓存分配失败，使用零号空表的大块进行分配	优先将其放入堆缓存若堆缓存满，链入零号空表
巨块	巨块申请很罕见，用虚方法分配，实际不是从堆区分配的	直接释放没有堆表操作

Windows 堆管理特点

快表中的空闲块被设置为占用态，故不会发生堆块合并操作
快表只有精确匹配时才会分配，不存在”次优解”和“找零钱”
快表是单链表，操作会比双链表简单，插入删除都少用很多指令
在分配与释放时总是优先使用快表，失败后才用空表
快表只有4项，很容易被填满，所以空表也是频繁使用的

堆调试

在调试堆时，不可以直接使用调试器加载exe进行调试，当直接加载时，exe被标记为调试模式，在调试状态下将会启用调试态对管理策略，主要差异如下：

调试堆不使用快表，只使用空表分配
所有堆块都被加上了多余的16字节尾部，用来防止溢出（防止程序溢出而不是堆溢出攻击），这包括8字节的0xAB和8字节的0x00
块首的标识位不同

当代码在调试状态下正常运行，在Release模式下崩溃，很有可能就是这个原因

代码

#include "stdio.h"
#include "stdlib.h"
#include <windows.h>

int main(int argc, char* argv[])
{
	HLOCAL h1,h2,h3,h4,h5,h6;
	HANDLE hp;
	hp = HeapCreate(0, 0x1000, 0x10000);

	_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);

	HeapFree(hp, 0, h1);
	HeapFree(hp, 0, h3);
	HeapFree(hp, 0, h5);

	HeapFree(hp, 0, h4);
	return 0;
}

将代码编译为Release模式后并运行，当代码运行到第11行会出现异常，这时Windows会提示你是否需要附加到调试器，在此附加到调试器即可进行调试

堆结构

运行上述代码并附加到调试器后，EAX中存储的就是HeapCreate返回的内存地址（句柄）

以此地址为基地址，+0x178的偏移位置就是空表的位置

每8个字节为空表的一项，在这里注意到除了0项外的所有空表项都是指向自身

跳转到0号空表地址处

此地址（3A0688）保存的第一个地址为链表的上一个节点，（3A068C）保存的第二个地址为下一个节点

此地址-8 *（（DWORD*)3A688 - 8) **中的4个字节，保存了这个堆块的大小

这4个字节分为两部分，每两个字节为一部分，转换成数值为0x130 和 0x8，0x130代表当前堆块的大小为 0x130 * 8，0x8代表上一个堆块占用的空间为0x8 * 0x8

此地址-4 *（（DWORD*)3A688 - 4) **中的4个字节，保存了这个堆块的一些标志位，详见下图

在3A0680开始后的8个字节为块头，而链表中保存的地址跳过了这8个字节，但是在块大小中是包含这8个字节的，此堆块的大小为0x130 * 8，在这个大小中是包含块头的8个字节大小的

其他非0项空表的结构与其相同

运行流程

单步执行过第一个分配操作之后，此次申请将会在0项空表中进行分割，分割后重新修改两个块的块头信息，结束之后将标志位设置Busy，并将地址返回

在第一次释放时，根据释放的大小 / 8 决定将这个堆块放入空表的哪一项中，并修改其标志位

出现多次释放时，若两个块空闲块相邻，将合并这几个堆块，后修改其块首，使用新的堆块大小 / 8，来放入对应空表的位置

当多次释放后，再次申请时优先在空表中查找符合大小的堆块，并在链表尾端摘出此堆块，如果存在，返回给程序使用，如不存在…(详见堆块操作中的分配部分)

快表问题

在上面的代码中是没有用到快表的，若想使用快表，需要将上面代码的第9行替换为

1	hp = HeapCreate(0, 0, 0);

这时空快表就会被启用了

快表被启用后，HeapCreate返回的地址 + 0x688 处将不会是0号空表指向的位置了，这个地址被快表占领了

在上面运行流程的释放过程也会发生变化，释放时优先释放到快表结构中，释放到快表时，不会将堆块的块头标志位修改为空闲状态，也是因为这个原因快表中不会出现合并的情况

快表中的每项只保存4个堆块，如快表[4]对应的链表中，已经有了4个堆块，那么又产生了一次释放，对应的快表项还是快表[4]，在这种情况下会将其保存到空表中

在快表启用的状态下，多次释放后，再次申请时优先在快表中查找符合大小的堆块，并在链表尾端摘出此堆块，如没有则在空表中查找，如果存在，返回给程序使用，如不存在…(详见堆块操作中的分配部分)

溢出利用点分析 DWORD SHOOT

在上述中，如果出现申请堆空间的情况，如空表中出现大小匹配的块，那么将在空表[*]的位置中取出链表指针，并将链表中的最后一项摘下来返回程序使用

这时就产生了一次链表摘除操作，链表摘除时代码模拟：

int remove(ListNode *node)
{
	node->blink->flink = node->flink;
	node->flink->blink = node->blink;
}

我们通过溢出的方式修改node的两个节点的内容来进行对某一内存的修改

首先我们需要申请堆块，大小随意如0x200，假定地址为0x401000，那么0x401200处为下一个堆块的块头，保存下一个堆块的大小和标志，则0x401208处则保存了下一个堆块的链表数据，

我们通过溢出的方式将下一个堆块的链表中的两个数据进行修改，这样当堆管理器对这个堆块进行操作的时候（合并、分配、摘除），将会出发Dword Shoot

Good Job