largebin_attack

发表于 | 分类于 |

0x00 前言

largebin attack 以前就是稍微看过，没怎么做过题，这里总结下largebin的管理机制,然后做一两道题练手然后就开始深入内核pwn的学习了。感觉自己刷题还是不够，等以赛代练吧。

0x01 lagrgebin 管理机制

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

组 数量 公差
1 32 64B
2 16 512B
3 8 4096B
4 4 32768B
5 2 262144B
6 1 不限制

与smallbin不同的是，largebin中不再是一个index只对应一个大小的size，而是存储等差数列变化的chunk块。其相关定义如下：

这个宏写的真的是十分优雅

1
2
3
4
5
6
7
#define largebin_index_64(sz)                                                \
  (((((unsigned long) (sz)) >> 6) <= 48) ?  48 + (((unsigned long) (sz)) >> 6) :\
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
   126)

largebin管理的是一个范围区间的堆块，此时fd_nextsize与bk_nextsize就派上了用场。

大小对应相同index中的堆块，其在链表中的排序方式为：

  • 堆块从大到小排序。

  • 对于相同大小的堆块，最先释放的堆块会成为堆头，其fd_nextsize与bk_nextsize会被赋值，其余的堆块释放后都会插入到该堆头结点的下一个结点，通过fd与bk链接，形成了先释放的在链表后面的排序方式，且其fd_nextsize与bk_nextsize都为0。

  • 不同大小的堆块通过堆头串联，即堆头中fd_nextsize指向比它小的堆块的堆头，bk_nextsize指向比它大的堆块的堆头，从而形成了第一点中的从大到小排序堆块的方式。同时最大的堆块的堆头的bk_nextsize指向最小的堆块的堆头，最小堆块的堆头的fd_nextsize指向最大堆块的堆头，以此形成循环双链表。

接下来具体看源码中是如何实现将largebin chunk从unsorted bin中取下来放入到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
/* place chunk in bin */

          if (in_smallbin_range (size))
            {
              ...  // chunk为smallbin，放入到smallbin中
            }
          else
            {
              victim_index = largebin_index (size);//第一步，获取当前要插入的chunk对应的index
              bck = bin_at (av, victim_index); //当前index中最小的chunk
              fwd = bck->fd;                   //当前index中最大的chunk

              /* maintain large bins in sorted order */
              if (fwd != bck)
                { // 该chunk对应的largebin index中不为空
                  /* Or with inuse bit to speed comparisons */
                  size |= PREV_INUSE;
                  /* if smaller than smallest, bypass loop below */
                  assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
                  if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) //第三步，如果要插入的chunk的size小于当前index中最小chunk的大小，则直接插入到最后面。
                    {
                      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 ((fwd->size & NON_MAIN_ARENA) == 0);
                      while ((unsigned long) size < fwd->size) //第四步，如果插入的chunk不为最小，则通过`fd_nextsize`从大到小遍历chunk，找到小于等于要插入chunk的位置
                        {
                          fwd = fwd->fd_nextsize;
                          assert ((fwd->size & NON_MAIN_ARENA) == 0);
                        }

                      if ((unsigned long) size == (unsigned long) fwd->size)
                        /* Always insert in the second position.  */
                        fwd = fwd->fd; //第五步，如果存在堆头，则插入到堆头的下一个节点
                      else
                        { //第六步，否则这个chunk将会成为堆头，`bk_nextsize`和`fd_nextsize`将被置位
                          victim->fd_nextsize = fwd;
                          victim->bk_nextsize = fwd->bk_nextsize;
                          fwd->bk_nextsize = victim;
                          victim->bk_nextsize->fd_nextsize = victim;
                        }
                      bck = fwd->bk;
                    }
                }
              else   //第二步，chunk对应的largebin index中为空
                victim->fd_nextsize = victim->bk_nextsize = victim;
            }

          mark_bin (av, victim_index);
          //设置fd与bk完成插入
          victim->bk = bck; 
          victim->fd = fwd;
          fwd->bk = victim;
          bck->fd = victim;
          ...
        }

整个流程可以总结为：

  1. 找到当前要插入的chunk对应的largebin的index，并定位该index中的最小的chunkbck和最大的chunkfwd。
  2. 如果fwd等于bck，表明当前链表为空，则直接将该chunk插入，并设置该chunk为该大小堆块的堆头，将bk_nextsize和fd_nextsize赋值为它本身。
  3. 如果fwd不等于bck，表明当前链表已经存在chunk，要做的就是找到当前chunk对应的位置将其插入。首先判断其大小是否小于最小chunk的size，(size) < (bck->bk->size)，如果小于则说明该chunk为当前链表中最小的chunk，即插入位置在链表末尾，无需遍历链表，直接插入到链表的末尾，且该chunk没有对应的堆头，设置该chunk为相应堆大小堆的堆头，将bk_nextsize指向比它大的堆头，fd_nextsize指向双链表的第一个节点即最大的堆头。
  4. 如果当前chunk的size不是最小的chunk，则从双链表的第一个节点即最大的chunk的堆头开始遍历，通过fd_nextsize进行遍历，由于fd_nextsize指向的是比当前堆头小的堆头，因此可以加快遍历速度。直到找到小于等于要插入的chunk的size。
  5. 如果找到的chunk的size等于要插入chunk的size，则说明当前要插入的chunk的size已经存在堆头，那么只需将该chunk插入到堆头的下一个节点。
  6. 如果找到的chunk的size小于当前要插入chunk的size，则说明当前插入的chunk不存在堆头，因此该chunk会成为堆头插入到该位置，设置fd_nextsize与bk_nextsize。

通过源码分析可以与之前的排序方式对应上，接下来我们再看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
/*
         If a large request, scan through the chunks of current bin in
         sorted order to find smallest that fits.  Use the skip list for this.
       */
      if (!in_smallbin_range (nb))
        {
          bin = bin_at (av, idx); //找到申请的size对应的largebin链表

          /* skip scan if empty or largest chunk is too small */
          if ((victim = first (bin)) != bin &&
              (unsigned long) (victim->size) >= (unsigned long) (nb)) //第一步，判断链表的第一个结点，即最大的chunk是否大于要申请的size
            {
              victim = victim->bk_nextsize; 
              while (((unsigned long) (size = chunksize (victim)) <
                      (unsigned long) (nb))) //第二步，从最小的chunk开始，反向遍历 chunk size链表，直到找到第一个大于等于所需chunk大小的chunk退出循环
                victim = victim->bk_nextsize; 

              /* Avoid removing the first entry for a size so that the skip
                 list does not have to be rerouted.  */
              if (victim != last (bin) && victim->size == victim->fd->size) //第三步，申请的chunk对应的chunk存在多个结点，则申请相应堆头的下个结点，不申请堆头。
                victim = victim->fd;

              remainder_size = size - nb;
              unlink (av, victim, bck, fwd); //第四步，largebin unlink 操作

              /* Exhaust */
              if (remainder_size < MINSIZE) //第五步，如果剩余的空间小于MINSIZE，则将该空间直接给用户
                {
                  set_inuse_bit_at_offset (victim, size);
                  if (av != &main_arena)
                    victim->size |= NON_MAIN_ARENA;
                }
              /* Split */
              else
                {
                  remainder = chunk_at_offset (victim, nb); //第六步，如果当前剩余空间还可以构成chunk，则将剩余的空间放入到unsorted bin中。
                  /* We cannot assume the unsorted list is empty and therefore
                     have to perform a complete insert here.  */
                  bck = unsorted_chunks (av);
                  fwd = bck->fd;
      if (__glibc_unlikely (fwd->bk != bck))
                    {
                      errstr = "malloc(): corrupted unsorted chunks";
                      goto errout;
                    }
                  remainder->bk = bck;
                  remainder->fd = fwd;
                  bck->fd = remainder;
                  fwd->bk = remainder;
                  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;
            }
        }

可以将整个流程总结为：

  1. 找到当前要申请的空间对应的largebin链表，判断第一个结点即最大结点的大小是否大于要申请的空间，如果小于则说明largebin中没有合适的堆块，需采用其他分配方式。

  2. 如果当前largebin中存在合适的堆块，则从最小堆块开始，通过bk_nextsize反向遍历链表，找到大于等于当前申请空间的结点。

  3. 为减少操作，判断找到的相应结点（堆头）的下个结点是否是相同大小的堆块，如果是的话，将目标设置为该堆头的第二个结点，以此减少将fd_nextsize与bk_nextsize赋值的操作。

  4. 调用unlink将目标largebin chunk从双链表中取下。

  5. 判断剩余空间是否小于MINSIZE，如果小于直接返回给用户。

  6. 否则将剩余的空间构成新的chunk放入到unsorted bin中。

再看下unlink的源码：

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

/* Take a chunk off a bin list */
#define unlink(AV, P, BK, FD) {                                            \
    if (__builtin_expect (chunksize(P) != (next_chunk(P))->prev_size, 0))      \
      malloc_printerr (check_action, "corrupted size vs. prev_size", P, AV);  \
    FD = P->fd;                                      \
    BK = P->bk;                                      \
    if (__builtin_expect (FD->bk != P || BK->fd != P, 0))              \
      malloc_printerr (check_action, "corrupted double-linked list", P, AV);  \
    else {                                      \
        FD->bk = BK;                                  \
        BK->fd = FD;                                  \
        if (!in_smallbin_range (P->size)                      \
            && __builtin_expect (P->fd_nextsize != NULL, 0)) {              \
        if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0)          \
        || __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0))    \
          malloc_printerr (check_action,                      \
                   "corrupted double-linked list (not small)",    \
                   P, AV);                          \
            if (FD->fd_nextsize == NULL) {                      \
                if (P->fd_nextsize == P)                      \
                  FD->fd_nextsize = FD->bk_nextsize = FD;              \
                else {                                  \
                    FD->fd_nextsize = P->fd_nextsize;                  \
                    FD->bk_nextsize = P->bk_nextsize;                  \
                    P->fd_nextsize->bk_nextsize = FD;                  \
                    P->bk_nextsize->fd_nextsize = FD;                  \
                  }                                  \
              } else {                                  \
                P->fd_nextsize->bk_nextsize = P->bk_nextsize;              \
                P->bk_nextsize->fd_nextsize = P->fd_nextsize;              \
              }                                      \
          }                                      \
      }                                          \
}

再看看largebin的unlink检查，从代码中可以看到，就是多了fd_nextsize和bk_nextsize俩个位置的检查，原理和fd和bk的检查一致。但是需要注意的是对于存在多个满足空间的堆块来说，申请出来的是堆头的下一个结点，它的fd_nextsize和bk_nextsize为空。也就是说即使它是largebin chunk，但是它的fd_nextsize也为空，即不满足条件__builtin_expect (P->fd_nextsize != NULL, 0)，对于此类chunk的unlink，只会像smallbin的unlink一样检查fd与bk，而不会对fd_nextsize与bk_nextsize进行检查与操作。

至此largebin链表的形成以及申请largebin都已经阐述清楚。再小结下，对于largebin的链表的插入，双链表是从大到小的chunk排序，相同大小的chunk会有一个堆头，只有堆头的fd_nextsize与bk_nextsize会被赋值，其余堆块的该字段为0。插入的遍历是通过fd_nextsize从大到小进行的，如果该插入的chunk存在对应堆头，则插入到该堆头的下一个结点，否则的话该chunk会成为堆头插入到链表中。

对于largebin的申请，通过判断双链表的第一个结点（最大结点）的大小来判断是否存在满足的堆块，如果有则从小到大通过bk_nextsize反向遍历双链表，找到最小的满足申请需求的堆块，如果该堆头下一个结点的大小也满足则将该结点作为目标分配给用户，以此减少链表的fd_nextsize与bk_nextsize操作，提高效率。对于双链表的unlink，需要注意的就是fd_nextsize与bk_nextsize检查，特别需要注意的是当结点是堆头的下一个结点时，它的fd_nextsize与bk_nextsize为0，此时unlink操作与smallbin的unlink操作一致，没有fd_nextsize与bk_nextsize的检查与操作。

0x02 largebin attack

largebin attack是在largebin双链表的插入与取下的过程中出现问题，导致可以被申请出非预期内存的情形。总的来说存在两种攻击方式：

  • 在申请largebin的过程中，伪造largebin的bk_nextsize，实现非预期内存申请。

  • 在largebin插入的过程中，伪造largebin的bk_nextsize以及bk，实现任意地址写堆地址。

下面结合源码和实例具体看这两种攻击方式。

2.1 伪造伪造largebin的bk_nextsize

原理分析

此利用方式是在申请largebin的过程中出现的。回到申请largebin的源码中去看，它先判断当前双链表中存在满足申请需求的堆块（判断第一个堆块的大小），然后通过bk_nextsize反向遍历双链表找到第一个大于申请需求的堆块，申请该堆头对应的堆块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if ((victim = first (bin)) != bin &&
              (unsigned long) (victim->size) >= (unsigned long) (nb)) //判断链表的第一个结点，即最大的chunk是否大于要申请的size
            {
              victim = victim->bk_nextsize; 
              while (((unsigned long) (size = chunksize (victim)) <
                      (unsigned long) (nb))) //从最小的chunk开始，反向遍历 chunk size链表，直到找到第一个大于等于所需chunk大小的chunk退出循环
                victim = victim->bk_nextsize;  //漏洞点，伪造bk_nextsize

              if (victim != last (bin) && victim->size == victim->fd->size) //申请的chunk对应的chunk存在多个结点，则申请相应堆头的下个结点，不申请堆头。
                victim = victim->fd;

              remainder_size = size - nb;
              unlink (av, victim, bck, fwd); //largebin unlink 操作

            ... 
            return p;

问题出现在通过bk_nextsize反向遍历双链表的过程，如果能够伪造某个堆头结点中的bk_nextsize，将其指向非预期的内存地址，构造好数据使得非预期内存地址在通过unlink的检查之后，会将该空间返回给用户，最终使得可以申请出非预期的内存。最常见的就是用它来构造overlap chunk。

至于绕过unlink的检查，我认为最好的方式就是伪造的内存空间将fd与bk按照smallbinunlink的利用方式设置，而将bk_nextsize和fd_nextsize设置成0，这样就不会对这两个字段进行操作了。

典型的应用场景为：存在四个堆ABCD，largebin中存在链表A->B，其中A为0x420，B为0x400，C为0x410，C未释放。将B的bk_nextsize伪造指向C，同时将C的fd与bk构造好，将C的fd_nextsize与bk_nextsize赋值为0，当再次申请0x410大小的内存E时，遍历B->bk_nextsize会指向C，且C的大小满足需求，因此会调用unlink将C从双链表取下，因此申请出来的堆块E的地址会为C的地址，即E和C为同一内存块，实现overlap chunk的构造。

-------------本文结束感谢您的阅读-------------
+ +