結合混合符號執行的導向式灰盒模糊測試技術

戴 渭,陸余良,朱凱龍

(國防科技大學 電子對抗學院,合肥 230037)

0 概述

模糊測試是一種重要的軟件漏洞分析技術,其向程序提供大量的特殊或者隨機的測試用例,然后監控程序運行過程中的異常情況,通過人工輔助分析異常測試用例數據,從而定位軟件中的漏洞位置。模糊測試是一種簡單有效的強制性技術,雖然測試存在盲目性,但是因為模糊測試具有良好的可伸縮性,所以它在應對大型應用程序時,相較于其他漏洞分析技術具有更高的效率和更低的開銷,隨著軟件的規模和復雜度不斷增大,模糊測試具有其他漏洞挖掘技術無法比擬的優勢[1]。因此,模糊測試是漏洞分析技術在現實應用中的主流,也是發現漏洞最多的技術。

導向式灰盒模糊測試是指能夠快速達到程序目標區域且發現漏洞的模糊測試技術。當目標只集中在程序中的某一部分時,普通的模糊測試會將大量時間浪費在不相關的區域,而無法集中在期望的區域,導向式模糊測試可以將大量的時間預算用于達到這些特定的目標位置,以及對這些區域進行更多、更集中的測試,從而更加高效地發現目標區域的漏洞,并且減少不必要的開銷。文獻[2]提出的導向式灰盒模糊測試器AFLGO是在模糊測試框架AFL[3]的基礎上,通過前期對程序進行靜態分析得到的控制流圖(Control Flow Graphs,CFGs)以及函數調用圖(Call Graph,CG)來計算每個基本塊到若干個目標位置的距離,將目標的可達性作為一種優化,使用啟發式算法來提升距離更近的種子的能量,使其生成的測試用例能快速達到程序的目標區域,從而實現了模糊測試的導向性。

符號執行作為一種重要的程序分析方法,可以為程序測試提供高覆蓋率的測試用例,以觸發深層的程序錯誤[4]。由于在符號執行過程中,針對代碼執行路徑會生成相應路徑的約束條件,如果軟件較大或存在大量循環操作,可能導致路徑約束非常大,甚至呈現爆炸式增長[5]。混合符號執行[6]是結合了符號執行和具體執行的一種動態符號執行技術,其主要思想是生成具體的輸入來執行目標程序,目標是通過自動生成測試用例來盡量覆蓋程序中的可行路徑,進而發現程序內的缺陷[7]。在程序運行的過程中,收集路徑約束條件,按順序搜索程序路徑,利用約束求解器求解上一執行中收集到的約束集,從而得到下一次執行的測試用例;在下一次執行結束后,按一定的策略選擇其中某一分支判斷點進行約束取反,得到新的約束集,再用約束求解器對其進行求解,得到下一執行的測試用例。如此反復,可以避免執行重復路徑,從而以盡可能少的測試集達到高測試覆蓋的目的[4]。

導向式符號執行是利用符號執行、程序分析和約束求解等重型技術來系統有效地搜索可行路徑的狀態空間[9]。一旦識別出能夠到達目標的可行路徑,就生成滿足相應路徑約束的測試用例。導向式符號執行已被用于到達程序的高危區域,例如關鍵系統調用[9]、覆蓋補丁位置[10-11]以及崩潰再現[12]等。導向式符號執行技術與導向式模糊測試技術相比,缺點很明顯,它需要重量級的程序分析和約束求解,要花費巨大的開銷與時間,不適用于現實中的大型程序[1],但相較于導向式模糊測試,它能夠對程序進行更加深入的理解,在不考慮路徑爆炸和時間開銷的情況下,能夠覆蓋更全的程序路徑。而導向式模糊測試因為具有隨機性,在面對魔術字節等檢查語句時,難以生成通過檢查的測試用例,導致對路徑的覆蓋率較低。

本文對導向式模糊測試和混合符號執行技術進行研究,結合混合符號執行與導向式模糊測試技術,將符號執行只應用于導向式模糊測試不能通過的程序路徑,輔助測試用例的生成,從而繼承符號執行的優點,保證模糊測試的高效率和良好的可伸縮性,提高導向式模糊測試對程序目標區域的覆蓋率,以對目標區域進行更深入和更有效的檢測。

1 導向式灰盒模糊測試技術

在導向式灰盒模糊測試中,目標區域為由若干個目標函數組成的函數集,其基本思想是以種子到目標區域的距離為依據,控制種子的能量,距離越近,能量也越大,變異生成的測試用例就越多,這樣生成的測試用例能夠快速達到目標區域,從而達到導向的目的。通過靜態分析得到被測程序的CFGs以及CG,以此計算程序基本塊到目標區域的距離,通過跟蹤種子在程序中所執行的基本塊,定義種子到目標位置的距離,以距離的大小來分配種子在遺傳變異中的能量,即生成測試用例的數量,從而實現模糊測試的導向性,整體架構如圖1所示。

圖1 導向式灰盒模糊測試技術框架Fig.1 Framework of directed gray-box fuzzing test technology

對一個程序進行導向式模糊測試,目標區域為程序中的若干個函數組成的函數集,模糊測試的流程如下:

1)在目標程序運行之前,對程序進行靜態分析,通過CFGs和CG計算程序所有基本塊到目標區域的距離,將計算得到的距離信息插樁進入目標程序。

2)從種子集中按順序選取一個種子,執行程序,根據它執行的基本塊和基本塊的距離信息來計算種子到目標區域的距離。

3)通過動態調控函數動態地調控種子的能量,以此來調控變異生成測試用例的數量。

4)如果變異生成的測試用例執行了新的路徑,則將此測試用例加入種子集,如果產生Crash,則加入Crash集合,直到該種子生成的測試用例達到預定數量。

5)如果模糊測試長時間沒有產生新的狀態轉換,啟用混合符號執行,產生覆蓋了新路徑的種子,加入種子隊列,參與模糊測試。

重復流程2)～流程5),當種子集中的所有種子都被選取為一次迭代,繼續從頭開始選取種子進行下一次迭代,直到時間結束。流程1)～流程4)為本文設計的基于動態能量調控的導向式模糊測試技術,實現了模糊測試的導向性。流程5)為本文要著重研究的技術,輔助導向式模糊測試用例生成的混合符號執行技術。

2 導向式灰盒模糊測試技術實現

2.1 導向式模糊測試

為實現模糊測試的導向性,本文設計了基于動態能量調控的導向式模糊測試,主要分為靜態分析和動態執行兩個部分。

靜態分析的輸入為目標程序和給定的目標區域(若干個函數組成的函數集),結果是插樁了基本塊到目標區域距離信息的二進制程序;首先計算程序基本塊到目標區域的距離,通過給定的目標程序源代碼(或者二進制程序)構建程序的CG和每個函數的CFGs,再根據給定的目標區域計算基本塊到目標的距離,輸出程序所有基本塊到目標區域的距離信息。

動態執行的目標為插樁后的二進制程序,輸入為選定的種子集,輸出為導致目標產生Crash的測試用例,或者達到預定時間。在得到靜態分析的結果后,將種子集輸入執行插樁程序,跟蹤程序的基本塊轉換,并且記錄執行的所有基本塊距離之和,以此來計算出所有種子級別的目標距離。在進行模糊測試時,從種子集中依次選取種子,使用動態能量調控技術并根據種子距離為種子分配不同的能量,種子到目標距離越近,分配的能量就越多,種子根據能量變異生成不同數量的測試用例執行目標程序,同時繼續跟蹤程序的基本塊執行情況和距離信息,如果產生了新種子,則加入種子集參與循環。

2.1.1 種子到目標區域距離的計算

為實現模糊測試的導向性,使更加接近目標區域的種子生成更多的測試用例,需要計算一個種子到目標區域的距離,再根據距離來決定這個種子能夠生成多少測試用例。為精確地計算種子到目標區域的距離,本文對程序靜態分析技術進行了研究和拓展,首先運用靜態分析獲取程序的CFGs和CG,用于計算函數級別和基本塊級別的距離。使用CFGs和CG中的最短路徑的邊數來表示函數間和基本塊間的距離,通過Dijkstra’s算法[13]即可分別計算目標區域中每個目標函數到各個基本塊的最短距離,但這種表示方法不夠準確,因為兩個函數間可能不止一種調用方法,被調用函數也可能不止一個進入點,這樣相鄰函數間的邊應該被賦予不同的權值,它們的可達路徑不止一種,不能直接簡單地用邊的條數來表示距離。為了更好地定義相鄰函數間的距離,用Nf來表示被調用函數在調用方法中的個數,Nb表示被調用函數在調用函數中出現次數,用d′1和d′2表示Nf和Nb的影響因子,d′f則表示兩個相鄰函數之間邊的權值。通過程序和CG即可計算出函數間邊的權值,將其作為兩個相鄰函數之間的距離,再利用Dijkstra’s算法來分別計算每個目標函數到所有函數的最短距離,這樣便得到了加權后每個函數在調用圖中分別到各個目標函數的最短距離df(f,tf)。

(1)

(2)

d′f(f1,f2)=d′1·d′2

(3)

1)函數級別距離計算

函數級別的距離計算用來計算CG中的每個函數到所有目標函數的平均距離。對于一個函數f到多個目標函數的距離計算,根據它到每個目標函數的最短距離,使用調和平均值來計算出它到目標函數的平均距離作為到目標區域的距離,得到函數級別距離的計算公式:

(4)

其中,df(f,tf)為函數f到目標函數tf的最短距離,Tf為所有目標函數的集合,R(f,Tf)為函數f能夠達到的所有目標函數的集合。

2)基本塊級別距離計算

雖然種子的距離是程序間的,但是本文的計算只需要對CG和每個程序間CFGs進行一次分析,將基本塊級別的計算近似到了函數級別的計算。在同一個程序間CFGs中,將相鄰基本塊之間的邊作為它們的距離,兩個基本塊之間距離為它們之間的最短路徑的邊數。不在同一個CFGs的基本塊目標距離通過基本塊能夠調用的函數來確定,以調用函數的函數級距離的常數倍來近似計算,當一個基本塊沒有可以調用的函數時,就通過它所能達到的所有可以調用函數的基本塊來確定。基本塊到目標區域的距離計算公式如下:

db(b,Tb)=

(5)

其中,db(b,Tb)表示基本塊b到目標區域的距離,Btf為目標函數的基本塊集合,N(b)為基本塊b可以調用的函數集合,且滿足?b∈T,N(b)≠φ,db(b,t)為兩個基本塊b、t之間最短路徑的連接邊數,a為一個常數。

3)種子級別的距離計算

前兩個級別的距離計算是在靜態分析階段進行的,而種子級別的距離計算則是在模糊測循環開始后動態地實現的。本文通過跟蹤種子執行了哪些基本塊來計算種子到目標區域的距離,在AFL和LibFuzzer[14]等灰盒模糊測試器中,使用了輕量級的插樁來獲取程序的覆蓋信息,這種插樁能夠獲取基本塊的轉換信息,以及粗略的分支命中計數,本文在此基礎上進行拓展,將得到的所有基本塊距離向量加入程序的插樁,得到插樁后的二進制程序,這樣就可以追蹤種子執行的基本塊,計算出種子到目標區域的平均距離:

(6)

最后將得到的種子距離歸一化來得到最終的距離向量:

(7)

其中,dmax(s,Tb)和dmin(s,Tb)分別為所有種子中離目標最大的距離和最小的距離。

2.1.2 種子的動態能量調控技術

種子的能量調控用來調控一個選中的種子的變異次數,如果當前的種子距離目標區域更加接近,那么就要給它分配更多的能量,變異生成更多的測試用例,這樣就能夠更大概率生成所期望的測試用例(到達目標區域)。本文使用基于蟻群算法[15]的動態能量調控函數來動態地調控種子的能量。

蟻群算法是一種用來尋找最優化路徑的概率型算法,它具有分布計算、信息正反饋和啟發式搜索的特征,本質上是進化算法中的一種啟發式全局優化算法,它的基本方法如下:

1)N只螞蟻從一個出發點到四周搜索食物,N只螞蟻都搜索完畢為一輪迭代。

2)每只螞蟻在行進的路上釋放信息素,信息素的量和解的質量成正比,當找到食物時回到出發點,在路徑留下信息素,留下的量和距離成正相關,在第一次搜尋時,所有的路徑具有相同的信息素,同時每次迭代后信息素按比例減少。

3)螞蟻選擇一個路徑的概率和信息素的量成正比。

4)量高的路徑在每次迭代中信息素濃度越來越高,經過的螞蟻也越來越多,而質量差的路徑信息素慢慢變得越來越少,這樣在迭代中,螞蟻從剛開始的隨機搜尋慢慢地往最優解收斂,從最開始的接受較差解到最后的只接受更優解,在一定程度上緩解過早收斂的問題。

設定模糊測試中的種子為螞蟻搜索的路徑,種子與目標的距離遠近設定為解的質量,即距離越近,質量越高,那么每次迭代留下來的信息素也就越多。將螞蟻選擇路徑的概率用作能量調控,通過迭代次數的增加,信息素的量在增加,這個種子的能量也在慢慢增加,由此來實現動態能量調控函數。

基于蟻群算法的動態能量調控函數如下:

t:迭代次數

si:種子i

di:種子i到目標區域的距離

τi:ti路徑上的信息素

ρ:信息素蒸發系數0<ρ<1

Ei(t):第t次迭代時si的啟發度

τi(0)=C

Δτi(t)=Q·Ei(t)·(1-di),Q為常數

τi(t+1)=(1-ρ)τi(t)+Δτi(t)

Pi(t)=(1-di)·(1-ei)+ei

其中,τi(t)為種子si在模糊測試第t輪迭代時路徑上的信息素,Ei(t)為種子si在第t輪迭代時的啟發度(即蟻群算法中選取一個路徑的概率),Pi(t)為種子si在第t輪迭代時的能量,啟發度Ei(t)的大小和信息素的多少成正相關,而Ei(t)決定著能量Pi(t)的大小。被測程序剛剛開始運行時,種子集中所有種子的信息素為相同的數值,那么它們的路徑也都有著相同的啟發度和能量,到了新一輪迭代時,上一輪的信息素會以按照蒸發系數ρ的比率減小,同時會增加新得到的信息素Δτi(t),Δτi(t)大小根據種子到目標的距離遠近以及上一輪信息素的多少來決定,這樣在一輪輪的迭代下,距離目標更近種子的路徑上的信息素會越來越多,能量也會越來越大,不同種子的能量便在迭代之中產生了差距。

2.2 混合符號執行

導向式模糊測試可以快速地生成測試用例到達程序目標區域,繼而發現目標區域中不同的路徑,但是某些帶有特定值檢查的語句對于模糊測試是非常具有挑戰性的。當模糊測試長時間沒有觸發新的狀態轉換時,主要原因是因為模糊測試器無法生成特定的輸入滿足代碼中的復雜檢查,混合符號執行利用約束求解器,將達到但無法滿足復雜檢查的現有輸入轉換為達到并滿足此類檢查的新輸入。當調用混合符號執行時,跟蹤每一個新加入種子隊列的種子,以識別模糊測試無法滿足的狀態轉換,當這種轉換被識別時,混合符號執行產生輸入通過這種狀態轉換。

在目標區域中,某條語句需要輸入的測試用例中的某段偏移位置為特定的值才能通過,面對這種魔術字節,模糊測試很難隨機地生成通過檢查的測試用例,導致無法覆蓋這條分支,從而無法觸發這條路徑上可能的崩潰點。

函數示例如下:

int main (void)

{

…

if (x=0xACDB3061)

CRASH

…

}

混合執行結合了具體執行和符號執行,是動態符號執行的一種。其主要思想是用具體輸入執行程序,在程序運行的過程中,通過程序插樁手段收集路徑約束條件,按順序搜索程序路徑,利用約束求解器求解上一執行中收集到的約束集,從而得到下一次執行的測試用例;在下一次執行結束后,按一定的策略選擇其中某一分支判斷點進行約束取反,得到新的約束集,再用約束求解器對其進行求解,得到下一執行的測試用例[16]。混合執行的優點在于,它能夠探索和查找約束求解器可以滿足的任何路徑的輸入,這使得它有助于識別復雜比較(包括某些哈希函數)的解決方案[17]。在多數情況下模糊測試可以覆蓋大部分的路徑,它只需通過一些簡單高效的突變策略就能快速地找到更多的新路徑,而混合符號執行只需解決更困難的約束。

當模糊測試長時間沒有觸發新的路徑時,本文便認為模糊測試遇到了難以通過的狀態變換,此時啟用混合符號執行,調用最近覆蓋了新的路徑而加入隊列的種子,符號化地跟蹤這些種子,識別模糊測試無法滿足的狀態轉換,使用混合符號執行產生滿足這種狀態變換的測試用例,將結果加入種子隊列繼續進行模糊測試。這種方法能夠避免符號執行的路徑爆炸。

在啟用混合符號執行時,將種子符號化建模為一種符號狀態,使應用程序的二進制代碼轉換為中間表示,確定程序代碼對符號狀態的影響,這種符號狀態使用符號變量表示來自用戶的輸入或者其他非常量數據,例如來自環境的數據,其他的值被建模為具體值(如一些常量)。符號變量是一個變量,它可以產生許多可能的具體解,隨著具體的執行,符號約束被添加到這些變量中,這些約束是對符號值的潛在解的限制性陳述(如x>0),分析引擎在整個執行過程中跟蹤符號狀態中的所有具體值和符號值。在到達的程序中的任何節點上,都可以執行約束求解來確定滿足狀態中所有可能的符號約束,當使用滿足這些約束的具體值來代替符號值時,就是一個滿足這個約束的測試用例。當跟蹤到有條件的控制流轉換時,會檢查反轉這個條件是否會導致發現新的狀態變換,如果可以,則將生成一個示例輸入通過新的狀態轉換而不是沿著原來的控制流執行。這樣就能夠到達程序中未被覆蓋過的位置,在產生輸入之后,會繼續沿著匹配的路徑尋找新的狀態轉換。

混合符號執行使用了預約來確保能夠保持執行結果與跟蹤的種子所執行的結果相同,同時保持發現新的狀態轉換的能力。在預約束執行中,輸入的每個字節都被約束為與種子的實際字節相匹配,當發現新的基本塊轉換時,短暫地取消預約束,求解出滿足變換的輸入。如混合符號執行首先約束輸入中的所有字節,匹配跟蹤的輸入,當執行到魔術字節的檢查時,識別到一個之前未識別的狀態轉換,此時刪除開始添加的預約束,獲取這個位置的路徑約束(x=0xACDB3061),這樣便可以生成一個在特定位置包含了魔術字節的輸入,通過這個路徑轉換。

在得到了通過新的狀態轉換的測試用例后,將其加入種子集,并將新加入的種子優先選擇繼續進行模糊測試,重復整個導向式模糊測試的循環。

3 實驗與評估

為實現和評估混合符號執行在導向式模糊測試中的效果,本文在模糊測試框架AFL的基礎上設計了導向式模糊測試器AFL-Ant。該設計以python腳本的形式實現距離計算器,輸入為程序的CFGs、CG以及目標函數集,用networkx包來解析圖形,再使用Djikstra’s 算法來計算基本塊到目標的距離,計算并輸出基本塊距離信息BB-distance。AFL-Ant 拓展了AFL的插樁,將BB-distance 插樁到目標程序的基本塊,在記錄基本塊轉換的同時,也記錄所執行基本塊的距離累積值,該項目使用 ASAN[18]構建。AFL-Ant 的模糊測試器基于2.40b版本的 AFL,它通過記錄的基本塊距離累計值來計算當前的種子距離,使用本文所設計的基于蟻群算法的動態能量調控方法來調控種子能量。同時設計了基于Angr[19]的混合符號執行引擎,這個引擎是基于Mayhem[20]和S2E[21]拓展和改進的。為評估結合混合符號執行的導向式模糊測試器在模糊測試中對目標區域的覆蓋效果,本文通過補丁檢測來測試它的能力。

結合當前最近的導向式模糊測試器AFLGO所做的工作,本文選取了GNU Diffutils和GNU Binutils[22]兩組工具集作為目標程序,選取了它們在特定版本的補丁,將補丁所覆蓋的位置作為目標區域,設置了相同的初始種子集,分別使用AFL和AFL-Ant對它們進行導向式模糊測試,測試時間設置為8 h,最終比較它們在模糊測試中所覆蓋的目標區域基本塊的數量。

GNU Diffutils工具集測試工具為Diff、sdiff、diff3、cmp,程序大小為42 930行,選定補丁版本為2016-11-09—2017-05-12的175份commits。

GNU Binutil工具集測試工具為addr2line、ar、cxxfilt、elfedit、nm、objcopy、objdump、ranlib、readelf,程序大小為68 830行,選定補丁版本為2017-04-12—2017-08-11的181份commits。補丁情況如表1所示。

表1 補丁測試中的基本塊覆蓋情況Table 1 Basic block coverage in patch testing 塊

表1展示了補丁測試的結果,Diffutils的補丁基本塊數量為166塊,在實驗中,AFLGO覆蓋了其中的61塊,而AFL-Ant覆蓋了69塊,相比于AFLGO提高了13.1%;Binutils的補丁基本塊數量為852塊,AFLGO在實驗中覆蓋了其中的163塊,而AFL-Ant覆蓋了其中的178塊,相比于AFLGO提高了9.2%。合計AFL-Ant在補丁測試中對目標區域基本塊的覆蓋數量為247塊,相較于AFLGO的224塊提高了10.2%。

圖2統計了兩個導向式模糊測試器測試結果的交叉情況,兩個測試器總共覆蓋了補丁中的252個基本塊,其中有219塊是它們共同覆蓋到的。在AFLGO覆蓋的基本塊中,有5個是AFL-Ant未覆蓋到的,而AFL-Ant能夠覆蓋28個AFLGO無法覆蓋到的基本塊。

圖2 補丁測試覆蓋情況文氏示意圖Fig.2 Venn schematic diagram of patch test coverage

為了評估AFL-Ant和AFLGO在覆蓋目標區域的效率,在219個共同覆蓋的基本塊中,隨機選取了其中的120塊,將其分為了3組作為新的目標區域,用AFL-Ant和AFLGO分別對每組進行導向式模糊測試,實驗的時間上限設置為2 h,比較它們每組實驗中覆蓋所有目標所花費的時間。

實驗結果如表2所示,AFL-Ant在3組實驗中均能覆蓋到目標區域的所有基本塊,而在第3組實驗中,AFLGO未能在2 h內覆蓋所有的目標基本塊。同時,AFL-Ant覆蓋所有基本塊的時間均比AFLGO更快,這歸功于它更加高效的動態能量調控方法以及混合符號執行輔助通過復雜節點能力。

表2 補丁測試時間Table 2 Patch test time min

通過上述實驗可以看出,使用了混合符號執行的AFL-Ant能夠提高對目標區域的覆蓋率,發現更多的程序狀態變換,同時能夠覆蓋目標區域,更加高效地去挖掘漏洞。

4 結束語

本文對混合符號執行技術在導向式模糊測試中的應用進行研究,提出一種新的導向式模糊測試策略,即使用混合符號執行輔助導向式模糊測試的測試用例生成的方法,幫助導向式模糊測試到達一些脆弱的區域。實驗結果表明,該方法能夠提高導向式模糊測試對目標區域的覆蓋率,加快到達并覆蓋整個目標區域的速度,提高發現目標區域漏洞的概率。本文導向式模糊測試中使用CG和CFGs來進行種子的距離計算,但未考慮到間接調用關系,導致間接調用的函數間距離計算不夠準確,在未來工作中將通過改進靜態分析方法識別程序中的間接調用關系來完善種子的距離計算過程。同時,可將靜態分析技術和本文提出的混合符號執行引擎結合,以更大概率地去觸發程序漏洞。