Heap Exploitation(笔记)

堆内存

stdlib.h 提供如 malloc、free等标准库函数来管理动态内存

1
2
3
4
5
6
7

char *buffer = (char *)malloc(10);
// malloc(size_t n); 返回指向新分配的至少n个字节的块的指针，如果没有可用空间，则返回null。 此外，失败时，在ANSI-C系统上将errno设置为ENOMEM
strcpy(buffer, "hello");
printf("%s\n", buffer);

free(buffer);
// free(void* p); 释放p指向的内存块，这些内存先前已使用malloc或相关函数（如realloc）分配。如果p为null，则无效

对于malloc(size_t n); 如果n为0，则malloc返回最小大小的块（大多数32位系统位16字节，64位系统上大小为24或32字节） 大多数系统中，size_t 为无符号类型，所以带有负数参数的调用被解释为对大量空间的申请，通常是失败的，因为没有那么大的空间可分配。n的最大支持值因系统而异，但在所有情况下都小于size_t的最大可表示值

glibc堆

1. 与size_t相反，INTERNAL_SIZE_T在程序内部内部使用（默认与size_t等价）。
2. Alignment被定义为2 * (sizeof(size_t))。
3. MORECORE被定义为获取更多内存的函数调用。默认情况下，它被定义为sbrk。

malloc_chunk

malloc_chunk是一个结构体，代表一块特定的内存。已分配和未分配的内存块其属性各有不同

1
2
3
4
5
6
7
8
9
10

struct malloc_chunk {
  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_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;
};
typedef struct malloc_chunk* mchunkptr;

对于已分配的 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)                      .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             (size of chunk, but used for application data)    |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of nextchunk, in bytes                |A|0|1|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

• mchunk_prev_size：在pre_chunk未被使用时表示前一个chunk的size，在pre chunk时，可以作为pre_chunk的user_data的一部分
• mchunk_size：当前chunk的大小，后三位作为标志位使用（AMP）
  • A：A=0 为主分区分配，A=1 为非主分区分配
  • M：M=1表示使用mmap映射区域，M=0为使用heap区域
  • P：P=0 表示pre_chunk空闲，mchunk_prev_size才有效
• mem:从此处开始，就是user data开始的位置，malloc()/calloc() 的返回值，即返回给用户的指针

对于已经释放的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)                .
            .                                                               .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    'foot:' |             Size of chunk, in bytes                           |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of nextchunk, in bytes                |A|0|0|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

malloc_state

malloc_state 结构体表示分区的标题详细信息。主线程的分区是全局变量，并不是堆段的一部分；但是其他线程的 malloc_state 本身存储在堆段中（非主分区可以有多个堆）

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

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;
};
typedef struct malloc_state *mstate;

bins and chunks

bin 表示未分配的 chunk 链表。根据chunk的大小分为四类：

• fast bin
• unsorted bin
• small bin
• large bin

fast bin 的维护：

1
2

typedef struct malloc_chunk *mfastbinptr;
mfastbinptr fastbinsY[]; // Array of pointers to chunks

其他bin的维护：

1
2

typedef struct malloc_chunk* mchunkptr;
mchunkptr bins[]; // Array of pointers to chunks

每个bin由bin数组中的两个值表示。第一个是指向 HEAD 的指针，第二个是指向bin列表的 TAIL 的指针。在fast bin（单链表）中，第二个值是NULL

fast bin

默认为10个 fast bin，即 fastbinsY的长度为10。 bin中的每一个元素维护一个链表，添加、删除chunk遵循LIFO（先进后出）即操作都是在链表的第一个chunk

每个 bin 的链表中chunk大小相同， 10 个bin的链表中chunk大小以8字节递增：16,24,32,40,48,56,64,72,80,88（大小包括元数据）
只有chunk的prev_size 和 size 字段才能保存已分配chunk的元数据，下一个连续chunk的prev_size 可以用来保护用户数据。此外，两个连续的被释放的 fast bin 会合并成一块

unsorted bin

只有一个 unsorted bin，用于充当缓冲层以加速内存分配和释放请求。 释放 small bin和large bin 时会放到 unsorted bin中

small bin

bins[1~62] 为 small bin。 它比large bin 快，比 fast bin 慢；每个元素维护一个双链表。 遵循FIFO（先进先出）即插入在 HEAD，删除在 TAIL
每个 small bin 的链表中chunk 大小相同以8字节递增，依次为：16,24,...,254
释放时，将小chunks合并然后在unsorted中结束

large bin

bins[63:]为large bin 共63个,每个元素维护一个双链表，但是large bin 的链表中chunk大小不同，按递减顺序排序（HEAD处的chunk最大）。因此在添加、删除chunk时可以发生在链表的任何位置
large bin 的大小以64字节步长为间隔，依次为：512~75,576~632,...
像small bins一样，在释放时，large bins可以合并在一起，然后在unsorted bin中结束。

top chunk

top chunk 不属于任何 bin，是与分区顶部接壤的chunk。处理malloc请求时，被用作最后的处理chunk，即如果还需要更大的大小，可以通过sbrk系统调用来增加大小。此外，top chunk 的 prev_inuse 标志位总是被设置的

last remainder chunk

从最后依次拆分中得到的chunk。当没有确切大小的chunk时，更大的chunk会被分成两部分，一部分返回给用户，另一部分变成 last remainder chunk

内部函数

arena_get(ar_ptr,size)

获取分区并锁定相应的互斥锁。 ar_ptr 设置为指向相应的分区，szie 只是暗示立即将需要多少内存

sysmalloc[TODO]

sysmalloc处理需要更多系统内存的malloc情况。在条目中，假设av->top没有足够的空间来实现 nb 字节的请求，因此要求av->top被扩展或替换。

void alloc_perturb(char* p,size_t n)

如果perturb_byte（malloc使用的可调参数M_PERTURB）非零（默认情况下为0），则将p指向的n字节设置为等于perturb_byte^ 0xff。

void free_perturb(char* p,size_t n)

如果perturb_byte（malloc使用的可调参数M_PERTURB）非零（默认情况下为0），则将将p指向的n字节设置为等于perturb_byte。

void malloc_init_state(mstate av)

1. 对于非fast bin，为每个bin创建空的循环链表。
2. 设置FASTCHUNKS_BIT标志av。
3. 初始化av->top为第一个未排序的chunk。

unlink(AV,P,BK,FD)

操作物理上的相邻chunk

宏定义，用作从 bin 中删除一个 chunk

1. 检查块大小是否等于下一个块中先前设置的大小。否则，抛出错误（“corrupted size vs prev_size”）。
2. 检查是否P->fd->bk == P和P->bk->fd == P。否则，抛出错误（“损坏的双链表”）。
3. 调整相邻块的前向和后向指针（列表中）以便于删除：
4. 设置P->fd->bk= P->bk。
5. 设置P->bk->fd= P->fd。

void malloc_consolidate(mstate av)

free() 的专用版本

• 检查 global_max_fast是否为0（av未初始化）。如果为0，则malloc_init_state使用av作为参数调用并返回。

• 如果global_max_fast不为零，则清除FASTCHUNKS_BIT以使用 av。

• 从第一个到最后一个索引迭代fast bin数组：

  • 获取当前fastbin块的锁，如果它不为NULL则继续。
  • 如果上一个chunk（通过内存）未被使用，调用unlink处理上一个块。
  • 如果下一个chunk（通过内存）不是top chunk：
    • 如果下一个chunk未被使用，调用unlink处理下一个块。
    • 如果前一个chunk及下一个chunk有已被释放的chunk就将chunk与它们（通过内存）合并，然后将合并的chunk添加到unsorted bin的头部。
  • 如果下一个chunk（通过内存）是top chunk，则将chunk适当地合并到单个top chunk中。

对于一个chunk是否被使用的检查是使用PREV_IN_USE标志完成的。因此，其他fastbin块在此处不会被识别为空闲

核心函数

void * _int_malloc(mstate av，size_t bytes)

1. 更新bytes以校准等
2. 检查av是否为NULL。
3. 在没有可用分区的情况下（当av为NULL时），将调用sysmalloc以期用mmap调用获取块。如果成功，将调用alloc_perturb，之后返回指针。
4. 如果要申请的大小落在fast bin范围内：
5. 1 获取fast bin数组的索引，以根据请求大小访问适当的bin。
6. 2 删除该bin中的第一个chunk并将victim指向它。
7. 3 如果victim为NULL，则转到下一个情况（small bin）。
8. 4 如果victim不为NULL，请检查chunk的大小以确保它属于该特定的bin。否则会抛出错误（“malloc(): memory corruption (fast)”）。
9. 5 调用alloc_perturb然后返回指针。
10. 如果大小落在small bin范围内：
11. 1 获取small bin数组的索引，以根据请求大小访问适当的bin。
12. 2 如果此bin中没有chunk，请继续执行下一个情况（通过比较指针bin和bin->bk来检查）
13. 3 victim等于bin->bk（bin中的最后一个chunk）。如果它为NULL（在此期间发生initialization），调用malloc_consolidate并跳过检查不同bin的完整步骤。
14. 4 否则，当victim非NULL，检查victim->bk->fd和victim是否相等。如果它们不相等，则抛出错误（“malloc(): smallbin double linked list corrupted”）。
15. 4 为victim下一个chunk（在内存中，而不是在双向链表中）设置REV_INSUSE位。
16. 6 从bin列表中删除此chunk。
17. 7 根据av需要为此chunk设置适当的分区位。
18. 8 调用alloc_perturb然后返回指针。
19. 如果大小不属于small bin范围：
20. 1 获取large bin数组的索引，以根据请求大小访问适当的bin。
21. 2 看看av是否有fast chunks。这是通过检查av->flags中的FASTCHUNKS_BIT完成的。如果是这样，调用av上的malloc_consolidate。
22. 如果尚未返回指针，则表示以下一种或多种情况：
23. 1 大小属于fast bin范围但没有fast chunk可用。
24. 2 大小属于small bin范围，但没有small chunk可用（初始化期间调用malloc_consolidate）。
25. 3 大小属于large bin范围。
26. 检查unsorted chunks并遍历chunks将其放入bin中。这是chunks放入bin的唯一地方。从’TAIL’中迭代unsorted bin。
27. 1 victim 指向当前正在处理的chunk。
28. 2 检查victim的chunk大小是否在最小（2*SIZE_SZ）和最大（av->system_mem）范围内。否则抛出错误（”malloc(): memory corruption”）。
29. 3 如果请求的chunk的大小落在small bin范围内且victim是最后一个剩余chunk且它是unsorted bin中的唯一chunk且chunk大小>=请求的chunk大小则将该chunk分为2个chunk：
30. 3.1 第一个chunk匹配请求的大小并返回。
31. 3.2 剩下的chunk成为新的最后剩余chunk。它被插回到unsorted bin中。
32. 3.2.1 设置两个chunk的chunk_size和chunk_prev_size使之适当。
33. 3.2.2 调用alloc_perturb后返回第一个chunk。
34. 4 如果上述条件为假，则控制到达此处。从unsorted bin中取出victim。如果victim的大小与请求的大小完全匹配，请在调用alloc_perturb后返回此chunk。
35. 5 如果victim大小落在small bin范围内，将chunk添加到相应small bin的HEAD中。
36. 6 否则插入适当的large bin，同时保持排序顺序：
37. 6.1 首先检查最后一个chunk（最小）。如果victim的大小小于最后一个chunk，则将其插入到最后一个chunk。
38. 6.2 否则，循环查找大小> = victim大小的chunk。如果尺寸完全相同，则始终插入第二个位置。
39. 7 重复此整个步骤最多MAX_ITERS（10000）次或直到unsorted bin中的所有chunk都耗尽。
40. 检查unsorted bins后，检查请求的大小是否在small bins范围内，如果不在，则检查large bins。
41. 1 获取large bin数组的索引，以根据请求大小访问适当的bin。
42. 2 如果最大chunk（bin中的第一个chunk）的大小大于请求的大小：
43. 2.1 从’TAIL’迭代以找到一个chunk(victim)最小尺寸>=所请求大小的块。
44. 2.2 调用unlink从bin中删除victim chunk。
45. 2.3 计算victim的chunk的remainder_size（victim的chunk大小-请求的大小）。
46. 2.4 如果remainder_size> = MINSIZE（包括headers的最小chunk大小），则将chunk拆分为两个chunk。否则，将返回整个victim块。将剩余chunk插入unsorted bin中（’TAIL’端）。检查是否在unsorted bin中存在unsorted_chunks(av)->fd->bk == unsorted_chunks(av)。否则会抛出错误(“malloc(): corrupted unsorted chunks”)。
47. 2.5 调用alloc_perturb后返回victim chunk 。
48. 到目前为止，已经检查了unsorted bins以及相应的fast bins，small bins或large bins。使用所请求chunk 的确切大小来检查单个bin（fast bins或small bins）。重复以下步骤，直到所有bin都用完为止：
49. 1 bin数组的索引递增以检查下一个bin。
50. 2 使用av->binmap的map跳过空的bin。
51. 3 victim 指向当前bin的’TAIL’。
52. 4 使用binmap确保如果跳过bin（在上面的第2步中），它肯定是空的。但是，binmap不能确保跳过了所有空bin。检查victim是否为空。如果为空，则再次跳过bin并重复上述过程（或’继续’此循环）直到我们到达非空bin。
53. 5 将chunk（victim指向非空bin的最后一个chunk）拆分为两个chunk。将剩余chunk插入unsorted bin（’TAIL’端）。在unsorted bins中进行检查unsorted_chunks(av)->fd->bk == unsorted_chunks(av)是否成立。若不成立会抛出错误（“malloc(): corrupted unsorted chunks 2”）。
54. 6 调用alloc_perturb后返回victim chunk 。
55. 如果仍未找到空bin，则将使用top chunk来为请求提供服务：
56. 1 victim指向av->top。
57. 2 如果top chunk>=request size+MINSIZE的大小，则将其拆分为两个chunk。在这种情况下，剩余chunk成为新的top chunk，另一个chunk在调用alloc_perturb后返回给用户。
58. 3 看看是否av有fast chunks。这个操作通过检查完成FASTCHUNKS_BIT中的av->flags来完成。如果是有，调用av上的malloc_consolidate。返回步骤6（我们检查unsorted bins）。
59. 4 如果av没有fast chunks，则调用sysmalloc并返回调用alloc_perturb后获得的指针。

__libc_malloc(size_t bytes)

1. 调用arena_get获取mstate指针。
2. 使用分区指针和大小调用_int_malloc。
3. 解锁分区。
4. 在将指针返回到chunk之前，应满足以下条件之一：
5. 1 返回的指针为NULL
6. 2 Chunk是MMAPPED
7. 3 Chunk的分区与1中的分区相同。

_int_free(mstate av, mchunkptr p, int have)_lock)

1. 检查在内存中p是否在p + chunksize(p)之前（以避免wrapping）。否则会抛出错误（“free(): invalid pointer”）。
2. 检查chunk是否至少是MINSIZE的大小或是MALLOC_ALIGNMENT的倍数。否则会抛出错误（”free(): invalid size”）。
3. 如果chunk的大小属于fast bin列表：
4. 1 检查下一个chunk的大小是否在最小大小和最大大小（av->system_mem）之间，否则抛出错误（”free(): invalid next size (fast)”）。
5. 2 调用free_perturb处理chunk。
6. 3 为av设置FASTCHUNKS_BIT。
7. 4 根据chunk大小获取fast bin数组的索引。
8. 5 检查bin的顶部是否不是我们要添加的chunk。否则，抛出一个错误（“double free or corruption (fasttop)”）。
9. 6 检查顶部的fast bin chunk的大小是否与添加的chunk相同。否则，抛出一个错误（“invalid fastbin entry (free)”）。
10. 7 将chunk插入fast bin列表的顶部并返回。
11. 如果chunk没有mmapped：
12. 1 检查chunk是否是top chunk。如果是，则抛出错误（”double free or corruption (top)””）。
13. 2 检查下一个chunk（通过内存）是否在分区的边界内。如果不是，则抛出错误（“double free or corruption (out)”）。
14. 3 检查是否标记了下一个chunk的previous使用位（按内存）。如果没有，则抛出错误（“double free or corruption (!prev)”）。
15. 4 检查下一个chunk的大小是否在最小和最大大小（av->system_mem）之间。如果不是，则抛出错误（”free(): invalid next size (normal)”）。
16. 5 调用free_perturb处理chunk。
17. 6 如果未使用上一个chunk（按内存），调用unlink处理上一个块。
18. 7 如果下一个chunk（通过内存）不是top chunk：
19. 7.1 如果未使用下一个chunk，调用unlink处理下一个块。
20. 7.2 将chunk与前一个chunk，下一个chunk（通过内存）合并，如果有被释放的chunk，将其插入到unsorted bins的头部。插入前，请检查是否存在unsorted_chunks(av)->fd->bk == unsorted_chunks(av)。如果没有，则抛出错误（“free(): corrupted unsorted chunks”）。
21. 8 如果下一个chunk（通过内存）是top chunk，则将chunk适当地合并到单个top chunk中。
22. 如果chunk是mmapped，调用munmap_chunk。

__libc_fress(void* mem)

1. 如果 mem为NULL,直接返回。
2. 如果相应的chunk是mmapped，请在brk/mmap阈值需要动态调整时调用munmap_chunk。
3. 获取相应chunk的分区指针。
4. 调用_int_free。

安全检查

‘P’ 表示未链接的块
‘p’ 表示被释放的块

Heap Exploitation

攻击摘要

• ← Previous Post
• Next Post →