关于堆那些年的那些事

什么是堆

引用CTF-wiki的解释，个人觉得解释的非常好:

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

堆管理器

其次，堆跟栈不同的是，在汇编层面并没有对堆的操作和实现，因此堆可以说是人为写出来的一个管理系统，我们一般称管理堆的那部分程序为堆管理器，比如C语言里面的malloc函数和free函数堆管理器的一部分程序源码。以下是一些不同的堆管理器

dlmalloc  – General purpose allocator
ptmalloc2 – glibc
jemalloc  – FreeBSD and Firefox
tcmalloc  – Google
libumem   – Solaris

除去以上这些以外，还有目前比较主流的musl堆管理器，大多用于IOT的场景，也是需要攻克的一个难题。

堆管理器是干什么的

堆管理器处于用户程序与内核中间，主要做以下工作 1.响应用户的申请内存请求，向操作系统申请内存，然后将其返回给用户程序。同时，为了保持内存管理的高效性，内核一般都会预先分配很大的一块连续的内存，然后让堆管理器通过某种算法管理这块内存。只有当出现了堆空间不足的情况，堆管理器才会再次与操作系统进行交互。 2.管理用户所释放的内存。一般来说，用户释放的内存并不是直接返还给操作系统的，而是由堆管理器进行管理。这些释放的内存可以来响应用户新申请的 内存的请求。

ptmalloc2 – glibc

当前主流pwn题所使用的都是该堆管理器，因此往后我将会分不同版本编写其利用技巧

堆的基本结构体

malloc_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;
};

prev_size：如果这个chunk被释放了则显示物理相邻的上一个chunk的大小 size:显示这个chunk的大小 以上这两个字段我们成为chunk header字段，后面部分则成为user_data字段，每次malloc申请得到的内存指针，其实指向user_data的起始处。 fd 指向下一个（非物理相邻）空闲的 chunk bk 指向上一个（非物理相邻）空闲的 chunk fd_nextsize， bk_nextsize，也是只有 chunk 空闲的时候才使用，不过其用于较大的 chunk 一个正在使用的chunk结构如下图:

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of previous chunk, if unallocated (P clear)  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of chunk, in bytes                     |A|M|P|
  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             User data starts here...                          .
        .                                                               .
        .             (malloc_usable_size() bytes)                      .
next    .                                                               |
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             (size of chunk, but used for application data)    |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of next chunk, in bytes                |A|0|1|
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

一个释放的chunk结构如下图

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of previous chunk, if unallocated (P clear)  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`head:' |             Size of chunk, in bytes                     |A|0|P|
  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Forward pointer to next chunk in list             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Back pointer to previous chunk in list            |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Unused space (may be 0 bytes long)                .
        .                                                               .
 next   .                                                               |
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`foot:' |             Size of chunk, in bytes                           |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of next chunk, in bytes                |A|0|0|
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

chunk结构的一些特殊处理

chunk对齐与堆的对齐

首先关于堆的基地址，其是需要符合内存页对齐的，即最后的三个16进制位为0 chunk的最小大小为prev_size+size+fd+bk，即最小为4SIZE_SZ(size_t),在64位下最小为0x20的大小。 其次每个chunk的大小需要是2SIZE_SZ的整数倍，表现出来的形式就是最后一位16进制位为0，这也能解释为什么下面所说的AMP位对chunk大小没有影响 在源码中其实有不少函数对其是否对齐进行了检查，但这不是我们分析的重点(而且写的有点难看懂QAQ)，因此我们只需要知道它干了什么即可，下面是一个例子更好的理解堆对齐与chunk对齐：

#include <stdio.h>
#include <stdlib.h>
int main()
{
    char* a = malloc(0x18);
    char* b = malloc(0x20);
    char* c = malloc(0x28);
    free(a);
    free(b);
    free(c);
    return 0;
}</stdlib.h></stdio.h>

对于以上这个源码，我们可以用gdb进行调试，只需要观察其堆的基地址和各个chunk的地址和大小即可 可以看到每一个chunk地址的最后一个16进制位为0，堆的基地址后面的三个16进制位为0，对于小于0x20的chunk大小会自动成为0x20，大于或者等于0x20但是小于0x30的chunk大小会自动对齐成为0x30大小的chunk

AMP位

在上面的结构可以看到，size处最低的3bit对size大小不起作用(自动对齐),从而可以用于表示一些信息 NON_MAIN_ARENA，记录当前 chunk 是否不属于主线程，1 表示不属于，0 表示属于。 IS_MAPPED，记录当前 chunk 是否是由 mmap 分配的。 PREV_INUSE，记录前一个 chunk 块是否被分配。一般来说，堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1，以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时，我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。

chunk中的空间复用

当一个 chunk 处于使用状态时，它的下一个 chunk 的 prev_size 域无效，所以下一个 chunk 的该部分也可以被当前 chunk 使用,以下是一个展示的例子

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    char* a = malloc(0x10);
    char* b = malloc(0x10);
    char* c = malloc(0x10);
    strcpy(a, aaaaaaaaaaaaaaaabbbbbbbb); //16a 8b
    free(a);
    free(b);
    free(c);
    return 0;
}

用gdb调试可以看到如下的结果: 可以看到前两行是chunk a的结构，这里为了模拟写到了chunk b的prev_size字段，这里可以发现一个strcpy的特性，会在复制完的结尾加一个\'\x00\',因此覆盖了chunk b的size字段，正常来说的堆题是会限制输入的长度的，但是如果用了这个函数就有一个off by null的漏洞可以使用，这个漏洞的利用在后面也会经常的使用，但是在这个例子中，只是为了理解chunk空间复用是什么样的。

总结

认识chunk结构体是学习堆的第一步，需要彻底理解其结构和各个字段的作用以及特殊处理，才能在后面进行更加深入的学习