Heap Exploitation - ianchen0119/About-Security GitHub Wiki

Heap 是什麼?

在本頁提到的 Heap 與資料結構的 Heap 不同，這邊的 Heap 是指可供作業系統與 Process 分配的記憶體空間，我們都知道， Stack 會存放已經初始化的固定長度資料，比起 Stack ， Heap 有了更多彈性，我們想要使用多少空間就分配多少空間，並且在使用後可以進行記憶體回收避免浪費。

#include <stdlib.h>
int *p = (int*) malloc(sizeof(int));
// ...
free(p);

上面的 C 語言範例便是使用 malloc() 進行動態記憶體的配置，並且在使用完畢後呼叫 free() 對記憶體進行回收。

Memory Layout

觀察上圖，我們可以知道 Heap 是由底部往上分配的，與 Stack 恰恰相反。

Memory allocator 的實作

在 Linux 中，由 memory allocator 由 glibc 實作，更多資訊如下:

  • dlmalloc -- General purpose allocator
  • ptmalloc2 -- glibc
  • jemalloc -- Firefox
  • tcmalloc -- chrome

動態記憶體的分配流程

  • 第一次呼叫 malloc() 
           size >= 128 KB
+--------+ -----> +--------+ -----> +------------+
| malloc |        |  mmap  |        |  sys_mmap  |
+--------+        +--------+        +------------+
         |
         |                           trap to kernel
         | size < 128 KB
         + -----> +-------+ -----> +-----------+
                  |  brk  |        |  sys_brk  |
                  +-------+        +-----------+

當我們第一次呼叫 malloc() 且要求的大小小於 128 KB 時， sys_brk() 都會分配 132 KB 的 Heap 段落，該段落稱為 main arena 。 這時，如果我們在程式中再次呼叫 malloc() ，只要已分配出去的大小不多於 128 KB ，都不會再執行系統呼叫向作業系統要求更多空間。

補充: 一旦作業系統分配給 Process 這段空間 (main arena) ，即使在程式執行中呼叫 free() 釋放了這些空間，也不會立刻返回給作業系統，而是由 glibc 代為保管。

Heap 中的資料結構: Chunk

使用 malloc() 分配的空間就是一個 Chunk ， Chunk 主要由兩個區段組成:

  • Chunk header
    • prev_size
    • size
  • user data

此外，這些可用的 Chunk 會由鏈結串列管理，該鏈結串列的 Head 稱為 bin 。

Bin & Chunk

Chunk 會以大小進行分類，不同種類的 Chunk 會由個別的 bin 進行管理，像是:

  • fastbin (size <= 64B)
  • smallbin (size <= 512B)
  • largebin (size <= 128KB)
  • unsortedbin

至於 Chunk 主要有三類:

  • Allocated Chunk
    • prev_size Chunk 基本上會放在一大段的連續記憶體中，如果該 Chunk 的上一段(實際記憶體的上一塊) Chunk 為 free chunk ， prev_size 會存放上一塊 chunk 的大小。
    • size size 會存放該 Chunk 的大小，其中還包含了三個 flag:
      • PREV_INUSE (bit 0) -- 紀錄上一塊 Chunk 是否被使用 。
      • IS_MMAPPED (bit 1) -- 紀錄該 Chunk 是否由 mmap 分配。
      • NON_MAIN_ARENA (bit 2) -- 是否不屬於 main arena 。
  • Free Chunk
    • prev_size
    • size
    • fd (pointer to next chunk)
    • bk (pointer to last chunk)
  • Top Chunk 前面提到了，在第一次呼叫 malloc() 且要求的大小小於 128 KB 時， sys_brk() 都會分配 132 KB 的空間，這時實際上用到的即為 Allocated Chunk ，剩下的皆是 Top Chunk 。 之後再呼叫 malloc() 的話，只要大小足夠，都會從 Top Chunk 切割空間。

Free Chunk 的變化(分配記憶體時)

我們都知道，不同的 Chunk 會由不同的 bin 管理，當呼叫 malloc 與 free 時，管理 Free chunk 的 bin 會有以下變化:

  • 原本的狀態:
      +--------+ -----> +--------+ -----> +--------+
bin   |        |        |        |        |        |
      +--------+ <----- +--------+ <----- +--------+
  • 呼叫 malloc():
         +--------------------------+
         |                          |
         |                          V
+--------+ - x -> +--------+ - x -> +--------+
|        |        | malloc |        |        |
+--------+ <- x - +--------+ <- x - +--------+
         ^                          |
         |                          |
         +--------------------------+
  • 呼叫 free():
         +----------- X ------------+
         |                          |
         |                          V
+--------+ -----> +--------+ -----> +--------+
|        |        |  free  |        |        |
+--------+ <----- +--------+ <----- +--------+
         ^                          |
         |                          |
         +----------- X ------------+

Heap Buffer overflow

link

References

⚠️ **GitHub.com Fallback** ⚠️