基于系統(tǒng)調(diào)用依賴的Linux內(nèi)核模糊測試技術(shù)研究

◆楊 鑫 張 超 李 賀 單 征

（1.數(shù)學(xué)工程與先進計算國家重點實驗室 河南 450002）

（2.清華大學(xué) 網(wǎng)絡(luò)科學(xué)與網(wǎng)絡(luò)空間研究院 北京 100083）

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

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

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

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

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

總體上，本文系統(tǒng)地研究了基于系統(tǒng)調(diào)用依賴的Linux內(nèi)核模糊測試技術(shù)，主要貢獻如下：

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

（2）提出了基于共享內(nèi)核數(shù)據(jù)的新型的系統(tǒng)調(diào)用間依賴關(guān)系；并通過細(xì)致分析內(nèi)核中大量存在的間接函數(shù)調(diào)用信息，提高數(shù)據(jù)流分析的精度，提取了系統(tǒng)調(diào)用間基于共享內(nèi)核數(shù)據(jù)的依賴信息，降低了依賴信息的漏報。

（3）利用了分析得到的基于共享內(nèi)核數(shù)據(jù)的依賴信息，有效融合現(xiàn)有的資源數(shù)據(jù)依賴信息和根據(jù)代碼覆蓋反饋信息提取的動態(tài)依賴信息，為系統(tǒng)調(diào)用序列的生成和變異提供高效指導(dǎo)，提高了對內(nèi)核系統(tǒng)調(diào)用接口模糊測試的代碼覆蓋率和bug發(fā)現(xiàn)數(shù)量，具有良好的應(yīng)用價值和效果。

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

1 內(nèi)核系統(tǒng)調(diào)用接口模糊測試技術(shù)研究現(xiàn)狀和分析

針對內(nèi)核系統(tǒng)調(diào)用接口的模糊測試，其測試輸入為系統(tǒng)調(diào)用序列。模糊測試器通過生成或變異的方式產(chǎn)生系統(tǒng)調(diào)用序列，然后在目標(biāo)操作系統(tǒng)上執(zhí)行，來調(diào)用內(nèi)核功能，以期最大化代碼覆蓋率，發(fā)現(xiàn)盡可能多的程序缺陷。

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

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

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

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

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

綜合分析當(dāng)前內(nèi)核系統(tǒng)調(diào)用接口模糊測試技術(shù)，發(fā)現(xiàn)當(dāng)前對構(gòu)造有效系統(tǒng)調(diào)用接口測試輸入的要求上已有較全面的認(rèn)識，但對系統(tǒng)調(diào)用間依賴的分析手段和有效運用還存在一些不足。主要為：（1）靜態(tài)分析內(nèi)核數(shù)據(jù)依賴的漏報和誤報問題；（2）測試中對系統(tǒng)調(diào)用依賴運用存在的擴展性差和延續(xù)性弱的問題。

2 基于系統(tǒng)調(diào)用依賴的Linux內(nèi)核模糊測試技術(shù)設(shè)計和實現(xiàn)

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

圖1 Dependkaller架構(gòu)圖

2.1 靜態(tài)分析內(nèi)核數(shù)據(jù)依賴信息

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

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

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

2.1.1 分析內(nèi)核函數(shù)對共享內(nèi)核數(shù)據(jù)的依賴信息

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

圖2 算法流程

2.1.2 分析系統(tǒng)調(diào)用對共享內(nèi)核數(shù)據(jù)的依賴信息

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

2.2 融合生成靜態(tài)依賴權(quán)重，指導(dǎo)初步模糊測試

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

2.3 融入動態(tài)依賴權(quán)重，指導(dǎo)后續(xù)模糊測試

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

3 實驗

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

3.1 Dependkaller分析的內(nèi)核數(shù)據(jù)依賴信息是否更全面

3.1.1 實驗方法

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

3.1.2 實驗結(jié)果

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

表1 靜態(tài)分析結(jié)果對比

3.1.3 結(jié)果分析

通過實驗結(jié)果可以看出，Dependkaller提取的系統(tǒng)調(diào)用間內(nèi)核數(shù)據(jù)依賴信息更全面。

3.2 Dependkaller能否提高代碼覆蓋率和bug發(fā)現(xiàn)數(shù)量

3.2.1 實驗環(huán)境

實驗環(huán)境操作系統(tǒng)為Ubuntu Server 16.04，配置有384GB內(nèi)存，72個Intel CPU，可滿足實驗對內(nèi)存和CPU的需求。

3.2.2 實驗方法

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

3.2.3 實驗結(jié)果

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

表2 模糊測試結(jié)果對比

3.2.4 結(jié)果分析

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

4 結(jié)論

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