李明磊，陸余良，黃 暉，朱凱龍

（國防科技大學電子對抗學院，合肥 230037）

0 概述

隨著社會信息化程度的不斷提高，網絡空間安全成為國家安全的重中之重。在威脅網絡空間安全的眾多因素中，漏洞是最根本的原因。模糊測試技術是目前最有效的漏洞檢測技術之一，其為被測程序提供多種輸入并監(jiān)測被測程序的多種異常行為，如堆?；蚓彌_區(qū)溢出、內存泄漏等［1-2］。安全人員通過對程序異常行為進行分析，從而實現(xiàn)對軟件漏洞位置定位。

1988 年，MILLER 等人提出模糊測試的概念［3］，經過三十多年的發(fā)展，已經形成包括白盒模糊測試、灰盒模糊測試、黑盒模糊測試在內的三類模糊測試技術。白盒模糊測試技術基于程序源代碼進行分析，能夠根據(jù)程序源碼提供更具有針對性的測試用例，但對程序的分析會引入大量的額外開銷［4］。與白盒測試相反，黑盒測試不對被測程序進行分析，而是僅提供持續(xù)不斷的輸入并對程序運行結果進行收集。這使得黑盒測試具有較好的時間效率，能夠在短時間內覆蓋程序的大量路徑，但不具有針對性的測試用例也使得黑盒測試難以覆蓋程序深處的路徑。灰盒模糊測試是一種結合黑盒與白盒測試特點的測試方法，模糊測試器在提供給程序大量測試用例的同時通過輕量級程序分析工具對程序運行狀態(tài)進行分析，并根據(jù)分析結果對測試用例進行修改。灰盒模糊測試能夠在保持黑盒模糊測試高效、擴展性好的基礎上獲得對程序關鍵結構信息分析的能力，使模糊測試技術更加智能［5］。

近年來，研究人員將污點分析［6］、符號執(zhí)行［7］以及靜態(tài)分析［8］等技術與灰盒模糊測試技術相結合，使得灰盒模糊測試技術在路徑覆蓋率、時間效率以及路徑覆蓋深度等方面取得突破。文獻［9］開發(fā)的模糊測試器TaintScope 使用了符號執(zhí)行與污點分析技術，自動標記輸入中的校驗和字段并求解出可以通過程序校驗和檢測的測試用例。文獻［10］開發(fā)的模糊測試器Dowser 使用污點分析技術計算種子文件各比特位之間的突變比例，提高種子文件變異效率。文獻［11］開發(fā)的模糊測試器BORG 使用靜態(tài)分析技術得到程序的控制流程圖，并利用該程序流程圖使用符號執(zhí)行技術生成可以到達程序高危漏洞的測試用例。文獻［12］開發(fā)的模糊測試器AflFast 使用馬爾科夫鏈模型對程序路徑狀態(tài)轉換概率進行建模，根據(jù)概率模型選擇覆蓋低概率路徑的種子進行變異，以提高新路徑的發(fā)現(xiàn)速度。文獻［13］開發(fā)的模糊測試器Skyfire 使用概率上下文相關語法從大量現(xiàn)有樣本中生成高質量樣本。文獻［14］開發(fā)的模糊測試器VUzzer 使用了靜態(tài)分析與動態(tài)污點分析技術，計算每個種子的適應度來提高模糊測試器路徑覆蓋的深度。

隨著程序規(guī)模的不斷增長，為提高模糊測試的效率，在進行模糊測試前，研究人員通常會對目標程序進行脆弱性分析等工作，選定程序中存在潛在問題的區(qū)域作為目標區(qū)域進行測試，如程序的補丁區(qū)域。但上述的模糊測試器是面向整個程序進行測試，被用于補丁測試、高危區(qū)域測試時缺乏導向性，會將大量時間和系統(tǒng)資源浪費在程序的無關區(qū)域。因此，文獻［15］提出導向式灰盒模糊測試技術，導向式灰盒模糊測試技術能夠快速生成到達程序目標區(qū)域的測試用例并發(fā)現(xiàn)漏洞［16］，其不需要重量級的符號執(zhí)行、程序分析和約束求解技術，而是先通過靜態(tài)分析計算出程序各基本塊到目標區(qū)域的距離，并通過插樁的方式將距離信息插入到目標程序中，在測試階段根據(jù)插樁信息計算每個種子距離目標區(qū)域的距離，使用啟發(fā)式算法提升距離目標區(qū)域近的種子生成測試用例的數(shù)量，保證了測試的高效性與導向性［17］。

本文對現(xiàn)有的導向式灰盒模糊測試方法進行分析，提出一種距離與權重相結合的導向式灰盒模糊測試方法，通過改進距離計算方法提高導向式灰盒模糊測試的準確性。

1 導向式灰盒模糊測試分析

本文以文獻［15］開發(fā)的導向式灰盒模糊測試器Aflgo 為例，對導向式灰盒模糊測試的基本工作流程進行介紹。導向式灰盒模糊測試器由靜態(tài)分析與灰盒測試兩部分組成，靜態(tài)分析部分僅在模糊測試開始前運行一次，整體架構如圖1 所示。

圖1 導向式模糊測試技術框架Fig.1 Framework of guided fuzzing test technology

導向式灰盒模糊測試流程如下：

1）在靜態(tài)分析階段，對目標程序進行靜態(tài)分析得到目標程序的函數(shù)調用流程圖和程序控制流程圖。

2）計算出程序每一個基本塊到目標區(qū)域的距離并通過插樁的方式將距離信息插入到程序中。

3）模糊測試階段，從種子集中選擇一個種子進行測試，收集該種子執(zhí)行軌跡并計算種子與目標區(qū)域的距離。

4）根據(jù)種子到目標區(qū)域的距離動態(tài)調控種子的能量，即種子變異產生的測試用例的數(shù)量。

5）如果變異生成的測試用例覆蓋到程序新的路徑，就將此測試用例加入種子集。

重復操作流程3）～流程5），當種子集中種子都被選擇過一遍時為一輪，一輪測試后從種子集第一個種子開始新一輪測試直到時間結束。

Aflgo 通過與Afl 及導向式符號執(zhí)行工具KATCH［16］進行對比實驗，證明了其導向的有效性，但依然存在以下3 個問題：

1）距離計算粒度粗糙，沒有仔細區(qū)分函數(shù)與基本塊對種子距離的影響，而是簡單地認為函數(shù)距離是基本塊距離的常數(shù)倍。

2）沒有對程序不同位置的基本塊進行區(qū)分，認為程序中基本塊的權重是相同的，降低了距離計算的精度。

3）種子能量調控策略以程序運行時間作為調控指標不夠準確。程序受運行環(huán)境影響較大，同一個程序在不同運行環(huán)境下運行相同的時間運行狀態(tài)有很大的差別。

為解決上述問題，本文提出一種更加精確有效的距離計算與能量調控方法，對圖1 中的基本塊距離計算與種子能量計算進行改進，以提高導向式模糊測試器的導向性。

2 本文方法

實現(xiàn)導向式灰盒模糊測試導向性的關鍵在于計算種子到目標區(qū)域的距離。通過上文的分析可以看出，目前限制距離計算準確性的主要原因有兩點：1）如何計算不同函數(shù)、不同基本塊對種子到目標區(qū)域距離的影響；2）如何用統(tǒng)一的量綱表示程序中函數(shù)和基本塊到目標區(qū)域的距離。本文通過對導向式灰盒模糊測試中的距離與能量計算方法進行改進，將不同函數(shù)與基本塊的差異考慮到距離計算當中，統(tǒng)一函數(shù)與基本塊的距離計算標準，設計合理的種子能量調控策略。

為提高距離計算的準確性與合理性，本文將距離計算與能量調控分為函數(shù)路徑長度（Pf）計算、基本塊距離計算、種子距離與能量計算3 個部分。3 個部分為遞進關系，計算過程如圖2 所示。函數(shù)路徑長度表示不同函數(shù)參與距離計算時貢獻的距離，基本塊距離指程序中基本塊到目標區(qū)域的距離，種子距離指進行模糊測試過程中種子執(zhí)行軌跡到目標區(qū)域的距離，本文中目標區(qū)域由若干同屬一個函數(shù)的基本塊構成。

圖2 距離計算示意圖Fig.2 Schematic diagram of distance calculation

在靜態(tài)分析階段完成程序函數(shù)路徑長度計算與基本塊距離計算并將基本塊距離插樁到程序中。在模糊測試階段，模糊測試器記錄種子覆蓋到的基本塊信息，并根據(jù)基本塊信息計算種子距離與能量。

在計算函數(shù)路徑長度（Pf）前引入基本塊權重（Wb）概念以提高距離計算的合理性?；緣K權重表示基本塊在程序路徑中的重要程度，以區(qū)分不同基本塊對距離計算的影響。根據(jù)Wb得到函數(shù)內部基本塊間路徑距離計算公式L（i，j），路徑距離指兩點間最短的一條路徑的長度。根據(jù)本文的方法利用L（i，j）計算程序中每一個函數(shù)的函數(shù)路徑長度，L（i，j）由基本塊間的距離而來，因此函數(shù)路徑長度的量綱與基本塊距離的量綱是統(tǒng)一的。

得到程序函數(shù)路徑長度后，根據(jù)公式L（i，j）與函數(shù)調用圖可以得到程序任意基本塊到目標區(qū)域的距離。程序基本塊距離計算較為復雜，因此將基本塊分為四類進行計算，將計算得到的基本塊距離插樁到目標程序中。得到包含插樁信息的程序后，根據(jù)模糊測試時種子覆蓋到的基本塊中包含的基本塊距離信息計算種子距離并歸一化處理。為了更加合理地對種子能量進行調度，根據(jù)種子執(zhí)行輪次對種子能量進行修正。

3 技術實現(xiàn)

3.1 函數(shù)路徑長度計算

導向式灰盒模糊測試是為了在有限的時間里盡可能多地發(fā)現(xiàn)覆蓋目標區(qū)域的路徑。傳統(tǒng)的距離計算方法沒有對處于程序路徑不同位置的基本塊進行區(qū)分。以圖3 所示的程序路徑為例，傳統(tǒng)的計算方法［15］認為基本塊D和基本塊B到達目標區(qū)域G的距離相同。但從路徑圖可以看出，經過基本塊B到目標區(qū)域G有兩條路徑，而經過D到目標區(qū)域G的路徑僅有一條，經過基本塊B比經過基本塊D更容易到達目標區(qū)域。傳統(tǒng)的計算方式不能體現(xiàn)出不同位置基本塊的區(qū)別，降低了導向的精度和速度。為提高距離計算的準確性，本文對傳統(tǒng)的計算方法進行改進，給不同位置的基本塊賦予不同的權重，使得經過B到目標區(qū)域G的距離小于經過D到G的距離。

圖3 程序路徑示意圖Fig.3 Schematic diagram of program path

通過對程序路徑的分析，一個基本塊的后繼基本塊越多，則經過該基本塊的種子變異后覆蓋不同路徑的概率越高。因此，在距離計算中用基本塊出度（一個基本塊的后繼基本塊個數(shù)）作為基本塊的權重，用符號Wb表示。

在引入基本塊權重后基本塊間的距離如圖4 所示。分別計算圖4 中A到G的路徑1｛A，D，E，G｝和路徑2｛A、B、E、G｝的長度，得到路徑1 長度為7/3，路徑2 長度為11/6。在未將權重引入前，距離相同的兩條路徑在引入基本塊權重后距離產生差值，經過權重高的基本塊的路徑距離更短，在變異時可以得到更多的變異機會。

圖4 加權路徑距離計算Fig.4 Distance calculation of weighted path

式（1）表示同屬一個函數(shù)的基本塊i與基本塊j之間的距離，如果從i到j有多條路徑則選擇其中最短的一條路徑計算，集合B表示該路徑覆蓋到的基本塊，i∈B，j?B。

以圖4 為例，A到G的路徑有4 條。選擇其中最短的一條利用式（1）計算，可得A到G的路徑距離L（A，G）=11/6。

在之前的距離導向啟發(fā)式計算規(guī)則中［15］，不同函數(shù)在基本塊距離計算中貢獻的距離為相同的常數(shù)值，沒有考慮到不同函數(shù)對基本塊距離不同的影響，計算基本塊距離時會引起較大的誤差。為提高距離計算的精度，本文引入函數(shù)路徑長度的概念，用函數(shù)包含的基本塊表示該函數(shù)在基本塊距離計算中貢獻的距離。函數(shù)路徑長度指一條路徑穿過該函數(shù)實際經過的距離，用函數(shù)入口基本塊到函數(shù)出口基本塊全部路徑的距離的平均值表示該長度。

以圖5 為例，基本塊A為函數(shù)入口基本塊，基本塊G為函數(shù)出口基本塊。由A出發(fā)到G的路徑有4 條，分別為｛A，D，E，G｝、｛A，B，E，G｝、｛A，B，G｝和｛A，C，G｝，長度分別為7/3、11/6、5/6 和4/3，因此該函數(shù)路徑長度為19/12，當該函數(shù)參與到距離計算時貢獻的距離為19/12。

圖5 函數(shù)路徑長度計算Fig.5 Length calculation of function path

3.2 基本塊距離計算

依據(jù)3.1 節(jié)中得到的同屬一個函數(shù)的2 個基本塊間距離計算公式L（i，j）與函數(shù)路徑長度（Pf）計算方法，計算程序基本塊到目標區(qū)域距離。依據(jù)程序中基本塊與目標區(qū)域的位置分為4 種情況討論，如圖6 所示。其中，方框表示函數(shù)，圓圈表示基本塊，三角形表示目標基本塊。

圖6 基本塊分類Fig.6 Classification of basic blocks

為便于計算與討論，首先引入符號H，H表示程序中包含目標區(qū)域的函數(shù)從入口基本塊到目標區(qū)域的距離。如圖6 中基本塊D到目標區(qū)域的距離，利用式（2）可以求得該距離。集合Bt由該函數(shù)包含的目標基本塊組成，b1st為入口基本塊。

4 種情況討論如下：

情況1當基本塊為目標基本塊時，該基本塊到目標區(qū)域的距離為0。

情況2當基本塊與目標區(qū)域屬于同一函數(shù)但不是目標基本塊時，如圖6 中的基本塊C。利用式（1）分別計算基本塊C到每個目標基本塊的距離后，求調和平均值作為基本塊C到目標區(qū)域的距離。

情況3當基本塊與目標區(qū)域屬于不同函數(shù)但可以直接通過函數(shù)調用到達目標區(qū)域所在函數(shù)時，如圖6 中基本塊A。用基本塊A調用的系列函數(shù)的函數(shù)路徑長度的倒數(shù)和加上H作為基本塊A到目標區(qū)域的距離，即圖6 中函數(shù)F2與F3的函數(shù)路徑長度的倒數(shù)和與函數(shù)F4的H之和，如果有多條調用路徑則取平均值作為該基本塊的基本塊距離。

情況4當基本塊與目標區(qū)域屬于不同函數(shù)且可以通過同屬一個函數(shù)內的其他基本塊到達目標區(qū)域所在函數(shù)時，如圖6 中基本塊B通過基本塊A可以到達包含目標區(qū)域的函數(shù)F4。計算出基本塊A到目標區(qū)域的距離，在用該距離加上基本塊A到基本塊B的距離，作為基本塊B到目標區(qū)域的距離。

式（3）為基本塊距離計算公式，集合Tb由目標基本塊組成，集合Ta由與目標基本塊同屬一個函數(shù)的基本塊組成，集合Tf由可以直接到達包含目標區(qū)域的函數(shù)的基本塊組成，集合Tj由可以通過Tf中的元素到達包含目標區(qū)域的函數(shù)的基本塊組成。集合Fi由基本塊i到包含目標區(qū)域的函數(shù)所需要調用的函數(shù)組成，Num（Fi）表示集合Fi中元素的數(shù)量，Pf表示函數(shù)f的函數(shù)路徑長度。

在靜態(tài)分析階段利用式（3）完成對基本塊距離的計算，計算過程如算法1 所示。

算法1基本塊距離計算算法

對算法1 的代價進行分析，假設程序有m個函數(shù)和n個基本塊，符號Ki表示函數(shù)i包含的基本塊數(shù)量。對算法中第一個雙層循環(huán)進行分析（算法第1行～第6 行），由函數(shù)路徑長度計算方法可知，Calculate_Pf（function）相當于對函數(shù)function 包含的基本塊進行一次遍歷，代價為O（kfunction），而第二層循環(huán)（算法第2 行～第5 行）代價也為O（kfunction），所以算法1 中第一個雙層循環(huán)總執(zhí)行次數(shù)相當于程序中每個函數(shù)包含的基本塊數(shù)量之和的兩倍，故代價為O（n）。對算法1 第二個雙層循環(huán)（第9 行～第11 行）進行分析，由式（3）可知Calculate（BB）的代價為O（m），故第二個雙層循環(huán)的代價為O（m×n）。取兩個雙層循環(huán)代價之和作為算法1 的總代價，總代價為O（（m+1）×n）。多數(shù)應用程序中基本塊數(shù)量遠遠大于函數(shù)數(shù)量，m+1 可以看為常數(shù)項，所以距離計算花費的代價為O（n）。

3.3 種子距離與能量計算

在3.2 節(jié)中得到了程序中任意基本塊到目標區(qū)域的距離計算公式。在對程序靜態(tài)分析時利用公式計算出每一個基本塊到目標區(qū)域的距離并插樁到程序中。在模糊測試時追蹤每個種子執(zhí)行的軌跡，根據(jù)種子執(zhí)行到的基本塊計算該種子到目標區(qū)域的距離，如式（4）所示：

其中，集合Q由種子s覆蓋的基本塊構成，Num（Q）表示集合Q內元素的數(shù)量。

對種子距離進行歸一化得到式（5），集合S由模糊測試器使用的種子構成：

在模糊測試中種子能量是用來調控一個種子變異次數(shù)的重要變量，如果一個種子與模糊測試器的測試策略契合度越高，那么該種子得到的能量也越高，在種子進行變異時模糊測試器會根據(jù)種子的能量對種子進行變異操作，種子能量越高變異生成的測試用例越多。

為避免種子在模糊測試一開始就收斂到某一條路徑上，將模糊測試執(zhí)行的輪次t作為調節(jié)種子能量的因子。使得模糊測試在初始的幾輪測試中能夠探索足夠多的路徑，避免模糊測試路徑過度集中。將Afl 能量計算方法［18］與式（7）結合可以得到種子能量計算公式：

其中，A（s）表示在Afl 能量計算中種子s的能量。

當t趨近正無窮時，E(s，Tb)=A(s)×(s，Tb)；當t=1 時，E(s，Tb)=A(s)。當模糊測試剛開始時種子的距離對能量計算不會產生影響，而隨著迭代次數(shù)的增加，種子距離對能量的影響逐漸增強。圖7 為不同迭代次數(shù)對種子能量變化的影響，可以看到當種子距離一定時，隨著迭代次數(shù)的增加，種子能量在初始的幾輪迭代中急劇變化后迅速趨于穩(wěn)定，這證明了迭代次數(shù)t僅在測試開始階段影響種子能量計算，隨著迭代次數(shù)的不斷增加，t對種子能量影響逐漸降低，種子距離在種子能量計算中起主導作用。

圖7 迭代次數(shù)對種子能量的影響Fig.7 Effect of iteration times on seed energy

4 實驗與評估

為驗證本文方法的有效性，基于Afl［18］設計實現(xiàn)了原型系統(tǒng)Afl-guide，并與Aflgo、Afl 進行對比實驗。Afl-guide 使用LLVM［19］對目標程序進行分析生成函數(shù)調用圖和函數(shù)控制流程圖，使用Python 腳本利用Networkx 包實現(xiàn)對函數(shù)調用圖和函數(shù)控制流程圖的解析并計算基本塊距離。擴展Afl 的插樁模塊，將基本塊距離插樁到程序中。

本文結合Aflgo，選取libming 與GNU Binutils 作為測試程序。libming 是一款使用C 語言編寫的Flash（SWF）輸出庫，可在C ++、PHP、Python、Ruby和Perl 中使用，擁有10 萬行的代碼，是被廣泛使用的開源項目。GNU Binutils 是GNU/Linux 平臺中使用的二進制分析工具集，有著近100 萬行的代碼，被廣泛用于對模糊測試工具的測試中［20-21］。

實驗選取libming 和GNU Binutils 中近年公開的CVE 作為導向目標，分別用3 個工具對目標程序進行實驗，每組實驗重復5 次，持續(xù)24 h。實驗結果如表1 和表2 所示，其中，Arrive 表示到達目標點的次數(shù)，TTE 表示第一次覆蓋到目標站點花費的時間，Improve 為改善因子，值為Afl-guide 的TTE 與Aflgo和Afl 的TTE 的商，表示相較于Afl 與Aflgo，Aflguide 的效率提升了多少。實驗服務器設置為：AMD ryzen7 2700 處理器，64 GB 內存，2 TB 固態(tài)硬盤，運行Ubuntu 16.04（64 bit）操作系統(tǒng)。

表1 libming 目標站點覆蓋Table 1 libming target site coverage

表2 GNU Binutils 目標站點覆蓋Table 2 GNU Binutils target site coverage

在表1、表2 的數(shù)據(jù)中，除CVE-2016-4490 外，Afl-guide 與Aflgo 到達目標區(qū)域的時間明顯小于Afl，證明了Afl-guide 與Aflgo 的導向性。在CVE-2016-4490 中，目標站點在程序路徑的淺層容易被測試用例覆蓋，因此導向式模糊測試器在測試的過程中引入的資源消耗反而導致Afl-guide 與Aflgo 覆蓋目標站點的速度慢于Afl。通過表1 和表2 中的數(shù)據(jù)還可以看出，利用本文方法實現(xiàn)的工具Afl-guide 在導向性上優(yōu)于Aflgo。在CVE-2018-7867 中提升最為顯著，Afl-guide 到達目標點僅用了Aflgo 花費時間的27.8%。實驗結果表明，使用本文的方法可以快速生成覆蓋程序指定位置的測試用例，能夠大幅提高在已知程序脆弱區(qū)域、補丁檢測等情景下的模糊測試效率。

為進一步說明在種子能量計算過程中引入種子迭代次數(shù)的對路徑收斂速度的影響。Aflgo 與Aflguide 路徑覆蓋率比對情況如表3、表4 所示。其中，Cov 表示第一次覆蓋到目標區(qū)域時模糊測試器的路徑覆蓋率。AveC 表示Cov 與TTE 的比值，Better 值為Aflgo 的AveC 與Afl-guide 的AveC 的商，表示相較于Aflgo 的覆蓋率提升了多少。

表3 libming 路徑覆蓋率Table 3 libming path coverage

表4 GNU Binutils 路徑覆蓋率Table 4 GNU Binutils path coverage

從表3、表4 可以看出，Afl-guide 與Aflgo 在到達目標位置時路徑覆蓋率基本一致，但考慮到所花費的時間，單位時間內Afl-guide 的路徑覆蓋要高于Aflgo。證明在種子能量計算中引入種子迭代次數(shù)達到了預期的目標，在測試初期快速探索路徑并隨著輪次的增加快速收斂到目標區(qū)域。

5 結束語

本文對導向式灰盒模糊測試進行研究，提出一種距離與權重相結合的導向式灰盒模糊測試方法。對距離計算方法進行改進，提高了距離計算的精確性，增強模糊測試器的導向性。實驗結果表明，該方法能夠有效提高模糊測試導向的效率以及對目標區(qū)域覆蓋的概率。由于現(xiàn)在的靜態(tài)分析工具還無法有效識別程序中的間接調用，導致函數(shù)距離計算中存在一定的誤差，同時程序中存在校驗和的情況使得種子無法覆蓋到目標區(qū)域。下一步將對靜態(tài)分析方法進行改進，以提高函數(shù)距離的精度，并將符號執(zhí)行與模糊測試相結合，使模糊測試可以對校驗和程序進行快速導向。