# 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處理,改成<font color='red'>由kernel處理</font>
- 此時還是需要kernel做一點小小的事情
- `sys_brk`,修改`mm_struct`中的`brk`, `brk`的值為heap的最後位址(`s_brk`的值為heap的base address)
### Arena
- 主執行緒第一次呼叫`malloc`或`new`之後,系統會呼叫`brk()`給程式分配<font color='red'>132kb的heap空間</font>,這132kb的空間叫做<font color='red'>`Arena`</font>,因為由主執行緒分配的所以叫做`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`等
```c=
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`函式庫管理,依<font color='red'>chunk size</font>將釋放的`chunk`新增到`main arena`中對應的`bin`
1. `fast bin`: LIFO,用單向link list串接 - 因為`free`或`malloc`時都會把小區塊整合或是大區塊分割,但程式經常會`malloc`或`free`小區塊,如果每次都還要進行合併或分割會導致程式變慢,因此`fastbin`用來收集小區塊的chunk,<font color='red'>最多可以有8個free chunk</font>
2. `small bin`
3. `large bin`
4. `unsorted bin`
5. `tcache`
<br>
- 當再次呼叫`malloc`時,會先從這些`bin`中尋找是否有滿足需求的`chunk`
- 當程式呼叫`malloc`後,`glibc`會把一塊空間allocate給他,這個空間就叫做`chunk`,每個`chunk`包含兩部分
- `chunk header` : 給`glibc`管理用,大小為0x10
- `chunk data` : 真的要寫資料的地方
Note: chunk必須<font color='red'>0x10對齊</font>,如果要求的空間不是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)`
- 有時還會有額外兩個entry`fd_nextsize`跟`bk_nextsize`在`bk`下面
3. `top` : 沒有被使用過的chunk,會在heap的最頂端

- `top chunk`會盡可能地跟其他chunk合併,如果有個緊鄰`top chunk`的chunk被free,就會合併到`top chunk`中
- 因此`top chunk`的`PREV_INUSE`一定是1,因為如果前一個被free,一定會被合併進來
- demo
```c=
#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`

- 因為<font color='red'>chunkB小於0x400</font>,所以被收進`tcache bin`中,chunkA則在`unsorted bin`中

- <font color='red'>`tcache bin`最多可以放7個chunk</font>,放滿之後就依size
`< 0x400byte`就放進`fastbin`中
`> 400byte`就放進`unsorted bin`
- ex. `malloc`8個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
:::success
1. 只有`fd`一個ptr(single linked list)
2. 處理大小較小的chunk
- glibc default有`0x20-0x80`共7個bin,每個bin代表一個size
- 最多可到`0xb0`共10個bin
3. LIFO
- ex.
```c=
chunkA = malloc(0x18);
chunkB = malloc(0x18);
free(chunkA); //chunkA加入0x20的fastbin
free(chunkB); //chunkB加入0x20的fastbin
chunkC = malloc(0x18); //會拿到chunkB, LIFO
```
4. 如果是加入fastbin, <font color='red'>chunk的`PREV_INUSE`不會被清掉</font>
:::

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

#### Large bin
:::success
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`)來記錄<font color='red'>下一個大小跟自己不一樣</font>的chunk在哪裡
4. 每個bin中的freed chunk<font color='red'>由小到大排列</font>
5. 分配時使用<font color='red'>Best fit</font>
- ex.
```c=
chunkA = malloc(0x450);
chunkB = malloc(0x470);
free(chunkA);
free(chunkB);
chunkC = malloc(0x430); //會得到0x450大小的chunk,因為沒有剛好0x430大小的
//Best fit
```
:::

#### Unsorted bin
:::success
1. 有`fd`跟`bk` (double linked list)
2. 作為`small bin`跟`large bin`的cache
- <font color='red'>只有一個bin</font>
- 所有被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`中
:::success
1. 只有`fd` (single linked list)
2. 但還是有`bk`,用來存`key`,
- 用來判別這個chunk是否被free過(防止double free)
3. size從`0x20-0x410`共64個bin
- 每個bin中的chunk大小相同,一個bin最多可以有<font color='red'>7個chunk</font>
- 超過7個就會被放進`unsorted bin`等
4. LIFO
5. 跟fastbin一樣, <font color='red'>chunk的`PREV_INUSE`不會被清掉</font>
:::

#### 統整
:::warning
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
```c=
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中<font color='red'>絕大多數的chunk都是freed</font>
這樣造成極度浪費memory空間,因此glibc使用`consolidate`這套機制來處理這樣的問題
- 當一個<font color='red'>large bin chunk被`malloc`時</font>,會先檢查fastbin中有沒有連續的chunk,將他們組合起來丟到unsorted bin中
`Note: fastbin跟tcache如果沒有遇到malloc大空間,其中的chunk就不會被合併`
- demos
1. tcache_fastbin : tcache 7個被放滿之後就會放到fastbin中
```c=
#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,剛剛有提到<font color='red'>heap最前面0x290是保留給tcache的chunk</font>
```c=
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長這樣
```c=
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`中
```c=
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
```
:::danger
- 找`main_arena`的方法
因為`main_arena`一定會在`malloc_hook`下面
因此可以`readelf -a libc-2.31.so | greop "malloc_hook"`
:::
2. unsorted bin + small/large bin
```c=
#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`中
```c=
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),這些<font color='red'>ptr就是攻擊的主要目標</font>
- UAF(Use after free)
- double free
- Dangling pointer read/write
- Heap Overflow
### UAF
:::info
Common Tech
1. Fast bin dup / Tcache dup
2. Tcache stashing unlink
3. Large bin attack
:::
#### Fastbin attack
- 最終目標: 改變`fd`
- 如果fastbin chunk的<font color='red'>`fd`可控</font>,可以把`fd`改成可控的chunk的位置
- 改變`fd`的方法有UAF write, heap overflow, etc...,但通常題目沒有那麼簡單
- 因此通常要利用<font color='red'>`double free`</font>
- 正常來說如果有個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
```c=
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)` $\rightarrow$ `free(B)` $\rightarrow$ `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
