Linux下堆栈结构分析

作者 Lao Yuan, 发布于 Lao-Yuan's Blog , 禁止转载.

0x01 背景

这是一篇日志,是软件安全课程中堆栈安全实验.除了传统的栈结构外,我个人对堆的了解十分少,在学习过程中很幸运翻到了阿里的@走位写的入门贴,学到了很多堆栈结构的内容,本文也主要根据他的分享进行个人的学习总结.

(ps. 整理时发现原链接挂了,但能搜到很多转载的.出于对作者的尊重,仍然放上作者原文的链接.)

本文主要学习了传统的堆栈系统,并做一些实验.实验中会发现一些不很理解的内容,尤其是64位系统的堆结构已经发生了很大变化,仍需要研究,有机会会另起一篇文章讨论.

0x02 实验概述

内容

a) 编写几个程序,展示栈帧结构

b) 编写程序,观察Linux堆分配机制

平台

a) 物理机: ubuntu18.04 x64

b) 虚拟机: ubuntu16.04 x86

0x03 相关知识点

3.1 Linux内存布局

Linux给每个程序分配了虚拟的内存布局,而32位的系统结构又和64位有一些区别。32位进程可看到的内存结构如下所示:

32位内存布局

32位内存布局

从高地址到低地址为:不可访问的内核空间,栈空间(由高地址向低地址生长),内存布局区,堆空间(由低地址向高地址生长),BSS,数据段,文本段。本报告讨论进程的栈空间和堆空间的具体结构。

64位Linux系统的进程空间更大,如下图所示:

64位内存布局

64位内存布局

64位结构中,用户空间和内核空间各可操作128TB的内存空间。用户空间的布局和32位差别很小。

在linux中查看某进程的内存布局,除了使用一些系统工具外,也可以使用查看/proc/$pid/maps文件的方式,该文件存储了进程号为pid的进程的内存布局。

3.2 Linux栈帧结构

Linux进程栈结构如图所示:

Linux进程栈结构

Linux进程栈结构

32位系统和64位系统在栈管理上没有太大区别。栈帧是从高地址向低地址生长(申请)的。当新的调用栈时,多于6个(64位系统,其余使用寄存器传入)的传入参数先被压入栈中,接着压入原函数返回地址。当编译器开启栈保护机制时,压入栈保护字段。压入上一个调用栈的栈底指针ebp,将esp赋值为申请的内存长度。这样就完成了调用栈的申请。多次栈的申请是迭代的过程,根据保存的ebp、ret恢复原调用栈。

3.3 Linux堆结构

Linux堆结构较栈结构更为复杂。通常,程序设计者维护堆空间,将使用malloc、free函数申请,该函数将调用mmap和munmap,这两个函数又将使用sbrk、brk的系统调用函律数,下图为函数调用的关系。下面讨论具体的堆维护方法。

堆分配方法

堆分配方法

3.3.1 Arena

早期的Linux使用dlmalloc作为其默认的堆管理算法,现在大多使用ptmalloc2进行管理,其优势是支持多线程的堆管理,该管理算法被Linux glibc运行库管理。本实验只讨论其单线程时的内存分布规。ptmalloc2管理的内存分配区叫做arena。一般情况下,arena的概念是针对多线程提出的,main_ arena可以访问用户的heap区,使用sbrk和mmap函数向系统申请需要的内存,而non_main_arena则只可以使用mmap向系统申请大段内存,下图为ptmalloc2处理arena的方式。

Arena

Arena

一个程序可能有数个堆(因为多线程),每个堆会属于某个arena,Linux通过heap_info实现了这种多个堆的机制。本报告不讨论多线程的情况,因此不需要处理arena和heap_info的数据结构。

3.3.2 chunk

所有的内存管理机制,包括ptmalloc2,都使用chunk作为堆内存管理的单位。一个chunk的大小不是固定的,是由用户申请的大小决定的,可以理解为是由malloc(size)中size的大小决定的。Chunk总共分为4类:1) allocated chunk; 2) free chunk; 3)top chunk; 4)Last remainder chunk。从本质上来说,所有类型的chunk都是内存中一块连续的区域,只是通过该区域中特定位置的某些标识符加以区分。为了简便,我们先将这4类chunk简化为2类:allocated chunk以及free chunk,前者表示已经分配给用户使用的chunk,后者表示未使用的chunk。

经过走位@阿里聚安全的考证,chunk的结构经过了一系列的变化(可以在文末链接找到),本报告只讨论其最终的结构。当用户调用malloc后,堆管理机制glibc会查找到符合要求的一块内存(查找方式后边会讲到),将该内存初始化为一块allocated chunk,一块allocated chunk的结构如下图所示:

allocated chunk

allocated chunk

malloc函数的返回值为图中的payload首地址,大小为分配的大小,后面的padding是填充字段,即申请的大小会被自动补齐到整8字节,补齐的内存即为padding。payload+padding的大小并不是一个allocated chunk的大小,一个chunk还需要其控制信息,即chunk size,chunk size为整个chunk的大小,即payload + chunk head + padding。在32位系统中,chunk head大小为8字节,64位中为16字节。由于chunk size是8字节对其的,chunk header的低三位被用来存储其他控制信息,由高到低是N、M、P,P代表前一个chunk是否被占用,M代表此chunk是否由mmap分配,N代表此chunk是否为main_arena的chunk。若P为0,代表前一个chunk为free,则在chunk head前再存储前一个chunk的大小,便于之后的合并操作。

之前说明了allocated chunk的结构,如下是一个 free chunk 的结构:

free chunk

free chunk

一个free chunk的结构中,header和pre chunk部分与allocated chunk定义相同,但一个free chunk会多出两个指针,这两个指针用于构建之后讨论的bin所需的双(单)链表。fd指向一个前一个(更低地址)free chunk,bk指向一个后一个(更高地址)free chunk。

3.3.3 bin

malloc的内存会交由程序进行管理,而free的内存则被ptmalloc2管理,管理的方式是bin,一般意义上的堆表。由于可找到的资料中少有针对64位系统的bin结构的讨论,以下只讨论32位操作系统。

bin通过几个链表将所有的free chunk管理起来,在用户再次申请内存时将这些bin中索引的chunk进行分配。

系统针对不同大小的free chunk,将bin分为了4类:1) Fast bin; 2) Unsorted bin; 3) Small bin; 4) Large bin。在glibc中用于记录bin的数据结构有两种,如图所示:

bin 表

bin 表

fastbins: 这是一个数组,用于记录所有的fast bins; bins: 这也是一个数组,用于记录除fast bins之外的所有bins。事实上,一共有126个bins,分别是:bin 1 为unsorted bin;bin 2 到63为small bin;bin 64到126为large bin。 下图是bin的构成方式,接下来详细讨论不同bin的特点和结构。值得注意的是,这里的讨论的仅限于32位系统,在后文的实验中,发现64位系统的堆管理中bin结构与32位并不相同

bin 表具体结构

bin 表具体结构

Fast bin

Fast bin 共有10个,存储了chunk size 从16到80的free chunk,这些free chunk被称作fast chunk,如fastbin[0]索引所有大小为16字节的free chunk,fastbin[1]索引所有大小为24字节的free chunk,以此类推,步长为80字节。

与其他几种bin相比,fast bin的明显特点是它的索引方式是单链表即只使用free chunk结构中的fd指针。在使用时采用LIFO后入先出算法,free后的fast chunk直接链接在相应大小的fast bin链表队尾,malloc的fast chunk直接从相应大小的fast bin链表队尾拆链。

除了fast bin的单链表特点外,fast bin还有以下操作:

  • a) 不会对free chunk进行合并操作。鉴于设计fast bin的初衷就是进行快速的小内存分配和释放,因此系统将属于fast bin的chunk的P(未使用标志位)总是设置为1,这样即使当fast bin中有某个chunk同一个free chunk相邻的时候,系统也不会进行自动合并操作,而是保留两者。虽然这样做可能会造成额外的碎片化问题,但瑕不掩瑜。

  • b) malloc(fast chunk)操作:即用户通过malloc请求的大小属于fast chunk的大小范围(注意:用户请求size加上16字节就是实际内存chunk size)。在初始化的时候fast bin支持的最大内存大小以及所有fast bin链表都是空的,所以当最开始使用malloc申请内存的时候,即使申请的内存大小属于fast chunk的内存大小(即16到80字节),它也不会交由fast bin来处理,而是向下传递交由small bin来处理,如果small bin也为空的话就交给unsorted bin处理。

  • c) free(fast chunk)操作:这个操作很简单,主要分为两步:先通过chunksize函数根据传入的地址指针获取该指针对应的chunk的大小;然后根据这个chunk大小获取该chunk所属的fast bin,然后再将此chunk*添加到该fast bin的链尾即可。

Unsorted bin

当释放较小或较大的chunk的时候,如果系统没有将它们添加到对应的bins中(某种情况,后文讨论),系统就将这些chunk添加到unsorted bin中。为什么要这么做呢?这主要是为了让“glibc malloc机制”能够有第二次机会重新利用最近释放的chunk(第一次机会就是fast bin机制)。利用unsorted bin,可以加快内存的分配和释放操作,因为整个操作都不再需要花费额外的时间去查找合适的bin了。

unsorted bin只有1个。是一个由free chunks组成的循环双链表。在unsorted bin中,对chunk的大小并没有限制,任何大小的chunk都可以归属到unsorted bin中。

Small bin

小于512字节的chunk称之为small chunk,small bin就是用于管理small chunk的。就内存的分配和释放速度而言,small bin比larger bin快,但比fast bin慢。Small bin共有62个,最小的small bin的chunk size为16字节,步长为8字节,最大为512字节。

small bin还有如下操作:

  • a) 当malloc(small bin)时,类似于fast bins,最初所有的small bin都是空的,因此在对这些small bin完成初始化之前,即使用户请求的内存大小属于small chunk也不会交由small bin进行处理,而是交由unsorted bin处理,如果unsorted bin也不能处理的话,glibc malloc就依次遍历后续的所有bins,找出第一个满足要求的bin,如果所有的bin都不满足的话,就转而使用top chunk,如果top chunk大小不够,那么就扩充top chunk,这样就一定能满足需求了。

  • b) free(small chunk):当释放small chunk的时候,先检查该chunk相邻的chunk是否为free,如果是的话就进行合并操作:将这些chunks合并成新的chunk,然后将它们从small bin中移除,最后将新的chunk添加到unsorted bin中(可以看到这里用到了unsorted bin)。

Large bin

大于512字节的chunk称之为large chunk,large bin就是用于管理这些large chunk的。large bin 共有63个,但与fast bin和small bin不同的是,large bin中,每个bin链表中的chunk size可能是不同的。在这63个large bins中,前32个large bin依次以64字节步长为间隔,即第一个large bin中chunk size为512~575字节,第二个large bin中chunk size为576 ~ 639字节。紧随其后的16个large bin依次以512字节步长为间隔;之后的8个bin以步长4096为间隔;再之后的4个bin以32768字节为间隔;之后的2个bin以262144字节为间隔;剩下的chunk就放在最后一个large bin中。

鉴于同一个large bin中每个chunk的大小不一定相同,因此为了加快内存分配和释放的速度,就将同一个large bin中的所有chunk按照chunk size进行从大到小的排列:最大的chunk放在链表的front end,最小的chunk放在rear end。

malloc(large chunk)操作,初始化完成之前的操作类似于small bin,这里主要讨论large bins初始化完成之后的操作。首先确定用户请求的大小属于哪一个large bin,然后判断该large bin中最大的chunk的size是否大于用户请求的size(只需要对比链表中front end的size即可)。如果大于,就从rear end开始遍历该large bin,找到第一个size相等或接近的chunk,若相等,则分配给用户;若chunk大于用户请求的size的话,就将该chunk拆分为两个chunk:前者返回给用户,且size等同于用户请求的size;剩余的部分做为一个新的chunk添加到unsorted bin中。如果小于,则向更大size的large bin中请求chunk,若还是找不到,则查找top chunk。

large chunk的free和small bin的free操作相似,需要合并,合并后的需要添加到unsorted bin中

3.3.4 溢出思路

  • 1.如果申请了a、b、c三块连续小内存,大小为fast chunk,释放a和c,则c的fd指针指向a的地址。这时可以溢出b内存,覆盖c内存中保存的fd地址,即a地址为任意地址。当再次申请相同大小的地址时,可以申请到覆写过的地址,实现了写任意地址。

    这种方法的明显问题是,内存的边界保护使得程序无法写入没有权限的内存段。

  • 2.由于在small bin和large bin在对free(chunk)的处理过程中,会有合并chunk的过程,这个过程可能会出现memcpy操作。那么这种溢出的思路是溢出free函数的堆栈,使得free函数执行构造的shellcode。

0x04 实验过程和结果

实验中,我们编写代码读取栈和帧的dump,查看其内存结构。

4.1 进程整体内存布局

打印本程序的pid,通过pid找到/proc/$pid文件夹,查看maps文件的内容如下图所示,为本进程的内存布局。

进程整体内存布局

进程整体内存布局

可以看到,在进程一开始就被分配了heap段,这可能是gcc的特性或者已经用到的

getpid和print函数导致的,一般情况下只有在用户第一次申请堆空间时,glibc才会向系统申请大段内存用于堆管理。

4.2 栈帧结构

栈结构比较简单,编写了如下代码进行实验:

栈结构分析代码

栈结构分析代码

结果输出如下:

栈结构输出

栈结构输出

需要注意的是,只有在gcc编译时加入-fno-stack-protector选项才可以查看到如上结构,若不加该选项,则在ret addr之下会出现一个用于栈保护的字段。

4.3 堆结构

在实验中,先进行了64位系统下的堆分配实验,在出现和32位传统结构不同的情况后,实验验证了32位系统下的堆分配机制。

编写了如下两个内存dump函数,用于内存的dump:

内存dump函数1

内存dump函数1

内存dump函数2

内存dump函数2

4.3.1 64位系统的堆分配实验

设计如下程序验证64位堆的结构:

64位堆验证程序

64位堆验证程序

在这个程序中,设计申请了heap a、heap b、heap c三个堆,堆的大小为MALLOC_SIZE,测试时指定,用于测试不同大小的bin。分别释放这三个堆空间,观察堆的变化。再次申请一个heapb,查看申请到的地址情况。

fast bin实验

当MALLOC_SIZE为0x20大小,即一个fast bin的大小时,申请三个堆后内存如图所示:

64位 fast bin:堆实验1

64位 fast bin:堆实验 1

可以看到,每块内存的起始地址的-0x10(因为是64位系统)偏移处有数据,这个地址是该内存空间的chunk head,读出该数据后为0x31(小端编码),该数据说明:1) 该数据是奇数,即P位置是1,说明这个chunk的前一个chunk是allocated chunk;2) 去掉P位置后,发现此chunk的size是0x30=0x20+0x10,符合一个fast chunk的大小。

可以注意到heap c之后有一个chunk,其大小是0x20500,推测该chunk是top chunk。

接着free(heap a),内存结构如下所示:

64位 fast bin:堆实验 2

64位 fast bin:堆实验 2

没有变化,分析原因是,这个free chunk被链接到了fast bin的头指针上,没有上一个节点。为验证这个推测,进一步free(heap b),内存结构如下所示:

64位 fast bin:堆实验3

<font size="2" color="#595959"64位 >fast bin:堆实验3</font>

这时发现,chunk a仍没有变化,而chunk b的fd字段变为了chunk a的地址,即当前fast bin的头节点是chunk a,尾节点是chunk b,chunk b的fd指向chunk a。(fast chunk从尾节点开始处理)。接着free(heap c),结果如图所示:

64位 fast bin:堆实验 4

64位 fast bin:堆实验 4

进一步验证了fast bin的节点结构。此时chunk c处于队尾。现在再次malloc(0x20),观察是否会从fast bin的队尾拿到和heap c相同的堆空间。结果如图所示:

64位 fast bin:堆实验 5

64位 fast bin:堆实验 5

发现申请到了原来heap c的地址,即现在fast bin队尾的chunk。验证了64位下的fast chunk。

small bin实验

与之前代码类似,将申请的大小改为0x100,这个大小可以申请到一个small bin。首先申请heap a、heap b,结果如图所示:

64位 small bin实验1

64位 small bin实验 1

申请结果与fast bin相似,接下来执行free(heap a),得到结果如下:

64位 small bin实验 2

64位 small bin实验 2

在执行free(heap b),得到结果如下:

64位 small bin实验 3

64位 small bin实验 3

发现这段输出有以下特点:

  • a) fd被使用,且确实指向chunk a

  • b) chunk b的P字段仍然为1。P字段标志了前一个chunk是否in use,small bin与fast bin不同,small bin会合并chunk,而这里仍然只能看到单链表和P不置为0,这都是fast bin的标志

继续实验,free(heap c),结果如下:

64位 small bin实验4

64位 small bin实验 4

与之前结果相似,说明当前运行的机制并不是small bin,而是fast bin。 总结

经过简单实验,发现64位机器下堆管理机制和32位并不相同,结果表明fast bin运行正常,而small bin运行不正常。另外更改了更大的内存申请,small bin和large bin都没有按照期望的方式运行,而是依然按照fast bin的机制运行。可以做出假设,64位版本的glibc堆管理机制的fast bin、small bin large bin的chunk size可能已经发生了变化。由于资料较少,这里不做进一步分析。

4.3.2 32位系统的堆分配验证

为了验证64位环境下的实验方式是正确的,运行了同样的代码在32位机器上进行了实验。

32 位 fast bin实验

首先申请heap a,heap b,heap c堆内存,各申请0x20大小,dump如下图所示:

32位fast bin实验 1

32位fast bin实验 1

可以发现,32位机器的chunk size长度是4字节,header长度是8字节,与64位不同。其余运行结果相同。其中chunk size = 0x28,由于header长度是8字节,则正好是0x20的申请长度,与预期相符。

接着执行free(heap a)、free(heap b)操作,执行后dump如下:

32位fast bin实验 2

32位fast bin实验 2

可以观察到,fast bin机制生效,产生了一条fast bin的链表。

free(heap c),malloc(0x20)的结果均与预期相符,说明fast bin的机制在32位系统上生效。

32 位 small bin 实验

首先给heap a,heap b,heap c申请0xb0大小的堆空间,结果dump如下图所示:

32 位 small bin 实验 1

32 位 small bin 实验 1

再free(heap a),结果如下图所示:

32 位 small bin 实验 2

32 位 small bin 实验 2

可以发现,在free 了chunk a后,chunk b的P字段变为了0,说明前一个chunk,即chunk a,已经是free状态的了,同样,chunk a应该正处于small bin[0xb0]的队尾。同时可以观察到,chunk b的pre-chunk-size字段的值为0xb8,正是已经被free掉的chunk a的大小,与预期一致。

接着free(heap b),结果如图所示:

32 位 small bin 实验 3

32 位 small bin 实验 3

此时的dump有以下特点:

  • a) chunk a size = 0x170 = 2 * 0xb8

  • b) chunk c 的P字段变为了0

  • c) chun c 的pre chunk size为0x170

说明:heap b已经被成功free,且合并到了前一个chunk a上,合起来变成了新的chunk,大小为0x170 。之后free(heap c)得到相同结果。

4.3.3 总结

针对32位系统的堆结构实验印证了ptmalloc2的管理机制是生效的,那么64位的堆管理机制有了其他的变化,如不同bin的chunk size等,需要进一步的研究学习

0x05 相关资料

[1] Linux堆内存管理深入分析(上半部)

[2] Linux堆内存管理深入分析(下半部)