HackPluto's Blog

PWN-堆溢出

字数统计: 3.4k阅读时长: 13 min
2019/10/09 Share

堆的详解

https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/comment-page-1/

什么是堆

堆是分配给每个程序的内存区域。与堆栈不同,堆内存可以动态分配。这意味着程序可以在需要时从堆段中“请求”和“释放”内存。同样,该存储器是全局的,即可以从程序中的任何位置访问和修改该存储器,并且不局限于分配它的功能。这是通过使用“指针”引用动态分配的内存来实现的,与使用局部变量(在堆栈上)相比,这反过来导致性能略有下降。我们一般称管理堆的那部分程序为堆管理器。堆管理器处于用户程序与内核中间,主要做以下工作
1.响应用户的申请内存请求,向操作系统申请内存,然后将其返回给用户程序。同时,为了保持内存管理的高效性,内核一般都会预先分配很大的一块连续的内存,然后让堆管理器通过某种算法管理这块内存。只有当出现了堆空间不足的情况,堆管理器才会再次与操作系统进行交互。
2.管理用户所释放的内存。一般来说,用户释放的内存并不是直接返还给操作系统的,而是由堆管理器进行管理。这些释放的内存可以来响应用户新申请的内存的请求。
Linux 中早期的堆分配与回收由 Doug Lea 实现,但它在并行处理多个线程时,会共享进程的堆内存空间。因此,为了安全性,一个线程使用堆时,会进行加锁。然而,与此同时,加锁会导致其它线程无法使用堆,降低了内存分配和回收的高效性。同时,如果在多线程使用时,没能正确控制,也可能影响内存分配和回收的正确性。Wolfram Gloger 在 Doug Lea 的基础上进行改进使其可以支持多线程,这个堆分配器就是 ptmalloc 。在 glibc-2.3.x. 之后,glibc 中集成了 ptmalloc2。

使用动态内存

stdlib.h提供带有标准库功能的访问,修改和管理动态内存。常用的函数包括malloc和free:

1
2
3
4
5
6
7
8
// Dynamically allocate 10 bytes
char *buffer = (char *)malloc(10);

strcpy(buffer, "hello");
printf("%s\n", buffer); // prints "hello"

// Frees/unallocates the dynamic memory allocated earlier
free(buffer);

malloc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
malloc(size_t n)
Returns a pointer to a newly allocated chunk of at least n
bytes, or null if no space is available. Additionally, on
failure, errno is set to ENOMEM on ANSI C systems.

If n is zero, malloc returns a minimum-sized chunk. (The
minimum size is 16 bytes on most 32bit systems, and 24 or 32
bytes on 64bit systems.) On most systems, size_t is an unsigned
type, so calls with negative arguments are interpreted as
requests for huge amounts of space, which will often fail. The
maximum supported value of n differs across systems, but is in
all cases less than the maximum representable value of a
size_t.
*/

可以看出,malloc 函数返回对应大小字节的内存块的指针。此外,该函数还对一些异常情况进行了处理
当 n=0 时,返回当前系统允许的堆的最小内存块。
当 n 为负数时,由于在大多数系统上,size_t 是无符号数(这一点非常重要),所以程序就会申请很大的内存空间,但通常来说都会失败,因为系统没有那么多的内存可以分配。

free

1
2
3
4
5
6
7
8
9
10
11
12
/*
free(void* p)
Releases the chunk of memory pointed to by p, that had been
previously allocated using malloc or a related routine such as
realloc. It has no effect if p is null. It can have arbitrary
(i.e., bad!) effects if p has already been freed.

Unless disabled (using mallopt), freeing very large spaces will
when possible, automatically trigger operations that give
back unused memory to the system, thus reducing program
footprint.
*/

可以看出,free 函数会释放由 p 所指向的内存块。这个内存块有可能是通过 malloc 函数得到的,也有可能是通过相关的函数 realloc 得到的。
此外,该函数也同样对异常情况进行了处理
当 p 为空指针时,函数不执行任何操作。
当 p 已经被释放之后,再次释放会出现乱七八糟的效果,这其实就是 double free。
除了被禁用 (mallopt) 的情况下,当释放很大的内存空间时,程序会将这些内存空间还给系统,以便于减小程序所使用的内存空间。

malloc的系统调用

malloc调用brk或mmap syscall来获取内存。
brk:brk通过增加程序中断位置(brk)从内核获取内存(非零初始化)。最初,开始(start_brk)和堆段的结束(brk)将指向同一位置。
1.当ASLR关闭时,start_brk和brk将指向data / bss段的结尾(end_data)。
2.当ASLR打开时,start_brk和brk等于数据/ bss段的结尾(end_data)加上随机的brk偏移量。

上图中start_brk是堆段的开始,而brk(程序中断)是堆段的结束

mmap

malloc使用mmap创建私有的匿名映射段。 私有匿名映射的主要目的是分配新的内存(零填充),并且此新内存将由调用进程专用。

mmap内存映射原理
mmap内存映射的实现过程,总的来说可以分为三个阶段:
(一)进程启动映射过程,并在虚拟地址空间中为映射创建虚拟映射区域
1、进程在用户空间调用库函数mmap,原型:void mmap(void start, size_t length, int prot, int flags, int fd, off_t offset);
2、在当前进程的虚拟地址空间中,寻找一段空闲的满足要求的连续的虚拟地址
3、为此虚拟区分配一个vm_area_struct结构,接着对这个结构的各个域进行了初始化
4、将新建的虚拟区结构(vm_area_struct)插入进程的虚拟地址区域链表或树中
(二)调用内核空间的系统调用函数mmap(不同于用户空间函数),实现文件物理地址和进程虚拟地址的一一映射关系
5、为映射分配了新的虚拟地址区域后,通过待映射的文件指针,在文件描述符表中找到对应的文件描述符,通过文件描述符,链接到内核“已打开文件集”中该文件的文件结构体(struct file),每个文件结构体维护着和这个已打开文件相关各项信息。
6、通过该文件的文件结构体,链接到file_operations模块,调用内核函数mmap,其原型为:int mmap(struct file filp, struct vm_area_struct vma),不同于用户空间库函数。
7、内核mmap函数通过虚拟文件系统inode模块定位到文件磁盘物理地址。
8、通过remap_pfn_range函数建立页表,即实现了文件地址和虚拟地址区域的映射关系。此时,这片虚拟地址并没有任何数据关联到主存中。
(三)进程发起对这片映射空间的访问,引发缺页异常,实现文件内容到物理内存(主存)的拷贝
(前两个阶段仅在于创建虚拟区间并完成地址映射,但是并没有将任何文件数据的拷贝至主存。真正的文件读取是当进程发起读或写操作时。)
9、进程的读或写操作访问虚拟地址空间这一段映射地址,通过查询页表,发现这一段地址并不在物理页面上。因为目前只建立了地址映射,真正的硬盘数据还没有拷贝到内存中,因此引发缺页异常。
10、缺页异常进行一系列判断,确定无非法操作后,内核发起请求调页过程。
11、调页过程先在交换缓存空间(swap cache)中寻找需要访问的内存页,如果没有则调用nopage函数把所缺的页从磁盘装入到主存中。
12、之后进程即可对这片主存进行读或者写的操作,如果写操作改变了其内容,一定时间后系统会自动回写脏页面到对应磁盘地址,也即完成了写入到文件的过程。

多线程支持

在原来的 dlmalloc 实现中,当两个线程同时要申请内存时,只有一个线程可以进入临界区申请内存,而另外一个线程则必须等待直到临界区中不再有线程。这是因为所有的线程共享一个堆。在 glibc 的 ptmalloc 实现中,比较好的一点就是支持了多线程的快速访问。在新的实现中,所有的线程共享多个堆。

堆相关数据结构

宏观结构,包含堆的宏观信息,可以通过这些数据结构索引堆的基本信息。
微观结构,用于具体处理堆的分配与回收中的内存块。

微观结构

malloc_chunk

概述
在程序的执行过程中,我们称由 malloc 申请的内存为 chunk 。这块内存在 ptmalloc 内部用 malloc_chunk 结构体来表示。当程序申请的 chunk 被 free 后,会被加入到相应的空闲管理列表中。无论一个 chunk 的大小如何,处于分配状态还是释放状态,它们都使用一个统一的结构。虽然它们使用了同一个数据结构,但是根据是否被释放,它们的表现形式会有所不同。
malloc_chunk 的结构如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
This struct declaration is misleading (but accurate and necessary).
It declares a "view" into memory allowing access to necessary
fields at known offsets from a given base. See explanation below.
*/
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;
};

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 状态,那么会有两个位置记录其相应的大小
1.本身的 size 字段会记录,
2.它后面的 chunk 会记录。
一般情况下,物理相邻的两个空闲 chunk 会被合并为一个 chunk 。堆管理器会通过 prev_size 字段以及 size 字段合并两个物理相邻的空闲 chunk 块。















CATALOG
  1. 1. 堆的详解
    1. 1.1. 什么是堆
    2. 1.2. 使用动态内存
    3. 1.3. malloc的系统调用
    4. 1.4. 多线程支持
    5. 1.5. 堆相关数据结构
      1. 1.5.1. 微观结构