Remarks
Conference: NDSS 2020
Full Paper: HFL: Hybrid Fuzzing on the Linux Kernel
Summary
- 針對的問題： Linux 操作系統內核安全漏洞的發現需要新技術。
- 現有解決方案的不足：當前的模糊測試技術難以直接應用于內核安全漏洞發現。
- 提出的創新方案概述：解決內核安全漏洞發現過程中的三大挑戰：1） 具有由系統調用參數確定的間接控制傳輸，2）通過系統調用控制和匹配內部系統狀態，3）推斷用于調用系統調用的嵌套參數類型。提出一種基于混合模糊測試技術的內核安全漏洞發現技術。
- 達到的效果：在最新的 Linux 內核中 ，發現 24 個新型安全漏洞， 漏洞發現速率提高 3 倍以上。代碼覆蓋率比Moonshine提升15%，比Syzkaller提升26%。
Introduction
Linux其內核龐大導致存在很多未知的漏洞， 而這些內核安全漏洞影響巨大，迫切需要創新的技術提升當前的漏洞發現率 。本文創新發展的混合模糊測試技術，一直是近年來漏洞發現領域的研究熱點，技術價值正在逐步展現，值得漏洞挖掘相關研究人員跟蹤、掌握該技術，用于現有研究工作中。
本文的主要貢獻有：
- 第一個可以應用于內核測試的混合模糊測試工具。
- 解決內核安全漏洞發現過程中的三大挑戰：1） 具有由系統調用參數確定的間接控制傳輸，2）通過系統調用控制和匹配內部系統狀態，3）推斷用于調用系統調用的嵌套參數類型。提出一種基于混合模糊測試技術的內核安全漏洞發現技術。
- 在最近的 Linux 內核中 ，發現 24 個新型安全漏洞， 漏洞發現速率提高 3 倍以上。代碼覆蓋率比Moonshine提升15%，比Syzkaller提升26%。
Motivation
混合模糊測試結合了模糊測試和符號執行的優點，避免了各自一定的缺陷，是挖掘二進制漏洞的有力工具。但是在Linux內核的測試上，不論是單獨地模糊測試，單獨地符號執行，或者是混合模糊測試，都無法取得很好的結果，這是由于Linux內核的機制，比常規的軟件有很多特殊的地方。本文總結了三個特定于內核的挑戰。
- 挑戰一：為了支持大量的設備，Linux內核中大多數組件都和抽象接口實現層解耦合，一般來講，接口層用于訪問特定功能的實現，這方面與對象編程相似。Linux內核代碼中有運行時多態性和編譯時多態性，借用C++中的多態概念來分析，運行時多態是指程序運行時才可確定的多態性，主要通過繼承和虛函數獲得。Linux構建一個函數指針表（抽象接口），其中包含一系列指向具體實現的函數指針，在運行時候，執行某種操作，從函數指針表抓取某個指針，由當時具體的對象類型決定，在編譯階段不能確定系統調用哪個函數，也被稱為滯后聯編（或動態綁定），典型的例子就是虛擬文件系統。編譯時多態性，主要通過重載機制獲得。可在執行前，通過靜態分析提升測試效果。但是運行時多態性之前沒有有效的辦法解決。Fuzzer無法用輸入的索引值來獲取函數指針表中的指針。符號執行也不能解決。
- 挑戰二：利用fuzzing技術測試內核操作系統，一般都是以系統調用作為輸入，因為系統調用是用戶態和內核態交互的關鍵。并且內核的系統調用是上下文依賴的，需要在特定的內部狀態下。而不考慮上下文依賴的系統調用往往會直接被拒絕，無法進入下一步測試。對于符號執行技術，由于內核的系統狀態需要很多數據變量維持，符號執行容易遭遇狀態爆炸問題。
- 挑戰三：Linux內核中大量的系統調用的參數都是嵌入式結構，比如某個參數字段的內容指向另外一個結構，這樣的嵌入式結構的系統調用的各個參數的語義很難猜測，因此輸入很難構造，更難以把輸入模板化。
當前的一些內核模糊測試技術并沒有很好的解決上述的問題。如下圖所示。IMF使用系統調用跟蹤來分析系統調用順序，以期望解決上述挑戰二。MoonShine通過靜態分析來推斷系統調用依賴。DIFUZE通過靜態分析來推斷完整系統調用參數的類型。這些靜態分析的方法無法準確的推斷處結果，因為某些參數是須在運行時才能確定的。
Approach
總體來講，HFL的設計遵循了用戶級混合模糊測試技術的設計，將傳統的模糊和符號執行結合起來。HFL的總體運行流程如下圖所示。HFL的特征有Kernel Syscall Fuzzing，Coverage Guided Fuzzing，Symbolic Analyzer。前面兩個特征在內核模糊測試中很常見，就不贅述了。對于Symbolic Analyzer，傳統的混合模糊測試中，如何判定fuzzing遇到hard constraint，再切換到symbolic execution，一直是一個難點。在HFL中，其fuzzer通過維護一個頻度計數表在測試期間統計用戶程序（一系列的系統調用）執行時，條件判斷語句的true or false頻度，以此來判定程序是否被“卡住”。對于一個用戶程序執行過程中，越是先出現的分支判斷低頻度越要重視，因為他的非條件可能會觸發更多的代碼覆蓋。
針對內核的模糊測試，本文提出了以下解決方法：
- 將間接控制轉化為直接控制-轉換原始內核。
- 推斷系統調用序列，建立一致的系統狀態-縮小變量符號化的范圍。
- 確定系統調用時的嵌套參數類型-在運行時檢索嵌套的系統調用參數。
下面具體講HFL如何解決Motivation中提到的三個挑戰：
- 把指針的間接控制流轉換成直接控制流，HFL提出了一個基于內核源代碼操作的offline translator。在保證條件分支語義的同時，將間接的控制流轉換為直接的控制流，這樣內核底層的調用代碼塊都可以直接被訪問，而不需要在執行時才確定虛函數具體由哪個函數實現。具體做法是：在編譯的時候，遍歷所有的指令，對于間接控制流，執行以下步驟：(1)離線轉換器確保函數指針表的索引變量來源于系統調用的參數，即是由系統調用的參數決定某個功能的實現這種情況，不是這種情況的索引變量對fuzzer執行并無影響。HFL通過執行過程間數據流分析來跟蹤系統調用的參數是如何傳播，以確定是否需要轉換。(2)確定索引的值以后，結合給定的函數表，HFL對每個索引值進行分支變換（類似指令編譯優化的循環展開），通過插入一個條件轉移到相應的函數指針上。至此，控制流便由間接轉為直接，方便fuzzer測試。
- 為了推斷處合適的系統調用順序和系統調用依賴，HFL首先在內核上進行靜態分析，獲取可能存在依賴的系統調用組，然后再驗證這些潛在的依賴組以篩選出真正的依賴關系。HFL對目標內核進行指針分析（pointer-analysis），收集一對讀/寫操作，即其中一條指令執行讀指令，另一條指令執行寫指令，兩條指令都是從相同的內存位置讀取和寫入，這樣的讀/寫操作就被稱為候選依賴對。但是pointer analysis存在誤報問題，因此在執行內核時，符號化地執行這些潛在依賴項對時，HFL檢查他們是否訪問相同的地址，這樣就能確定是否存在正在的依賴，然后就能確定合適的系統調用順序。與以往的內核測試不一樣的是：HFL除了確定系統調用順序外，還使用符號約束信息（來自系統調用參數的符號化）來保證那些系統調用參數之間的依賴。HFL的fuzzer和symbolic analyzer之間聯系緊密，執行過程中，交互密切，相輔相成，直接測試結束。
- HFL使用concolic executor和內核特有知識來檢索復雜的嵌套參數結構。在嵌套結構中，(1)連接到嵌套輸入結構的內存位置和(2)內存緩沖區參數的長度，這兩個參數是系統調用構建的關鍵。HFL在concolic執行時不斷監視傳遞函數的調用，一旦被調用，就檢查傳遞函數的源緩沖區是否收到了符號污染，這樣就能確定來自我們感興趣的系統調用的傳遞函數，然后就能確認參數指向的緩沖區，HFL使用符號狀態來跟蹤某個位置的偏移值，最后就能確定內存位置。同時，也可以通過跟蹤傳遞函數的參數值來獲得緩沖區的長度。
Reflection
- 本文提出的解決方法，對于非內核的二進制程序測試也有幫助，比如大量用c++虛函數實現的多態和繼承的二進制程序，比如本身帶有大量嵌套結構的二進制程序等，都可以借鑒HFL的方法精神。
- 按理來說，先解決前面的分支問題較為重要，但是如QYSM所講，會出現過度約束問題（導致前面的約束條件滿足了，后面的條件約束無法滿足，反而會降低代碼覆蓋率。當后面的函數路徑并不依賴前面的分支時，即為過度約束），下面這個例子出自QYSM論文。解決過度約束這個問題的辦法就是部分求解約束，即從最后一個條件開始，倒推著求解約束。因此這是一個需要權衡的問題。
