基于系統調用依賴的Linux內核模糊測試技術研究

◆楊 鑫 張 超 李 賀 單 征

（1.數學工程與先進計算國家重點實驗室 河南 450002）

（2.清華大學 網絡科學與網絡空間研究院 北京 100083）

Linux操作系統被應用在絕大部分服務器和包括Android在內的許多場景中，支撐著互聯網關鍵基礎設施的運轉和信息技術產業的發展，占據了大量的操作系統市場份額。而操作系統的核心是內核，提供了操作系統最基本的功能和安全保障。如果在內核中發生安全問題，將給整個操作系統的穩定和安全帶來巨大的威脅。因此，對內核進行安全測試，提前發現未知安全問題，意義極其重大。目前，模糊測試是發掘內核缺陷的主要手段，即通過向內核提供的接口發送大量精心構造的輸入，然后觀測內核是否異常來發現內核的問題。一般來說，內核模糊測試的主要接口是系統調用，因為它是用戶態程序與操作系統內核交互的主要接口。而且，系統調用實現中的問題可能導致非特權的普通用戶態程序危害整個操作系統[1]。

系統調用接口模糊測試工具的輸入通常為多個系統調用組成的系統調用序列，構造系統調用序列的效率和質量是制約模糊測試效果的關鍵。Linux內核目前提供了300多個系統調用，如果隨機組合這些系統調用構成測試輸入，其輸入空間無比巨大。而且，系統調用之間存在著依賴關系，系統調用之間順序并不能隨意組合。部分系統調用的行為依賴于之前一些系統調用創建的共享內核狀態，如果沒有正確的內核狀態，后續的系統調用只能觸發淺層的錯誤處理代碼，而不能執行到深層的核心功能代碼[1]，測試效率將非常低下。

為此，現有的系統調用接口模糊測試工具[2][3]依靠人工不斷編寫了大量的規則，描述了基于資源參數類型的依賴關系，即使用特定資源作為參數的系統調用前，必須存在產生該資源的系統調用，這些資源包括各種類型的文件描述符等。例如，對于read系統調用，其第一個參數為文件描述符資源類型，那么為了使read系統調用能夠執行到核心功能代碼，就必須確保該文件描述符處于“open”狀態，即需要在read系統調用前使用open系統調用來達到該要求。

然而，系統調用之間的依賴不僅僅表現在使用資源作為參數的系統調用與生成資源的系統調用間，內核中還存在著一些對于同一進程共享的數據，對這些共享內核數據進行更改的系統調用，也會影響到其他使用這些內核數據的系統調用的執行。并且，這些內核數據通常并不直接體現到系統調用的參數或返回值上，很難直接通過系統調用的參數和返回值類型來分析得出。

為此，本文通過設計和實現Dependkaller，以自動提取系統調用間基于共享內核數據的依賴，并有效融合多種依賴關系，為系統調用序列的生成和變異提供高效指導。Dependkaller首先通過靜態分析Linux內核各個系統調用的代碼，提取出基于共享內核數據的依賴，并分配相應權重。然后，將內核數據依賴與現有的資源數據依賴進行融合，形成系統調用間的靜態依賴權重，并用該權重指導隨機生成和變異系統調用序列，對內核進行測試。然后，結合測試過程中收集的內核代碼覆蓋信息反饋，統計分析實際產生新的代碼覆蓋的系統調用序列，從而提取系統調用間的動態依賴權重。最后，利用動態依賴權重，不斷修正靜態分析得到的依賴權重，提升依賴權重的合理性，不斷提高系統調用序列生成和變異的效率。實驗結果表明，Dependkaller比MoonShine的靜態分析更全面，比syzkaller對內核代碼模糊測試的代碼覆蓋率提升16.89%，多發現了51.22%（即21個）漏洞。

總體上，本文系統地研究了基于系統調用依賴的Linux內核模糊測試技術，主要貢獻如下：

（1）通過對內核系統調用接口模糊測試技術的研究，揭示了目前方案在系統調用依賴分析和運用上存在的不足，即靜態依賴分析存在漏報和誤報，而且測試過程中對依賴信息的運用上存在擴展性差和延續性弱的問題。

（2）提出了基于共享內核數據的新型的系統調用間依賴關系；并通過細致分析內核中大量存在的間接函數調用信息，提高數據流分析的精度，提取了系統調用間基于共享內核數據的依賴信息，降低了依賴信息的漏報。

（3）利用了分析得到的基于共享內核數據的依賴信息，有效融合現有的資源數據依賴信息和根據代碼覆蓋反饋信息提取的動態依賴信息，為系統調用序列的生成和變異提供高效指導，提高了對內核系統調用接口模糊測試的代碼覆蓋率和bug發現數量，具有良好的應用價值和效果。

本文剩下的部分組織如下：第1節主要對Linux內核系統調用接口模糊測試技術進行介紹，分析存在的挑戰、目前的研究現狀和存在的問題；第2節介紹本文提出的基于系統調用依賴的Linux內核模糊測試技術的設計和實現；第3節進行了實驗驗證；最后，在第4節進行了總結。

1 內核系統調用接口模糊測試技術研究現狀和分析

針對內核系統調用接口的模糊測試，其測試輸入為系統調用序列。模糊測試器通過生成或變異的方式產生系統調用序列，然后在目標操作系統上執行，來調用內核功能，以期最大化代碼覆蓋率，發現盡可能多的程序缺陷。

測試輸入構造的效率是模糊測試效果的關鍵環節。根據文獻[4]，系統調用接口模糊測試輸入構造技術大致可以分為基于隨機、基于參數類型、基于hook（鉤子）和基于反饋四類。基于隨機的技術最為簡單，可以追溯到1991年，當時Tin Le研發了tsys fuzzer[5]，它簡單地循環使用隨機生成的參數調用隨機選擇的UNIX System V系統調用，直到系統崩潰。基于參數類型的模糊測試技術，如Dave Jones研發的Trinity[2]通過為參數添加一些隨機性來生成測試用例。而基于hook的模糊測試技術試圖通過在運行程序時攔截系統調用，改變正在執行的系統調用的合法參數值來對系統調用進行模糊測試，獲取更高的測試正確率，這一類主要有文獻[6，7]。基于反饋的技術首先出現在目前最成熟的Linux內核模糊測試框架syzkaller[3]上，它將測試例的代碼覆蓋率用于反饋，基于遺傳算法來保留能夠貢獻新的代碼覆蓋率的測試例并變異、生成新的測試例，對提高代碼覆蓋率具有顯著效果，挖掘了Linux內核大量漏洞。可見，傳統的系統調用接口模糊測試技術主要關注于提高構造系統調用參數的效率上。

然而，系統調用之間也存在著一些影響。系統調用要實際執行內核功能，通常需要一些預先存在的內核狀態，否則不能通過狀態檢查，只能執行淺層的錯誤處理代碼。這些內核狀態只能被其他系統調用按照特定順序進行設置，系統調用必須按照特定順序執行，系統調用之間的參數等資源存在依賴，這些統稱為系統調用依賴。

根據文獻[1]，內核狀態主要體現在兩個方面。一是用戶態可見的資源數據（如各種類型的文件描述符等），它是通過一些系統調用以返回值的方式產生，而另一些系統調用依賴它作為參數，才能正常執行。比如系統調用read和write必須使用open正確執行返回的文件描述符作為第一個參數，才能正常執行。我們稱這種依賴為資源數據依賴；二是用戶態不可見的共享內核數據，它是通過共享的內核數據傳遞，一些系統調用會修改一些共享內核數據，而另一些系統調用的執行會受這些共享內核數據的影響，我們稱這種依賴為內核數據依賴。舉例來說，Linux系統調用msync內核數據依賴于系統調用mlockall，因為mlockall通過修改共享內核數據struct vma的vm_flags域，而統一進程中的msync會根據vma.vm_flags的值，執行不同的程序路徑，即影響了msync的控制流。

為了高效地生成系統調用序列，syzkaller依靠專家經驗編寫大量系統調用的描述規則，規定了各個系統調用的參數和返回值信息，包括類型、值范圍、傳遞方向等。其中比較重要的是設定了一些特殊的參數類型，即資源類型，它們主要由一些系統作為返回值生成，可供其他一些系統調用使用。在系統調用生成時，如果某個系統調用需要某種類型資源作為參數，syzkaller從之前已產生的相同類型資源返回值中選擇一個作為參數（大概率）；或者直接在該系統調用前插入一個生成該類型資源的系統調用（小概率，或之前未產生過所需的資源），然后將返回值作為該系統調用的參數。同時，在生成下一個系統調用時，會優先選擇具有更多相同資源參數的系統調用。為此，syzkaller會先分析所有被測系統調用的參數類型，如果兩個系統調用都接收相同的資源類型作為參數，則給這兩個系統調用賦予更高的相關性，即在有其中一條系統調用存在的情況下，下一條系統調用被選擇的權重。syzkaller這樣的生成和變異系統調用序列的方式，基本確保了系統調用序列符合資源數據依賴，且具有較強的資源相關性。然而，對于共享內核數據依賴，該方案沒有進行考慮和應用。

MoonShine[1]首次提出了基于共享內核數據的隱含依賴概念，但它是用Smatch[8]分析Linux內核源碼的抽象語法樹進行提取的，只得到系統調用間是否存在依賴的信息，未考慮內核中大量存在的函數指針，存在較多漏報，并且存在靜態分析固有的誤報問題。而且，它只是基于真實用戶態程序動態執行產生的系統調用trace（執行記錄），提取包含資源數據依賴和內核數據依賴的系統調用序列，存在一些局限：（1）依賴于trace多樣性，一般的trace包含的系統調用種類和組合有限，較難擴展提升覆蓋率；（2）trace一般比較正常，需要基于依賴信息大量變異，但MoonShine沒有進行有效指導，后續生成和變異系統調用序列的效率依然很低。

綜合分析當前內核系統調用接口模糊測試技術，發現當前對構造有效系統調用接口測試輸入的要求上已有較全面的認識，但對系統調用間依賴的分析手段和有效運用還存在一些不足。主要為：（1）靜態分析內核數據依賴的漏報和誤報問題；（2）測試中對系統調用依賴運用存在的擴展性差和延續性弱的問題。

2 基于系統調用依賴的Linux內核模糊測試技術設計和實現

為了解決目前存在的不足，我們設計和實現了Dependkaller。首先，通過盡可能全面的靜態分析，獲取低漏報的內核數據依賴信息，并分配相應權重。然后，融合內核數據依賴權重和資源數據依賴權重生成靜態依賴權重，指導帶權重地隨機生成和變異初始的系統調用序列。為了減少人工和靜態分析提取的靜態依賴權重的漏報和誤報，我們在充分基于靜態依賴權重生成和變異系統調用序列并執行后，根據內核代碼覆蓋信息記錄工具KCOV[9]的反饋，分析覆蓋了新的內核代碼的系統調用序列，形成動態的系統調用依賴權重。最后，融合靜態依賴權重和動態依賴權重，共同指導后續的系統調用序列生成和變異。

圖1 Dependkaller架構圖

2.1 靜態分析內核數據依賴信息

根據文獻[1]對內核數據依賴（隱含依賴）的定義：前面系統調用的執行會修改共享內核數據，從而影響后面與該共享內核數據有關的系統調用的執行。更具體的定義：如果系統調用A在條件語句中使用了共享內核數據v，則v是A的讀依賴項；如果系統調用B會對共享內核數據v進行寫入，則v是B的寫依賴項；如果A的寫依賴項與B的讀依賴項存在相同的共享內核數據，則A對該共享內核數據的寫入，會影響B的條件判斷，即影響B的控制流，則稱系統調用B內核數據依賴于系統調用A。

為了使靜態分析盡可能減少漏報，針對內核代碼的特點，我們主要采用了細致的數據流分析和全面的函數指針分析。針對寫依賴的共享內核數據，只需分析系統調用會寫入的共享內核數據。針對讀依賴的共享內核數據，需分析系統調用會讀入的共享內核數據，且通過數據流分析，讀入的值還會影響條件語句的值。因為系統調用由一系列內核函數進行實現，系統調用對于共享內核數據的依賴也主要體現在內核函數的實現代碼中。因此，需要先基于函數調用信息分析系統調用相關的內核函數，然后分析這些內核函數對共享內核數據的依賴，最后得到各個系統調用對共享內核數據的依賴。

Dependkaller的靜態分析實現主要基于LLVM編譯器框架。首先使用LLVM中的Clang編譯器編譯Linux內核源碼為IR（Intermediate Representation，中間表示），然后編寫LLVM靜態分析程序，對IR進行分析，提取內核數據依賴信息。因為Linux內核源碼編譯生成為多個IR文件，每個IR文件對應于內核的單個源碼文件，且每個IR源碼中包含了內核函數的具體實現。因此，總體分析步驟為：（1）逐個分析內核源碼IR，提取函數調用信息和內核函數對共享內核數據的依賴信息；（2）根據函數調用信息提取系統調用實現相關的內核函數，分析得到系統調用對共享內核數據的依賴信息。具體實現如下。

2.1.1 分析內核函數對共享內核數據的依賴信息

因為Linux內核中主要使用復雜數據類型結構體（struct）來組織共享數據，用結構體中簡單數據類型域（field）來存儲共享數據。因此，本文主要分析基于結構體中域（struct.field）數據的依賴信息，并以struct的類型名和field的變量名作為依賴項的標識。算法流程如圖2所示，對于一個內核函數的IR，若其中存在Store指令的目標操作數為struct.field類型，則該struct.filed為該內核函數的一個寫依賴項（第3-6行）；若其中存在Load指令的源操作數為struct.filed類型，且該Load指令的目的操作數會影響Branch指令（對應于C語言的if、while、for等語句）或Switch指令（對應于C語言的switch語句）的操作數，則該struct.filed為該內核函數的一個讀依賴項（第8-12行）。因為Load指令的目的操作數只需影響Branch指令或Switch指令的操作數，可以直接也可以間接影響，所以需要對Load指令的目的操作數進行數據流分析，看是否有流入Branch指令或Switch指令的操作數。在基于LLVM實現時，需要以源操作數為struct.filed類型的Load指令的目的操作數為起點Value，遞歸地分析其User（LLVM IR中，一個Value的User是將該Value作為操作數的指令或表達式），如果存在某個User為Branch指令或Switch指令，則該struct.filed為該函數的讀依賴項。

圖2 算法流程

2.1.2 分析系統調用對共享內核數據的依賴信息

通過2.1.1，我們得到了各個內核函數對共享內核數據的依賴信息。然而，我們需要的是系統調用對共享內核數據的依賴信息，可通過分析提取各個系統調用實現相關的內核函數，然后將相關內核函數對內核數據的依賴信息整合到對應的系統調用中即可。為了提取各個系統調用實現相關的內核函數，需要分析內核中的函數調用關系。因為內核中存在大量的通過函數指針進行的間接函數調用，而LLVM內置的函數調用分析程序不支持分析間接函數調用，為了減少分析漏報造成依賴信息的缺失，我們采用基于類型分析[10]的方法來保守地找出所有的間接函數調用。具體為：首先收集所有被取地址的函數（即函數指針的目標函數），只要其參數類型和和數量與間接調用函數的相同，則認為這個被取地址的函數是被間接調用的目標，從而構建兩者的調用關系。通過這樣，可以獲取整個內核的函數調用信息，然后以各個系統調用為起始節點，逐層分析被調函數，可得到系統調用實現相關的內核函數。然后，將相關內核函數對共享內核數據的依賴信息整合到對應的系統調用即得到系統調用對內核數據的讀寫依賴信息。最后，交叉對比各個系統調用的讀、寫依賴的struct.field，如果系統調用A寫依賴的struct.field與系統調用B讀依賴的struct.field相同，則系統調用B依賴于A，而相應的struct.field則為系統調用A和B的依賴項。最終可得到各個系統調用之間依賴的所有struct.field。

2.2 融合生成靜態依賴權重，指導初步模糊測試

為了充分利用分析所得的系統調用知識，深入持續指導模糊測試進程，我們將分析得到的系統調用對共享內核數據的依賴信息轉化為系統調用選擇的權重，即存在某條系統調用的前提下，下一條系統調用被選擇的權重，權重值為系統調用之間依賴的struct.field數量的歸一化值。并與syzkaller提供的資源依賴權重（同樣地歸一化后）相加，得到系統調用狀態轉移的靜態權重。最后，基于該靜態權重，影響模糊測試生成和變異系統調用序列時，選擇下一條系統調用的權重，從而在生成和變異系統調用序列時高效地反映系統調用的資源和內核數據依賴。

2.3 融入動態依賴權重，指導后續模糊測試

由于人工分析的資源數據依賴和靜態分析得到的內核數據依賴存在漏報和誤報的可能，單純依靠靜態依賴權重指導模糊測試還存在效率上的提升空間。為此，先充分利用靜態權重指導生成和變異形成大量系統調用序列，經內核執行后，根據KCOV反饋的內核代碼覆蓋信息，分析能覆蓋新的內核代碼的系統調用序列，得到當前實際的系統調用組合情況。因為系統調用依賴主要表現為前面系統調用對后面系統調用的影響，所以通過統計分析前后系統調用對的頻次，即可得到當前的動態依賴權重。動態依賴權重反映了實際存在依賴的系統調用對，可用于修正靜態依賴權重存在的漏報、誤報或權重值的偏差。具體方法是將動態依賴權重（同樣地歸一化后）與靜態依賴權重相加，得到實際依賴權重，指導后續生成和變異系統調用序列。隨著越來越多系統調用的產生，動態依賴權重將越來越準確，實際依賴權重也將越來越準確，指導模糊測試的效率也將會越來越高。

3 實驗

Dependkaller主要代碼實現包括兩個部分，第一部分為基于LLVM的靜態分析模塊，實現對Linux內核源碼中系統調用內核數據依賴信息的提取；第二部分為基于Syzkaller的內核模糊測試模塊，實現對目標內核的模糊測試。為了驗證Dependkaller的效果，本部分主要回答兩個問題：（1）Dependkaller分析的內核數據依賴信息是否更全面？（2）Dependkaller能否提高代碼覆蓋率和bug發現數量？

3.1 Dependkaller分析的內核數據依賴信息是否更全面

3.1.1 實驗方法

實驗對象為MoonShine分析所采用的Linux 4.19內核。主要將Dependkaller對Linux內核靜態分析提取的內核數據依賴信息，與MoonShine通過Smatch獲取的內核數據依賴信息[1]進行對比。

3.1.2 實驗結果

Linux 4.19內核包含的系統調用數目為366個。而Dependkaller和MoonShine對Linux 4.19內核靜態分析提取的依賴組數（會影響其他系統調用數據流和控制流的系統調用數量）分別為294和228組，Dependkaller比MoonShine多找出64組（28%）存在內核數據依賴的系統調用，如表1。

表1 靜態分析結果對比

3.1.3 結果分析

通過實驗結果可以看出，Dependkaller提取的系統調用間內核數據依賴信息更全面。

3.2 Dependkaller能否提高代碼覆蓋率和bug發現數量

3.2.1 實驗環境

實驗環境操作系統為Ubuntu Server 16.04，配置有384GB內存，72個Intel CPU，可滿足實驗對內存和CPU的需求。

3.2.2 實驗方法

為了評估Dependkaller的設計方案對代碼覆蓋率的影響，我們分別實現了只加入靜態依賴權重的Dependkaller（以下簡稱Statickaller），以及在后期（語料庫達到2萬時）融入了動態依賴權重的Dependkaller，并與原始的syzkaller進行對比測試。均提供空的語料庫，對所有系統調用進行測試，不開啟崩潰復現功能。為了盡可能消除實驗的隨機性和資源不足的影響，每個實驗組配置8個QEMU虛擬機，每個虛擬機配置4GB，運行4個模糊測試器進程，同時生成、變異和執行系統調用序列。測試目標為當前最新的Linux 5.20內核。測試直到三組實驗程序的代碼覆蓋率均無明顯提升為止。

3.2.3 實驗結果

因為內核代碼空間巨大，模糊測試隨機性較大，實驗持續了10天，三組實驗程序的內核代碼覆蓋率才沒有較明顯增長。因為在記錄代碼覆蓋信息時，采用基本塊邊覆蓋數較為可行且準確，所以記錄了最終syzkaller、Statickaller和Dependkaller的基本塊邊覆蓋數量，以及Statickaller和Dependkaller相對syzkaller的增長率。同時，記錄造成crash的bug類型數量。如表2。

表2 模糊測試結果對比

3.2.4 結果分析

通過實驗結果可以看出，在充分進行模糊測試后，融入了內核數據依賴指導的Statickaller比syzkaller在基本塊邊覆蓋方面，有了11.43%的增長，多發現34.15%的bug。而同時融入了動態依賴的Dependkaller，又有了4.89%的增長，最終獲得16.89%的代碼覆蓋率增長和51.22%（21個）的bug數量增長。可以看出，先基于靜態依賴進行充分測試，后融入動態依賴提升測試效率的方案具有一定效果。

4 結論

本文研究發現了Linux內核系統調用接口模糊測試技術在系統調用依賴的分析和運用上存在的不足，設計和實現了基于系統調用依賴的Linux內核模糊測試工具Dependkaller，通過較全面的動靜結合方式分析和運用依賴信息，持續高效生成和變異系統調用序列，Dependkaller的靜態依賴分析結果更為全面，對Linux內核的模糊測試比syzkaller在代碼覆蓋率方面提升了16.89%，多發現51.22%（21個）的bug。結果表明Dependkaller對于提高Linux內核系統調用接口模糊測試具有一定的應用價值。