从一个linux堆分配例子中理解4种bins(fast、unsorted、small和large bin)

  为什么fast bin中chunk的大小和small bin中的有重叠?

前言

  之前在学习pwn的时候,看过linux的堆分配相关的内容,也提出了上面那个问题,并最终找到了答案。但是昨天看到群里有个兄弟问同样问题的时候,脑子却是一片空白,怎么也想不起来。不过有做笔记习惯的我们当然不慌,镇定自若地寻找以前的笔记,奈何却发现只记录了2个问题:

  1. 为什么fast bin和small bin中存储的大小有重叠?什么时候会使用重叠的small bin?
  2. 释放的块只要不满足fast bin大小的块都会放到unsorted bin中,那么什么时候才会保存到small bin和large bin中?

  (卧槽,我答案呢….)

  哎,好记性不如烂笔头,赶紧祭出gdb分析一通,并写下此篇文章记录一下。

环境搭建(kali + gdb + python3.7 + pwngdb)

  使用的kali虚拟机,其中 pwngdb 是新安装的,所以也稍微记录一下。这里gdb很坑,kali自带的python是3.6的,而gdb编译的python库是3.7(不知道是不是我升级了的原因),导致pwngdb安装的时候找不到python3.7,所以有3个选择:

  1. 重新编译gdb并配置依赖库为python3.6。
  2. 安装一个python3.7。
  3. 胡乱修改pwngdb的setup.h文件,让其安装成功(虽然安装成功了,但是最后缺少各种东西,运行不去来,别问我是怎么知道的,而且我还找到一个跟我一样经历的人:安装pwndbg遇到的坑)。

  那么这里我们就选择安装一个python3.7。编译安装python3.7后,再安装pwngdb时会出现另一个ssl的问题,其实是没有安装ssl的库。好吧,安装好ssl库以后重新编译安装python3.7,最后就顺利安装好pwngdb了。嗯,半天时间就过去了。

  总的来说可能需要用到以下几个命令:

  •   安装pwngdb时,提示找不到python3.7,那么需要安装一个python3.7,安装python3.7前,需要安装ssl库:

    1
    sudo apt-get install libssl-dev
  •   源码编译安装python3.7:

    1
    2
    3
    cd Python-3.7.1
    sudo ./configure
    sudo make && make install
  •   创建符号链接(让pwngdb能找到python3.7):

    1
    ln -s /usr/local/bin/python3.7 /usr/bin/python3.7
  •   安装pwngdb:

    1
    2
    cd pwndbg
    sudo ./setup.sh

问题回顾

  fast bin保存的chunk大小是16-80字节,unsorted bin 保存其他被free掉但不满足fast bin中的chunk,small bin保存的chunk大小是小于512字节,大于等于512字节的chunk保存到large bin中。(注意:这里的各种bin保存的是已经被free函数释放的内存,而不是已分配的内存,不要搞混了。)

  那么从上面可以发现, fast bin中chunk的字节大小是small bin的子集,存在重叠,那什么时候chunk会保存到small bin呢?另一个问题就是,chunk被释放后,首先是保存在fast bin或者unsorted bin中的,那么什么时候会保存到large bin中呢?既然释放的chunk首先不会跑到small和large bin中,那么我们可以大胆猜想,在分配内存的时候,chunk可能会移动到这个2个bin中,也就是说,当unsorted bin被遍历时,其中的chunk就会相应地被放到small bin和large bin中。

  这样猜想是有根据的,unsorted bin是链表结构,free掉的chunk会被插入到链表最后,这时候遍历不划算。而malloc的时候需要遍历unsorted bin中的chunk,找到合适的chunk,这时再将其他不满足的chunk保存到small bin和large bin中也是顺便的事情,所以从unsorted bin命名也可看成,这是一个未排序的bin,需要排序就需要遍历,遍历后的chunk就直接分类了。

  具体分析可以看freebuf的2篇文章,文章详细描述了为什么linux内存管理是这样设计:

  Linux堆内存管理深入分析(上)
  Linux堆内存管理深入分析(下)

  为验证上面的猜想,我们可以查看linux的源码,也可以做个小实验验证一下,我这里主要还是动态分析为主。

小实验

  先来看一下实验的代码(经过多次测试并优化):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdlib.h>
#include<stdio.h>

void main()
{
void *a,*b,*c,*d,*e = NULL;

// 第 1 步
a = malloc(0x500);
b = malloc(0x100); // 防止a,c释放后合并
c = malloc(0x500);
d = malloc(0x100); // 防止c 释放后与top_chunk合并

// 第 2 步
free(a); // 执行后unsorted bin有1个0x500的块
free(c); // 执行后unsorted bin有2个0x500的块

// 第 3 步
c = malloc(0x400); // 从unsorted bin中分配,还剩下0x100的块2放到unsorted bin中,另一个0x500的块1放到了large bin中
a = malloc(0x400); // 从large bin中分配,还剩下0x100的块1放到unsorted bin中,原来0x100的块2放到small bin

// 第 4 步
e = malloc(0x500); // 从top_chunk分配,unsorted bin中的块1也放到small bin中

// 第 5 步
free(a);
free(b);
free(c);
free(d);
free(e);
}

  接着用gcc编译生成程序,并使用安装了pwngdb插件的gdb来调试程序。

  本来打算截取pwndbg输出的堆状态来说明,但是发现不够清晰,而且每个chunk还有头大小,导致不能够很好说明,所以我自己画了一个简化的堆状态图来说明。图中没有画出来的bin,默认都为空。其中,初始化堆图如下:

  首先程序运行完第一步,分配了abcd 4个内存块,其中b和d是为了防止a和c 释放后发生合并,此时简化的堆如下:

  第二步,程序释放了a和c的内存,此时的a和c对应的chunk保存到unsorted bin中,简化的堆如下:

  第三步,第1句,申请分配0x400大小的内存赋值给c,这时系统首先会遍历unsorted bin,发现块2的chunk大小是0x500,满足申请,返回0x400大小,剩下的0x100放回到unsorted bin中,并对其他chunk进行排序,这时的另一个0x500块1会被放到large bin中。简化的堆如下:

  第2句,申请0x400大小的内存赋值给a,此时系统还是遍历unsorted bin,发现没有满足的chunk,然后把其中0x100的chunk块2放到small bin中。接着搜索large bin,发现了一个0x500的chunk块1满足要求,返回0x400大小,剩下的0x100的chunk块1保存到unsorted bin中。简化的堆如下:

  第四步:申请0x500大小的内存赋值给e,此时unsorted bin还是没有满足的chunk,而且0x100的chunk块1会被放到small bin中。接着large bin中也没有合适的chunk。最后系统从top chunk中分配内存。简化的堆如下:

  第五步:释放所有内存,状态回到一开始:

总结

  上面的小实验解决了前面提到的2个问题:fast bin和small bin回收chunk的途径不一样,所以大小重叠也是正常,实验同时也说明了在申请内存的时候,unsorted bin被会遍历,这时就有可能会将满足条件的chunk移动到small bin和large bin中。

  当然,上面只是一个很简单的场景,更详细的内容可以阅读linux源码和其他分析文章。

Pwndbg命令

  虽然文章没有提到pwndbg的使用,但是结果都是基于pwndbg调试出来的,顺便附上几个使用到的命令:

1
2
3
4
5
6
b main (main函数中下断 )
r (启动程序)
n (单步步过)

heap (查看堆信息)
bin (查看各个bin信息)

  最后,从libc2.26版本开始,bins中多了一个tcachebin,有兴趣的朋友可以自行了解,很多pwn题也开始利用这个bin来攻击,但是并不影响上面的结果。

坚持原创技术分享,您的支持将鼓励我继续创作!