点击蓝字  关注我们

日期: 2023-11-20

作者: Mr-hello

介绍: 拖了5年的CTF堆知识学习之路，该篇文章是主要了解堆区相关数据结构。

0x00 前言

从2018年毕业，参加了几次 CTF 比赛，均被 Pwn 类型的题目死死绊住脚步，于是我花了半年时间学习了一下栈知识，倒是可以应对部分简单的栈溢出题目，并且也知道如何修复漏洞，但是在2018年下半年的某次比赛中，又有一个新的问题挡在我面前那就是堆，后来从2018年下半年开始，我一直告诉自己要学习堆知识，翻过这座大山，然而已经过去了五年，每次都变成了上号啊！刷图啊！你真菜啊！

最终的最终还是下定决心去学习这方面的知识，部分内容来自于网上文章如有雷同，请理解，五年啊，这五年你知道我是怎么过的么！现在五年之期已到！

0x01 堆结构

堆和栈都是一种数据结构，在内存中线性分布储存数据，栈由高地址向低地址伸展，堆由低地址向高地址伸展。堆的位置一般都在 bss 段的高地址处。堆不同于栈，堆是动态分配的，只有在程序中需要时才会分配，栈是程序加载进内存后就会出现，而堆是由 malloc、alloc、realloc 等函数分配内存后才会出现。

linux 下，栈的极限大小是8MB，而堆的极限大小，可根据内存大小而定。所以堆可申请大小，比栈大得多。但程序对堆操作的是由堆管理器来实现的，而不是操作系统内核，因此程序每次申请或者释放堆时都需要进行系统调用，当频繁进行堆操作时，就会严重影响程序的性能。

在网上找到了一个64位系统堆(malloc_chunk)结构图，就用下图来讲堆的基本结构吧。

1. prev size：它记录前一个(较低地址的chunk)空闲堆块的大小，注意这里当前一个堆块为空闲状态时才会有值，如果前一个堆块为使用状态则该值始终为0。

2. size ：它记录的是当前堆块的大小，大小必须是 2 * SIZE_SZ 的整数倍。如果申请的内存大小不是 2 * SIZE_SZ 的整数倍，会被转换满足大小的最小的 2 * SIZE_SZ 的倍数。32位系统中，SIZE_SZ 是 4；64 位系统中，SIZE_SZ 是 8，该值是控制信息加上数据体的大小，这个字段的最后三位相当于三个 flag ，有另外的作用。

1. NON_MAIN_ARENA     是否位于主线程
2. IS_MAPPED          是否是由 mmap 分配
3. PREV_INUSE         前一个 chunk 块是否被分配

注意：最后一个 PREV_INUSE 用来记录前一个 chunk 块是否被分配，如果被分配该值为1，所以往往会在已分配的堆块中发现自身 size 值比申请的大1字节。

使用 malloc 函数分配到的内存的返回值指针是指向数据体部分。

举例：

malloc(32) //64位系统

此时申请到的堆块总大小为 32 + 8 + 8 = 48

32字节为用户数据体大小，8字节为 prev size 大小；第二个8字节为 size 大小。但当我们操作输出堆块大小时，往往会得到49这个数值，因为上文提到的 PREV_INUSE 可能为1，所以会看到多1个字节。

在64/32位系统中，存在系统最小分配内存概念，即当你在64位系统中申请小于16字节的堆块时，系统默认会申请 16 + 8 + 8 字节的内存大小，这种情况在32位系统中变为 8 + 4 + 4 字节，也就是说即使自己申请 malloc(0) ，也会得到最小32字节/16字节的堆块大小。

3. user data：用户数据区域，如堆块处于分配状态时，用来存储数据，但是一旦将堆块释放时，会出现以下字段，其中 fd_nextsize、bk_nextsize 会出现在较大的 chunk(large chunk)。

fd：指向下一个空闲的chunk，非物理相邻。
bk：指向上一个空闲的chunk，非物理相邻。
fd_nextsize：指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
bk_nextsize：指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。

注意：前文提到 prev size 是记录前一个空闲堆块大小，当前堆块如果在使用状态时，下一个 chunk 的 prev size 无效，所以当前堆块可以对下一个 chunk 的该部分进行使用，会出现 chunk 中的空间复用。

一般情况下，物理相邻的两个空闲堆块会被合并成为一个大堆块。

0x02 arena

堆管理器主要是通过 malloc/free 函数来分配和释放内存块。现在系统为了方便，在程序第一次申请堆块时，会把很大的内存分配给程序。这样的话就避免了多次内核态与用户态的切换，提高了程序的效率。我们将这一块很大的内存称之为 arena。此外，我们称由主线程申请的内存为 main_arena。后续的申请的内存会一直从这个 arena 中获取，直到空间不足。当 arena 空间不足时，它可以通过增加 brk 的方式来增加堆的空间。类似地，arena 也可以通过减小 brk 来缩小自己的空间。

top chunk

即堆中的第一个堆块，程序之后分配到的内存均要放在其后。当系统当前所有 free chunk(无论何种 bin) ，无法满足用户请求的内存大小时，可将该 chunk 重新“裁剪”分配给用户使用。

0x03 free and bins

free函数

在堆块知识中，除去认识堆结构体，最重要的就是 free 函数，因为在 CTF PWN 堆类型题目溢出点绝大多数会出现在 free 函数处。

在经过 free 函数之后，main_arena 区域中某处会存储一个指向已经 free 了的指针，该指针会指向 free chunk 的头部，而不是 user data。

程序在执行 free 函数后，会做两件事情：

1. 清空当前堆块的 user data

2. 将此堆块的指针存储到 main_arena 中(或者 fast bin 中)

bins

程序释放掉的 chunk 不会立刻归还给系统，堆管理器会进行统一管理空闲 chunk ，这样当用户再次申请内存时，堆管理器可以试图在空闲的堆块中挑选一块合适的交给用户，以此避免频繁的系统调用，减低分配内存所带来的开销。

堆管理器在管理空闲堆块时，会根据释放的堆块大小，分为四类管理：fast bins，small bins，large bins，unsorted bins

bins 主要用于索引不同 bin 的 fd 和 bk，通过数组方式进行存储，其存储规则如下：

1. 第一个为 unsorted bin，即该下标指向的链表中的 free chunk 未进行排序。

2. 索引为2至63的下标中存储 small bin，同一个下标的 small bin 链表中存储的 free chunk 大小相同，两个相邻下标的 small bin 链表中的 free chunk 大小相差两个机器字长，32位系统相差8字节，64位系统相差16字节。

3. small bins 后面的 bin 是large bins 。large bins 中的每一个 bins 数组下标中都包含一定范围大小的 free chunk 链表，其中的 chunk 按 fd 指针的顺序从大到小排列，相同大小的 chunk 同样按照最近使用顺序排列。

注意：并不是所有的 free chunk 被释放后就立即被放到 bins 中。对管理器为了提高分配的速度，会把一些小的 free chunk 先放到 fast bins 的容器内。

fast bin

以32位系统为例，为了快速重新分配回内存而存在的一个结构，其根本和 bins 存储类似，均为数组方式，下标为其内所包含的 free chunk 大小为16字节，24字节，32字节，……，80字节。当用户提出申请一块 <= 64字节的内存时，会首先检查对应大小的 fast bin 中是否包含未被使用的 chunk。如果存在则直接将该 chunk 移除 bin 并将该堆块地址返回给程序；否则通过其他方式(top chunk)得到一块符合大小的 chunk 并返回，fast bin 链表中最多可支持10个 bin，其中下标 0~6 对应存储16字节，24字节，32字节，……，80字节 free chunk 链表，最后三个下标，保留未使用。

64位系统对应32字节，48字节，64字节，……，128字节。

fast bins特性：单向链表，采用 LIFO 策略，fastbin 范围的 chunk 的 inuse 始终被置为 1。因此它们不会和其它被释放的 chunk 合并。

small bin

small bins 中每个 chunk 的大小与其所在的 bin 的 index 的关系为：chunk_size = 2 * 机器字长 *index，具体如下：

small bin特性：循环双向链表，采用 FIFO 策略。

large bin

large bins 中包含63个 bin结构，每个 bin 中的 chunk 大小不一致，处在一定区间范围内。这63个 bin 结构被分为6组，每组 bin 中的 chunk 大小之间的公差一致。

注意：相同大小的large bin使用 fd 和 bk 指针连接，不同大小的 large bin 通过 fd_nextsize 和 bk_nextsize 按大小排序连接。

unsorted bin

unsorted bin 中的空闲 chunk 主要有两方面来源：

1. 一个较大的 chunk 被分割为两部分，剩余部分大于 MINISIZE

2. 释放一个不属于 fast bin 的 chunk，并且该 chunk 不和 top chunk 紧邻

在 unsorted bin 不为空时，用户申请非 fast bin 大小的内存空间时，会优先从 unsorted bin 中查找，如果找到符合该申请的chunk(等于或者大于)，则直接分配或者分割该 chunk。

0x04 总结

以上，堆中的重要结构体了解完毕，但是这只是仅仅知道这些结构体在堆申请/释放时被用来干什么，但具体如何找漏洞点，如何运用，还有很长的路要走。

如侵权请私聊我们删文