Pwn进你的心
0%

Ptmalloc算法：Fastbin Attack

Posted on Edited on In 9.7k 9 mins.

Ptmalloc算法：Fastbin Attack

广义上来说，涉及到 Fastbin 的攻击都是 Fastbin Attack，这也是堆利用中的一个大类

利用方式十分灵活：Double free，House Of Spirit……都是它的分支

作用效果也多样：申请到“malloc_hook”打“one_gadget”，申请到栈上打“stackoverflow”……

Fastbin bin

Fast bin可以看着是small bins的一小部分cache ，设计初衷就是进行快速的小内存分配和释放

基础信息：

Fast bin通常有7条链表

  • 32位：16-64字节 0x10-0x40
  • 64位：32-128字节 0x20-0x80

fastbinsY 是一个数组，相同大小的 chunk 放在一个数组元素指向的链表里面

先不管 fastbin 的分配方式，主要分析释放过程：

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
51
52
53
54
55
56
57
58
59
60
61
62
63
#define fastbin_index(sz) ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

static void _int_free (mstate av, mchunkptr p, int have_lock)
{
  size = chunksize (p);    //获取p的size
  check_inuse_chunk(av, p);//检查p的物理相邻的下一个堆块的inuse位是否置1

  //检查p的大小是否小于global_max_fast
  if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())
      #if TRIM_FASTBINS
          //检查p物理相邻的堆块是否是top chunk
          && (chunk_at_offset(p, size) != av->top)
      #endif
      ) 
  {
    //检查p的物理相邻下个堆块是否存在,且大小是否满足最小和最大要求
    if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
	       || __builtin_expect (chunksize (chunk_at_offset (p, size))
			     >= av->system_mem, 0))
        {.......}

	//对chunk的data块通过memset赋值，但是默认情况下是不进行操作    
    free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
    //设置 malloc_state的flag
    set_fastchunks(av);

    //获取p对应大小的fastbinY的索引
    unsigned int idx = fastbin_index(size);
    //fb指向对应大小的fastbinY的地址
    fb = &fastbin (av, idx);

    /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */
    // old为 对应大小的fastbinY的fd值，也就是第一个对块的地址
    mchunkptr old = *fb, old2;
    unsigned int old_idx = ~0u;
    
    do
      {
      	 // Check that the top of the bin is not the record we are going to add
         //检查 fastbin中对应的bin的第一项 是否 等于 p (新加入的堆块)
        	if (__builtin_expect (old == p, 0))
      	  {
      	    errstr = "double free or corruption (fasttop)";
      	    goto errout;
      	  }
          //获取 fastbin中对应的bin的第一项的索引。
        	if (have_lock && old != NULL)
        	  old_idx = fastbin_index(chunksize(old));
          //让  p 的fd指向 顶部的fastbin块
        	p->fd = old2 = old;
    }
    while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
    //catomic_compare_and_exchange_val_rel 功能是 如果*fb等于old2，则将*fb存储为p，返回old2；
    // *fb=p 也就是 让对应fastbin的fd指向 p(新加入的堆块)

    //检查fastbin中对应的bin的第一项的大小是否与p(要添加的块)的大小相同。
    if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
      {
        	errstr = "invalid fastbin entry (free)";
        	goto errout;
      }
  }
}

​ // 64位中size可以在0～0xF之间浮动（“0x70”和“0x7f”属于同一个链表），32位同理

单向链表后进先出，fastbinsY 数组中每一个元素指向该链表的尾结点，尾结点在通过 fd 指针指向前一个节点

  • 插入头部（最前端）
  • 从前往后进行获取
1
2
3
4
5
free(ptr1);
free(ptr2);
free(ptr3);

fastbin: ptr3 -> ptr2 -> ptr1 // fast chunk 并不会合并

注意：

  • Fast bin是 单向链表 只有fd指针，没有bk指针
  • Fast chunk不会对其他free chunk进行合并
  • Fast bin中无论是 插入 还是 移除 fast chunk，都是对“头部”进行操作（操作FD指针），而不会对某个中间的fast chunk进行操作（ 最后释放的，最先申请 ）

通常情况下：

  • 如果chunk大小 小于“0x40(32位) / 0x80(64位)”，那么该chunk会直接存入Fast bin
  • 如果内存请求 小于“0x40(32位) / 0x80(64位)”，那么程序会优先在Fast bin中查找

Fastbin bin 合并

合并时机：

  • 情况一：在申请 large chunk 时
  • 情况二：当申请的 chunk 需要申请新的 top chunk 时
  • 情况三：free 的堆块大小大于 fastbin 中的最大 size（注意这里并不是指当前fastbin中最大 chunk 的size，而是指 fastbin 中所定义的最大 chunk 的 size，是一个固定值）

第一种情况：

在申请 large 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
if (in_smallbin_range (nb))
    // 申请的大小是否在smallbin所定义的大小中
  {
    idx = smallbin_index (nb);
    bin = bin_at (av, idx);
 
    if ((victim = last (bin)) != bin)
      {
        if (victim == 0) /* initialization check */
          malloc_consolidate (av); // 初始化fastbin
        else
          {
            bck = victim->bk;
  if (__glibc_unlikely (bck->fd != victim))
              {
                errstr = "malloc(): smallbin double linked list corrupted";
                goto errout;
              }
            set_inuse_bit_at_offset (victim, nb);
            bin->bk = bck;
            bck->fd = bin;
 
            if (av != &main_arena)
              victim->size |= NON_MAIN_ARENA;
            check_malloced_chunk (av, victim, nb);
            void *p = chunk2mem (victim);
            alloc_perturb (p, bytes);
            return p;
          }
      }
  }
else
    // 如果不是，则会对fastbin进行合并
  {
    idx = largebin_index (nb);
    if (have_fastchunks (av))
      malloc_consolidate (av); 
    /* 进行合并 */
  }

程序验证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
int main(){
    void *ptr1,*ptr2,*ptr3,*ptr4;
    ptr1 = malloc(0x20);
    ptr2 = malloc(0x20);
    ptr3 = malloc(0x30);          // avoid merge with top chunk
    strcpy(ptr1,"aaaaaaaa");
    strcpy(ptr2,"bbbbbbbb");
    strcpy(ptr3,"cccccccc");
    free(ptr1);
    free(ptr2);
    ptr4 = malloc(0x500);
}

两个 free 执行以后：

1
2
3
4
5
6
7
8
Free chunk (fastbins) | PREV_INUSE
Addr: 0x55555555b000
Size: 0x31
fd: 0x00

Free chunk (fastbins) | PREV_INUSE
Addr: 0x55555555b030
Size: 0x31

一个 malloc 执行以后：

1
2
3
4
5
Free chunk (smallbins) | PREV_INUSE
Addr: 0x55555555b000
Size: 0x61
fd: 0x7ffff7dd1bc8
bk: 0x7ffff7dd1bc8

第二种情况：

当申请的 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
victim = av->top;
size = chunksize (victim);
 
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
    // 判断top chunk的size是否足够我们进行下一次的分配
  {
    remainder_size = size - nb;
    remainder = chunk_at_offset (victim, nb);
    av->top = remainder;
    set_head (victim, nb | PREV_INUSE |
              (av != &main_arena ? NON_MAIN_ARENA : 0));
    set_head (remainder, remainder_size | PREV_INUSE);
 
    check_malloced_chunk (av, victim, nb);
    void *p = chunk2mem (victim);
    alloc_perturb (p, bytes);
    return p;
  }
 
else if (have_fastchunks (av))
    // 判断是否有fastbin的存在
  {
    malloc_consolidate (av);
    /* 进行合并 */
    if (in_smallbin_range (nb))
      idx = smallbin_index (nb);
    else
      idx = largebin_index (nb);
  }

else
  {
    void *p = sysmalloc (nb, av);
    if (p != NULL)
      alloc_perturb (p, bytes);
    /* 扩展top chunk */
    return p;
  }

程序验证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
int main(){
        void *ptr1,*ptr2,*ptr3,*ptr4,*ptr5;
        ptr1 = malloc(0x20);
        ptr2 = malloc(0x20);
        ptr3 = malloc(0x20f00);
        ptr4 = malloc(0x30);         
        strcpy(ptr1,"aaaaaaaa");
        strcpy(ptr2,"bbbbbbbb");
        strcpy(ptr3,"cccccccc");
        free(ptr1);
        free(ptr2);
        ptr5 = malloc(0x70);
}

申请最后一个chunk前：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Free chunk (fastbins) | PREV_INUSE
Addr: 0x55555555b000
Size: 0x31
fd: 0x00

Free chunk (fastbins) | PREV_INUSE
Addr: 0x55555555b030
Size: 0x31
fd: 0x55555555b000

Allocated chunk | PREV_INUSE
Addr: 0x55555555b060
Size: 0x20f11

Allocated chunk | PREV_INUSE
Addr: 0x55555557bf70
Size: 0x41

Top chunk | PREV_INUSE
Addr: 0x55555557bfb0
Size: 0x51

申请最后一个chunk后：

1
2
3
4
5
Free chunk (smallbins) | PREV_INUSE
Addr: 0x55555555b000
Size: 0x61
fd: 0x7ffff7dd1bc8
bk: 0x7ffff7dd1bc8

第三种情况：

在 free(chunk) 的时候，如果 chunk 的大小大于 fastbin 中所定义的最大堆块的大小，则进行合并

1
2
3
if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
  if (have_fastchunks(av))
malloc_consolidate(av);

程序验证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
int main(){
        void *ptr1,*ptr2,*ptr3,*ptr4;
        ptr1 = malloc(0x70);
        ptr2 = malloc(0x70);
        ptr3 = malloc(0x70);  // avoid merge with top chunk
        ptr4 = malloc(0x100);
        strcpy(ptr1,"aaaaaaaa");
        strcpy(ptr2,"bbbbbbbb");
        strcpy(ptr3,"cccccccc");
        free(ptr1);
        free(ptr2);
        free(ptr4);
}

free(ptr4) 执行前：

1
2
3
4
5
6
7
8
9
10
pwndbg> heap
Free chunk (fastbins) | PREV_INUSE
Addr: 0x55555555b000
Size: 0x81
fd: 0x00

Free chunk (fastbins) | PREV_INUSE
Addr: 0x55555555b080
Size: 0x81
fd: 0x55555555b000

free(ptr4) 执行后：

1
2
3
4
5
Free chunk (unsortedbin) | PREV_INUSE
Addr: 0x55555555b000
Size: 0x101
fd: 0x7ffff7dd1b78
bk: 0x7ffff7dd1b78

合并过程：

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
static void malloc_consolidate(mstate av)
{
    mfastbinptr*    fb;                 /* current fastbin being consolidated */
    mfastbinptr*    maxfb;              /* last fastbin (for loop control) */
    mchunkptr       p;                  /* current chunk being consolidated */
    mchunkptr       nextp;              /* next chunk to consolidate */
    mchunkptr       unsorted_bin;       /* bin header */
    mchunkptr       first_unsorted;     /* chunk to link to */

    /* These have same use as in free() */
    mchunkptr       nextchunk;
    INTERNAL_SIZE_T size;
    INTERNAL_SIZE_T nextsize;
    INTERNAL_SIZE_T prevsize;
    int             nextinuse;
    mchunkptr       bck;
    mchunkptr       fwd;

    /*
    If max_fast is 0, we know that av hasn't
    yet been initialized, in which case do so below
  */

    if (get_max_fast () != 0) {
        (av);

        unsorted_bin = unsorted_chunks(av);

        maxfb = &fastbin (av, NFASTBINS - 1);
        fb = &fastbin (av, 0);
        do {
            p = atomic_exchange_acq (fb, 0);
            if (p != 0) {
                do {
                    check_inuse_chunk(av, p);
                    nextp = p->fd;

                    /* Slightly streamlined version of consolidation code in free() */
                    size = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
                    nextchunk = chunk_at_offset(p, size);
                    nextsize = chunksize(nextchunk);

                    if (!prev_inuse(p)) {
                        prevsize = p->prev_size;
                        size += prevsize;
                        p = chunk_at_offset(p, -((long) prevsize));
                        unlink(av, p, bck, fwd);
                    }

                    if (nextchunk != av->top) {
                        nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

                        if (!nextinuse) {
                            size += nextsize;
                            unlink(av, nextchunk, bck, fwd);
                        } else
                            clear_inuse_bit_at_offset(nextchunk, 0);

                        first_unsorted = unsorted_bin->fd;
                        unsorted_bin->fd = p;
                        first_unsorted->bk = p;

                        if (!in_smallbin_range (size)) {
                            p->fd_nextsize = NULL;
                            p->bk_nextsize = NULL;
                        }

                        set_head(p, size | PREV_INUSE);
                        p->bk = unsorted_bin;
                        p->fd = first_unsorted;
                        set_foot(p, size);
                    }

                    else {
                        size += nextsize;
                        set_head(p, size | PREV_INUSE);
                        av->top = p;
                    }

                } while ( (p = nextp) != 0);

            }
        } while (fb++ != maxfb);
    }
    else {
        malloc_init_state(av);
        check_malloc_state(av);
    }
}
  • 首先将与该块相邻的下一块的PREV_INUSE置为 1
  • 如果相邻的上一块未被占用，则合并，再判断相邻的下一块是否被占用，若未被占用，则合并
  • 不管是否完成合并，都会把 fastbin 或者完成合并以后的 bin 放到 unsortbin 中（如果与 top chunk 相邻，则合并到 top chunk 中）

Fastbin bin Attack

最简单的 fastbin attack 就是 double free：

1
2
3
free(chunk1);
free(chunk2);
free(chunk1);
1
2
3
4
5
6
7
8
9
pwndbg> bins
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x0
0x50: 0x562efbf8d120 —▸ 0x562efbf8d170 ◂— 0x562efbf8d120
0x60: 0x0
0x70: 0x0
0x80: 0x0
  • 这样可以将同一个 chunk 申请两次，就有机会修改 free chunk

但常规的 fastbin 在申请的时候有一个检查：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (victim != 0)
  {
    if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
      {
        errstr = "malloc(): memory corruption (fast)";
      errout:
        malloc_printerr (check_action, errstr, chunk2mem (victim), av);
        return NULL;
      }
    check_remalloced_chunk (av, victim, nb);
    void *p = chunk2mem (victim);
    alloc_perturb (p, bytes);
    return p;
  }
  • 检查目标 fast chunk->size 是否符合 fast bin 规定的 size

这个检查需要我们格外伪造一个 chunk->size，通常有如下的处理方法：

  • 尝试在 free_hook + xxx 的地方错位申请一个 chunk，利用 free_hook 前面的 libc 地址，将其高位的 \x7f 当做 chunk->size
  • 使用 House Of Storm 的思路，利用 largebin attack 往目标地址附加错位写一个堆地址，将堆地址高位的 \x56 当做 chunk->size（堆头部地址只可能是 0x55 或者 0x56 ）
  • 首先完成 double free，并往 fast chunk->fd 中写入 chunk->size，当程序把 fastbin 中的 chunk 申请到只剩下 chunk->size 时停止，此时 chunk->size 会被写入 main_arena 中，然后再次 double free 劫持 main_arena 进而劫持 top chunk（PS：劫持 top chunk 后就优先打 malloc_hook，将 malloc_hook 前面的 libc 地址给当成是 top chunk->size）