Hybrid Fuzzing Paper Summary

簡介

Hybrid Fuzzing 是結合了 Fuzzing 和 Symbolic Execution 的分析技術，能夠結合兩種技術的優點，同時互補不足。但是在兩者的結合中，涌現出一些新的問題。本文對近年來在頂會及相關知名會議中發表的 hybrid fuzzing 論文進行梳理。

背景

Fuzzing

fuzzing 又稱模糊測試，是一種輕量級的動態測試方法，通過不停變異輸入，輸入給測試程序，觀察程序運行是否表現異常來檢測是否存在漏洞。fuzzing 以其快速高效的效果，成為近年來較為流行的漏洞挖掘技術。

fuzzing 的優點在于快速高效，以 AFL 為代表，AFL 是一種 Coverage-guided fuzzing，追求盡可能的覆蓋到多的代碼，每當有變異的輸入覆蓋到新的代碼，就將該輸入保存下來作為 seed，后續在其之上繼續變異。通過這樣不停迭代，探索到更多的代碼區域。

但由于 fuzzing 的變異通常是隨機的，對于一些簡單的條件分支語句，因為 fuzzing 的速度夠快，能夠很快的探索輸入空間從而滿足條件，但是對于一些復雜的條件語句，fuzzing 需要探索的輸入空間巨大，很難在有限的時間內探索到。

Symbolic/Concolic Execution

symbolic execution 符號執行是程序分析技術的一種，通過采用抽象的符號來代替實際執行值，作為程序的輸入變量，得到每個路徑抽象的符號表達式，最后對符號表達式進行求解，得到一個具體的變量值，該具體值就可以執行該條路徑。

這里提到的符號執行是靜態的，并不是真實的執行，每分析到一個分支語句，需要構建 true 和 false 兩條路徑的表達式，故復雜的程序路徑數量往往成指數倍的增長，導致路徑爆炸 (path exploration) 的問題。

動態符號執行 (Dynamic symbolic execution) 是傳統靜態符號執行的一種變體，是同時使用符號值和具體值進行執行的一種方法，所以又稱為 concolic execution，意為 concrete + symbolic (實際執行 + 符號執行)。concolic 執行會首先產生一些隨機輸入，用這些輸入喂給程序運行，在運行過程中同時符號化的執行程序。因為采用的是具體的輸入，所以執行該輸入的時候，只會沿著這個輸入的路徑進行執行，在分支處對條件進行取反，求解得到該路徑分支上另一條路徑的解，生成新的測試輸入，再將新的輸入讓程序執行，就會得到另一條沒有被執行過的路徑，如此循環，來完成對所有路徑的探索。

所以實際上，concolic 執行采用的是深度優先的搜索策略，每次 concolic 執行會沿著某一個輸入的路徑，完整執行程序到結束，然后再對路徑上沒有測試的路徑約束條件取反，得到新的輸入，再將新輸入給程序執行，進入新的路徑。

符號執行技術無論是靜態還是動態，相對于 fuzzing 來說，開銷是很大的，但是其針對復雜的條件語句是非常有效的，能夠求解很多僅僅依靠 fuzzing 隨機變異策略無法滿足的約束條件。

Hybrid fuzzing

hybrid fuzzing 混合模糊測試，實際上就是將 fuzzing 和 concolic execution 結合起來，在 fuzzing 的同時，用 fuzzing 產生的輸入給 concolic execution 執行。

由于 fuzzing 的高效，能夠快速探索大部分的程序路徑，生成大量的輸入，當遇到復雜的約束條件時，可以求助于 concolic execution。concolic execution 可以幫助 fuzzing 求解復雜的約束條件，而 fuzzing 可以為 concolic execution 快速探索程序路徑。

Driller

hybrid fuzzing 的概念提出的很早，但2016年的 Driller 是最早將 hybrid fuzzing 應用實際的論文，Driller 本質上是將 AFL 和 angr 簡單結合起來，當 AFL 停滯不前的時候，就切換 angr 進行求解，幫助 fuzzing 過復雜的約束。

QSYM

2018年 QSYM 被提出，文章中提到現有的 concolic execution engine 并不是為 hybrid fuzzing 定制的，存在很多性能上的瓶頸，QSYM進行很多優化：

(1) 首先，用動態二進制翻譯 (Dynamic Binary Translation) 取代 IR (Inter Representation)來執行，現有的符號執行引擎采用 IR 來執行處于工程上的考量，因為 IR 指令數量少，實現相對容易，但是將二進制程序指令轉化為 IR 只能以基本塊為單位，但是基本塊中的指令并不是全部與輸入有關，一些無關指令可以跳過，但是基于 IR 的符號執行無法進行指令級的優化。所以 QSYM 放棄 IR，轉而使用DBT，對每條二進制指令進行動態插樁，進行符號執行。

(2) 放棄了符號執行中的快照機制，因為傳統的符號執行需要在分支處進行分叉，分為 true 和 false 兩個分支，故路徑是成指數倍增長，為了避免多條路徑重復執行的開銷，引入了快照機制，將分支處的狀態保存下來，以待后續繼續執行。但在 hybrid fuzzing 的場景中，fuzzing 產生的輸入完全是隨機的，并不一定是有相同的前綴路徑，快照對于 hyrbrid fuzzing 中的 concolic engine 來說沒有什么用，所以直接放棄快照。

(3) 對求解的優化，有時候符號執行會遇到 over-constraint 問題，此時對收集的部分約束進行求解，即便它不完整，能夠解決over-constraint的問題。

(4) 對基本塊進行剪枝，記錄下已經求解的分支，后續不再求解，并對基本塊出現的次數進行檢測，如果基本塊重復出現多次，則進行剪枝，同時記錄基本塊出現的上下文，當上下文不同時則會保留，避免過度剪枝。

QSYM 的效果很好，且完全適配 AFL，缺點是只支持 X86 的部分指令。

問題

當然，hybrid fuzzing 也不是那么無敵，也存在很多問題：

(1) 由于 symbolic execution 自身的原因，執行起來很慢，開銷很大。

(2) concolic execution 和 fuzzing 的結合，由于 fuzzing 產生輸入的速度很快，concolic execution 不可能將這些seed全部執行一遍，所以需要對這些輸入進行調度，換句話說，就是對 seed/path 進行排序，決定哪些輸入應該先被執行。

(3) 當符號執行構建的約束過于復雜時，求解器也無法對這些約束求解。

(4) 在將hybrid fuzzing 應用到其他領域時，例如 OS kernel 上，需要解決特定的應用問題。

論文解讀

DigFuzz

本文認為，現有的 hybrid fuzz 存在兩種策略：

(1) 一種是 demand launch，即按照需要，在 fuzzing 過程停滯不前時，采用 concolic execution 幫助求解分支條件。這種方式比較笨拙，當 fuzzing 進行的過程中的時間被浪費了。

(2) 還有一種是 optimal switch，即對一條路徑用 fuzzing 探索和用 concolic execution 進行探索的代價進行評估，用代價最小的方式。但是評估 concolic execution 的開銷需要收集路徑約束，這個代價本身就很大了。

所以本文提出一種 discriminative dispatch 的策略，用一種代價較小的方法評估每條路徑的難度，按照探索難度對路徑進行排序，將難度最大的路徑留給 concolic execution 進行探索。

這里的難點在于，如何用一種輕量級的方法評估一條路徑的探索難度，DigFuzz 提出基于蒙特卡洛的路徑概率排序模型 (Monte Carlo Based Probabilistic Path Prioritization Model, MCP3)，在 fuzzing 的過程中，用 seed 的 trace 構建執行路徑樹，用覆蓋率計算每個分支的概率，路徑的概率為路徑上分支的概率相乘，最后基于路徑的概率對路徑進行排序，概率越小代表路徑越難探索，將最難探索的路徑優先給 concolic execution 進行探索。

Savior

本文認為，現有的 coverage-guided hybrid fuzzing 忽略了對漏洞的檢測問題：

(1) 存在漏洞的代碼是少數，所以以coverage為導向引導不是最佳策略

(2) 即便能夠到達存在漏洞的代碼位置，很多漏洞因為沒有滿足特定的數據條件，也未必能觸發漏洞。

Savior 認為應該以 bug 為導向，針對上述兩個問題，Savior 采用兩個方法來解決：

(1) bug-driven prioritization：采用靜態分析得到每個分支可以到達的基本塊數量，動態分析得到 seed 執行路徑上未探索分支，綜合可以得到這些未探索分支可以到達的基本塊數量。利用 UBSan (Undefined Behavior Sanitizer) 在每個基本塊上標記的數量來表示存在漏洞的可能性大小，綜合上述 metric 用于對 seed 進行排序。

(2) bug-guided verification：提取執行路徑上的 UBSan label，并對這些 label 中的 predicate 進行驗證，即用 concolic execution 為這些 label 生成約束并求解，驗證 label 中的 predicate 是否滿足。

雖然 Savior 的 key idea 是 bug-driven hyrbrid fuzzing，實際上也是對 seed 做了一個排序，只是這個排序是基于 UBsan 和 trace 中到達基本塊數量做的。

MEUZZ

本文一作和 Savior 是同一人，所以思路也是相似的，也是對 seed 做一個排序調度，只不過本文是基于機器學習的方法做的。

本文認為，seed selection 在 hybrid fuzzing 中有很重要的作用，因為 fuzzing 速度遠大于 concolic，由于時間和資源有限，concolic execution 只能執行部分的 seed，故需要對 seed 進行調度排序。

而現有的工作對 seed 的挑選都是基于一些啟發式規則，這些規則并不能完全適用于所有程序。基于學習的方法是最適合于不同的程序的，可以根據程序的執行情況進行學習，從而調整 seed selection 策略。

所以 MEUZZ 提出基于機器學習的方法來進行 seed selection。首先是對程序和 seed 進行特征提取，然后對 concolic engine 產生的每個 seed 構建一個后代樹，記錄在 fuzz 過程中，從該 seed 產生的后代 seed，將這棵樹的大小，即 node 數量作為 seed 的 label，在 hybrid fuzzing 過程中不斷更新模型，挑選 seed。

Intriguer

問題

本文認為，hybrid fuzzing 中還存在一些問題可以改進：

(1) 符號模擬非常慢

(2) 一些不必要的求解占據了大多數的時間

(3) 資源被過度分配

(4) 一些難觸發的漏洞被忽略了

下面具體來說明一下這些問題：

符號模擬執行慢

根據本文調研，發現程序中大部分的數據轉移指令，例如 mov 一類的指令，在程序中占比很大，但是這些指令沒有符號模擬的必要，因為只需要對 mov 指令的前后兩條指令的數據的值進行比較，就可以知道數據的轉移位置。

所以，如果可以避免這些 mov 類的指令執行，可以大大縮短符號模擬的時間。

不必要的求解

程序中存在一些復雜的函數，例如 hash 函數，加密解密函數，壓縮函數等等，這些函數操作非常復雜，涉及的輸入很多，且容易產生無法求解的約束，減少對這些約束的求解，避免多數時間浪費在這些不必要的求解上。

資源過度分配

concolic execution 相比 fuzzing，求解能力強很多，類似 magic byte 這樣程序中常見的約束很容易解掉，但是本文認為，類似于x == 0xdeadbeef，以及x > 0 ^ x < 1000這樣的約束，都不是真正復雜的約束，應該將 solver 用在真正復雜難解的約束上。

難以觸發的bug

這一點與 Savior 的說法一致，因為有些漏洞的觸發需要控制流條件和數據條件同時滿足才能觸發，hyrbrid fuzzing 只能幫助到達代碼位置，而數據條件的滿足需要額外的操作。

Field-level constraint solving

所以本文提出了一種利用 field 信息，簡化求解和執行的方法。利用 taint 追蹤輸入在程序中的數據流信息，包括數據對應在輸入的 offset以及數據的 value。

以一個簡單的C代碼為例：

假設a來自于輸入的{0x0, 0x1, 0x2, 0x3}，b來自輸入的{0x4, 0x5, 0x6, 0x7}，最后需要對第5行的約束a+c == 0x12345678進行求解。

將這段代碼的匯編指令如下：

本文的方法則如下：

假設此時a=0x1111，b=0x2222，根據 taint，我們可以知道第1條mov 指令的操作數是b，值為0x2222，以及來自于輸入的 offset是 {0x4, 0x5, 0x6, 0x7}，這時候無需對第一條 mov 指令進行符號模擬，直接執行第2條指令add eax, 0x1

此時我們知道 eax 中是變量 b，直接構建約束b + 1，并且知道結果為 0x2223，中間的 mov 指令即便不進行符號模擬，直接到第6條指令add eax, edx，此時根據 value 和 offset，我們可以直接構建約束 (b+1)+a。

最后在 cmp 指令處，對約束 (b+1)+1 = 0x12345678進行求解即可。

由此可以看出，中間的 mov 指令不需要符號模擬，不影響最后的約束構建和求解。

在執行過程中，會將指令的 field 和 value 都記錄下來，針對同一個輸入，構建出 field transition tree，針對這棵樹來構建約束

為了求解效果最大化，根據樹的節點深度進行劃分，只有深度大于1的節點被認為是復雜約束，將 solver 僅用于復雜約束的求解。同時仿照 Savior 的做法，在一些算數指令上插入一些邊界檢查的約束，例如F+100 > INT_MAX、F-100 < 0等

Pangolin

本文解決的是 hybrid fuzzing 中，計算冗余的問題。

一條路徑可能會有多個分支，假設已經對該路徑的第一個分支進行了求解，需要對下一個分支進行探索，此時，第一個分支的解信息其實可以幫助我們縮小后續分支的搜索空間，降低后續分支的求解難度。

以圖為例，假設第3行的約束已經被求解，得到解空間為x=3, y=4, 0

將 fuzzing 過程中，對Z的變異從整個正整數空間縮小到(0, 200)
將 concolic execution 中，第4行分支的約束從z*z<40000 ^ z>195簡化為0195

本文的 key idea 就是保留和重用路徑上一個階段的解空間，本文稱為：多邊形路徑摘要 (polyhedral path abstraction)，這些路徑摘要是與目標路徑約束相關的輸入變量的邊界范圍。

首先需要推斷出路徑摘要，文章提出一種方法，可以將路徑約束簡化為一組線性不等式，這個不等式是近似但不完全等于路徑約束，是包含的關系，保證不等式的范圍完全覆蓋路徑約束的數據范圍。

然后引導 fuzzing 變異，保證變異的范圍在路徑摘要的范圍內，且滿足均勻分布。同時能夠加快求解的速度，主要是能快速驗證約束是否可解，因為簡化后的不等式組都是線性的，如果簡化后的不等式組都不可解，說明真正的路徑約束更加不可能求解，直接剪枝。

CAB-Fuzz

本文是對閉源 OS 進行的一個 concolic execution 工作，其實不能算是 hybrid fuzzing。CAB-Fuzz 的取名意為Context-Aware and Boundary-focused。其次值得一提的是，本文的作者中有 QSYM 的作者Insu Yun。

對閉源 OS 進行符號執行，常見的挑戰就是狀態爆炸問題，而且對于閉源的 OS，缺少文檔和配套的 test suites，很難構建一個合適 pre-context。

本文實際上是繞過了這兩個問題：

(1) 因為狀態太多，本文就集中于邊界的值上，文章觀察到，邊界值是最容易出問題的地方，特別是循環的邊界和數組的邊界，所以在循環時取0次、1次、最大次的值進行符號執行，數組的值取最低地址和最高地址的值進行符號執行。

(2)至于如何構建context，文章直接采用 real world program 執行，在執行后自然構建 context 以后，再進行 on-the-fly concolic execution，繞過了這個問題。

HFL

本文是對 Linux kernel 的一個 hybrid fuzzing 工具，面臨的 challenge 主要是以下幾點 kernel 特定的問題：

(1) 由 syscall 參數決定的間接控制流跳轉

(2) syscall 決定的系統內部狀態

(3) syscall 調用時需要推斷嵌套參數類型

現有的 hybrid fuzzing 要么是沒有解決這些問題，要么是用靜態分析不準確的部分解決這些問題。

本文針對以上問題的解決方法如下：

(1) 在編譯時將原有的間接控制流跳轉轉為直接的跳轉，例如圖

(2) 對 syscall 的調用順序進行推斷，首先進行靜態的指針分析，收集所有對相同地址進行讀寫的指令對，作為 candidate pair，然后在運行時對 candidate pair 進行進一步驗證，符號執行時是否確實是對相同地址的讀寫。最后對這些指令操作的數據進行追蹤，相關的函數就是存在調用順序依賴的關系。

(3) 最后是識別嵌套的參數類型，具體是先對一些 transfer 函數進行監控，通過內存位置和內存 buffer 的長度來進行判斷嵌套的參數類型。

參考文獻

[1] Driller: Augmenting Fuzzing Through Selective Symbolic Execution

[2] QSYM: A Practical Concolic Execution Engine Tailored for Hybrid Fuzzing

[3] Send Hardest Problems My Way: Probabilistic Path Prioritization for Hybrid Fuzzing

[4] SAVIOR: Towards Bug-Driven Hybrid Testing

[5] MEUZZ: Smart Seed Scheduling for Hybrid Fuzzing

[6] Intriguer: Field-Level Constraint Solving for Hybrid Fuzzing

[7] Pangolin: Incremental Hybrid Fuzzing with Polyhedral Path Abstraction

[8] CAB-FUZZ: Practical Concolic Testing Techniques for COTS Operating Systems

[9] HFL: Hybrid Fuzzing on the Linux Kernel

簡介

背景