堆溢出综述

本实验中，我将带领大家通过几个程序了解一下WindowsXP中的堆内存管理机制以及几个重要的堆结构，然后进行堆溢出的调试与简单利用。

什么是堆？从程序员的角度看，堆具备以下特性。

（1）堆是一种在程序运行时动态分配的内存。所谓动态是指所需内存的大小在程序设计时不能预先决定，需要在程序运行时参考用户的反馈。

（2）堆在使用时需要程序员用专用函数进行申请，如C语言中的malloc等函数，C++中的new函数等都是最常见的分配堆内存的函数，堆内存申请有可能成功，也有可能失败，这与申请内存的大小、机器性能和当前运行环境有关。

（3）一般用一个堆指针来使用申请得到的内存，读、写、释放都通过这个指针来完成。

（4）使用完毕后需要把堆指针传给堆释放函数回收这片内存，否则会造成内存泄漏。典型的释放函数包括free、delete等。

步骤1：了解堆的数据结构与管理策略

堆的相关数据结构

• 堆块

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

• 堆表

  堆表一般位于堆区的起始位置，用于索引堆区中所有堆块的重要信息，包括堆块的位置、堆块的大小、空闲还是占用等。堆表的数据结构决定了整个堆区的组织方式，是快熟检索空闲块，保证堆分配效率的关键。

  在windows中，占用态的堆块被使用它的程序索引，而堆表值索引所有空闲态的堆块。其中，最重要的堆表有两种：空闲双向链表Freelist和快速单向链表Lookaside。

• 空表Freelist

  空闲堆块的块首中包含一对重要的指针，这对指针用于将空闲堆块组织成双向链表。按照堆块的大小不通，空表总共被分为128条。

  堆区一开始的堆表区中有一个128项的指针数组，被称做空表索引（Freelist array）。该数组的每一项包括两个指针，用于表示一条空表。

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

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

• 快表Lookaside

  快表是Window用来加速堆块分配而采用的一种堆表。这里之所以把它叫做“快表”是因为这类单向链表中从来不会发生堆块合并（其中的空闲块块首被设置为占用态，用来防止堆块合并）。

  快表也有128条，组织结构与空表类似，只是其中的堆块按照单链表组织。快表总是被初始化为空，而且每条快表最多只有4个结点，故很快就会被填满。如下图所示:

堆管理策略

• 分配算法

  • 小块

    首先进行快表分配；若快表分配失败，进行普通表分配；若普通表分配失败，使用堆缓存（heap cache）分配；若堆缓存分配失败，尝试零号空表分配（freelist[0]）；若零号空表分配失败，进行内存紧缩后再尝试分配；若仍无法分配，返回NULL

  • 大块

    首先使用堆缓存进行分配；若堆缓存分配失败，使用free[0]中的大块进行分配。

  • 巨块

    一般来说，巨块申请非常罕见，要使用到虚分配方法（实际上不是从堆区分配的）。这种类型的堆块在堆溢出利用中几乎不会遇到，本节暂不讨论。

• 释放算法

  • 小块

    优先链入快表（只能链入4个空闲块）；如果快表满，则将其链入相应的空表。

  • 大块

    优先将其放入堆缓存；若堆缓存满，将链入freelist[0]。

  • 巨块

    直接释放，没有堆表操作。

步骤2：通过实例了解HeapAlloc分配堆块的过程

首先要明确Lookaside表是一个单链表，每次HeapFree释放的堆块被插到链表头，每次HeapAlloc都从链表头取一项然后返回给申请者；链表尾指向空。进程内存空间中有这样的单链表共128项，以数组形式管理。

新建一个文本文档，将其重命名为HeapAlloc.c，右键 -> 打开方式 -> Microsoft ® Developer Studio，用Visual Studio 6.0打开并编辑，写入如下内容：

#include ＜stdio.h＞
#include ＜windows.h＞  


int main()  
{  
    HLOCAL h1,h2,h3,h4,h5,h6,h7,h8,h9;  
    char* pi=NULL;  
    HANDLE hp;  
    char xpsp1Str[8] = {0};  


    hp = HeapCreate(0,0,0);  
    getchar();  
    __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,16);  
    h6 = HeapAlloc(hp,HEAP_ZERO_MEMORY,16);  
    h7 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);  

    HeapFree(hp,0,h1);  
    HeapFree(hp,0,h2);  
    HeapFree(hp,0,h3);  
    HeapFree(hp,0,h4);  
    HeapFree(hp,0,h5);  
    HeapFree(hp,0,h6);  
    HeapFree(hp,0,h7);  

    h8 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);  
    h9 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);  
    return 0;  
}

在菜单栏右键选择Build选项卡，然后将Win32 Debug修改成Win32 Release，然后依次点击 Compile -> Build -> Execute三个键，如下图所示来运行程序：

此时程序在等待我们输入，随便输入一个字符，发现程序崩溃了(根据环境不同，可能会在程序崩溃时没有系统错误提示，但不影响后续实验)。如下图：

这是由于我们在代码中设置了__asm int 3的缘故，这样做是为了能调试正常状态下的堆分部，我们把Windbg调试器设置为即时调试器，只要程序一出现异常，Windbg调试器会立马捕捉到异常，并到达异常现场。设置命令如下图所示：

依次点击 Compile -> Build -> Execute三个键，然后输入一个字符后，你应该能看到下面界面：

Windbg调试器已经捕捉到异常，并来到了异常现场。我们在0:000>命令框中输入p然后回车，一共进行5次操作，p命令其实是单步F10。执行后如下图所示：

为了证明开始时几个HeapAlloc分配得到的堆块来自私有堆空闲链表，可用dt _HEAP @esi命令验证，在命令行中输入dt _HEAP @esi然后回车，接着输入p然后回车，如下图所示：

esi中存放的是堆句柄。此时我们看一下反汇编窗口，如下图所示：

红框中四行汇编指令对应的C语言便是h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);,eax寄存器中的值便是h1。

解释一下：

1.程序开始时，堆管理器中只有一大块空闲内存，由FreeList[0]指向，当前FreeList[0]的地址是003a0178（怎么计算的？esi+0x178偏移），空闲内存地址是003a1e90。对于这段代码，开始的几句HeapAlloc都是瓜分这块内存区域的内存;

2._HEAP!FrontEndHeap指向程序快表地址，对于这段代码，快表位于003a0688;

3.由于MS并没有公开快表结构，对于xp系统，只知每个快表项占0x30B，按调试的结论,可能是这样的结构:

struct   
{  
    DWORD* next; //同一链表中下一元素地址  
    WORD entryCount1; //链表中元素个数  
    WORD unknownW;  
    DWORD unknownDW1;DWORD maxEntryCount; //链表中最多容纳元素数量  
    DWORD unknownDW2;DWORD entryCount2;//链表中元素个数  
    QWORD unKnownQ D1,unKnownQ D2,unKnownQ D3;  
};

4._HEAP!FrontEndHeap指向的区域的头0x30B可能是一个快表数组管理结构，之后才是快表数组。目前整个快表数组都是空的,输入dd 003a0688回车，如下图所示：

我们知道h1为003a1e90，我们继续单步把h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);对应的汇编代码执行完，来到地址00401050时，我们观察eax寄存器的值,如下图所示：

我们发现此时eax中的值为003a1ea0，如果还不确定，我们再单步把h3 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);对应的汇编代码执行完，来到地址0040105a时，我们再次观察eax寄存器的值，如下图所示：

我们发现此时eax中的值为003a1eb0，联合h1的值3a1e90，每次分配到的内存都和前面相差0x10B，好奇怪啊，每次调用HeapAlloc请求分配8B，结果分配到0x10B，而且前后间隔是等间距的，这是因为什么？

因为对于非调试运行的Release程序HeapAlloc每次分配8+8N的空间，其中8B是用户空间的管理结构HEAP_ENTRY(细节可参考张银奎老师<软件调试>23章)，记载着调用HeapAlloc时分配的空间大小,紧随HEAP_ENTRY之后的8N8是用户请求空间的数值向上取整的结果，作为用户可用空间返回给请求者，输入命令:dt _HEAP_ENTRY回车，看到_HEAP_ENTRY的结构体布局：

0:000> dt _HEAP_ENTRY
ntdll!_HEAP_ENTRY
   +0x000 Size             : Uint2B  粒度个数
   +0x002 PreviousSize     : Uint2B  前一个堆块大小
   +0x000 SubSegmentCode   : Ptr32 Void
   +0x004 SmallTagIndex    : UChar
   +0x005 Flags            : UChar   堆的状态
   +0x006 UnusedBytes      : UChar
   +0x007 SegmentIndex     : UChar

然后输入命令：dt _HEAP_ENTRY 0x3a1e90-8（h1的Heap_Entry）回车，输入命令：dt _HEAP_ENTRY 0x3a1ea0-8（h2的Heap_Entry），如下图所示：

SIZE为2（粒度个数），2*8（粒度大小）=0x10B HEAP_ENTRY占用8B 用户请求8B，Flags表示占用态，PreviousSize 表示为上次分配的堆块大小，即h1分配的空间。

我们继续往下调试，接下来是分配h4/h5/h6/h7的堆块，由于都是相同的，我们快速单步步过到地址：0040108f对应的汇编为call ebx {ntdll!RtlFreeHeap (7c92ff0d)}直到调用HeapFree释放空间，按前面结论，释放的空间应该暂住在快表中(对于xp，快表中其实只能容纳4个同样大小的堆块，超过4个还是要进入空闲链表)，这是第一次调用HeapFree释放h1。我们再单步F10一下，然后输入命令：dd 003a0688回车，如下图所示：

0:000> dd 0x003a0688
003a0688  00000000 00000000 01000004 00000000
003a0698  00000000 00000000 00000000 00000000
003a06a8  00000000 00000007 00000000 00000000 前0x30B 快表管理头 
003a06b8  00000000 00000000 01000004 00000000
003a06c8  00000000 00000000 00000000 00000000
003a06d8  00000000 00000000 00000000 00000000 中0x30B 快表数组[0]
003a06e8  003a1e90 00010001 01000004 00000004 快表数组[1]
003a06f8  00000004 00000001 00000000 00000000

套用前面的结构，003a06e8处的内容应该是这样:

struct   
{  
    DWORD* next; //同一链表中下一元素地址=003a1e90   
    WORD entryCount1; //链表中元素个数=1  
    WORD unknownW;  
    DWORD unknownDW1;  
    DWORD maxEntryCount; //链表中最多容纳元素数量=4  
    DWORD unknownDW2;  
    DWORD entryCount2; //链表中元素个数=1  
    QWORD unknowQD1,unknowQD2,unknowQD3;  
};

为验证，我们快速单步F10释放h2/h3/h4来到地址：004010ac时，待h2-h4全部释放完，我们来看下快表[1]中单链表的内容，如下图所示：

如下解释：

struct   
{  
    DWORD* next; //同一链表中下一元素地址=003a1ec0 原h4释放   
    WORD entryCount1; //链表中元素个数=4  
    WORD unknownW;  
    DWORD unknownDW1;  
    DWORD maxEntryCount; //链表中最多容纳元素数量=4  
    DWORD unknownDW2;  
    DWORD entryCount2; //链表中元素个数=4  
    QWORD unknowQD1,unknowQD2,unknowQD3;  
};  

:000> dd 003a1ec0 L1  
003a1ec0  003a1eb0 ;下一个节点地址是原h3释放的  
0:000> dd 003a1ec0 L1  
003a1ec0  003a1eb0 ;下一个节点地址是原h2释放的  
0:000> dd 003a1eb0 L1  
003a1eb0  003a1ea0 ;下一个节点地址是原h1释放的  
0:000> dd 003a1ea0 L1  
003a1ea0  003a1e90 ;下一个节点为空!  
0:000> dd 003a1e90 L1  
003a1e90  00000000

从Windbg调试输出可知，后释放的堆块被链在单链表的最开头部分。

最后，我们来看下从快表中分配堆块。因为这次快表[1]中有元素了，因此如果请求的堆块的大小和快表[1]中大小相同，堆管理器就从中取堆块返回给调用者。我们单步F10到达地址：004010cc处，对应的汇编为：call edi {ntdll!RtlAllocateHeap (7c9300a4)}，此时对应的C语言为：h8 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);，然后再单步F10一次，执行后，输入命令：dd 003a06e8 L2回车，然后再单步F10执行到地址：004010d5后，输入命令：dd 003a06e8 L2回车后，如下图所示：

第一次调用HeapAlloc从快表[1]的单链表中取表头元素，这是前面h4释放的，0003说明快表中还剩3个堆块;第二次调用HeapAlloc，仍从快表[1]的单链表中取表头元素，这是前面h3释放的，同时0002说明快表中还剩2个堆块。

到此，我们就把堆中的相关数据结构和管理策略通过调试的方式进行熟悉和了解。