PWN

PWN|Heap 堆入门

Posted by Elli0t on 2020-08-03

每个进程可访问的虚拟内存空间为3G,但在程序编译时,不可能也没必要为程序分配这么大的空间,只分配并不大的数据段空间,程序中动态分配的空间就是从这一块分配的。如果这块空间不够,malloc函数族(realloc,calloc等)就调用sbrk函数将数据段的下界移动,sbrk函数在内核的管理下将虚拟地址空间映射到内存,供malloc函数使用。

概念

brk

sbrk 用来改变 “program break” (程序间断点)的位置,这个位置可参考下图:

hello

sbrk(0) gives current program break location

ptmalloc2(支持多线程)

  • 不同的线程维护不同的堆,称为per thread arena
  • 主线程创建的堆称之为main arena
  • Arena 收到 CPU 核数的限制
    • 对于32位:arena 数量上限 = 2 * 核数
    • 对于64位:arena 数量上限 = 8 * 核数

glibc 堆管理的实现

  • arena
    • 指的是堆区域本身,并非结构
    • 主线程的 main arena 通过 sbrk 创建
    • 其他线程的 arena 通过 mmap 创建
  • malloc_state
    • 管理 arena 的核心结构,包含堆的状态信息、bins 链表等
    • main arena 对应的 malloc_state 结构储存在 glibc 的全局变量中
    • 其他线程 arena 对应的 malloc_state 储存在 arena 本身当中
  • bins
    • bins 用来管理空闲内存块,通常使用链表结构来进行组织
  • chunks
    • 内存块的结构

以下介绍的堆管理环境为 glibc 2.26以下(不含2.26),即出现 tcache 之前的堆管理方式,以下央视的环境均是64位程序及操作系统

Arena 头部结构:malloc_state

malloc_state 储存了 Arena 的状态,其中包括了很多用于管理空闲块的 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
struct malloc_state
{
/* Serialize access. */
__libc_lock_define (, mutex);

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

/* Set if the fastbin chunks contain recently inserted free blocks. */
/* Note this is a bool but not all targets support atomics on booleans. */
int have_fastchunks;

/* 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;
};

static struct malloc_state main_arena; /* global variable in libc.so */

Main Arena 概念

image-20200626085358744

空闲内存块(free chunk)结构

image-20200626090349149

在64位平台下,free chunk 的第一个字段 prev_size (8字节)储存了前一个 chunk 的大小

free chunk 的第二个字段记录了当前 chunk 的大小,该字段最低三个 bit 被用作其他含义。

  • P 代表 PREV_INUSE,即代表前一个 chunk 是否被使用。
  • M 代表 IS_MMAPPED,代表当前 chunk 是否是 mmap 出来的。
  • N 代表 NON_MAIN_ARENA,代表改 chunk 是否属于非 Main Arena。

64位系统,堆的大小是以 0x10 的大小递进的,这就是 N、M、P 能够放在低三位而不影响 size 的原因(计算 size 前会将低三位与操作)

第三字段 fd 和第四字段 bk (8字节)前向指针和后向指针,这两个字段用于 bin 链表当中,用来链接大小相同或者相近的 free chunk ,便于后续分配时查找。

分配内存块(allocated chunk)结构

image-20200626160226184

allocated chunk 的前两个字段和 free chunk 相通。

第三个字段开始到最后,chunk 中储存的都是用户数据。甚至下一个 chunk 的第一个字段 prev_size,也可以被用来存放数据,原因是这个 prev_size 字段只有当“前一个” chunk 是 free 的时候才有意义,如果“前一个” chunk 是已经分配的,堆管理器并不关心。

所以对一个 chunk 来说,用户可用大小从偏移 +8 开始(即 size 的位置),一直到下一个 chunk 的 prev_size 字段。

在64位平台下,chunk 的大小一定是 0x10 字节的整数倍。 malloc 返回🔙的指针为图中 mem 指向的位置,即数据开头。

malloc 参数与 chunk 大小的关系

  • malloc 参数为用户申请的内存大小
  • chunk 包含数据和 metadata
  • 返回的 chunk 只要保证其中可用数据大小大于等于用户申请即可
  • 在 x86 32位平台下,chunk 的大小一定是8字节的整数倍;x64 平台下,chunk 的大小一定是16字节是整数倍

Bins 结构

  • Bins 是用来管理和组织空闲内存块的链表结构,根据 chunk 的大小和状态,有许多不同的 Bins 结构

  • Fast bins

    • 用于管理小的 chunk

    • mfastbinptr fastbinsY[NFASTBINS];

  • Bins

    • small bins - 用于管理中等大小的 chunk

    • large bins - 用于管理较大的 chunk

    • unsorted bins - 用于存放未整理的 chunk

    • mchunkptr bins[NBINS * 2 - 2];

Fast bins

image-20200626172529196
  • 大小(chunk 的大小)

    • x86_32:16~64字节
    • x64:32~128字节
  • 相同大小的 chunk 放在一个 bin 中

  • 单向链表

  • 后进先出(First in last out)

  • 相邻的空闲 fast bin chunk 不会被合并

  • 当 chunk 被 free 时,不会清理 PREV_INUSE 标志✅

Small bins

image-20200627081704575
  • chunk 大小 < 1024 bytes (64 位)
  • 相同大小的 chunk 放在一个 bin 中
  • 双向循环♻️链表
  • 先进先出(First in first out)
  • 当有空闲块相邻时,chunk 会被合并成一个更大的 chunk
  • bins[2], bins[3], …, bins[124], bins[125] 共62组 samllbin,大小范围[0x20, 0x3f0](64位)

bins[2]~bins[3] 为一组

Large bins

Large bins 图片和 Small bins 是一样的

  • chunk 大小 >= 1024 bytes (64 位)
  • 每组 bin 表示一组 size 范围而不是具体的 size ,例如 bins[126],bins[127] 的链表中保存长度在 [0x400, 0x440] 的 chunk
  • 双向循环♻️链表
  • 先进先出(First in first out)
  • chunk 按照大小从大到小在一个 bins 里面排序
  • 当有空闲块相邻,chunk 会被合并
  • bins[126], bins[127], …, bins[250], bins[251] 共63组 largebin,大小范围 [0x400, X](64位)

每组 bins 🀄️中的 chunk 大小不一定相同,只是在一个☝️范围内,按由大到小的顺序在链表中排列(是为了更好的检索)。bins[126],bins[127] 的链表中保存长度在 [0x400, 0x440]

Unsorted bin(垃圾桶🚮)

  • 64位平台中:chunk 大小 > 128 字节
  • 只存在唯一一个 unsorted bin
  • 双向循环♻️链表
  • 当一个 chunk (非 fast bin)被 free,它首先被放入 unsorted bin,等后续整理时才会放入对应的 small bin/large bin
  • bins[0], bins[1] 一组

Unsorted bins 与 small bins 事例

image-20200627084418769

其他 chunk

  • Top chunk

    • 不属于任何 bin

    • 在 arena 中处于最高地址

    • 当没有其他空闲块时,top chunk 就会被用于分配

    • 分裂时

      • 一块是请求大小的 chunk

      • 另一块余下 chunk 将成为新的 top chunk

  • Last_remainder

    • 当请求 small chunk 大小的内存时,如发生分裂,则剩余的 chunk 保存为 last_remainder

malloc( ) 的工作流程

  1. 如果 size < max fast,在 fast bins 中寻找 fast chunk,如果找到则结束🔚
  2. 如果 size in_samllbin_range,在 small bins 中寻找 small chunk,如找到则结束🔚
  3. 如果 size not in_smallbin_range,合并所有 fastbin 的 chunk
  4. 循环♻️
    1. 检查 unsorted bin 中的 last_remainder
      1. 如果满足一定的条件,则分裂之,将剩余的 chunk 标记为新的 last_remainder
    2. 在 unsorted bin 中搜索,同时进行整理
      1. 如遇到精确大小,则返回,否则就把当前 chunk 整理到 small/large bin 中去
    3. 在 small bin 和 large bin 中搜索最适合的 chunk (不一定是精确大小)
  5. 使用 top chunk

Free( ) 的工作流程

  1. 如果 size < max fast,放入 fast bin,结束🔚
  2. 如果前一个 chunk 是 free 的
    1. unlink 前面的 chunk
    2. 合并两个 chunk,并放入 unsorted bin
  3. 如果后一个 chunk 是 top chunk ,则将当前 chunk 并入 top chunk
  4. 如果后一个 chunk 是 free 的
    1. unlink 后面的 chunk
    2. 合并两个 chunk ,并放入 unsorted bin
  5. 前后 chunk 都不是 free 的,放入 unsorted bin

free( ) 的去向只有三个:

  1. fast bin
  2. top chunk
  3. unsorted bin

Attack

Fastbin attack

  • Fast bin 利用技术

    • Fast bin 为单向链表,结构简单,容易伪造
    • 为了提高效率,安全检查较少
    • 只针对 Fast bin 大小的 chunk,small/large chunk 不适用
  • 利用思路

    • 空闲 Fast chunk 如果发生溢出被覆盖,则链表指针 fd 可以被修改
    • 可以通过修改链表指针 fd,在Fast bin 链表中引入伪造的空间 Fast chunk
    • 下次分配时分配出伪造的 Fast chunk
    • 伪造的 Fast chunk 可以在 .bss 全局变量处,也可以在栈上

202008031553

利用后造成影响

  • 在栈上伪造 Fast bin
    • 覆盖返回地址
  • 在 bss 上伪造 Fast bin
    • 修改全局变量
  • 在堆上伪造 Fast bin
    • 修改堆上数据