模糊測試改進技術評估①

張 陽,佟思明,程 亮,孫曉山

1(中國科學院大學,北京 100049)

2(中國科學院 軟件研究所 可信計算與信息保障實驗室,北京 100190)

1 緒論

近年來,利用軟件漏洞實施安全攻擊的行為層出不窮,如何更好地保證軟件質量和安全,減少軟件及系統漏洞,成為當前安全領域一個重要的研究方向.

模糊測試[1]是一種動態軟件漏洞挖掘技術,能夠有效檢測軟件或計算機系統中的安全漏洞.其核心思想是將變異生成的隨機數據輸入待測試程序中,監視程序運行情況,當發現程序出現崩潰或其他異常情況時保存數據,從而找到程序漏洞.相比于其他軟件安全檢測技術,如代碼審計[2]、污點分析[3]、符號執行[4]等,模糊測試技術具有自動化程度高,時間開銷小,應用范圍廣的優點,模糊測試作為一種高效的漏洞挖掘技術在近些年得到了學術界及工業界的廣泛關注和應用.

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

2 研究背景

本節首先介紹模糊測試技術的基本分類,說明基于變異的灰盒模糊測試工具工作流程,然后介紹經典基于變異的灰盒模糊測試工具American Fuzzy Lop (AFL)[5].

2.1 模糊測試技術分類

當前模糊測試技術方法根據樣本生成方法可以分為基于變異的模糊測試以及基于生成的模糊測試兩類[6].

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

基于變異的模糊測試通過改變已有的數據樣本去生成測試數據.對于種子樣本,模糊測試工具通過對該樣本進行位翻轉、數學加減、插入刪除、拼接等操作,得到新的種子,遍歷更多的程序執行路徑,以達到更高的代碼覆蓋,從而發現更多程序中可能存在的漏洞.

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

基于生成的模糊測試則主要應用于針對協議、JS引擎等以高度結構化格式文件為輸入的目標程序,由于這些程序中存在大量的格式檢查,輸入文件的不同字段具有一定的語法語義,隨機的變異往往無法滿足要求,因此需要通過一定的規則和算法生成輸入文件.

根據對待測試程序內部結構的認知程度,模糊測試可以分為白盒模糊測試、黑盒模糊測試以及灰盒模糊測試3 類[6].

(1)黑盒模糊測試

黑盒模糊測試不考慮待測試程序的內部邏輯,持續生成隨機樣本輸入程序,觀察待測試程序的執行情況.

(2)白盒模糊測試

白盒模糊測試指在獲取到待測試程序的內部實現信息,如源代碼、設計細節以及運行時信息等之后,利用已有信息針對性地對程序進行測試的方法.

(3)灰盒模糊測試

灰盒模糊測試介于黑盒模糊測試和白盒模糊測試之間,通過獲取一些待測試程序的信息,如運行時分支覆蓋來指導模糊測試從而提高測試效率.常見灰盒模糊測試工具通過輕量級代碼插樁等方法獲取所需信息.

基于變異的灰盒模糊測試具有應用范圍廣、執行效率高的特點,受到了相關學者的廣泛關注,近年提出的模糊測試工作多數基于此類型,因此本文主要針對基于變異的灰盒模糊測試改進技術進行評估與分析.

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

多數基于變異的灰盒模糊測試工具工作流程如圖1所示,首先從初始種子隊列中選取合適的輸入,然后,模糊測試工具重復地對這些輸入進行變異并執行待測試程序.如果程序運行中出現了異常行為,則模糊測試工具保留變異的輸入以便將來使用,并記錄觀察到的具體信息.最終,由于達到特定目標,如發現某種漏洞,或用戶主動停止,模糊測試結束.

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

2.3 American Fuzzy Lop (AFL)

AFL[5]由Google 的Michal Zalewski 所開發,是當前最流行的模糊測試工具之一.

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

圖2 AFL 工作流程圖

AFL 作為經典的基于變異的灰盒模糊測試工具,設計結構完整,算法準確高效,可擴展性強,近年來很多模糊測試改進工作選擇基于AFL 實現[7-11],因此本文選擇AFL 作為基準模糊測試工具進行改進技術的評估與分析.

3 模糊測試改進技術總結

本節首先介紹對模糊測試改進技術的分類以及相應類別中近年提出的先進改進技術,然后對這些單一改進技術進行整理總結與分析,如圖3 所示.

3.1 模糊測試改進技術分類與介紹

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

(1)種子選取策略改進技術

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

(2)變異策略改進技術

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

(3)能量分配策略改進技術

能量分配指,在非確定性變異階段對選定種子選擇隨機變異次數的過程.能量分配策略改進技術通過對種子的價值進行評估,優化對不同種子選擇的變異次數,對更有可能生成更多有價值樣本的種子賦予更多的變異次數.AFLFast[12]基于馬爾科夫鏈提出了5 種不同的能量分配策略,根據種子的被選擇的次數以及訪問路徑被訪問的次數計算分配的變異次數; BanditAFL[18]將能量分配問題看作多臂老虎機問題,通過強化學習計算最優的能量分配策略; EcoFuzz[14]首先計算發現新路徑平均所需的變異次數,并根據當前種子路徑被訪問的次數以及上一個種子發現新路徑的變異次數進行調整.

(4)其他方面改進技術

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

3.2 模糊測試改進技術總結與分析

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

圖3 模糊測試改進技術分類整理

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

此外,在46 個模糊測試改進工具中,65.22% (30/46)的工具基于AFL 改進實現,且幾乎所有工具將AFL 作為對照工具進行相應改進技術的評估,AFL 在當前的模糊測試改進工作中至今仍處于非常重要的地位.

4 評估體系建立

為了系統量化地評估單一模糊測試改進技術,本文建立了單一模糊測試改進技術評估體系.本節首先對評估體系設計進行整體介紹,然后說明評估體系指標選取,最后對說明綜合評估結果的計算模型.

4.1 評估體系概述

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

圖4 模糊測試評估體系架構圖

4.2 評估體系指標選取

根據近期國內外模糊測試改進工作的整理,結合對模糊測試改進效果影響因素的分析,選取了4 個用于評估的指標,即測試程序邊覆蓋率、去重后崩潰樣本數量、覆蓋低頻邊所占比例以及覆蓋測試程序內存操作指令的數量.

(1)邊覆蓋數量

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

(2)去重崩潰樣本數量

在模糊測試中,程序由于異常輸入所導致的崩潰,很可能是因為觸發了程序中潛在的漏洞,當程序在執行過程中發生崩潰,AFL 會首先檢查此前的崩潰輸入中是否有與當前輸入的分支覆蓋完全相同的輸入樣本,若沒有則保存.通常情況下,崩潰樣本越多,可能存在的漏洞數量則越多.然而,AFL 所收集的崩潰樣本可能

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

圖5 觸發漏洞示例程序代碼片段

(3)低頻邊比例

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

(4)內存操作指令數量

內存操作指令數量同樣可用于評價發現邊的價值.一些模糊測試相關研究論文中指出,多數程序漏洞為錯誤的內存訪問操作所引起,如內存越界讀寫[7,47,49].目標程序中的內存訪問操作指令越多,可能隱含的漏洞則越多.因此,統計模糊測試工具訪問的基本塊中所包含的內存操作指令數量,并將其作為模糊測試評估系統的第4 個指標.

4.3 綜合評估結果計算

為得到多個模糊測試改進工具的效果評價比較結果,在統計得到多個指標的數據結果后,根據優序圖算法[56]計算得到不同指標的權重,通過technique for order preference by similarity to ideal solution (TOPSIS)[57]算法計算每個模糊測試工具的效果分數,并對分數排序得到效果比較結果.TOPSIS 算法常用于解決多指標評價問題,相較于類似算法,如灰色關聯度分析或模糊綜合評價模型,TOPSIS 算法更適用于指標數據完整準確評價排序問題,因此選擇TOPSIS 算法作為模糊測試效果評估的主要算法.該模糊測試改進評估體系具體包括以下步驟.

(1)對評估指標數據進行標準化處理.由于所提出的4 個評估指標數量單位不同,需要通過標準化處理轉換為無量綱數據進一步用于評估結果計算.數據標準化處理公式如下:

其中,rij表示第i個指標第j項數據標準化后的數值,xij表示第i個指標第j項數據的初始數值,m表示每項指標的數據總數.

(2)通過優序圖算法計算各項指標的不同權重.由于邊覆蓋數量指標被廣泛應用于模糊測試改進評估中,且和崩潰數量等指標相比具有較高穩定性,因此將該4 項指標的權重規定為2:1:1:1,計算得到各項指標權重如下:

其中,w1-w11表示11 個測試程序的發現邊數量指標,w12-w44則表示剩余指標,該權重數據由優序圖算法計算所得.

根據指標權重及標準化數據計算得到該指標的數據結果,公式如式(3):

(3)計算理想解和負理想解.TOPSIS 算法中的理想解和負理想解分別代表最優及最差的解決方案.此處最優解決方案和最差解決方案分別指,存在最理想的模糊測試算法,其測試數據在各項指標上均取得最高和最低分數,公式如下:

其中,A+和A-表示正負理想解,v+i和v-i表示第i項指標權重標準化的最優值和最差值.

(4)計算每一個候選項,即模糊測試改進工具的數據與正負理想解之間的距離,計算公式如下:

(5)計算模糊測試改進工具數據距離理想解的貼近程度,貼近程度越大則該模糊測試改進工具評價效果越好,計算公式如下:

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

5 評估實驗設置

在建立了模糊測試改進技術評估體系后,將在該體系基礎上對單一模糊測試改進技術進行評估與分析.本章首先對模糊測試改進技術評估實驗的基準模糊測試工具、待評估單一改進技術、測試程序等相關細節進行說明,然后介紹待評估單一模糊測試改進算法.

5.1 基準模糊測試工具

在單一模糊測試改進技術評估實驗中,選擇AFL 2.52b 作為基準模糊測試工具,所有的單一改進將均在AFL 2.52b 基礎上進行實現.如第3.2 節中所述,AFL自2015年提出以來一直受到廣泛關注,多數模糊測試改進工作選擇基于AFL 改進實現,幾乎所有改進工具都將AFL 作為評估對比工具.在AFL 基礎上實現的模糊測試改進工具和算法涵蓋了所有的改進類別.因此,在本課題的模糊測試改進技術評估中,選擇AFL 最新穩定版本AFL 2.52b 作為基準模糊測試工具.

5.2 待評估單一改進技術

為了保證模糊測試改進技術評估的準確性和客觀性,選擇的待評估單一模糊測試改進技術需要滿足以下條件:

(1)由于選擇AFL 作為基準模糊測試工具,算法的原始模糊測試改進工具需基于AFL 實現;

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

(3)算法需基于常見的傳統模糊測試進行優化,一些針對性的改進如定向模糊測試改進或內核模糊測試改進不在本次課題進行評估.

基于以上標準,在第3.2 節中所述46 個近年所提出的模糊測試改進工具中,選擇了來自5 個工具的8 個單一改進算法,分別屬于3 種不同改進類別,改進算法的具體信息如表1 所示.其中,*-seed、* -mutation和*-power 分別表示模糊測試工具*的種子選取、變異和能量分配改進技術.

表1 待評估模糊測試單一改進技術說明

5.3 測試程序

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

表2 模糊測試改進技術評估所使用測試程序

5.4 單一模糊測試改進算法

為了評估所選擇的8 個單一模糊測試改進技術效果,在選擇的基準模糊測試工具AFL 基礎上根據原論文中設計的算法實現相應的8 個模糊測試工具.首先根據原有模糊測試改進工作論文的算法描述,深入分析相應工具的單一改進算法實現,按照表1 所述的單一改進算法劃分,將原有工具的代碼實現進行拆分,基于AFL 形成新的單一模糊測試改進工具,通過所建立的模糊測試評估體系進行系統性評估,從而得到單一改進算法的效果評估.

5.5 其他實驗條件

本次實驗在Intel(R)Xeon(R)E5-2450 2.10 GHz,4 核,64 位Ubuntu 16.04 系統的計算機上進行測試,測試時間設定為72 h,單個實驗重復10 次取平均值作為實驗結果.參考原有論文,BanditAFL 改進算法在測試中的訓練時間選擇為4 h.

6 單一改進技術評估結果與分析

在實現模糊測試改進技術評估體系建立及實驗設置后,我們對各改進類別內的不同單一改進技術進行測試評估與分析.本節將分別介紹3 個類別改進算法的評估結果與原因分析.

6.1 種子選取策略改進

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

表3 3 種模糊測試改進技術的評估分數與排名

圖6 AFLFast-seed,FairFuzz-seed 與EcoFuzz-seed 在評估體系4 個指標測試數據

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

6.2 變異策略改進

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

表4 FairFuzz-mutation 與MOPT-mutation 評估分數與排名

圖7 FairFuzz-mutation 與MOPT-mutation 在評估體系4 個指標測試數據

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

6.3 能量分配策略改進

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

表5 3 種模糊測試改進技術的評估分數與排名

圖8 AFLFast-power,BanditAFL-power 與EcoFuzz-power 在評估體系4 個指標測試數據

BanditAFL-power 采用LSTM 算法,根據不同種子的內容優化當前應分配的最優變異次數,首先通過算法訓練得到模型,在測試過程中通過讀取模型數據計算,得到能量分配結果.經過數據分析可知,BanditAFL-power的執行次數較低,雖然該算法具有較高的時間開銷,但由于根據模型計算得到的能量分配結果更加科學準確,仍然具有高效的執行結果,也在一定程度上反映了將時間開銷較大的機器學習等算法應用于模糊測試的可行性.

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

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

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

7 相關工作

一些文章對所提出的模糊測試技術進行了總結或評估.Li 等人[1]對模糊測試中涉及到的不同的技術問題的針對性解決方法進行了整理和總結.Manes 等人[9]根據模糊測試的不同測試階段整理了各階段所提出的模糊測試改進方案.Liang 等人[7]總結了針對不同應用和不同問題所提出的優化模糊測試工具.Klees 等人[58]總結并分析了近年來所提出的模糊測試工作中用到的模糊測試評估方法,并提出了模糊測試效果評估應達到的一些標準.Li 等人[59]設計實現了一個模糊測試評估系統UniFuzz,并對流行的模糊測試工具效果進行了評估.Metzman 等人[10]基于提出的指標建立了線上模糊測試工具評估平臺FuzzBench.然而,當前仍沒有工作對模糊測試的單一改進技術進行系統量化的評估與分析.

TOPSIS 算法[57]為Hwang 等人于1981年首次提出的多指標綜合評價方法,其基本思想為在原始數據標準化處理后,找到理想最優最劣方案,計算每個候選項到最優最劣方案的相對接近程度,從而得到候選項間的綜合評價結果.TOPSIS 算法自提出以來,已在工業與制造業、人力資源管理、商業與市場分析、醫學等多個領域應用于多指標綜合評估[57],具有客觀性和有效性.

8 結論與展望

本文針對單一模糊測試改進技術評估分析的問題,基于理論分析與實際經驗提出了4 個評估指標,建立了客觀量化改進技術評估體系.對近年中模糊測試改進技術進行了整體總結與分析,從中選擇了5 個先進模糊測試工具中的8 個單一改進算法,將這些改進算法分為3 類,在所建立的評估體系中進行了實驗評估,將同一改進類別中的不同改進技術進行對比.我們對實驗結果進行了展示與說明,并結合測試數據與實際算法設計實現進行了深入的原因分析.實驗結果表明:

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

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

(3)在能量分配策略改進算法中,采用LSTM 算法的BanditAFL 算法改進效果更好,AFLFast 由于算法間存在依賴關系導致單一能量分配算法無法實現應有的效果提升.

在未來的研究工作中,我們希望繼續探究更多模糊測試改進技術相關問題,如不同類別的改進算法間效果有何差異,如何組合單一改進算法得到效果最好的模糊測試工具,同時通過總結分析對未來的模糊測試改進工作提出一些參考意見與建議.