Large-Bin-Attack

September 3, 2019 PWN 访问: 25 次

参考文献

raycp
相对于small bins来说,大于small bins最大chunk_size的chunk会进入到large bins中;而large binssmall binsfast bins相比,管理方法是有很大区别的
large bins分为63个bin,每个bin中的chunk_size并不是同样大的,而是每个bin中都是一个固定公差的等差数列,但是每个bin和每个bin的这个固定公差又是不一样的,这63个bin分成6组,数量分别是32、16、8、4、2、1,公差依此是64B、512B、4096B、32768B、262144B。
glibc源码定义largebins如下所示(虽然我也没看懂)

#define largebin_index_32(sz)                                                \
  (((((unsigned long) (sz)) >> 6) <= 38) ?  56 + (((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)
#define largebin_index_32_big(sz)                                            \
  (((((unsigned long) (sz)) >> 6) <= 45) ?  49 + (((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)
// XXX It remains to be seen whether it is good to keep the widths of
// XXX the buckets the same or whether it should be scaled by a factor
// XXX of two as well.
#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)

根据自己的理解得出下面结论:

size index
[0x400 , 0x440) 64
[0x440 , 0x480) 65
[0x480 , 0x4C0) 66
[0x4C0 , 0x500) 67
[0x500 , 0x540) 68
等差 0x40
[0xC00 , 0xC40) 96
[0xC40 , 0xE00) 97
[0xE00 , 0x1000) 98
[0x1000 , 0x1200) 99
[0x1200 , 0x1400) 100
[0x1400 , 0x1600) 101
等差 0x200
[0x2800 , 0x2A00) 111
[0x2A00 , 0x3000) 112
[0x3000 , 0x4000) 113
[0x4000 , 0x5000) 114
等差 0x1000
[0x9000 , 0xA000) 119
[0xA000 , 0x10000) 120
[0x10000 , 0x18000) 121
[0x18000 , 0x20000) 122
[0x20000 , 0x28000) 123
[0x28000 , 0x40000) 124
[0x40000 , 0x80000) 125
[0x80000 , …. ) 126

在largebin中,每个bin中是有两个链表来维护,具体来调试一下:

#include<stdio.h>
#include<stdlib.h>
int main()
{
    char *gap;
    char *ptr0 = malloc(0x400 - 0x10); //A
    gap = malloc(0x10);
    char *ptr1 = malloc(0x410 - 0x10); //B
    gap = malloc(0x10);
    char *ptr2 = malloc(0x420 - 0x10); //C
    gap = malloc(0x10);
    char *ptr3 = malloc(0x430 - 0x10); //D
    gap = malloc(0x10);
    free(ptr2);
    free(ptr3);
    free(ptr0);
    free(ptr1);
    malloc(0x440); //trigger that sort largebin from unsorted bin to largebins
    return 0;
}

首先我们申请chunk(大小全部落在largebin的第一个bin中,也就是[0x400 , 0x440) ),然后让其全部进入到unsorted bin中,然后再malloc一个不同大小的chunk,触发使刚刚的chunk进入到largebin中,根据再gdb中的调试信息画出结构图

从图中可以看出来fd_nextsize和bk_nextsize也起到了一定的作用,首先是fd和bk指针构成了一个双向链表,这个链表的作用就是将一个bin中所有的chunk都链在一起
而fd_nextsize和bk_nextsize构成的双向链表是为了把在同一个bin中大小不同的chunk给链接到一块,再来看一个例子

#include <stdio.h>
#include <stdlib.h>
int main()
{
    char *gap;
    char *ptr0 = malloc(0x400 - 0x10); //A
    printf("A:%p\n",ptr0);
    gap = malloc(0x10);
    char *ptr1 = malloc(0x410 - 0x10); //B
    printf("B:%p\n", ptr1);
    gap = malloc(0x10);
    char *ptr2 = malloc(0x420 - 0x10); //C
    printf("C:%p\n", ptr2);
    gap = malloc(0x10);
    char *ptr3 = malloc(0x430 - 0x10); //D
    printf("D:%p\n", ptr3);
    gap = malloc(0x10);
    char *ptr4 = malloc(0x400 - 0x10); //E
    printf("E:%p\n", ptr4);
    gap = malloc(0x10);
    char *ptr5 = malloc(0x410 - 0x10); //F
    printf("F:%p\n", ptr5);
    gap = malloc(0x10);
    char *ptr6 = malloc(0x420 - 0x10); //G
    printf("G:%p\n", ptr6);
    gap = malloc(0x10);
    char *ptr7 = malloc(0x430 - 0x10); //H
    printf("H:%p\n", ptr7);
    gap = malloc(0x10);
    char *ptr8 = malloc(0x400 - 0x10); //I
    printf("I:%p\n", ptr8);
    gap = malloc(0x10);
    char *ptr9 = malloc(0x410 - 0x10); //J
    printf("J:%p\n", ptr9);
    gap = malloc(0x10);
    char *ptr10 = malloc(0x420 - 0x10); //K
    printf("K:%p\n", ptr10);
    gap = malloc(0x10);
    char *ptr11 = malloc(0x430 - 0x10); //L
    printf("K:%p\n", ptr11);
    gap = malloc(0x10);
    free(ptr2); //C
    free(ptr3); //D
    free(ptr0); //A
    free(ptr1); //B
    free(ptr7); //H
    free(ptr6); //G
    free(ptr5); //F
    free(ptr4); //E
    free(ptr11); //L
    free(ptr10); //K
    free(ptr9);  //J
    free(ptr8); //I
    malloc(0x440); //trigger that sort largebin from unsorted bin to largebins
    return 0;
}

根据调式信息画出示意图,这幅图是通过fd和bk指针构成了一个双向链表

这幅图是通过fd_nextsize和bk_nextsize指针构成了一个双向链表

这两幅图表示的是同一个bin中的chunk,可以鲜明的看出来fd_nextsize和bk_nextsize指针的作用,fd_nextsize指针指向相邻下一个比它小的chunk地址,而bk_nextsize指针指向相邻上一个比它大的chunk地址
通过看glibc源码来看在unsorted bin中的chunk是如何分配到了smallbin和largebin中
/glibc-2.23/malloc/malloc.c:3532

          /* place chunk in bin */
          if (in_smallbin_range (size))//这里首先验证时进入smallbins还是largebins
            {//进入smallbins
              victim_index = smallbin_index (size);
              bck = bin_at (av, victim_index);
              fwd = bck->fd;
            }
          else
            {//进入largebins
              victim_index = largebin_index (size);//获取要插入的bins对应的index
              bck = bin_at (av, victim_index);//获取该bin中最小的chunk
              fwd = bck->fd;//获取该bin中最小的chunk
              /* 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 ((bck->bk->size & NON_MAIN_ARENA) == 0);
                  if ((unsigned long) (size) < (unsigned long) (bck->bk->size))//如果要插入的chunk的size小于当前bin中最小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
                    {//如果插入的chunk不为最小,则通过fd_nextsize从大到小遍历chunk,找到小于等于要插入chunk的位置
                      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
                        {否则这个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//如果bin是空的话,直接设置fd_nextsize 和bk_nextsize 是自己本身
                victim->fd_nextsize = victim->bk_nextsize = victim;
            }

unsortedbin中的chunk到largebin中的流程

  • 首先是先判断进入smallbin还是largebin
  • 若是进入largebin中,首先是获取到该chunk应进入到哪一个index的bin中,简单的来说就是获取index
  • 获取该indexbin的最大chunk和最小chunk
  • 判断最大chunk和最小chunk是否不相等,也就是判断这个bin是否为空
  • 如果为空的话就直接将这个chunk这设置成堆头
  • 如果不为空,就判断该chunk的size是不是最小的,若是最小的话直接插入到最后,若不是,则会按照fd_nextsize遍历,直到找到合适的位置
  • 然后判断是不是堆头(是不是该大小的第一个chunk),如果是的话就设置好fd_nextsize 和bk_nextsize ,若不是的话都置为0

在largebin中的chunk是如何分配出去的

  • 先是更具申请的大小找到合适的largebin,然后比较是否大于第一个节点
  • 若大于第一个节点,从最小的chunk开始反向遍历,直到找到第一个大于等于所需要的大小的chunk就退出循环
  • 如果申请大小的chunk是存在多个节点,那么则申请堆头的下一个节点,不申请堆头,以此来减少对bk_nextsize和fd_nextsize的操作
  • 然后进行unlink操作

/glibc-2.23/malloc/malloc.c:3604

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

largebin的unlink操作可以分为两类,第一类是unlink不是堆头的chunk,那就和unsortedbin是一样的,fd_nextsize和bk_nextsize指针并不参与unlink的操作;第二类是unlink是堆头的chunk,现在fd_nextsize和bk_nextsize就要出场了,那不仅要操作fd和bk指针,而且要操作fd_nextsize和bk_nextsize指针
/glibc-2.23/malloc/malloc.c:1414

#define unlink(AV, P, BK, FD) {                                            \
    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;             \
              }                                   \
          }                                   \
      }                                       \
}

可以看出来,相比unsorted bin的unlink操作只是多了对bk_nextsize 和fd_nextsize指针的操作。

这里应该注意的是,当插入largebin时是通过fd_nextsize指针从大到小遍历的,而取出的时候是通过bk_nextsize指针从小到大进行遍历

利用方式

申请largebin的过程

当我们可以控制已经到达largebin中的chunk时,我们对chunk的bk_nextsize指针进行伪造,就可以制定地址申请成为chunk

unsorted bin中进入到largebin中的时候

伪造fwd的bk_nextsize指针,

可以达到效果:

victim->bk_nextsize=target
target->fd_nextsize(target+0x20)=victim

伪造fwd的bk指针

达到效果:

bck = target
target->fd(target+0x10)=victim

添加新评论