『glibc源码补完计划』UnsortedBin

glibc_2.23，除非特别说明，否则下文默认为此版本下的分析。

UnsortedBin

最近学习堆题的时候接触到了unsortedbin的利用，感觉还挺有意思的，所以先把它的源码读了，方便以后构建利用思路。之所以这里分析glibc2.23的代码而非2.35的代码，是因为从2.29开始，unsortedbin加入了一坨检查机制以至于它在高版本下难以被攻击，所以索性读低版本的了。

glibc2.23在unsortedbin中取chunk的时候的检查：

1
2
if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)|| __builtin_expect (victim->size > av>system_mem, 0))
            malloc_printerr (check_action, "malloc(): memory corruption",chunk2mem (victim), av);

glibc2.29对unsortedbin链表完整性的检查：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bck = victim->bk;
       size = chunksize (victim);
       mchunkptr next = chunk_at_offset (victim, size);

       if (__glibc_unlikely (size <= 2 * SIZE_SZ)
           || __glibc_unlikely (size > av->system_mem))
         malloc_printerr ("malloc(): invalid size (unsorted)");
       if (__glibc_unlikely (chunksize_nomask (next) < 2 * SIZE_SZ)
           || __glibc_unlikely (chunksize_nomask (next) > av->system_mem))
         malloc_printerr ("malloc(): invalid next size (unsorted)");
       if (__glibc_unlikely ((prev_size (next) & ~(SIZE_BITS)) != size))
         malloc_printerr ("malloc(): mismatching next->prev_size (unsorted)");
       if (__glibc_unlikely (bck->fd != victim)
           || __glibc_unlikely (victim->fd != unsorted_chunks (av)))
         malloc_printerr ("malloc(): unsorted double linked list corrupted");
       if (__glibc_unlikely (prev_inuse (next)))
         malloc_printerr ("malloc(): invalid next->prev_inuse (unsorted)");

Unsorted Bin的基本情况 & 对一些变量的理解

当用户申请一块堆内存的时候，malloc会先去fast bin里找适合的chunk，如果没有则去找small bin，如果还没有这才去找unsorted bin。也就是说如果考虑unsorted bin attack，那就要先考虑到前面两个bin的影响。unsorted bin是一个双向链表，取放的原则是FIFO。最先放入的chunk我们叫尾部，最后放入的叫头部，取出chunk的时候是从尾部取的。

unsorted_chunks(av): unsorted bin的堆头。unsorted bin一旦被使用，就会初始化这个堆头，它和main_arena在相同glibc版本下有着固定偏移（比如glibc2.23中是main_arena+0x58）。
av: 一个指向当前arena地址的指针，也就是指向分配区的指针。
victim: 指当前unsorted bin链表中处于尾部的chunk。
bck: victim的上一个chunk。
nb: 用户申请的chunk大小，包括了维护chunk的0x10结构部分。
remainder: unsorted bin中的chunk被切割后剩下的部分。
last_remainder: 最后一次被切割的chunk剩下的部分。

Unsorted Bin由一个循环的双向链表维护，也就是说，链表的头部chunk的bk会指向堆头，而尾部chunk的fd也会指向堆头，如下图所示（chunk0先被释放可看做尾部，chunk1后被释放可看做头部）：

unsortedbin循环链表

不难想象，如果unsorted bin中只含有一个chunk，那么这个chunk的fd和bk都会指向堆头，堆头的fd和bk都会指向这个chunk。

malloc时unsorted bin的行为

接下来我们将源码分段来分析。以下分析顺序基于unsorted bin的行为顺序。

一些基本检查
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (;; )
    {
      int iters = 0;
      while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
        {
          bck = victim->bk;
          if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
              || __builtin_expect (victim->size > av->system_mem, 0))
            malloc_printerr (check_action, "malloc(): memory corruption",
                             chunk2mem (victim), av);
          size = chunksize (victim);

		/*其他的下面再看*/

        }

     }

这段代码检查了unsorted bin中是否含有chunk，设置了victim和bck两个变量，并且检查victim的size字段。这个检查相当地简单，所以给予了我们攻击的可能。当然，这种可能在2.29之后概率就很低了。

对唯一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
/*
          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) && //用户申请的大小在smallbin范围中
           bck == unsorted_chunks (av) && //unsorted bin中只有唯一chunk
           victim == av->last_remainder && //这个chunk是上一次被分割的chunk（包括尚未被分割的chunk）
           (unsigned long) (size) > (unsigned long) (nb + MINSIZE)) //这个chunk的size大于用户申请的大小+MINSIZE
         {
           /* split and reattach remainder */
           remainder_size = size - nb; //剩余部分的大小
           remainder = chunk_at_offset (victim, nb); //剩余部分的chunk地址
           unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder; //修改堆头的fd和bk
           av->last_remainder = remainder; //更新最后被分割的chunk指针
           remainder->bk = remainder->fd = unsorted_chunks (av); //修改剩余部分的fd和bk
           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)); //设置取出来的部分的size字段 
           set_head (remainder, remainder_size | PREV_INUSE); //设置剩余部分的size字段
           set_foot (remainder, remainder_size); //设置物理意义上下一个chunk的prev_size

           check_malloced_chunk (av, victim, nb); //对切割下来的chunk进行检查
           void *p = chunk2mem (victim); //返回mem指针给用户
           alloc_perturb (p, bytes);
           return p; 
         }

只有满足if条件后malloc才会去切割unsorted bin中的chunk以返回合适的chunk给用户，否则会直接进入下一步。

移除尾部chunk
1
2
3
/* remove from unsorted list */
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);

代码很简单，但是确实把尾部的chunk扔出了unsorted bin。之所以会有这么一步是因为只要上一步切割没实现，那么接下来无论如何尾部chunk都不可能留在unsorted bin里了，要么被分配到其他bin中，要么大小刚刚好而被返回给用户。

victim返回给用户
1
2
3
4
5
6
7
8
9
10
11
/* Take now instead of binning if exact fit */
if (size == nb)
  {
    set_inuse_bit_at_offset (victim, size);
    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;
  }

如果用户申请的chunk大小和victim的大小刚刚好一样，那太好了，直接把victim返回给用户，皆大欢喜。当然，除了会改一改标志位除外，其他地方不会动。也就是说，原本存在上面的fd和bk指针现在依然残留在上面，那就可以利用这一点来泄露libc地址了。

victim进入到small bin或large bin中
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
          /* place chunk in bin */
		 /*核心的放置步骤在57行*/
          if (in_smallbin_range (size)) //如果victim在smallbin范围中（size<0x400）
            {
              victim_index = smallbin_index (size); //找到对应size的bin的索引
              bck = bin_at (av, victim_index); //将bck设置为对应bin的地址
              fwd = bck->fd; //将fwd设置为对应bin当前的头部chunk
            }
          else //如果victim在largebin范围中
            {
              victim_index = largebin_index (size); //同上
              bck = bin_at (av, victim_index);
              fwd = bck->fd;

              /* maintain large bins in sorted order */
              /*下面一大坨看起来和复杂但其实它就在干一件事，那就是保持large bin内的chunk要按照size大小从小到大排序*/
              if (fwd != bck)
                {
                  /* 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))
                    {
                      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)
                        {
                          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
                        {
                          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;
            }

		 /*放置chunk到对应bin的核心步骤，也就是设置fd和bk增加链表节点*/
          mark_bin (av, victim_index); //将victim要进入的bin的binmap设置为1，意味着这个bin里包含空闲chunk
          victim->bk = bck;
          victim->fd = fwd;
          fwd->bk = victim;
          bck->fd = victim;

/*然后返回到while处重新找下一个chunk是否能满足用户需求然后返回，除非unsorted bin已经空了，或者已经循环了MAX_ITERS次*/
#define MAX_ITERS       10000
          if (++iters >= MAX_ITERS)
            break; //这个break是给最初那个while用的，这里也是while语句块的最后一个语句了。
依然找不到合适chunk的解决办法

如果unsorted bin已经空了或者循环次数过多了，但是还找不到合适的chunk给用户，ptmalloc就开largebin去找大小最合适的chunk，这个chunk大小可能比需要的还要大，所以会把它放进unsorted bin中进行切割。如果还没有，ptmalloc急了就会开地图炮去找合适的chunk来切割。实在没有的话，那就只能去切割top chunk了，或者合并fastbin亦或者直接sysmalloc，此处不做分析。

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
/*
      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);

       /* skip scan if empty or largest chunk is too small */
       if ((victim = first (bin)) != bin &&
           (unsigned long) (victim->size) >= (unsigned long) (nb))
         {
           victim = victim->bk_nextsize;
           while (((unsigned long) (size = chunksize (victim)) <
                   (unsigned long) (nb)))
             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)
             victim = victim->fd;

           remainder_size = size - nb;
           unlink (av, victim, bck, fwd);

           /* Exhaust */
           if (remainder_size < 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);
               /* 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;
         }
       /*至此，最开始的for语句块结束了*/

free时unsorted bin的行为

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
     /*
Place the chunk in unsorted chunk list. Chunks are
not placed into regular bins until after they have
been given one chance to be used in malloc.
     */

     bck = unsorted_chunks(av); //将要被free的chunk插入链表头部
     fwd = bck->fd; 
     if (__glibc_unlikely (fwd->bk != bck)) //检查当前头部chunk的bk是否被破坏，对unsorted bin来说bk很重要
{
  errstr = "free(): corrupted unsorted chunks";
  goto errout;
}
     p->fd = fwd; //设置被free的chunk的fd和bk指针
     p->bk = bck;
     if (!in_smallbin_range(size))
{
  p->fd_nextsize = NULL;
  p->bk_nextsize = NULL;
}
     bck->fd = p; //插入链表
     fwd->bk = p;

     set_head(p, size | PREV_INUSE); //设置size字段
     set_foot(p, size); //设置物理相邻chunk的prev_size

     check_free_chunk(av, p);
   }

chunk被释放后会进入unsorted bin有以下几种情况：
- 这个chunk不属于fastbin范围，则会先进入unsorted bin
- unsorted bin中的chunk被切割后，剩余部分如果大于MINSIZE，则会继续放回到unsorted bin中
- 触发malloc_consolidate之后，合并好的的chunk会先被放到unsorted bin中
- 这个chunk不与top chunk相邻，否则会被top chunk合并

关于这些情况的源码分析将在另一篇文章中进行。

参考阅读：
- heap 中常见函数、宏与值

本博客采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议(CC BY-NC-SA 4.0) 发布.
因本人技术水平和知识面有限, 内容如有纰漏或者需要修正的地方, 欢迎大家指正。转载请注明来自C_LBY's blog！
Page View
⬆︎TOP