堆基础

相关数据结构(libc-2.23中)

强烈推荐《Glibc内存管理-ptmalloc2源代码分析》

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

这张图是一个简单的模型

malloc_chunk.png

  • prev_size:如果之前的chunk被free掉,那么改为有效,且为上一个chunk的size值

  • 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,**prev_inuse:
    **- **1.在没有被free时:
    ** Prev_inuse=1,表示上一个chunk没有被free掉
    - 2 .被free时:
    Prev_inuse=0,表示上一个chunk被free掉,在有些bin中,free(这个chunk)时,就会通过prev_size的大小实现chunk的合并

  • fd,bk

    chunk 处于分配状态时,从 fd 字段开始是用户的数据。chunk 空闲时,会被添加到对应的空闲管理链表中,其字段的含义如下

    • fd 指向下一个(非物理相邻)空闲的 chunk
    • bk 指向上一个(非物理相邻)空闲的 chunk和fd一起构成双链表结构,这其中就涉及了例如从双链表中拆离出chunk的Unlink函数
    • 通过 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 的 prev_size 域无效,所以下一个 chunk 的该部分也可以被当前chunk使用。这就是chunk中的空间复用。

各种各样的bin

这里就引用《Glibc内存管理-ptmalloc2源代码分析》的话和图

用户 free 掉的内存并不是都会马上归还给系统,ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk,当用户进行下一次分配请求时,ptmalloc 会首先试图在空闲的 chunk 中挑选一块给用户,这样就避免了频繁的系统调用,降低了内存分配的开销。ptmalloc将相似大小的 chunk 用双向链表链接起来,这样的一个链表被称为一个 bin。Ptmalloc 一共维护了 128 个 bin,并使用一个数组来存储这些 bin(如下图所示)。

bins

fastbin

保存 0x20~0x80 大小的 chunk,如果被释放的chunk->size满足这个要求就会首先放入到这个bin中,且不修改下一个chunk->prev_size,fastbin使用单链表进行存储,存取顺序为LIFO(先进后出)

1
chunk_1 <--- chunk_2 <--- chunk_3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <stdlib.h>

int main()
{
char *p1 = malloc(0x10);
strcpy(p1,"11111111");

char *p2 = malloc(0x20);
strcpy(p2,"22222222");

char *p3 = malloc(0x30);
strcpy(p3,"33333333");

free(p1);
free(p2);
free(p3);

}

small bin

同一个 small bin 中的 chunk 具有相同的大小。两个相邻的 small bin 中的 chunk 大小相差 8bytes。small bins 中的 chunk 按照最近使用顺序进行排列,最后释放的 chunk 被链接到链表的头部,而申请 chunk 是从链表尾部开始,这样,每一个 chunk 都有相同的机会被 ptmalloc 选中。

unsorted bin

数组中的第一个为 unsorted bin,无法分进其他bin的chunk就会分配到这里, unsortedbin会不断增大,始终只有一块

fastbin

在libc-2.27中,tcache分配完,直接进unsorted bin,每一代glibc的分配方式都不大相同

当空闲的 chunk 被链接到 bin 中的时候,ptmalloc 会把表示该 chunk 是否处于使用中的标志 P 设为 0(注意,这个标志实际上处在下一个 chunk 中),同时 ptmalloc 还会检查它前后的 chunk 是否也是空闲的,如果是的话,ptmalloc 会首先把它们合并为一个大的 chunk,然后将合并后的 chunk 放到 unstored bin 中。要注意的是,并不是所有的 chunk 被释放后就立即被放到 bin 中。ptmalloc 为了 高分配的速度,会把一些小的的 chunk 先放到一个叫做 fast bins 的容器内。

故而,ptmalloc 中在分配过程中引入了 fast bins,不大于 max_fast (默认值为 64B)的 chunk 被释放后,首先会被放到 fast bins 中,fast bins 中的 chunk 并不改变它的使用标志 P。这样也就无法将它们合并,当需要给用户分配的 chunk 小于或等于 max_fast 时,ptmalloc 首先会在 fast bins 中查找相应的空闲块,然后才会去查找 bins 中的空闲 chunk。在某个特定的时候,ptmalloc 会遍历 fast bins 中的 chunk,

在pwndbg中长这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
int main()
{
void *p1 = malloc(0x30);
void *p2 = malloc(0x30);
void *p3 = malloc(0x30);
void *p4 = malloc(0x30);
free(p1);
free(p2);
free(p3);
free(p4);
p1 = malloc(0x40);
p2 = malloc(0x40);
p3 = malloc(0x40);
p4 = malloc(0x40);
free(p1);
free(p2);
free(p3);
free(p4);
return 0;
}

fastbin.png

相同大小的空闲chunk组成单链表

Topchunk

在gbd中,我们经常看见这样的chunk

1
2
3
4
5
6
7
#include <stdio.h>
#include <stdlib.h>
int main()
{
malloc(0x30);
return 0;
}

在malloc前

beformalloc.png

malloc过后

malloc-after.png

发现除了我们的chunk外,多了一个chunk,而且size特别大

这个 chunk 不属于任何一个 bin,它的作用在于当所有的bin 都无法满足用户请求的大小时,如果其大小不小于指定的大小,就进行分配,并将剩下的部分作为新的 top chunk。否则,就对heap进行扩展后再进行分配。在main arena中通过sbrk扩展heap,而在thread arena中通过mmap分配新的heap。

需要注意的是,top chunk 的 prev_inuse 比特位始终为1,否则其前面的chunk就会被合并到top chunk中。

Last_remainder mmaped_chunk

这两个个篇幅较多,直接看书就好了

堆分配和释放的实现

首先假如我们在4G内存大小的空间运行着一个32位的系统,那么内存中的分配空间如下

x32.png

64位的内存分布大致如下

duFyhn.png

堆分配-malloc

sbrk与mmap

这两者时实现堆分配的较低层原理

brk、sbrk

对应的有两个 Linux C中的sbrk()和一个API,一般指ptmalloc中的 sbrkbrk

1
2
3
4
5
6
7
8
9
/* Set the end of accessible data space (aka "the break") to ADDR.
Returns zero on success and -1 for errors (with errno set). */
extern int brk (void *__addr) __THROW __wur;

/* Increase or decrease the end of accessible data space by DELTA bytes.
If successful, returns the address the previous end of data space
(i.e. the beginning of the new space, if DELTA > 0);
returns (void *) -1 for errors (with errno set). */
extern void *sbrk (intptr_t __delta) __THROW;
  • brk中
    • *addr是数据段的结束地址,通过改变该地址来改变数据段的 大小,当结束地址向高地址移动,进程内存空间增大,当结束地址向低地址移动, 进程内存空间减小。
    • brk() 调用成功时返回 0,失败时返回 -1。
  • sbrk中
    • delta 表示增量,即增加或减少的空间大小,调用成功时返回增加后减小前数据段的结束地址,失败时返回 -1。

《CTF All in One》中有这样讲

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
#include<stdio.h>
#include<unistd.h>
int main()
{
void *curr_brk, *tmp_brk, *pre_brk;

printf("PID_now:%d\n",getpid());

tmp_brk = curr_brk = sbrk(0);
printf("初始化后的结束地址:%p\n",curr_brk);
getchar();

brk(curr_brk+4096);
curr_brk = sbrk(0);
printf("brk()分配过后的结束地址:%p\n",curr_brk);
getchar();

pre_brk = sbrk(4096);
curr_brk = sbrk(0);
printf("sbrk返回值(=之前的地址):%p\n",pre_brk);
printf("sbrk之后的结束地址:%p\n",curr_brk);
getchar();

brk(tmp_brk);
curr_brk = sbrk(0);
printf("恢复到初始化之前的地址:%p\n",curr_brk);
getchar();
}

关闭ASLR

echo 0 > /proc/sys/kernel/randomize_va_space

开两个窗口同时调一下:

cat /proc/<PID>/maps

  • 1. 初始化
1
2
3
4
5
6
7
void *curr_brk, *tmp_brk, *pre_brk;

printf("PID_now:%d\n",getpid());

tmp_brk = curr_brk = sbrk(0);
printf("初始化后的结束地址:%p\n",curr_brk);
getchar();

sbrk-1

  • 2. 使用brk分配
1
2
3
4
brk(curr_brk+4096);
curr_brk = sbrk(0);
printf("brk()分配过后的结束地址:%p\n",curr_brk);
getchar();

sbrk-2

  • **3.**使用sbrk分配
1
2
3
4
5
pre_brk = sbrk(4096);
curr_brk = sbrk(0);
printf("sbrk返回值(=之前的地址):%p\n",pre_brk);
printf("sbrk之后的结束地址:%p\n",curr_brk);
getchar();

sbrk-3

  • **4.**使用brk缩减heap
1
2
3
4
brk(tmp_brk);
curr_brk = sbrk(0);
printf("恢复到初始化之前的地址:%p\n",curr_brk);
getchar();

sbrk-4

mmap

原版定义

1
2
3
4
#include <sys/mman.h>

void *mmap(void *addr, size_t len, int prot, int flags,
int fildes, off_t off);

mmap() 函数要求内核创建一个从地址 addr 开始的 新虚拟内存区域,并将文件描述符 fildes 指定的对象的一个连续的片 (chunk)映射到这个新区域。连续的对象片大小为 len 字节,从距文件开始处 偏移量为 off 字节的地方开始。 prot 描述虚拟内存区域的访问权限 位, flags 描述被映射对象类型的位组成。

  • addr:映射区开始地址,为0时表示开始位置有系统决定
  • len:映射到调用进程地址空间的字节数
  • prot:期望的内存保护标志,不能与文件的打开模式冲突
    • PROT_EXEC //页内容可以被执行
    • PROT_READ //页内容可以被读取
    • PROT_WRITE //页可以被写入
    • PROT_NONE //页不可访问
  • flags:指定映射对象的类型,映射选项和映射页是否可以共享。它的值可以是一个或者多个以下位的组合体
    • MAP_FIXED //使用指定的映射起始地址,如果由start和len参数指定的内存区重叠于现存的映射空间,重叠部分将会被丢弃。如果指定的起始地址不可用,操作将会失败。并且起始地址必须落在页的边界上。
    • MAP_SHARED //与其它所有映射这个对象的进程共享映射空间。对共享区的写入,相当于输出到文件。直到msync()或者munmap()被调用,文件实际上不会被更新。
    • MAP_PRIVATE //建立一个写入时拷贝的私有映射。内存区域的写入不会影响到原文件。这个标志和以上标志是互斥的,只能使用其中一个。
    • MAP_ANON //表明进行的是匿名映射
  • fildes:即将映射到进程空间的文件描述字
  • off:参数一般设为0,表示从文件头开始映射。被映射对象内容的起点。

这里同样引用《CTF All in One》中的例子

同样的

关闭ASLR

echo 0 > /proc/sys/kernel/randomize_va_space

开两个窗口同时调一下:

cat /proc/<PID>/maps

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <sys/mman.h>
#include <unistd.h>
int main()
{
void *curr_brk;
printf("当前进程 PID:%d\n", getpid());
printf("初始化后\n");
getchar();

char *addr;
addr = mmap(
NULL, (size_t)4096, PROT_READ|PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
printf("mmap 完成\n");
getchar();

munmap(addr, (size_t)4096);
printf("munmap 完成\n");
getchar();
}
  • 1.初始化
1
2
3
4
void *curr_brk;
printf("当前进程 PID:%d\n", getpid());
printf("初始化后\n");
getchar();

init

  • 2.使用mmap创建映射段
1
2
3
4
5
6
char *addr;
addr = mmap(
NULL, (size_t)4096, PROT_READ|PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
printf("mmap 完成\n");
getchar();

mmap

  • 3.使用munmap减小函数
1
2
3
munmap(addr, (size_t)4096);
printf("munmap 完成\n");
getchar();

图里面打掉一个字母…

munmap

但是最常用的还是``malloc calloc realloc free`这些函数,我们再以libc-2.23为例,看看这几个函数是如何实现的

malloc

堆初始化

堆初始化是在用户第一次申请内存时执行 malloc_consolidate 再执行 malloc_init_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
31
32
33
34
35
36
37
38
39
struct malloc_state
{
/* 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. 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;
};

创建堆

malloc_init_state

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//malloc/malloc.c line 1799
static void malloc_init_state (mstate av)
{
int i;
mbinptr bin;

/* Establish circular links for normal bins */
for (i = 1; i < NBINS; ++i)
{
bin = bin_at (av, i);
bin->fd = bin->bk = bin;
}

#if MORECORE_CONTIGUOUS
if (av != &main_arena)
#endif
set_noncontiguous (av);
if (av == &main_arena)
set_max_fast (DEFAULT_MXFAST);
av->flags |= FASTCHUNKS_BIT;

av->top = initial_top (av);
}

接着就是各种hook

1
2
3
4
5
6
7
/* Forward declarations.  */
static void *malloc_hook_ini (size_t sz,
const void *caller) __THROW;
static void *realloc_hook_ini (void *ptr, size_t sz,
const void *caller) __THROW;
static void *memalign_hook_ini (size_t alignment, size_t sz,
const void *caller) __THROW;

malloc_hook_ini 为例

1
2
void *weak_variable (*__malloc_hook)
(size_t __size, const void *) = malloc_hook_ini;

这个说明了malloc_hook只是一个弱引用,那么由此我们衍生出了将 malloc_hook 修改为 libc_system的攻击方法

1
2
3
4
5
6
7
8
// malloc/hooks.c#L28
static void *
malloc_hook_ini (size_t sz, const void *caller)
{
__malloc_hook = NULL;
ptmalloc_init ();
return __libc_malloc (sz);
}

最后调用了libc中的malloc函数

(该部分参照了CTF-Wiki上的解释)

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
// malloc/malloc.c#L2931
void * __libc_malloc (size_t bytes)
{
mstate ar_ptr;
void *victim;

void *(*hook) (size_t, const void *)
= atomic_forced_read (__malloc_hook);

// 检查是否有内存分配钩子,如果有,调用钩子并返回.
if (__builtin_expect (hook != NULL, 0))
return (*hook)(bytes, RETURN_ADDRESS (0));
//在arena获取chunk
arena_get (ar_ptr, bytes);

//然后调用 _int_malloc 函数去申请对应的内存。
victim = _int_malloc (ar_ptr, bytes);

/* Retry with another arena only if we were able to find a usable arena
before. */
//如果分配失败的话,ptmalloc 会尝试再去寻找一个可用的 arena,并分配内存。
//英文注释就是这个意思
if (!victim && ar_ptr != NULL)
{
LIBC_PROBE (memory_malloc_retry, 1, bytes);
ar_ptr = arena_get_retry (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
}

//如果申请到了 arena,那么在退出之前还得解锁。
if (ar_ptr != NULL)
(void) mutex_unlock (&ar_ptr->mutex);

//最后的检查
//要么没有申请到内存 !victim
//要么是 mmap 的内存 chunk_is_mmapped (mem2chunk (victim))
//要么申请到的内存必须在其所分配的arena中 ar_ptr == arena_for_chunk (mem2chunk (victim))
assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
ar_ptr == arena_for_chunk (mem2chunk (victim)));
//返回chunk
return victim;
}
libc_hidden_def (__libc_malloc)

上面出现了这个函数 _int_malloc,接着看这个函数干了什么

_int_malloc的代码量很大,因为它时malloc函数功能的主要实现者

malloc/malloc.c#L3318

wiki上也是说的很详细了

https://wiki.x10sec.org/pwn/heap/heap_implementation_details/#_int_malloc

这里简单说下实现过程

  • bin里面找合适的
  • 所有bin均不满足时,考虑top_chunk
  • top_chunk也不满足时,考虑重新进行内存申请

堆释放

free

由上面的我们大概知道过程,free的过程也是相似

也是 __free_hook -> __libc_free -> _int_free

__libc_free

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
// malloc/malloc.c#L2933
void __libc_free (void *mem)
{
mstate ar_ptr;
mchunkptr p; /* chunk corresponding to mem */

void (*hook) (void *, const void *)
= atomic_forced_read (__free_hook);
//这里和__libc_malloc差不多,检查是否有hook
if (__builtin_expect (hook != NULL, 0))
{
(*hook)(mem, RETURN_ADDRESS (0));
return;
}

//内存为0的话不起作用
if (mem == 0) /* free(0) has no effect */
return;

//按照chunk的格式去解析内存(mem)
p = mem2chunk (mem);

//对mmap的chunk的释放
if (chunk_is_mmapped (p)) /* release mmapped memory. */
{
/* see if the dynamic brk/mmap threshold needs adjusting */
if (!mp_.no_dyn_threshold
&& p->size > mp_.mmap_threshold
&& p->size <= DEFAULT_MMAP_THRESHOLD_MAX)
{
mp_.mmap_threshold = chunksize (p);
mp_.trim_threshold = 2 * mp_.mmap_threshold;
LIBC_PROBE (memory_mallopt_free_dyn_thresholds, 2,
mp_.mmap_threshold, mp_.trim_threshold);
}
munmap_chunk (p);
return;
}

//根据chunk获得area的指针
ar_ptr = arena_for_chunk (p);
//执行释放
_int_free (ar_ptr, p, 0);
}

_int_free

malloc/malloc.c#L3840

其中也是很了很多情况以及很多的检查

同样Wiki讲的很细了

https://wiki.x10sec.org/pwn/heap/heap_implementation_details/#_int_free

平时作题出错的话可以向里面看看是哪里的检查有问题