前言
前段时间入门了 pwn ，慢慢掌握了一些栈上的一些攻击技巧，但是发现在比赛中堆的利用才是王道…无奈只能在堆上再花些功夫。但是发现入门堆不是一件容易的事，毕竟涉及到了内存管理的知识，比较复杂。所以笔者看了大量文章和接受了大牛的指点，决定对堆中的一些基本概念进行总结，还恳请师傅们斧正~
这里不会讲太多的原理性（函数源码的实现等等）的东西，尽量以最简单的形式再结合一下小例子来揭开堆和内存管理的神秘面纱。
什么是堆？
首先先明确一下堆的概念，堆不同于栈，堆是动态分配的（由操作系统内核或者堆管理器），只有在程序中需要时才会分配。在 CTF 的 pwn 程序中，栈是程序加载进内存后就会出现，而堆是由 malloc、alloc、realloc 函数分配内存后才会出现。
- windows 和 linux 下的堆分配、管理方式都不同，这里主要讲到的是 CTF 中常出现的 linux 下的堆分配知识
先看看堆在虚拟内存中的位置
- 堆的生长方向是从低地址向高地址生长的，而栈是从高地址向低地址生长的。
实际上堆可以申请到的内存空间比栈要大很多，在 linux 的 4G 的虚拟内存空间里最高可以达到 2.9 G 的空间
对堆操作的是由堆管理器（ptmalloc2）来实现的，而不是操作系统内核。因为程序每次申请或者释放堆时都需要进行系统调用，系统调用的开销巨大，当频繁进行堆操作时，就会严重影响程序的性能
下面的分析都是以 glibc 库下的 ptmalloc2 堆管理器来讲解的。
堆的基本结构
先简单的画一个图吧：
1.pre size 字段。只有在前面一个堆块是空闲的时候才有指，用来指示前一个堆块的大小。前面一个堆块在使用时，他的值始终为 0
2.size 字段。是用来指示当前堆块的大小的（头部加上 user data 的大小）。但是这个字段的最后三位相当于三个 flag ，有另外的作用。
这三位的作用分别是：
1.NON_MAIN_ARENA 这个堆块是否位于主线程
2.IS_MAPPED 记录当前 chunk 是否是由 mmap 分配的
3.PREV_INUSE 记录前一个 chunk 块是否被分配
这里重点讲解最后一位：用来记录前一个 chunk 块是否被分配，被分配的话这个字段的值为 1，所以经常会在已分配的堆块中的 size 字段中发现值比原来大 1 个字节。
- 所以前一个堆块的释放与否都和这两个字段（pre_size、size）的值有关，这是因为便于内存的释放操作（free）
4.user data 顾名思义就是用来存放用户数据的。
使用 malloc 函数分配到的内存的返回值指针是指向 user data （用户数据区），在后面的例子中也会讲到这个问题。
例如在 64 位程序中：
malloc(8)
申请到的堆块总大小为 16 + 8 + 8 + 1 = 0x21
1.第一个 16 字节是系统最小分配的内存，也就是说你如果想要申请的内存小于系统最小分配的内存的话，就会按照最小的内存来分配。
- 在 64 位系统中这个值是 16 个字节，在 32 位系统中是 8 个字节
- 例如，如果代码中是 malloc(0) 的话，堆管理器也会分配最小内存空间给你
2.第二个 8 字节是 pre size 字段的大小（32 位的为 4 字节）
3.第三个 8 字节为 size 字段的大小（32 位的为 4 字节）
4.最后一个 1 字节是 PREV_INUSE 的值，只有 0 或 1两个值
说了这么多的理论肯定会有点头大，不过没关系。在后面会有实例讲解，动手调试的时候对照着每一个字段分析就会好点。
指针与地址
指针这一块知识在 c 语言里学的不太好的，可以在学习堆的过程中慢慢巩固一下知识。
- 熟练掌握指针的使用在堆的题目分析中还是很有帮助的。下面简单说一下堆分配中的指针会用到了地方。
首先要明确用户在调用 malloc 函数时返回的值为一个指针，指向分配到堆空间（用户数据区），这个在最前面的那个图片也已经标出来了。
有时候题目是以更复杂的情况，用指针来表示某个数据结构的，例如下面的这个图中的例子：
first chunk（second chunk）表示第一和第二个结构，每个结构中都有一个 point_heap 指针来指向存储用户数据的堆块（chunk）。
左边的这个本身就是一个堆块，用来存放一些全局信息。比如 max_size 存储了能够存储的最大结构数量；exist_num 表示已经存储的结构的数量。
IDA 中常见的指针表示形式
在 IDA 伪代码中的指针形式形如下面的情况：
*(qword_6020A8 + 8)
表示取到 qword_6020A8 这个地址加 8 偏移的那个地址存储的值
汇编代码等同于：
.text:0000000000400F85 mov rax, cs:qword_6020A8
.text:0000000000400F8C mov rax, [rax+8]
简单转化一下，也就是：
*(addr) = [addr]
链表
在 pwn 的堆题目中，经常会有像一些”笔记管理系统”之类的题目，例如下面这里例子
代码提供了最基本的增删查改的功能。这个”笔记”的数据结构通常就是使用链表连接起来的，记录了当前 note 的大小、属性、内容等等。
例如，下面这个例子就是以指针为基础来存储这个 note 结构的。这里的 i 代表 note 的索引，若这里的 i = 0 时：
(qword_6020A8 + 16) 就*代表从 qword_6020A8 这个地址出再往后偏移 16 个字节，取到这个地址存储的值，接着把 1 赋值给这个地方（也就是把 1 存入这个地址）
同样的 *(qword_6020A8 + 24) 就代表偏移 24 个字节处的值为 len
依次类推就可以在不连续的内存空间中，把整个 note 的数据结构存储下来了。
申请堆块的本质
堆管理器 ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。
ptmalloc2 的作用通俗的讲就是相当于一个”中间商”，在程序想要申请向系统申请堆空间时，这里的 ptmalloc2 就会申请一块很大的空间，并根据算法从这些内存中把空间真正的分配给程序。
简单点说就是下面这个图中的情况：
这里的举一个最简单的例子：
#include <stdlib.h>
#include <malloc.h>
int main(){
char *p;
p = malloc(10);
return 0;
}
在 gdb 中进行调试，在 call malloc 处下一个断点，在这里使用 vmmap 命令，查看内存分布。可以看到此时并没有发现堆段
单步 n ，vmmap 命令再次查看内存，发现出现了堆段
但是这里我们明明只是申请了 10 字节的大小，但是为什么这里的为什么给了这么大的堆段呢？
0x00602000 ~ 0x00623000
计算一下，刚好是 132 kB
(0x00623000-0x00602000)/1024 = 132 kB
原来这132KB的堆空间叫做arena，此时因为是主线程分配的，所以这个区域叫做 main arena
也就是说这 132 KB 是”厂家”（内核）批发给”中间商”（ptmalloc2）的货物，以便下次程序在向系统申请小内存的时候，直接去”中间商”去取就行了，他就会在这 132KB 中按照要申请”货物”的多少进行分配下去。若”中间商”缺货了话，ptmalloc2 就继续去找”厂家”（系统内核）去取货
查看已分配的堆内存分布
在上面我们动态调试的时候已经执行了 malloc 函数，申请到的堆指针是保存在 eax 中的
我们这里使用下面这个命令来查看内存堆块情况：
x/32gx 0x602010-0x10
- 32位的程序使用 x/32xw 比较直观一点
这里减去 0x10 表示从堆块的头部开始观察（包含 pre size 和 size 字段）
main_arena 与 top chunk
main_arena
这个 main_arena 其实就是 ptmalloc2 堆管理器通过与操作系统内核进行交互申请到的，也就是相当于上面所说的”批发”到的一堆货物
因为是主线程分配的，所以叫做main arena，通过增加 program break location 的方式来增加 main arena 的大小。
使用 brk 方式扩展内存的方式这里就不说了，感兴趣可以自己去查一下资料
参考 ctf-wiki：
https://ctf-wiki.github.io/ctf-wiki/pwn/linux/glibc-heap/heap_overview/#_4
在 gdb 调试中，使用
x/32gx &main_arena
可以看到 main_arena 的内存分配情况。
top chunk
顾名思义，是堆中第一个堆块。相当于一个”带头大哥”，程序以后分配到的内存到要放在他的后面。
在系统当前的所有 free chunk(无论那种 bin)，都无法满足用户请求的内存大小的时候，将此 chunk 当做一个应急消防员，分配给用户使用。
简单点说，也就是在程序在向堆管理器申请内存时，没有合适的内存空间可以分配给他，此时就会从 top chunk 上”剪切”一部分作为 chunk 分配给他
free 函数和 bins
bins 这个概念是与内存回收相关的，也就是堆管理器会根据用户已经申请到的内存空间大小进行释放，来决定放入哪类 bins 当作去。bins 直接翻译过来就是”垃圾桶”的意思，所以在系统在决定使用哪个 bins 时可以看作为”垃圾的分类”。
主要的 bins 分为以下几类，这里重点讲解一下 fast bin，因为 fast bin 是使用到的最多的一类，也是其中结构最为简单的。
free 函数
free 函数的使用是和 bins 的分配息息相关的。用一个简单的例子来理解一下 free 函数的实现原理。
代码如下：
#include <stdlib.h>
#include <string.h>
int main(){
char *p;
p = malloc(10);
memcpy(p,"Hello",5);
free(p);
return 0;
}
- 程序将 “Hello” 字符串复制到申请到的堆内存空间中。
编译后用 gdb 调试，在 call memcpy 处下一个断点，单步后将 “Hello” 复制到堆块中
继续使用 x/32gx 0x602010-0x10 命令查看堆块情况
继续单步 n，执行 free 函数之后，查看堆块情况
这里可以看出原本堆块中存储的内容已经被清空，然后查看一下 main_arena 的值，发现其中 +0x8 的偏移处，存储了指向已经 free 了的指针（指向头部，而不是 user data）
所以调用 free 函数以后程序做了两件事：
1.清空此堆块的 user data
2.将此堆块的指针存储到 main_arena 中了（或是 fast bin 中）
fast bin
顾名思义，就是为了快速重新分配回内存而存在的一个结构。
fastbin所包含chunk的大小为16 Bytes, 24 Bytes, 32 Bytes, … , 80 Bytes。当分配一块较小的内存(mem<=64 Bytes)时，会首先检查对应大小的fastbin中是否包含未被使用的chunk，如果存在则直接将其从fastbin中移除并返回；否则通过其他方式（剪切top chunk）得到一块符合大小要求的chunk并返回。
引用一张图：
- 这里的横向排列的就是 main_arene（fast bin）的内存地址
假如此时 0x0804a000 处的堆块（实际堆块中的 size 字段要减去 PREV_INUSE 字段值 1，）已经被 free 了，那么他就会被存储在表示 40 bytes 的 fast bin 的内存地址里
- 注意：这里把指针和地址区别开。地址存储的是指针，64 位的指针占 8 个字节。
假设我们现在还是以 64 位下的 malloc(10) 为例子。
根据前面那个 free 函数的例子，查看 main_arena 地址中的指针值我们可以看出来，+0x8 偏移处才是指向 malloc(10) 的堆块的指针（这个堆块分配后的 user data 实际大小是 16 字节）
gdb-peda$ x/2gx &main_arena (16 bytes 的链表头)
0x7ffff7dd3760 <main_arena>: 0x0000000000000000 0x0000000000602000
所以这个 16 字节的堆块的指针会被插入属于他的这个链表队列中，也就是如下的情况。
所以这也就印证了在 main_arena 中分别表示 16 Bytes, 24 Bytes, 32 Bytes, … , 80 Bytes 的内存地址中分别存储着已经 free 的而且满足这个大小的 chunk的指针。
1.使用单链表来维护释放的堆块
也就是和上图一样，从main_arena 到 free 第一个块的地方是采用单链表形式进行存储的，若还有 free 掉的堆块，则这个堆块的 fk 指针域就会指针前一个堆块。
如下图所示，此时就是一个单链表结构
2.采用后进先出的方式维护链表（类似于栈的结构）
当程序需要重新 malloc 内存并且需要从fastbin 中挑选堆块时，会选择后面新加入的堆块拿来先进行内存分配
如上图，如果程序重新请求和上面的堆块大小一样时候（malloc），堆管理器就会直接使用 fast bin 里的堆块。
这里的话也就是直接使用第二次释放的这个堆块，然后将这个堆块从链表中移除，接着根据堆块的 fk 指针找到这个堆块，此时 main_arena 就指向了这里。也就是恢复到了上面第一个图中的情况。
small bin
顾名思义，这个是一个 small chunk ，满足的内存空间比 fast bin 大一点。
如果程序请求的内存范围不在 fast bin 的范围内，就会考虑small bin。简单点说就是大于 80 Bytes 小于某一个值时，就会选择他。
unsorted bin
当 fast bin、small bin 中的 chunk 都不能满足用户请求 chunk 大小时，堆管理器就会考虑使用 unsorted bin 。它会在分配 large chunk 之前对堆中碎片 chunk 进行合并，以便减少堆中的碎片。
- unsorted bin 与 fast bin 不同，他使用双向链表对 chunk 进行连接
- unsorted 的字面意思就是”不可回收”的意思，可以看作将不可回收的垃圾（不满足能够进行内存分配的堆块）都放到这个”垃圾桶”中。
总结
总之想要通透的理解堆这个概念，还是要多写一点小程序动手调试，多看看网上大牛们的文章。另外可以多逛逛一些想看雪这样的专业论坛，也可以收获到很多东西。
这里只是对自己已经接触过的知识进行一些自我感觉比较通俗易懂的方式进行总结，文章中的错误在所难免，望大牛们能够谅解。
参考文章
https://ctf-wiki.github.io/ctf-wiki/pwn/linux/glibc-heap/heap_implementation_details/#_2