最近開始入坑linux下的堆漏洞成因與利用方式嘹朗，首先從認(rèn)識(shí)堆開始，一步步為自己的學(xué)習(xí)做一些總結(jié)。

0x00 什么是堆

要想知道堆的漏洞與利用方式，就必須要了解堆赛糟，知己知彼，才能百戰(zhàn)不勝嘛宙搬，是不是葫掉？

在程序運(yùn)行過(guò)程中，堆可以動(dòng)態(tài)的為程序提供內(nèi)存空間,并允許程序申請(qǐng)未知大小的空間刨摩，與棧不同寺晌，堆從低地址向高地址增長(zhǎng)，并且一經(jīng)分配澡刹，交由linux中的堆管理器來(lái)管理呻征。

我主要學(xué)習(xí)的是目前l(fā)inux所使用的glibc內(nèi)存管理機(jī)制ptmalloc2，其主要通過(guò)malloc/free函數(shù)來(lái)申請(qǐng)和釋放堆塊罢浇。glibc內(nèi)存管理器介于用戶與內(nèi)核之間陆赋，主要負(fù)責(zé)將內(nèi)核分配出的內(nèi)存按照用戶的需求分配或回收，而內(nèi)核會(huì)一次分配一個(gè)較大的內(nèi)存給堆管理器管理嚷闭，從而避免了程序與內(nèi)核空間的多次交互攒岛，同樣的，程序所釋放的內(nèi)存塊胞锰，也由內(nèi)存管理器暫時(shí)管理灾锯，不直接返還給內(nèi)核。

0x01 堆的基本操作

我們都知道對(duì)堆的基本操作主要有申請(qǐng)malloc和釋放free兩種關(guān)鍵操作嗅榕。

malloc

malloc申請(qǐng)內(nèi)存時(shí)與內(nèi)核交互主要通過(guò)brk和mmap函數(shù)來(lái)分配內(nèi)存空間顺饮，不同的是兩種方式調(diào)用的情況不同，首次申請(qǐng)的內(nèi)存不大于128KB時(shí)凌那，由brk申請(qǐng)兼雄，首次申請(qǐng)的內(nèi)存大于等于128KB時(shí)，就由mmap與內(nèi)核交互分配內(nèi)存空間案怯。
首次malloc時(shí)君旦，會(huì)將內(nèi)存分配給內(nèi)存管理器，當(dāng)申請(qǐng)的空間小于128KB調(diào)用brk時(shí)，無(wú)論申請(qǐng)多大空間金砍，都會(huì)自動(dòng)分配132KB的內(nèi)存局蚀，直到這些內(nèi)存全部用完，才會(huì)再次與內(nèi)核交互申請(qǐng)多余的內(nèi)存恕稠。

首次malloc

申請(qǐng)的這132KB都屬于main_arena琅绅，第二次分配時(shí)，只要第一次分配的128KB沒(méi)有被全部用完鹅巍，就不會(huì)與內(nèi)核申請(qǐng)內(nèi)存空間千扶，直到所有的空間被分配完畢后，再次使用brk申請(qǐng)內(nèi)存空間骆捧。
malloc的異常處理
malloc(size_t n)的參數(shù)設(shè)置n異常時(shí)進(jìn)行了異常處理:
當(dāng)參數(shù)n小于0時(shí)澎羞，由于size_t大多數(shù)情況下是無(wú)符號(hào)數(shù)，便會(huì)使內(nèi)核分配過(guò)大的內(nèi)存空間給用戶敛苇，但通常我們沒(méi)有這么大的空間用來(lái)分配妆绞，都會(huì)導(dǎo)致程序崩潰。
當(dāng)參數(shù)n等于0時(shí)枫攀，會(huì)返回當(dāng)前系統(tǒng)允許的最小堆塊括饶。

brk申請(qǐng)空間

我們利用一個(gè)簡(jiǎn)單的函數(shù)來(lái)證明隨著用戶申請(qǐng)空間的不同系統(tǒng)會(huì)選擇不同的方式來(lái)為他們分配內(nèi)存。
函數(shù)代碼如下：

#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");
    }
}
}

函數(shù)可以創(chuàng)建兩個(gè)指針p和q来涨，并可以free图焰，打印出指針的地址，方便我們觀察蹦掐，也利于我們后續(xù)學(xué)習(xí)bins等堆塊知識(shí)
我們運(yùn)行他技羔，申請(qǐng)一個(gè)小于首次分配132KB 的任意數(shù)值。

malloc_brk

mmap申請(qǐng)空間

當(dāng)我們運(yùn)行時(shí)輸入一個(gè)大于132KB的空間時(shí)，（139265=132KB+1）觀察指針的地址：

malloc_mmap

vmmap

free

在free的過(guò)程中，也有對(duì)異常的處理晶默。
free(void *p)
當(dāng)p為空指針時(shí)谨娜，不做任何處理。
當(dāng)p已經(jīng)被釋放時(shí)磺陡，再次釋放會(huì)產(chǎn)生double free的效果趴梢。
釋放掉的內(nèi)存不會(huì)直接交由內(nèi)核漠畜，而是先交給內(nèi)存管理器對(duì)內(nèi)存進(jìn)行管理。

0x02 堆的數(shù)據(jù)結(jié)構(gòu)

malloc_chunk
我們稱運(yùn)行過(guò)程中被malloc分配的內(nèi)存為一個(gè)chunk坞靶，這塊內(nèi)存在ptmalloc中用malloc_chunk 結(jié)構(gòu)體表示憔狞，當(dāng)程序申請(qǐng)的chunk被free時(shí)，會(huì)被加入相應(yīng)的空閑管理列表中彰阴。
無(wú)論一個(gè) chunk 的大小如何瘾敢，處于分配狀態(tài)還是釋放狀態(tài)，它們都使用一個(gè)統(tǒng)一的結(jié)構(gòu)尿这。雖然它們使用了同一個(gè)數(shù)據(jù)結(jié)構(gòu)簇抵，但是根據(jù)是否被釋放，它們的表現(xiàn)形式會(huì)有所不同射众。
malloc_chunk的結(jié)構(gòu)：

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;
};

其中對(duì)INTERNAL_SIZE_T的定義為：

#ifndef INTERNAL_SIZE_T
# define INTERNAL_SIZE_T size_t
#endif

size_t在64位中是64位的無(wú)符號(hào)整數(shù)碟摆，32位中是32位無(wú)符號(hào)數(shù)。
malloc_chunk中對(duì)每一個(gè)字段的解釋為:

prev_size: 如果該 chunk 的物理相鄰的前一地址chunk（兩個(gè)指針的地址差值為前一chunk大羞冻鳌）是空閑的話焦履，那該字段記錄的是前一個(gè) chunk 的大小(包括 chunk 頭)。否則雏逾，該字段可以用來(lái)存儲(chǔ)物理相鄰的前一個(gè)chunk 的數(shù)據(jù)。這里的前一 chunk 指的是較低地址的 chunk 郑临。

size :該 chunk 的大小栖博，大小必須是 2 * SIZE_SZ 的整數(shù)倍。如果申請(qǐng)的內(nèi)存大小不是 2 * SIZE_SZ 的整數(shù)倍厢洞，會(huì)被轉(zhuǎn)換滿足大小的最小的 2 * SIZE_SZ 的倍數(shù)仇让。32 位系統(tǒng)中，SIZE_SZ 是 4躺翻；64 位系統(tǒng)中丧叽，SIZE_SZ 是 8。 該字段的低三個(gè)比特位對(duì) chunk 的大小沒(méi)有影響公你，它們從高到低分別表示:
NON_MAIN_ARENA踊淳，記錄當(dāng)前 chunk 是否不屬于主線程，1表示不屬于陕靠，0表示屬于迂尝。
IS_MAPPED，記錄當(dāng)前 chunk 是否是由 mmap 分配的剪芥。
PREV_INUSE垄开，記錄前一個(gè) chunk 塊是否被分配。一般來(lái)說(shuō)税肪，堆中第一個(gè)被分配的內(nèi)存塊的 size 字段的 P位都會(huì)被設(shè)置為1溉躲，以便于防止訪問(wèn)前面的非法內(nèi)存榜田。當(dāng)一個(gè) chunk 的 size 的 P 位為 0 時(shí)，我們能通過(guò) prev_size 字段來(lái)獲取上一個(gè) chunk 的大小以及地址锻梳。這也方便進(jìn)行空閑chunk之間的合并箭券。

fd，bk: chunk 處于分配狀態(tài)時(shí)唱蒸，從 fd 字段開始是用戶的數(shù)據(jù)邦鲫。chunk 空閑時(shí)，會(huì)被添加到對(duì)應(yīng)的空閑管理鏈表中神汹，其字段的含義如下
fd指向下一個(gè)（非物理相鄰）空閑的 chunk
bk 指向上一個(gè)（非物理相鄰）空閑的 chunk
通過(guò) fd 和 bk 可以將空閑的 chunk 塊加入到空閑的 chunk 塊鏈表進(jìn)行統(tǒng)一管理

fd_nextsize庆捺， bk_nextsize，也是只有 chunk 空閑的時(shí)候才使用屁魏，不過(guò)其用于較大的 chunk（large chunk）滔以。
fd_nextsize指向前一個(gè)與當(dāng)前 chunk 大小不同的第一個(gè)空閑塊，不包含 bin 的頭指針氓拼。
bk_nextsize 指向后一個(gè)與當(dāng)前 chunk 大小不同的第一個(gè)空閑塊你画，不包含 bin 的頭指針。

一般空閑的 large chunk 在 fd 的遍歷順序中桃漾，按照由大到小的順序排列坏匪。這樣做可以避免在尋找合適chunk 時(shí)挨個(gè)遍歷。
一個(gè)已經(jīng)分配了的chunk分為chunk header和user data撬统，當(dāng)malloc分配一個(gè)chunk時(shí)指針實(shí)際指向的就是user data适滓，

相鄰chunk

bin

bin是一種記錄free chunk 的鏈表數(shù)據(jù)結(jié)構(gòu)，系統(tǒng)通過(guò)chunk的不同大小將bin分為了4類:
1) Fast bin
2) Unsorted bin
3) Small bin
4) Large bin

在glibc中記錄bin的數(shù)組有兩個(gè)撕彤，fastbinY（記錄所有的fastbins鱼鸠，共10個(gè)），bins（記錄除fastbin之外的所有bins羹铅，共126個(gè)）
數(shù)組bin中包含有1個(gè)unsorted bin瞧柔，62個(gè)small bins，63個(gè)large bins
處于各個(gè)free bins中的chunk通過(guò)fd與bk相互鏈接在一起睦裳。

（1）fastbins

在內(nèi)存的分配與釋放過(guò)程中造锅，fastbins是所有bins中速度最快的。

1.以32位操作系統(tǒng)為例廉邑，默認(rèn)情況下哥蔚，對(duì)于 SIZE_SZ 為 4B 的平臺(tái)倒谷，小于 64B 的 chunk 分配請(qǐng)求，對(duì)于 SIZE_SZ 為 8B 的平臺(tái)糙箍，小于 128B 的 chunk 分配請(qǐng)求渤愁，首先會(huì)查找 fast bins 中是否有所需大小的 chunk 存在（精確匹配），如果存在深夯，就直接返回抖格。
2.每個(gè)fastbins都是一個(gè)單鏈表，通過(guò)LIFO（last in frist out）算法咕晋，添加（free內(nèi)存）就是加入鏈表尾雹拄，刪除（malloc內(nèi)存）就是從鏈表尾部刪除。
3.設(shè)計(jì)fastbins的目的就是為了對(duì)小的堆塊的快速分配掌呜，所以fastbins中的堆塊不會(huì)自動(dòng)合并滓玖，因此屬于fastbins中的chunk標(biāo)志位P總置1，即使有物理相鄰的兩個(gè)堆塊都為free质蕉，也不會(huì)合并势篡，而是全部保留。

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 定義了默認(rèn)的 fast bins 中最大的 chunk 大小禁悠，對(duì)于 SIZE_SZ
為 4B 的平臺(tái)，最大 chunk 為 64B兑宇，對(duì)于 SIZE_SZ 為 8B 的平臺(tái)碍侦，最大 chunk 為 128B。ptmalloc
默認(rèn)情況下調(diào)用 set_max_fast(s)將全局變量 global_max_fast 設(shè)置為 DEFAULT_MXFAST顾孽，也就
是設(shè)置 fast bins 中 chunk 的最大值。

（2）small bins

ptmalloc使用small bins管理較小的空閑chunk比规，每個(gè)small bin的chunk size與index有著如下關(guān)系：
Chunk_size=2 * SIZE_SZ * index

1.在 SIZE_SZ 為 4B 的平臺(tái)上若厚，small bins 中的 chunk 大小是以 8B 為公差的等差數(shù)列，最大
的 chunk 大小為 504B蜒什，最小的 chunk 大小為 16B测秸，所以實(shí)際共 62 個(gè) bin。分別為 16B灾常、24B霎冯、
32B，……钞瀑，504B沈撞。在 SIZE_SZ 為 8B 的平臺(tái)上，small bins 中的 chunk 大小是以 16B 為公差
的等差數(shù)列雕什，最大的 chunk 大小為 1008B缠俺，最小的 chunk 大小為 32B显晶，所以實(shí)際共 62 個(gè) bin。
分別為 32B壹士、48B磷雇、64B，……躏救，1008B唯笙。
2.合并操作，當(dāng)有兩個(gè)物理相鄰的空閑堆塊時(shí)盒使，將對(duì)他們進(jìn)行合并操作崩掘。

（3）large bins

1.在 SIZE_SZ 為 4B 的平臺(tái)上，大于等于512B 的空閑 chunk忠怖，或者呢堰，在 SIZE_SZ 為 8B 的平
臺(tái)上，大小大于等于 1024B 的空閑 chunk凡泣，由 sorted bins 管理枉疼。Large bins 一共包括 63 個(gè) bin，
每個(gè) bin 中的 chunk 大小不是一個(gè)固定公差的等差數(shù)列鞋拟，而是分成了 6 組 bin骂维，每組 bin 是一個(gè)
固定公差的等差數(shù)列，每組的 bin 數(shù)量依次為 32贺纲、16航闺、8、4猴誊、2潦刃、1，公差依次為 64B懈叹、512B乖杠、
4096B、32768B澄成、262144B 等胧洒。
2.以 SIZE_SZ 為 4B 的平臺(tái)為例，第一個(gè) large bin 的起始 chunk 大小為 512B墨状，共 32 個(gè) bin卫漫，
公差為 64B，等差數(shù)列滿足如下關(guān)系：

Chunk_size=512 + 64 * index /*從512B開始肾砂，第一組bins的公差為64B*/

第二個(gè)large bin的起始chunk大小為第一個(gè)結(jié)束時(shí)的大小列赎，

Chunk_size=512 + 64 * 32 + 512 * index /*從第一組bins結(jié)束時(shí)開始計(jì)算，公差為512B*/

（4）unsorted bin

Unsorted bin 可以看作是 small bins 和 large bins 的 cache镐确，只有一個(gè) unsorted bin粥谬，以雙
向鏈表管理空閑 chunk肛根，空閑 chunk 不排序，所有的 chunk 在回收時(shí)都要先放到 unsorted bin
中漏策，分配時(shí)派哲，如果在 unsorted bin 中沒(méi)有合適的 chunk，就會(huì)把 unsorted bin 中的所有 chunk
分別加入到所屬的 bin 中掺喻，然后再在 bin 中分配合適的 chunk芭届。Bins 數(shù)組中的元素 bin[1]用于
存儲(chǔ) unsorted bin 的 chunk 鏈表頭。

unsorted bin 的隊(duì)列使用 bins 數(shù)組的第一個(gè)感耙，如果被用戶釋放的 chunk 大于 max_fast褂乍，
或者 fast bins 中的空閑 chunk 合并后，這些 chunk 首先會(huì)被放到 unsorted bin 隊(duì)列中即硼，在進(jìn)
行 malloc 操作的時(shí)候逃片，如果在 fast bins 中沒(méi)有找到合適的 chunk，則 ptmalloc 會(huì)先在 unsorted
bin 中查找合適的空閑 chunk只酥，然后才查找 bins褥实。如果 unsorted bin 不能滿足分配要求。malloc
便會(huì)將 unsorted bin 中的 chunk 加入 bins 中裂允。然后再?gòu)?bins 中繼續(xù)進(jìn)行查找和分配過(guò)程损离。從
這個(gè)過(guò)程可以看出來(lái)，unsorted bin 可以看做是 bins 的一個(gè)緩沖區(qū)绝编，增加它只是為了加快分
配的速度僻澎。

部分內(nèi)容總結(jié)參考自：
1）Glibc 內(nèi)存管理Ptmalloc2 源代碼分析
2）Linux堆內(nèi)存管理深入分析(下半部)作者@走位，阿里聚安全
3）ctf-wiki 堆數(shù)據(jù)結(jié)構(gòu)講解
感謝師傅們留下的精華知識(shí)O(∩_∩)O