堆入坑指南

Posted on | In

原文借鉴：https://www.anquanke.com/post/id/163971

0x01什么是堆

1
2
3
4
5
6
7
首先先明确一下堆的概念，堆不同于栈，堆是动态分配的（由操作系统内核或者堆管理器），只有在程序中需要时才会分配。在 CTF 的 pwn 程序中，栈是程序加载进内存后就会出现，而堆是由 malloc、alloc、realloc 函数分配内存后才会出现。
windows 和 linux 下的堆分配、管理方式都不同，这里主要讲到的是 CTF 中常出现的 linux 下的堆分配知识
先看看堆在虚拟内存中的位置
堆的生长方向是从低地址向高地址生长的，而栈是从高地址向低地址生长的。
实际上堆可以申请到的内存空间比栈要大很多，在 linux 的 4G 的虚拟内存空间里最高可以达到 2.9 G 的空间

对堆操作的是由堆管理器（ptmalloc2）来实现的，而不是操作系统内核。因为程序每次申请或者释放堆时都需要进行系统调用，系统调用的开销巨大，当频繁进行堆操作时，就会严重影响程序的性能

0x02堆的基本结构

1
2
3
4
5
6
7
8
9
10
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 （用户数据区），在后面的例子中也会讲到这个问题。

0x0364位程序例子

1
2
3
4
5
6
7
8
9
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两个值

0x04指针和地址

1
2
3
4
5
熟练掌握指针的使用在堆的题目分析中还是很有帮助的。下面简单说一下堆分配中的指针会用到了地方。
首先要明确用户在调用 malloc 函数时返回的值为一个指针，指向分配到堆空间（用户数据区），这个在最前面的那个图片也已经标出来了。
有时候题目是以更复杂的情况，用指针来表示某个数据结构的
first chunk（second chunk）表示第一和第二个结构，每个结构中都有一个 point_heap 指针来指向存储用户数据的堆块（chunk）。
左边的这个本身就是一个堆块，用来存放一些全局信息。比如 max_size 存储了能够存储的最大结构数量；exist_num 表示已经存储的结构的数量。

0x05IDA中常见的指针表示形式

1
2
3
4
5
6
7
8
9
10
11
在 IDA 伪代码中的指针形式形如下面的情况：
*(qword_6020A8 + 8)
表示取到 qword_6020A8 这个地址加 8 偏移的那个地址存储的值
汇编代码等同于：
.text:0000000000400F85                 mov     rax, cs:qword_6020A8
.text:0000000000400F8C                 mov     rax, [rax+8]
简单转化一下，也就是：
*(addr) = [addr]
(qword_6020A8 + 16) 就*代表从 qword_6020A8 这个地址出再往后偏移 16 个字节，取到这个地址存储的值，接着把 1 赋值给这个地方（也就是把 1 存入这个地址）
同样的 *(qword_6020A8 + 24) 就代表偏移 24 个字节处的值为 len
依次类推就可以在不连续的内存空间中，把整个 note 的数据结构存储下来了。

0x06 申请堆块的本质

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
堆管理器 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 字段）

0x07 main_arena与top chunk

1
2
3
4
5
6
7
8
9
10
11
12
13
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 分配给他

0x08 free函数和bins

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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并返回。

fast bin 的特性

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 的字面意思就是”不可回收”的意思，可以看作将不可回收的垃圾（不满足能够进行内存分配的堆块）都放到这个”垃圾桶”中。
0%