glibc中的bins链表详解

glibc中的bins链表详解

[toc]

不知道是否有师傅和我一样，有时候会迷失在glibc的链表中，傻傻分不清楚fd和bk指向的是什么，也会忘记chunk的释放和分配顺序。因此就有了这篇文章，以一系列小实验来记录下各个链表的fd、bk指针的作用，以及各个链表的分配顺序。

fastbin

通过以下代码在glibc2.23进行测试：

// 先进行一个fastbin的测试
// Notice, a -> b means that a's fd pointer points to b

#include <stdio.h>
#include <stdlib.h>


int main(){
    size_t* p1 = malloc(0x20);
    size_t* p2 = malloc(0x20);
    printf("The addr of p1 is %p.\n", (size_t*)((size_t)p1 - 0x10));
    printf("The addr of p2 is %p.\n", (size_t*)((size_t)p2 - 0x10));
    printf("\n");

    free(p1);
    free(p2);
    printf("We free p1 first and free p2 later.\n");
    printf("And p1->fd = %p, while p1->bk = %p.\n", (size_t*)p1[0], (size_t*)p1[1]);
    printf("While p2->fd = %p, p2->bk = %p.\n", (size_t*)p2[0], (size_t*)p2[1]);
    printf("So we can see that the link of fastbin is p2 (free later) -> p1 (free first).\n");
    printf("It's %p -> %p.\n", (size_t*)((size_t)p2 - 0x10), (size_t*)((size_t)p1 - 0x10));
    printf("\n");
    
    size_t* p3 = malloc(0x20);
    printf("Now we malloc a chunk again, and it's address is %p.\n", (size_t*)((size_t)p3 - 0x10));
    printf("Which proves that fastbin is Last In, Frist Out.(LIFO)\n");
    printf("And the fd pointer of fastbin points to the chunk that is free before.\n");
    return 0;
}

其输出为：

$ ./test 
The addr of p1 is 0x555555559000.
The addr of p2 is 0x555555559030.

We free p1 first and free p2 later.
And p1->fd = (nil), while p1->bk = (nil).
While p2->fd = 0x555555559000, p2->bk = (nil).
So we can see that the link of fastbin is p2 (free later) -> p1 (free first).
It's 0x555555559030 -> 0x555555559000.

Now we malloc a chunk again, and it's address is 0x555555559030.
Which proves that fastbin is Last In, Frist Out.(LIFO)
And the fd pointer of fastbin points to the chunk that is free before.

这证明：

• fastbin是LIFO(Last in, Fist out)，即最后释放的chunk会最先被申请回去。这种分配方式满足操作系统上的时间局部性。
• fastbin中只存在fd指针，不存在bk指针，后释放的chunk的fd指针指向先释放的chunk。
• 从链表头添加，从链表头取出。

即：

unsortedbin

通过以下代码在glibc2.23进行测试：

// 这里是unsortedbin的测试
// Notice, a -> b means that a's fd pointer points to b

#include <stdio.h>
#include <stdlib.h>


int main(){
    setvbuf(stdin, 0, 2, 0);
    setvbuf(stdout, 0, 2, 0);
    setvbuf(stderr, 0, 2, 0);

    size_t* p1 = malloc(0xf0);
    malloc(0x20);
    size_t* p2 = malloc(0xf0);
    malloc(0x20); 
    printf("The addr of p1 is %p.\n", (size_t*)((size_t)p1 - 0x10));
    printf("The addr of p2 is %p.\n", (size_t*)((size_t)p2 - 0x10));
    printf("\n");

    free(p1);
    printf("Now we free p1, and it's fd and bk are %p and %p.\n", (size_t*)p1[0], (size_t*)p1[1]);
    printf("\n");

    free(p2);
    printf("Now we free p2.\n");
    printf("And p1->fd = %p, while p1->bk = %p.\n", (size_t*)p1[0], (size_t*)p1[1]);
    printf("While p2->fd = %p, p2->bk = %p.\n", (size_t*)p2[0], (size_t*)p2[1]);
    printf("\n");

    printf("FD: p2 (free later) -> p1 (free first) -> main_arena + x\n");
    printf("BK: p1 (free first) -> p2 (free later) -> main_arena + x\n");
    printf("FD: %p -> %p -> %p.\n", (size_t*)((size_t)p2 - 0x10), (size_t*)((size_t)p1 - 0x10), (size_t*)(*p1));
    printf("BK: %p -> %p -> %p.\n", (size_t*)((size_t)p1 - 0x10), (size_t*)((size_t)p2 - 0x10), (size_t*)(p2[1]));
    printf("\n");

    size_t* p3 = malloc(0xf0);
    printf("Now we malloc a chunk again, and it's address is %p.\n", (size_t*)((size_t)p3 - 0x10));
    printf("Which proves the order of Unsortedbin is FIFO(First In, First Out).\n");
    printf("The fd pointer points to the chunk freed before it.\n");
    printf("The bk pointer points to the chunk freed after it.\n");
    return 0;
}

其输出为：

$ ./test
The addr of p1 is 0x555555559000.
The addr of p2 is 0x555555559130.

Now we free p1, and it's fd and bk are 0x7ffff7dd1b78 and 0x7ffff7dd1b78.

Now we free p2.
And p1->fd = 0x7ffff7dd1b78, while p1->bk = 0x555555559130.
While p2->fd = 0x555555559000, p2->bk = 0x7ffff7dd1b78.

FD: p2 (free later) -> p1 (free first) -> main_arena + x
BK: p1 (free first) -> p2 (free later) -> main_arena + x
FD: 0x555555559130 -> 0x555555559000 -> 0x7ffff7dd1b78.
BK: 0x555555559000 -> 0x555555559130 -> 0x7ffff7dd1b78.

Now we malloc a chunk again, and it's address is 0x555555559000.
Which proves the order of Unsortedbin is FIFO(First In, First Out).
The fd pointer points to the chunk freed before it.
The bk pointer points to the chunk freed after it.

这说明：

• unsortedbin是遵循FIFO(First in, First out)的，即先释放的会先被申请出去。
• unsortedbin的fd指针指向比他先释放的chunk，而bk指针指向比它后释放的chunk。
• fd和bk指针都会指向main_arena，因此最先释放的chunk的fd指针将会指向main_arena，而最后释放的chunk的bk指针会指向main_arena。
• 从链表头插入，从链表尾取出

即：

smallbin

通过以下代码在glibc2.23进行测试：

// 这里是smallbin的测试
// Notice, a -> b means that a's fd pointer points to b

#include <stdio.h>
#include <stdlib.h>


int main(){
    setvbuf(stdin, 0, 2, 0);
    setvbuf(stdout, 0, 2, 0);
    setvbuf(stderr, 0, 2, 0);

    size_t* p1 = malloc(0xf0);
    malloc(0x20);
    size_t* p2 = malloc(0xf0);
    malloc(0x20); 
    printf("The addr of p1 is %p.\n", (size_t*)((size_t)p1 - 0x10));
    printf("The addr of p2 is %p.\n", (size_t*)((size_t)p2 - 0x10));
    printf("\n");

    free(p1);
    malloc(0x100);
    printf("Now we free p1 and malloc a chunk of size 0x100, which drives p1 to smallbin.\n");

    free(p2);
    malloc(0x100);
    printf("And then we free p2 and malloc a chunk of size 0x100, drives p2 to the smallbin.\n");

    printf("Now p1->fd = %p, while p1->bk = %p.\n", (size_t*)p1[0], (size_t*)p1[1]);
    printf("While p2->fd = %p, p2->bk = %p.\n", (size_t*)p2[0], (size_t*)p2[1]);
    printf("\n");

    printf("FD: p2 (free later) -> p1 (free first) -> main_arena + x\n");
    printf("BK: p1 (free first) -> p2 (free later) -> main_arena + x\n");
    printf("FD: %p -> %p -> %p.\n", (size_t*)((size_t)p2 - 0x10), (size_t*)((size_t)p1 - 0x10), (size_t*)(*p1));
    printf("BK: %p -> %p -> %p.\n", (size_t*)((size_t)p1 - 0x10), (size_t*)((size_t)p2 - 0x10), (size_t*)(p2[1]));
    printf("\n");

    size_t* p3 = malloc(0xf0);
    printf("Now we malloc a chunk again, and it's address is %p.\n", (size_t*)((size_t)p3 - 0x10));
    printf("Which proves the order of Smallbin is FIFO(First In, First Out).\n");
    printf("The fd pointer points to the chunk freed before it.\n");
    printf("The bk pointer points to the chunk freed after it.\n");
    return 0;
}

其输出为：

$ ./smallbin 
The addr of p1 is 0x555555559000.
The addr of p2 is 0x555555559130.

Now we free p1 and malloc a chunk of size 0x100, which drives p1 to smallbin.
And then we free p2 and malloc a chunk of size 0x100, drives p2 to the smallbin.
Now p1->fd = 0x7ffff7dd1c68, while p1->bk = 0x555555559130.
While p2->fd = 0x555555559000, p2->bk = 0x7ffff7dd1c68.

FD: p2 (free later) -> p1 (free first) -> main_arena + x
BK: p1 (free first) -> p2 (free later) -> main_arena + x
FD: 0x555555559130 -> 0x555555559000 -> 0x7ffff7dd1c68.
BK: 0x555555559000 -> 0x555555559130 -> 0x7ffff7dd1c68.

Now we malloc a chunk again, and it's address is 0x555555559000.
Which proves the order of Smallbin is FIFO(First In, First Out).
The fd pointer points to the chunk freed before it.
The bk pointer points to the chunk freed after it.

这说明：

• 其和unsortedbin的管理机制基本一样，同样为FIFO，只是unsortedbin只有一条链，而smallbin根据大小不同，有很多链。
• smallbin的fd指针指向比他先释放的chunk，而bk指针指向比它后释放的chunk。
• fd和bk指针都会指向main_arena，因此最先释放的chunk的fd指针将会指向main_arena，而最后释放的chunk的bk指针会指向main_arena。
• 从链表头插入，从链表尾取出

即：

largebin

largebin的链表结构比较复杂，若仍然使用代码的形式给读者展示，比较晦涩。这部分内容可以查看Rolan师傅的文章进行参考。这里放一张以前画的largebin的结构图。

其中：

• 每一个largebin中存放的chunk大小是不相同的，一共有63个largebin。在这63个largebin中，前32个largebin的最大chunk和最小的chunk之差为64bytes(0x40)。例如第一个largebin的大小为512bytes-568bytes（32位），而第二个largebin的大小就为576bytes-632bytes。

• 每一个largebin中的chunk按照大小顺序从大到小排序。

• 若大小相同，则会按照释放顺序排序：最先释放的chunk拥有fd_nextsize和bk_nextsize指针，之后的chunk的这两个指针的值都为0。若将这个chunk称为小堆头，那么后面释放的chunk都会被插入到小堆头的后面。因此，对于同一个大小的large chunk，最先释放的在最上面，除此之外越先释放在越后面。

• fd_nextsize和bk_nextsize是指向当前bin的下一个大小的chunk。fd_nextsize指向比自己小的，而bk_nextsize指向比自己大的。

tcache

通过以下代码在glibc2.27下完成测试：

// 这里是tcache的测试
// Notice, a -> b means that a's fd pointer points to b

#include <stdio.h>
#include <stdlib.h>


int main(){
    setvbuf(stdin, 0, 2, 0);
    setvbuf(stdout, 0, 2, 0);
    setvbuf(stderr, 0, 2, 0);

    size_t* p1 = malloc(0x20);
    size_t* p2 = malloc(0x20);
    printf("The addr of p1 is %p.\n", (size_t*)((size_t)p1 - 0x10));
    printf("The addr of p2 is %p.\n", (size_t*)((size_t)p2 - 0x10));
    printf("\n");

    free(p1);
    free(p2);
    printf("We free p1 first and free p2 later.\n");
    printf("And p1->fd = %p, while p1->bk = %p.\n", (size_t*)p1[0], (size_t*)p1[1]);
    printf("While p2->fd = %p, p2->bk = %p.\n", (size_t*)(p2[0] - 0x10), (size_t*)p2[1]);
    printf("So we can see that the link of tcache is p2 (free later) -> p1 (free first).\n");
    printf("It's %p -> %p.\n", (size_t*)((size_t)p2 - 0x10), (size_t*)((size_t)p1 - 0x10));
    printf("\n");
    
    size_t* p3 = malloc(0x20);
    printf("Now we malloc a chunk again, and it's address is %p.\n", (size_t*)((size_t)p3 - 0x10));
    printf("Which proves that tcache is Last In, Frist Out.(LIFO)\n");
    printf("And the fd pointer of tcache points to the chunk that is free before.\n");
    return 0;
}

其结果如下：

（根据glibc版本的不同，其bk指针有差异，指示的是其安全规则）

$ ./tcache 
The addr of p1 is 0x555555559250.
The addr of p2 is 0x555555559280.

We free p1 first and free p2 later.
And p1->fd = (nil), while p1->bk = (nil).
While p2->fd = 0x555555559250, p2->bk = (nil).
So we can see that the link of tcache is p2 (free later) -> p1 (free first).
It's 0x555555559280 -> 0x555555559250.

Now we malloc a chunk again, and it's address is 0x555555559280.
Which proves that tcache is Last In, Frist Out.(LIFO)
And the fd pointer of tcache points to the chunk that is free before.

从上面可以看到：

• tcache的管理机制和fastbin的管理机制很像，区别在于tcache还包括smallbin大小，且其bk指针用于安全校验。
• tcache是LIFO(Last in, Fist out)，即最后释放的chunk会最先被申请回去。这种分配方式满足操作系统上的时间局部性。
• tcache同样也是后释放的chunk的fd指针指向先释放的chunk。
• 从链表头添加，从链表头取出。

即：（是的，我只需要更改fastbin为tcache即可。）

参考文献

unsortbin attack分析与总结-二进制漏洞-看雪-安全社区|安全招聘|kanxue.com

Largebin attack总结-二进制漏洞-看雪-安全社区|安全招聘|kanxue.com