heap_1

堆利用

  • Heap allocator管理堆的分配和回收
    • 减少系统调用次数
    • 提高效率
  • 主要结构：chunk，bin，arena
    • 使用bins来管理空闲堆块
    • arena管理分配信息
  • 堆的基本组成是块
1
2
3
4
5
6
7
8
9
10
11
12
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;
};

一般来说，size_t 在 64 位中是 64 位无符号整数，32 位中是 32 位无符号整数。

每个字段的具体的解释如下

  • 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。 该字段的低三个比特位对 chunk 的大小没有影响，它们从高到低分别表示
  • 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 时挨个遍历。

一个已经分配的 chunk 的样子如下。我们称前两个字段称为 chunk header，后面的部分称为user data。每次 malloc 申请得到的内存指针，其实指向user data的起始处。

当一个 chunk 处于使用状态时，它的下一个 chunk 的 prev_size 域无效，所以下一个 chunk 的该部分也可以被当前chunk使用。这就是chunk中的空间复用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 被记录在链表中（可能是循环双向链表，也可能是单向链表）。具体结构如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 处于 free 状态，那么会有两个位置记录其相应的大小

  • 本身的size字段会记录，

  • 它后面的 chunk 会记录。

一般情况下，物理相邻的两个空闲 chunk 会被合并为一个 chunk 。堆管理器会通过 prev_size 字段以及 size 字段合并两个物理相邻的空闲 chunk 块。

bin

bin 通用的宏如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct malloc_chunk *mbinptr;

/* addressing -- note that bin_at(0) does not exist */
#define bin_at(m, i)                                                           \
    (mbinptr)(((char *) &((m)->bins[ ((i) -1) * 2 ])) -                        \
              offsetof(struct malloc_chunk, fd))

/* analog of ++bin */
//获取下一个bin的地址
#define next_bin(b) ((mbinptr)((char *) (b) + (sizeof(mchunkptr) << 1)))

/* Reminders about list directionality within bins */
// 这两个宏可以用来遍历bin
// 获取 bin 的位于链表头的 chunk
#define first(b) ((b)->fd)
// 获取 bin 的位于链表尾的 chunk
#define last(b) ((b)->bk)

fast bin

  • 单向链表

  • 大多数程序经常会申请以及释放一些比较小的内存块。如果将一些较小的 chunk 释放之后发现存在与之相邻的空闲的 chunk 并将它们进行合并，那么当下一次再次申请相应大小的 chunk 时，就需要对 chunk 进行分割，这样就大大降低了堆的利用效率。因为我们把大部分时间花在了合并、分割以及中间检查的过程中。因此，ptmalloc 中专门设计了 fast bin，对应的变量就是 malloc state 中的 fastbinsY

  • 为了更加高效地利用 fast bin，glibc 采用单向链表对其中的每个 bin 进行组织，并且每个 bin 采取 LIFO 策略，最近释放的 chunk 会更早地被分配，所以会更加适合于局部性。也就是说，当用户需要的 chunk 的大小小于 fastbin 的最大大小时， ptmalloc 会首先判断 fastbin 中相应的 bin 中是否有对应大小的空闲块，如果有的话，就会直接从这个 bin 中获取 chunk。如果没有的话，ptmalloc才会做接下来的一系列操作。

  • 默认情况下（32位系统为例）， fastbin 中默认支持最大的 chunk 的数据空间大小为 64 字节。但是其可以支持的chunk的数据空间最大为80字节。除此之外， fastbin 最多可以支持的 bin 的个数为 10 个，从数据空间为8字节开始一直到80字节，定义如下

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#define NFASTBINS (fastbin_index(request2size(MAX_FAST_SIZE)) + 1)

#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST (64 * SIZE_SZ / 4)
#endif

/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE (80 * SIZE_SZ / 4)

/*
   Since the lowest 2 bits in max_fast don't matter in size comparisons,
   they are used as flags.
 */

/*
   FASTCHUNKS_BIT held in max_fast indicates that there are probably
   some fastbin chunks. It is set true on entering a chunk into any
   fastbin, and cleared only in malloc_consolidate.

   The truth value is inverted so that have_fastchunks will be true
   upon startup (since statics are zero-filled), simplifying
   initialization checks.
 */
//判断分配区是否有 fast bin chunk，1表示没有
#define FASTCHUNKS_BIT (1U)

#define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0)
#define clear_fastchunks(M) catomic_or(&(M)->flags, FASTCHUNKS_BIT)
#define set_fastchunks(M) catomic_and(&(M)->flags, ~FASTCHUNKS_BIT)

/*
   NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
   regions.  Otherwise, contiguity is exploited in merging together,
   when possible, results from consecutive MORECORE calls.

   The initial value comes from MORECORE_CONTIGUOUS, but is
   changed dynamically if mmap is ever used as an sbrk substitute.
 */
// MORECODE是否返回连续的内存区域。
// 主分配区中的MORECORE其实为sbr()，默认返回连续虚拟地址空间
// 非主分配区使用mmap()分配大块虚拟内存，然后进行切分来模拟主分配区的行为
// 而默认情况下mmap映射区域是不保证虚拟地址空间连续的，所以非主分配区默认分配非连续虚拟地址空间。
#define NONCONTIGUOUS_BIT (2U)

#define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0)
#define noncontiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) != 0)
#define set_noncontiguous(M) ((M)->flags |= NONCONTIGUOUS_BIT)
#define set_contiguous(M) ((M)->flags &= ~NONCONTIGUOUS_BIT)

/* ARENA_CORRUPTION_BIT is set if a memory corruption was detected on the
   arena.  Such an arena is no longer used to allocate chunks.  Chunks
   allocated in that arena before detecting corruption are not freed.  */

#define ARENA_CORRUPTION_BIT (4U)

#define arena_is_corrupt(A) (((A)->flags & ARENA_CORRUPTION_BIT))
#define set_arena_corrupt(A) ((A)->flags |= ARENA_CORRUPTION_BIT)

/*
   Set value of max_fast.
   Use impossibly small value if 0.
   Precondition: there are no existing fastbin chunks.
   Setting the value clears fastchunk bit but preserves noncontiguous bit.
 */

#define set_max_fast(s)                                                        \
    global_max_fast =                                                          \
        (((s) == 0) ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
#define get_max_fast() global_max_fast

Unsorted bin

  • 管理Unsorted chunk
  • 双向循环链表
  • 只有一个bin， FIFO
  • Unsorted bin中的chunk大小不一样
  • 所有的fast chunk之外的chunk被free时都会先放入unsorted bin

smallbin

  • 管理small chunk
  • 双向链表
  • 共62个bins，FIFO
  • 大小0x20~0x400(64bit)
  • 0x10递增
  • 每个bin中的chunk大小一致

large bin

  • 管理large chunk
  • 双向循环链表
  • 63个bins，FIFO
  • 同一个bin中的chunk大小可以不一样，但是应该在某个范围内
  • 0x400(64bit)
  • 按照从大到小排列

Arena

  • 用于管理bins
  • 由主线程创建的arena，叫做main_arena
  • 由其他线程创建的arena，叫做thread arena
  • arena数量有限
    • For 32 bit systems:
      Number of arena = 2 * number of cores.
    • For 64 bit systems:
      Number of arena = 8 * number of cores.

相关堆漏洞

堆溢出

  • 修改下一个堆块的size，标志位，fd/bk指针等
  • 修改下一堆块的用户数据，比如指针等

use after free

  • 一个内存块被释放后再次使用
  • 释放后指针没有被置为NULL
  • 内存数据没有被清理

Double free

  • UAF的特例
  • free chunk的时候堆块前向，后向合并，将使用unlink

  • FD=P->fd = target addr -12
  • BK=P->bk = expect value
  • FD->bk = BK，即 *(target addr-12+12)=BK=expect value
  • BK->fd = FD，即*(expect value +8) = FD = target addr-12

Off by one

  • 只能溢出一个字节
  • 改写下一块的size
  • 改写下一个块的prev inuse位

gdb调试小技巧

  • p main_arena(查看堆结构)
  • heap arena(查看已经存在的堆)
  • heap Chunks 地址
  • vmmap heap

Fast bin attack

  • 关键:控制fd指针
  • size检查
  • 链表中第一个chunk是否和要free的chunk相同
  • 利用misalignment伪造size=>0x70x7fxxxxxxxxxxxxxx
  • Overwrite GOt
  • Overwrite main_arena(always top chunk ptr)
  • Overwrite realloc_hook/malloc_hook/free_hook(but always infeasible)

Unsorted bin attack

  • 任意地址写固定值
  • 关键点：控制bk指针，bk=addr-0x10(64bit)
  • Malloc一个大小正好的堆块
  • 最终到达效果addr=main_arena+0x58
  • 通常改写global_max_fast
  • bk = addr - 0x10
  • unsorted_chunks(av) -> bk = addr - 0x10
  • bck ->fd = addr - 0x10 +0x10 = unsorted_chunk(av)

Small bin attack

  • 伪造fake chunk，并且让fake chunk的fd指向victim
  • 改写victim的bk为fake chunk
  • 可以把fake chunk放入对应的small bin中的chunk大小不一样
  • 下次malloc就可以分配到fake——chunk处

large bin attack

  • 把large chunk的bk_nextsize指针改写成addr_A
  • 通过malloc把一个比当前chunk(victim)小的块放入large bin中
  • addr_A + 0x20将被改写成vitcim的指针
  • fwd = bck
  • bck = bck -> bk
  • victim -> fd_nextsize = fwd -> fd
  • victim -> bk_nextsize = fwd ->fd -> bk_nextsize
  • fwd -> fd -> bk_nextsize = victim -> bk_nextsize -> fd_nextsize = victim

House of Spirit

  • 本质是fast bin attack
  • fase a fast bin chunk

House of foece

  • Top chunk attack
  • 把top chunk的size改写成一个较大的数 eg：-1
  • mallic特定值 eg:malloc(free_hook-top_chunk - 0x10)
  • malloc任意值，人后就可以分配到free_hook了

House of Lore

  • 本质上是Small bin attack
  • 改写small bin chunk的bk指针，让其指向fake chunk
  • 下次要满足bck -> fd == victim的检查，也就是fake chunk的fd指针要指向被改变的small bin attack

House of Orange

  • 没有free函数
  • 当top chunk不能满足当前分配的需求时，会用brk拓展堆，之前的top chunk就会被放入unsorted bin中
  • 伪造的size必须要对其到内存页
  • size要大于MINSIZE(0x10)
  • size要小于之后申请的chunk size+MINSIZE(0x10)
  • size的prev inuse位必须为1

house of Roman

  • fast bin attack + unsorted bin attack
  • 没有泄漏
  • Partial write to bypass ASLR
文章目录
  1. 1. 堆利用
    1. 1.1. bin
    2. 1.2. fast bin
    3. 1.3. Unsorted bin
    4. 1.4. smallbin
    5. 1.5. large bin
    6. 1.6. Arena
  2. 2. 相关堆漏洞
    1. 2.1. 堆溢出
    2. 2.2. use after free
    3. 2.3. Double free
    4. 2.4. unlink
    5. 2.5. Off by one
    6. 2.6. gdb调试小技巧
    7. 2.7. Fast bin attack
    8. 2.8. Unsorted bin attack
    9. 2.9. Small bin attack
    10. 2.10. large bin attack
    11. 2.11. House of Spirit
    12. 2.12. House of foece
    13. 2.13. House of Lore
    14. 2.14. House of Orange
    15. 2.15. house of Roman
|