前置知識#
Fuzzing 的方法是通過大量生成 input，來找出被測程序的錯誤的方法。
Fuzzing 的關鍵點之一在於 input 生成方法，其二在於 input 的排序方法，其三在於軟體內部資訊的獲取和應用。
如果 input 完全是自己構建的，那麼這種方法稱之為 generational fuzzing
如果 input 是通過原始種子略微修改後得到的，那麼這種 fuzzing 為 Mutational fuzzing。
如果 Mutator 可以經過一定的程式資訊的引導，那麼這叫做 GrayBox Fuzzing，比如覆蓋率引導的模糊測試
如果 Seed 經過 Power Schedule 的精力分配，隨後 Mutator 根據 Seed 的精力大小排序，那麼這種方法稱之為 Boosted GrayBox Fuzzing
grey-box fuzzing 是什麼#
白盒是很大程度上利用了源碼進行約束求解、程式分析等操作
黑盒是一點源碼的資訊都沒有獲取
而灰盒是局部獲取了程式的資訊，常見的就是獲取程式的執行覆蓋率，最常見的手段是二進制插桩（編譯時在每個跳轉分支後面插入自定義的記錄程式碼）。比如 AFL 就是灰盒 fuzzer。
DGF（directed grey-box fuzzing）是什麼#
為什麼會有 DGF#
大多數的灰盒模糊測試都是使用種子的覆蓋率進行引導的，在有限的時間內覆蓋盡可能多的路徑。這麼做的主要原因是因為程式的覆蓋率和 bug 的覆蓋率是呈正相關的，當一個模糊測試工具能夠覆蓋更多的程式碼的時候往往能找到更多的 bug。
但是，並不能將程式中所有的程式碼同等或者說等權重的對待，因為模糊測試工具覆蓋的絕大多數程式碼都是不包含 bug 的。而且在實際的應用過程中，想要覆蓋完整的程式碼分佈，是十分困難的或者說是完全不可能的。
為了克服這種問題，就提出了導向型模糊測試。
和傳統的灰盒 fuzzing 有什麼區別#
和傳統的灰盒模糊測試相比：
1. 目標不同：傳統的灰盒模糊測試為了提高程式碼覆蓋率，而 DGF 更傾向於測試指定程式塊的 bug
2. 技術不同：DGF 一般需要數據流和控制流圖來計算種子和目標程式段的距離
DGF 最終要解決的問題#
利用種子和目標 target 之間的距離，作為適應度函數來幫助種子進行選擇。
將距離目標位置更近的種子，更多的變異機會，來引導灰盒模糊測試到達目標位置。
整個導向型灰盒模糊測試將之前的可達性問題轉換成了一個優化問題。
也就是優化生成的種子和目標位置之間的距離。
在了解導向型灰盒模糊測試的整個過程之後，能夠發現，整個問題的關鍵就是如何定義種子和目標位置之間的距離，來進行優化。
Background#
DGF 當前主要基於兩個關鍵機制：
1.DGF 可以支持由無向灰盒 fuzzing 中的覆蓋率引導來進化測試用例
2.DGF 通過 CFG（控制流圖）中的執行節點和目標節點的距離來衡量每個測試用例的優先級，並排序，從而為 fuzzer 提供到達目標程式點的指導
當前有兩個 DFG 的擴展性問題：
1. 傳統的覆蓋反饋不總是能提供找到目標程式點（可以說是存在 crash 的程式段）的有意義的指導
2. 當程式具有複雜的控制結構時，現存的種子距離算法表現不佳
關於覆蓋率引導，有時候會因為程式龐大，導致覆蓋率引導的方向和目標程式點背離，Beacon 最先嘗試解決該問題，並使用一個最弱先決條件來判斷是否會到達目標程式點，但是這個方法在程式有複雜循環時不起效
當程式較大時，執行節點鏈的長度會很長，會包含很多和目標程式點語義不相關的節點，WindRanger 是第一個使用偏差基本塊（DBBs）來解決偏差問題，但是在循環結構中不是一個好的形式
Motivation#
簡單來看就是一段 C 語言的數組越界錯誤，用戶可以輸入任意大小的整數作為索引，而一個易受攻擊的函數沒有驗證輸入的索引
到達這個易受攻擊的函數的路徑只有一條，但是從 main 出發經過這條路徑的同時，中途會有很多分岔路徑，會大大分散測試用例的能量分配，導致誤導
同時對比 AFLGo 的種子距離計算和 WindRanger 的種子距離計算，得出的結果相同，即當涉及複雜的環路結構時，基於 DBB 的距離度量同樣會誤導
Solution#
Selective coverage instrumentation#
為了到達程式 P 的指定程式點 t，在 t 處 backward 地構造了 Def-Use Graph，來收集所有依賴語句，並使用 Thin Slicing
關於 Thin Slicing：將指標解引用了（去除指標帶來的多餘變量），可以減小切片（理解為資料依賴的一個 backward 的資料流圖）的大小，從而為定向 fuzzing 提供更有效率的指導
為什麼要用 DUG 呢，因為 DUG 可以自動忽略掉很多不相關的節點，即留下來的只有有資料依賴關係的節點；同時，即使對應的 CFG 有循環，DUG 也不會有循環（只要沒有循環資料依賴性）
Semantic relevance scoring#
從目標節點到 DUG 上最遠的距離記為 1，其後所有節點到目標節點的最短距離每接近一個節點就加 1，這樣執行節點路徑的分數總和為語義相關分數
達到效果：種子執行了更多的節點，或更接近目標程式點的節點，則綜合分數更高（如 3c 圖所示）
Exp#
使用 AFL、AFLGo、Beacon、WindRanger、DAFL 五個 fuzzer，分別對 Beacon paper 中的 41 個漏洞進行了 fuzz，指標是 TTE（Time-to-Exposure），即 fuzz 一個漏洞 24 小時，得到第一個 crash 的耗時
但是不知道為什麼圖裡沒有 Beacon
結果是 DFL 最少也能平均比其他幾個 fuzzer 快 1.93 倍
之後還做了消融實驗：
Thin slicing 能夠使得平均快 2.01 倍
Selective coverage instrumentation 能夠使得平均快 1.73 倍（對比 AFL）
Semantic relevance scoring 能夠使得平均快 1.39 倍（對比 AFL）
這兩個 technique 合起來能夠達到 1.93 倍（對比 AFL）
Discussion#
討論了 DAFL 對於多目標的支持，即在執行節點鏈路上有多個目標程式點，取到他們的平均距離為相關分數
還討論了支持其他語言比如 C/C++、Go 等語言的問題
總結#
由於現有的 DGF distance 計算存在誤導的問題，用 DUG 取代 CFG，利用資料流資訊取代了控制流資訊，使得那些無關的節點不存在了，從而不會誤導 fuzzer 的定向
使用 thin slicing 剪枝，DUG 會變得更精簡，提高 fuzzer 效率
參考鏈接#
Fuzzing 技術總結（Brief Surveys on Fuzz Testing）
https://zhuanlan.zhihu.com/p/43432370
Directed Greybox Fuzzing 相關內容整理
https://zhuanlan.zhihu.com/p/415316061
Hawkeye：定向灰盒模糊測試技術
https://zhuanlan.zhihu.com/p/130767857
給你的模糊測試開開窍 —— 定向灰盒模糊測試（Directed Greybox Fuzzing）綜述
https://www.cnblogs.com/welkinchan/p/17685797.html
【學習筆記】Fuzzing 學習筆記 3—— 灰盒 Fuzzing
https://superlova.github.io/2020/08/20/%E3%80%90%E5%AD%B8%E4%B9%A0%E7%AC%94%E8%A8%98%E3%80%91Fuzzing%E5%AD%B8%E4%B9%A0%E7%AC%94%E8%A8%983%E2%80%94%E2%80%94%E7%81%B0%E7%9B%92Fuzzing