資安 pwn 技術研究所：Heap pwn 篇 (2) – 各種 bin 格式

~ me

bin 是個 array。共有 126 個 bin。如上圖。即共有：

  1. 62 個 small bin
  2. 63 個 large bin
  3. 1 個 unsorted bin
  4. 10 個 fastbin
  5. 64 個 tcache bin per thread

~ small bin ~

  1. small bin 是整齊排好的
  2. 從最小的 兩個「2*SIZE_SZ」單位開始，每個 ID 遞增一個單位。
    • 同前文：在 64-bit 環境下，SIZE_SZ=8；32-bit 環境下 SIZE_SZ=4。
    • 所以 32-bit 下，small bin 1 是 2*2*4=16；64-bit 下 small bin 1 是 2*2*8=32。
    • 之後每個遞增 2×4=8 (32 bit) 或 2×8=16 (64 bit)
    • 最大的為 63*2*4=504 (32 bit) 或 63*2*8=1008 (64 bit)
    • 例如 32-bit 0x10=16 是進入 small bin 1，加上 metadata 為 size=0x20

~ large bin ~

large bin 是有不同大小。如上圖。

~ unsorted bin ~

以上三個是基本機制：

  1. 先進入 unsorted bin。
  2. 到 malloc 在 unsorted bin 尋找時，若符合的 chunk 它就會直接用；若不符合的 chunk 它就會整理到 small bin 或 large bin中。而永遠都只有一個 small bin 或 large bin 符合任何一個 size。
  3. 若 free 當中合併了，或釋放了，都會進入 unsorted bin。
  4. 然後加上了下面 fastbin 的機制

~ fastbin 機制 ~

  1. fastbin 有 10 個。大小時和頭十個 small bin 一樣。
    • 32-bit 下，fast bin 1 是 2*2*4=16；64-bit 下 fast bin 1 是 2*2*8=32。
    • 32-bit 下，fast bin 10 是 11*2*4=88；64-bit 下 fast bin 1 是 11*2*8=176。
    • 例如 32-bit 0x10=16 是進入 fast bin 1，加上 metadata 為 size=0x20
  2. fastbin 的方式，是沒有真正 freed。它的下一個 chunk 的 PREV_INUSE 仍為 1。
  3. fastbin 內的 chunk 因為沒有真正 freed，所以也不會合併
  4. 因為沒有合併，所以不需要 double linked-list。fastbin 內只是一個 single linked-list。

~ tcache bin 機制 ~

  1. tcache bin 是用來處理 multi-threading 中的 race condition、lock 之類的資源浪費或問題。是可以加速程式的運行效率。
  2. tcache bin 有 64 個 (per thread)。每個 bin 最多有 7 個 chunk。
    • 64 bit 的由最小的 24，遞增 16，至 1032 (63×16 + 24)（0 – 24 size 都進入 tcache bin 1，例如 0x10=16 是進入 tcache bin 1）
    • 32 bit 的由最小的 12，遞增 8，至 516 (63×8 + 12)
  3. 若 tcache bin 滿了，則會流動到其他 bin

~ Reference ~

Part 2: Understanding the GLIBC Heap Implementation
https://azeria-labs.com/heap-exploitation-part-2-glibc-heap-free-bins/

Glibc Malloc Principle
https://www.openeuler.org/en/blog/wangshuo/Glibc%20Malloc%20Principle/Glibc_Malloc_Principle

《資安 pwn 不正常技術研究所》系列：

未知 的大頭貼

發表者：me

:)