Basic

管理heap的数据结构被称为Arena。

Linux早期版本采用dlmalloc作为默认的内存分配器，但是遇到多线程环境时，多个线程将共用同一个堆，因此临界区的竞争将会降低内存分配的效率。

而现在使用的ptmalloc(per thread malloc)对多线程的支持就很好（线程数<=CPU内核数时），每个线程都有一个自己的Arena。

主线程的arena叫做main_arena，他是一个静态全局变量，该arena的malloc_state存放在glibc的代码中。

main_arena对应的堆通过brk申请，子arena对应的堆则通过mmap申请。因此主Arena只有一个堆，而子Arena可以对应多个堆，当原来的堆不够用时，就会申请新的堆，然后和原来的堆链为一个链表。

malloc

概述

函数用法：

1
void *ptr = malloc(size)

第一次申请内存需要通过syscall（glibc, OS, kernel三方沟通）来实现，此后都交由glibc实作的内存管理机制来管理。

第一次malloc的时候，如果要申请的内存小于128KB，就会用sys_brk来直接申请128KB的空间，当做程序的heap段（通常都是这种状况）；如果要申请的内存大于128KB，就会用mmap。

要注意的是heap是从低地址往高地址成长的（这点与stack相反，但mmap映射的heap同stack，由高位向低位增长）

与calloc的区别：

calloc申请到的chunk会将内容全部初始化为0

(要注意的是, malloc函数返回的指针是指向user data处的，并不是chunk的开头部分)

(puts函数内部会调用malloc分配堆内存，要注意)

分析

其实在glibc的代码中并没有malloc函数，该函数真正调用的是__libc_malloc。

而且__libc_malloc只是用来简单封装 _int_malloc函数。而 _int_malloc函数才是申请内存块的核心。

__libc_malloc在被调用时会首先检查是否有malloc_hook，如果有的话，就会去调用。

Heap chunk

每一个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;
};

·chunk header

​ 大小是0x10, heap和stack一样，都只会开0x10的倍数大小，不会因为开一个char之类的就让后面 开始偏移了（事实上，chunk的大小必须是2*SIZE_SZ的整数倍，SIZE_SZ这个常量的值和操作系统有关，在x86系统中是4，x64系统中是8）

·prev_size & size (8, 8 bytes in x64)

​ prev_size用来存上一块内存（只有PREV_INUSE位为1时才启用，不然是可以被物理相邻的前一个chunk利用的，这就是chunk中的空间复用）size用来存这一块的size，由于heap chunk的大小肯定是0x10的倍数，所以低3位用来表示0~7的bit是用不上的，于是拿来当标记位了。

·3 flag bits in size bits 0~2:

​ PREV_INUSE: 连续内存上一块chunk是否处于被free掉的状态（第一个chunk和small bin, tcache bin的P位默认标记为1, 防止被合并）

​ IS_MMAPPED: 是否通过mmap分配

​ NON_MAIN_ARENA:是否不属于main_arena

heapchunk1.png

比如说你要malloc申请0x64个字节的数据，实际上可能会给0x80（0x70的data，0x10的header）

然后返回的指针是data处的。

freed chunk&bins

·free掉chunk

​ 在free回收之后，其实只是还给了glibc来管理，总的来说还是在被程序占用着。下次再申请满足要求的chunk时，可以直接从bins里面拿，防止了频繁的系统调用。

·依据size区分bins并回收

管理这些的结构为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
struct malloc_state {
    /* Serialize access.  */
    __libc_lock_define(, 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, help to speed up the process of determinating if a given bin is definitely empty.*/
    unsigned int binmap[ BINMAPSIZE ];

    /* Linked list, points to the next arena */
    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;
};

·fastbin

​ fastbin的大小一般是0x20, 0x30 …… 0x80，具体的话貌似在glibc的一个global_max_fast（大概是叫这个吧）上会写。回收fastbin的话，在arena上会有很多个单链表（在fastbinsY数组中，每个size最多存10个）护各个size的fastbin的使用情况，如果之后要再开空间，找到有合适大小的fastbin就可以直接拿来用。

​ fastbins通常不会被合并，但是当释放的chunk与该chunk相邻的空闲chunk合并后的大小大于FASTBIN_CONSOLIDATION_THRESHOLD时，内存碎片可能就比较多了，我们就需要把fast bins中的chunk都进行合并，以减小内存碎片对系统的影响。

1638862443980.png

fastbin只会用到fd，smallbin只会用到fd和bk，largebin被free掉之后的结构如图。

·small bin

​ small bins中每个chunk的大小与其所在的bin的index的关系为：chunk_size = 2 * SIZE_SZ * index

​ 一共有62个循环双向链表，每个链表都有链表头节点。此外，small bins中每个bin对应的链表采用FIFO的规则（这点不同于fastbins）。

·large bin

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

1642663746570.png

·unsorted bin

​ unsorted bin可以视为空闲的chunk回归其所属bin之前的缓冲区。其中的空闲chunk处于乱序状态，主要有两个来源：

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

​ ·释放一个不属于fastbin的chunk，并且该chunk不和top chunk物理相邻时，该chunk会被首先放到unsorted bin中。

​ ·当进行 malloc_consolidate 时，可能会把合并后的 chunk 放到 unsorted bin 中，如果不是和 top chunk 近邻的话。

​ unsorted bin在使用的过程中，采用的顺序也是FIFO（同small bin）

·对于small bins, large bins, unsorted bins来说，ptmalloc将他们维护在同一个数组中。这些bin对应的数据结构在malloc_state中有如下定义：

1
2
3
#define NBINS 128
/* Normal bins packed as described above */
mchunkptr bins[ NBINS * 2 - 2 ];

数组中的bin依次如下：

​ 1.第一个为unsorted bin

​ 2.索引从2到63的bin被称为small bin，同一个small bin链表中的chunk的大小相同，两个相邻索 引的small bin链表中的chunk大小相差2个机器字长（机器字长：x86:4bytes, x64:8bytes）

​ 3.small bins后面的bin被称作large bins。large bins中的每一个bin都包含一定范围内的chunk，其中的chunk按fd指针的顺序从大到小排列。相同大小的chunk同样按照最近使用的顺序排列。

·tcache bin

​ libc2.26版本新增的机制，和fastbin类似（但是tcache存的是userdata的地址），每个size的chunk默认最多存7个，如果存满了就会存到fastbin或者unsortedbin里去。PREV_INUSE标记也始终为1。

tcache bin新增了两个结构体：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* We overlay this structure on the user-data portion of a chunk when the chunk is stored in the per-thread cache.  */
typedef struct tcache_entry
{
  struct tcache_entry *next;
} tcache_entry;

/* There is one of these for each thread, which contains the per-thread cache (hence "tcache_perthread_struct").  Keeping overall size low is mildly important.  Note that COUNTS and ENTRIES are redundant (we could have just counted the linked list each time), this is for performance reasons.  */
typedef struct tcache_perthread_struct
{
  char counts[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

static __thread tcache_perthread_struct *tcache = NULL;

在_int_free函数的开头会首先调用tcache_put函数尝试将chunk放进tcache bin(分配大小不能超过0x408)

1
2
3
4
5
6
7
8
9
static void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
  tcache_entry *e = (tcache_entry *) chunk2mem (chunk);
  assert (tc_idx < TCACHE_MAX_BINS);
  e->next = tcache->entries[tc_idx];
  tcache->entries[tc_idx] = e;
  ++(tcache->counts[tc_idx]);
}

在__libc_malloc函数的开头会调用tcache_get函数尝试从tcache bin取出chunk

1
2
3
4
5
6
7
8
9
10
static void *
tcache_get (size_t tc_idx)
{
  tcache_entry *e = tcache->entries[tc_idx];
  assert (tc_idx < TCACHE_MAX_BINS);
  assert (tcache->entries[tc_idx] > 0);
  tcache->entries[tc_idx] = e->next;
  --(tcache->counts[tc_idx]);
  return (void *) e;
}

一个简单的判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#if USE_TCACHE
  {
    size_t tc_idx = csize2tidx (size);

    if (tcache
      && tc_idx < mp_.tcache_bins
      && tcache->counts[tc_idx] < mp_.tcache_count)
      {
        tcache_put (p, tc_idx);
        return;
      }
  }
#endif

注：一个tcache bin中的最大数量mp_.tcache_count默认是7

在内存分配的 malloc 函数中有多处，会将内存块移入 tcache 中。

（1）首先，申请的内存块符合 fastbin 大小时并且在 fastbin 内找到可用的空闲块时，会把该 fastbin 链上的其他内存块放入 tcache 中。

（2）其次，申请的内存块符合 smallbin 大小时并且在 smallbin 内找到可用的空闲块时，会把该 smallbin 链上的其他内存块放入 tcache 中。

（3）当在 unsorted bin 链上循环处理时，当找到大小合适的链时，并不直接返回，而是先放到 tcache 中，继续处理。

·top chunk

​ 程序第一次进行 malloc 的时候，heap 会被分为两块，一块给用户，剩下的那块就是 top chunk。其实，所谓的 top chunk 就是处于当前堆的物理地址最高的 chunk。这个 chunk 不属于任何一个 bin，它的作用在于当所有的 bin 都无法满足用户请求的大小时，如果其大小不小于指定的大小，就进行分配，并将剩下的部分作为新的 top chunk。否则，就对 heap 进行扩展后再进行分配。在 main arena 中通过 sbrk 扩展 heap，而在 thread arena 中通过 mmap 分配新的 heap。

·last reamainder

​ 在用户使用 malloc 请求分配内存时，ptmalloc2 找到的 chunk 可能并不和申请的内存大小一致，这时候就将分割之后的剩余部分称之为 last remainder chunk ，unsorted bin 也会存这一块。top chunk 分割剩下的部分不会作为 last remainder。

基础攻击手法

堆溢出

堆溢出是一种特定的缓冲区溢出。但是堆上没有直接存程序返回地址之类的，没办法直接控制EIP，但是可以利用堆中的机制（如unlink）来实现任意地址写入或控制堆块中的内容等效果，从而控制程序的执行流程。

OFF BY ONE

利用思路：

1.溢出字节为可控制任意字节：通过修改大小造成块结构之间出现重叠，从而泄露其他块数据，或是覆盖其他块数据。

2.溢出字节为 NULL 字节：在 size 为 0x100 的时候，溢出 NULL 字节可以使得 prev_in_use 位被清，这样前块会被认为是 free 块。（1） 这时可以选择使用 unlink 方法（见 unlink 部分）进行处理。（2） 另外，这时 prev_size 域就会启用，就可以伪造 prev_size ，从而造成块之间发生重叠。此方法的关键在于 unlink 的时候没有检查按照 prev_size 找到的块的大小与prev_size 是否一致。（在2.28及之前版本没有此检查，之后已经有了）

有一种常见的利用场景就是strlen()和strcpy()函数配合使用的情况，strlen()在检查长度的时候不会把’\x00’算进去，但是strcpy()会把’\x00’一起复制，所以有时可以用这个’\x00’覆盖到下一chunk的size位。

UAF

全称：use after free

·ptr未清空 -> Dangling pointer

​ 比如一个指针所指的区域已经被free掉了，但是指针依然指着那个位置

·Object -> 解析方式不同

​ 伪造vtable（c++）

·function pointer -> control rip

假设有如下结构体：

1
2
3
4
5
6
7
8
9
struct human{
	long age;
	void (*say)();
	char name[0x10];
};  //共需要8+8+0x10=0x20

struct f__k{
	char trash[0x20];
};  //也是0x20b

一个简单的uaf:

1
2
3
4
5
6
7
8
9
10
11
12
struct f__k *a = (struct f__k*) malloc (sizeof (struct f__k));

strcpy(a->trash, "aaaaaaaabbbbbbbbccccccccdddddddd");
printf("name:%s\nage:%p\n", ((struct human*)a)->name, ((struct human*)a)->age);

free(a);

struct human *b = (struct human*) malloc (sizeof(struct human));

printf("name:%s\nage:%p\n", b->name, b->age);

b->say();

fastbin的空间也是FILO（first in last out）的，在链表头部插入，头部取出。

相当于最近free掉了一个0x20的空间，我再申请一个0x20的空间，肯定就是用的最近free掉的那个。

double free

顾名思义就是对同一块内存free两次（大多数时候会被系统检测到，然后直接异常结束，但是如果存在漏洞的话还是可以bypass掉）

比如说常见的一种fastbin的监测机制就是查看你现在free掉的是不是fastbin那个链表当前的某个头部，要绕过的话就很简单，只需要free(a), free(b)然后再free(a)就行。

可以达到类似于uaf的效果，比如说先free掉a，再free掉b，然后再free掉a，这样一来，假如第一次拿到一个指针q指向a这块内存，但q不可控，然后后面再拿到一个指针p也指向a，但是p可控，目的就达成了。

double free通常和uaf配合起来用。

利用unlink过程中的FD->fd = BK, BK->bk = FD，修改某个地方的指针值。

最长用到的就是将heap数组某一位的值，*ptr变成ptr+0x18

fastbin attack

利用堆溢出，修改后续被free掉的fastbin的fd指针，指向一个目标地址附近的fakechunk，以此申请到目标chunk，由于fastbin没有使用unlink，所以只需要保证目标fakechunk的size能通过检查就行了（通常找0x7f比较简单，而且0x7f的prev_inuse位也是1）

house of spirit:

伪造一个堆块，将其free，然后申请到。

unsortedbin attack

前提：能够控制unsorted bin的bk指针

效果：把任意地址值改写成一个较大的数值（比如说修改掉循环的次数，进行更多次循环，或者修改掉global_max_fast，让更大的chunk被视为fastbin，以此来进行fastbin attack）

方法：将unsorted bin尾结点的bk改为目标addr-0x10

（此方法在libc2.29+失效，改用tcache stashing unlink attack实现相同效果）

largebin attack

largebin attack是未来更深入的利用，需要好好掌握。

参照ctf-wiki给出的将large chunk放入bins的代码：

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
else
            {
              victim_index = largebin_index (size);
              bck = bin_at (av, victim_index);
              fwd = bck->fd;

              /* maintain large bins in sorted order */
              if (fwd != bck)
                {
                  /* Or with inuse bit to speed comparisons */
                  size |= PREV_INUSE;
                  /* if smaller than smallest, bypass loop below */
                  assert (chunk_main_arena (bck->bk));
                  if ((unsigned long) (size)
              < (unsigned long) chunksize_nomask (bck->bk))
                    {
                      fwd = bck;
                      bck = bck->bk;

                      victim->fd_nextsize = fwd->fd;
                      victim->bk_nextsize = fwd->fd->bk_nextsize;
                      fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
                    }
                  else
                    {
                      assert (chunk_main_arena (fwd));
                      while ((unsigned long) size < chunksize_nomask (fwd))
                        {
                          fwd = fwd->fd_nextsize;
              assert (chunk_main_arena (fwd));
                        }

                      if ((unsigned long) size
              == (unsigned long) chunksize_nomask (fwd))
                        /* Always insert in the second position.  */
                        fwd = fwd->fd;
                      else
                        {
                          victim->fd_nextsize = fwd;
                          victim->bk_nextsize = fwd->bk_nextsize;
                          if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
                            malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
                          fwd->bk_nextsize = victim;
                          victim->bk_nextsize->fd_nextsize = victim;
                        }
                      bck = fwd->bk;
                      if (bck->fd != fwd)
                        malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
                    }
                }

tcache attack

详细的tcache tricks可以看我后面更的这篇：https://kotoriseed.gitee.io/2022/04/11/tcache%20summary/

leak libc

管理主线程的heap的main_arena是libc的一个静态全局变量，而且像small bin这样的，有fd和bk指针维护的双链表必会有一个指针指向main_arena上的bins数组的某个位置，由此就能得到libc上的地址。

leak出main_arena的地址:

1.制造堆块overlap

2.利用uaf

3.利用_IO_2_1_stdout _

有时程序不含输出堆块内容这个功能的时候，可以劫持_IO_2_1_stdout_，修改_flags成员，绕过setbuf(stdout, 0)，让程序下一次调用输出函数的时候，将 _IO_write_base和 _IO_write_ptr之间的内容打印出来。然后再结合vmmap得到基址，利用libc_base + libc.symbols[‘__malloc_hook’] + 0x10得到。

算出基址:

1.通过vmmap直接算

2.利用__malloc_trim()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int __malloc_trim (size_t s)
{
  int result = 0;

  if (__malloc_initialized < 0)
    ptmalloc_init ();

  mstate ar_ptr = &main_arena;  //<=here!
  do
    {
      __libc_lock_lock (ar_ptr->mutex);
      result |= mtrim (ar_ptr, s);
      __libc_lock_unlock (ar_ptr->mutex);

      ar_ptr = ar_ptr->next;
    }
  while (ar_ptr != &main_arena);

  return result;
}

这个函数用到了main_arena的地址，所以是可以直接在ida里分析的时候算的。

3.利用__malloc_hook()

__malloc_hook和main_arena的偏移是0x10，所以可以很方便的算出来。

结语

接下来的更高级的手法，或者更具体的利用，我将在其他文章里面结合实际例子更新。