# Heap Exploitation

- **基於NTU Computer Security Fall 2019所寫的筆記**

[yuawn NTU-Computer-Security](https://github.com/yuawn/NTU-Computer-Security)

## Heap workflow

- **通過 `nmmap`或 `brk`跟kernel要memory**


- **跟kernel要了memory會放在glibc再透過`malloc`來跟glibc要memory**


## **chunks**
- 注意heap是以16 bytes唯一排
`Allocated chunk` malloc拿到的
`Free chunk` free掉的
`Top Chunk` 未分配的

---


### Allocated chunk

- **`chunk header`也可叫`metadata`**
- **! `pointer`會指向user data的頭而不是header**
- **`size`跟`N` `M` `P`中間有個byte不做使用**

---
- **`prev_size/data` 連續記憶體上⼀塊如是 free chunk，則紀錄該size，
若是 allocated chunk 則同時為它的 data。**

- **`size` 該memory的大小(佔4bytes)**

- **`(P) PREV_INUSE` 上⼀個 chunk 是否使⽤中**

- **`(M) IS_MMAPED` chunk 是否透過 mmap 出來的**

- **`(N) NON_MAIN_ARENA` 該 chunk 是否不屬於 main arena**


### Free Chunk

- **連續記憶體下⼀塊的 `P flag` 為0**
---

- **`(fd) forward pointer` 指向同⼀ bin 中的前⼀塊 chunk (linked list)**

- **`(bk) backward pointer` 指向同⼀ bin 中的後⼀塊 chunk (linked list)**


### Top Chunk

- **第⼀次`malloc`後，剩下的空間為 `top chunk`，分配空間時視情況從 `top chunk` 切割分配**

- **free `Top chunk 連續記憶體上⼀塊chunk`時，若不是 `fastbin` 則會與 `Top chunk` merge，`top chunk` `P` 恆為1。**


## bins
- **回收 Free chunk 的資料結構**

- **主要依據 `size` ⼤⼩，分為：**
**`tcache bin`**
**`fast bin`**
`small bin`
`large bin`
`unsorted bin`
---
### Fast bin

- **Size < `0x90` bytes**
- **bin 中依據 `size` 又會劃分為，0x20, 0x30, 0x40 ...**
- **`global_max_fast` = 0x80(在判定中是<=0x80)**
- **Singly linked list，`fd` 指向前⼀個，`bk` 沒⽤到**
- **LIFO (Last in, First out)**
- **! free 時`不會`將下⼀塊 `chunk P flag` 設成 `0`**

---
### Small bin

**• 僅在malloc時被切割才會放到這
• Circular doubly linked list
• 依據 size 劃分為 62 個bin
• 0x20, 0x30 ~ 0x3f0
• 0x20 ~ 0x80 的⼤⼩與 fast bin 重疊，會根據機制放到fast bin或small bin
• FIFO (First in, First out)
• free 掉時會將下⼀塊chunk P 設為0**

---
### Large bin

**• 僅在malloc時被切割才會放到這
• Circular doubly linked list (依據⼤⼩遞減排序)
• size >= 1024 bytes (0x400)
• 63 bins
• 細節可以參考 source code
• header
• fd_nextsize
• bk_nextsize**


---
### Unsorted bin

- **Circular doubly linked list**
- **free 的 chunk `size` ⼤於 `fast bin` 時，不會直接放到對應的 `bin` 裡，會先丟到
`unsorted bin` 中。**
- **`malloc` `fast bin` `size` ⼤⼩時會先去 `fast bin` `list` 裡找，若沒有則會⾄ `unsorted bin`找，如找到⼀樣⼤⼩則回傳，若無但找到⼤⼩⼤於所需⼤⼩的 `chunk` 則切割回傳，剩下的部分會丟回 `unsorted bin`，若都沒有則從 `top chunk` 切出來回傳。**

- **在`malloc`時會因為`unsorted bin`的切割而造成`small bin`也有`fast bin`的`size`。**

---

### Tcache
- **`glibc` >= `2.26`**
- **小於 `0x408` ⼤⼩範圍的 `chunk` 都會使⽤ `tcache`**
- **`Tcache` 中，當滿 `7` 個時，再 `free` 才會再放⾄ `fastbin` 中。**
- **`tcache fd` 是指向 `user data`。**
- **`malloc` 時沒有檢查 `size` 是否合法**
- **bypass `double free` check fill up the tcache bins list in same size(7) then free the same chunk from tcache again it will be put to the type(`fastbin`/`small bin`/`large bin`) of its size instead of catching double free**

## malloc
- **`malloc` `fast bin` `size` ⼤⼩時會先去 `fast bin` `list` 裡找，若沒有則會⾄ `unsorted bin`找，如找到⼀樣⼤⼩則回傳，若無但找到⼤⼩⼤於所需⼤⼩的 `chunk` 則切割回傳，剩下的部分會丟回 `unsorted bin`，若都沒有則從 `top chunk` 切出來回傳。**

## Hooks

- **`glibc` 中存在許多 `function hooks`，會是個很好的寫入目標**
**__malloc_hook
__free_hook
__realloc_hook**
- **執⾏該 `function` 時，發現該 `function hook` 有值，則當作 `function pointer` 跳上去執⾏。**

## Use After Free (UAF)

- **`free( ptr )`**

- **`free` 完 `pointer` 後未將 `ptr` 清空 `( ptr = NULL )`，稱之 `dangling pointer` 。**

- **`information leak`**

- **`fast bin` leak `heap address`**
- **`unsorted bin` leak `libc address`**

## Fastbin attack

- **fastbin 在檢查 double free 時，cmp `linked list` 第⼀個 `chunk` 即將要 `free` 掉的 `chunk`**

- **bypass `free(A) free(B) free(A)`**


- **malloc(0x70)**


- **write `s` to fake `fd`**


- **`malloc`到`fake chunk`**


- **write everywhere!**


### **constraints**

- **`malloc` check `chunk size`是否正確**

- **bypass by using aslr address like 0x7f which is
size 0x70 N=true M=true P=true if u ignore the 0xc6**