2020 程安 pwn筆記2 (Heap)

tags: 程式安全

Process Memory Layout

Low addr
text
data
heap
share library text
share library data
stack
High addr

• heap: 動態分配的memory(ex malloc/new)
• 在程式呼叫malloc或new之前,process是不會有heap segment的
• 有很多種實作方式,以glibc來說使用ptmalloc
  • 每個OS有不同實作方式
    • glibc - ptmalloc
    • windows - winheap
    • freebsd - jemalloc
    • OSx - zone allocator

ptmalloc

• Workflow
  

  • 要求memory大小小於128k: 會跟heap pool要求適合大小的空間
  • 要求超過128k會往mmap的方向走
    • 不再由libc處理,改成由kernel處理
    • 此時還是需要kernel做一點小小的事情
      • sys_brk,修改mm_struct中的brk, brk的值為heap的最後位址(s_brk的值為heap的base address)

Arena

• 主執行緒第一次呼叫malloc或new之後,系統會呼叫brk()給程式分配132kb的heap空間,這132kb的空間叫做Arena,因為由主執行緒分配的所以叫做main arena

  • 每個thread都有一個Arena,每個Arena中有多個chunk,這些chunk用linked list串接起來,linked list的head稱為bin,之後如果再申請空間會從這132kb中的chunk先分配,不夠再呼叫brk()來增加空間,或是太多空閒記憶體時呼叫s_brk()來減少空間

• Arena header包含bins的資訊,top chunk,last_remainder等

struct malloc_state
{
 /* Serialize access. */
 __libc_lock_define (, mutex);//定義了一个0x4byte的lock

 /* Flags (formerly in max_fast). */
 int flags;//0x4

 /* Set if the fastbin chunks contain recently inserted free blocks. */
 /* Note this is a bool but not all targets support atomics on booleans. */
 int have_fastchunks;//0x4

 /* Fastbins */
 mfastbinptr fastbinsY[NFASTBINS]; //fastbin链的head,總共10个, 每个0x10字节

 /* Base of the topmost chunk -- not otherwise kept in a bin */
 mchunkptr top;//0x4 到此为止总共0x96字节

 /* The remainder from the most recent split of a small request */
 mchunkptr last_remainder;        //切割后剩下的chunk链接到last_remainder

 /* Normal bins packed as described above */
 mchunkptr bins[NBINS * 2 - 2];   // 每个bin头有fd和bk两个指针

 /* Bitmap of bins */
 unsigned int binmap[BINMAPSIZE];   //位图,用32bit来分别表示当前bin哪个链上有chunk，通过按位与的方式

 /* Linked list */
 struct malloc_state *next;

 /* Linked list for free arenas. Access to this field is serialized
    by free_list_lock in arena.c. */
 struct malloc_state *next_free;

 /* Number of threads attached to this arena. 0 if the arena is on
    the free list. Access to this field is serialized by
    free_list_lock in arena.c. */
 INTERNAL_SIZE_T attached_threads;

 /* Memory allocated from the system in this arena. */
 INTERNAL_SIZE_T system_mem;
 INTERNAL_SIZE_T max_system_mem;
}

Chunk

• 主執行緒呼叫free之後,程式的heap空間並不會被釋放掉,而是由glibc的malloc函式庫管理,依chunk size將釋放的chunk新增到main arena中對應的bin

  1. fast bin: LIFO,用單向link list串接 - 因為free或malloc時都會把小區塊整合或是大區塊分割,但程式經常會malloc或free小區塊,如果每次都還要進行合併或分割會導致程式變慢,因此fastbin用來收集小區塊的chunk,最多可以有8個free chunk
  2. small bin
  3. large bin
  4. unsorted bin
  5. tcache
     
     
  • 當再次呼叫malloc時,會先從這些bin中尋找是否有滿足需求的chunk

• 當程式呼叫malloc後,glibc會把一塊空間allocate給他,這個空間就叫做chunk,每個chunk包含兩部分

  • chunk header : 給glibc管理用,大小為0x10
  • chunk data : 真的要寫資料的地方

  Note: chunk必須0x10對齊,如果要求的空間不是0x10的倍數,會被padding到0x10對齊
  ex. malloc(0x28)

  $\Rightarrow$ 會得到0x30 + 0x10(header)大小的chunk

• chunk種類有三種

  1. inuse : 正在使用中的chunk
     Size的最後3bit有特殊用途(反正size一定是0x10的倍數,後面的4bit不存也罷)
     

     • ex. 下面代表此chunk大小為0xb0,後面的1代表PREV_INUSE=1
       

  2. freed : 有被使用過但已被free掉的chunk
     Size的最後3bit跟inuse一樣,但freed chunk的PREV_INUSE一定為0
     

     • ex. 下圖是一個freed chunk,其中fd指向同一個bin中的下一個freed chunk,bk指向前一個
       

     • Note:

       • 一個chunk size至少0x20,因為至少要有header(0x10) + fd(0x8) + bk(0x8)
       • 有時還會有額外兩個entryfd_nextsize跟bk_nextsize在bk下面

  3. top : 沒有被使用過的chunk,會在heap的最頂端
     

     • top chunk會盡可能地跟其他chunk合併,如果有個緊鄰top chunk的chunk被free,就會合併到top chunk中
       • 因此top chunk的PREV_INUSE一定是1,因為如果前一個被free,一定會被合併進來

• demo

  ​#include <stdio.h>
  ​#include <stdlib.h>
  
  ​int main(){
  ​	setvbuf(stdin, NULL, _IONBF, 0);
  ​	setvbuf(stdout, NULL, _IONBF, 0);
  ​	setvbuf(stderr, NULL, _IONBF, 0);
  
  ​	char *chunkA = malloc(0x418); //chunk size will be 0x420
  ​	char *chunkB = malloc(0x18);  //chunk size will be 0x20
  
  ​	free(chunkA);
  ​	free(chunkB);
  ​	
  ​	return 0;
  ​}
  ​
  ​//gcc -o chunk chunk -g
  

  • 第9行之後,heap被分配空間,執行完兩個malloc之後
    

    
    • 第一次呼叫malloc後一定會分配132kb大小的arena
      0x290+0x420+0x20+0x20930=0x21000=132K
    • 第一個0x290的Chunk是保留給tcache的空間
    • 下圖中可以看到被分配的chunkA
      0x421 = 0x420(size) + 0x1(PREV_INUSE)
      
      

  • 執行完chunkA的free後,可以看到chunkA的fd跟bk都指向0x7fffff78bbe0,這個位址對應到main_arena struct中的top,代表top chunk的位置
    

    
    • 此時chunkB還是inuse,PREV_INUSE被設成0,header前面8byte被設成前一個chunk(chunkA)的size
      
      

  • 再free掉chunkB

    • chunkB的bk被寫進0x8005010,指向tcache bin
      

      

    • 因為chunkB小於0x400,所以被收進tcache bin中,chunkA則在unsorted bin中
      

      
      • tcache bin最多可以放7個chunk,放滿之後就依size
        < 0x400byte就放進fastbin中
        > 400byte就放進unsorted bin
        • ex. malloc8個0x20後,再free掉
          
          
        • 此時的bin
          
          

bins

glibc有幾種處理freed chunk的方式
依chunk大小,性質,何時free掉區分成

1. Fast bin
2. Unsorted bin
3. Small bin
4. Large bin
5. Tcache

Fast bin

1. 只有fd一個ptr(single linked list)
2. 處理大小較小的chunk
   • glibc default有0x20-0x80共7個bin,每個bin代表一個size
   • 最多可到0xb0共10個bin
3. LIFO
   • ex.
   ​chunkA = malloc(0x18);
   ​chunkB = malloc(0x18);
   ​
   ​free(chunkA); //chunkA加入0x20的fastbin
   ​free(chunkB); //chunkB加入0x20的fastbin
   ​
   ​chunkC = malloc(0x18); //會拿到chunkB, LIFO
   

4. 如果是加入fastbin, chunk的PREV_INUSE不會被清掉

Small bin

1. 有fd跟bk (double linked list)
2. 處理大小為0x20-0x3f0的chunk,共62個bin
3. FIFO

Large bin

1. 有fd跟bk (double linked list)

2. 處理大小 >=0x400的chunk,共63個bin

   • 前32個bin存4種size(0x400-0x430)
   • 接下來16個bin存32種size(0x440-0x630)
   • 8個bin存256種size(0x640-0x1630)
   • 4個bin存2048種size(0x1640-0x9630)
   • 2個bin存16384種size(0x9640-0x49630)
   • 最後一個bin存剩下的

   所以一種大小的chunk還是只會對應到一種bin

3. 每個bin中的chunk大小不一致,所以需要額外的entry(fd_nextsize跟bk_nextsize)來記錄下一個大小跟自己不一樣的chunk在哪裡

4. 每個bin中的freed chunk由小到大排列

5. 分配時使用Best fit

   • ex.
   ​chunkA = malloc(0x450);
   ​chunkB = malloc(0x470);
   ​
   ​free(chunkA);
   ​free(chunkB);
   ​
   ​chunkC = malloc(0x430); //會得到0x450大小的chunk,因為沒有剛好0x430大小的
   ​			 //Best fit
   

Unsorted bin

1. 有fd跟bk (double linked list)
2. 作為small bin跟large bin的cache
   • 只有一個bin
   • 所有被free掉應該要進small bin或large bin的chunk都會先被丟進unsorted bin中
     • 之後再malloc時會先進unsorted bin中traverse有無適合大小的chunk
     • 被traverse過不符合大小就會被丟進small bin或large bin

Tcache(可以當成thread的fastbin來看)

• 當很多個thread共用同一個memory時,需要用lock來避免race condition
  • 因此讓每個thread會有自己獨立的heap空間來減少lock的使用,讓速度變快
    
    $\Rightarrow$ 讓每個thread都有自己的tcache
  • tcache基本上跟其他bin都差不多,但更像fastbin,差別在於
    • tcache被放在heap上
    • fastbin是被放在main_arena中

1. 只有fd (single linked list)
2. 但還是有bk,用來存key,
   • 用來判別這個chunk是否被free過(防止double free)
3. size從0x20-0x410共64個bin
   • 每個bin中的chunk大小相同,一個bin最多可以有7個chunk
   • 超過7個就會被放進unsorted bin等
4. LIFO
5. 跟fastbin一樣, chunk的PREV_INUSE不會被清掉

統整

1. fastbin處理較小的chunk
2. small bin跟large bin處理fastbin無法處理的chunk
3. 在chunk被丟進small/large bin之前,會先被丟進unsorted bin中
4. tcache會擋在所有bin前面,0x20-0x410的chunk都會先被丟進tcache,直到tcache對應大小的bin不夠放

• 為啥fastbin跟small bin處理的size會overlap?

  • 當unsorted bin只有一個0x400大小的chunk,此時malloc(0x398)會要求一塊0x3a0大小的chunk,因為Best fit,因此會將這塊0x400大小的chunk切出0x3a0給他,剩下的0x400-0x3a0 = 0x60雖然符合fastbin可處理的範圍,但卻不會丟進fastbin,而是繼續放在unsorted bin中,最後可能流入small bin中

• ex

  ​chunkA = malloc(0x1008); //size=0x1010 -> large
  ​chunkB = malloc(0x408);  //size=0x410 -> tcache
  ​chunkC = malloc(0x418);  //size=0x420 -> large
  ​chunkD = malloc(0x18);   //用來防止chunkC被top chunk合併
  ​
  ​free(chunkA);
  ​free(chunkB);
  ​free(chunkC);
  ​
  ​chunk0 = malloc(0x398); //size=0x3a0
  ​chunk1 = malloc(0x500); //size=0x510,用來讓切剩的chunk進small bin
  

  • 執行完所有free後,unsorted bin中多了兩個freed chunk
    

    

  • 接著第10行再malloc(0x398),traverse後發現沒有剛好大小的chunk,會將0x1010的chunk放入large bin中,並將Best fit的0x420大小的chunk切成適當大小,剩下的0x420-0x3a0 = 0x80繼續放在unsorted bin
    

    

  • 最後第11行再malloc(0x500),此時traverse unsorted bin後會把剛剛剩下0x80的chunk放進small bin, 並把large bin中0x1010的chunk切出0x510,剩下0xb00又被放回unsorted bin
    

    

• Consolidate

  • 想像一隻程式malloc了極多的小空間後又free掉,此時fastbin串接了非常多的小size的chunk
    接著程式又malloc了一塊很大的空間,這些小freed chunk無法被使用,但top chunk也不夠大到能夠分配這塊大空間,此時只好向kernel要求更多空間,但其實目前heap中絕大多數的chunk都是freed
    這樣造成極度浪費memory空間,因此glibc使用consolidate這套機制來處理這樣的問題
  • 當一個large bin chunk被malloc時,會先檢查fastbin中有沒有連續的chunk,將他們組合起來丟到unsorted bin中
    Note: fastbin跟tcache如果沒有遇到malloc大空間,其中的chunk就不會被合併

• demos

1. tcache_fastbin : tcache 7個被放滿之後就會放到fastbin中

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

int main(){

	setvbuf(stdin, NULL, _IONBF, 0);
	setvbuf(stdout, NULL, _IONBF, 0);
	setvbuf(stderr, NULL, _IONBF, 0);

	char *tcache_chunks[7];
	char *fastbin_chunks[2];

	for (int i=0; i<7; i++) tcache_chunks[i] = malloc(0x18);  //size=0x20
	for (int i=0; i<2; i++) fastbin_chunks[i] = malloc(0x18); //size=0x20
	char *chunkA = malloc(0x28);
	
	for (int i=0; i<7; i++) free(tcache_chunks[i]);
	for (int i=0; i<2; i++) free(fastbin_chunks[i]);
	free(chunkA);

	return 0;
}

//gcc -g -o tcache_fastbin tcache_fastbin.c

• 執行結果(free掉之後)
  

  

• 而free掉之後看heap base,剛剛有提到heap最前面0x290是保留給tcache的chunk

gef⭐meow x/40gx 0x0000000008005000 //heap base
0x8005000:      0x0000000000000000      0x0000000000000291 //size = 0x290 + PREV_INUSE
0x8005010:      0x0000000000010007      0x0000000000000000
//代表0x20的tcache bin有7個chunk
//0x30的tcache bin有1個chunk
0x8005020:      0x0000000000000000      0x0000000000000000
0x8005030:      0x0000000000000000      0x0000000000000000
0x8005040:      0x0000000000000000      0x0000000000000000
0x8005050:      0x0000000000000000      0x0000000000000000
0x8005060:      0x0000000000000000      0x0000000000000000
0x8005070:      0x0000000000000000      0x0000000000000000
0x8005080:      0x0000000000000000      0x0000000000000000
//每2個byte代表一個tcache bin的chunk數,需要0x10-0x8F共64*2byte
0x8005090:      0x0000000008005360      0x00000000080053c0 
	         //指向0x20大小的freed chunk   //0x30
	         //(最後一個被free掉的)
0x80050a0:      0x0000000000000000      0x0000000000000000
		 //0x40                  //0x50
//後面每8個byte依序放不同size的tcache bin指向的第一個chunk

• 每個tcache中的chunk長這樣

gef⭐meow x/50gx 0x0000000008005000+0x290
0x8005290:      0x0000000000000000      0x0000000000000021
0x80052a0:      0x0000000000000000      0x0000000008005010
0x80052b0:      0x0000000000000000      0x0000000000000021
0x80052c0:      0x00000000080052a0      0x0000000008005010
0x80052d0:      0x0000000000000000      0x0000000000000021
0x80052e0:      0x00000000080052c0      0x0000000008005010
0x80052f0:      0x0000000000000000      0x0000000000000021
0x8005300:      0x00000000080052e0      0x0000000008005010
0x8005310:      0x0000000000000000      0x0000000000000021
0x8005320:      0x0000000008005300      0x0000000008005010
0x8005330:      0x0000000000000000      0x0000000000000021
0x8005340:      0x0000000008005320      0x0000000008005010
0x8005350:      0x0000000000000000      0x0000000000000021
0x8005360:      0x0000000008005340      0x0000000008005010
		//指向下一個chunk         //key

• 而fastbin的ptr會放在main_arena中

gef⭐meow x/100gx 0x7fffff78bb80 //main_arena
0x7fffff78bb80 <main_arena>:    0x0000000000000000      0x0000000000000001
0x7fffff78bb90 <main_arena+16>: 0x0000000008005390      0x0000000000000000
				//指向第一個0x20 fastbin chunk //0x30
0x7fffff78bba0 <main_arena+32>: 0x0000000000000000      0x0000000000000000
				//0x40			  //0x50
0x7fffff78bbb0 <main_arena+48>: 0x0000000000000000      0x0000000000000000
				//0x60			  //0x70
0x7fffff78bbc0 <main_arena+64>: 0x0000000000000000      0x0000000000000000
				//0x80                   //0x90
0x7fffff78bbd0 <main_arena+80>: 0x0000000000000000      0x0000000000000000
				//0xa0                   //0xb0
0x7fffff78bbe0 <main_arena+96>: 0x00000000080053e0      0x0000000000000000
				//top chunk ptr          //last remainder
0x7fffff78bbf0 <main_arena+112>:        0x00007fffff78bbe0      0x00007fffff78bbe0
				//bin ptr
0x7fffff78bc00 <main_arena+128>:        0x00007fffff78bbf0      0x00007fffff78bbf0
0x7fffff78bc10 <main_arena+144>:        0x00007fffff78bc00      0x00007fffff78bc00

gef⭐meow x/10gx  0x0000000008005390 //0x20 fastbin chunk ptr
0x8005390:      0x0000000000000000      0x0000000000000021
0x80053a0:      0x0000000008005370      0x0000000000000000
		//指向下一個chunk
				
gef⭐meow x/10gx  0x0000000008005370
0x8005370:      0x0000000000000000      0x0000000000000021
0x8005380:      0x0000000000000000      0x0000000000000000
		//是0x20 fastbin的最後一個chunk,故fd=NULL

• 找main_arena的方法
  因為main_arena一定會在malloc_hook下面
  因此可以readelf -a libc-2.31.so | greop "malloc_hook"

2. unsorted bin + small/large bin

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

int main(){

	setvbuf(stdin, NULL, _IONBF, 0);
	setvbuf(stdout, NULL, _IONBF, 0);
	setvbuf(stderr, NULL, _IONBF, 0);

	char *tcache_chunks_0x90[7];
	char *unsorted_chunks[4];
	char *tcache_chunks_0x3f0[7];

	unsorted_chunks[0] = malloc(0x88); //size=0x90 -> tcache
	char *guard_chunk_1 = malloc(0x18); //防止合併	
	unsorted_chunks[1] = malloc(0x3e8);
	char *guard_chunk_2 = malloc(0x18); //防止合併
	unsorted_chunks[2] = malloc(0x418); //size=0x420 -> unsorted bin -> large bin	
	for (int i=0; i<7; i++) tcache_chunks_0x90[i] = malloc(0x88);  //size=0x90
	for (int i=0; i<7; i++) tcache_chunks_0x3f0[i] = malloc(0x3e8);  //size=0x3f0
	unsorted_chunks[3] = malloc(0x508);
	char *guard_chunk_3 = malloc(0x18); //防止合併
	
	for (int i=0; i<7; i++) free(tcache_chunks_0x90[i]);
	for (int i=0; i<7; i++) free(tcache_chunks_0x3f0[i]);
	for (int i=0; i<4; i++) free(unsorted_chunks[i]);

	char *trigger_traverse = malloc(0x100);
	return 0;
}

• free掉之後
  

  

• 再次malloc trigger_traverse
  

  

• unsorted/small/large bin的ptr都放在main_arena中

gef⭐meow x/40gx  0x00007fffff78bbe0
0x7fffff78bbe0 <main_arena+96>: 0x0000000008008020      0x0000000008005450
                               //top chunk
0x7fffff78bbf0 <main_arena+112>:        0x0000000008005450      0x0000000008005450
                                        //1st of unsorted bin   //last chunk of unsorted bin
0x7fffff78bc00 <main_arena+128>:        0x00007fffff78bbf0      0x00007fffff78bbf0
                                        //1st of 0x20 smallbin  //last chunk of 0x20 small bin
0x7fffff78bc10 <main_arena+144>:        0x00007fffff78bc00      0x00007fffff78bc00
                                        //1st of 0x30 smallbin  //last chunk of 0x30 smallbin
...

0x7fffff78bc70 <main_arena+240>:        0x0000000008005290      0x0000000008005290
                                        //1st of 0x90 smallbin  //last chunk of 0x90 smallbin
... /*62個small bin完後面接large bin*/

0x7fffff78bfe0 <main_arena+1120>:       0x7fffff78bfe0 <main_arena+1120>:       0x0000000008005750      0x0000000008005750
                                        //1st of 0x420 largebin //last of 0x420 largebin

Heap Exploitation

由上述可知每個chunk都有ptr涵蓋其中(稱為heap chunk meta data),這些ptr就是攻擊的主要目標

• UAF(Use after free)
  • double free
  • Dangling pointer read/write
• Heap Overflow

UAF

Common Tech

1. Fast bin dup / Tcache dup
2. Tcache stashing unlink
3. Large bin attack

Fastbin attack

• 最終目標: 改變fd

  • 如果fastbin chunk的fd可控,可以把fd改成可控的chunk的位置

• 改變fd的方法有UAF write, heap overflow, etc…,但通常題目沒有那麼簡單

  • 因此通常要利用double free

• 正常來說如果有個chunk被double free

  1. 第一次free, fd會被改成null
  2. 第二次free, 會被glibc檢查到而crash
     • 噴double free or corruption (fasttop)

• bypass Glibc的double free檢查機制

  • free的時候會檢查fastbin的第一個chunk是不是要被free的那個chunk

    ​​do
    ​​    {
    ​​    /* Check that the top of the bin is not the record we are going to add (i.e., double free).  */
    ​​    if (__builtin_expect (old == p, 0))
    ​​        malloc_printerr ("double free or corruption (fasttop)");
    ​​        p->fd = old2 = old;
    ​​    } 
    ​​while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
    

  • bypass方式: 不要讓要double free的chunk在第一個就好

    • free(A)

      $\to$ free(B)
      $\to$ free(A)
      1. 1st free(A): fastbin的ptr指向A,A的fd被設成NULL
      2. free(B): fastbin的ptr指向B, B的fd指向A
      3. 2nd free(A):
         • 此時fastbin的第一個指向B,要free的chunk(A) != B,通過檢查
         • fastbin的ptr指向A, A的fd指向B
         • 至此我們成功把A的fd改寫成B的addr
      

• double free之後的攻擊方式

  • Fast bin dup
    4. 此時再malloc一個同等大小的空間
       char *chunkC = malloc(0x18)
       • 因為此時fast bin指向chunkA,因此我們會分配到chunkA
    5. 我們可以再chunkC中隨便寫東西(read(0, chunkC, 0x8 )),把chunkA的fd改成我們偽造的chunk