# [HEAPSTER: Analyzing the Security of Dynamic Allocators for Monolithic Firmware Images](https://degrigis.github.io/bins/heapster.pdf)

## Abstract

* 動態內存分配器(Dynamic memory allocators)是系統中的關鍵元件，需要在安全與性能之間找到平衡
* 動態內存分配器也用於 IoT 設備，但沒有受到嚴格的安全審查
* IoT 設備中，firmware image 通常是唯一可用的資訊，但找 heap 相關的漏洞是手動且困難的
* 且模擬韌體來測試 heap 漏洞會帶來一系列挑戰
* 為了填補這空白，該論文提出 HEAPSTER，是一個自動識別單片韌體使用的 heap library 的系統，透過符號執行和有界模型來檢查安全性
* 收集了 20 個單片韌體資料集和 799 個實際設備的單片韌體來評估
* 確認 11 個不同的 heap management library(HML) 系列，包含 48 個變體。每種已辨識的韌體都發現至少一個嚴重漏洞

## Introduction

* 動態內存分配器負責在程式執行時保留適當大小的內存
* 塊的數量和大小會受到許多因素影響，開發時需要考慮性能和安全
* 有些開發人員認為 heap 保護是攻擊後的緩解措施，攻擊應該在應用程式中解決而不是在 heap library 解決，但該論文認為至少應防止簡單的錯誤(ex: a one-byte overflow)
* IoT 中的動態內存分配，需要在有限的資源下執行，有時還要考慮時間，在工業控制系統中，安全性更加重要。
* Linux-based 和單片韌體都有動態內存分配，但後者更難分析
* 只有 binary 檔案沒有 source code
* 沒有傳統的作業系統，應用程式和 lib code 難以定位
* 不同的設備有不同的要求，開發人員可能會自己實現分配器而沒經過審查
* 其他 heap 實作的安全性論文
* HeapHopper 利用符號執行和有界模型檢查動態分配器的安全性
* Insu et al. 用模糊測試實現不同 lib 的攻擊面
* 還有一堆針對現有 lib 的修補和重新設計
* 沒有針對 IoT 系統的動態分配器研究
* 傳統上認為在 IoT 上實作動態內存分配器是不好的做法，但現在 RTOS 的技術和資源進步，動態分配器已經頻繁出現
* 提出了 HEAPSTER，是一個框架，用於識別、分類、測試單片韌體映像使用的 heap management library 的安全性
* 透過辨識如何在 firmware image 中生成和使用 pointer 來辨識那些 function 是動態分配的 interface(ex:malloc free)
* HEAPSTER 識別完 allocator 和 de-allocator 的 prototypes 後，會去了解適當的參數並調用
* 最後執行有界模型檢查分析，檢查是否存在常見的 heap 漏洞，發現漏洞時會產出 PoV
* 基於 HeapHopper 去修改
* 使用兩個資料集，第一個是其他論文的，第二個是現實世界的
* 結果表明有 11 種 HML 系列，包含 48 種變體，每一種都能找到至少一個 PoV
* 貢獻
* HEAPSTER 是第一個自動識別單片韌體的 HML 並測試安全性的系統
* 透過修改 HeapHopper 實現 Heap 安全測試
* 展示了一組從 Firmware 回復的低安全性的 HML
* [開源](https://github.com/ucsb-seclab/heapster)

## Challenges and Goals

### Firmware Loading

* 單片韌體有自定義格式，像自定義入口或內存給特定裝置使用
* 當分析工具不支援韌體的指令集時，連模擬都很困難
* 只關注 ARM CortexM 架構
* 假設 Metadata 都已知
* 目標是識別特定函數的邊界

### HML Identification

* 單片韌體可能包含數百個功能，要找出和 Heap 相關的功能需要自動化
* 專注於識別 low-level dynamic memory allocators
* 至少有兩個 primitives
* 分配和釋放
* 即時的處理每個服務，每次分配時要計算下一塊的大小
* 內存管理系統，塊未來要能被重新使用
* 透過參數接收分配的大小、透過參數釋放
* 分配的內存地址丟到暫存器 return 給呼叫者

### Firmware Initialization

* Heap 相關的初始化與其他初始化有關，因此在測試 Heap 安全性前需要先識別並執行所有初始化

### Firmware Re-hosting

* 系統利用動態執行目標 function，而不是完全模擬
* 缺少的外部模型和原始環境可能會影響分析
* 本文專注於模擬有限數量的功能，利用執行模型解決問題

### Symbolic Execution Scalability

* 系統利用符號執行和有界模型檢查發現 Heap 漏洞
* 符號執行會路徑爆炸且 cost 高，因此需要定義分析範圍

## Approach

* 
1. 將 firmware 和 metadata 輸入到模擬器中
2. HEAPSTER 辨識會進行記憶體相關操作的 function(ex: memcpy)
3. 利用 inter-procedural source-sink 分析 return 的 pointer
4. HEAPSTER 逐一模擬 pointer，監視他們的行為是否為內存分配器
5. 根據內存分配器找到對應的釋放器
6. 7. 8. 找到一對分配器時，收集更多 Prototypes 的資訊和他們的實作
* HML 的 metadata 等，用於管理內存的數據

9. 把前面收集到的資訊丟給 HeapHopper 分析
10. 自動生成 PoC(靜態)
11. 利用符號執行和有界模型檢查生成 PoV(動態)
12. 透過模擬器再生成一次 PoV 避免誤報

### Firmware Loading

* 需要四個資訊
* the base address
* the entry point
* the memory range covered by the dynamic memory
* MMIO range
* 前兩項由 Firmxray 拉過來用
* 剩下兩個由 CPU 架構的官方規範設定

### Firmware Functions Classification

#### Basic Functions Identification

* 想法源於 Sibyl
* 某些基本 function 的行為是可預測的
* memcpy 執行完後，dest 應該有 src 的 n 個 bytes，且 src 不會變
* HEAPSTER 會辨識每個 function，與九種模型匹配
* memcpy 和 memset 和他們的變體
* memcmp
* strlen strcat strncat strncpy

#### Pointer Source Identification

* 為了辨識指標來源，HEASTER 會從基本 function 的使用點開始，利用 Reaching Definitions data-flow 來分析參數如何生成
* 使用 function 的時候，RD 會建立一個有向圖
* node 是暫存器
* edge 是依賴關係
* node 還會有兩種標籤
* RetVal: 這個暫存器是 return 值
* Arg: 這個暫存器是 function 參數
* 
* 分析到恆定值就停止，忽略遞迴因為沒意義

### Allocator Identification

* 不是每個辨識的指標都是內存分配器，像上面的 baz 只是回傳一個指標常數
* 所有 malloc 函數也都會被標記成指標來源，即使他不在參數安全範圍
* 如果執行多次 function，返回的內存空間都在 heap 區域，才標示為分配器

#### Pointer Sources Execution

* 檢查分配器有正確的參數
* malloc 參數是整數...

#### Pointer Sources & Heap Initializers

* Pointer Sources 的成功模擬取決於全域變數的初始化
* 例如上圖的 last 就是全域變數
* Heap 相關的全域變數可能
* 在 entry point 初始化
* 由 heap 相關的 lib 初始化
* 混和兩種
* 解決方法：動態執行 firmware 的 entry point(ResetHandler)
* 如果執行階段還是有找不到的全域變數，選一組其他的初始化 function 來用或是設為 0

### De-allocator Identification

* 有 function 做記憶體分配的時候，應該要有另一個 function 做釋放

#### Deallocator Candidate Test

* 先利用靜態分析找出那些非基本 function 有做釋放，接著要將他們和分配的 function 配對
* 配對步驟
* 呼叫分配 function A `X` 次，回傳值為 a1 ~ ax
* 呼叫釋放 function D `X` 次，參數為 a1 ~ ax
* 再次呼叫分配 function A `X` 次，看看回傳值是否等於 a1 ~ ax
* 配對成功時，將 (A, D) 這個 pair 當作是這個韌體的 HML

#### HML Pairs Filtering

* 為了避免配對誤報，去檢查 HML 中是否有重複的分配器
* 重複的就解除

### HML Analysis

#### Prototype Recovery

* malloc 和 free 有許多不同的實作方式，不能只認為只有 malloc(size) 和 free(*ptr) 這兩種
* 因此有多個參數時，需要找到哪個參數是 size 和 *ptr
* 檢查方式是依序將每個參數當作符號值做符號執行，並檢查哪個參數的約束條件最多

#### Hotspot Detection

* 有時候韌體發生錯誤時，程式碼會藉由無限迴圈等方式讓韌體停頓，這在符號執行時會導致分析卡死
* 為了檢察這些 function，會提供合法和無效的參數來分析 malloc 和 free 是否正常
* 有地方卡死時，會記住該 function，未來執行時就跳過
* 跳過的 function 因為使韌體停頓且永遠不會 return，因此不太會導致 heap 的分析產生誤報
* 後續生成的 PoV 不會跳過任何 function

#### HML Properties

* 符號執行時會需要知道
* heap base address
* heap growth direction
* size of inline metadata

### HML Model Definition

* 得到 HML 後進行安全測試的元件是 HeapHopper

#### Heap Transitions

* HeapHopper 會將 HML 轉換成狀態機，進而檢查是否出現
* DF: Double free
* FF: Fake free
* UAF: Use after free
* O: Heap overflow

#### Heap Vulnerabilities

* 如果沒有針對 exploitation primitives 防禦，可能還會出現以下漏洞
* OC: Overlapping Chunks
* NHA: Non-Heap Allocation
* AW: Arbitrary Write
* RW: Restricted Write

### HML Bounded Model Checking

#### HeapHopper Analysis

* HeapHopper 藉由符號執行執行安全分析，發現問題時會產生 PoC
* 接著會將所有符號值都換成具體值，產生 PoV

### PoV Validation

* HeapHopper 論文中有提到誤報這個問題
* HEAPSTER 為了避免誤報，生成 PoV 時會不跳過任何有問題的 function 重新模擬一次 PoV
* 如果沒觸發漏洞就丟棄該 PoV

### HeapHopper Modifications

* 修改 HeapHopper 讓它支援 ARM CortexM CPU
* PoC 生成
* 生成 ARM 的 Binary file
* 支援 malloc 和 free 的不同變體
* PoC 載入
* 模擬 PoC 測試程式時會把整個 firmware image 當作一個 libary 載入
* Arbitrary Write Model
* 就模型的名字換一下而已

## Implementation

* 在 angr 上用 Python 實作

### Firmware Preparation

* 藉由 FirmXRay 找出 entry point 和 base address
* 藉由 angr 建立 CFG，辨識出 function 數量、參數和可能的 return 值

### Static Analyses

* 利用 angr 分析 Reaching Definitions data-flow，推斷暫存器和 pointer 的關係

### Functions Emulation

* 利用 angr 的 VEX 引擎動態執行韌體的 function

## Evaluation

* 兩次評估
* 小規模、20個韌體，包含 stripped 和保有 symbols 的韌體
* 大規模、799個韌體，全部都沒有 symbols
* 分四個部分探討
* HML 識別
* 大致的 HML 分類
* 細緻的 HML 分類
* 安全分析

#### HML Identification

* 每個韌體跑 72 小時
* 記憶體限制 70 GB

#### Coarse-grained Clustering

* 希望可以識別同一個 heap library 的分配器
* 做法是對 malloc 的 function 做 Bindiff，相似度 > 0.7 就是同一類
* 0.7 是經驗法則
* 某些異常值手動修復

#### Fine-grained Clustering

* 目標是識別相同的 HML
* 相同的 HML 通常有相同的漏洞
* 做法是對 malloc 和深度 4 以內 call 到他的 function 都做 Bindiff，相似度 = 1.0 就是同一個 HML

#### Security Evaluation

* 給定一個 exploitation primitive，跑深度 7 以內的所有組合

### Ground-Truth Dataset

#### HML Identification

* 平行化分析，48 小時完成所有韌體的分析
* Pointer Source Identification 最花記憶體
* Deallocator Identification 最花時間(3.5h)
* 18 個樣本成功的把 memcpy 最後的指標標記成指標源
* 多個參數的 malloc 和 free 都成功找出 size 或 ptr 的那個參數

#### Coarse-grained Clustering

* 
* HML 分成了三組
* 實際上確實對應到 nano_malloc, newlib_malloc 和 lwip_malloc

#### Fine-grained Clustering

* 發現 A 組中有 8 個子集合、B 組有 6 個子集合、C 組有 2 個
* 手動驗證發現結果是對的

#### HML Security Evaluation

* 測試了所有 20 個 HML，每個平均需要分析 2k 個 PoC
* 總共花了 27 小時完成
* 

#### Results Discussion

* 結果發現 A B 特別容易受到 OC、NHA 和 RW 攻擊
* A3 A4 B 會受到 AW 攻擊
* C 只會受到 OC 攻擊

### Wild Dataset

#### HML Identification

* 799 個韌體中發現了 340 個 HML
* Allocator Identification 最花記憶體也最花時間(2.4h)
* 有 17 個樣本花太多時間而中止
* 雖然 Wild 資料集更大更複雜，但平均表現更好
* HML 橫跨了穿戴裝置、感測器和醫療設備等不同設備中

#### Coarse-grained Clustering

* 
* 有 10 種類型，其中 E 和前面的 A 一樣、J 和前面的 B 一樣
* 多了 8 種類型

#### Fine-grained Clustering

* 共 32 種變體

#### HML Security Evaluation

* 為了加快分析速度，每一種變體只測試一個 HML，共測試 32 個
* 每個 HML 分析 2k 個 PoC，每個最多跑 10 分鐘
* 單個 HML 跑不超過 3 小時，總共分析了 36 小時
* 每個 PoV 生成跑 5 分鐘，超過就當作誤報
* 成果一樣寫在上面的圖

#### Results Discussion

* 所有變體都可能受到 OC 和 RW 影響
* 如果能在程式碼中找到 exploitation primitive 就能攻擊 heap

### HML Identification: False Negatives

* HEAPSTER 有時候會沒找到 HML，使用 BinDiff 時確有發現
* 另外在對比 HML 是否完美匹配時，BinDiff 有時會沒匹配到一樣的 HML，那是因為反組譯不精準的關係
* 誤報的原因大多是因為 HEAPSTER 沒找到 allocator function，這代表他沒找到對應的初始化 function

### Security Impact of Vulnerabilities in HML for Applications

#### Threat Model for Applications

* 如果 MMIO 讀取的 function 連接到 malloc 或 free 等 function 時，就可能導致 HML 受攻擊

#### Manual Investigation

* 人工調查後發現了 4 個可能受到整數溢出錯誤影響的韌體
* 雖然該漏洞的發現表明可以實踐並應用，但需要 re-hosting 的方法來確認

#### Hardware Example

* 為了驗證，透過 STM32-NucleoF401RE 加上 X-NUCLEO-IDW01M1 Wi-Fi 擴充，來驗證漏洞是否存在
* 使用 Mbed Studio IDE 選擇對應的 HML
* 實驗發現該 HML 確實受到所以發現的漏洞

## Discussion and Limitations

* 分析成果取決於 CFG 的精度，該論文依賴 angr
* Heap 的初始化失敗時會直接用 0 初始化，這可能導致誤報
* 本文將所有存取 MMIO 的 function 當作攻擊者的進入點，但實際上這些 function 不一定都會接收使用者輸入

## Conclusions

* 介紹了 HEAPSTER，自動識別單片韌體的 HML 並測試安全性
* 實作使用了 HeapHopper 的修改版本
* 評估表明可以識別 HML 並測試是否存在嚴重漏洞

###### tags: `paper`