Large bin attack

这种攻击方式主要利用的是 chunk 进入 bin 中的操作，在 malloc 的时候，遍历 unsorted bin 时，对每一个 chunk，若无法 exact-fit 分配或不满足切割分配的条件，就会将该 chunk 置入相应的 bin 中，而此过程中缺乏对 largebin 的跳表指针的检测。

源码分析

2.29及以下版本中

源代码参考自：https://www.cnblogs.com/Rookle/p/13140339.html#house_of_storm

       if (in_smallbin_range(size)) 
    {
        victim_index = smallbin_index(size);//获取size对应的smallbin的index
        bck = bin_at(av, victim_index);//bck指向size对应的smallbin的链表头
        //fwd指向size对应的smallbin的链表中的新加入的chunk(small bin使用头插法)
        fwd = bck->fd;
    }
    else//如果不再smallbin的范围，也就是说在large bin 的范围
    {
        victim_index = largebin_index(size);//获取size对应的large bin的index
        bck = bin_at(av, victim_index);//bck指向size对应的large bin的链表头
        fwd = bck->fd;//fwd指向size对应的large bin的链表中的新加入的chunk
        
        //如果large bin 非空，在largbin进行按顺序插入
        if (fwd != bck) {
            /* Or with inuse bit to speed comparisons */
            size |= PREV_INUSE;
            assert((bck->bk->size & NON_MAIN_ARENA) == 0);//默认不启用assert
            /*
            	large bin中的chunk是按从大到小排列的，如果size < large bin 
            	的最后一个chunk，说明size是这个large bin中的最小的，我们把它
            	加入到此large bin尾部。
            */
            if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) {
                
                fwd = bck;
                bck = bck->bk;
                
                /*
                large bin 中size最小的chunk的fd_nextsize会指向size最大的
                那个chunk，也就是首部的chunk。同样，large bin 中size最大的
                chunk的bk_nextsize会指向size最小的那个chunk。
                victim的bk_nextsize指向large bin原来最小的chunk，它的
                bk_nextsize指向最大的那个chunk。那么原来的最小的就成了第二小的了。
                把它fd_nextsize和bk_nextsize都修正。
                */
                victim->fd_nextsize = fwd->fd;
                victim->bk_nextsize = fwd->fd->bk_nextsize;
                //最大size的chunk的bk_nextsize，和原来最小chunk的bk_nextsize都指向victim
                fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
            } 
            else //如果victim不是large bin 中最小的chunk
            {
                assert((fwd->size & NON_MAIN_ARENA) == 0);//默认不启用assert
                //从大到小（从头到尾）找到合适的位置
                while ((unsigned long) size < fwd->size) {
                    fwd = fwd->fd_nextsize;
                    assert((fwd->size & NON_MAIN_ARENA) == 0);
                }
				//如果size刚好相等，就直接加入到其后面省的改fd_nextsize和bk_nextsize了
                if ((unsigned long) size == (unsigned long) fwd->size)
                    fwd = fwd->fd;
                else 
                {
                    //size不相等，即size>fwd->size，把victim加入到纵向链表中
                    victim->fd_nextsize = fwd;
                    victim->bk_nextsize = fwd->bk_nextsize;
                    fwd->bk_nextsize = victim;
                    victim->bk_nextsize->fd_nextsize = victim;
                }
                bck = fwd->bk;
            }
        } 
        else //如果large bin 为空，将victim加入到纵向列表
        	victim->fd_nextsize = victim->bk_nextsize = victim;
    }

    //#define mark_bin(m, i)    ((m)->binmap[idx2block (i)] |= idx2bit (i))
    mark_bin(av, victim_index); //把victim加入到的bin的表示为非空
    //把victim加入到large bin的链表中
    victim->bk = bck;
    victim->fd = fwd;
    fwd->bk = victim;
    bck->fd = victim;
}

2.30版本及以上

源码参考于：https://bbs.pediy.com/thread-262424.htm

/* place chunk in bin */
 
         if (in_smallbin_range (size))        //如果是smallbin的大小就放到smallbin
           {
             victim_index = smallbin_index (size);
             bck = bin_at (av, victim_index);
             fwd = bck->fd;
           }
         else                                                    //如果是largebin的大小，那么：
           {
             victim_index = largebin_index (size);//根据size获取对应的largebin索引
             bck = bin_at (av, victim_index);         //获取largebin表头
             fwd = bck->fd;                                             //获取对应索引largebin的第一个chunk（循环链表的head->next）
 
             /* maintain large bins in sorted order */
             if (fwd != bck)                                            //当第一个不等于最后一个（即当前的largebin不空）
               {
                 /* Or with inuse bit to speed comparisons */
                 size |= PREV_INUSE;
                 /* if smaller than smallest, bypass loop below */
                 assert (chunk_main_arena (bck->bk));    //是否在main_arena?（主线程）
                 if ((unsigned long) (size)
             < (unsigned long) chunksize_nomask (bck->bk))//bck->bk储存的是当前索引的largebin中大小最小的chunk，如果我们要插入的chunk比这个大小还小，那么就要插入largebin的尾部。
                   {
                     fwd = bck;                                    //fwd此时为largebin表头
                     bck = bck->bk;                            //bck设置为largebin中最后一个的chunk
 
                     victim->fd_nextsize = fwd->fd;//由于我们要插入的在末尾，比他小的就是循环回去的第一个chunk
                     victim->bk_nextsize = fwd->fd->bk_nextsize;//比他大的就是之前的最小的那个
 
                     //原来链表的第一个chunk的bk指向此时新插入的最后一个chunk
                     fwd->fd->bk_nextsize =
                     victim->bk_nextsize->fd_nextsize = victim;
                   }
 
                 // 如果不是插入尾部，那么我们要找到这个chunk应该插入的位置
                 else
                   {
                     assert (chunk_main_arena (fwd));
                     //使用这个while循环尝试从链表头部开始遍历，直到找到一个比victim大或等于的chunk退出while
                     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;//直接将victim插入他的后面（通过fd），不修改nextsize指针。
 
                     //如果大小不一样(即此时fwd是相邻的大于victim的chunk)
                     //需要构造nextsize双向链表，构造新节点,victim作为堆头
                     else
                       {
                         //比victim小的指向fwd
                         //比victim大的指向fwd的bk_nextsize（比fwd大的那个）
                         //相当于插入了fwd与fwd->bk_nextsize之间
                         victim->fd_nextsize = fwd;
                         victim->bk_nextsize = fwd->bk_nextsize;
 
                         if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))//检查size链完整性
                           malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
                         //对应的去改fwd的相关指针成链
                         fwd->bk_nextsize = victim;
                         victim->bk_nextsize->fd_nextsize = victim;
                         //插入完成
                       }
 
                     bck = fwd->bk;
                     if (bck->fd != fwd)
                       malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
                   }
               }
             else
               victim->fd_nextsize = victim->bk_nextsize = victim;//此时victim为唯一的chunk，也要做循环链表
           }
                   //放到对应的 bin 中，构成 bk<-->victim<-->fwd。
         mark_bin (av, victim_index);    //标识bitmap
         victim->bk = bck;
         victim->fd = fwd;
         fwd->bk = victim;
         bck->fd = victim;

总结来说

在2.29及以下版本中，根据unsorted chunk的大小不同，分别执行如下代码

当unsorted bin当中的chunk的size小于属于同样index的large bin当前存在的最小块时，执行如下代码

          if ((unsigned long) (size)
< (unsigned long) chunksize_nomask (bck->bk))
            {
              fwd = bck;
              bck = bck->bk; 

              victim->fd_nextsize = fwd->fd;             /*fwd现在是表头*/            /*这里victim应该指的新放入的对那个chunk*/
              victim->bk_nextsize = fwd->fd->bk_nextsize;
              fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
            }

反之执行如下代码

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

当执行第一种情况时，我们只需要构造large chunk的bk_nextsize为target addr-0x20，最后就能target中写入该chunk的地址。

而当执行第二种情况时，我们需要构造large chunk的bk和bk_nextsize，这样能够往bk和bk_nextsize中写入当前chunk的地址。通常和unsorted bin attack来达成house of storm攻击

而在2.30版本后，由于增加了检查，使得只能够利用第一种情况，即向large chunk的bk_nextsize伪造我们的targe-0x20中写入当前chunk的地址。