libcpwn基础知识-入门

写了自己也不怎么会看并且看一遍忘一遍系列

微观结构

1. 数据结构概念

  1. malloc_chunk: 即Chunk Header,一个heap被分为多个chunk,至于每个chunk的大小,这是根据用户的请求决定的,也就是说用户调用malloc(size)传递的size参数”就是”chunk的大小。每个chunk都由一个结构体malloc_chunk表示。
  2. bin: 将free chunk分类连接的链表,同一个链表中各个chunk的大小相等(有一个特例,详情见后文)

2. 数据结构详解

1. Chunk
  • 分类:

    • allocated chunk
    • free chunk
    • top chunk
    • last remainder chunk
  • allocated & free chunk

chunk,堆内存管理的最小单位。chunk大小为8的整数倍,因此chunksize后的3个bit位不能空着,用于设置一些flag。这里一步到位记录阿里聚安全文中讲的最新的chunk,第0bit记录前一个bit是否free(通过是否free判断当前chunk之前的4个字节是pre_chunk_footer还是pre_chunk_padding,当前chunk是否free通过下一个chunk的前4字节获得即可,这里很巧妙),第1bit记录当前chunk是否是通过mmap系统调用产生的,第2bit记录当前chunk是否是thread arena(1为属于)。

footer的作用是:当free的chunk的前一个chunk为空时,在free时可以确定前一个free chunk的起始地址从而合并两个chunk

再进一步,发现footer的作用并不大,但是如果前一个chunk是free的话,在合并的时候我们又需要知道前一个chunk的大小,怎么办?将footer从尾部移到首部,同时footer改为保存前一个free chunk的size,如果前一个chunk是allocated chunk,则footer变为前一个chunk的payload或padding的一部分。下图很清楚:

  • top chunk

当一个chunk处于一个arena的最顶部(即最高内存地址处)的时候,就称之为top chunk。该chunk并不属于任何bin,而是在系统当前的所有free chunk(无论那种bin)都无法满足用户请求的内存大小的时候,将此chunk当做一个应急消防员,分配给用户使用。如果top chunk的大小比用户请求的大小要大的话,就将该top chunk分作两部分:1)用户请求的chunk;2)剩余的部分成为新的top chunk。否则,就需要扩展heap或分配新的heap了——在main arena中通过sbrk扩展heap,而在thread arena中通过mmap分配新的heap。

程序第一次进行 malloc 的时候,heap 会被分为两块,一块给用户,剩下的那块就是 top chunk。
这里需要注意,首先main arena通过sbrk扩展heap,thread arena通过mmap。其次通过看malloc_state能看出其中的mchunkptr top指针直接指向top chunk。当top chunk不够时,就需要sbrk扩展或者mmap分配新heap,这也就解释了为什了上边thread arena中可以有多个heap segment,而main arena只有一个。

  • Last Remainder Chunk

    TODO

2. bins
  • 分类:

    • Fast bin
    • Unsorted bin
    • Small bin
    • Large bin
  • bin之间的关系
    fastbinsY是一个用于记录所有的fast bins的数组,bins是一个用于记录除fast bins之外的所有bins的数组。在malloc_state中的定义如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    struct malloc_state
    {
    ……
    /* Fastbins */
    mfastbinptr fastbinsY[NFASTBINS];
    ……
    /* Normal bins packed as described above */
    mchunkptr bins[NBINS * 2 - 2]; // #define NBINS 128
    ……
    };
    // mfastbinptr和mchunkptr都是malloc_chunk的指针,

bins就是由空闲chunk组成的数组, 每一个bin都是双向链表. bin存放是整理过的chunks, 并且bin中合并过的空闲chunk是不存在相邻的, 所以bin中的每一个 chunk都是可以被使用, 并且都是紧挨着正在使用的chunk内存末尾。bins中的chunk是按照大小排序的,采用FIFO, 从头部插入节点, 尾部取节点。这样有个特点就是更容易内存的合并。虽然定义了NBINS=128,但是bins[0]和bins[127]其实是不存在的,bins[1]为unsorted bin,然后有62个smallbin和63个largebin。

  • Fast bin要点

    1. 64位下,fast bin的chunk size(+0x10)为0x20-0x80,一共个7个。malloc小于0x10时申请0x10

    2. 每个fast bin都是一个单链表(只使用fd指针),在fast bin中无论是添加还是移除fast chunk,都是对链表尾进行操作,而不会对某个中间的fast chunk进行操作(LIFO)。需要注意的是,为了实现LIFO,fastbinsY数组中每个fastbin元素均指向了该链表的rear end(尾结点),而尾结点通过其fd指针指向前一个结点,依次类推。

    3. 不会对free chunk进行合并操作。鉴于设计fast bin的初衷就是进行快速的小内存分配和释放,因此系统将属于fast bin的chunk的P(未使用标志位)总是设置为1,这样即使当fast bin中有某个chunk同一个free chunk相邻的时候,系统也不会进行自动合并操作,而是保留两者。虽然这样做可能会造成额外的碎片化问题,但瑕不掩瑜。

    4. malloc:64位下用户请求小于0x80时。在初始化的时候fast bin支持的最大内存大小以及所有fast bin链表都是空的,所以当最开始使用malloc申请内存的时候,即使申请的内存大小属于fast chunk的内存大小(即0x20到0x80字节),它也不会交由fast bin来处理,而是向下传递交由small bin来处理,如果small bin也为空的话就交给unsorted bin处理。初始化过程见https://paper.seebug.org/255/#95int95free

    5. free:fast chunk的P位始终被置为1。因此它们不会和其它被释放的chunk合并。但是当释放的chunk与该chunk相邻的空闲 chunk合并后的大小大于FASTBIN_CONSOLIDATION_THRESHOLD时,内存碎片可能比较多了,我们就需要把 fast bins中的chunk都进行合并,以减少内存碎片对系统的影响

  • Small bin要点

    1. smallbins是用来管理较小空间的bins,其中每个bins里面的chunk大小都是相同的,一共包含62个bin,具体大小依据系统是32位还是64位,
      32位:16B,24B,32B…,504B => 62bins,
      64位:32B,48B,64B…,1008B => 62bins
      这样当应用需要多大的空间,直接从smallbins里面申请就可以了。

      这里其实有疑问,small bin和fast bin的大小有重合。解答是:见ctf-wiki // TODO

    2. malloc:和fast bin类似,最初small bin都是空的。malloc small bin大小时,从small bin中申请,失败(第一次肯定失败)则从unsorted bin中申请,unsorted bin也不行则遍历后续的所有bins,找出第一个满足要求的bin,如果所有的bin都不满足,就使用top chunk,如果top chunk大不够,就扩充top chunk,这样就一定ok了。

    3. free:当释放small chunk的时候,先检查该chunk地址相邻的chunk是否为free,如果是的话就进行合并操作,将这些chunk合并成新的chunk,并将新的chunk添加到unsorted bin中

  • Large bin

    1. 512+字节大小从这里找
    2. malloc:初始化完成之前的操作类似于small bin,这里主要讨论large bins初始化完成之后的操作。首先确定用户请求的大小属于哪一个large bin,然后判断该large bin中最大的chunk的size是否大于用户请求的size(只需要对比链表中front end的size即可)。如果大于,就从rear end开始遍历该large bin,找到第一个size相等或接近的chunk,若相等,则分配给用户;若chunk大于用户请求的size,则将该chunk拆分为两个chunk:返回用户请求的size的chunk;将剩余的部分做为一个新的chunk加入unsorted bin。如果小于,则向更大size的large bin中请求chunk,若还是找不到,则查找top chunk。
  • Unsorted bin(这里主要记录unsorted bin的使用场景)
    • 开始时fastbin和smallbin未初始化,则会直接到unsorted bin中找。
    • free small chunk的时候,如果有相邻的free chunk,则合并放到unsorted bin中。
    • malloc large bin的时候,如果找到的chunk大小大于用户申请的size,则将chunk拆分为两个chunk,一个满足size的分给用户,剩下的加入unsorted bin中。
    • free large chunk时,用到的场景和small bin相同。
    • malloc small chunk举例,先去small bin中找,找不到合适的就去unsorted bin中找,找不到合适的则将unsorted bin清空(这也是何时忘small和large bin中插入值),将其中的各个bin按大小插入对应bins中,然后去top chunk拿到需要的chunk。

要点总结:ctf-wiki中有一段写的很棒:
任何堆的实现都需要从以下两个角度考虑相应的问题

  • 宏观角度
    • 创建堆
    • 堆初始化
    • 删除堆
  • 微观角度
    • 申请内存块
    • 释放内存块

因此这里copy一下malloc和free的整体流程:
// TODO
free: 这里注意,free只是链入bin中,并未将内容设置为空,因此下次malloc的空间直接使用时就可能uaf

3. 数据结构内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct malloc_chunk { // Chunk Header
/* #define INTERNAL_SIZE_T size_t */
INTERNAL_SIZE_T prev_size; /* 如果前一个物理相邻的chunk空闲,则记录它的size */
INTERNAL_SIZE_T size; /* 当前chunk(包括该Chunk Header)的大小 */
/*
chunk 处于分配状态时,从 fd 字段开始是用户的数据。
chunk 空闲时,会被添加到对应的空闲管理链表中,其字段的含义如下:
fd 指向下一个(非物理相邻)空闲的 chunk
bk 指向上一个(非物理相邻)空闲的 chunk
通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理
*/
struct malloc_chunk* fd;
struct malloc_chunk* bk;
/*
只有 chunk 空闲的时候才使用,不过其用于较大的 chunk(large chunk)。
fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块,不包含 bin 的头指针。
bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块,不包含 bin 的头指针。
一般空闲的 large chunk 在 fd 的遍历顺序中,按照由大到小的顺序排列。这样做可以避免在寻找合适chunk时挨个遍历。 // TODO
*/
struct malloc_chunk* fd_nextsize;
struct malloc_chunk* bk_nextsize;
};

具体的已分配&未分配的malloc_chunk的结构参考ctf-wiki,这里不搬运了。

宏观结构

1. 数据结构概念

  1. heap_info: 即Heap Header。malloc后,main会直接给分132k大小的堆,叫main arena,线程create后malloc的时候给一个thread arena。因为一个thread arena(注意:不包含main thread)可以包含多个heaps,所以为了便于管理,就给每个heap分配一个heap header。那么在什么情况下一个thread arena会包含多个heaps呢?在当前heap不够用的时候,malloc会通过系统调用mmap申请新的堆空间,新的堆空间会被添加到当前thread arena中,便于管理。
  2. malloc_state: 即Arena Header,每个thread只含有一个Arena Header。Arena Header包含bins的信息、top chunk以及最后一个remainder chunk等。

NOTE:

  1.Main thread不含有多个heaps所以也就不含有heap_info结构体。当需要更多堆空间的时候,就通过扩展sbrk的heap segment来获取更多的空间,直到它碰到内存mapping区域为止。
  2.不同于thread arena,main arena的arena header并不是sbrk heap segment的一部分,而是一个全局变量!因此它属于libc.so的data segment。

上图为只含一个heap segment的main arena与thread arena, 如node描述的,main arena的malloc_state在libc.so的数据段中,并不是堆段的一部分。

​ 从上图可以看出,thread arena只含有一个malloc_state(即arena header),却有两个heap_info(即heap header)。由于两个heap segments是通过mmap分配的内存,两者在内存布局上并不相邻而是分属于不同的内存区间,所以为了便于管理,libc malloc将第二个heap_info结构体的prev成员指向了第一个heap_info结构体的起始位置(即ar_ptr成员),而第一个heap_info结构体的ar_ptr成员指向了malloc_state,这样就构成了一个单链表,方便后续管理。

2. 数据结构详解

实验

fastbin实验

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <malloc.h>

int main() {
char * heapa;
char * heapb;
char * heapc;

heapa = malloc(0x20);
heapb = malloc(0x20);
heapc = malloc(0x20);

free(a);
free(b);
free(c);
}

malloc三次后的内存:

这里是64位,所以chunk header是0x10,可以看出,size+p位为0x31,出去p的1后,size正好是0x10+0x20。malloc三次后,可以看出申请了三个chunk,大小满足fastbin。下边的0x20f71为top chunk大小,每次malloc后都会减少0x30。

free一次后的内存:

free一次后,因为fastbin是空的,所以第一个free的bin当作头,所以没有fd啥的,内存不变

free两次后的内存:
-w675

清楚的看到,heapb的fd指向了a。要记住的是,malloc的3个0x20的chunk没啥链表啥的联系,只有free之后,加到fastbin里,才有联系。a为fastbin的链表头,新free的bin采用尾插,因此当释放c时,c的fd就指向了b。注意此时topchunk不变,fastbin的p位依然置1,并不回收内存。

数据结构代码(参考)

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
struct malloc_chunk { // Chunk Header
/* #define INTERNAL_SIZE_T size_t */
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. 这两个指针只在free chunk中存在*/
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 _heap_info // Heap Header
{
mstate ar_ptr; /* Arena for this heap. */
struct _heap_info *prev; /* Previous heap. */
size_t size; /* Current size in bytes. */
size_t mprotect_size; /* Size in bytes that has been mprotected
PROT_READ|PROT_WRITE. */
/* Make sure the following data is properly aligned, particularly
that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
MALLOC_ALIGNMENT. */
char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

struct malloc_state // Arena Header
{
/* Serialize access. */
mutex_t 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. */
struct malloc_state *next_free;
/* Memory allocated from the system in this arena. */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};


参考
https://paper.seebug.org/255/#95int95malloc

Proudly powered by Hexo and Theme by Hacker
© 2021 LFY