最近开始入坑linux下的堆漏洞成因与利用方式，首先从认识堆开始，一步步为自己的学习做一些总结。

0x00 什么是堆

要想知道堆的漏洞与利用方式，就必须要了解堆，知己知彼，才能百战不胜嘛，是不是？

在程序运行过程中，堆可以动态的为程序提供内存空间,并允许程序申请未知大小的空间，与栈不同，堆从低地址向高地址增长，并且一经分配，交由linux中的堆管理器来管理。

我主要学习的是目前linux所使用的glibc内存管理机制ptmalloc2，其主要通过malloc/free函数来申请和释放堆块。glibc内存管理器介于用户与内核之间，主要负责将内核分配出的内存按照用户的需求分配或回收，而内核会一次分配一个较大的内存给堆管理器管理，从而避免了程序与内核空间的多次交互，同样的，程序所释放的内存块，也由内存管理器暂时管理，不直接返还给内核。

0x01 堆的基本操作

我们都知道对堆的基本操作主要有申请malloc和释放free两种关键操作。

malloc

malloc申请内存时与内核交互主要通过brk和mmap函数来分配内存空间，不同的是两种方式调用的情况不同，首次申请的内存不大于128KB时，由brk申请，首次申请的内存大于等于128KB时，就由mmap与内核交互分配内存空间。
首次malloc时，会将内存分配给内存管理器，当申请的空间小于128KB调用brk时，无论申请多大空间，都会自动分配132KB的内存，直到这些内存全部用完，才会再次与内核交互申请多余的内存。

首次malloc

申请的这132KB都属于main_arena，第二次分配时，只要第一次分配的128KB没有被全部用完，就不会与内核申请内存空间，直到所有的空间被分配完毕后，再次使用brk申请内存空间。
malloc的异常处理
malloc(size_t n)的参数设置n异常时进行了异常处理:
当参数n小于0时，由于size_t大多数情况下是无符号数，便会使内核分配过大的内存空间给用户，但通常我们没有这么大的空间用来分配，都会导致程序崩溃。
当参数n等于0时，会返回当前系统允许的最小堆块。

brk申请空间

我们利用一个简单的函数来证明随着用户申请空间的不同系统会选择不同的方式来为他们分配内存。
函数代码如下：

#include <stdlib.h>
void main()
{
    int flag=0;
    char *p=NULL,*q=NULL;
    int choice;
    int size=0;
    char point;
    while (1){
    puts("this is a malloc func!");
    puts("1.add");
    puts("2.del");
    printf("input your choice: ");
    scanf("%d",&choice);    
    if(choice==1)
    {   
    printf("input your index(p or q): ");
    scanf("%s",&point);
    if(flag==1 && point=='p')
    {
        puts("the point p already have !");
        exit(0);
    }
    else if(flag==2 && point=='q')
    {
        puts("the point q already have !");
        exit(0);
    }
    if(point=='p' && flag!=1)
    {
        printf("input your size: ");
        scanf("%d",&size);
        p=malloc(size);
        printf("input your data: ");
        scanf("%s",p);
        puts("this is your data");
        flag=1;
        puts(p);
        printf("p addr==>%p\n",p);  
    }
    else if(point=='q' && flag!=2)
    {
        printf("input your size: ");
        scanf("%d",&size);
        q=malloc(size);
        printf("input your data: ");
        scanf("%s",q);
        puts("this is your data");
        flag=2;
        puts(q);
        printf("q addr==>%p\n",q);
    }
    else
        {
            puts("unknow index");
        }
    }
    
    else if(choice==2)
    {
        printf("input your index(p or q): ");
        scanf("%s",&point);
        if(point=='p')
        {
            free(p);
            flag=0;
            puts("del p sucess!");
        }
        else if(point=='q')
        {
            free(q);
            flag=0;
            puts("del q sucess!");
        }
        else
        {
            puts("unknow index");
        }
        
    }
    else
    {
        puts("unknow choice");
    }
}
}

函数可以创建两个指针p和q，并可以free，打印出指针的地址，方便我们观察，也利于我们后续学习bins等堆块知识
我们运行他，申请一个小于首次分配132KB 的任意数值。

malloc_brk

mmap申请空间

当我们运行时输入一个大于132KB的空间时，（139265=132KB+1）观察指针的地址：

malloc_mmap

vmmap

free

在free的过程中，也有对异常的处理。
free(void *p)
当p为空指针时，不做任何处理。
当p已经被释放时，再次释放会产生double free的效果。
释放掉的内存不会直接交由内核，而是先交给内存管理器对内存进行管理。

0x02 堆的数据结构

malloc_chunk
我们称运行过程中被malloc分配的内存为一个chunk，这块内存在ptmalloc中用malloc_chunk 结构体表示，当程序申请的chunk被free时，会被加入相应的空闲管理列表中。
无论一个 chunk 的大小如何，处于分配状态还是释放状态，它们都使用一个统一的结构。虽然它们使用了同一个数据结构，但是根据是否被释放，它们的表现形式会有所不同。
malloc_chunk的结构：

struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      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;
};

其中对INTERNAL_SIZE_T的定义为：

#ifndef INTERNAL_SIZE_T
# define INTERNAL_SIZE_T size_t
#endif

size_t在64位中是64位的无符号整数，32位中是32位无符号数。
malloc_chunk中对每一个字段的解释为:

prev_size: 如果该 chunk 的物理相邻的前一地址chunk（两个指针的地址差值为前一chunk大小）是空闲的话，那该字段记录的是前一个 chunk 的大小(包括 chunk 头)。否则，该字段可以用来存储物理相邻的前一个chunk 的数据。这里的前一 chunk 指的是较低地址的 chunk 。

size :该 chunk 的大小，大小必须是 2 * SIZE_SZ 的整数倍。如果申请的内存大小不是 2 * SIZE_SZ 的整数倍，会被转换满足大小的最小的 2 * SIZE_SZ 的倍数。32 位系统中，SIZE_SZ 是 4；64 位系统中，SIZE_SZ 是 8。 该字段的低三个比特位对 chunk 的大小没有影响，它们从高到低分别表示:
NON_MAIN_ARENA，记录当前 chunk 是否不属于主线程，1表示不属于，0表示属于。
IS_MAPPED，记录当前 chunk 是否是由 mmap 分配的。
PREV_INUSE，记录前一个 chunk 块是否被分配。一般来说，堆中第一个被分配的内存块的 size 字段的 P位都会被设置为1，以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时，我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲chunk之间的合并。

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 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适chunk 时挨个遍历。
一个已经分配了的chunk分为chunk header和user data，当malloc分配一个chunk时指针实际指向的就是user data，

相邻chunk

bin

bin是一种记录free chunk 的链表数据结构，系统通过chunk的不同大小将bin分为了4类:
1) Fast bin
2) Unsorted bin
3) Small bin
4) Large bin

在glibc中记录bin的数组有两个，fastbinY（记录所有的fastbins，共10个），bins（记录除fastbin之外的所有bins，共126个）
数组bin中包含有1个unsorted bin，62个small bins，63个large bins
处于各个free bins中的chunk通过fd与bk相互链接在一起。

（1）fastbins

在内存的分配与释放过程中，fastbins是所有bins中速度最快的。

1.以32位操作系统为例，默认情况下，对于 SIZE_SZ 为 4B 的平台，小于 64B 的 chunk 分配请求，对于 SIZE_SZ 为 8B 的平台，小于 128B 的 chunk 分配请求，首先会查找 fast bins 中是否有所需大小的 chunk 存在（精确匹配），如果存在，就直接返回。
2.每个fastbins都是一个单链表，通过LIFO（last in frist out）算法，添加（free内存）就是加入链表尾，删除（malloc内存）就是从链表尾部删除。
3.设计fastbins的目的就是为了对小的堆块的快速分配，所以fastbins中的堆块不会自动合并，因此属于fastbins中的chunk标志位P总置1，即使有物理相邻的两个堆块都为free，也不会合并，而是全部保留。

fastbin的最大值被定义在DEFAULT_MXFAST中，如下:

#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST (64 * SIZE_SZ / 4)
#endif
/*
Set value of max_fast.
Use impossibly small value if 0.
Precondition: there are no existing fastbin chunks.
Setting the value clears fastchunk bit but preserves noncontiguous bit.
*/
#define  set_max_fast(s) global_max_fast = (((s) == 0) ? SMALLBIN_WIDTH: ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
#define  get_max_fast() global_max_fast

上面的宏 DEFAULT_MXFAST 定义了默认的 fast bins 中最大的 chunk 大小，对于 SIZE_SZ
为 4B 的平台，最大 chunk 为 64B，对于 SIZE_SZ 为 8B 的平台，最大 chunk 为 128B。ptmalloc
默认情况下调用 set_max_fast(s)将全局变量 global_max_fast 设置为 DEFAULT_MXFAST，也就
是设置 fast bins 中 chunk 的最大值。

（2）small bins

ptmalloc使用small bins管理较小的空闲chunk，每个small bin的chunk size与index有着如下关系：
Chunk_size=2 * SIZE_SZ * index

1.在 SIZE_SZ 为 4B 的平台上，small bins 中的 chunk 大小是以 8B 为公差的等差数列，最大
的 chunk 大小为 504B，最小的 chunk 大小为 16B，所以实际共 62 个 bin。分别为 16B、24B、
32B，……，504B。在 SIZE_SZ 为 8B 的平台上，small bins 中的 chunk 大小是以 16B 为公差
的等差数列，最大的 chunk 大小为 1008B，最小的 chunk 大小为 32B，所以实际共 62 个 bin。
分别为 32B、48B、64B，……，1008B。
2.合并操作，当有两个物理相邻的空闲堆块时，将对他们进行合并操作。

（3）large bins

1.在 SIZE_SZ 为 4B 的平台上，大于等于512B 的空闲 chunk，或者，在 SIZE_SZ 为 8B 的平
台上，大小大于等于 1024B 的空闲 chunk，由 sorted bins 管理。Large bins 一共包括 63 个 bin，
每个 bin 中的 chunk 大小不是一个固定公差的等差数列，而是分成了 6 组 bin，每组 bin 是一个
固定公差的等差数列，每组的 bin 数量依次为 32、16、8、4、2、1，公差依次为 64B、512B、
4096B、32768B、262144B 等。
2.以 SIZE_SZ 为 4B 的平台为例，第一个 large bin 的起始 chunk 大小为 512B，共 32 个 bin，
公差为 64B，等差数列满足如下关系：

Chunk_size=512 + 64 * index /*从512B开始，第一组bins的公差为64B*/

第二个large bin的起始chunk大小为第一个结束时的大小，

Chunk_size=512 + 64 * 32 + 512 * index /*从第一组bins结束时开始计算，公差为512B*/

（4）unsorted bin

Unsorted bin 可以看作是 small bins 和 large bins 的 cache，只有一个 unsorted bin，以双
向链表管理空闲 chunk，空闲 chunk 不排序，所有的 chunk 在回收时都要先放到 unsorted bin
中，分配时，如果在 unsorted bin 中没有合适的 chunk，就会把 unsorted bin 中的所有 chunk
分别加入到所属的 bin 中，然后再在 bin 中分配合适的 chunk。Bins 数组中的元素 bin[1]用于
存储 unsorted bin 的 chunk 链表头。

unsorted bin 的队列使用 bins 数组的第一个，如果被用户释放的 chunk 大于 max_fast，
或者 fast bins 中的空闲 chunk 合并后，这些 chunk 首先会被放到 unsorted bin 队列中，在进
行 malloc 操作的时候，如果在 fast bins 中没有找到合适的 chunk，则 ptmalloc 会先在 unsorted
bin 中查找合适的空闲 chunk，然后才查找 bins。如果 unsorted bin 不能满足分配要求。malloc
便会将 unsorted bin 中的 chunk 加入 bins 中。然后再从 bins 中继续进行查找和分配过程。从
这个过程可以看出来，unsorted bin 可以看做是 bins 的一个缓冲区，增加它只是为了加快分
配的速度。

部分内容总结参考自：
1）Glibc 内存管理Ptmalloc2 源代码分析
2）Linux堆内存管理深入分析(下半部)作者@走位，阿里聚安全
3）ctf-wiki 堆数据结构讲解
感谢师傅们留下的精华知识O(∩_∩)O