堆溢出研究试验

发表于 | 分类于 |

1. 环境准备


针对堆进行调试，我整整花了3天时间，中间多次想不再进行调试！开始觉得还没怎么调试就结束，这不太好...中间觉得离最终能够调试已经很近了，加油...最后觉得已经到了这一步了，放弃就怪可惜的
哎！人就是这样矛盾的生物

话归正传，我们来看看调试所需要的环境

软件 备注
Windows 2000虚拟机 无论你用的VMware，亦或是Virtualbox，请确保windows 2000能够正常复制粘贴，很多朋友都是在此处浪费了大量时间，我也不例外
VC6.0 无论是纯净版还是绿色版，只要能用即可！
注意在调试程序的时候勾选：工具->选项->调试中的实时调试 ；
而且还应该调成Release版本：组建(Build)->移除工程配置，双击other - Win32 Release
Ollydbg 建议大家使用Ollydbg110版本，因为我此版本测试通过！而吾爱破解专用版Ollydbg无法正常使用，大家切忌使用此版本，否则十分坑爹！
启动od，然后点击option->just-in-time debugging选中Make ollydbg Just-in-time debugger并确认，最后重启od

2. 堆的数据结构

2.1 堆块

1） 堆块分为块首和块身
块首是堆块头部的几个字节，用来标识这个堆块自身的信息，包括本块的大小、本块空闲还是占用等信息；
块身紧跟在块首后面的部分，是最终分配给用户使用的数据区。

2） 块首大小为（8字节）

堆块的基础数据结构

3） 空闲态的堆块在块首后有两个指针

2.2 堆表（空表和快表）

位于堆区的起始位置，用于索引堆区中堆块的重要信息。堆表的数据结构决定了整个堆区的组织方式。堆表在设计时可能会考虑采用平衡二叉树等高级数据结构用于优化查找效率。现代操作系统的堆表往往不止一种数据结构。

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

堆表

1） 空表：双向回环链表(Freelist)

堆区一开始的堆表区中有一个128项的指针数组（看到有人说把它看成队列的），被称作空表索引。该数组的每一项包含两个指针，用于表示一条空表。
free[1] 标识了所有堆中所有大小为8字节的空闲堆块，之后每个索引指示的空闲堆块递增8个字节。即：
free[2]标识了16个字节的空闲堆块。
free[k] 标识了 k * 8 个字节的空闲堆块。
指示第1项空表索引比较特殊，从图中我们也可以看到：这条双向链表链入了所有大于等于1024字节的堆块（小于512KB），堆块按照升序排列。

空表

2） 快表：单向链表(Lookaside)

快速单项链表是Windows用来加速堆块分配而采用的一种堆表。这类单项链表不会发生堆块合并（其中的空闲块块首会被设置为占用态，用来防止堆块合并）。

快速单项链表有128条，组织结构与空闲双向链表类似，只是其中的堆块按照单项链表组织。快表总是被初始化为空，而且每条快表最多只有4个结点，故很快就会被填满。

快表

3） 区别

a) 以上两个都为128大小的指针数组 （空表每一项有两个指针，快表每一项有一个指针）
b) 快表最多只有四个节点
c) 空表除了数组的第一个元素外其他分别链接：数组下标*8 大小的堆块，数组的第一个元素链接着大于1kb的堆块，并升序排序
d) 快表的堆块处于占用状态，不会发生堆块合并
e) 快表的只存在精确分配，快表优先空表分配

2.3 内存块

小块（小于1kb）

分配方式：优先快表，其次空表非零元素（free[0]），然后堆缓存，最后空表零元素。否则就紧缩，然后再尝试。再否则就返回NULL
释放：优先链入快表（只能链入4个空闲块），如果快表满则链入相应的空表

大块（大于1kb小于512kb）

分配方式：优先堆缓存，其次空表零元素
释放： 优先放入堆缓存，若堆缓存满则链入freelist[0]

巨块（大于512kb）

分配方式：虚分配
释放：直接释放

3 堆结构的验证和分析

在堆中进行内存分配的时候，C语言函数调用的是malloc()函数，c++中调用new()函数，当动态调试进入函数内部的时候察觉此两个函数调用的都是底层ntdll.dll中的RtAllocateHeap()函数，所有的windows分配堆的函数在底层调用的都是此函数，这也死程序员可以看到的关于堆的最底层函数。因此研究堆分配，重点关注此函数即可。

3.1 堆的调试

在此之前需要理解一个概念：调试堆与调试栈不同，不能直接加载或者attach 程序，否则堆管理策略就会采用调试状态下的堆管理策略，使用调试状态下的堆管理函数。

正常堆和调试堆的区别：
1.调试堆只采用空表分配，不采用快表分配
2.所有的堆块末尾都加上十六个字节的用来防止程序溢出，（仅仅是用来防止程序溢出，而不是堆溢出），其中这十六个字节包括：8个字节的0xAB 和 8个字节的0x00
3.块首的标志标志位不同，调试状态下的堆和正常堆的区别如同debug下的PE文件和release下的PE文件类似，做堆移除实验的时候，调试器中可以v正常运行的shellcode，单独运行却不行。很可能就是调试堆与正常堆的差异造成的。

为拉避免采用调试状态下的堆，我i们直接在程序中嵌入 int3 断点，然后调用实时调试器即可

3.2 空表结构验证调试

3.2.1 验证代码
#include <windows.h>

int main()
{
     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);

     //free block and prevent coaleses
     //释放掉1、3、5,内存不相联不会发生堆块合并
     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;
}
3.2.2 堆调试环境配置
  1. 在VC6.0中创建该工程，然后勾选：工具->选项->调试中的实时调试，并将运行结果设置为Release版本
  2. 在OllyDbg中"Options"菜单中选中"Just-in-time debugging"，单击"Make OllyDbg just-in-time debugger"，然后单击"Done"按钮确认。
  3. 运行上面程序之后，在系统出现错误提示的时候，选择"取消"
    选择调试
  4. 然后可以在Ollydbg中进行调试，使用Alt+M可以查看当前内存映射状态，如图所示
    OllyDbg中调试
3.2.3 实验过程

可以看出程序断点断在了VA=0x0040101D处，此时内存映射窗口也在上图中显示。其实你应该知道：进程堆地址为0x130000, S大小为0x6000。可以使用GetProcessHeap()获取函数句柄。
获取进程堆地址

其实本实验中的内存分配函数malloc()有属于自己的堆区（0x00340000，大小0x2000）.

识别堆表

在程序初始化的过程中，malloc使用的堆和进程堆都已经经过了若干次分配和释放操作，里面的堆块相对比较“凌乱”，因此我们在程序中使用HeapCreate()函数创建一个新的堆，通过调试这个比较“整齐”的堆来理解堆管理。

当HeapCreate()成功创建了堆区之后，会把整个堆区的起始地址返回给EAX，如上上图所示，地址为0x00360000
在内存映射窗口双击0x00360000地址所在行即可进入数据窗口。
从0x00360000开始，堆表中包含的信息依次是段表索引（Segment List）、虚表索引（Virtual Allocation list）、空表使用标识（freelist usage bitmap）和空表索引区

当然，上面给出的区域并不完整，下面是我从网上找到的完整表述：


0:000> dt _HEAP 00080000
   +0x000 Entry           : _HEAP_ENTRY
   +0x008 Signature        : 0xeeffeeff
   +0x00c Flags           : 0x50000062
   +0x010 ForceFlags       : 0x40000060
   +0x014 VirtualMemoryThreshold : 0xfe00
   +0x018 SegmentReserve    : 0x100000
   +0x01c SegmentCommit     : 0x2000
   +0x020 DeCommitFreeBlockThreshold : 0x200
   +0x024 DeCommitTotalFreeThreshold : 0x2000
   +0x028 TotalFreeSize    : 0xcb
   +0x02c MaximumAllocationSize : 0x7ffdefff
   +0x030 ProcessHeapsListIndex : 1
   +0x032 HeaderValidateLength : 0x608
   +0x034 HeaderValidateCopy : (null)
   +0x038 NextAvailableTagIndex : 0
   +0x03a MaximumTagIndex  : 0
   +0x03c TagEntries       : (null)
   +0x040 UCRSegments      : (null)
   +0x044 UnusedUnCommittedRanges : 0x00080598 _HEAP_UNCOMMMTTED_RANGE
   +0x048 AlignRound       : 0x17
   +0x04c AlignMask        : 0xfffffff8
   +0x050 VirtualAllocdBlocks : _LIST_ENTRY [ 0x80050 - 0x80050 ]
   +0x058 Segments      : [64] 0x00080640 _HEAP_SEGMENT
   +0x158 u                : __unnamed
   +0x168 u2               : __unnamed
   +0x16a AllocatorBackTraceIndex : 0
   +0x16c NonDedicatedListLength : 1
   +0x170 LargeBlocksIndex : (null)
   +0x174 PseudoTagEntries : (null)
   +0x178 FreeLists    : [128] _LIST_ENTRY [ 0x829b0 - 0x829b0 ]
   +0x578 LockVariable     : 0x00080608 _HEAP_LOCK
   +0x57c CommitRoutine    : (null)
   +0x580 FrontEndHeap  : 0x00080688
   +0x584 FrontHeapLockCount : 0
   +0x586 FrontEndHeapType : 0x1 ''
   +0x587 LastSegmentIndex : 0 ''

可以明显看出，空表开始位置在0x00360178处，其余的堆块一般与溢出利用关系不大。
当一个堆刚刚被初始化时，它的堆块状况是非常简单的：

  • 只有一个空闲态的大块(称为“尾块”)
  • 偏移0x178的位置是空表的头，可以参见介绍空表时所用的图。如图可以看到，当前的freelist[0]的值是0x00360688，而其他元素都指向自身(蓝框指向0x00360688,红框指向自身地址)。（启用块表后0x688位置就是快表）
    空表头
  • Freelist[0]指向“尾块”，八个字节（前四个字节是前向指针，后四个字节时后巷指针，即：空表的一对指针），其余各项指向本身
  • 除零号空表索引外，其余各项索引都指向自己，这意味着其余所有的空闲链表都没有空闲块。

占用态

占用态

空闲态
空闲态

占用态和空闲态的共同点

0-2 字节代表本快的大小（包括块首）
2-4字节表示计算单位是多少字节

占用态与空闲态的不同点

Flags出 占用态标志是1 空闲态标志是 0

空闲态块首后的八个字节为一对指针，分别是前向指针和后向指针。当堆块变为占用态的时候重新回分配数据。

实际上尾块的起始位置是 0x360680， 一般引用堆块的指针都会跃过8字节的块首，直接指向数据区

因此根据地址 0x360680处八个字节的情况(参见下图)可以知道：此尾块的大小是 0x130 计算单位是 0x0008 个字节 总大小是 0x980字节 (0x130 * 0x8 = 0x980)。
尾块

注意：堆块的大小是包含块首在内的
堆块的分配

上面也讲了，堆块在分配的时候会将块首计算在内。所以程序中的费喷情况如下：

堆句柄 请求字节数 实际需要的字节数 实际分配（堆单位） 实际分配（字节）
H1 3 11 2 16
H2 5 13 2 16
H3 6 14 2 16
H4 8 16 2 16
H5 19 27 4 32
H6 24 32 4 32

直接在CPU窗口，命令F8单步执行程序到地址:0x0040102B处，这时我们执行完了
h1 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 3)
当h1被分配以后直接查看地址：0x00360178地址处的值（0x00360698）：
h1
此时的地址0x360178处的值已经从0x360688改变为0x360698 同时跳转到 0x360698,如下图：
h1
从图中可以看出：分配给h1的大小为0x0002, size=16bytes

接下来运行到地址0x00401059，此时h1~h6全部分配完，查看0x00360178的地址可以看出，值已经更改为0x00360708。接下来到0x00360680处进行查看

h1~h6的分配情况如下：
h1-h6

如上所示，现在的地址是：0x360700大小是0x120 = 0x130 - 0x2 * 4 - 0x4 * 2

以上从h1 - h6的分配情况验证啦 空表分配中的找零钱现象（从一个大块中依次一小块一小块地进行切割）

下面是我的一些思考：
首先，尾块上的指针指向什么？其实尾块上的指针表示的是没有分配完的区间有多大。因此如果要查看指针所指向的内容，应该找其Self Size中的内容。
例如上图中的0x700是尾块，那么h6中的data实际上应该是0x6E0~0x700。以此类推，可以找到h5，h4，h3，h2，h1中的数据雷荣。h1的堆块为0x680~0x690。
堆块的释放

接着上面的程序执行，直接执行到地址：00401077地址处
HeapFree(hp,0,h1); //free to freelist[2]
HeapFree(hp,0,h3); //free to freelist[2]
HeapFree(hp,0,h5); //free to freelist[4]
分别释放啦堆块 h1 h3 h5这样做是防止相邻堆块进行堆块的合并。直接查看地址 0x360178地址处的值重点观察变化的值如下图：
地址变化

从上图中可以发现地址 0x360188 的值发生啦变化 从原来的指向自身现在变为指向：0x360688 0x3608A8

地址0x360198处的值变化为： 0x003606C8 和 0x003606c8

由上图可知 h1 h3分别被释放到 freelist[2] 空表中， h5被释放到啦 freelist[4]空表中。

根据freelist【2】 的空表索引 以及h1 h3堆块的指针组，可以发现 ：
链表结构
如图所示左边箭头是前向指针，顺序为 Freelist -> h1 > h3 右边是后向指针 顺序是 h3> h1 > freelist[2]

对于h5堆块倒是没啥 ，freelist[5]直接索引到 地址 0x3606c8

堆块的合并

接着程序运行直接运行到地址 0x401080地址处，执行的是代码：

HeapFree(hp,0,h4); //coalese h3,h4,h5,link the large block to freelist[8]

当释放h4的时候会发生堆块的合并现象（两个连续的空闲块就会发生合并）。首先是先从空表中将三个空闲块摘下，重新计算合并后的堆块的大小，然后合并成新的空闲块，链入空表。如下图所示分别为空表索引区状态和合并后堆块状态：
堆块状态
堆块状态

如上图所所示：

  • 在0x188处的freelist[2]，原来标识的空表中有两个空闲块h1和h3，而现在只有一个h1，因为h3在合并时被摘下了。同理0x198处的freelist[4]也被摘下了。
  • 在0x1B8处的freelist[8]，原来指向自身，现在指向合并后的新空闲块0x3606A8，处的值 0x0008 即是：合并后的堆块的大小。后八个字节的指针对，则指向空表的索引区。

注意事项

以上是空表中的堆块的合并，并且只发生在空表中。

整个过程比较费时，繁琐，在强调效率的情况下，堆块合并就会被禁止，设置为占用太。

空表中第一个块的情况下不会向前发生合并，最后一个块不会向后进行合并。

3.3 快表结构验证调试

3.3.1 验证代码
#include <stdio.h>
#include <windows.h>

void main()
{
    HLOCAL h1,h2,h3,h4;
    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);

    h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16);
    HeapFree(hp, 0, h2);
}
3.3.2 实验过程

空表地址
快表地址
首先在dump窗口中直接跳转至0x360178处，此处是快表地址，发现地址指向0x00361E90，不是原来的0x00360688。此时基本上可以看出有快表！
直接在dump窗口中进行跳转到0x360688处，此时发现快表为空。这也是为什么要反复申请释放内存的原因。
首先从FreeList[0]中依次申请8，8，16，24字节的内存，然后进行释放到快表中（快表未满时释放到快表中）。根据三个堆块的大小我们可以知道8字节的会被释放到Lookaside[1]中、16字节的会被释放到Lookaside[2]中、24字节的会被释放到Lookaside[3]中。

先运行程序到地址 0x40109F处。此时直接观察快表中的变化，此时发现仍然为空，下面运行释放程序，直接单步执行命令运行到地址：0x401106处，这是观察快表的变化如图所示：
快表测试1

运行程序到地址 0x40110D处观察堆块是否链如快表：
运行状态

如上图所示h1 - h4已经链接进入块表中并且都是处于占用态。 地址 0x361e90指向下一个堆块（因为h1 h2 同时为八字节的空闲堆块）

当程序运行到地址 0x40111D时（也就是执行完申请内存的代码时）
h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,16);
此时申请的堆块应该从块表中申请，此时查看堆表区的索引：
重新申请时的快表
重新申请时的空表
从以上两图中可以看到当继续申请内存的时候，是从快表lookside[2]处卸下的堆块。

当释放的时候，代码执行到0x401140,还是将空闲堆块释放到此处执行代码：
HeapFree(hp,0,h2);
执行完后继续查看上图中地址的值：
释放内存值快表
如图所示：当释放完堆块后还是链接进入啦快表 looksize[2]

3.4 快表中堆块与空表中堆块区别

  • 块首中的标志位为0x01，也就是这个堆块是Busy状态，这也是为什么快表中的堆块不进行合并操作的原因。
  • 块首只存指向下一堆块的指针，不存在指向前一堆块的指针。


参考文献

堆溢出研究二
堆溢出（一）堆结构
!Heap
Advanced Windows Debugging: Memory Corruption Part II—Heaps
Reliable Windows Heap Exploits BY SHOK