堆初学

前言

前面的两个学期都没有咋认真学，但是在暑假集训中，每天只需要学一件事，就是学习pwn知识，今天是7-15，前面我花了十天左右的时间学习了格式化字符串。但是也没有完全学会，只掌握了那几种方法。非栈上的还是没有掌握完全。先就这样吧，该开堆了，不开堆跟不上进度了。初步学习堆感觉堆的世界很大，有很多的新知识去学。

堆更多的是对指针的利用，不同于栈的思路。

本篇笔记记录堆原理，和堆的相关数据结构，以及ptmalloc2工具

堆概述 - CTF Wiki

堆相关知识

堆概述

什么是堆？

在程序运行过程中，堆可以提供动态分配的内存，允许程序申请大小未知的内存。堆其实就是程序虚拟地址空间的一块连续的线性区域，它由低地址向高地址方向增长。我们一般称管理堆的那部分程序为堆管理器。

引用自《堆概述 - CTF Wiki》

先看堆在虚拟内存中的位置

堆的生长方向是从低地址向高地址生长的，而栈是从高地址向低地址生长的。

**/我对这里有问题/**

我通过查资料，着重看一下这个heap和stack的内存分布

stack从高地址向低地址扩展，这样栈空间的起始位置就能确定下来。动态的调整栈空间大小也不需要移动栈内的数据，如果是从低地址到高地址的扩展，结尾的地址是固定的，

如果要扩大或缩小，则需要移动整个栈的数据。

并且**这样设计可以使得堆和栈能够充分利用空闲的地址空间。**如果栈向上涨的话，我们就必须得指定栈和堆的一个严格分界线，但这个分界线怎么确定呢？平均分？但是有的程序

使用的堆空间比较多，而有的程序使用的栈空间比较多。

所以就可能出现这种情况：一个程序因为栈溢出而崩溃的时候，其实它还有大量闲置的堆空间呢，但是我们却无法使用这些闲置的堆空间。所以呢，最好的办法就是让堆和栈一个向上涨，一个向下涨，

这样它们就可以最大程度地共用这块剩余的地址空间，达到利用率的最大化。

这样我产生了一个问题那为什么IDA x64 中地址为什么是从低到高显示的？

IDA 是静态工具，显示的是指令或数据在文件中的地址映射，按“从小到大”展示；而栈和堆的生长方向是运行时动态行为，和 IDA 的显示顺序无关。

看到的 vs 实际生长方向

区域	IDA中看到的显示顺序	实际运行时生长方向	是否相反？
.text段	地址从低到高显示	不生长，固定	✅ 一致
.data段/.bss段	地址从低到高	不生长，固定	✅ 一致
堆（heap）	IDA 看不到	低地址 ➡️ 高地址	✅ 一致
栈（stack）	IDA 看不到	高地址 ➡️ 低地址	❗相反！
栈帧变量在内存中排列	高地址在上（rsp起点）	随调用逐层往低地址	❗相反！

实际上堆可以申请到的内存空间比栈要大很多，在 linux 的 4G 的虚拟内存空间里最高可以达到 2.9 G 的空间

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

堆的基本结构

先引用一张图片

1.pre size 字段。只有在前面一个堆块是空闲的时候才有值，用来指示前一个堆块的大小。前面一个堆块在使用时，他的值始终为 0
2.size 字段。是用来指示当前堆块的大小的（头部加上 user data 的大小）。但是这个字段的最后三位相当于三个 flag ，有另外的作用。

 这三个作用分别是：

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

这里重点讲解最后一位PREV_INUSE：用来记录前一个 chunk 块是否被分配，被分配的话这个字段的值为 1，所以经常会在已分配的堆块中的 size 字段中发现值比原来大 1 个字节。

所以前一个堆块的释放与否都和这两个字段（pre_size、size）的值有关，这是因为便于内存的释放操作（free）

3.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）。（也就是point_heap指针指向的是user_date这个起始部分）

左边的这个本身就是一个堆块，用来存放一些全局信息。比如 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 个字节（也就是0x6020A8 + 0x10 = 0x6020B8），取到这个地址存储的值，接着把 1 赋值给这个地方（也就是把 1 存入这个地址）

同样的 *(qword_6020A8 + 24) 就代表偏移 24 个字节处的值为 len

依次类推就可以在不连续的内存空间中，把整个 note 的数据结构存储下来了。

具体示例：

// 第一个note (i=0)
*(0x6020A8 + 24 * 0 + 16) = 1;    // 0x6020B8 = 1
*(0x6020A8 + 24 * 0 + 24) = 5;    // 0x6020C0 = 5 (假设长度5)
*(0x6020A8 + 24 * 0 + 32) = 0x403000; // 0x6020C8 = 字符串地址

// 第二个note (i=1)
*(0x6020A8 + 24 * 1 + 16) = 1;    // 0x6020C0 = 1
*(0x6020A8 + 24 * 1 + 24) = 8;    // 0x6020C8 = 8 
*(0x6020A8 + 24 * 1 + 32) = 0x404000; // 0x6020D0 = 字符串地址

那为什么是在不连续的内存空间中呢？

动态内存分配的特性

代码显示这是一个**交互式菜单程序**（`sub_400998`），用户可以选择"New Note"（新建笔记）等操作。

每次用户创建新笔记时（比如选择"New Note"），程序会动态分配一块内存来存储该笔记的内容（字符串）和元数据（状态、长度等）。

动态分配的内存通常不会是连续的

	操作系统或内存管理器会从堆（heap）中分配空闲块，这些块的地址取决于当前内存的使用情况。

	例如：第一个笔记可能在`0x6020A8`，第二个可能在`0x602100`（中间可能有其他程序分配的内存），第三个可能在`0x602150`。

灵活性：

动态分配允许程序在运行时根据用户需求创建任意数量的笔记，而不需要预先分配固定大小的内存。

内存利用率：

如果使用连续内存（如数组），即使某些笔记被删除，剩余空间也无法被其他数据复用（除非实现复杂的内存整理逻辑）。

动态分配可以更高效地利用内存碎片。

操作系统支持：

现代操作系统（如Linux、Windows）的堆管理器会自动处理内存分配和释放，程序员无需关心具体地址。

如果强行使用连续内存（如数组）：

删除笔记后需要移动后续数据，效率低。

预先分配的内存可能浪费（如果用户只创建少量笔记）。

还有一点就是这个note是使用状态标记的，如果我想要删除一个note，我只需要将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的指针。

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

参考资料

CTF pwn 中最通俗易懂的堆入坑指南-安全KER - 安全资讯平台

堆与栈的内存开辟、高地址与低地址_内存高地址和低地址-CSDN博客

这篇文章文章主要是对CTF pwn 中最通俗易懂的堆入坑指南-安全KER - 安全资讯平台本篇文章的进一步理解，如有需要可以看原文