顧濤濤,盧帥兵,李 響，況曉輝，趙 剛

(軍事科學(xué)院系統(tǒng)工程研究院信息系統(tǒng)安全技術(shù)國防科技重點實驗室，北京 100101)

1 引言

當(dāng)今信息化時代，軟件產(chǎn)業(yè)飛速發(fā)展，從國防技術(shù)、工業(yè)控制、航空航天、金融證券、郵電通信和醫(yī)療衛(wèi)生等專業(yè)領(lǐng)域到日常生活中的衣食住行，軟件都扮演了重要的角色。隨著人們對軟件功能需求越來越多，軟件變得越來越復(fù)雜，代碼的規(guī)模也大幅增大。不可避免地，軟件的脆弱性問題也越來越多，軟件的安全性問題日益凸顯[1]。近年來，利用軟件脆弱性進行惡意攻擊的事件層出不窮。2014年，美國銀行摩根大通遭黑客攻擊，泄露了超過8 300萬個賬戶、7 600萬個家庭和700萬家小企業(yè)的相關(guān)數(shù)據(jù)。2017年5月12日被披露的勒索病毒 “WannaCry”，是利用一個名為“永恒之藍”的Windows系統(tǒng)脆弱性[2]制作而成的。該勒索病毒席卷了全球100多個國家，對醫(yī)療、教育和銀行等重要機構(gòu)進行攻擊，造成了巨大的經(jīng)濟損失。

軟件脆弱性分析已經(jīng)成為軟件安全領(lǐng)域的一個重要研究方向[3]。安全研究人員使用各種方法來挖掘軟件的脆弱性，例如代碼審計、數(shù)據(jù)流分析、動態(tài)符號執(zhí)行和模糊測試等。在挖掘軟件脆弱性的研究中，以代碼審計為代表的手動分析方法需要依賴專業(yè)人員的經(jīng)驗知識，難以大規(guī)模應(yīng)用；數(shù)據(jù)流分析[4]等靜態(tài)分析方法存在漏報率和誤報率高的缺點，實際應(yīng)用受限；動態(tài)符號執(zhí)行技術(shù)[5]難以解決狀態(tài)爆炸導(dǎo)致的約束求解困難等問題；而模糊測試[6]因自動化程度高、誤報率低等優(yōu)點，逐漸得到產(chǎn)業(yè)界和學(xué)術(shù)界的關(guān)注和認可。然而，真實程序規(guī)模龐大、復(fù)雜多樣，利用模糊測試技術(shù)發(fā)現(xiàn)軟件中潛在脆弱性時也面臨著代碼覆蓋度低、測試效率低等諸多挑戰(zhàn)。隨著并行計算技術(shù)的發(fā)展，并行模糊測試技術(shù)已成為產(chǎn)業(yè)界和學(xué)術(shù)界的研究熱點。早在2016年，微軟[7]和谷歌[8]相繼發(fā)布了各自的分布式模糊測試服務(wù)。微軟的付費服務(wù)Springfield是一款基于云的脆弱性檢測工具，結(jié)合模糊測試幫助開發(fā)人員發(fā)現(xiàn)其應(yīng)用程序的脆弱性。谷歌的開源項目OSS-Fuzz(continuous Fuzzing for Open Source Software)利用了最新的模糊測試技術(shù)和可擴展分布式技術(shù)，為開源軟件進行持續(xù)性的模糊測試。截至2020年6月，OSS-Fuzz已在300個開源項目中發(fā)現(xiàn)超過20 000個漏洞。近期，谷歌開放了OSS-Fuzz后端ClusterFuzz[9]的源代碼，微軟也開源了基于Microsoft Azure云服務(wù)的模糊測試平臺OneFuzz[10]。在學(xué)術(shù)界，安全領(lǐng)域的四大頂級會議每年都接收大量關(guān)于模糊測試的論文[11-13]，也有越來越多的研究團隊開始關(guān)注模糊測試的效率問題。

本文在簡述模糊測試技術(shù)及其面臨的挑戰(zhàn)的基礎(chǔ)上，建立了并行模糊測試的模型框架，從系統(tǒng)結(jié)構(gòu)、任務(wù)劃分、語料庫共享和崩潰去重等方面，分析了當(dāng)前并行模糊測試技術(shù)的研究進展，從并行效率和并行有效性等方面對已有工作進行了評估，討論了并行模糊測試技術(shù)的可能發(fā)展方向。

2 模糊測試技術(shù)面臨的挑戰(zhàn)

2.1 模糊測試的基本流程

模糊測試最早可追溯到1988年，在威斯康辛大學(xué)Miller教授[14]的計算機實驗課上，模糊生成器(Fuzz generator)的概念被首次提出，用于測試Unix程序的健壯性，即用隨機數(shù)據(jù)來測試程序直至程序崩潰。模糊測試一般流程是通過自動化或者半自動化的方法構(gòu)造海量的測試用例并輸入到目標測試程序;然后執(zhí)行目標測試程序并監(jiān)控執(zhí)行過程，檢查程序的行為有無異常;最后對引起程序異常行為的輸入進行詳細分析，確認目標程序的脆弱性。測試過程如圖1所示。

Figure 1 General flow of fuzzing圖1 模糊測試一般流程

模糊測試技術(shù)分為基于生成(Generated-based)的模糊測試技術(shù)和基于變異(Mutation-based)的模糊測試技術(shù)。基于生成的模糊測試技術(shù)是模糊測試器(Fuzzer)利用目標程序輸入規(guī)定的語法來自動生成符合目標程序輸入的測試用例，而基于變異的模糊測試則是模糊測試器通過對程序輸入進行變異(如位翻轉(zhuǎn)、字節(jié)反轉(zhuǎn)、算數(shù)增減和拼接等操作)生成大量的測試用例。傳統(tǒng)的模糊測試工具采用完全隨機的變異策略，測試效果很差，有研究人員把遺傳算法引入了模糊測試，通過反饋機制能消除一部分隨機性。其中覆蓋度是被廣泛采用的反饋內(nèi)容，當(dāng)前最流行的基于變異的覆蓋度反饋模糊測試工具AFL(American Fuzzy Lop)[15]在執(zhí)行已經(jīng)插樁的程序過程中，跟蹤測試用例經(jīng)過的程序路徑并記錄下來，優(yōu)先保留能觸發(fā)新路徑的測試用例，將其加入種子庫，進行下一次迭代，通過這樣的覆蓋度反饋，能引導(dǎo)模糊測試快速探索更深的程序路徑。相應(yīng)的流程圖如圖2所示。由于基于覆蓋度反饋方式是模糊測試領(lǐng)域的重要分支，下面著重介紹該技術(shù)面臨的挑戰(zhàn)。

Figure 2 Fuzzing process based on coverage feedback 圖2 基于覆蓋度反饋模糊測試的流程

2.2 基于覆蓋度反饋模糊測試面臨的主要挑戰(zhàn)

基于覆蓋度反饋的模糊測試的有效性，大量研究人員對圖2中的初始種子構(gòu)建、種子篩選、種子變異、待測目標程序執(zhí)行環(huán)境的構(gòu)建和測試任務(wù)的執(zhí)行等環(huán)節(jié)進行了大量改進。基于覆蓋度反饋的模糊測試技術(shù)面臨的主要挑戰(zhàn)如下所示：

(1)如何獲得初始輸入？最先進的基于覆蓋度反饋的模糊測試技術(shù)都采用基于變異的方式生成測試用例。該策略使測試技術(shù)的有效性在很大程度上依賴初始種子的質(zhì)量，良好的初始種子可以顯著提高測試的效率和效果。當(dāng)前關(guān)注這個問題的工作有很多。Wang等[16]提出了一種數(shù)據(jù)驅(qū)動的種子生成方案Skyfire,從輸入中學(xué)習(xí)概率上下文敏感語法，然后在生成輸入時，把學(xué)到的知識再利用起來。隨著機器學(xué)習(xí)技術(shù)的迅速發(fā)展，來自微軟研究院的Godefroid等[17]使用基于神經(jīng)網(wǎng)絡(luò)的統(tǒng)計機器學(xué)習(xí)技術(shù)來自動生成測試用例。

(2)如何從種子池中篩選種子？在測試過程中，執(zhí)行引擎會重復(fù)地從種子庫中選擇種子，在新一輪循環(huán)開始之前會對選擇的種子進行突變，如何從種子池中選擇好的種子是模糊測試面臨的另一個問題。B?hme等[18]提出了基于馬爾科夫鏈的種子選擇算法，為執(zhí)行低頻路徑的種子分配更多的能量，更好地測試低頻路徑。導(dǎo)向型模糊測試[19]采用定向選擇策略，將一些易受攻擊的代碼定義為目標位置，優(yōu)先選擇距離目標位置更近的測試用例。模糊測試器EcoFuzz[20]采用了一種自適應(yīng)的種子調(diào)度算法，在AFL上運行時獲得了極佳的節(jié)能優(yōu)勢。

(3)如何進行變異？基于覆蓋度反饋模糊測試技術(shù)通過變異種子生成測試用例。然而，如何變異出能夠覆蓋更多程序路徑和觸發(fā)更多漏洞的測試用例是一個關(guān)鍵問題。Rawat等[21]提出了一種集成靜態(tài)分析和動態(tài)污點分析的應(yīng)用感知灰盒模糊測試工具Vuzzer。該工具先利用靜態(tài)分析提取影響控制流的即時值、魔法值和其他特征字符串，再利用動態(tài)污點分析技術(shù)收集信息，影響程序控制流分支。Gan等[22]提出了基于數(shù)據(jù)流的模糊測試器GREYONE，利用數(shù)據(jù)流信息，設(shè)計了模糊測試驅(qū)動的污點推斷模型FTI(Fuzzing-driven Taint Inference)模型，可以精準推斷程序路徑分支轉(zhuǎn)移與測試用例偏移字節(jié)的關(guān)系。

(4)模糊測試技術(shù)如何適應(yīng)多樣化的目標程序場景？比如對操作系統(tǒng)進行模糊測試時，由于操作系統(tǒng)內(nèi)核位于計算機體系底層，特權(quán)級高，不僅需要處理硬件管理事務(wù)，還要對上層程序的運行提供支持，這就導(dǎo)致監(jiān)控內(nèi)核運行時存在一定的技術(shù)困難，必須針對性地構(gòu)建相應(yīng)的測試環(huán)境和插樁，以及進行其他一些預(yù)處理工作?，F(xiàn)在大部分的內(nèi)核模糊測試都不同程度地利用了虛擬化技術(shù)來監(jiān)控運行內(nèi)核[23 - 27]。當(dāng)前代表性的工作有kAFL、HFL、Razzer和JANUS[24 - 27]等等，文獻[28]研究了如何測試虛擬機管理器。文獻[29]研究了如何測試數(shù)據(jù)庫。文獻[30]將模糊測試技術(shù)應(yīng)用到了無人車測試中。

(5)如何加快測試任務(wù)的執(zhí)行速度？根據(jù)概率論的“大數(shù)定律”，只要重復(fù)次數(shù)夠多，隨機性夠強，偶然的事件也會成為必然事件，模糊測試就是“大數(shù)定律”的典型應(yīng)用。 隨著被測目標程序代碼量的快速增長，想要獲得更高的脆弱性發(fā)現(xiàn)率，需要快速執(zhí)行大量的測試用例。在已有的研究[15]中，流行的AFL利用Linux內(nèi)核中的fork調(diào)用，每一次執(zhí)行測試用例時，復(fù)制一個已加載好的進程，避免了重復(fù)執(zhí)行程序運行前的初始化工作，這樣有效提升了單位時間執(zhí)行測試用例的數(shù)量。在模糊測試中，跟蹤程序的執(zhí)行過程也是關(guān)鍵的一環(huán)。文獻[31]利用Intel PT技術(shù)來跟蹤二進制程序的模糊測試，大大降低了單次執(zhí)行的開銷。Nagy等[12]提出了通過放棄跟蹤不觸發(fā)新的代碼覆蓋的執(zhí)行過程，來降低模糊測試過程中的跟蹤執(zhí)行開銷。Zhou等[13]提出的Zeror，在保證模糊測試過程中收集信息的精度的同時，提升了執(zhí)行效率。

能快速地執(zhí)行大量測試用例是模糊測試取得成功的主要原因之一。面對越來越復(fù)雜的測試任務(wù)，現(xiàn)有的模糊測試方法的效率遇到了許多瓶頸，如亟需發(fā)布的項目無法被快速有效地測試，影響產(chǎn)品發(fā)布時間，以及對關(guān)鍵脆弱性的快速查找效率低等問題。因此，越來越多的研究人員開始利用并行計算來提升模糊測試的效率和有效性。比如，谷歌利用云服務(wù)將其可擴展的模糊測試基礎(chǔ)設(shè)施ClusterFuzz[9]部署在25 000個核心上，這是典型的并行模糊測試設(shè)施。截至2020年9月，ClusterFuzz已經(jīng)在谷歌開發(fā)的產(chǎn)品中發(fā)現(xiàn)超過25 000個漏洞[32]。

3 并行模糊測試模型框架

并行模糊測試使用多個模糊測試器同時測試目標程序，是提升模糊測試效率的有效方法。并行模糊測試模型框架如圖3所示，全局主節(jié)點負責(zé)分發(fā)測試任務(wù)，避免子節(jié)點重復(fù)工作，各個子節(jié)點之間通過分享種子等執(zhí)行信息來協(xié)同探索目標程序，最后去除各個子節(jié)點發(fā)現(xiàn)的重復(fù)崩潰，得到全局不重復(fù)唯一崩潰集合。

Figure 3 Framework of parallel fuzzing model 圖3 并行模糊測試模型框架

當(dāng)前并行模糊測試研究的重點主要包括:(1)并行模糊測試體系結(jié)構(gòu)研究，包括控制器/調(diào)度器的設(shè)計，模糊測試器的同構(gòu)/異構(gòu)選擇(各子節(jié)點是否采用不同的模糊測試器)等；(2)任務(wù)劃分問題，有效劃分能減少各個模糊測試器的重復(fù)工作，提升測試的有效性；(3)語料庫共享問題，即共享什么，如何共享，共享時機；(4)崩潰去重問題，在大規(guī)模的并行模糊測試節(jié)點下，有效的崩潰去重方法能大大提升系統(tǒng)的可用性。本文在表1對現(xiàn)有并行模糊測試工作的特征進行了概述。

4 并行模糊測試研究進展

4.1 系統(tǒng)部署規(guī)模及結(jié)構(gòu)

從體系結(jié)構(gòu)角度看，已有研究工作可分為單機/多機并行、主從/對等結(jié)構(gòu)和模糊測試器同構(gòu)/模糊測試器異構(gòu)等類型。

現(xiàn)在的單機多核資源豐富，有些研究[15,33 - 42]將并行模糊測試部署在單機多核上，其并行度不高，一般是100以內(nèi)。比如AFL[15]的并行模式和LibFuzzer[40]，模糊測試技術(shù)在并行時沒有數(shù)據(jù)依賴，理想情況下,效率提升可隨并行度增加而成倍增加，但是在以上2個Fuzzer并行度達到16及以上時，會出現(xiàn)單核性能下降的情況，即單個模糊測試器執(zhí)行測試用例數(shù)大大減少。文獻[33]指出這是由于在單機內(nèi)，AFL和LibFuzzer為加速而采用的fork系統(tǒng)調(diào)用和文件系統(tǒng)，在并行度較大時，頻繁調(diào)用或讀寫種子會出現(xiàn)資源競爭，這嚴重降低了單核模糊測試的性能。文獻[41]的Honggfuzz是自動支持多進程和多線程執(zhí)行的模糊測試技術(shù)，不需要像AFL那樣手動部署多個Fuzzer副本。也有大量研究工作[32，43 - 47]將并行模糊測試部署在多機多核上，稱作分布式模糊測試技術(shù)。例如典型的ClusterFuzz[32]，它將并行模糊測試部署在約25 000個核心的谷歌云上，作為基礎(chǔ)設(shè)施為開發(fā)人員提供軟件模糊測試服務(wù)。Grid[44]利用網(wǎng)格計算資源，將分布在不同地方的模糊測試器通過網(wǎng)絡(luò)通信向服務(wù)端申請和提交模糊測試任務(wù)。文獻[45,46]中也是多機并行工作，在分布式節(jié)點上分別運行AFL的并行模式。Manul[47]是一個支持測試開源程序或黑盒二進制程序的分布式模糊測試工具，可以部署在Windows、Linux和MacOS上。文獻[43]中的測試器UNIFUZZ也支持分布式部署，并評估驗證了128個節(jié)點同時執(zhí)行的有效性。

Table 1 Overview of the parallel fuzzers

在并行模糊測試的框架選擇方面，只有少數(shù)的工作[15，40,41]選擇了對等結(jié)構(gòu)，即整個并行模糊測試中的所有節(jié)點都只執(zhí)行測試任務(wù)，不存在主節(jié)點去調(diào)控子節(jié)點的執(zhí)行。更多的并行模糊測試工作都選擇了主從結(jié)構(gòu)，這是由于模糊測試本身的盲目性，主節(jié)點可以實現(xiàn)豐富的控制、調(diào)度和分析策略來對各個子節(jié)點進行調(diào)節(jié)，使各節(jié)點高效協(xié)同地工作。比如,文獻[42,43]的測試器P-Fuzz和UNIFUZZ在主節(jié)點實現(xiàn)了很好的調(diào)度策略和任務(wù)分發(fā)策略來指導(dǎo)子節(jié)點的執(zhí)行。

近來，越來越多的研究團隊認為異構(gòu)模糊測試器的并行更加有效。文獻[38]的測試器EnFuzz從理論和工程上證明了各并行節(jié)點模糊測試器的多樣性是提升模糊測試有效性的關(guān)鍵點，不同的模糊測試器在并行執(zhí)行目標程序時，對不同路徑約束的求解能力不一樣，協(xié)作執(zhí)行可以到達目標程序更深的路徑。文獻[39]中的測試器CUPID也采用異構(gòu)模糊測試器并行工作?；旌夏：郎y試[48 - 50]也可以看作是一種特殊的異構(gòu)并行模糊測試技術(shù)。

4.2 任務(wù)劃分

程序內(nèi)部包含多種狀態(tài)。使用并行模糊測試技術(shù)測試目標程序時，使每個模糊測試器分別測試目標程序的不同狀態(tài)，能有效提高測試效率。任務(wù)劃分是把一個測試任務(wù)精準地劃分成不同的子任務(wù)，不同任務(wù)間程序狀態(tài)不重復(fù)。已有研究工作可分為基于狀態(tài)空間的任務(wù)劃分和基于輸入空間的任務(wù)劃分2類。

基于狀態(tài)空間的任務(wù)劃分是指:被測目標程序內(nèi)部有多條路徑，表示不同的程序狀態(tài)，根據(jù)路徑將程序內(nèi)部的狀態(tài)劃分為多個部分，不同的模糊測試器執(zhí)行不同部分，完成并行測試。典型研究工作包括Liang等[37]開發(fā)的并行模糊測試器PAFL，它采用了一種基于目標程序分支位圖(Branch Bitmap)的任務(wù)劃分方法，將其分為N份，每個模糊測試器負責(zé)執(zhí)行屬于自己的目標程序分支。開始執(zhí)行時，先根據(jù)種子命中的每個分支的命中次數(shù)來選擇種子，在該種子命中的所有分支中，命中次數(shù)最少的分支是否屬于當(dāng)前模糊測試器任務(wù)范圍，如果屬于則正常執(zhí)行，否則略過該種子并繼續(xù)檢查下一個種子。通過這種任務(wù)劃分策略，每個模糊測試器分別測試程序的不同區(qū)域，增加了并行模糊測試的有效性。然而，Li等[36]認為PAFL框架存在一定缺陷，且當(dāng)測試器FairFuzz[51]應(yīng)用該框架時，只會執(zhí)行命中最稀有分支的測試用例，命中其他有價值分支的用例會被拋棄，因此設(shè)計了更優(yōu)的任務(wù)分發(fā)方式：把單個測試用例對應(yīng)的多個分支都作為一個任務(wù)以備候選，這樣就不會錯過執(zhí)行其他有價值的分支。

Ye等[35]提出的PAFL也是采用類似的任務(wù)劃分和分發(fā)策略，首先通過動態(tài)執(zhí)行信息周期性篩選出有價值的程序狀態(tài)(執(zhí)行次數(shù)較少)，這些程序狀態(tài)之間的關(guān)聯(lián)性較低；然后將其周期性地分發(fā)給各個子實例，各個實例通過“別針”技術(shù)(通過避免變異影響路徑跳轉(zhuǎn)的字節(jié))使各節(jié)點執(zhí)行分配到的程序狀態(tài)，一定周期后，各子節(jié)點上傳執(zhí)行過的狀態(tài)到主節(jié)點，更新全局執(zhí)行狀態(tài)，然后再重新進行狀態(tài)分配，如此重復(fù)直至完成任務(wù)。Grid框架[44]也是根據(jù)測試任務(wù)本身來劃分，在其服務(wù)器端基于SPIKE的分割思想，把目標任務(wù)劃分為不同的子任務(wù)，存儲在HTTP服務(wù)器上，遠程節(jié)點在Zookeeper中獲取任務(wù)簡述，然后到HTTP服務(wù)器去下載相應(yīng)任務(wù)執(zhí)行。

基于狀態(tài)空間來劃分任務(wù)的工作不多，各個實例專注于執(zhí)行其分配到的任務(wù)，在提升模糊測試效率的同時，也增加了代碼覆蓋度。但是，由于其依賴于目標程序結(jié)構(gòu)，使得模糊測試的并行度有限，不適用于大規(guī)模擴展。

并行模糊測試工作大都是基于輸入空間來劃分任務(wù)?；谳斎肟臻g任務(wù)劃分的依據(jù)是不同的輸入測試用例能觸發(fā)的程序狀態(tài)不一樣，因此每個模糊測試器在執(zhí)行觸發(fā)不同路徑的測試用例時，也能保證并行模糊測試的有效性。這方面的代表性工作有UNIFUZZ和P-Fuzz，它們都采用了主從結(jié)構(gòu)，通過主節(jié)點的調(diào)度策略，分配觸發(fā)不同路徑的種子到不同的從節(jié)點。具體來說，當(dāng)各個子節(jié)點發(fā)現(xiàn)有趣的測試用例時，將其傳送到主節(jié)點，然后在全局視角下，主節(jié)點進一步篩選出有趣種子，再通過“請求-回應(yīng)”機制(子節(jié)點實例完成各自的任務(wù)后，主動向主節(jié)點申請任務(wù)，主節(jié)點回應(yīng)后，分發(fā)種子，這在一定程度上實現(xiàn)了負載均衡)分發(fā)任務(wù)到各子節(jié)點。大部分基于輸入空間來劃分任務(wù)的并行模糊測試研究[33，42,43，47]都需要一個主節(jié)點從全局的角度去調(diào)度種子，而AFL、LibFuzzer和Honggfuzz直接共享所有的種子，導(dǎo)致了大量重復(fù)工作?；诋悩?gòu)模糊測試器(比如EnFuzz、CUPID)的任務(wù)劃分也是基于輸入空間劃分的，各測試器之間差異很大，對不同路徑約束求解能力不一，變異種子的方式不同，因此即使被分配了相同的種子，也有可能觸發(fā)不同的目標程序狀態(tài)，這樣就保證了資源利用的有效性。當(dāng)然給并行異構(gòu)模糊測試器加入主節(jié)點，以確定哪一個模糊測試器可以從一個特定的種子受益，更能提升異構(gòu)模糊測試器并行時的有效性。梁洪亮等[52]將符號執(zhí)行與模糊測試的隨機變異方式相結(jié)合，提出了一種適用于并行化環(huán)境的路徑取反算法來生成測試用例，可使各模糊測試器觸發(fā)不同的程序狀態(tài)。

良好的任務(wù)劃分策略不僅能高效地利用硬件資源，而且還能很好地提升測試效果?；跔顟B(tài)空間劃分任務(wù)的方式，更為直觀，利用被測任務(wù)程序的內(nèi)部特征，符合我們對常規(guī)并行計算的理解。但是，由于模糊測試任務(wù)的特性，基于狀態(tài)劃分的并行工作使實例間的語料庫共享帶來的收益不大。另外，由于現(xiàn)有的大部分工作的劃分方式都依賴位圖實現(xiàn)，而位圖不能全面準確地代表程序狀態(tài)空間，因此精準地劃分任務(wù)也是一個難點?；谳斎肟臻g劃分任務(wù)，即依賴種子來劃分任務(wù),是大規(guī)模并行測試采用較多的方式，在大規(guī)模節(jié)點下，同時借助全局和局部的執(zhí)行信息能較好地避免任務(wù)沖突，提升效率。

4.3 語料庫共享

并行模糊測試中各模糊測試器之間的有效共享信息能提高各個節(jié)點對測試程序路徑的探索效率。本節(jié)集中討論并行模糊測試中語料庫共享的內(nèi)容、時機和開銷。

各子節(jié)點之間共享有趣的種子(覆蓋新路徑的種子)是促進節(jié)點間良好協(xié)作的關(guān)鍵。早期的研究直接共享有趣種子[15,45,46]，每個模糊測試器遍歷其他模糊測試器輸出目錄中的有趣種子，判斷其對自己來說是否為有趣新種子，如果有趣則加入本地種子庫，完成共享操作。LibFuzzer在并行工作時，每個模糊測試器在獨立的進程中運行，共享同一個輸出目錄，每個模糊測試器直接共享其他實例發(fā)現(xiàn)的有趣種子。Honggfuzz自動部署并行模式，主進程負責(zé)模糊測試執(zhí)行環(huán)節(jié)以外的所有工作，子進程并行執(zhí)行多個測試用例，也通過同一個輸出目錄實現(xiàn)語料庫共享。ClusterFuzz的基本執(zhí)行單位bot直接共享有趣種子，每個基本執(zhí)行單位把本地的有趣種子上傳到谷歌云存儲平臺中，然后再定期從云存儲中的全局語料庫下載種子。在近期的一些改進工作中，共享內(nèi)容不僅包括有趣種子，還有各節(jié)點的其他信息，這部分信息主要用來指導(dǎo)節(jié)點間更好地共享種子。共享種子以外的其他信息的并行工作都采用主從結(jié)構(gòu)，文獻[34,37,42,43,47]都設(shè)計了一種全局/本地的語料庫共享機制，全局狀態(tài)由所有模糊測試器共同維護，本地狀態(tài)自己維護，這樣可以從全局的角度出發(fā)判斷哪個種子該分配到哪個子節(jié)點。Liang等[37]提出的PAFL就是在全局/本地框架下通過Upload、Update和Pull操作實現(xiàn)種子共享的，首先通過Upload操作上傳各實例的本地指導(dǎo)信息(如分支覆蓋信息)到主節(jié)點，接著通過Update操作來更新全局信息，最后通過Pull操作為各實例獲取當(dāng)前的全局信息和種子，同時更新自己的本地信息和種子。P-Fuzz和UNIFUZZ在語料庫共享過程中，當(dāng)各實例發(fā)現(xiàn)有趣的種子時，就把有趣種子和本地實例的代碼覆蓋位圖傳送到主節(jié)點，然后主節(jié)點合并更新全局代碼覆蓋位圖，最后根據(jù)全局覆蓋位圖為各實例分發(fā)種子，同時用全局位圖更新本地位圖。Manul也在執(zhí)行過程中共享了代碼覆蓋位圖。Li等[34]認為在大規(guī)模并行共享時，代碼覆蓋度的載體位圖會成為共享時的瓶頸，因此通過靜態(tài)分析收集基本塊的跳轉(zhuǎn)，設(shè)計了一個更適合大規(guī)模并行時共享的信息載體。UNIFUZZ在共享代碼覆蓋信息和種子的同時，還分享了模糊測試過程中的信息(比如該種子的執(zhí)行次數(shù))，這個信息伴隨有趣種子上傳。UNIFUZZ是基于AFL開發(fā)的，主節(jié)點利用種子的執(zhí)行次數(shù)來評價種子，進而篩選出更優(yōu)的種子。在未來的研究工作中，還可以共享各子節(jié)點間更豐富的測試信息來互相協(xié)作。

語料庫共享時機的選擇取決于并行度和共享內(nèi)容。由于模糊測試自動執(zhí)行大量測試用例，大規(guī)模實例并行時需要考慮共享時的競爭問題，對于共享代碼覆蓋信息的工作，由于子節(jié)點的覆蓋信息更新很快，頻繁地共享指導(dǎo)信息會導(dǎo)致性能下降。因此,大部分研究[9,15,37,40,45 - 47]都是周期性共享信息。也有部分工作[44,45]基于主從結(jié)構(gòu)實現(xiàn)即時共享，當(dāng)各子實例發(fā)現(xiàn)有趣種子時，即時將覆蓋信息和種子上傳到主節(jié)點，通過加鎖/解鎖來避免競爭，當(dāng)各子節(jié)點完成任務(wù)時，即時從主節(jié)點獲取任務(wù)和種子。在異構(gòu)模糊測試器[38,39]并行時，由于各子節(jié)點執(zhí)行速度不一致，因此不適合周期性共享，采用了全局同步-本地異步的共享方式，當(dāng)各子節(jié)點發(fā)現(xiàn)有趣種子時，即時上傳到主節(jié)點，然后主節(jié)點周期性地向各子節(jié)點共享有趣種子。也有Ye等[35]的PAFL根據(jù)其設(shè)計的共享機制采取了按需請求(On-Demand)的方式，當(dāng)子節(jié)點沒有特定的種子時，才向主節(jié)點申請相應(yīng)的種子。

并行模糊測試框架引入語料庫共享環(huán)節(jié)帶來的共享開銷是研究人員研究的又一個重點。共享開銷與共享機制和共享途徑相關(guān)。對于各個子實例都是平等結(jié)構(gòu)，沒有主節(jié)點，各個實例之間共享時的復(fù)雜度為O(n2)，比如AFL的并行模式，因此，文獻[33]的Perf-Fuzz針對AFL的共享開銷問題設(shè)計了內(nèi)存共享，在內(nèi)存中維護一個(Testcase_log)循環(huán)隊列，每個日志存儲測試用例的文件名、大小、哈希值和代碼覆蓋位圖，各個子節(jié)點從隊列中依次取出種子簡要信息，將其中代碼覆蓋位圖和自己的位圖對比，決定是否執(zhí)行該測試用例。主從結(jié)構(gòu)框架的復(fù)雜度為O(n),顯然更小。從共享途徑來看，單機內(nèi)的工作[33，37，49]可以采用內(nèi)存共享來降低開銷。多機分布式部署的工作[9,45,47 - 49]，都是通過高性能網(wǎng)絡(luò)通信，基于文件系統(tǒng)傳輸有趣種子。其中Manul[49]在單機內(nèi)使用共享內(nèi)存存儲共享信息，在分布式環(huán)境下，采用虛擬共享內(nèi)存存儲共享信息。UNIFUZZ[45]和P-Fuzz[44]采用主從結(jié)構(gòu)，在主節(jié)點使用數(shù)據(jù)庫存儲種子摘要信息，通過摘要信息去調(diào)度種子，進而降低共享開銷。

4.4 崩潰去重

模糊測試的崩潰去重環(huán)節(jié)是提高測試結(jié)果可用性的關(guān)鍵[53]?；诜答伒乃惴〞延|發(fā)崩潰的測試用例保存為種子，進一步對其變異執(zhí)行，此時新的測試用例很容易執(zhí)行相似的函數(shù)，出現(xiàn)相同的錯誤，導(dǎo)致重復(fù)的崩潰，沒有崩潰去重環(huán)節(jié)會嚴重影響對測試結(jié)果的判斷。當(dāng)前流行的單核模糊測試實例崩潰去重方法有：堆?；厮莨?、基于覆蓋的重復(fù)數(shù)據(jù)刪除和語義感知的重復(fù)數(shù)據(jù)刪除。并行模糊測試技術(shù)的崩潰去重是新引入的問題，當(dāng)模糊測試實例并行時，各實例僅在各自內(nèi)部進行崩潰去重，但并行節(jié)點之間也會出現(xiàn)重復(fù)崩潰，特別當(dāng)節(jié)點數(shù)過多時，這個問題會變得不可忽視。當(dāng)前的并行模糊測試研究中，只有少部分工作提出了改進，EnFuzz在主節(jié)點維護了一個全局崩潰列表，利用全局代碼覆蓋位圖和內(nèi)存檢測工具去除全局重復(fù)崩潰，并對崩潰進行分類;Li等[34]基于基本塊的跳轉(zhuǎn)設(shè)計了適用于大規(guī)模并行的數(shù)據(jù)結(jié)構(gòu)來簡化執(zhí)行信息表示，同時利用測試用例觸發(fā)的基本塊跳轉(zhuǎn)序列和自身的堆棧校驗和過濾去除重復(fù)崩潰；ClusterFuzz部署在超過了25 000個并行實例，其內(nèi)部通過谷歌云強大的算力來統(tǒng)計全局崩潰信息，利用內(nèi)存錯誤檢測工具和漏洞相關(guān)聯(lián)的堆棧跟蹤信息去除重復(fù)崩潰。在大規(guī)模并行模糊測試技術(shù)中，如何精準且低開銷地去除重復(fù)崩潰是該技術(shù)面臨的重要挑戰(zhàn)。

4.5 評估

當(dāng)前的并行模糊測試技術(shù)通過對硬件資源的有效利用，大大提升了其模糊測試的效率。Perf-Fuzz從操作系統(tǒng)層面改進了AFL和LibFuzzer，消除文件系統(tǒng)和fork調(diào)用瓶頸，引入內(nèi)存共享機制和更輕量級的啟動任務(wù)策略，驗證了在單機內(nèi)部署120個實例時該改進工作的有效性。P-Fuzz和UNIFUZZ在到達代碼覆蓋度(單核模糊測試的代碼覆蓋度)上限之前，隨著資源增加，有效地減少了執(zhí)行時間。也有部分工作相對于單核代碼覆蓋度，不僅減少了執(zhí)行時間，還增加了覆蓋度。在PAFL[35,37]的評估環(huán)節(jié)中，由于其采用基于狀態(tài)空間的任務(wù)劃分策略，各實例專注于執(zhí)行程序各部分，使驗證環(huán)節(jié)中的程序代碼覆蓋度上有一定提升，AFLFast[18]和FairFuzz[53]應(yīng)用并行框架PAFL[37]部署在4個實例上，分別提升了8%和17%的代碼覆蓋度，多觸發(fā)了79%和52%的唯一崩潰。作為第一個異構(gòu)并行模糊測試器，EnFuzz采用基于輸入空間的任務(wù)劃分策略，從其評估數(shù)據(jù)來看，有效地提高了代碼覆蓋度，比參考對象平均多發(fā)現(xiàn)了93%的唯一漏洞，多執(zhí)行了48.25%的路徑，多覆蓋了17.8%的分支。

5 結(jié)束語

并行模糊測試技術(shù)的效率提升程度與其并行結(jié)構(gòu)、任務(wù)分發(fā)策略和語料庫共享策略相關(guān)。時間效率方面，由于各實例間無數(shù)據(jù)相關(guān)依賴，隨著并行實例數(shù)的增加，測試時間理論上應(yīng)線性減少，但是由于模糊測試固有的隨機性以及并行框架引入的其他開銷，依然存在一定的時間效率損失。大部分并行工作選擇了主從結(jié)構(gòu)，主節(jié)點擁有全局的執(zhí)行信息，其任務(wù)分發(fā)機制、語料庫共享機制和崩潰去重機制都能在主節(jié)點中更好地實現(xiàn)。從部分并行模糊測試技術(shù)的評估結(jié)果來看，其效率提升與任務(wù)分發(fā)策略和語料庫共享策略相關(guān)。好的策略能減少各節(jié)點間的重復(fù)工作，提高資源利用率，也能降低節(jié)點間通信的額外開銷。語料庫共享策略方面，在主節(jié)點對種子進行篩選比較的方式比各實例遍歷各自輸出目錄的種子更有效；使用內(nèi)存共享語料庫比通過文件系統(tǒng)共享語料庫開銷低，但實現(xiàn)更復(fù)雜；在共享時機的選擇上，周期性共享比即時共享更容易實現(xiàn)，但周期設(shè)置不當(dāng)也會導(dǎo)致各部分信息無法及時共享，進而影響有效性。任務(wù)分發(fā)策略方面，基于輸入空間的任務(wù)劃分策略可擴展性強，實現(xiàn)簡單，能有效縮短測試時間，但是會遭遇無法突破代碼覆蓋度的瓶頸；基于狀態(tài)空間的任務(wù)劃分策略使得每一個測試實例專注于執(zhí)行各自劃分到的程序路徑，能充分測試該程序狀態(tài)，在縮短測試時間的同時也提升了代碼覆蓋度，但會遇到可擴展性問題。從評估結(jié)果看，由于各異構(gòu)模糊測試器對同一問題有不同的解決能力，能探索更深的路徑，異構(gòu)模糊測試器并行技術(shù)能提高代碼覆蓋度，另外由于采用基于輸入空間的任務(wù)劃分策略，因此可以大規(guī)模部署。因此,在未來的大規(guī)模分布式模糊測試技術(shù)中，采用異構(gòu)模糊測試器是很好的方案。

在未來的異構(gòu)并行模糊測試技術(shù)工作中，可以關(guān)注以下幾個研究方向：

(1)由于異構(gòu)模糊測試器的差異性，其各自包含的執(zhí)行信息有異同之處，因此如何選擇更合適的語料庫共享策略是可以研究的問題。通過在主節(jié)點處對需共享的信息進行統(tǒng)一的轉(zhuǎn)換后再進行判斷和共享，可以初步解決這個問題。

(2)異構(gòu)模糊測試器對測試任務(wù)的表現(xiàn)能力不同，從資源調(diào)度的角度，對更優(yōu)的模糊測試器分配更多的資源，從而提升效率。

(3)異構(gòu)并行模糊測試技術(shù)的崩潰去重問題。在并行模糊測試技術(shù)的崩潰去重的基礎(chǔ)上，各異構(gòu)模糊測試器可以采用不同的崩潰去重方案，如何在主節(jié)點精準地去重是可以研究的問題。

(4)異構(gòu)并行模糊測試技術(shù)的任務(wù)分發(fā)問題。雖然異構(gòu)模糊測試器對不同約束的求解能力不一樣，但是在主節(jié)點分發(fā)測試用例時，如何更準確地判斷哪一個模糊測試器將會從某個測試用例中受益是可以研究的問題。

(5)異構(gòu)模糊測試器之間的組合問題。已有部分工作研究如何選擇最優(yōu)的異構(gòu)模糊測試器組合，但是都是靜態(tài)選擇?？紤]到執(zhí)行過程中需面對程序路徑的變化，如何動態(tài)調(diào)整異構(gòu)模糊測試器的組合也是可以研究的方向。