1. 堆与栈的区别：

• 栈是具有硬件直接支持的 （高地址到低地址）
• 栈存储数据+控制流信息
• 堆是由操作系统的库函数予以支持的（主动申请，低地址到高地址）
• 堆存储数据
• 栈的地址较高（0x7fff…）而堆的地址通常较低(0x5fff…)

所以相比较而言，栈的溢出攻击要简单一点，通过缓冲区溢出修改返回地址。而堆的攻击则主要体现在如何获得对数据的非法访问，或者越权访问，覆盖写入 等等

---

2. 堆的申请

堆是用malloc函数申请使用的。如：void *ptr=malloc(0x10);

在内存中的调用过程：

1. 系统会调用一些函数在内存中开辟一大段空间作为堆的分配使用空间。
2. malloc函数再从这一片堆的分配使用空间中分配0x10大小的空间，将指向该空间的地址返回给ptr，剩下的空间称为topchunk
   

堆的创建和维护：
通过malloc实现，而具体的malloc实现方式：

• dlmalloc – General purpose allocator
• ptmalloc2 – glibc
• jemalloc – FreeBSD and Firefox
• tcmalloc – Google
• libumem – Solaris

• 在一种情况下，堆的大小是合适的，此时系统调用sys_brk函数直接调整。
  

如果空间比较大的话需要调用MMP去管理，创建私有的匿名映射段，分配新的内存。

看一段代码：

---

3. 堆的工作原理

1. 起初，系统创建进程

2. 数据段上空无一物，进程的运行在栈上。
   

3. malloc说，要有堆，于是有了堆。
   

---

1. 然后看一下上一段代码的调试过程：
   
   重点问题已经在红字部分标注出来：为什么申请1000字节的大小，却分配了132K字节堆呢？

这一部分，被称为arena，又由于他是由主线程创建的，所以也称为main arena。剩下的申请直接从剩余部分。此时系统调用sys_brk函数直接调整。

2. free之后：观察到两段代码并没有发生改变。
   

bin就是管理空闲空间的。

3. 然后到子进程，没有malloc之前，就已经分配了栈空间：
   

4. 在malloc之后：
   
   申请了1KB，其实分配了1MB，这个空间放在内存映射段中（地址大于0x4000000）。

堆的工作原理总结：

场景，单核的32位操作系统（场地数量2*1+1=3），运行多线程程序---1个主线程+3个用户线程，malloc如何确保这4个线程共享3个arena？> 主线程分配主arena,线程1、2分别分配arena，那么线程3需要重复使用已分配好的arena> glibc malloc循环遍历所有可用的场地，如果lock成功（该 场地当前对应的线程并未使用堆内存），则将该场地供线程3使用> 如果没有找到可用的area，则将线程3的malloc操作阻塞，直到找到可用的为止

在堆中有三种重要的数据结构：

1. malloc_state是arena的head：
   一个进程的arena可以有多个堆，而这些堆共享一个head，即malloc_state，主线程只有一个堆。

2. heap_info：一个线程的arena可以维持多个堆（因为线程在MMP区），可以申请新的堆。heap_info是堆头。Main Arena只有一个堆，所以不需要heap_info。

3. malloc_chunk：是数据块的头部，每个数据块都有它的头部 。

申请新的堆可以是不连续的，通过指针链接。

---

4. 堆的使用

问题1：向前合并
减少碎片，提高使用效率。若前后均未free，根据size可以直接定位后一个free，如何向前合并？

增加一个脚标，然而很浪费内存，应当进行优化：

增加标志位b，与a一同进行判断，然后去除payload的脚标。

那么此时第二个问题就出来了：多线程时标志位不够！

需要记录：Main/Thread Arena？ _brk/mmap实现？
然而，只有3个标志位。

前一个M与后一个P保存了同一份信息，那么应该怎么进行优化呢？只需保留前一个chunk的标志位即可。

此时标志位含义：
N:_brk?
M:MMP?
P:前一个chunk的空闲？

最终优化;

fd指针与bk指针：显式指针。提高效率。

4. 隐式/显式链表结构（后者简称bin）

一开始：

2号被占用后：

释放出2号chunk。

5. bin

bin是记录free chunk的链表数据结构，在glibc中可分为：

• fastbinsY，一个用于记录所有fastbins的数组，size为16-80字节
• bins，也是一个数组，记录除fast bins之外的所有bins；其中bin 1 为unsorted bin，bin 2 到63为small bin（小于512字节），bin 64到126为large bin（大于512字节）
  

具体模型：

1. 大小为 16 ~ 80 字节的 chunk 被称为「fast chunk」。在所有的 bins 中，fast bins 路径享有最快的内存分配及释放速度。
   数量：10
   每个 fast bin 都维护着一条 free chunk 的单链表，采用单链表是因为链表中所有 chunk 的大小相等，增删 chunk 发生在链表顶端即可；—— LIFO。添加操作(free内存)就是将新的fast chunk加入链表尾，删除操作(malloc内存)就是将链表尾部的fast chunk删除。需要注意的是**，为了实现LIFO算法，fastbinsY数组中每个fastbin元素均指向了该链表的rear end（尾结点），而尾结点通过其fd指针指向前一个结点，依次类推。**
   chunk 大小：8 字节递增
   fast bins 由一系列所维护 chunk 大小以 8 字节递增的 bins 组成。也即，fast bin[0] 维护大小为 16 字节的 chunk、fast bin[1] 维护大小为 24 字节的 chunk。依此类推……
   指定 fast bin 中所有 chunk 大小相同；
   在 malloc 初始化过程中，最大的 fast bin 的大小被设置为 64 而非 80 字节。因为默认情况下只有大小 16 ~ 64 的 chunk 被归为 fast chunk 。
   无需合并 —— 两个相邻 chunk 不会被合并。虽然这可能会加剧内存碎片化，但也大大加速了内存释放的速度！

2. malloc(fast chunk)
   初始情况下 fast chunck 最大尺寸以及 fast bin 相应数据结构均未初始化，因此即使用户请求内存大小落在 fast chunk 相应区间，服务用户请求的也将是 small bin 路径而非 fast bin 路径；
   初始化后，将在计算 fast bin 索引后检索相应 bin；
   相应 bin 中被检索的第一个 chunk 将被摘除并返回给用户。

3. free(fast chunk)
   计算 fast bin 索引以索引相应 bin；free 掉的 chunk 将被添加到上述 bin 的顶端。

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

1. unsorted bin的个数： 1个。
2. unsorted bin是一个由free chunks组成的循环双链表。
   Chunk size: 在unsorted bin中，对chunk的大小并没有限制，任何大小的chunk都可以归属到unsorted bin中。这就是前言说的特例了，不过特例并非仅仅这一个，后文会介绍。

小于512字节的chunk称之为small chunk，small bin就是用于管理small chunk的。就内存的分配和释放速度而言，small bin比larger bin快，但比fast bin慢。每个small bin也是一个由对应free chunk组成的循环双链表。第一个small bin中chunk大小为16字节，后续每个small bin中chunk的大小依次增加8字节，即最后一个small bin的chunk为16 + 61*8 = 508字节。
大于512字节的chunk称之为large chunk，large bin就是用于管理这些large chunk的。第一个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。

6. Top chunk：

当一个chunk处于一个arena的最顶部(即最高内存地址处)的时候，就称之为top chunk。

该chunk并不属于任何bin，而是在系统当前的所有free chunk(无论那种bin)都无法满足用户请求的内存大小的时候，将此chunk当做一个应急消防员，分配给用户使用。

如果top chunk的大小比用户请求的大小要大的话，就将该top chunk分作两部分：
1）用户请求的chunk；
2）剩余的部分成为新的top chunk。
否则，就需要扩展heap或分配新的heap了——在main arena中通过sbrk扩展heap，而在thread arena中通过mmap分配新的heap。

7. 栈溢出

7.1 与栈溢出的区别：

1. 溢出方向 == 堆增长方向

   首先破坏（虚拟地址意义上的）下一个堆块的构造：覆盖下一块头部的信息。

2. Linux上的典型堆溢出利用方式：

• 攻击fastbin
• 攻击unlink

7.2 攻击fastbin：

注意fastbin数组指向的是队尾

7.2.1 攻击原理:

在chunk被分配时，从队尾删除，并将当前chunk的fd写入到fastbin。下次分配就分配这个fd对应地址的chunk。
具体用法是chunk0写入溢出，覆盖相邻的chunk1的fd。当chunk1被分配时，被篡改的chunk1中的fd被写入fastbin。在chunk2被分配时就分配攻击者想攻击的内存地址。因为被分配的内存空间可写，攻击者因此实现对指定地址写入数据的目的。

7.2.2 攻击代码：

该代码在调用read时，向buf0写入的内容超过了其本身的大小，发生了堆溢出。我们可以利用此处漏洞，修改相邻chunk的fd内容，造成在为buf2分配内存时，从fastbin返回得到非正常的地址。
0x29=41=32+8+1 数据段32Bytes + 头部8Bytes + flag=1(表示被使用）

7.3 攻击unlink：

核心就是理解与利用glibc malloc的free机制

一旦涉及到free内存（非mmaped的chunks的回收机制），那么就意味着有新的chunk由allocated状态变成了free状态，此时glibc malloc就需要进行合并操作——向前以及(或)向后合并

将previous free chunk合并到当前free chunk，叫做向后合并；将后面的free chunk合并到当前free chunk，叫做向前合并

7.4 前向合并

攻击者在代码[3]中精心构造输入数据并通过strcpy覆盖了second chunk的chunk header，相关数据如下
prev_size =一个偶数，这样其PREV_INUSE位就是0了，即表示前一个chunk为free
size = -4
fd = free函数的got表地址address – 12；(简称为“free addr – 12”)
bk = shellcode的地址

此时P = nextchunk, BK = bck, FD = fwd。

1)首先FD = nextchunk->fd = free地址 – 12;
2)然后BK = nextchunk->bk = shellcode起始地址；
3)再将BK赋值给FD->bk，即（free地址 – 12）->bk = shellcode起始地址；
4)最后将FD赋值给BK->fd，即(shellcode起始地址)->fd = free地址 – 12。

结合上图就很好理解第3，4步了。细心的朋友已经注意到，free addr -12和shellcode addr对应的prev_size等字段是用虚线标记的，为什么呢？因为事实上它们对应的内存并不是chunk header，只是在我们的攻击中需要让glibc malloc在进行unlink操作的时候将它们强制看作malloc_chunk结构体。这样就很好理解为什么要用free addr – 12替换next chunk的fd了，因为(free addr -12)->bk刚好就是free addr（free函数的got表地址），也就是说第3步操作的结果就是将free addr处的数据替换为shellcode 的起始地址。

由于已经将free addr处的数据替换为了shellcode的起始地址，所以当程序在代码[5]处再次执行free的时候，就会转而执行shellcode了。

8. 堆溢出防御

相比栈溢出，针对堆溢出的防御措施更易实用化

堆依靠系统库实现其维护，故堆保护 == 系统库升级

针对unlink的保护：

• Double Free检测:该机制不允许释放已经处于free状态的chunk。因此，当攻击者将second chunk的size设置为-4的时候，就意味着该size的PREV_INUSE位为0，也就是说second chunk之前的first chunk(我们需要free的chunk)已经处于free状态，那么再free就报出double free错误
• next size非法检测: 检测next size是否在8到当前arena的整个系统内存大小之间。因此当检测到next size为-4的时候，就会报出invalid next size错误
• 双链表冲突检测:执行unlink操作的时候检测链表中前一个chunk的fd与后一个chunk的bk是否都指向当前需要unlink的chunk