pwn学习-初识堆

发布于 2021-01-28  1322 次阅读


0x00 概念

堆其实就是程序虚拟地址空间的一块连续的线性区域,它由低地址向高地址方向增长。一般称管理堆的那部分程序为堆管理器。

当程序运行过程中, 动态申请内存时, 并不会直接在内核中申请下来需求的内存, 而是会在第一次申请内存时申请一块很大的内存空间, 这个内存空间中的所有数据,全部用于当程序下一次申请空间时更快的给予内存, 这一大块空间就是堆,由堆管理器来管理。

目前 Linux 标准发行版中使用的堆分配器是 glibc 中的堆分配器:ptmalloc2。ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。

需要注意的是,在内存分配与使用的过程中,Linux 有这样的一个基本内存管理思想,只有当真正访问一个地址的时候,系统才会建立虚拟页面与物理页面的映射关系。 所以虽然操作系统已经给程序分配了很大的一块内存,但是这块内存其实只是虚拟内存。只有当用户使用到相应的内存时,系统才会真正分配物理页面给用户使用。

程序运行时的虚拟内存空间

0x01 结构

malloc_chunk

程序申请下来的内存成为chunk, 在ptmalloc中使用malloc_chunk结构体表示。

无论一个 chunk 的大小如何,处于分配状态还是释放状态,它们都使用一个统一的结构。在 glibc 的malloc.c中,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;
};

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|
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

这里 prev_size 和 size 统称为chunk头。

  • prev_size:如果该 chunk 的物理相邻的前一地址 chunk(两个指针的地址差值为前一 chunk 大小)是空闲的话,那该字段记录的是前一个 chunk 的大小 (包括 chunk 头)。否则,该字段可以用来存储物理相邻的前一个 chunk 的数据。这里的前一 chunk 指的是较低地址的 chunk 。
  • size:该 chunk 的大小,大小必须是 2 * SIZE_SZ 的整数倍。如果申请的内存大小不是 2 * SIZE_SZ 的整数倍,会被转换满足大小的最小的 2 * SIZE_SZ 的倍数。32 位系统中,SIZE_SZ 是 4;64 位系统中,SIZE_SZ 是 8。 此时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 之间的合并。
  • fd,bk。 chunk 处于分配状态时,从 fd 字段开始是用户的数据。chunk 空闲时,会被添加到对应的空闲管理链表中,其字段的含义如下
    • fd 指向下一个(非物理相邻)空闲的 chunk
    • bk 指向上一个(非物理相邻)空闲的 chunk
    • 通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理
  • fd_nextsize, bk_nextsize,也是只有 chunk 空闲的时候才使用,不过其用于较大的 chunk(large chunk)。
    • fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块,不包含 bin 的头指针。
    • bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块,不包含 bin 的头指针。
    • 一般空闲的 large chunk 在 fd 的遍历顺序中,按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。

bins

bin是一种记录free chunk的链表数据结构,用户释放的chunk并不会马上归还系统,ptmalloc会统一管理空闲的chunk, 当用户再次申请,会首先从bins中选择是否存在合适的chunk。

系统针对不同大小的free chunk,将bin分为了4类:
- 1) Fast bin;
- 2) Unsorted bin;
- 3) Small bin;
- 4) Large bin。

然后在每一类bins中都会使用链表来连接其中的chunk。

其中的small bins, large bins, unsorted bins都维护在一个大数组中,而fast bins则独立在外,用于存放一些比较小的chunk。

bins[]数组,用于记录除fastbins之外的所有bins。事实上,一共有126个bins,分别是:

  • bin 1 为unsorted bin;

  • bin 2 到 63 为small bin;

  • bin 64 到 126 为large bin。

malloc_state是管理arena的核心结构,包含堆堆状态信息、bins链表等。

malloc_state的结构如下:

struct malloc_state {
    /* Serialize access.  */
    __libc_lock_define(, mutex);

    /* Flags (formerly in max_fast).  */
    int flags;

    /* Fastbins */
    mfastbinptr fastbinsY[ NFASTBINS ];

    /* Base of the topmost chunk -- not otherwise kept in a bin */
    mchunkptr top;

    /* The remainder from the most recent split of a small request */
    mchunkptr last_remainder;

    /* Normal bins packed as described above */
    mchunkptr bins[ NBINS * 2 - 2 ];

    /* Bitmap of bins */
    unsigned int binmap[ BINMAPSIZE ];

    /* Linked list */
    struct malloc_state *next;

    /* Linked list for free arenas.  Access to this field is serialized
       by free_list_lock in arena.c.  */
    struct malloc_state *next_free;

    /* Number of threads attached to this arena.  0 if the arena is on
       the free list.  Access to this field is serialized by
       free_list_lock in arena.c.  */
    INTERNAL_SIZE_T attached_threads;

    /* Memory allocated from the system in this arena.  */
    INTERNAL_SIZE_T system_mem;
    INTERNAL_SIZE_T max_system_mem;
};

fastbins

fastbinsY[]是一个数组,记录了所有的fastbins。

Fast bins主要是用于提高小内存的分配效率,默认情况下,对于SIZE_SZ为4B的平台,小于64B 的chunk分配请求,对于SIZE_SZ为8B 的平台,小于128B的chunk分配请求,首先会查找fastbins中是否有所需大小的chunk存在(精确匹配),如果存在,就直接返回。

Fast bins可以看着是small bins的一小部分cache,默认情况下, fastbins 只 cache了smallbins 的前7个大小的空闲chunk,也就是说,对于SIZE_SZ为4B的平台, fast bins有7个chunk空闲链表(bin),每个bin的chunk大小依次为16B,24B,32B,40B,48B,56B,64B;对于SIZE_SZ为8B的平台,fast bins有7个chunk空闲链表(bin),每个 bin的chunk 大小依次为32B,48B,64B,80B,96B,112B,128B。

以64为系统为例,分配的内存大小与chunk大小和 fastbins的对应关系如下表所示:

Fastbin Holds chunk size Read chunk size
0 0-0x10 0x20
1 0x11-0x20 0x30
2 0x21-0x30 0x40
3 0x31-0x40 0x50
4 0x41-0x50 0x60
5 0x51-0x60 0x70
6 0x61-0x70 0x80

unsorted bin

unsorted bin 可以视为空闲 chunk 回归其所属 bin 之前的缓冲区。

  • 当一个较大的 chunk 被分割成两半后,如果剩下的部分大于 MINSIZE,就会被放到 unsorted bin 中。

  • 释放一个不属于 fast bin 的 chunk,并且该 chunk 不和 top chunk 紧邻时,该 chunk 会被首先放到 unsorted bin 中。

Small Bin

small bins 中每个 chunk 的大小与其所在的 bin 的 index 的关系为:chunk_size = 2 * SIZE_SZ *index

下标 SIZE_SZ=4(32 位) SIZE_SZ=8(64 位)
2 16 32
3 24 48
4 32 64
5 40 80
x 24x 28x
63 504 1008

small bins 中一共有 62 个循环双向链表,每个链表中存储的 chunk 大小都一致。可以将small bins理解为一个大数组,每个位置对应着每一类大小的chunk的链表。比如对于 32 位系统来说,下标 2 对应着大小为均为 16 字节的chunk的双向链表。每个链表都有链表头结点,这样可以方便对于链表内部结点的管理。此外,small bins 中每个 bin 对应的链表采用 FIFO 的规则,所以同一个链表中先被释放的 chunk 会先被分配出去。

Large Bin

large bins 中一共包括 63 个 bin,每个 bin 中的 chunk 的大小不一致,而是处于一定区间范围内。此外,这 63 个 bin 被分成了 6 组,每组 bin 中的 chunk 大小之间的公差一致,具体如下:

数量 公差
1 32 64B
2 16 512B
3 8 4096B
4 4 32768B
5 2 262144B
6 1 不限制

这里以32位平台为例,第一个large bin 的起始 chunk 大小为 512 字节,位于第一组,所以该 bin 可以存储的 chunk 的大小范围为 [512,512+64),满足关系 chunk_size = 512 + 64 * index

而第二组largebin的起始chunk大小为第一组bin的结束chunk大小,满足关系 chunk_size = 512 + 64 * 32 + 512 * index

0x02 实例

示例源码:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char *a1 = malloc(0x10);
    char *a2 = malloc(0x10);
    char *a3 = malloc(0x10);
    char *a4 = malloc(0x10);

    free(a1);
    free(a2);
    free(a3);
    free(a4);

}

打开gdb调试,在main函数处下断点,运行至第一个malloc函数结束处,使用heap指令:

可以看见已经为程序分配了一块起始地址为0x602000,大小为0x21的空间,注意这里是0x21,而不是我们源码中所写的0x10,这是因为申请得到的空间大小除了用户申请的大小外,还要加上chunk头的大小,也就是0x10,而且此时该chunk的PREV_INUSE位为1,大小就为 0x10 + 0x10 + 0x1 = 0x21

将四个malloc函数全部运行,再次查看程序的heap,四个大小为0x21的chunk依次排列:

接着运行至第一个free函数结束,可以看见第一个chunk已经free掉了,fd指向了0x00,也就是NULL。需要特别注意的是,fastbin 范围的 chunk 的 inuse 始终被置为 1。因此它们不会和其它被释放的 chunk 合并。因此chunk的size仍为0x21。

然后查看fastbins,可以看见0x20处有了第一个值,也就是刚才free掉的chunk的地址

接着将四个free函数运行完,可以看见四个chunk的已经free掉了,然后fd也分别指向了上一个free掉的chunk的地址,fastbins的0x20处就有了刚才free掉的四个chunk的地址。

我们为了印证malloc_chunk结构体中fd所说的指向下一个(非物理相邻)空闲的 chunk,将示例源码修改一下,将free(a2);free(a3);交换一下位置,让a3先于a2被free掉,然后运行至四个free函数结束,查看一下heap和fastbins,可以看到Addr为0x602020的chunk,也就是a2对应的chunk的fd指向了0x602040,也就是a3对应的chunk的地址,而a3对应的chunk的fd指向了0x602000,也就是a0对应的chunk的地址,释放顺序为:a1、a3、a2、a4,于是这里的指向就变为了:a4 —▸ a2 —▸ a3 —▸ a1,fastbins的0x20处的内容也是:0x602060 —▸ 0x602020 —▸ 0x602040 —▸ 0x602000。此时顺序就不是刚才一样物理相邻了,而是变成了与其释放顺序有关。

此时我们将a2申请的空间修改为0x100,然后运行至 free(a2); 处,查看bins,可以发现此时a2的chunk,也就是0x602020地址对应的chunk没有在fastbins中,而是在unsortedbin中。

0x03 参考资料

CTF-wiki

堆简述

pwn-堆学习笔记