浅析堆的申请释放及相应保护机制

0×00 前面的话

在了解这部分的时候,首先你最好阅读一下这两篇博客:

Linux堆内存管理深入分析上

Linux堆内存管理深入分析下

在内存中,堆是一个很有趣的地方,因为它可以由用户去直接的进行分配与销毁,所以也产生了一些很有趣、奇思妙想的漏洞,像unlink漏洞、House系列漏洞等等。但是在学习的过程中,我们很容易难以理解那些介绍的比较模糊的概念,比如 unsortedbin 在某些条件下会放回 smallbin 或 largebin 中,那到底是什么时候?也会对一些大佬构造的 payload 犯迷糊,为什么这里多了一个chunk,为什么这个字节要填充…,大佬们往往不对这些细节做过多的解释,但是这可难为了我们初学堆利用的新兵,所以,我想写几篇文章,将堆的运作机制,例如一些基本的概念,malloc机制、free机制、保护机制,和利用方法结合起来说一下,让大家能够对堆这一块有个较为清楚的认识,少走一些弯路。首先呢,我想在这篇文章中较为细致的介绍一下堆中的一些情况,剩下的有机会的话我会一并写成一个系列。

这篇文章主要分为四个部分:

1
2
3
4
0x01 chunk 简介
0x02 bin 简介
0x03 malloc 机制
0x04 free 机制

这些内容相对比较重要,如果看完还觉得不够的,推荐大家去读一下华庭老师的《glibc内存管理ptmalloc源代码分析》。

0×01 chunk 简介

首先先说一下堆是如何分配的,在内存中,堆(低地址到高地址,属性RW)有两种分配方式(与malloc申请chunk做区分):

1
2
mmap: 当申请的size大于128kb时,由mmap分配。有时候是0x22000
brk: 当申请的size小于128kb时,由brk分配,第一次分配132KB(main arena),第二次在brk下分配,不够则执行系统调用,向系统申请

在内存中进行堆的管理时,系统基本是以 chunk 作为基本单位,chunk的结构在源码中有定义

1
2
3
4
5
6
7
8
9
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;
};

INTERNAL_SIZE_T 即 size_t

1
2
3
#ifndef INTERNAL_SIZE_T
#define INTERNAL_SIZE_T size_t
#endif

我们可以打印一下本机的 sizeof(size_t),这个长度可以说是一个基准单位

1
2
3
4
5
#include<stdio.h>
int main() {
printf("sizeof(size_t) is %d\n",sizeof(size_t));
return 0;
}

这个结构不再多谈,相关的介绍网上很多,主要提一下结构体中最后两个指针 fd_nextsize 和 bk_nextsize,这两个指针只在 largebin 中使用,其他情况下为 NULL。我们可以根据 chunk 的状态将其分为三种(allocated chunk、free chunk、top chunk):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
allocated chunk:
chunk header:
prev_size(当上一块是free状态时,存储该chunk的size,否则被上一块chunk使用)
size(该chunk大小(包括chunk header),某位3 bits为标志位)
0bit表示上一chunk是否free
1bit表示该chunk是否由mmap分配
2bit表示该chunk是否属于main arena
data:
free chunk:
chunk header:
prev_size:
size:
fd:指向 bin 中的next chunk
bk:指向 bin 中的last chunk(bin中先进的为last,后进的为next)
fd_nextsize:
bk_nextsize:
top chunk:brk中未分配的顶端chunk
chunk header:
prev_size:
size:

其中在 free chunk中有一种特殊的chunk(last remainder chunk):

1
last remainder chunk:从free chunk中malloc时,如果该chunk足够大,那么将其分为两部分,未分配的放到last remainder中并交由 unsorted bin 管理。

重点强调一下:这里的上一块表示在内存的堆中连续的chunk的上一块,区别bin中的前后关系。另外 chunk 的前后关系只有在bin中是使用fd、bk指针标识的,在内存中连续的chunk则通过 prev_size 和 size 来寻找前后 chunk,当然,这也就造成了漏洞。

由于chunk会在几种状态之间切换,当其为free chunk时,最少需要4sizeof(size_t)的空间,所以有最小分配大小。

并且由于prev_size的复用,所以实际申请的大小为 max(2sizeof(size_t)(chunk_header)-sizeof(size_t)(prev_size)+申请大小, 最小分配大小),而且 chunk的size是按照 2sizeof(size_t)对齐的,也就是说当你申请一个不是 2
sizeof(size_t)整倍数的空间时, malloc 返回的 size 有会对齐,大于实际申请的空间。

另外提一下,当 malloc 一个chunk后,实际返回用户的地址为chunk除去chunk header后的地址,而在bin中存储的是chunk的地址,也就是说

1
2
p = malloc(0x40); // 假设chunk的地址为 0xdeadbeef,则返回给用户的地址是 0xdeadbeef+sizeof(chunk header)
free(p) //将p释放掉后,保存在bin中的地址为 0xdeadbeef

0×02 bin简介

bin在内存中用来管理free chunk,bin为带有头结点(链表头部不是chunk)的链表数组,根据特点,将bin分为四种,分别为(fastbin、unsortedbin、smallbin、largebin):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
fastbin:
根据chunk大小维护多个单向链表
sizeof(chunk) < 64(bytes)
下一chunk(内存中)的free标志位不取消,显示其仍在使用
后进先出(类似栈),后free的先被malloc
拥有维护固定大小chunk的10个链表
unsortedbin:
双向循环链表
不排序
暂时存储free后的chunk,一段时间后会将chunk放入对应的bin中(详见0x02)
只有一个链表
smallbin:
双向循环链表
sizeof(chunk) < 512 (bytes)
先进先出(类似队列)
16,24...64,72...508 bytes(62个链表)
largebin:
双向循环链表
sizeof(chunk) >= 512 (bytes)
free chunk中多两个指针分别指向前后的large chunk
63个链表:0-31(512+64*i)
32-48(2496+512*i)
...
链表中chunk大小不固定,先大后小

这其中 fastbin 像是cache,用来实现快速的chunk分配,其中的chunk size大小与smallbin中的有重复(只是说大小,chunk并不重复)

unsortedbin 功能也是作为cache,尽量减少搜索合适chunk的时间。

这四个bin中,除了fastbin,其他三个都是维护双向循环链表,并且由一个长度为128 size_t的数组bins维护,bins结构如下:

NULL unsortbin smallbin largebin NULL
0 1 2-63 64-126 127

0×03 malloc机制

malloc功能主要由 _int_malloc() 函数实现,原型如下:

1
static Void_t* _int_malloc(mstate av,size_t bytes)

当接收到申请的内存大小后,我们看一下malloc的申请过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
长度位于 fastbin 时:
1.根据大小获得fastbin的index
2.根据index获取fastbin中链表的头指针
如果头指针为 NULL,转去smallbin
3.将头指针的下一个chunk地址作为链表头指针
4.分配的chunk保持inuse状态,避免被合并
5.返回除去chunk_header的地址
长度位于 smallbin 时:
1.根据大小获得smallbin的index
2.根据index获取smallbin中双向循环链表的头指针
3.将链表最后一个chunk赋值给victim
4.if(victim == 表头)
链表为空,不从smallbin中分配
else if(victim == 0)
链表未初始化,将fastbin中的chunk合并
else
取出victim,设置inuse
5.检查victim是否为main_arena,设置标志位
6.返回除去chunk_header的地址
长度位于 largebin 时:
1.根据大小获得largebin的index
2.将fastbin中chunk合并,加入到unsortbin中

留意一点:系统实际分配的内存地址与返回的地址是不同的,返回的地址直接指向了除去 chunk header 的地址。

当然,我们注意到上面的分配过程并没有完成,当 smallbin 中没有 chunk 或者 smallbin 未初始化时,并没有返回分配结果,这种情况下的chunk分配将在后面与largebin的分配一起处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
unsortedbin:
1.反向遍历unsortedbin,检查 2*size_t<chunk_size<内存总分配量
2.unsortedbin的特殊分配:
如果前一步smallbin分配未完成
并且 unsortedbin中只有一个chunk
并且该chunk为 last remainder chunk
并且该chunk大小 >(所需大小+最小分配大小)
则切分一块分配
3.如果请求大小正好等于当前遍历chunk的大小,则直接分配
4.继续遍历,将合适大小的chunk加入到smallbin中,向前插入作为链表的第一个chunk。(smallbin中每个链表中chunk大小相同)
5.将合适大小的chunk加入到largebin中,插入到合适的位置(largebin中每个链表chunk由大到小排列)
largebin:
1.反向遍历largebin,由下到上查找,找到合适大小后切分
切分后大小<最小分配大小,返回整个chunk,会略大于申请大小
切分后大小>最小分配大小,加入 unsortedbin。
2.未找到,index+1,继续寻找

如果这之后还未找到合适的chunk,那么就会使用top chunk进行分配,还是没有的话,如果在多线程环境中,fastbin可能会有新的chunk,再次执行合并,并向unsortedbin中重复上面,还是没有的话,就只能向系统申请了。

以上就是malloc分配的全经过。

几个malloc检查:

1
2
3
4
1.从fastbin中取出chunk后,检查size是否属于fastbin
2.从smallbin中除去chunk后,检查victim->bk->fd == victim
3.从unsortbin取chunk时,要检查2*size_t<chunk_size<内存总分配量
4.从largebin取chunk时,切分后的chunk要加入unsortedbin,需要检查 unsortedbin的第一个chunk的bk是否指向unsortedbin

0×04 free机制

1.首先使用 chunksize(p) 宏获取p的size

1
2
3
4
5
#define PREV_INUSE 0x1
#define IS_MMAPPED 0x2
#define NON_MAIN_ARENA 0x4
#define SIZE_BITS (PREV_INUSE|IS_MMAPPED|NON_MAIN_ARENA)
#define chunksize(p) ((p)->size & ~(SIZE_BITS))

也就是直接屏蔽了控制位信息,不过不要紧,chunk的分配是 2*sizeof(size_t) 对齐的,所以屏蔽低三位对大小无影响

2.安全检查:

1
2
chunk的指针地址不能溢出
chunk 的大小 >= MINSIZE(最小分配大小),并且检查地址是否对齐

3.大小为fastbin的情况(不改变inuse位)

1
2
3
1).检查下一个chunk的size:2*size_t<chunk_size<内存总分配量
2).double free检查:
检查当前free的chunk是否与fastbin中的第一个chunk相同,相同则报错

简单的小例子

1
2
3
4
5
6
7
8
#include <stdio.h>
#include <stdlib.h>
int main() {
char *a=malloc(24);
char *b=malloc(24);
free(a);
free(a);
}

报错

1
2
3
4
5
6
7
8
9
#include <stdio.h>
#include <stdlib.h>
int main() {
char *a=malloc(24);
char *b=malloc(24);
free(a);
free(b);
free(a);
}

没问题

4.其他情况

1
2
3
4
5
6
7
8
9
10
11
12
13
1).检查下一个chunk的size:2*size_t<chunk_size<内存总分配量
如果当前 chunk 为 sbrk()分配,那么它相邻的下一块 chunk 超过了分配区的地址,会报错
2).double free检查:
检查当前free的chunk是否为top chunk,是则报错
根据下一块的inuse标识检查当前free的chunk是否已被free
3) unlink合并:
检查前后chunk是否free,然后向后(top chunk方向)合并,并改变对应的inuse标志位
unlink检查: I.当前chunk的size是否等于下一chunk的prev_size
II.P->bk->fd == P && P->bk->fd == P
如果合并后 chunk_size > 64bytes,则调用函数合并fastbin中的chunk到unsortedbin中
将合并后的chunk加入unsortedbin
4) unsortedbin检查
需要检查 unsortedbin的第一个chunk的bk是否指向unsortedbin

我们可以看到,针对free的检查主要是下一块的size和inuse位,另外fastbin的检查可以用来做double free。

0×05

以上就是对堆的情况所做的一些介绍,了解堆的保护机制后,我们便可以在攻击时想办法进行绕过,从而构造出那些光怪陆离的payload。

*本文原创作者:hellowuzekai,属于FreeBuf奖励计划,禁止转载