CTF-PWN技巧之堆结构 - 智能硬件个人技术分享

内容隐藏

三、Bins

一、什么是堆

在程序运行过程中，堆可以提供动态分配的内存，允许程序申请大小未知的内存。堆其实就是程序虚拟地址空间的一块连续的线性区域，它由低地址向高地址方向增长。我们一般称管理堆的那部分程序为堆管理器。

二、堆结构

1、malloc_chunk结构体

在源码 glibc-2.26/malloc/malloc.c 文件中定义了堆块的数据结构，分为以下几个字段

struct malloc_chunk {

  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

2、最小堆结构

mchunk_prev_size	mchunk_size
fd	bk
fd_nextsize	bk_nextsize

解释如下：

mchunk_prev_size：前一堆块的大小，free的时候有效
mchunk_size：当前堆块的大小，其中包含3个比特位：A/M/P，A表示是否属于主分配区，M则表示当前内存区域获得的虚拟内存（1：mmap，0：heap区域），P表示前一个块是否正在使用
fd：后一堆块的地址，free的时候有效
bk：前一堆块的地址，free的时候有效
fd_nextsize：后一堆块的大小，free的时候有效，堆块为Large bin
bk_nextsize：前一堆块的大小，free的时候有效，堆块为Large bin

关于3个比特位的定义如下：

/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
#define PREV_INUSE 0x1

/* extract inuse bit of previous chunk */
#define prev_inuse(p)       ((p)->mchunk_size & PREV_INUSE)


/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
#define IS_MMAPPED 0x2

/* check for mmap()'ed chunk */
#define chunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED)


/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
   from a non-main arena.  This is only set immediately before handing
   the chunk to the user, if necessary.  */
#define NON_MAIN_ARENA 0x4

/* Check for chunk from main arena.  */
#define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0)

/* Mark a chunk as not being on the main arena.  */
#define set_non_main_arena(p) ((p)->mchunk_size |= NON_MAIN_ARENA)


/*
   Bits to mask off when extracting size

   Note: IS_MMAPPED is intentionally not masked off from size field in
   macros for which mmapped chunks should never be seen. This should
   cause helpful core dumps to occur if it is tried by accident by
   people extending or adapting this malloc.
 */
#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)

/* Get size, ignoring use bits */
#define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS))

/* Like chunksize, but do not mask SIZE_BITS.  */
#define chunksize_nomask(p)         ((p)->mchunk_size)

......

可以得出，堆块的实际大小为mchunk_size & ~(1 | 2 | 4)的值。

示例代码：

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

int main(int argc , char* argv[])
{
    char *a = malloc(0x100);
    char *b = malloc(0x100);
    char *c = malloc(0x100);
    free(b);
    strcpy(a,"1111");
    return 0;
}

编译后在main函数结尾return处下断点，以下为gdb调试的时候查看的堆块情况：

解释如下：

prev_size：值为0，不采用
size：当前堆块的大小，大小实际为0x110，P比特位值为1
用户数据为"1111"

三、Bins

为了解决包括诸多浪费问题，free有一套明确的策略：

如果Size中M位被标记，表明chunk由mmap分配，则直接将其归还给系统；
否则，如果该chunk的P位未标记，表明上一个chunk处于释放，向上合并成更大的chunk；
如果chunk的下一个chunk未被使用，则向下合并为更大的chunk；
如果chunk与Top Chunk相邻，就直接与其合并；
否则，放入适当的Bins中。

现代堆管理器建立了一系列的Bins以储存不久前被释放的chunk，包括：SmallBin、LargeBin、UnsortedBin、FastBin、TcacheBin。

类别	说明
SmallBin	总共62个循环双链表，在 32 位系统上，小于 512 字节（或在 64 位系统上小于 1024 字节）。
LargeBin	总共63个循环双链表，在 64 位系统上大于等于 1024 字节。
UnsortedBin	总共1个循环双链表，当SmallBin和LargeBin都不能满足的时候采用。
FastBin	总共10个单链表，涵盖大小为 16、24、32、40、48、56、64、72、80 和 88 字节的chunk，同样不需要额外的排序操作。但特殊的是，被放入这里的chunk并不会被标记为“未被利用”，即下一个chunk的P位不会被置零，这种表现像是还未被释放一样。
TcacheBin	总共64个单链表，从glibc2.26开始增加，每个链包含最多7个节点，优先级高于fastbin，在 64 位系统上小于 1024 字节。

以下以TcacheBin和LargeBin为例，简单介绍一下这两种类别的区别。

1、示例代码（tcachebins）

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

int main(int argc , char* argv[])
{
    char *t[7];
    
    for(int i=0;i<7;i++)
    {
        t[i]=malloc(0x100);
    }
   
    for(int i=0;i<7;i++)
    {
        free(t[i]);
    }
    return 0;
}

编译后在main函数结尾return处下断点，以下为gdb调试的时候查看的堆块情况：

解释如下：

0x5555555597e0为tcachebins的一条链中的一个节点
prev_size：值为0
size：当前堆块的大小，大小实际为0x110，P比特位值为1
fd：当前largebins链中的下一个节点地址
bk：当前largebins链中的上一个节点地址

2、示例代码（largebins）

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

int main(int argc , char* argv[])
{
    char *t[7];
    
    for(int i=0;i<7;i++)
    {
        t[i]=malloc(0x410+0x10*i);
        malloc(0x10);
    }
   
    for(int i=0;i<7;i++)
    {
        free(t[i]);
    }
    
    malloc(0x500);
    return 0;
}

编译后在main函数结尾return处下断点，以下为gdb调试的时候查看的堆块情况：