0×00 前面的话
在内存中，堆是一个很有趣的地方，因为它可以由用户去直接的进行分配与销毁，所以也产生了一些很有趣、奇思妙想的漏洞，像unlink漏洞、House系列漏洞等等。但是在学习的过程中，我们很容易难以理解那些介绍的比较模糊的概念，比如 unsortedbin 在某些条件下会放回 smallbin 或 largebin 中，那到底是什么时候？也会对一些大佬构造的 payload 犯迷糊，为什么这里多了一个chunk，为什么这个字节要填充…，大佬们往往不对这些细节做过多的解释，但是这可难为了我们初学堆利用的新兵，所以，我想写几篇文章，将堆的运作机制，例如一些基本的概念，malloc机制、free机制、保护机制，和利用方法结合起来说一下，让大家能够对堆这一块有个较为清楚的认识，少走一些弯路。首先呢，我想在这篇文章中较为细致的介绍一下堆中的一些情况，剩下的有机会的话我会一并写成一个系列。
这篇文章主要分为四个部分：
0x01 chunk 简介
0x02 bin 简介
0x03 malloc 机制
0x04 free 机制
这些内容相对比较重要，如果看完还觉得不够的，推荐大家去读一下华庭老师的《glibc内存管理ptmalloc源代码分析》。
0×01 chunk 简介
首先先说一下堆是如何分配的，在内存中，堆（低地址到高地址，属性RW）有两种分配方式（与malloc申请chunk做区分）:
mmap: 当申请的size大于128kb时，由mmap分配
brk: 当申请的size小于128kb时，由brk分配，第一次分配132KB（main arena）,第二次在brk下分配，不够则执行系统调用，向系统申请
在内存中进行堆的管理时，系统基本是以 chunk 作为基本单位，chunk的结构在源码中有定义
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};
INTERNAL_SIZE_T 即 size_t
#ifndef INTERNAL_SIZE_T
#define INTERNAL_SIZE_T size_t
#endif
我们可以打印一下本机的 sizeof(size_t)，这个长度可以说是一个基准单位
#include<stdio.h>
int main() {
printf("sizeof(size_t) is %d\n",sizeof(size_t));
return 0;
}
这个结构不再多谈，相关的介绍网上很多，主要提一下结构体中最后两个指针 fd_nextsize 和 bk_nextsize，这两个指针只在 largebin 中使用，其他情况下为 NULL。我们可以根据 chunk 的状态将其分为三种（allocated chunk、free chunk、top chunk）:
allocated chunk:
chunk header:
prev_size（当上一块是free状态时，存储该chunk的size，否则被上一块chunk使用）
size（该chunk大小（包括chunk header），某位3 bits为标志位）
0bit表示上一chunk是否free
1bit表示该chunk是否由mmap分配
2bit表示该chunk是否属于main arena
data:
free chunk:
chunk header:
prev_size:
size:
fd:指向 bin 中的next chunk
bk:指向 bin 中的last chunk（bin中先进的为last，后进的为next）
fd_nextsize:
bk_nextsize:
top chunk:brk中未分配的顶端chunk
chunk header:
prev_size:
size:
其中在 free chunk中有一种特殊的chunk(last remainder chunk):
last remainder chunk:从free chunk中malloc时，如果该chunk足够大，那么将其分为两部分，未分配的放到last remainder中并交由 unsorted bin 管理。
重点强调一下：这里的上一块表示在内存的堆中连续的chunk的上一块，区别bin中的前后关系。另外 chunk 的前后关系只有在bin中是使用fd、bk指针标识的，在内存中连续的chunk则通过 prev_size 和 size 来寻找前后 chunk，当然，这也就造成了漏洞。
由于chunk会在几种状态之间切换，当其为free chunk时，最少需要4*sizeof(size_t)的空间，所以有最小分配大小。
并且由于prev_size的复用，所以实际申请的大小为 max(2sizeof(size_t)(chunk_header)-sizeof(size_t)(prev_size)+申请大小,最小分配大小)，而且 chunk的size是按照 2sizeof(size_t)对齐的，也就是说当你申请一个不是 2*sizeof(size_t)整倍数的空间时， malloc 返回的 size 有会对齐，大于实际申请的空间。
另外提一下，当 malloc 一个chunk后，实际返回用户的地址为chunk除去chunk header后的地址，而在bin中存储的是chunk的地址，也就是说
p = malloc(0x40); // 假设chunk的地址为 0xdeadbeef,则返回给用户的地址是 0xdeadbeef+sizeof(chunk header)
free(p) //将p释放掉后，保存在bin中的地址为 0xdeadbeef
0×02 bin简介
bin在内存中用来管理free chunk，bin为带有头结点（链表头部不是chunk）的链表数组，根据特点，将bin分为四种，分别为(fastbin、unsortedbin、smallbin、largebin):
fastbin:
根据chunk大小维护多个单向链表
sizeof(chunk) < 64(bytes)
下一chunk（内存中）的free标志位不取消，显示其仍在使用
后进先出（类似栈），先free的先被malloc
拥有维护固定大小chunk的10个链表
unsortedbin:
双向循环链表
不排序
暂时存储free后的chunk，一段时间后会将chunk放入对应的bin中（详见0x02）
只有一个链表
smallbin:
双向循环链表
sizeof(chunk) < 512 (bytes)
先进先出（类似队列）
16,24...64,72...508 bytes(62个链表)
largebin:
双向循环链表
sizeof(chunk) >= 512 (bytes)
free chunk中多两个指针分别指向前后的large chunk
63个链表:0-31(512+64*i)
32-48(2496+512*i)
...
链表中chunk大小不固定，先大后小
这其中 fastbin 像是cache，用来实现快速的chunk分配，其中的chunk size大小与smallbin中的有重复（只是说大小，chunk并不重复）
unsortedbin 功能也是作为cache，尽量减少搜索合适chunk的时间。
这四个bin中，除了fastbin，其他三个都是维护双向循环链表，并且由一个长度为128 size_t的数组bins维护，bins结构如下：
| 0 | 1 | 2-63 | 64-126 | 127 |
0×03 malloc机制
malloc功能主要由 _int_malloc() 函数实现，原型如下：
static Void_t* _int_malloc(mstate av,size_t bytes)
当接收到申请的内存大小后，我们看一下malloc的申请过程。
长度位于 fastbin 时:
1.根据大小获得fastbin的index
2.根据index获取fastbin中链表的头指针
如果头指针为 NULL，转去smallbin
3.将头指针的下一个chunk地址作为链表头指针
4.分配的chunk保持inuse状态，避免被合并
5.返回除去chunk_header的地址
长度位于 smallbin 时:
1.根据大小获得smallbin的index
2.根据index获取smallbin中双向循环链表的头指针
3.将链表最后一个chunk赋值给victim
4.if(victim == 表头)
链表为空，不从smallbin中分配
else if(victim == 0)
链表未初始化，将fastbin中的chunk合并
else
取出victim,设置inuse
5.检查victim是否为main_arena,设置标志位
6.返回除去chunk_header的地址
长度位于 largebin 时:
1.根据大小获得largebin的index
2.将fastbin中chunk合并，加入到unsortbin中
留意一点：系统实际分配的内存地址与返回的地址是不同的，返回的地址直接指向了除去 chunk header 的地址。
当然，我们注意到上面的分配过程并没有完成，当 smallbin 中没有 chunk 或者 smallbin 未初始化时，并没有返回分配结果，这种情况下的chunk分配将在后面与largebin的分配一起处理
unsortedbin:
1.反向遍历unsortedbin,检查 2*size_t<chunk_size<内存总分配量
2.unsortedbin的特殊分配:
如果前一步smallbin分配未完成
并且 unsortedbin中只有一个chunk
并且该chunk为 last remainder chunk
并且该chunk大小 >（所需大小+最小分配大小）
则切分一块分配
3.如果请求大小正好等于当前遍历chunk的大小，则直接分配
4.继续遍历，将合适大小的chunk加入到smallbin中，向前插入作为链表的第一个chunk。(smallbin中每个链表中chunk大小相同)
5.将合适大小的chunk加入到largebin中，插入到合适的位置（largebin中每个链表chunk由大到小排列）
largebin:
1.反向遍历largebin，由下到上查找，找到合适大小后切分
切分后大小<最小分配大小，返回整个chunk，会略大于申请大小
切分后大小>最小分配大小，加入 unsortedbin。
2.未找到，index+1，继续寻找
如果这之后还未找到合适的chunk，那么就会使用top chunk进行分配,还是没有的话，如果在多线程环境中，fastbin可能会有新的chunk，再次执行合并，并向unsortedbin中重复上面，还是没有的话，就只能向系统申请了。
以上就是malloc分配的全经过。
几个malloc检查：
1.从fastbin中取出chunk后，检查size是否属于fastbin
2.从smallbin中除去chunk后，检查victim->bk->fd == victim
3.从unsortbin取chunk时，要检查2*size_t<chunk_size<内存总分配量
4.从largebin取chunk时，切分后的chunk要加入unsortedbin,需要检查 unsortedbin的第一个chunk的bk是否指向unsortedbin
0×04 free机制
1.首先使用 chunksize(p) 宏获取p的size
#define PREV_INUSE 0x1
#define IS_MMAPPED 0x2
#define NON_MAIN_ARENA 0x4
#define SIZE_BITS (PREV_INUSE|IS_MMAPPED|NON_MAIN_ARENA)
#define chunksize(p) ((p)->size & ~(SIZE_BITS))
也就是直接屏蔽了控制位信息，不过不要紧，chunk的分配是 2*sizeof(size_t) 对齐的，所以屏蔽低三位对大小无影响
2.安全检查：
chunk的指针地址不能溢出
chunk 的大小 >= MINSIZE(最小分配大小)，并且检查地址是否对齐
3.大小为fastbin的情况(不改变inuse位)
1).检查下一个chunk的size：2*size_t<chunk_size<内存总分配量
2).double free检查：
检查当前free的chunk是否与fastbin中的第一个chunk相同，相同则报错
简单的小例子
#include <stdio.h>
#include <stdlib.h>
int main() {
char *a=malloc(24);
char *b=malloc(24);
free(a);
free(a);
}
报错
#include <stdio.h>
#include <stdlib.h>
int main() {
char *a=malloc(24);
char *b=malloc(24);
free(a);
free(b);
free(a);
}
没问题
4.其他情况
1).检查下一个chunk的size：2*size_t<chunk_size<内存总分配量
如果当前 chunk 为 sbrk()分配，那么它相邻的下一块 chunk 超过了分配区的地址，会报错
2).double free检查：
检查当前free的chunk是否为top chunk，是则报错
根据下一块的inuse标识检查当前free的chunk是否已被free
3) unlink合并：
检查前后chunk是否free，然后向后（top chunk方向）合并，并改变对应的inuse标志位
unlink检查： I.当前chunk的size是否等于下一chunk的prev_size
II.P->bk->fd == P && P->bk->fd == P
如果合并后 chunk_size > 64bytes,则调用函数合并fastbin中的chunk到unsortedbin中
将合并后的chunk加入unsortedbin
4) unsortedbin检查
需要检查 unsortedbin的第一个chunk的bk是否指向unsortedbin
我们可以看到，针对free的检查主要是下一块的size和inuse位，另外fastbin的检查可以用来做double free。
0×05
以上就是对堆的情况所做的一些介绍，了解堆的保护机制后，我们便可以在攻击时想办法进行绕过，从而构造出那些光怪陆离的payload。