title: Linux heap 學習
tags: Heap,pwn,linux
grammar_cjkRuby: true
利用週末的時間，系統的學習了linux 系統的glibc堆分配機制，從中瞭解了很多以前很模糊的東西。本文打算系統的講解一下關於堆的分配和使用機制，同時思考可能存在的一些攻擊方法。
0x01 Linux 堆概述
在程序運行過程中，動態的進行內存分配。是在內存中的一段連續的空間，由低地址向高地址增長。由堆管理其負責調用分配。
0x1 實現庫
目前實現堆管理的庫有很多
dlmalloc – General purpose allocator
ptmalloc2 – glibc
jemalloc – FreeBSD and Firefox
tcmalloc – Google
libumem – Solaris
主要介紹ptmalloc2 – glibc，ptmalloc2 主要是通過 malloc/free 函數來分配和釋放內存塊。
0x2 分配函數
堆內存的分配函數是malloc(n)
1.當 n=0 時，返回當前系統允許的堆的最小內存塊。
2.當 n 為負數時，由於在大多數系統上，size_t 是無符號數（這一點非常重要），所以程序就會申請很大的內存空間，但通常來說都會崩潰，因為系統沒有那麼多的內存可以分配。
malloc是用戶層使用的函數，真正分配內存的是系統調用函數 (s)brk 函數以及 mmap, munmap 函數。
在一開始創建堆的時候使用brk函數，直接在數據段的後面申請一段空間（稱為arena）
堆擴展那麼當arena空間不夠時系統怎麼處理？
malloc採取的機制是
1.當調用malloc函數，arena空間不夠時，如果申請的大小<128KB(0x20000字節) 直接使用brk分配機制，也就是說直接拓展arena
2.前提一樣，如果申請的空間>= 128KB時，直接使用mmap分配機制
測試程序針對第一種情況
#include
#include
#include
#include
#include
int
main() {
char
* addr;
printf(
"Welcome to per thread arena example::%d\n"
,getpid());
addr = (
char
*) malloc(
1000
);
getchar();
addr = (
char
*) malloc(
0x20000
);
getchar();
addr = (
char
*) malloc(
0x10000
);
getchar();
addr = (
char
*) malloc(
0x10000
);
getchar();
free(addr);
return
0
;
}
針對第二種情況，測試腳本
#include
#include
#include
#include
#include
int
main() {
pthread_t
t1;
void
* s;
int
ret;
char
* addr;
printf(
"Welcome to per thread arena example::%d\n"
,getpid());
addr = (
char
*) malloc(
1000
);
getchar();
// addr = (char*) malloc(0x40000);
// addr = (char*) malloc(0x40000);
addr = (
char
*) malloc(
0x10000
);
getchar();
addr = (
char
*) malloc(
0x10000
);
getchar();
addr = (
char
*) malloc(
0x20000
);
getchar();
free(addr);
return
0
;
}
0x3 釋放函數
堆內存釋放函數是free(p)，其中p是堆指針，指向的是data部分（不加上head頭部）
1.當 p 為空指針時，函數不執行任何操作。
2.當 p 已經被釋放之後，再次釋放會出現亂七八糟的效果，這其實就是 double free。
除了被禁用 (mallopt) 的情況下，當釋放很大的內存空間時，程序會將這些內存空間還給系統，以便於減小程序所使用的內存空間。
在執行釋放函數時，會檢查該塊的前一塊是否是空塊，如果是將會進行堆塊的合併。
0x02 Heap 分配機制
在程序使用堆的時候會調用malloc去申請內存空間，返回的是一個堆塊指針，指向堆結構體，當它被釋放時會被插入相對應的空閒結塊鏈表。
0x1 堆塊結構
堆塊結構是一個結構體，具體內容如下
/*
This struct declaration is misleading (but accurate and necessary).
It declares a "view" into memory allowing access to necessary
fields at known offsets from a given base. See explanation below.
*/
struct
malloc_chunk {
INTERNAL_SIZE_T prev_size;
/* Size of previous chunk (if free). */
INTERNAL_SIZE_T size;
/* Size in bytes, including overhead. */
struct
malloc_chunk* fd;
/* double links -- used only if free. */
struct
malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */
struct
malloc_chunk* fd_nextsize;
/* double links -- used only if free. */
struct
malloc_chunk* bk_nextsize;
};
在size的底三位記錄了當前的堆塊狀態和上一個內存地址相鄰的堆塊的使用狀態參數解釋
- prevsize
- 記錄上一個堆塊（這裡指的是內存地址相鄰的堆塊，而不是鏈表中的相鄰）的大小，當本塊的p位（記錄上一堆塊的使用狀態）為1時，prevsize屬於上一個堆塊，進行內存賦值等操作。反之則表示上一堆塊的大小
- size
- 記錄本塊大小，該 chunk 的大小，大小必須是 2 * SIZE_SZ 的整數倍。包括header在內的堆塊大小，第三位分別為N、M、P
- P
- PREV_INUSE，表示前一個chunk是否為allocated
- M
- IS_MAPPED，表示當前chunk是否是通過mmap系統調用產生的
- N
- NONMAINARENA，表示當前chunk是否是thread arena
- FD
- 指向鏈表中前一個堆塊的指針，該指針指向的是chunk的head
- BK
- 指向鏈表中後一個堆塊的指針，該指針也是指向chunk的head，通過 fd 和 bk 可以將空閒的 chunk 塊加入到空閒的 chunk 塊鏈表進行統一管理
- FD_nextsize
- 指向前一個與當前 chunk 大小不同的第一個空閒塊，不包含 bin 的頭指針。
- BK_nextsize
- 指向後一個與當前 chunk 大小不同的第一個空閒塊，不包含 bin 的頭指針。一般空閒的 large chunk 在 fd 的遍歷順序中，按照由大到小的順序排列。這樣做可以避免在尋找合適chunk 時挨個遍歷。
內存對齊堆塊申請的時候不一定都是內存對齊的，比如在x86操作系統下申請0x95。那麼堆的對齊方式又是如何呢？
經過實驗發現如下規律
機器類型對齊位數x868bytex6416byte
同時通過輸出size_t，為堆塊中的基本單位
機器類型基本單元x864bytex648byte
分配大小計算
在進行內存申請的時候有許多計算規則，如果想要數量掌握堆的管理機制以及利用方法，那麼就必須瞭解堆塊是如何分配其大小的。
首先提幾個概念，內存複用、地址對齊。內存複用體現在下一塊的prevsize，複用的內存不算在chunk大小上。在計算是首先 size mod2*size_t剩餘的數據與sizet進行比較，如果小則直接分配，如果大則直接增加 2*size_t以一個例子為例： malloc(0x43)
- 在x86環境下 對齊單元為0x8還剩下0x3字節數據，可以利用複用的內存進行擴充。加上頭部8字節，一共分配了0x48字節chunk
malloc(0x45)
- 在x86環境下對齊之後還剩0x5字節數據，複用還不行，那麼直接增加0x8個字節，一共分配0x50字節chunk
舉一個0x64的例子 malloc(0x45)
- 對齊之後還有0x5字節，可以採取複用，最後大小為0x50
malloc(0x49)
- 對齊之後，不可以採取複用，最後大小為0x60
最後補充一點，每一個chunk都要有data段，所以不能只用頭和複用段。
bin
當用戶釋放chunk後，chunk並不會立即回到系統中去，而是有ptmalloc統一進行管理，當再有內存空間申請的請求時，ptmalloc分配器會在空閒的chunk中挑一塊給用戶。那麼維護空閒chunk的結構是鏈表形式，主要有四種fast bins，small bins，large bins，unsorted bin。在下面的介紹中將一一講述。
bin的鏈表中的指針指向的是head頭部，並非是數據部分，這點應該格外注意。
0x2 Fast bin
防止經常使用的較小的堆塊被合併，降低堆的利用效率。
fastbin總共有10個鏈表，不同位數操作系統的堆塊大小不同
索引x86x6400x200x1010x300x1820x400x2030x500x2840x600x3050x700x3860x800x40
需要注意的幾點
- Fastbin的free chunk中p標誌位是一直為1的也就是說，fastbin的空閒塊總是標識被佔用。也是防止被其他塊進行合併
- Fastbin 鏈表是單鏈表，方便操作
利用fd執行後面的指針
0x3 Small bin
小於512字節的chunk稱之為small chunk，small bin就是用於管理small chunk的。採用FIFO的算法
需要注意幾點
- smallbin個數是62個參照上圖
- 維護的是雙向鏈表
- 當相鄰的兩個堆塊都是free狀態時，會發生合併現象
- 與fastbin的大小相沖突，大小衝突的smallbin還會收錄堆塊嗎？答案是會的，不是一次申請的fastbin大小堆塊被釋放，就有可能放入smallbin裡面
- smallbin的來源是？smallbin的來源是unsortedbin，具體會在unsortedbin中講解
0x4 Lager bin
large bins 中一共包括 63 個 bin，每個 bin 中的 chunk 的大小不一致，而是處於一定區間範圍內。此外，這 63 個 bin 被分成了 6 組，每組 bin 中的 chunk 大小之間的公差一致，具體如下：
需要注意幾點
- 合併同smallbin
- 同一個largebin其chunk大小有可能不一樣，處於某一範圍之內(例如第一個為521~575之間)。在同一個largebin裡面chunk的大小是按照從大到小的順序排放的
- 在橫向也有鏈表相連接如下圖
- malloc時，首先確定大小屬於哪個largebin。然後將剩餘的chunk丟到unsortedbin中，等待分配。
0x5 Unsorted bin
unsorted bin 位於 bin[1]，當釋放較小或較大的chunk的時候，如果系統沒有將它們添加到對應的bins中，主要來源如下
1.當一個較大的 chunk 被分割成兩半後，如果剩下的部分大於MINSIZE，就會被放到 unsorted bin 中。
2.釋放一個不屬於 fast bin 的 chunk，並且該 chunk 不和 top chunk 緊鄰時，該 chunk 會被首先放到 unsorted bin 中。關於 top chunk 的解釋，請參考下面的介紹。
3.當申請的內存被釋放時除了fastbin大小的chunk直接插入鏈表中外，其他的chunk都被放在unsorted bin裡面待分配。
4.unsorted chunk的刪除並不使用 unlink ，使用的是下面方法，因此只是改變了chunk的bk塊的前項指針，在malloc操作時最後訪問的unsorted ，如果沒有合適的大小就一個一個的刪除，添加到其他鏈表中，所以這時如果偽造了chunk的bk值，很容易引起崩潰
victim = unsortedchunks(av)->bk // victim為free掉的p
bck = victim->bk; // bck 為 任意地址 -0x10
unsortedchunks(av)->bk = bck; // 調整鏈表
bck->fd = unsorted_chunks(av); // 任意地址 -0x10 + 0x10 = unsortedbin
0x6 Top chunk
對於非主分配區會預先從 mmap 區域分配一塊較大的空閒內存模擬 sub-heap,通過管 理 sub-heap 來響應用戶的需求,因為內存是按地址從低向高進行分配的,在空閒內存的最 高處,必然存在著一塊空閒 chunk,叫做 top chunk.當 bins 和 fast bins 都不能滿足分配需 要的時候,ptmalloc 會設法在 top chunk 中分出一塊內存給用戶,如果 top chunk 本身不夠大, 分配程序會重新分配一個 sub-heap,並將 top chunk 遷移到新的 sub-heap 上, 新的 sub-heap 與已有的 sub-heap 用單向鏈表連接起來,然後在新的 top chunk 上分配所需的內存以滿足分配的需要,實際上,top chunk 在分配時總是在 fast bins 和 bins 之後被考慮,所以,不論 top chunk 有多大,它都不會被放到 fast bins 或者是 bins 中. top chunk 的大小是隨著分配和回 收不停變換的,如果從 top chunk 分配內存會導致 top chunk 減小,如果回收的 chunk 恰好 與 top chunk 相鄰,那麼這兩個 chunk 就會合併成新的 top chunk,從而使 top chunk 變大. 如果在 free 時回收的內存大於某個閾值,並且 top chunk 的大小也超過了收縮閾值,ptmalloc 會收縮 sub-heap,如果 top-chunk 包含了整個 sub-heap,ptmalloc 會調用 munmap 把整個 sub-heap 的內存返回給操作系統.
0x7 Last remainder
Last remainder 是另外一種特殊的 chunk,就像 top chunk 和 mmaped chunk 一樣,不會 在任何 bins 中找到這種 chunk.當需要分配一個 small chunk, 但在 small bins 中找不到合適 的 chunk, 如果 last remainder chunk 的大小大於所需的 small chunk 大小,last remainder chunk 被分裂成兩個 chunk, 其中一個 chunk 返回給用戶, 另一個 chunk 變成新的 last remainder chuk.
0x8 保護機制
按照free與malloc分類
free
- free的檢查主要是根據本chunk的size檢測下一塊的inuse位，查看是否有double free的情況發生
- 檢查當前free的chunk是否與fastbin中的第一個chunk相同，相同則報錯
- 根據當前的inuse以及後一塊的後一塊的inuse判斷是否需要合併，如果需要合併則對在鏈表中的freebin進行unlink操作
malloc
- 從fastbin中取出chunk後，檢查size是否屬於fastbin
- 從smallbin中除去chunk後，檢查victim->bk->fd == victim
- 從unsortbin取chunk時，要檢查2*sizet
size - 從 largebin取chunk時，切分後的chunk要加入unsortedbin,需要檢查 unsortedbin的第一個chunk的bk是否指向unsortedbin
- 如果freebin中有合適大小的堆塊那麼執行unlink操作
unlink
- 當需要unlink一個堆塊時首先檢測大小是否等於後一塊的prev_size
- 接著檢查unlink的堆塊是否在鏈表中
下面通過一些代碼進行測試
free 會檢查double free的情況
#include
#include
#include
#include
#include
int
main(){
unsigned
long
*q,*p,*point;
p=malloc(
0x400
);
q=malloc(
0x500
);
point = (
uint64_t
*)q -
1
;
*point =
0x510
;
//this one should be 0x511 to prove p is used
free(p);
}
free 函數會檢查unsorted chunk在鏈表中的情況
首先執行的是unlink，其次會對unsorted chunk在鏈表中的情況進行檢查
#include
#include
#include
#include
#include
unsigned
long
*list;
int
main(){
unsigned
long
*q,*p,*x,*point;
p=malloc(
0x80
);
q=malloc(
0x100
);
x=malloc(
1
);
free(p);
// malloc(0x110); without it freebin will be unsortedbin
list = (
unsigned
long
*)p-
2
;
point = (
unsigned
long
*)p ;
//fd's addr
// *point = &list-3;
*(point+
1
) = &list-
2
;
//canot change the bk's value cas it has pass the check
free(q);
}
鏈表釋放前會檢查當前chunk size 與後一個chunk的prev_size
unlink 後向合併
#include
#include
#include
#include
#include
int
main(){
unsigned
long
*q,*p,*point;
p=malloc(
0x80
);
q=malloc(
0x90
);
malloc(
1
);
free(p);
point = (
char
*)p -
0x8
;
//addr of the chunk size
*point =
0x510
;
//fake size make that size != next_chunk(prev_size)
free(q);
}
unlink 前向合併
#include
#include
#include
#include
#include
int
main(){
unsigned
long
*q,*p,*x,*point;
p=malloc(
0x80
);
q=malloc(
0x90
);
x=malloc(
1
);
free(q);
point = (
char
*)x -
0x10
;
//addr of the chunk size
*point =
0x110
;
//fake size make that size != next_chunk(prev_size) . The value should be 0xa0
free(p);
}
unlink會檢查chunk是否在鏈表裡
free 中的unlink執行雙鏈表檢測
前項合併
#include
#include
#include
#include
#include
unsigned
long
*list;
int
main(){
unsigned
long
*q,*p,*x,*point;
p=malloc(
0x80
);
q=malloc(
0x100
);
x=malloc(
1
);
free(q);
malloc(
0x110
);
//to be come smallbins
list = (
unsigned
long
*)q-
2
;
point = (
unsigned
long
*)q ;
//fd's addr
*point = &list;
//delete this line open two lines after it
// *point = &list-3;
// *(point+1) = &list-2;
free(p);
}
後向合併
#include
#include
#include
#include
#include
unsigned
long
*list;
int
main(){
unsigned
long
*q,*p,*x,*point;
p=malloc(
0x80
);
q=malloc(
0x100
);
x=malloc(
1
);
free(p);
malloc(
0x110
);
//to be come smallbins
list = (
unsigned
long
*)p-
2
;
point = (
unsigned
long
*)p ;
//fd's addr
*point = &list;
//delete this line open two lines after it
// *point = &list-3;
// *(point+1) = &list-2;
free(q);
}
malloc時unsortedbin 不執行unlink
malloc函數會首先搜索smallbin和largebin，當有空閒的unsortedbin時，再搜索unsortedbin，方法是從unsorted的首塊開始進行鏈表的清空（只有malloc會這樣拆卸unsorted表）。所以可以用作unsorted attack
#include
#include
int
main(){
unsigned
long
stack_var1=
1
;
unsigned
long
stack_var2=
2
;
unsigned
long
*q,*p=malloc(
400
);
q=malloc(
500
);
free(p);
//------------VULNERABILITY-----------
p[
1
]=(
unsigned
long
)(&stack_var1-
2
);
p[
0
] = (
unsigned
long
)(q);
//------------------------------------
malloc(
400
);
//this option will check fastbin smallbin ,the last one is unsorted bin .if not find fit chunk in unsorted bin it will make the chunk into small or large bin list，if malloc != 400 it will crash
fprintf(stderr,
"%p: %p\n"
, &stack_var1, (
void
*)stack_var1);
fprintf(stderr,
"%p: %p\n"
, &stack_var2, (
void
*)stack_var2);
}
malloc時smallbin不執行unlink操作
#include
#include
long
long
int
*x;
int
main(){
unsigned
long
stack_var1=
1
;
unsigned
long
stack_var2=
2
;
unsigned
long
*q,*p=malloc(
400
);
q=malloc(
500
);
x = p-
2
;
free(p);
malloc(
0x400
);
//------------VULNERABILITY-----------
p[
0
] = (
unsigned
long
)(&x-
1
);
//this one is Unlimited
p[
1
] = (
unsigned
long
)(&x-
2
);
//-------------------------------------------
malloc(
400
);
//this option will check fastbin smallbin ,the last one is unsorted bin .if not find fit chunk in unsorted bin it will make the chunk into small or large bin list
fprintf(stderr,
"%p: %p\n"
, &stack_var1, (
void
*)stack_var1);
fprintf(stderr,
"%p: %p\n"
, &stack_var2, (
void
*)stack_var2);
}
總結
具體的總結如下，終於可以好好的總結一下了。1.freefree 操作裡面會有子操作unlink，unlink（會進行雙向鏈表檢測，檢測過後就是賦值操作）。
如果是smallbin chunk直接進行unlink檢測
如果是unsorted chunk還需要對其進行unsorted檢測
之後會有一個對於鏈表的操作
2.mallocmalloc裡面是不執行unlink操作的，對於smallbin只會檢測 p->bk-fd==p對於unsortedbin 不會進行檢測，所以會造成unsorted attack攻擊
3.all最後就是每次在free list中卸掉鏈表都需要對所拆鏈表的size和下一塊的prev_size進行比較。這一點不論是free還是malloc都遵循。
未完待續......
閱讀更多 合天網安實驗室 的文章
