专栏首页zhisheng0Day技术分析-4-堆溢出原理

0Day技术分析-4-堆溢出原理

《0Day技术分析》系列文章已经全部推送完毕,需要的电子稿的请加QQ1041218129(备注好需求),也可以直接在公众号查看文章目录。

堆溢出原理

1 堆的工作原理

堆是一块比较神秘的地方,同PE文件一样,微软从来没公开过操作系统对堆的管理细节,但是通过前辈们的努力,堆基本上已经被研究清楚了,这里的基本上是指堆管理中心与攻击相关的数据结构及算法。

1.1. 堆与栈

在第二章,我们讨论了栈溢出,栈中的数据及其大小在程序设计时就已经确定,在使用栈时不需要额外的申请操作。栈空间由系统维护,栈空间的分配与回收都由系统完成,最终达到栈平衡,栈的操作对程序员是透明的。

程序在执行时需要两种不同的内存协同配合,一种是栈,另外一种就是我们这章要讨论的堆,对于程序员来说,堆的操作不是透明的,堆有以下的几种特性:

  • 堆是在程序运行时动态分配的内存,就是说所需内存的大小在程序设计时并不能确定
  • 使用堆需要程序员调用函数进行申请,比如malloc/new等,但是堆内存的申请有可能成功也有可能失败,这与机器性能、当前的运行环境、申请内存的大小有关
  • 如果申请成功,将得到一个指向这块堆内存空间的地址,也就是指针,对这块堆内存的所有操作都通过这个指针完成
  • 当不再使用申请的堆内存空间时,仍然需要调用相关函数对这块堆内存进行回收,如free/delete,否则会造成内存泄漏

可见,堆与栈有着很大的区别,我们下面总结一下:

注意,栈总是线性变化的,所以管理机制相对简单,栈溢出的利用就比较容易,堆则杂乱无章,再加上堆的管理并不透明,所以堆的利用就显得比较有意思。

1.2. 堆的管理策略

程序员使用堆时只需要三个步骤:申请一定大小的内存、使用这块内存、回收这块内存,当程序在申请内存时,堆管理程序需要在杂乱的堆区中辨别哪些内存正在使用,哪些内存是空闲的,并且要在空闲的内存中找到一块合适大小的区域,将这块内存的地址以指针方式返回。

下面我们看几个关键词:

  • 杂乱,是指在经过反复的申请、释放之后,原本大片连续的空闲的内存变得大小不等、空闲块和占用块可能间隔的存有大量碎片的状态
  • 辨别,是指堆管理程序必须识别出哪些内存区域正在使用,哪些是空闲的,并且哪些区域适合当前申请的区域
  • 适当,是指堆管理程序要找到一块最合适的内存区域,比如用户申请8个字节,不能返回用户1024个字节的内存区域的指针,最好是返回8个字节内存区域的指针 1.3. 堆数据结构

显然,对堆的管理不仅需要合适的算法,还需要合适的设计。在设计上堆的数据结构一般包括堆表和堆块两类。

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

堆块:出于性能考虑,堆区的内存并不以字节为单位标识,而是以堆块为单位标识,一个堆块分为块首和块身两部分,块首是堆块头部的几个字节,用来标识堆块自身的信息(堆块的大小、空闲还是占用等),块身则是紧邻块首的部分,也是分配给用户的数据区。堆管理程序一般返回块身的地址,所以感觉不到块首的存在,但堆块与堆块之间是有间隙的。

如下图所示:

在Windows下,占用态的堆块被使用它的程序索引,而堆表只索引空闲态的堆块,最重要的堆表有两种:空闲双向链表Freelist(简称空表)、快速单向链表Lookaside(简称快表)。

1.4. 空表

空闲堆块的块首保存着两个重要的指针,这两个指针用于将空闲堆块组织成双向链表,按照堆块大小的不同,空表被分为128条。

在堆区开始的堆表中有一个128项的指针数组,称为空表索引(Freelist array),这个数组中的每一项都包含两个指针,用于标识一条空表。如下图:

在上面图中我们可以得知,从free[1]开始,每条链表中所标识的空闲堆块大小都是一样的,每条链表中空闲堆块的大小等于索引项ID*8个字节。

free[0]有点特殊,这条链表中标识了所有大于等于1024字节但小于512K的堆块,这条链表中的堆块按照从小到大的顺序排列。

1.5. 快表

快表比较简单,是Windows用来加速堆块分配而采用的堆表,之所以称为快表,是因为其中的空闲块的块首总是被设置成占用态,从来不会产生堆块的合并。

从上图中可以看出,快表也有128条,组织结构与空表类似,但是其中的堆块是按单链表组织,并且每条快表中最多只有4个结点,所以很快就会被填满。

1.6. 堆块分配

从快表中分配堆块相对简单,大致过程为寻找到大小匹配的空闲堆块、将其状态修改为占用态、将其从堆表中卸下、返回指向堆块的指针给程序。

普通空表分配要先找到最优的空闲块,若失败则寻找次优的空闲块分配,即最小满足要求的空闲块。

free[0]空表中的堆块是按大小从小到大排序的,在分配时,是先反向查找,即先找到最大的块,如果满足,再正向搜索最小能满足要求的空闲块进行分配,如果最大块都不能满足,无须再正向搜索,则分配失败,。

总结一下:当空表中无法找到最优的堆块时,一个稍大的堆块会被用于分配,当次优分配发生时,会先从大块中按请求的大小精确地割出一块进行分配,然后对剩下的部分重建块首,链入空表;对于快表,只有在精确匹配时才分分配,不存在分割。

1.7. 堆块释放

堆块的释放包括将堆块状态修改为空闲态,链入相应的堆表,所有的释放块都会链入堆表的末尾,分配的时候也优先从堆表末尾开始。注意快表最多只有4项。

1.8. 堆块合并

显然,经过反复的分配与释放,堆区变得千疮百孔,产生很多碎片,为了有效利用内存,堆管理程序需要对这些碎片进行堆块合并操作。

当堆管理程序发现两个空闲堆块相邻时,就会将这两个堆块进行合并,合并时将这两个块从空闲链表中卸下,然后将两个堆块合并,重建新的块首,将新的块重新链入空闲链表。

堆区还有一种操作叫做内存紧缩(shrink thecompact),由RtlCompactHeap执行,其效果相当于磁盘碎片整理,用于对整个堆进行调整,尽量合并可用的碎片。

在进行堆分配与释放时,根据操作内存大小的不同,可以把内存块按大小分为三类:小块(size < 1KB)、大块(1KB <= size 512KB)、巨块(size >= 512KB),我们看一下下面的表格:

再强调几个要点:

  • 快表中的空闲块被设置为占用态,所以不会发生堆合并操作
  • 快表只有精确匹配时才会分配
  • 快表是单链表,操作比双链表简单
  • 因为快表的速度,在分配和释放时优先使用快表,失败后再使用空表
  • 快表只有4项,很容易被填满,因此空表的使用也比较频繁

2 验证一下

在语言级别,如C/C++中提供了如malloc/new之类的库函数来向堆申请内存,在用户态,我们能看到的最底层的堆分配函数是RtlAllocateHeap(),这个函数位于ntdll.dll中,也就是说,我们只关注这个函数就可以了。

2.1. 空表实例

2.1.1. 默认堆与私有堆

Windows的堆分为默认堆和私有堆两种,默认堆是在程序初始化时由操作系统创建的,所有的标准内存管理函数都是在默认堆中申请内存的;而私有堆是在默认堆中保留了一块内存,用堆管理函数在这个保留的内存块中分配内存。

一个进程的默认堆只有一个,而私有堆可以有多个,私有堆的缺点是分配和释放内存块的过程中多了一个扫描堆中的内存链的过程,所以在私有堆中分配内存速度看起来好像要慢一点。

对于默认堆,如果有多个线程试图同时对默认堆中的堆块进行操作,那么只有一个线程能够进行,其它线程必须等待这个线程操作完成之后才能继续执行;对于私有堆,其空间是预留的,不同线程在不同的私有堆中同时分配内存并不会引起冲突,所以整体的运行速度可能更快。

当系统在物理内存和页文件之间进行页面交换的时候,系统的性能会受到很大的影响,在某些情况下,使用私有堆可以防止系统频繁地在物理内存和交换文件之间进行数据交换,因为将经常访问的内存局限于一个小范围地址的话,页面交换就不太可能发生,把频繁访问的大量小块内存放在同一个私有堆中就可以保证它们在内存中的位置接近。

私有堆有利于封装和保护模块化的程序,当一个程序包含多个模块的时候,使用默认堆会使所有模块分配的内存块是交叉排列在一起的,如果模块A中的一个错误导致内存操作越界,可能会覆盖掉模块B使用的内存块,而模块B执行出错时则很难发现错误的源头来自于模块A。如果让不同的模块使用自己的私有堆,那么它们使用的内存就会完全隔离开来,虽然越界错误仍然可能发生,但很容易跟踪和定位。

最后,在默认堆中分配的内存需要一块块单独释放,而将一个私有堆释放后,在这个堆里的内存就全部被释放掉了,并不需要预先释放堆中的每个内存块。

2.1.2. 实例代码

我们先看需要调试的代码:

上面的HeapCreate这个函数就创建了一个私有堆。

2.1.4. 调试状态的堆与常规状态下的堆

在对堆进行调试之前要明白一点,调试状态的堆和常规状态下的堆在管理策略上有较大的差异:

  • 调试状态下的堆不使用快表,只使用空表
  • 所有堆块在调试状态下都被加上了多余的16个字节的尾部来防止程序溢出,包括8个字节的0xAB和8个字节的0x00
  • 块首的标记位不同

这种区别就像PE文件的Debug版本与Release版本的区别差不多,为了防止堆管理程序检测到当前进程处于调试状态而启用调试状态的堆策略,我们在代码里加了一个人工断点:__asm int 3,然后让程序单独执行,当初始化堆完成后,断点会中断程序,此时用OD来attach进程,就能看到真正的堆了。

__asm不用太多解释,表示后面要嵌入汇编代码,显然我们这里要嵌入的就是int3,机器码是CC,在直接系统服务中,int 3代表断点中断,在这里我们只需要知道这一行的意思是插入了一行人工断点,会引发程序异常即可。

2.1.5. 设置默认代码调试器

下面我们看一下如何设置默认的调试器,我们经常看到一些程序出错时出现类似下面的弹出框:

在上面的图中,我们点击“确定”按钮会退出程序,但当点击取消时会调用一个默认的调试器来对出错的程序进行调试,如果我们安装了VC、VS之类的,会自动启动这些IDE,并attach到出错的程序上。

在这里我们当然希望使用OD,所以我们将OD设置成默认调试器,方法如下:option->Just-in-timedebugging,出现下面的对话框:

知道点击哪个按钮了吧,当然是Make allyDbgjust-in-time debugger,然后点击Done按钮即可。此时运行我们的堆调试程序,再出现那个应用程序错误的对话框时,点击取消就会启动OD了:

在上图中,我们点那个M按钮,就可以看到当前的内存映射状态:

2.1.5. 查看堆表

当HeapCreate函数成功返回时,会把申请的堆块的地址返回,一般返回值都在EAX中,在这里是0x003A0000:

堆表中的数据依次是段表索引(Segment List)、虚表索引(Virtual Allocation List)、空表使用标识(freelistusage bitmap)及空表索引区。

我们关注的是偏移0x178处的空表索引区,其余的堆表一般情况下与堆溢出利用关系不大,下面我们实际看一下这个空表。

在OD中有一个插件heap_vis,但是这个插件不能很好的区分freelist及lookaside两种堆表,而且这个插件很不稳定,其实我发现不是不稳定,直接就使OD死掉了,而且在XP SP2下一直存在问题,所以我们在内存区直接Ctrl + G去这个地址看一下:

可以看到,在堆初始化时,其结构是非常简单的:

  • 只有一个空闲的大块,这个块被称为尾块,位于堆偏移0x0688处,启用快表后这个位置将是快表索引区
  • freelist[0]指向尾块,除了这个特殊的空表之外,其余各项索引都指向自己,这说明其余所有的空闲链表中都没有空闲块

下面我们看占用态与空间态堆块的数据结构:

上面第一张图是占用态的,第二张图是空闲态的,块首结构基本一致,只是空闲块的块首使用了紧邻块首后面的8个字节存放了空表指针,这8个字节在堆块被占用时会划分到块身部分用于存放数据。

我们看一下0x003A0688这个位置的信息:

  • 这个块其实是从0x003A0680开始的,前面的8个字节是块首部分,在堆表中的指针直接指向了这8个字节之后的数据区
  • 块首的两个字节是当前堆块的大小,这里是0x130,以8个字节为单位,其0x980个字节,堆块的大小是包括块首在内计算的
  • 指向快表的指针位于堆偏移0x584字节的地方,在我们实验过程中有可能都为NULL,这是因为堆是可扩展的时候快表才会启用

2.1.6. 堆块的分配

我们可以使用OD反复调试,在__asm int 3之后有6次调用HeapAlloc函数的过程,每次申请的字节数都不一样,我们来看一下:

当在OD中遇到机器码为CC的int3时,需要我们在OD的Debug选项中设置一下才能使用F7或F8继续运行,这个对话框可以在菜单options->debugging option调出来,选择Exceptions选项卡,将INT3 breaks去掉,点OK即可:

我们可以在每一次调用后查看堆表及堆块的情况,也可以打个断点,在这6次调用之后再看:

我们在上面标出的第一行前面的8个字节是H1的块首,我们标出的第二行是H5的块首,后面应该就是数据了,此时这些块已经不再由堆表索引,而是由使用它们的程序来索引,但我们看到,原来的数据还在,并没有被清除,我们标出的第三行是尾块的块首及两个指针,下面我们来解释一下:

  • 堆块的大小包含了块首的大小,如果申请了8个字节,则实际分配16个字节
  • 堆块是以8个字节为单位,不足8个字节的按8个字节补齐
  • 初始状态下,快表和空表都为空,也不存在精确分配,即使用次优块,这个次优块就是尾块,在堆偏移的0x0688处
  • 当不断从尾块切走一些小块后,会修改块首的size信息,最后把freelist[0]指向新的尾块位置

我们再看一下这个堆偏移0x178处,这里果然指向堆偏移0x708处:

我们看一下H1-H6堆的分配情况:

2.1.7. 堆块的释放

我们通过看代码可以知道,前三次的释放在内存中并不连续,此时不会发生合并,H1和H3都分配了16个字节,应该被链入freelist[2]中,因为索引号2*8=16,同样的道理,H5应该被链入freelist[4]中。

我们看一下执行完这三次操作后,这些堆块又重新可以被堆表索引,所以肯定会出现块首及其指针,此时堆区的数据就更清楚了:

上面第一行是H1释放后的两个指针,第二行是H3释放后的两个指针,第三行是H5释放后的指针,我们发现H1的第一个指针指向H3,H3的第二个指针指向H1,而H1的第二个指向和H3的第一个指针都指向堆表,现在我们可以想到,H1和H3在一个链表中,H5在另外一个链表中,加上之前的尾块(freelist[0]指向的块),堆表中应该有三条空闲链表,我们回到0x003A0178处看一下:

我们看这里的几个指针就可以看出共有三条空表链出现,因为其它的指针还指向自身的位置。

2.1.8. 堆块的合并

当释放H4时,H3/H4/H5这3个空闲块因为彼此相邻而发生堆块合并操作,合并时要把这3个空闲块全都从空表中摘下,而且注意H3/H4和H5还不在一条链表上,然后计算合并后新堆块的大小,最后按合并后的大小链接到空表中。

我们来算一下,这三个空闲块合并后加上块首共有2+2+4=8个堆单位,共64个字节,因为索引号8*8=64,所以会被链入freelist[8]。

我们再来看一下这张图:

这是上面H1/H3/H5被释放后的情况,那个H3所在的块首位置为0x003A06A0,从0x003A06A8开始是这个H3的两个指针,我们来看一下H4释放之后的情况:

可以看出,块首部分的大小改变了,后面的指针因为其大小改为64个字节,所以指向了freelist[0],但后面的数据并没有变化。

我们用原来的堆表跟现在的堆表对比一下,先看一下合并前的堆表:

现在的堆表如下:

总结:

  • freelist[0]中原来有两个,现在变成了一个,因为H3被摘下了
  • freelist[4]中原来有H5,现在被摘下了,所以两个地址变成了本身
  • freelist[8]中原来两个指针都指向本身,现在有了一个新空闲块,所以指向了0x003A06A8

堆合并确实可以更加有效地利用内存,关键是有时候也必须合并,但合并的过程需要修改好多的指针,十分不爽,所以块合并只发生在空表中,快表不会发生,另外空表的第一个块不会向前合并,最后一个块不会向后合并。

2.2. 快表实例

有了空表的调试经验,我们再看快表就简单多了,下面我们先看代码上的区别:

不同之处在于下面这两行:

hp = HeapCreate(0,0x1000,0x10000);

hp = HeapCreate(0,0,0);

2.2.1. 查看堆表

我们用OD attach一下看看:

此时的EAX仍然是0x003A0000,加上0x178得到0x003A0178,我们看一下这个位置的数据:

这里不再是堆偏移0x0688,前面我们已经说过,启用快表之后,堆偏移0x0688的地方将是快表索引区,那我们去0x003A0688去看看:

我们只关注从第一个红色标记的地方开始的部分,之前的是什么东西,我们不知道,也不关心。

2.2.2. 堆的分配与释放

我们看到的是初始化时快表索引是空的,所以我们要先申请堆空间,然后释放,释放时会优先释放到快表索引中,我们看看是不是这样。

从上面的图中可以看出,快表索引与空表索引不一样,空表索引中有两个指针,但快表索引中只有一个,却有其它的数据,这些数据我们不解释。

我们调用了4次申请与4次释放,分别为两个8字节,一个16字节,一个24字节,分别对应的索引号为1、2、3,即分别释放到Lookaside[1]、Lookaside[2]、Lookaside[3]中。

第一条链中有两个堆块,我们去0x003A1EA0这个地址看一下堆块情况:

与空表堆块不同的有两点:

  • 块首中的标识为0x01,即堆块为Busy状态,不能合并
  • 块首中只有下一堆块的指针,但没有指向前一堆块的指针

与空表相同的地方是块首前面仍然是那个16位的结构,包含块首在内的大小,而且当这个堆块被申请占用后,这个指向下个堆块的指针仍然会用作保存数据,这个堆块由使用它的程序来索引。

后面的再申请与释放的过程与空表一致,在这里不再重复。

3 堆溢出利用

我们已经看到,对堆的分配、释放、合并等操作最终都是对链表的操作,分配时将堆块从链表中卸下,释放时把堆块链入链表,合并是先将几个堆块卸下,然后修正块首后再链入链表。

很显然,这些卸下和链入的操作都发生在链表上,如果我们能伪造链表中的指针,利用卸下和链入的操作,就可以获得读写内存的机会,甚至植入我们的代码。

现在很明白了,堆溢出的利用就是用精心构造的数据溢出此堆块,并覆盖下一个堆块的块首,改写块首部分的前向指针和后向指针,在分配、释放或是合并时获得向内存任意地址写放任意数据的机会。

我们看一下从链表中卸下一个堆块的例子:

int remove(ListNode *listNode)

{

listNode->blink->flink = listNode->flink;

listNode->flink->blink = listNode->blink;

}

我们看下面的图片更清楚一点:

双向链表的操作在数据结构课程里有讲,一看就能明白,不再详述,在这里,可以看到,当溢出发生时非法数据可以淹没下一个堆块的块首,这个堆块的块首的两个指针是可以被攻击者利用的,也就是说这个块首中存放的两个指针是可以伪造的,举例来说:

本文分享自微信公众号 - zhisheng(zhisheng_blog),作者:xxyifan

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-04-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HTTPS 虐我千百遍,我却待她如初恋!

    本篇将讨论 HTTPS 的加解密原理,很多人都知道 RSA,以为 HTTPS=RSA,使用 RSA 加解密数据,实际上这是不对的。

    zhisheng
  • 不好意思,我和 Java 内存模型杠上了!

    Java内存模型是在硬件内存模型上的更高层的抽象,它屏蔽了各种硬件和操作系统访问的差异性,保证了Java程序在各种平台下对内存的访问都能达到一致的效果。

    zhisheng
  • 渣渣菜鸡的 ElasticSearch 源码解析 —— 启动流程(下)

    上篇文章写完了 ES 流程启动的一部分,main 方法都入口,以及创建 Elasticsearch 运行的必须环境以及相关配置,接着就是创建该环境的节点了。

    zhisheng
  • Java并发之volatile关键字内存可见性问题

    Main函数启动后,调用一个线程向list中添加数据。List的size为5的时候,设置变量flag为true.然后,主线程根据flag的值进行其他操作。

    凯哥Java
  • Java直接内存与非直接内存性能测试

    什么是直接内存与非直接内存 根据官方文档的描述: A byte buffer is either direct or non-direct. Given a d...

    用户1154259
  • 语音交互设计的一点认知

    语音用户界面(或VUI)是一种交互模型,在该模型中,人与机器进行交互,并至少部分通过使用语音来执行一组任务。

    半吊子全栈工匠
  • 回归分析中的问题和修正的探讨(下篇)

    探讨的上篇中, 我们探讨了多重共线性MultiCollinearity和异方差Heteroskedasticity, 接下来我们讨论自相关和误差变量。

    史博
  • 如何合理的使用动态数据源

    秋日芒草
  • 秋招季,用Python分析深圳程序员工资有多高?

    多图预警、多图预警、多图预警。秋招季,毕业也多,跳槽也多。我们的职业发展还是要顺应市场需求,那么各门编程语言在深圳的需求怎么呢?工资待遇怎么样呢?一起来用 Py...

    小小詹同学
  • 秋招季,用Python分析深圳程序员工资有多高?

    多图预警、多图预警、多图预警。秋招季,毕业也多,跳槽也多。我们的职业发展还是要顺应市场需求,那么各门编程语言在深圳的需求怎么呢?工资待遇怎么样呢?zone 在上...

    1480

扫码关注云+社区

领取腾讯云代金券