title: Linux heap 学习

tags: Heap,pwn,linux

grammar_cjkRuby: true

利用周末的时间，系统的学习了linux 系统的glibc堆分配机制，从中了解了很多以前很模糊的东西。本文打算系统的讲解一下关于堆的分配和使用机制，同时思考可能存在的一些攻击方法。

0x01 Linux 堆概述

在程序运行过程中，动态的进行内存分配。是在内存中的一段连续的空间，由低地址向高地址增长。由堆管理其负责调用分配。

0x1 实现库

目前实现堆管理的库有很多

dlmalloc – General purpose allocator

ptmalloc2 – glibc

jemalloc – FreeBSD and Firefox

tcmalloc – Google

libumem – Solaris

主要介绍ptmalloc2 – glibc，ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。

0x2 分配函数

堆内存的分配函数是malloc(n)

1.当 n=0 时，返回当前系统允许的堆的最小内存块。

2.当 n 为负数时，由于在大多数系统上，size_t 是无符号数（这一点非常重要），所以程序就会申请很大的内存空间，但通常来说都会崩溃，因为系统没有那么多的内存可以分配。

malloc是用户层使用的函数，真正分配内存的是系统调用函数 (s)brk 函数以及 mmap, munmap 函数。

在一开始创建堆的时候使用brk函数，直接在数据段的后面申请一段空间（称为arena）

堆扩展那么当arena空间不够时系统怎么处理？

malloc采取的机制是

1.当调用malloc函数，arena空间不够时，如果申请的大小<128KB(0x20000字节) 直接使用brk分配机制，也就是说直接拓展arena

2.前提一样，如果申请的空间>= 128KB时，直接使用mmap分配机制

测试程序针对第一种情况

#include
 

#include
 

#include
 

#include
 

#include
 
 

int
 main() {
 
char
* addr;
 printf(
"Welcome to per thread arena example::%d\n"
,getpid());
 addr = (
char
*) malloc(
1000
);
 getchar();
 addr = (
char
*) malloc(
0x20000
);
 getchar();
 addr = (
char
*) malloc(
0x10000
);
 getchar();
 addr = (
char
*) malloc(
0x10000
);
 getchar();
 free(addr);
 
return
 
0
;
}

针对第二种情况，测试脚本

#include
 

#include
 

#include
 

#include
 
 

#include
 

int
 main() {
 
pthread_t
 t1;
 
void
* s;
 
int
 ret;
 
char
* addr;
 printf(
"Welcome to per thread arena example::%d\n"
,getpid());
 addr = (
char
*) malloc(
1000
);
 getchar();
 
// addr = (char*) malloc(0x40000);
 
// addr = (char*) malloc(0x40000);
 addr = (
char
*) malloc(
0x10000
);
 getchar();
 addr = (
char
*) malloc(
0x10000
);
 getchar();
 addr = (
char
*) malloc(
0x20000
);
 getchar(); 

 free(addr);
 
return
 
0
;
}

0x3 释放函数

堆内存释放函数是free(p)，其中p是堆指针，指向的是data部分（不加上head头部）

1.当 p 为空指针时，函数不执行任何操作。

2.当 p 已经被释放之后，再次释放会出现乱七八糟的效果，这其实就是 double free。

除了被禁用 (mallopt) 的情况下，当释放很大的内存空间时，程序会将这些内存空间还给系统，以便于减小程序所使用的内存空间。

在执行释放函数时，会检查该块的前一块是否是空块，如果是将会进行堆块的合并。

0x02 Heap 分配机制

在程序使用堆的时候会调用malloc去申请内存空间，返回的是一个堆块指针，指向堆结构体，当它被释放时会被插入相对应的空闲结块链表。

0x1 堆块结构

堆块结构是一个结构体，具体内容如下

/*
 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;
};

在size的底三位记录了当前的堆块状态和上一个内存地址相邻的堆块的使用状态参数解释

• 
  
• prevsize
• 记录上一个堆块（这里指的是内存地址相邻的堆块，而不是链表中的相邻）的大小，当本块的p位（记录上一堆块的使用状态）为1时，prevsize属于上一个堆块，进行内存赋值等操作。反之则表示上一堆块的大小
• size
• 记录本块大小，该 chunk 的大小，大小必须是 2 * SIZE_SZ 的整数倍。包括header在内的堆块大小，第三位分别为N、M、P
• P
• PREV_INUSE，表示前一个chunk是否为allocated
• M
• IS_MAPPED，表示当前chunk是否是通过mmap系统调用产生的
• N
• NONMAINARENA，表示当前chunk是否是thread arena
• FD
• 指向链表中前一个堆块的指针，该指针指向的是chunk的head
• BK
• 指向链表中后一个堆块的指针，该指针也是指向chunk的head，通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理
• FD_nextsize
• 指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
• BK_nextsize
• 指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适chunk 时挨个遍历。

内存对齐堆块申请的时候不一定都是内存对齐的，比如在x86操作系统下申请0x95。那么堆的对齐方式又是如何呢？

经过实验发现如下规律

机器类型对齐位数x868bytex6416byte

同时通过输出size_t，为堆块中的基本单位

机器类型基本单元x864bytex648byte

分配大小计算

在进行内存申请的时候有许多计算规则，如果想要数量掌握堆的管理机制以及利用方法，那么就必须了解堆块是如何分配其大小的。

首先提几个概念，内存复用、地址对齐。内存复用体现在下一块的prevsize，复用的内存不算在chunk大小上。在计算是首先 size mod2*size_t剩余的数据与sizet进行比较，如果小则直接分配，如果大则直接增加 2*size_t以一个例子为例： malloc(0x43)

• 在x86环境下 对齐单元为0x8还剩下0x3字节数据，可以利用复用的内存进行扩充。加上头部8字节，一共分配了0x48字节chunk

malloc(0x45)

• 在x86环境下对齐之后还剩0x5字节数据，复用还不行，那么直接增加0x8个字节，一共分配0x50字节chunk

举一个0x64的例子 malloc(0x45)

• 对齐之后还有0x5字节，可以采取复用，最后大小为0x50

malloc(0x49)

• 对齐之后，不可以采取复用，最后大小为0x60

最后补充一点，每一个chunk都要有data段，所以不能只用头和复用段。

bin

当用户释放chunk后，chunk并不会立即回到系统中去，而是有ptmalloc统一进行管理，当再有内存空间申请的请求时，ptmalloc分配器会在空闲的chunk中挑一块给用户。那么维护空闲chunk的结构是链表形式，主要有四种fast bins，small bins，large bins，unsorted bin。在下面的介绍中将一一讲述。

bin的链表中的指针指向的是head头部，并非是数据部分，这点应该格外注意。

0x2 Fast bin

防止经常使用的较小的堆块被合并，降低堆的利用效率。

fastbin总共有10个链表，不同位数操作系统的堆块大小不同

索引x86x6400x200x1010x300x1820x400x2030x500x2840x600x3050x700x3860x800x40

需要注意的几点

• Fastbin的free chunk中p标志位是一直为1的也就是说，fastbin的空闲块总是标识被占用。也是防止被其他块进行合并
• Fastbin 链表是单链表，方便操作

利用fd执行后面的指针

0x3 Small bin

小于512字节的chunk称之为small chunk，small bin就是用于管理small chunk的。采用FIFO的算法

需要注意几点

• smallbin个数是62个参照上图
• 维护的是双向链表
• 当相邻的两个堆块都是free状态时，会发生合并现象
• 与fastbin的大小相冲突，大小冲突的smallbin还会收录堆块吗？答案是会的，不是一次申请的fastbin大小堆块被释放，就有可能放入smallbin里面
• smallbin的来源是？smallbin的来源是unsortedbin，具体会在unsortedbin中讲解

0x4 Lager bin

large bins 中一共包括 63 个 bin，每个 bin 中的 chunk 的大小不一致，而是处于一定区间范围内。此外，这 63 个 bin 被分成了 6 组，每组 bin 中的 chunk 大小之间的公差一致，具体如下：

需要注意几点

• 合并同smallbin
• 同一个largebin其chunk大小有可能不一样，处于某一范围之内(例如第一个为521~575之间)。在同一个largebin里面chunk的大小是按照从大到小的顺序排放的
• 在横向也有链表相连接如下图
• malloc时，首先确定大小属于哪个largebin。然后将剩余的chunk丢到unsortedbin中，等待分配。

0x5 Unsorted bin

unsorted bin 位于 bin[1]，当释放较小或较大的chunk的时候，如果系统没有将它们添加到对应的bins中，主要来源如下

1.当一个较大的 chunk 被分割成两半后，如果剩下的部分大于MINSIZE，就会被放到 unsorted bin 中。

2.释放一个不属于 fast bin 的 chunk，并且该 chunk 不和 top chunk 紧邻时，该 chunk 会被首先放到 unsorted bin 中。关于 top chunk 的解释，请参考下面的介绍。

3.当申请的内存被释放时除了fastbin大小的chunk直接插入链表中外，其他的chunk都被放在unsorted bin里面待分配。

4.unsorted chunk的删除并不使用 unlink ，使用的是下面方法，因此只是改变了chunk的bk块的前项指针，在malloc操作时最后访问的unsorted ，如果没有合适的大小就一个一个的删除，添加到其他链表中，所以这时如果伪造了chunk的bk值，很容易引起崩溃

victim = unsortedchunks(av)->bk // victim为free掉的p

bck = victim->bk; // bck 为 任意地址 -0x10

unsortedchunks(av)->bk = bck; // 调整链表

bck->fd = unsorted_chunks(av); // 任意地址 -0x10 + 0x10 = unsortedbin

0x6 Top chunk

对于非主分配区会预先从 mmap 区域分配一块较大的空闲内存模拟 sub-heap,通过管 理 sub-heap 来响应用户的需求,因为内存是按地址从低向高进行分配的,在空闲内存的最 高处,必然存在着一块空闲 chunk,叫做 top chunk.当 bins 和 fast bins 都不能满足分配需 要的时候,ptmalloc 会设法在 top chunk 中分出一块内存给用户,如果 top chunk 本身不够大, 分配程序会重新分配一个 sub-heap,并将 top chunk 迁移到新的 sub-heap 上, 新的 sub-heap 与已有的 sub-heap 用单向链表连接起来,然后在新的 top chunk 上分配所需的内存以满足分配的需要,实际上,top chunk 在分配时总是在 fast bins 和 bins 之后被考虑,所以,不论 top chunk 有多大,它都不会被放到 fast bins 或者是 bins 中. top chunk 的大小是随着分配和回 收不停变换的,如果从 top chunk 分配内存会导致 top chunk 减小,如果回收的 chunk 恰好 与 top chunk 相邻,那么这两个 chunk 就会合并成新的 top chunk,从而使 top chunk 变大. 如果在 free 时回收的内存大于某个阈值,并且 top chunk 的大小也超过了收缩阈值,ptmalloc 会收缩 sub-heap,如果 top-chunk 包含了整个 sub-heap,ptmalloc 会调用 munmap 把整个 sub-heap 的内存返回给操作系统.

0x7 Last remainder

Last remainder 是另外一种特殊的 chunk,就像 top chunk 和 mmaped chunk 一样,不会 在任何 bins 中找到这种 chunk.当需要分配一个 small chunk, 但在 small bins 中找不到合适 的 chunk, 如果 last remainder chunk 的大小大于所需的 small chunk 大小,last remainder chunk 被分裂成两个 chunk, 其中一个 chunk 返回给用户, 另一个 chunk 变成新的 last remainder chuk.

0x8 保护机制

按照free与malloc分类

free

1. free的检查主要是根据本chunk的size检测下一块的inuse位，查看是否有double free的情况发生
2. 检查当前free的chunk是否与fastbin中的第一个chunk相同，相同则报错
3. 根据当前的inuse以及后一块的后一块的inuse判断是否需要合并，如果需要合并则对在链表中的freebin进行unlink操作

malloc

1. 从fastbin中取出chunk后，检查size是否属于fastbin
2. 从smallbin中除去chunk后，检查victim->bk->fd == victim
3. 从unsortbin取chunk时，要检查2*sizetsize
4. 从 largebin取chunk时，切分后的chunk要加入unsortedbin,需要检查 unsortedbin的第一个chunk的bk是否指向unsortedbin
5. 如果freebin中有合适大小的堆块那么执行unlink操作

unlink

1. 当需要unlink一个堆块时首先检测大小是否等于后一块的prev_size
2. 接着检查unlink的堆块是否在链表中

下面通过一些代码进行测试

free 会检查double free的情况

#include
 

#include
 

#include
 

#include
 

#include
 

int
 main(){
 
unsigned
 
long
 *q,*p,*point;
 p=malloc(
0x400 

);
 q=malloc(
0x500
);
 point = (
uint64_t
*)q - 
1
;
 *point = 
0x510
;
//this one should be 0x511 to prove p is used
 free(p); 
}

free 函数会检查unsorted chunk在链表中的情况

首先执行的是unlink，其次会对unsorted chunk在链表中的情况进行检查

#include
 

#include
 

#include
 

#include
 

#include
 

unsigned 

 
long
 *list;
int
 main(){
 
unsigned
 
long
 *q,*p,*x,*point;
 p=malloc(
0x80
);
 q=malloc(
0x100
);
 x=malloc(
1
);
 free(p);
 
// malloc(0x110); without it freebin will be unsortedbin
 list = (
unsigned
 
long
 *)p-
2
;
 point = (
unsigned
 
long
 *)p ;
//fd's addr
 
// *point = &list-3;
 *(point+
1
) = &list-
2
;
//canot change the bk's value cas it has pass the check
 free(q);
}
 

链表释放前会检查当前chunk size 与后一个chunk的prev_size

unlink 后向合并

#include
 

#include
 
 

#include
 

#include
 

#include
 

int
 main(){
 
unsigned
 
long
 *q,*p,*point;
 p=malloc(
0x80
);
 q=malloc(
0x90
);
 malloc(
1
);
 free(p);
 point = (
char
*)p - 
0x8
;
//addr of the chunk size
 *point = 
0x510
;
//fake size make that size != next_chunk(prev_size)
 free(q);
}

unlink 前向合并

#include
 

#include
 

#include
 

#include
 

#include
 

int
 main(){
 
unsigned
 
long
 *q,*p,*x,*point;
 p=malloc(
0x80
);
 q=malloc(
0x90
);
 x=malloc(
1
);
 free(q);
 point = (
char
*)x - 
0x10
;
//addr of the chunk size
 *point = 
0x110
;
//fake size make that size != next_chunk(prev_size) . The value should be 0xa0
 free(p);
} 

unlink会检查chunk是否在链表里

free 中的unlink执行双链表检测

前项合并

#include
 

#include
 

#include
 

#include
 

#include
 

unsigned
 
long
 *list;
int
 main(){
 
unsigned
 
long
 *q,*p,*x,*point;
 p=malloc(
0x80
);
 q=malloc( 

0x100
);
 x=malloc(
1
);
 free(q);
 malloc(
0x110
);
//to be come smallbins
 list = (
unsigned
 
long
 *)q-
2
;
 point = (
unsigned
 
long
 *)q ;
//fd's addr
 *point = &list;
//delete this line open two lines after it
 
// *point = &list-3;
 
// *(point+1) = &list-2;
 free(p);
}

后向合并

#include
 

#include
 

#include
  


#include
 

#include
 

unsigned
 
long
 *list;
int
 main(){
 
unsigned
 
long
 *q,*p,*x,*point;
 p=malloc(
0x80
);
 q=malloc(
0x100
);
 x=malloc(
1
);
 free(p);
 malloc(
0x110
);
//to be come smallbins
 list = (
unsigned
 
long
 *)p-
2
;
 point = (
unsigned
 
long
 *)p ;
//fd's addr
 *point = &list;
//delete this line open two lines after it 

 
// *point = &list-3;
 
// *(point+1) = &list-2;
 free(q);
}

malloc时unsortedbin 不执行unlink

malloc函数会首先搜索smallbin和largebin，当有空闲的unsortedbin时，再搜索unsortedbin，方法是从unsorted的首块开始进行链表的清空（只有malloc会这样拆卸unsorted表）。所以可以用作unsorted attack

#include
 

#include
 

int
 main(){
 
unsigned
 
long
 stack_var1=
1
;
 
unsigned
 
long
 stack_var2=
2
;
 
unsigned
 
long 

 *q,*p=malloc(
400
);
 q=malloc(
500
);
 free(p);
 
//------------VULNERABILITY-----------
 p[
1
]=(
unsigned
 
long
)(&stack_var1-
2
);
 p[
0
] = (
unsigned
 
long
)(q);
 
//------------------------------------
 malloc(
400
);
//this option will check fastbin smallbin ,the last one is unsorted bin .if not find fit chunk in unsorted bin it will make the chunk into small or large bin list，if malloc != 400 it will crash
 fprintf(stderr, 
"%p: %p\n"
, &stack_var1, (
void
*)stack_var1);
 fprintf(stderr, 
"%p: %p\n"
, &stack_var2, (
void
*)stack_var2);
}

malloc时smallbin不执行unlink操作

#include
 

#include
 

long
 
long
 
int
 *x;
int
 main(){ 

 
unsigned
 
long
 stack_var1=
1
;
 
unsigned
 
long
 stack_var2=
2
;
 
unsigned
 
long
 *q,*p=malloc(
400
);
 q=malloc(
500
);
 x = p-
2
;
 free(p);
 malloc(
0x400
);
 
//------------VULNERABILITY-----------
 p[
0
] = (
unsigned
 
long
)(&x-
1
);
//this one is Unlimited
 p[
1
] = (
unsigned
 
long
)(&x- 

2
);
 
//-------------------------------------------
 malloc(
400
);
//this option will check fastbin smallbin ,the last one is unsorted bin .if not find fit chunk in unsorted bin it will make the chunk into small or large bin list
 fprintf(stderr, 
"%p: %p\n"
, &stack_var1, (
void
*)stack_var1);
 fprintf(stderr, 
"%p: %p\n"
, &stack_var2, (
void
*)stack_var2);
}

总结

具体的总结如下，终于可以好好的总结一下了。1.freefree 操作里面会有子操作unlink，unlink（会进行双向链表检测，检测过后就是赋值操作）。

如果是smallbin chunk直接进行unlink检测

如果是unsorted chunk还需要对其进行unsorted检测

之后会有一个对于链表的操作

2.mallocmalloc里面是不执行unlink操作的，对于smallbin只会检测 p->bk-fd==p对于unsortedbin 不会进行检测，所以会造成unsorted attack攻击

3.all最后就是每次在free list中卸掉链表都需要对所拆链表的size和下一块的prev_size进行比较。这一点不论是free还是malloc都遵循。

未完待续......

閱讀更多 合天網安實驗室 的文章

關鍵字: FreeBSD Google Solaris