資安 pwn 技術研究所：Heap pwn 篇 (3) – Free 與 alloc 流程

~ me

~ 檢查 ~

Free 之前，會用一系列的 check 檢查：

  1. chunk 是對齊 2*SIZE_SZ 的整數倍
    • 同前文：在 64-bit 環境下，SIZE_SZ=8；32-bit 環境下 SIZE_SZ=4。
  2. free 是可行的。例如不是太小、太大、不對齊，或越過了程式的邊界的地址空間。
  3. chunk 是在 arena 的址址空間內。
  4. chunk 不是已標記成 freed。這是檢查下一個 chunk 的 PREV_INUSE bit。

~ Free 演算法 ~

Free 的演算法如下所示：

  1. 如果 pointer 為 null，則不用運行 free；
  2. 將 chunk 變成 free 狀態（但未必會將下一個 chunk 的 PREV_ISUSE 設為 0，視乎哪一個 bin）
  3. 做上面的 sanity check 檢查；
  4. 若可以放進 tcache bin，就放進去；除非滿了七個，就繼續往下面；
  5. 如果 IS_MAPPED=1，那麼是要 munmaped；
  6. 否則就要取得 thread heap lock，然後做下面步驟；
  7. 若可以放進 fast bin，就放進去；
  8. 若 chunk 大於 64KB，就將 fastbin 都放進 unsorted bin；
  9. 若前一個 chunk 是 freed，那麼就會向前合併。若下一個 chunk 是 freed，那麼就會向後合併；然後放進 unsorted bin；
  10. 若是處於邊界，就會做 trimming，而不會進入 bin；
  11. 若以上皆不是，就會標籤為 freed，然後放進 unsorted bin。
  12. 完。

~ malloc 演算法 ~

malloc 演算法如下所示：

  1. 若 tcache bin 有適用的 chunk，就用；
  2. 若 size 是大到需要用 mmap，就用；
  3. 否則就要取得 thread heap lock，然後做下面步驟；
  4. 檢查 fastbin 和 small bin
    • 若 fastbin 有，就用；
    • 否則，若 small bin 有，就用；
    • 有可能將 chunk 升級進 tcache bin
  5. 檢查 unsorted bin
    • 將 fast bin 的都解放進 unsorted bin
    • 若 unsorted bin 有，就用，而且停下；否則，就將檢查到的 unsorted bin chunk 放進 small 或 large bin；
    • 有可能將 unsorted bin chunk 升級進 tcache bin
  6. 檢查 large bin
    • 若 size 是符合 large bin，就檢查 large bin；同樣，有，就用；
  7. 造出新 chunk
    • 若以上都不符合，就嘗試從 top of the heap 取得；
    • 若 top of the heap 不夠大，就運行 sbrk 以增大；
    • 若 top of the heap 不能增大（即 sbrk 失敗），就運行 mmap 以取得 chunk；
  8. 若以上都不合，則回傳 NULL

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

未知 的大頭貼

發表者：me

:)