Heap--初探--bins神将

CTF-PWN

发布日期: 2020-09-07

文章字数: 1.1k

阅读时长: 4 分

阅读次数:

Previously on Heap–初探–chunk的获取与释放：我们当时最大的疑惑差不多就是Free后的chunks都怎么了，这里来逐一解答。

前情提要

ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk。当用户再一次请求分配内存时，ptmalloc 分配器会试图在空闲的 chunk 中挑选一块合适的给用户。这样可以避免频繁的系统调用，降低内存分配的开销。
如果实在没有合适的就让商人去top chunk切一块下来
之后我们堆管理器的操作都是以chunk为最小单元，然后一般说的都是chunk地址而不是user_data_start 地址

链表

链表的每个单元都由数据域与指针域组成。
单项链表：

双向循环链表:

Fastbins

大多数程序经常会申请以及释放一些比较小的内存块。如果将一些较小的 chunk 释放之后发现存在与之相邻的空闲的 chunk 并将它们进行合并，那么当下一次再次申请相应大小的 chunk 时，就需要对 chunk 进行分割，这样就大大降低了堆的利用效率。因为我们把大部分时间花在了合并、分割以及中间检查的过程中。
因此，ptmalloc 中专门设计了 fast bin–ctfwiki-pwn
为了提高chunk获取和释放的效率，fastbins采用单链表数据结构来存储对应大小的free chunks，并且采用了FILO策略先进先出，利用的是fd进行单链表链接，而不是bk。链表如下：

所以在free一个可以被放入fastbins的chunk后，他会像压入栈里面一样压入对应的bin（对应大小的bin）中同时其fd会被填入free chunk3的地址（如上图）
这就是为啥之前我们在free一个chunk后（被放入了fastbins）我们再去看那个chunk里面的数据fd字段改变的原因。
例子：

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

int main()
{
    void* p1 = malloc(0x24);
    void* p2 = malloc(0x24);
    void* p3 = malloc(0x24);
    void* p4 = malloc(0x24);

    free(p1);
    free(p2);
    free(p3);
    free(p4);
    return 0;
}

gdb执行到return 0；

In file: /home/matrix/test.c
   10 
   11     free(p1);
   12     free(p2);
   13     free(p3);
   14     free(p4);
 ► 15     return 0;
   16 }
──────────────────────────────────────────────────────────────────[ STACK ]──────────────────────────────────────────────────────────────────
00:0000│ rsp  0x7fffffffdda0 —▸ 0x602010 ◂— 0x0
01:0008│      0x7fffffffdda8 —▸ 0x602040 —▸ 0x602000 ◂— 0x0
02:0010│      0x7fffffffddb0 —▸ 0x602070 —▸ 0x602030 ◂— 0x0
03:0018│      0x7fffffffddb8 —▸ 0x6020a0 —▸ 0x602060 ◂— 0x0
04:0020│ rbp  0x7fffffffddc0 —▸ 0x4005e0 (__libc_csu_init) ◂— push   r15
05:0028│      0x7fffffffddc8 —▸ 0x7ffff7a2d840 (__libc_start_main+240) ◂— mov    edi, eax
06:0030│      0x7fffffffddd0 ◂— 0x1
07:0038│      0x7fffffffddd8 —▸ 0x7fffffffdea8 —▸ 0x7fffffffe249 ◂— '/home/matrix/a.out'
────────────────────────────────────────────────────────────────[ BACKTRACE ]────────────────────────────────────────────────────────────────
 ► f 0           4005d6 main+112
   f 1     7ffff7a2d840 __libc_start_main+240
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
pwndbg> x/32gx 0x602010-0x10
0x602000:    0x0000000000000000    0x0000000000000031  <===== chunk1
0x602010:    0x0000000000000000    0x0000000000000000  
0x602020:    0x0000000000000000    0x0000000000000000 
0x602030:    0x0000000000000000    0x0000000000000031  <===== chunk2
0x602040:    0x0000000000602000    0x0000000000000000
0x602050:    0x0000000000000000    0x0000000000000000
0x602060:    0x0000000000000000    0x0000000000000031  <===== chunk3
0x602070:    0x0000000000602030    0x0000000000000000
0x602080:    0x0000000000000000    0x0000000000000000
0x602090:    0x0000000000000000    0x0000000000000031  <===== chunk4
0x6020a0:    0x0000000000602060    0x0000000000000000
0x6020b0:    0x0000000000000000    0x0000000000000000
0x6020c0:    0x0000000000000000    0x0000000000020f41  <===== top chunk
0x6020d0:    0x0000000000000000    0x0000000000000000

可以看到在free了这四个一样的chunk后：chunk4=====>chunk3=====>chunk2=====>chunk1
注意这里按理说前一个chunk是free状态然后当前chunk 的size的最后位应该置0。但是这里设计fastbins为了防止相邻两的freechunk合并的情况，就把里面的free chunk的size最后的P位都置1，因为合并后可能又要分类啥的太花费时间了。

其他bins

除了fastbins（tache）其他的bins都是双向链表结构。很相似（除largebins）如下。其数据存放规则是FIFO：先进先出

unsortedbin

存放刚刚释放还未分类且无法进入fastbins中的free chunks，相当于相当于small bins 和large bins的缓冲区。
如果用户malloc的大小大于fastbins里面的free chunks那么对管理器会先在unsorted bin中找，如果没找到就会触发unsorted bin中的free chunks遍历并合并，归类到他们该去的bins
这里面的chunks很没有规律，大大小小的都有，只有一个bin来存放，是名副其实的垃圾堆。但是可以减少程序中的碎片free chunks

smallbins

small bins 中每个 chunk 的大小与其所在的 bin 的 index 的关系为：chunk_size = 2 * SIZE_SZ *index，具体如下
下标 | SIZE_SZ=4（32 位）| SIZE_SZ=8（64 位）
–:|:—:|:–
2 | 16 | 32
3 | 24 | 48
4 | 32 | 64
5 | 40 | 80
x | 2*4*x | 2*8*x
63 | 504 | 1008
每个bin链表中存放的chunks大小都一致

可以发现这里的free chunks大小与fastbins中的大小是有一部分重叠的，这背后的原理比较复杂先暂且放放。