模糊測(cè)試改進(jìn)技術(shù)評(píng)估①

張 陽(yáng),佟思明,程 亮,孫曉山

1(中國(guó)科學(xué)院大學(xué),北京 100049)

2(中國(guó)科學(xué)院 軟件研究所 可信計(jì)算與信息保障實(shí)驗(yàn)室,北京 100190)

1 緒論

近年來(lái),利用軟件漏洞實(shí)施安全攻擊的行為層出不窮,如何更好地保證軟件質(zhì)量和安全,減少軟件及系統(tǒng)漏洞,成為當(dāng)前安全領(lǐng)域一個(gè)重要的研究方向.

模糊測(cè)試[1]是一種動(dòng)態(tài)軟件漏洞挖掘技術(shù),能夠有效檢測(cè)軟件或計(jì)算機(jī)系統(tǒng)中的安全漏洞.其核心思想是將變異生成的隨機(jī)數(shù)據(jù)輸入待測(cè)試程序中,監(jiān)視程序運(yùn)行情況,當(dāng)發(fā)現(xiàn)程序出現(xiàn)崩潰或其他異常情況時(shí)保存數(shù)據(jù),從而找到程序漏洞.相比于其他軟件安全檢測(cè)技術(shù),如代碼審計(jì)[2]、污點(diǎn)分析[3]、符號(hào)執(zhí)行[4]等,模糊測(cè)試技術(shù)具有自動(dòng)化程度高,時(shí)間開銷小,應(yīng)用范圍廣的優(yōu)點(diǎn),模糊測(cè)試作為一種高效的漏洞挖掘技術(shù)在近些年得到了學(xué)術(shù)界及工業(yè)界的廣泛關(guān)注和應(yīng)用.

模糊測(cè)試逐漸成為最有效的漏洞挖掘技術(shù)之一,但受其動(dòng)態(tài)測(cè)試的本質(zhì)所限,模糊測(cè)試的代碼覆蓋率難以達(dá)到較高水平.為了提高模糊測(cè)試技術(shù)的效率與準(zhǔn)確率,近年來(lái),相關(guān)領(lǐng)域?qū)W者在模糊測(cè)試技術(shù)上提出了一系列改進(jìn)策略與算法[1].這些工作通常對(duì)模糊測(cè)試過(guò)程中的多個(gè)步驟同時(shí)進(jìn)行了改進(jìn),包含多種改進(jìn)技術(shù),以追求更好的改進(jìn)效果.然而,當(dāng)前仍沒有工作對(duì)單一改進(jìn)技術(shù)的改進(jìn)效果及其原因進(jìn)行系統(tǒng)全面的評(píng)估和分析.因此,本文建立了單一模糊測(cè)試改進(jìn)技術(shù)評(píng)估體系,對(duì)近年來(lái)信息安全高水平會(huì)議期刊模糊測(cè)試改進(jìn)工具所包含的單一改進(jìn)技術(shù)進(jìn)行拆分、評(píng)估與分析,基于改進(jìn)算法特點(diǎn)進(jìn)行分類,通過(guò)數(shù)據(jù)對(duì)比得到不同改進(jìn)類別中改進(jìn)算法的實(shí)際效果評(píng)價(jià),希望對(duì)模糊測(cè)試改進(jìn)技術(shù)有更清晰深入的認(rèn)識(shí),同時(shí)根據(jù)不同改進(jìn)技術(shù)的不同改進(jìn)效果原因分析,幫助未來(lái)的模糊測(cè)試改進(jìn)工作取得更好的效果.

2 研究背景

本節(jié)首先介紹模糊測(cè)試技術(shù)的基本分類,說(shuō)明基于變異的灰盒模糊測(cè)試工具工作流程,然后介紹經(jīng)典基于變異的灰盒模糊測(cè)試工具American Fuzzy Lop (AFL)[5].

2.1 模糊測(cè)試技術(shù)分類

當(dāng)前模糊測(cè)試技術(shù)方法根據(jù)樣本生成方法可以分為基于變異的模糊測(cè)試以及基于生成的模糊測(cè)試兩類[6].

(1)基于變異的模糊測(cè)試

基于變異的模糊測(cè)試通過(guò)改變已有的數(shù)據(jù)樣本去生成測(cè)試數(shù)據(jù).對(duì)于種子樣本,模糊測(cè)試工具通過(guò)對(duì)該樣本進(jìn)行位翻轉(zhuǎn)、數(shù)學(xué)加減、插入刪除、拼接等操作,得到新的種子,遍歷更多的程序執(zhí)行路徑,以達(dá)到更高的代碼覆蓋,從而發(fā)現(xiàn)更多程序中可能存在的漏洞.

(2)基于生成的模糊測(cè)試

基于生成的模糊測(cè)試則主要應(yīng)用于針對(duì)協(xié)議、JS引擎等以高度結(jié)構(gòu)化格式文件為輸入的目標(biāo)程序,由于這些程序中存在大量的格式檢查,輸入文件的不同字段具有一定的語(yǔ)法語(yǔ)義,隨機(jī)的變異往往無(wú)法滿足要求,因此需要通過(guò)一定的規(guī)則和算法生成輸入文件.

根據(jù)對(duì)待測(cè)試程序內(nèi)部結(jié)構(gòu)的認(rèn)知程度,模糊測(cè)試可以分為白盒模糊測(cè)試、黑盒模糊測(cè)試以及灰盒模糊測(cè)試3 類[6].

(1)黑盒模糊測(cè)試

黑盒模糊測(cè)試不考慮待測(cè)試程序的內(nèi)部邏輯,持續(xù)生成隨機(jī)樣本輸入程序,觀察待測(cè)試程序的執(zhí)行情況.

(2)白盒模糊測(cè)試

白盒模糊測(cè)試指在獲取到待測(cè)試程序的內(nèi)部實(shí)現(xiàn)信息,如源代碼、設(shè)計(jì)細(xì)節(jié)以及運(yùn)行時(shí)信息等之后,利用已有信息針對(duì)性地對(duì)程序進(jìn)行測(cè)試的方法.

(3)灰盒模糊測(cè)試

灰盒模糊測(cè)試介于黑盒模糊測(cè)試和白盒模糊測(cè)試之間,通過(guò)獲取一些待測(cè)試程序的信息,如運(yùn)行時(shí)分支覆蓋來(lái)指導(dǎo)模糊測(cè)試從而提高測(cè)試效率.常見灰盒模糊測(cè)試工具通過(guò)輕量級(jí)代碼插樁等方法獲取所需信息.

基于變異的灰盒模糊測(cè)試具有應(yīng)用范圍廣、執(zhí)行效率高的特點(diǎn),受到了相關(guān)學(xué)者的廣泛關(guān)注,近年提出的模糊測(cè)試工作多數(shù)基于此類型,因此本文主要針對(duì)基于變異的灰盒模糊測(cè)試改進(jìn)技術(shù)進(jìn)行評(píng)估與分析.

2.2 基于變異的灰盒模糊測(cè)試工具流程

多數(shù)基于變異的灰盒模糊測(cè)試工具工作流程如圖1所示,首先從初始種子隊(duì)列中選取合適的輸入,然后,模糊測(cè)試工具重復(fù)地對(duì)這些輸入進(jìn)行變異并執(zhí)行待測(cè)試程序.如果程序運(yùn)行中出現(xiàn)了異常行為,則模糊測(cè)試工具保留變異的輸入以便將來(lái)使用,并記錄觀察到的具體信息.最終,由于達(dá)到特定目標(biāo),如發(fā)現(xiàn)某種漏洞,或用戶主動(dòng)停止,模糊測(cè)試結(jié)束.

圖1 基于變異的灰盒模糊測(cè)試工具流程圖

2.3 American Fuzzy Lop (AFL)

AFL[5]由Google 的Michal Zalewski 所開發(fā),是當(dāng)前最流行的模糊測(cè)試工具之一.

AFL 是一個(gè)采用遺傳算法基于變異的灰盒模糊測(cè)試工具,能夠有效提高待測(cè)試程序的代碼覆蓋率.AFL 需要用戶提供待測(cè)試程序、運(yùn)行測(cè)試應(yīng)用程序的示例命令和至少一個(gè)小的示例輸入文件.然后,AFL 嘗試實(shí)際執(zhí)行指定的命令,通過(guò)對(duì)輸入文件進(jìn)行各種變異修改來(lái)執(zhí)行待測(cè)試程序的不同路徑.當(dāng)測(cè)試程序崩潰或掛起時(shí),可能意味著發(fā)現(xiàn)了一個(gè)新的安全漏洞.在這種情況下,AFL 將保存修改后的輸入文件以供用戶進(jìn)一步檢查.為了最大限度地提高模糊測(cè)試性能,AFL在編譯過(guò)程中通過(guò)代碼插樁,在程序運(yùn)行時(shí)記錄分支覆蓋情況,進(jìn)一步引導(dǎo)模糊測(cè)試.模糊測(cè)試工具AFL的具體工作流程如圖2 所示.

圖2 AFL 工作流程圖

AFL 作為經(jīng)典的基于變異的灰盒模糊測(cè)試工具,設(shè)計(jì)結(jié)構(gòu)完整,算法準(zhǔn)確高效,可擴(kuò)展性強(qiáng),近年來(lái)很多模糊測(cè)試改進(jìn)工作選擇基于AFL 實(shí)現(xiàn)[7-11],因此本文選擇AFL 作為基準(zhǔn)模糊測(cè)試工具進(jìn)行改進(jìn)技術(shù)的評(píng)估與分析.

3 模糊測(cè)試改進(jìn)技術(shù)總結(jié)

本節(jié)首先介紹對(duì)模糊測(cè)試改進(jìn)技術(shù)的分類以及相應(yīng)類別中近年提出的先進(jìn)改進(jìn)技術(shù),然后對(duì)這些單一改進(jìn)技術(shù)進(jìn)行整理總結(jié)與分析,如圖3 所示.

3.1 模糊測(cè)試改進(jìn)技術(shù)分類與介紹

由第2 節(jié)介紹可知,當(dāng)前基于變異的灰盒模糊測(cè)試工具工作流程可根據(jù)不同操作進(jìn)行較為清晰的階段劃分.基于不同模糊測(cè)試階段的操作復(fù)雜程度與近年相關(guān)學(xué)者對(duì)不同階段的改進(jìn)關(guān)注程度,本文將模糊測(cè)試改進(jìn)技術(shù)分為了4 個(gè)類別,即種子選取策略改進(jìn)、變異策略改進(jìn)、能量分配策略改進(jìn)以及其他方面的改進(jìn)技術(shù).下面將對(duì)各類別的改進(jìn)技術(shù)進(jìn)行說(shuō)明,并對(duì)屬于不同類別的一些改進(jìn)技術(shù)進(jìn)行簡(jiǎn)單介紹.

(1)種子選取策略改進(jìn)技術(shù)

該類別的改進(jìn)技術(shù)重點(diǎn)解決如何從種子隊(duì)列中選擇高質(zhì)量種子進(jìn)行變異的問(wèn)題.AFLFast[12]傾向于選擇低頻路徑更多的、更少被選擇的種子進(jìn)行變異;FairFuzz[13]提出了低頻邊的概念,在測(cè)試過(guò)程中記錄不同邊被訪問(wèn)的次數(shù),僅選擇具有低頻邊的種子進(jìn)行進(jìn)一步變異; CollAFL[7]優(yōu)先選擇具有更多內(nèi)存訪問(wèn)操作、未訪問(wèn)的鄰居邊或未訪問(wèn)的鄰居后繼的種子;SAFL[8]通過(guò)符號(hào)執(zhí)行生成初始種子集合,并在測(cè)試中優(yōu)先選擇具有稀有邊的種子; EcoFuzz[14]將模糊測(cè)試分為了探索(exploration)和利用(exploitation)兩個(gè)階段,在探索階段按照順序選擇種子,利用階段優(yōu)先選擇自轉(zhuǎn)移頻率低且隊(duì)列中編號(hào)較大的種子.

(2)變異策略改進(jìn)技術(shù)

當(dāng)從隊(duì)列中選擇了種子后,模糊測(cè)試工具對(duì)選擇的種子進(jìn)行一系列變異操作以生成新樣本,訪問(wèn)目標(biāo)程序中新的路徑,從而觸發(fā)新的漏洞.變異策略改進(jìn)技術(shù)通過(guò)優(yōu)化對(duì)選定種子的變異操作和變異位擇,提高變異效率,從而提高模糊測(cè)試效果.Angora[11]通過(guò)污點(diǎn)分析技術(shù)搜索種子中能夠提高代碼覆蓋率的變異操作和變異位置,并在模糊測(cè)試過(guò)程中通過(guò)梯度下降算法解決路徑約束問(wèn)題; B?ttinger 等人[15]提出通過(guò)強(qiáng)化學(xué)習(xí)得到能夠增加代碼覆蓋的變異操作及變異位置;FairFuzz[13]在確定性變異階段記錄不影響低頻邊覆蓋的變異操作和變異位置,并在后續(xù)隨機(jī)的非確定性變異階段進(jìn)行相應(yīng)變異; MOPT[16]通過(guò)粒子群算法優(yōu)化變異操作的選擇; Karamcheti 等人[17]提出根據(jù)湯普森采樣算法選擇當(dāng)前最優(yōu)的變異操作.

(3)能量分配策略改進(jìn)技術(shù)

能量分配指,在非確定性變異階段對(duì)選定種子選擇隨機(jī)變異次數(shù)的過(guò)程.能量分配策略改進(jìn)技術(shù)通過(guò)對(duì)種子的價(jià)值進(jìn)行評(píng)估,優(yōu)化對(duì)不同種子選擇的變異次數(shù),對(duì)更有可能生成更多有價(jià)值樣本的種子賦予更多的變異次數(shù).AFLFast[12]基于馬爾科夫鏈提出了5 種不同的能量分配策略,根據(jù)種子的被選擇的次數(shù)以及訪問(wèn)路徑被訪問(wèn)的次數(shù)計(jì)算分配的變異次數(shù); BanditAFL[18]將能量分配問(wèn)題看作多臂老虎機(jī)問(wèn)題,通過(guò)強(qiáng)化學(xué)習(xí)計(jì)算最優(yōu)的能量分配策略; EcoFuzz[14]首先計(jì)算發(fā)現(xiàn)新路徑平均所需的變異次數(shù),并根據(jù)當(dāng)前種子路徑被訪問(wèn)的次數(shù)以及上一個(gè)種子發(fā)現(xiàn)新路徑的變異次數(shù)進(jìn)行調(diào)整.

(4)其他方面改進(jìn)技術(shù)

除上述3 種常見模糊測(cè)試改進(jìn)技術(shù)類別外,一些工具提出了針對(duì)模糊測(cè)試不同階段的多種其他方面改進(jìn)技術(shù).如,CollAFL[7]指出傳統(tǒng)的邊覆蓋計(jì)算是不精確的,提出了通過(guò)解決哈希碰撞問(wèn)題計(jì)算更準(zhǔn)確的邊覆蓋的方法; INSTRIM[19]修改了傳統(tǒng)AFL 的插樁方法以達(dá)到更快的代碼執(zhí)行速度; Xu 等人[20]通過(guò)優(yōu)化系統(tǒng)調(diào)用等方法提高模糊測(cè)試效率.該類別的改進(jìn)技術(shù)通常從較獨(dú)特的角度優(yōu)化模糊測(cè)試流程或嘗試解決較少被考慮的問(wèn)題,因此我們不對(duì)這一類別的改進(jìn)技術(shù)進(jìn)行進(jìn)一步劃分.

3.2 模糊測(cè)試改進(jìn)技術(shù)總結(jié)與分析

我們對(duì)近年來(lái)在安全高水平會(huì)議期刊中發(fā)表的灰盒模糊測(cè)試改進(jìn)工作共46 篇文章[7,8,11-54]進(jìn)行了整理,將其中的改進(jìn)技術(shù)進(jìn)行分類.按照第3.1 節(jié)中的分類標(biāo)準(zhǔn),將基于變異的灰盒模糊測(cè)試改進(jìn)技術(shù)劃分為種子選取策略改進(jìn)、變異策略改進(jìn)、能量分配策略改進(jìn)以及其他方向改進(jìn)4 類.模糊測(cè)試相關(guān)改進(jìn)技術(shù)整理如圖3 所示.其中橫坐標(biāo)表示模糊測(cè)試改進(jìn)技術(shù)提出的時(shí)間,縱坐標(biāo)表示改進(jìn)所屬類別,將每個(gè)改進(jìn)工具根據(jù)以上兩個(gè)標(biāo)準(zhǔn)歸納入不同單元格內(nèi),每個(gè)單元格顏色表示包含該類別改進(jìn)技術(shù)的工具數(shù)量,顏色所表示含義參照右側(cè)圖例.其中工具中所標(biāo)注的*表示該模糊測(cè)試工具基于AFL 實(shí)現(xiàn).

圖3 模糊測(cè)試改進(jìn)技術(shù)分類整理

由圖3 分析可知,從整體上看,在整理的46 個(gè)模糊測(cè)試改進(jìn)工具中,47.83% (22/46)的工具提出了種子選取策略改進(jìn),47.83% (22/46)的工具提出了變異策略改進(jìn),8.70% (4/46)提出了能量分配策略改進(jìn),39.13%(18/46)提出了其他方向的改進(jìn)方法.從改進(jìn)類別方面分析,模糊測(cè)試研究人員更多關(guān)注種子選取和變異策略的改進(jìn),而對(duì)能量分配策略以及其他方向的改進(jìn)關(guān)注度較低.從改進(jìn)技術(shù)所提出的時(shí)間分析,自從2015年高效的模糊測(cè)試工具AFL 被提出實(shí)現(xiàn),模糊測(cè)試改進(jìn)技術(shù)進(jìn)入快速發(fā)展階段,每年有很多不同類別的改進(jìn)工作被陸續(xù)提出,2018年達(dá)到一個(gè)高峰期,2019年后由于模糊測(cè)試代碼覆蓋率的瓶頸問(wèn)題沒有得到有效解決,且沒有更多快速發(fā)展的模糊測(cè)試新興方向,模糊測(cè)試改進(jìn)工作的熱度呈下降趨勢(shì).

此外,在46 個(gè)模糊測(cè)試改進(jìn)工具中,65.22% (30/46)的工具基于AFL 改進(jìn)實(shí)現(xiàn),且?guī)缀跛泄ぞ邔FL 作為對(duì)照工具進(jìn)行相應(yīng)改進(jìn)技術(shù)的評(píng)估,AFL 在當(dāng)前的模糊測(cè)試改進(jìn)工作中至今仍處于非常重要的地位.

4 評(píng)估體系建立

為了系統(tǒng)量化地評(píng)估單一模糊測(cè)試改進(jìn)技術(shù),本文建立了單一模糊測(cè)試改進(jìn)技術(shù)評(píng)估體系.本節(jié)首先對(duì)評(píng)估體系設(shè)計(jì)進(jìn)行整體介紹,然后說(shuō)明評(píng)估體系指標(biāo)選取,最后對(duì)說(shuō)明綜合評(píng)估結(jié)果的計(jì)算模型.

4.1 評(píng)估體系概述

該單一模糊測(cè)試改進(jìn)技術(shù)評(píng)估體系整體設(shè)計(jì)如圖4所示.首先準(zhǔn)備待評(píng)估的模糊測(cè)試改進(jìn)技術(shù),確定基準(zhǔn)模糊測(cè)試工具,在其之上結(jié)合待評(píng)估的模糊測(cè)試改進(jìn)技術(shù),形成單一改進(jìn)模糊測(cè)試工具.選擇用于測(cè)試的程序集,將單一改進(jìn)模糊測(cè)試工具在測(cè)試程序集上進(jìn)行多次固定時(shí)間的模糊測(cè)試,獲得隊(duì)列中的種子樣本、崩潰樣本,以及其他模糊測(cè)試的運(yùn)行時(shí)信息.之后對(duì)獲取到的數(shù)據(jù)進(jìn)行處理,計(jì)算得到單一改進(jìn)模糊測(cè)試工具的邊覆蓋數(shù)量、去重后的崩潰樣本數(shù)量、低頻邊比例以及內(nèi)存操作指令數(shù)量4 個(gè)指標(biāo),根據(jù)算法計(jì)算得到最終的模糊測(cè)試改進(jìn)效果評(píng)估結(jié)果.

圖4 模糊測(cè)試評(píng)估體系架構(gòu)圖

4.2 評(píng)估體系指標(biāo)選取

根據(jù)近期國(guó)內(nèi)外模糊測(cè)試改進(jìn)工作的整理,結(jié)合對(duì)模糊測(cè)試改進(jìn)效果影響因素的分析,選取了4 個(gè)用于評(píng)估的指標(biāo),即測(cè)試程序邊覆蓋率、去重后崩潰樣本數(shù)量、覆蓋低頻邊所占比例以及覆蓋測(cè)試程序內(nèi)存操作指令的數(shù)量.

(1)邊覆蓋數(shù)量

測(cè)試程序中的邊用于反映程序中基本塊之間的執(zhí)行路徑關(guān)系,邊的覆蓋率越高,測(cè)試的程序路徑越全面,從而能夠發(fā)現(xiàn)其中更多的潛在漏洞.與路徑覆蓋相比,邊覆蓋指標(biāo)只關(guān)注覆蓋邊的情況而忽略發(fā)現(xiàn)新邊的種子以及新邊在一次執(zhí)行中覆蓋的次數(shù),更能清晰準(zhǔn)確地反映程序覆蓋情況.近年的模糊測(cè)試改進(jìn)工作評(píng)估中往往將邊覆蓋率作為評(píng)價(jià)模糊測(cè)試工具效果的基本指標(biāo),因此將邊覆蓋數(shù)量作為該評(píng)估體系的第1 個(gè)指標(biāo).

(2)去重崩潰樣本數(shù)量

在模糊測(cè)試中,程序由于異常輸入所導(dǎo)致的崩潰,很可能是因?yàn)橛|發(fā)了程序中潛在的漏洞,當(dāng)程序在執(zhí)行過(guò)程中發(fā)生崩潰,AFL 會(huì)首先檢查此前的崩潰輸入中是否有與當(dāng)前輸入的分支覆蓋完全相同的輸入樣本,若沒有則保存.通常情況下,崩潰樣本越多,可能存在的漏洞數(shù)量則越多.然而,AFL 所收集的崩潰樣本可能

存在大量重復(fù).如圖5 所示,假設(shè)此時(shí)存在一個(gè)待檢測(cè)的程序代碼片段,其第5 行的crash()函數(shù)存在漏洞,當(dāng)兩個(gè)輸入的變量a 分別為True 和False 的時(shí)候都會(huì)觸發(fā)該漏洞,由于執(zhí)行路徑不同,AFL 會(huì)將兩個(gè)輸入樣本均保留,然而這兩個(gè)樣本實(shí)際上觸發(fā)的為一個(gè)漏洞.因此,在評(píng)估以AFL 為基礎(chǔ)的模糊測(cè)試工具時(shí),將AFL 原始保留的崩潰樣本進(jìn)行去重,將調(diào)用棧相同的樣本看做同一個(gè)崩潰樣本,計(jì)算去重后的崩潰樣本數(shù)量,作為評(píng)估體系的第2 個(gè)指標(biāo).

圖5 觸發(fā)漏洞示例程序代碼片段

(3)低頻邊比例

在模糊測(cè)試中發(fā)現(xiàn)邊的數(shù)量整體上可以反映模糊測(cè)試工具的漏洞挖掘效果,但已發(fā)現(xiàn)邊的價(jià)值是有差異的.因此,所提出模糊測(cè)試評(píng)估體系通過(guò)低頻邊比例來(lái)評(píng)價(jià)所發(fā)現(xiàn)邊的價(jià)值.低頻邊比例指標(biāo)指,對(duì)于一個(gè)測(cè)試程序所發(fā)現(xiàn)的邊中,訪問(wèn)概率低的邊占所發(fā)現(xiàn)邊總數(shù)的比例.在模糊測(cè)試相關(guān)研究中,很多論文強(qiáng)調(diào)了低頻分支的重要性[12-14,40,55].模糊測(cè)試工具變異生成的樣本往往傾向于多次遍歷少量高頻邊,而程序中大量的邊很少被訪問(wèn).因此,模糊測(cè)試工具訪問(wèn)的邊中低頻邊比例越高,其價(jià)值也相對(duì)較高,低頻邊比例為評(píng)估體系的第3 個(gè)指標(biāo).

(4)內(nèi)存操作指令數(shù)量

內(nèi)存操作指令數(shù)量同樣可用于評(píng)價(jià)發(fā)現(xiàn)邊的價(jià)值.一些模糊測(cè)試相關(guān)研究論文中指出,多數(shù)程序漏洞為錯(cuò)誤的內(nèi)存訪問(wèn)操作所引起,如內(nèi)存越界讀寫[7,47,49].目標(biāo)程序中的內(nèi)存訪問(wèn)操作指令越多,可能隱含的漏洞則越多.因此,統(tǒng)計(jì)模糊測(cè)試工具訪問(wèn)的基本塊中所包含的內(nèi)存操作指令數(shù)量,并將其作為模糊測(cè)試評(píng)估系統(tǒng)的第4 個(gè)指標(biāo).

4.3 綜合評(píng)估結(jié)果計(jì)算

為得到多個(gè)模糊測(cè)試改進(jìn)工具的效果評(píng)價(jià)比較結(jié)果,在統(tǒng)計(jì)得到多個(gè)指標(biāo)的數(shù)據(jù)結(jié)果后,根據(jù)優(yōu)序圖算法[56]計(jì)算得到不同指標(biāo)的權(quán)重,通過(guò)technique for order preference by similarity to ideal solution (TOPSIS)[57]算法計(jì)算每個(gè)模糊測(cè)試工具的效果分?jǐn)?shù),并對(duì)分?jǐn)?shù)排序得到效果比較結(jié)果.TOPSIS 算法常用于解決多指標(biāo)評(píng)價(jià)問(wèn)題,相較于類似算法,如灰色關(guān)聯(lián)度分析或模糊綜合評(píng)價(jià)模型,TOPSIS 算法更適用于指標(biāo)數(shù)據(jù)完整準(zhǔn)確評(píng)價(jià)排序問(wèn)題,因此選擇TOPSIS 算法作為模糊測(cè)試效果評(píng)估的主要算法.該模糊測(cè)試改進(jìn)評(píng)估體系具體包括以下步驟.

(1)對(duì)評(píng)估指標(biāo)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理.由于所提出的4 個(gè)評(píng)估指標(biāo)數(shù)量單位不同,需要通過(guò)標(biāo)準(zhǔn)化處理轉(zhuǎn)換為無(wú)量綱數(shù)據(jù)進(jìn)一步用于評(píng)估結(jié)果計(jì)算.數(shù)據(jù)標(biāo)準(zhǔn)化處理公式如下:

其中,rij表示第i個(gè)指標(biāo)第j項(xiàng)數(shù)據(jù)標(biāo)準(zhǔn)化后的數(shù)值,xij表示第i個(gè)指標(biāo)第j項(xiàng)數(shù)據(jù)的初始數(shù)值,m表示每項(xiàng)指標(biāo)的數(shù)據(jù)總數(shù).

(2)通過(guò)優(yōu)序圖算法計(jì)算各項(xiàng)指標(biāo)的不同權(quán)重.由于邊覆蓋數(shù)量指標(biāo)被廣泛應(yīng)用于模糊測(cè)試改進(jìn)評(píng)估中,且和崩潰數(shù)量等指標(biāo)相比具有較高穩(wěn)定性,因此將該4 項(xiàng)指標(biāo)的權(quán)重規(guī)定為2:1:1:1,計(jì)算得到各項(xiàng)指標(biāo)權(quán)重如下:

其中,w1-w11表示11 個(gè)測(cè)試程序的發(fā)現(xiàn)邊數(shù)量指標(biāo),w12-w44則表示剩余指標(biāo),該權(quán)重?cái)?shù)據(jù)由優(yōu)序圖算法計(jì)算所得.

根據(jù)指標(biāo)權(quán)重及標(biāo)準(zhǔn)化數(shù)據(jù)計(jì)算得到該指標(biāo)的數(shù)據(jù)結(jié)果,公式如式(3):

(3)計(jì)算理想解和負(fù)理想解.TOPSIS 算法中的理想解和負(fù)理想解分別代表最優(yōu)及最差的解決方案.此處最優(yōu)解決方案和最差解決方案分別指,存在最理想的模糊測(cè)試算法,其測(cè)試數(shù)據(jù)在各項(xiàng)指標(biāo)上均取得最高和最低分?jǐn)?shù),公式如下:

其中,A+和A-表示正負(fù)理想解,v+i和v-i表示第i項(xiàng)指標(biāo)權(quán)重標(biāo)準(zhǔn)化的最優(yōu)值和最差值.

(4)計(jì)算每一個(gè)候選項(xiàng),即模糊測(cè)試改進(jìn)工具的數(shù)據(jù)與正負(fù)理想解之間的距離,計(jì)算公式如下:

(5)計(jì)算模糊測(cè)試改進(jìn)工具數(shù)據(jù)距離理想解的貼近程度,貼近程度越大則該模糊測(cè)試改進(jìn)工具評(píng)價(jià)效果越好,計(jì)算公式如下:

(6)根據(jù)距離理想解貼近程度,計(jì)算待評(píng)估的模糊測(cè)試改進(jìn)工具效果評(píng)分并進(jìn)行排名,得到整體上各改進(jìn)工具改進(jìn)效果評(píng)估比較結(jié)果.

5 評(píng)估實(shí)驗(yàn)設(shè)置

在建立了模糊測(cè)試改進(jìn)技術(shù)評(píng)估體系后,將在該體系基礎(chǔ)上對(duì)單一模糊測(cè)試改進(jìn)技術(shù)進(jìn)行評(píng)估與分析.本章首先對(duì)模糊測(cè)試改進(jìn)技術(shù)評(píng)估實(shí)驗(yàn)的基準(zhǔn)模糊測(cè)試工具、待評(píng)估單一改進(jìn)技術(shù)、測(cè)試程序等相關(guān)細(xì)節(jié)進(jìn)行說(shuō)明,然后介紹待評(píng)估單一模糊測(cè)試改進(jìn)算法.

5.1 基準(zhǔn)模糊測(cè)試工具

在單一模糊測(cè)試改進(jìn)技術(shù)評(píng)估實(shí)驗(yàn)中,選擇AFL 2.52b 作為基準(zhǔn)模糊測(cè)試工具,所有的單一改進(jìn)將均在AFL 2.52b 基礎(chǔ)上進(jìn)行實(shí)現(xiàn).如第3.2 節(jié)中所述,AFL自2015年提出以來(lái)一直受到廣泛關(guān)注,多數(shù)模糊測(cè)試改進(jìn)工作選擇基于AFL 改進(jìn)實(shí)現(xiàn),幾乎所有改進(jìn)工具都將AFL 作為評(píng)估對(duì)比工具.在AFL 基礎(chǔ)上實(shí)現(xiàn)的模糊測(cè)試改進(jìn)工具和算法涵蓋了所有的改進(jìn)類別.因此,在本課題的模糊測(cè)試改進(jìn)技術(shù)評(píng)估中,選擇AFL 最新穩(wěn)定版本AFL 2.52b 作為基準(zhǔn)模糊測(cè)試工具.

5.2 待評(píng)估單一改進(jìn)技術(shù)

為了保證模糊測(cè)試改進(jìn)技術(shù)評(píng)估的準(zhǔn)確性和客觀性,選擇的待評(píng)估單一模糊測(cè)試改進(jìn)技術(shù)需要滿足以下條件:

(1)由于選擇AFL 作為基準(zhǔn)模糊測(cè)試工具,算法的原始模糊測(cè)試改進(jìn)工具需基于AFL 實(shí)現(xiàn);

(2)算法的原始改進(jìn)模糊測(cè)試工具需開源;

(3)算法需基于常見的傳統(tǒng)模糊測(cè)試進(jìn)行優(yōu)化,一些針對(duì)性的改進(jìn)如定向模糊測(cè)試改進(jìn)或內(nèi)核模糊測(cè)試改進(jìn)不在本次課題進(jìn)行評(píng)估.

基于以上標(biāo)準(zhǔn),在第3.2 節(jié)中所述46 個(gè)近年所提出的模糊測(cè)試改進(jìn)工具中,選擇了來(lái)自5 個(gè)工具的8 個(gè)單一改進(jìn)算法,分別屬于3 種不同改進(jìn)類別,改進(jìn)算法的具體信息如表1 所示.其中,*-seed、* -mutation和*-power 分別表示模糊測(cè)試工具*的種子選取、變異和能量分配改進(jìn)技術(shù).

表1 待評(píng)估模糊測(cè)試單一改進(jìn)技術(shù)說(shuō)明

5.3 測(cè)試程序

在本次評(píng)估中,共選擇了11 個(gè)測(cè)試程序,包括tcpdump -nr,xmllint,readpng,mutool show,mpg321--stdout,nm,objdump -d,readelf -a,c++filt,size,catdoc,具體程序信息如表2 所示.所選擇的測(cè)試程序均在第3.2 節(jié)中所述的46 個(gè)模糊測(cè)試改進(jìn)工作中被廣泛應(yīng)用于效果評(píng)估,且這些程序的輸入格式涵蓋了近年模糊測(cè)試改進(jìn)評(píng)估中的幾乎所有格式,因此將這些程序作為評(píng)估的測(cè)試程序,并選擇AFL 所提供的種子文件作為初始種子.

表2 模糊測(cè)試改進(jìn)技術(shù)評(píng)估所使用測(cè)試程序

5.4 單一模糊測(cè)試改進(jìn)算法

為了評(píng)估所選擇的8 個(gè)單一模糊測(cè)試改進(jìn)技術(shù)效果,在選擇的基準(zhǔn)模糊測(cè)試工具AFL 基礎(chǔ)上根據(jù)原論文中設(shè)計(jì)的算法實(shí)現(xiàn)相應(yīng)的8 個(gè)模糊測(cè)試工具.首先根據(jù)原有模糊測(cè)試改進(jìn)工作論文的算法描述,深入分析相應(yīng)工具的單一改進(jìn)算法實(shí)現(xiàn),按照表1 所述的單一改進(jìn)算法劃分,將原有工具的代碼實(shí)現(xiàn)進(jìn)行拆分,基于AFL 形成新的單一模糊測(cè)試改進(jìn)工具,通過(guò)所建立的模糊測(cè)試評(píng)估體系進(jìn)行系統(tǒng)性評(píng)估,從而得到單一改進(jìn)算法的效果評(píng)估.

5.5 其他實(shí)驗(yàn)條件

本次實(shí)驗(yàn)在Intel(R)Xeon(R)E5-2450 2.10 GHz,4 核,64 位Ubuntu 16.04 系統(tǒng)的計(jì)算機(jī)上進(jìn)行測(cè)試,測(cè)試時(shí)間設(shè)定為72 h,單個(gè)實(shí)驗(yàn)重復(fù)10 次取平均值作為實(shí)驗(yàn)結(jié)果.參考原有論文,BanditAFL 改進(jìn)算法在測(cè)試中的訓(xùn)練時(shí)間選擇為4 h.

6 單一改進(jìn)技術(shù)評(píng)估結(jié)果與分析

在實(shí)現(xiàn)模糊測(cè)試改進(jìn)技術(shù)評(píng)估體系建立及實(shí)驗(yàn)設(shè)置后,我們對(duì)各改進(jìn)類別內(nèi)的不同單一改進(jìn)技術(shù)進(jìn)行測(cè)試評(píng)估與分析.本節(jié)將分別介紹3 個(gè)類別改進(jìn)算法的評(píng)估結(jié)果與原因分析.

6.1 種子選取策略改進(jìn)

在我們選取的單一模糊測(cè)試改進(jìn)算法中,AFLFastseed、FairFuzz-seed 和EcoFuzz-seed 屬于種子選取策略的改進(jìn)算法.實(shí)驗(yàn)結(jié)果如圖6 所示.其中,柱狀圖數(shù)據(jù)條上方標(biāo)注數(shù)字與高度分別代表該指標(biāo)標(biāo)準(zhǔn)化前后的值,圖7、圖8 數(shù)據(jù)表示方法相同.從直觀上看,EcoFuzz-seed 相較于其他兩個(gè)單一改進(jìn)算法效果較差.我們基于模糊測(cè)試改進(jìn)技術(shù)評(píng)估體系對(duì)3 個(gè)單一改進(jìn)工具計(jì)算了綜合分?jǐn)?shù),結(jié)果如表3 所示.在3 個(gè)算法中,FairFuzz-seed 效果最好,AFLFast-seed 次之,最后是EcoFuzz-seed,與數(shù)據(jù)觀察結(jié)果一致.

表3 3 種模糊測(cè)試改進(jìn)技術(shù)的評(píng)估分?jǐn)?shù)與排名

圖6 AFLFast-seed,FairFuzz-seed 與EcoFuzz-seed 在評(píng)估體系4 個(gè)指標(biāo)測(cè)試數(shù)據(jù)

AFLFast 和FairFuzz 的種子選取策略核心思想相似,即優(yōu)先選擇遍歷更多低頻分支的種子,AFLFastseed 和FairFuzz-seed 在評(píng)估中效果突出可以反映這種思想的有效性.EcoFuzz 的策略和AFLFast、FairFuzz相比具有較大差別.由EcoFuzz 的種子選取策略算法可知,EcoFuzz-seed 傾向于選擇具有更低自轉(zhuǎn)移頻率和隊(duì)列中更大編號(hào)的種子,自轉(zhuǎn)移頻率在其論文中定義為,種子在變異后仍然覆蓋相同路徑的概率.然而,由一個(gè)種子變異生成的樣本可能雖然和種子覆蓋的原路徑不同,但仍然覆蓋了其他種子生成的樣本中覆蓋的高頻路徑.因此,由此策略選擇的種子生成的樣本可能包含其他樣本覆蓋的高頻路徑,但仍被優(yōu)先選擇進(jìn)行變異,此時(shí)選擇的種子可能并不能帶來(lái)更高效的模糊測(cè)試效果.

6.2 變異策略改進(jìn)

在選擇的5 個(gè)模糊測(cè)試工具中,FairFuzz 和MOPT均提出了不同的變異策略優(yōu)化算法,期望在對(duì)種子進(jìn)行變異的過(guò)程中選擇更有效的變異位置和變異操作,實(shí)現(xiàn)更高效的模糊測(cè)試.我們將實(shí)現(xiàn)的單一模糊測(cè)試改進(jìn)算法FairFuzz-mutation 和MOPT-mutation 在模糊測(cè)試改進(jìn)技術(shù)評(píng)估體系中進(jìn)行實(shí)驗(yàn)和評(píng)估,實(shí)驗(yàn)結(jié)果如圖7 所示.綜合上,FairFuzz-mutation 和MOPTmutation 的模糊測(cè)試效果相似,在一些測(cè)試程序上,如mpg321,readpng,size,xmllint,FairFuzz-mutation 效果更好,而在其他一些程序上,如c++filt,mutool,nm,objdump,readelf,MOPT-mutation 具有更好效果.在評(píng)估體系中計(jì)算得到的綜合評(píng)分如表4 所示.從評(píng)估數(shù)據(jù)上看,MOPT-mutation 在綜合效果上略優(yōu)于FairFuzz-mutation.

表4 FairFuzz-mutation 與MOPT-mutation 評(píng)估分?jǐn)?shù)與排名

圖7 FairFuzz-mutation 與MOPT-mutation 在評(píng)估體系4 個(gè)指標(biāo)測(cè)試數(shù)據(jù)

雖然FairFuzz-mutation 和MOPT-mutation 的綜合模糊測(cè)試效果相似,但兩者的改進(jìn)策略具有很大不同.FairFuzz-mutation 關(guān)注樣本中覆蓋的低頻邊,在確定性變異階段維護(hù)branch_mask 數(shù)組記錄低頻邊訪問(wèn)情況,在非確定性變異階段只進(jìn)行當(dāng)前變異位置中仍能覆蓋到低頻邊的變異操作.而MOPT-mutation 則主要通過(guò)粒子群算法選擇當(dāng)前最優(yōu)的變異操作.通過(guò)數(shù)據(jù)分析可知,MOPT-mutation 在11 個(gè)測(cè)試程序中的10 個(gè)程序具有更高的目標(biāo)程序執(zhí)行次數(shù),一定程度上能夠反映MOPT-mutation 的算法效率更高.雖然FairFuzzmutation 的低頻邊覆蓋策略在提高代碼覆蓋上效果良好,但由于其需要一直維護(hù)branch_mask 數(shù)組,帶來(lái)了相對(duì)較大的時(shí)間開銷,在綜合測(cè)試效果上略次于MOPTmutation.

6.3 能量分配策略改進(jìn)

AFLFast、BanditAFL 和EcoFuzz 均提出了能量分配算法以優(yōu)化為選定種子分配的變異次數(shù).測(cè)試結(jié)果如圖8 所示,整體上,BanditAFL-power 的改進(jìn)效果優(yōu)于其他兩個(gè)改進(jìn)算法,在11 個(gè)程序中的8 個(gè)程序上(mpg321,mutool,nm,objdump,readelf,readpng,size,xmllint),BanditAFL 在4 個(gè)指標(biāo)上的效果均優(yōu)于或等于其他兩個(gè)改進(jìn)算法.在模糊測(cè)試改進(jìn)技術(shù)評(píng)估體系上計(jì)算綜合評(píng)估分?jǐn)?shù)如表5 所示,BanditAFL-power 綜合效果最好,其次為EcoFuzz-power,最后是AFLFastpower.

表5 3 種模糊測(cè)試改進(jìn)技術(shù)的評(píng)估分?jǐn)?shù)與排名

圖8 AFLFast-power,BanditAFL-power 與EcoFuzz-power 在評(píng)估體系4 個(gè)指標(biāo)測(cè)試數(shù)據(jù)

BanditAFL-power 采用LSTM 算法,根據(jù)不同種子的內(nèi)容優(yōu)化當(dāng)前應(yīng)分配的最優(yōu)變異次數(shù),首先通過(guò)算法訓(xùn)練得到模型,在測(cè)試過(guò)程中通過(guò)讀取模型數(shù)據(jù)計(jì)算,得到能量分配結(jié)果.經(jīng)過(guò)數(shù)據(jù)分析可知,BanditAFL-power的執(zhí)行次數(shù)較低,雖然該算法具有較高的時(shí)間開銷,但由于根據(jù)模型計(jì)算得到的能量分配結(jié)果更加科學(xué)準(zhǔn)確,仍然具有高效的執(zhí)行結(jié)果,也在一定程度上反映了將時(shí)間開銷較大的機(jī)器學(xué)習(xí)等算法應(yīng)用于模糊測(cè)試的可行性.

值得注意的是,雖然能量分配策略是AFLFast 原論文中全篇著重介紹的算法,但其單一改進(jìn)算法AFLFastpower 在3 個(gè)能量分配改進(jìn)算法中效果相對(duì)最差,我們對(duì)這一現(xiàn)象進(jìn)行了進(jìn)一步分析.在實(shí)驗(yàn)中,我們應(yīng)用了AFLFast 原論文中認(rèn)為效果最好的FAST 能量分配策略,其能量分配計(jì)算公式計(jì)算如下:

其中,p(i)表示為當(dāng)前遍歷路徑i的種子分配的能量,α(i)表示原AFL 計(jì)算的能量分配結(jié)果,β為常數(shù),取β ＞1,s(i)表示當(dāng)前種子被選擇的次數(shù),f(i)表示當(dāng)前路徑被執(zhí)行的次數(shù),M為常數(shù),即能量分配最大值.

AFLFast-power 傾向于為種子選取次數(shù)更少、路徑執(zhí)行次數(shù)更少的種子分配更多能量.基于馬爾科夫鏈算法,AFLFast 能夠在更短時(shí)間內(nèi)得到高頻路徑集合,從而提高模糊測(cè)試效率.然而,在不結(jié)合AFLFastseed,即AFLFast 的種子選取策略時(shí),新生成的種子位于種子隊(duì)列靠后的位置,而模糊測(cè)試工具仍然按照隊(duì)列順序選擇種子,根據(jù)式(7),一些多次選擇的種子仍會(huì)被分配到較高的變異次數(shù),無(wú)法在較短時(shí)間內(nèi)快速搜索路徑狀態(tài),而浪費(fèi)了較多時(shí)間.

7 相關(guān)工作

一些文章對(duì)所提出的模糊測(cè)試技術(shù)進(jìn)行了總結(jié)或評(píng)估.Li 等人[1]對(duì)模糊測(cè)試中涉及到的不同的技術(shù)問(wèn)題的針對(duì)性解決方法進(jìn)行了整理和總結(jié).Manes 等人[9]根據(jù)模糊測(cè)試的不同測(cè)試階段整理了各階段所提出的模糊測(cè)試改進(jìn)方案.Liang 等人[7]總結(jié)了針對(duì)不同應(yīng)用和不同問(wèn)題所提出的優(yōu)化模糊測(cè)試工具.Klees 等人[58]總結(jié)并分析了近年來(lái)所提出的模糊測(cè)試工作中用到的模糊測(cè)試評(píng)估方法,并提出了模糊測(cè)試效果評(píng)估應(yīng)達(dá)到的一些標(biāo)準(zhǔn).Li 等人[59]設(shè)計(jì)實(shí)現(xiàn)了一個(gè)模糊測(cè)試評(píng)估系統(tǒng)UniFuzz,并對(duì)流行的模糊測(cè)試工具效果進(jìn)行了評(píng)估.Metzman 等人[10]基于提出的指標(biāo)建立了線上模糊測(cè)試工具評(píng)估平臺(tái)FuzzBench.然而,當(dāng)前仍沒有工作對(duì)模糊測(cè)試的單一改進(jìn)技術(shù)進(jìn)行系統(tǒng)量化的評(píng)估與分析.

TOPSIS 算法[57]為Hwang 等人于1981年首次提出的多指標(biāo)綜合評(píng)價(jià)方法,其基本思想為在原始數(shù)據(jù)標(biāo)準(zhǔn)化處理后,找到理想最優(yōu)最劣方案,計(jì)算每個(gè)候選項(xiàng)到最優(yōu)最劣方案的相對(duì)接近程度,從而得到候選項(xiàng)間的綜合評(píng)價(jià)結(jié)果.TOPSIS 算法自提出以來(lái),已在工業(yè)與制造業(yè)、人力資源管理、商業(yè)與市場(chǎng)分析、醫(yī)學(xué)等多個(gè)領(lǐng)域應(yīng)用于多指標(biāo)綜合評(píng)估[57],具有客觀性和有效性.

8 結(jié)論與展望

本文針對(duì)單一模糊測(cè)試改進(jìn)技術(shù)評(píng)估分析的問(wèn)題,基于理論分析與實(shí)際經(jīng)驗(yàn)提出了4 個(gè)評(píng)估指標(biāo),建立了客觀量化改進(jìn)技術(shù)評(píng)估體系.對(duì)近年中模糊測(cè)試改進(jìn)技術(shù)進(jìn)行了整體總結(jié)與分析,從中選擇了5 個(gè)先進(jìn)模糊測(cè)試工具中的8 個(gè)單一改進(jìn)算法,將這些改進(jìn)算法分為3 類,在所建立的評(píng)估體系中進(jìn)行了實(shí)驗(yàn)評(píng)估,將同一改進(jìn)類別中的不同改進(jìn)技術(shù)進(jìn)行對(duì)比.我們對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了展示與說(shuō)明,并結(jié)合測(cè)試數(shù)據(jù)與實(shí)際算法設(shè)計(jì)實(shí)現(xiàn)進(jìn)行了深入的原因分析.實(shí)驗(yàn)結(jié)果表明:

(1)在種子選取策略改進(jìn)算法中,由于其采用的低頻路徑、低頻邊優(yōu)先改進(jìn)思想準(zhǔn)確有效,AFLFast 和FairFuzz 具有更好的改進(jìn)效果;

(2)在變異策略改進(jìn)算法中,MOPT 與FairFuzz 采用不同改進(jìn)方案,具有相似改進(jìn)效果,MOPT 具有更高算法效率和更快執(zhí)行速度;

(3)在能量分配策略改進(jìn)算法中,采用LSTM 算法的BanditAFL 算法改進(jìn)效果更好,AFLFast 由于算法間存在依賴關(guān)系導(dǎo)致單一能量分配算法無(wú)法實(shí)現(xiàn)應(yīng)有的效果提升.

在未來(lái)的研究工作中,我們希望繼續(xù)探究更多模糊測(cè)試改進(jìn)技術(shù)相關(guān)問(wèn)題,如不同類別的改進(jìn)算法間效果有何差異,如何組合單一改進(jìn)算法得到效果最好的模糊測(cè)試工具,同時(shí)通過(guò)總結(jié)分析對(duì)未來(lái)的模糊測(cè)試改進(jìn)工作提出一些參考意見與建議.