結(jié)合混合符號(hào)執(zhí)行的導(dǎo)向式灰盒模糊測(cè)試技術(shù)

戴 渭,陸余良,朱凱龍

(國(guó)防科技大學(xué) 電子對(duì)抗學(xué)院,合肥 230037)

0 概述

模糊測(cè)試是一種重要的軟件漏洞分析技術(shù),其向程序提供大量的特殊或者隨機(jī)的測(cè)試用例,然后監(jiān)控程序運(yùn)行過(guò)程中的異常情況,通過(guò)人工輔助分析異常測(cè)試用例數(shù)據(jù),從而定位軟件中的漏洞位置。模糊測(cè)試是一種簡(jiǎn)單有效的強(qiáng)制性技術(shù),雖然測(cè)試存在盲目性,但是因?yàn)槟：郎y(cè)試具有良好的可伸縮性,所以它在應(yīng)對(duì)大型應(yīng)用程序時(shí),相較于其他漏洞分析技術(shù)具有更高的效率和更低的開(kāi)銷,隨著軟件的規(guī)模和復(fù)雜度不斷增大,模糊測(cè)試具有其他漏洞挖掘技術(shù)無(wú)法比擬的優(yōu)勢(shì)[1]。因此,模糊測(cè)試是漏洞分析技術(shù)在現(xiàn)實(shí)應(yīng)用中的主流,也是發(fā)現(xiàn)漏洞最多的技術(shù)。

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

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

導(dǎo)向式符號(hào)執(zhí)行是利用符號(hào)執(zhí)行、程序分析和約束求解等重型技術(shù)來(lái)系統(tǒng)有效地搜索可行路徑的狀態(tài)空間[9]。一旦識(shí)別出能夠到達(dá)目標(biāo)的可行路徑,就生成滿足相應(yīng)路徑約束的測(cè)試用例。導(dǎo)向式符號(hào)執(zhí)行已被用于到達(dá)程序的高危區(qū)域,例如關(guān)鍵系統(tǒng)調(diào)用[9]、覆蓋補(bǔ)丁位置[10-11]以及崩潰再現(xiàn)[12]等。導(dǎo)向式符號(hào)執(zhí)行技術(shù)與導(dǎo)向式模糊測(cè)試技術(shù)相比,缺點(diǎn)很明顯,它需要重量級(jí)的程序分析和約束求解,要花費(fèi)巨大的開(kāi)銷與時(shí)間,不適用于現(xiàn)實(shí)中的大型程序[1],但相較于導(dǎo)向式模糊測(cè)試,它能夠?qū)Τ绦蜻M(jìn)行更加深入的理解,在不考慮路徑爆炸和時(shí)間開(kāi)銷的情況下,能夠覆蓋更全的程序路徑。而導(dǎo)向式模糊測(cè)試因?yàn)榫哂须S機(jī)性,在面對(duì)魔術(shù)字節(jié)等檢查語(yǔ)句時(shí),難以生成通過(guò)檢查的測(cè)試用例,導(dǎo)致對(duì)路徑的覆蓋率較低。

本文對(duì)導(dǎo)向式模糊測(cè)試和混合符號(hào)執(zhí)行技術(shù)進(jìn)行研究,結(jié)合混合符號(hào)執(zhí)行與導(dǎo)向式模糊測(cè)試技術(shù),將符號(hào)執(zhí)行只應(yīng)用于導(dǎo)向式模糊測(cè)試不能通過(guò)的程序路徑,輔助測(cè)試用例的生成,從而繼承符號(hào)執(zhí)行的優(yōu)點(diǎn),保證模糊測(cè)試的高效率和良好的可伸縮性,提高導(dǎo)向式模糊測(cè)試對(duì)程序目標(biāo)區(qū)域的覆蓋率,以對(duì)目標(biāo)區(qū)域進(jìn)行更深入和更有效的檢測(cè)。

1 導(dǎo)向式灰盒模糊測(cè)試技術(shù)

在導(dǎo)向式灰盒模糊測(cè)試中,目標(biāo)區(qū)域?yàn)橛扇舾蓚€(gè)目標(biāo)函數(shù)組成的函數(shù)集,其基本思想是以種子到目標(biāo)區(qū)域的距離為依據(jù),控制種子的能量,距離越近,能量也越大,變異生成的測(cè)試用例就越多,這樣生成的測(cè)試用例能夠快速達(dá)到目標(biāo)區(qū)域,從而達(dá)到導(dǎo)向的目的。通過(guò)靜態(tài)分析得到被測(cè)程序的CFGs以及CG,以此計(jì)算程序基本塊到目標(biāo)區(qū)域的距離,通過(guò)跟蹤種子在程序中所執(zhí)行的基本塊,定義種子到目標(biāo)位置的距離,以距離的大小來(lái)分配種子在遺傳變異中的能量,即生成測(cè)試用例的數(shù)量,從而實(shí)現(xiàn)模糊測(cè)試的導(dǎo)向性,整體架構(gòu)如圖1所示。

圖1 導(dǎo)向式灰盒模糊測(cè)試技術(shù)框架Fig.1 Framework of directed gray-box fuzzing test technology

對(duì)一個(gè)程序進(jìn)行導(dǎo)向式模糊測(cè)試,目標(biāo)區(qū)域?yàn)槌绦蛑械娜舾蓚€(gè)函數(shù)組成的函數(shù)集,模糊測(cè)試的流程如下:

1)在目標(biāo)程序運(yùn)行之前,對(duì)程序進(jìn)行靜態(tài)分析,通過(guò)CFGs和CG計(jì)算程序所有基本塊到目標(biāo)區(qū)域的距離,將計(jì)算得到的距離信息插樁進(jìn)入目標(biāo)程序。

2)從種子集中按順序選取一個(gè)種子,執(zhí)行程序,根據(jù)它執(zhí)行的基本塊和基本塊的距離信息來(lái)計(jì)算種子到目標(biāo)區(qū)域的距離。

3)通過(guò)動(dòng)態(tài)調(diào)控函數(shù)動(dòng)態(tài)地調(diào)控種子的能量,以此來(lái)調(diào)控變異生成測(cè)試用例的數(shù)量。

4)如果變異生成的測(cè)試用例執(zhí)行了新的路徑,則將此測(cè)試用例加入種子集,如果產(chǎn)生Crash,則加入Crash集合,直到該種子生成的測(cè)試用例達(dá)到預(yù)定數(shù)量。

5)如果模糊測(cè)試長(zhǎng)時(shí)間沒(méi)有產(chǎn)生新的狀態(tài)轉(zhuǎn)換,啟用混合符號(hào)執(zhí)行,產(chǎn)生覆蓋了新路徑的種子,加入種子隊(duì)列,參與模糊測(cè)試。

重復(fù)流程2)～流程5),當(dāng)種子集中的所有種子都被選取為一次迭代,繼續(xù)從頭開(kāi)始選取種子進(jìn)行下一次迭代,直到時(shí)間結(jié)束。流程1)～流程4)為本文設(shè)計(jì)的基于動(dòng)態(tài)能量調(diào)控的導(dǎo)向式模糊測(cè)試技術(shù),實(shí)現(xiàn)了模糊測(cè)試的導(dǎo)向性。流程5)為本文要著重研究的技術(shù),輔助導(dǎo)向式模糊測(cè)試用例生成的混合符號(hào)執(zhí)行技術(shù)。

2 導(dǎo)向式灰盒模糊測(cè)試技術(shù)實(shí)現(xiàn)

2.1 導(dǎo)向式模糊測(cè)試

為實(shí)現(xiàn)模糊測(cè)試的導(dǎo)向性,本文設(shè)計(jì)了基于動(dòng)態(tài)能量調(diào)控的導(dǎo)向式模糊測(cè)試,主要分為靜態(tài)分析和動(dòng)態(tài)執(zhí)行兩個(gè)部分。

靜態(tài)分析的輸入為目標(biāo)程序和給定的目標(biāo)區(qū)域(若干個(gè)函數(shù)組成的函數(shù)集),結(jié)果是插樁了基本塊到目標(biāo)區(qū)域距離信息的二進(jìn)制程序;首先計(jì)算程序基本塊到目標(biāo)區(qū)域的距離,通過(guò)給定的目標(biāo)程序源代碼(或者二進(jìn)制程序)構(gòu)建程序的CG和每個(gè)函數(shù)的CFGs,再根據(jù)給定的目標(biāo)區(qū)域計(jì)算基本塊到目標(biāo)的距離,輸出程序所有基本塊到目標(biāo)區(qū)域的距離信息。

動(dòng)態(tài)執(zhí)行的目標(biāo)為插樁后的二進(jìn)制程序,輸入為選定的種子集,輸出為導(dǎo)致目標(biāo)產(chǎn)生Crash的測(cè)試用例,或者達(dá)到預(yù)定時(shí)間。在得到靜態(tài)分析的結(jié)果后,將種子集輸入執(zhí)行插樁程序,跟蹤程序的基本塊轉(zhuǎn)換,并且記錄執(zhí)行的所有基本塊距離之和,以此來(lái)計(jì)算出所有種子級(jí)別的目標(biāo)距離。在進(jìn)行模糊測(cè)試時(shí),從種子集中依次選取種子,使用動(dòng)態(tài)能量調(diào)控技術(shù)并根據(jù)種子距離為種子分配不同的能量,種子到目標(biāo)距離越近,分配的能量就越多,種子根據(jù)能量變異生成不同數(shù)量的測(cè)試用例執(zhí)行目標(biāo)程序,同時(shí)繼續(xù)跟蹤程序的基本塊執(zhí)行情況和距離信息,如果產(chǎn)生了新種子,則加入種子集參與循環(huán)。

2.1.1 種子到目標(biāo)區(qū)域距離的計(jì)算

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

(1)

(2)

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

(3)

1)函數(shù)級(jí)別距離計(jì)算

函數(shù)級(jí)別的距離計(jì)算用來(lái)計(jì)算CG中的每個(gè)函數(shù)到所有目標(biāo)函數(shù)的平均距離。對(duì)于一個(gè)函數(shù)f到多個(gè)目標(biāo)函數(shù)的距離計(jì)算,根據(jù)它到每個(gè)目標(biāo)函數(shù)的最短距離,使用調(diào)和平均值來(lái)計(jì)算出它到目標(biāo)函數(shù)的平均距離作為到目標(biāo)區(qū)域的距離,得到函數(shù)級(jí)別距離的計(jì)算公式:

(4)

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

2)基本塊級(jí)別距離計(jì)算

雖然種子的距離是程序間的,但是本文的計(jì)算只需要對(duì)CG和每個(gè)程序間CFGs進(jìn)行一次分析,將基本塊級(jí)別的計(jì)算近似到了函數(shù)級(jí)別的計(jì)算。在同一個(gè)程序間CFGs中,將相鄰基本塊之間的邊作為它們的距離,兩個(gè)基本塊之間距離為它們之間的最短路徑的邊數(shù)。不在同一個(gè)CFGs的基本塊目標(biāo)距離通過(guò)基本塊能夠調(diào)用的函數(shù)來(lái)確定,以調(diào)用函數(shù)的函數(shù)級(jí)距離的常數(shù)倍來(lái)近似計(jì)算,當(dāng)一個(gè)基本塊沒(méi)有可以調(diào)用的函數(shù)時(shí),就通過(guò)它所能達(dá)到的所有可以調(diào)用函數(shù)的基本塊來(lái)確定?；緣K到目標(biāo)區(qū)域的距離計(jì)算公式如下:

db(b,Tb)=

(5)

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

3)種子級(jí)別的距離計(jì)算

前兩個(gè)級(jí)別的距離計(jì)算是在靜態(tài)分析階段進(jìn)行的,而種子級(jí)別的距離計(jì)算則是在模糊測(cè)循環(huán)開(kāi)始后動(dòng)態(tài)地實(shí)現(xiàn)的。本文通過(guò)跟蹤種子執(zhí)行了哪些基本塊來(lái)計(jì)算種子到目標(biāo)區(qū)域的距離,在AFL和LibFuzzer[14]等灰盒模糊測(cè)試器中,使用了輕量級(jí)的插樁來(lái)獲取程序的覆蓋信息,這種插樁能夠獲取基本塊的轉(zhuǎn)換信息,以及粗略的分支命中計(jì)數(shù),本文在此基礎(chǔ)上進(jìn)行拓展,將得到的所有基本塊距離向量加入程序的插樁,得到插樁后的二進(jìn)制程序,這樣就可以追蹤種子執(zhí)行的基本塊,計(jì)算出種子到目標(biāo)區(qū)域的平均距離:

(6)

最后將得到的種子距離歸一化來(lái)得到最終的距離向量:

(7)

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

2.1.2 種子的動(dòng)態(tài)能量調(diào)控技術(shù)

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

蟻群算法是一種用來(lái)尋找最優(yōu)化路徑的概率型算法,它具有分布計(jì)算、信息正反饋和啟發(fā)式搜索的特征,本質(zhì)上是進(jìn)化算法中的一種啟發(fā)式全局優(yōu)化算法,它的基本方法如下:

1)N只螞蟻從一個(gè)出發(fā)點(diǎn)到四周搜索食物,N只螞蟻都搜索完畢為一輪迭代。

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

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

4)量高的路徑在每次迭代中信息素濃度越來(lái)越高,經(jīng)過(guò)的螞蟻也越來(lái)越多,而質(zhì)量差的路徑信息素慢慢變得越來(lái)越少,這樣在迭代中,螞蟻從剛開(kāi)始的隨機(jī)搜尋慢慢地往最優(yōu)解收斂,從最開(kāi)始的接受較差解到最后的只接受更優(yōu)解,在一定程度上緩解過(guò)早收斂的問(wèn)題。

設(shè)定模糊測(cè)試中的種子為螞蟻搜索的路徑,種子與目標(biāo)的距離遠(yuǎn)近設(shè)定為解的質(zhì)量,即距離越近,質(zhì)量越高,那么每次迭代留下來(lái)的信息素也就越多。將螞蟻選擇路徑的概率用作能量調(diào)控,通過(guò)迭代次數(shù)的增加,信息素的量在增加,這個(gè)種子的能量也在慢慢增加,由此來(lái)實(shí)現(xiàn)動(dòng)態(tài)能量調(diào)控函數(shù)。

基于蟻群算法的動(dòng)態(tài)能量調(diào)控函數(shù)如下:

t:迭代次數(shù)

si:種子i

di:種子i到目標(biāo)區(qū)域的距離

τi:ti路徑上的信息素

ρ:信息素蒸發(fā)系數(shù)0<ρ<1

Ei(t):第t次迭代時(shí)si的啟發(fā)度

τi(0)=C

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

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

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

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

2.2 混合符號(hào)執(zhí)行

導(dǎo)向式模糊測(cè)試可以快速地生成測(cè)試用例到達(dá)程序目標(biāo)區(qū)域,繼而發(fā)現(xiàn)目標(biāo)區(qū)域中不同的路徑,但是某些帶有特定值檢查的語(yǔ)句對(duì)于模糊測(cè)試是非常具有挑戰(zhàn)性的。當(dāng)模糊測(cè)試長(zhǎng)時(shí)間沒(méi)有觸發(fā)新的狀態(tài)轉(zhuǎn)換時(shí),主要原因是因?yàn)槟：郎y(cè)試器無(wú)法生成特定的輸入滿足代碼中的復(fù)雜檢查,混合符號(hào)執(zhí)行利用約束求解器,將達(dá)到但無(wú)法滿足復(fù)雜檢查的現(xiàn)有輸入轉(zhuǎn)換為達(dá)到并滿足此類檢查的新輸入。當(dāng)調(diào)用混合符號(hào)執(zhí)行時(shí),跟蹤每一個(gè)新加入種子隊(duì)列的種子,以識(shí)別模糊測(cè)試無(wú)法滿足的狀態(tài)轉(zhuǎn)換,當(dāng)這種轉(zhuǎn)換被識(shí)別時(shí),混合符號(hào)執(zhí)行產(chǎn)生輸入通過(guò)這種狀態(tài)轉(zhuǎn)換。

在目標(biāo)區(qū)域中,某條語(yǔ)句需要輸入的測(cè)試用例中的某段偏移位置為特定的值才能通過(guò),面對(duì)這種魔術(shù)字節(jié),模糊測(cè)試很難隨機(jī)地生成通過(guò)檢查的測(cè)試用例,導(dǎo)致無(wú)法覆蓋這條分支,從而無(wú)法觸發(fā)這條路徑上可能的崩潰點(diǎn)。

函數(shù)示例如下:

int main (void)

{

…

if (x=0xACDB3061)

CRASH

…

}

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

當(dāng)模糊測(cè)試長(zhǎng)時(shí)間沒(méi)有觸發(fā)新的路徑時(shí),本文便認(rèn)為模糊測(cè)試遇到了難以通過(guò)的狀態(tài)變換,此時(shí)啟用混合符號(hào)執(zhí)行,調(diào)用最近覆蓋了新的路徑而加入隊(duì)列的種子,符號(hào)化地跟蹤這些種子,識(shí)別模糊測(cè)試無(wú)法滿足的狀態(tài)轉(zhuǎn)換,使用混合符號(hào)執(zhí)行產(chǎn)生滿足這種狀態(tài)變換的測(cè)試用例,將結(jié)果加入種子隊(duì)列繼續(xù)進(jìn)行模糊測(cè)試。這種方法能夠避免符號(hào)執(zhí)行的路徑爆炸。

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

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

在得到了通過(guò)新的狀態(tài)轉(zhuǎn)換的測(cè)試用例后,將其加入種子集,并將新加入的種子優(yōu)先選擇繼續(xù)進(jìn)行模糊測(cè)試,重復(fù)整個(gè)導(dǎo)向式模糊測(cè)試的循環(huán)。

3 實(shí)驗(yàn)與評(píng)估

為實(shí)現(xiàn)和評(píng)估混合符號(hào)執(zhí)行在導(dǎo)向式模糊測(cè)試中的效果,本文在模糊測(cè)試框架AFL的基礎(chǔ)上設(shè)計(jì)了導(dǎo)向式模糊測(cè)試器AFL-Ant。該設(shè)計(jì)以python腳本的形式實(shí)現(xiàn)距離計(jì)算器,輸入為程序的CFGs、CG以及目標(biāo)函數(shù)集,用networkx包來(lái)解析圖形,再使用Djikstra’s 算法來(lái)計(jì)算基本塊到目標(biāo)的距離,計(jì)算并輸出基本塊距離信息BB-distance。AFL-Ant 拓展了AFL的插樁,將BB-distance 插樁到目標(biāo)程序的基本塊,在記錄基本塊轉(zhuǎn)換的同時(shí),也記錄所執(zhí)行基本塊的距離累積值,該項(xiàng)目使用 ASAN[18]構(gòu)建。AFL-Ant 的模糊測(cè)試器基于2.40b版本的 AFL,它通過(guò)記錄的基本塊距離累計(jì)值來(lái)計(jì)算當(dāng)前的種子距離,使用本文所設(shè)計(jì)的基于蟻群算法的動(dòng)態(tài)能量調(diào)控方法來(lái)調(diào)控種子能量。同時(shí)設(shè)計(jì)了基于Angr[19]的混合符號(hào)執(zhí)行引擎,這個(gè)引擎是基于Mayhem[20]和S2E[21]拓展和改進(jìn)的。為評(píng)估結(jié)合混合符號(hào)執(zhí)行的導(dǎo)向式模糊測(cè)試器在模糊測(cè)試中對(duì)目標(biāo)區(qū)域的覆蓋效果,本文通過(guò)補(bǔ)丁檢測(cè)來(lái)測(cè)試它的能力。

結(jié)合當(dāng)前最近的導(dǎo)向式模糊測(cè)試器AFLGO所做的工作,本文選取了GNU Diffutils和GNU Binutils[22]兩組工具集作為目標(biāo)程序,選取了它們?cè)谔囟ò姹镜难a(bǔ)丁,將補(bǔ)丁所覆蓋的位置作為目標(biāo)區(qū)域,設(shè)置了相同的初始種子集,分別使用AFL和AFL-Ant對(duì)它們進(jìn)行導(dǎo)向式模糊測(cè)試,測(cè)試時(shí)間設(shè)置為8 h,最終比較它們?cè)谀：郎y(cè)試中所覆蓋的目標(biāo)區(qū)域基本塊的數(shù)量。

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

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

表1 補(bǔ)丁測(cè)試中的基本塊覆蓋情況Table 1 Basic block coverage in patch testing 塊

表1展示了補(bǔ)丁測(cè)試的結(jié)果,Diffutils的補(bǔ)丁基本塊數(shù)量為166塊,在實(shí)驗(yàn)中,AFLGO覆蓋了其中的61塊,而AFL-Ant覆蓋了69塊,相比于AFLGO提高了13.1%;Binutils的補(bǔ)丁基本塊數(shù)量為852塊,AFLGO在實(shí)驗(yàn)中覆蓋了其中的163塊,而AFL-Ant覆蓋了其中的178塊,相比于AFLGO提高了9.2%。合計(jì)AFL-Ant在補(bǔ)丁測(cè)試中對(duì)目標(biāo)區(qū)域基本塊的覆蓋數(shù)量為247塊,相較于AFLGO的224塊提高了10.2%。

圖2統(tǒng)計(jì)了兩個(gè)導(dǎo)向式模糊測(cè)試器測(cè)試結(jié)果的交叉情況,兩個(gè)測(cè)試器總共覆蓋了補(bǔ)丁中的252個(gè)基本塊,其中有219塊是它們共同覆蓋到的。在AFLGO覆蓋的基本塊中,有5個(gè)是AFL-Ant未覆蓋到的,而AFL-Ant能夠覆蓋28個(gè)AFLGO無(wú)法覆蓋到的基本塊。

圖2 補(bǔ)丁測(cè)試覆蓋情況文氏示意圖Fig.2 Venn schematic diagram of patch test coverage

為了評(píng)估AFL-Ant和AFLGO在覆蓋目標(biāo)區(qū)域的效率,在219個(gè)共同覆蓋的基本塊中,隨機(jī)選取了其中的120塊,將其分為了3組作為新的目標(biāo)區(qū)域,用AFL-Ant和AFLGO分別對(duì)每組進(jìn)行導(dǎo)向式模糊測(cè)試,實(shí)驗(yàn)的時(shí)間上限設(shè)置為2 h,比較它們每組實(shí)驗(yàn)中覆蓋所有目標(biāo)所花費(fèi)的時(shí)間。

實(shí)驗(yàn)結(jié)果如表2所示,AFL-Ant在3組實(shí)驗(yàn)中均能覆蓋到目標(biāo)區(qū)域的所有基本塊,而在第3組實(shí)驗(yàn)中,AFLGO未能在2 h內(nèi)覆蓋所有的目標(biāo)基本塊。同時(shí),AFL-Ant覆蓋所有基本塊的時(shí)間均比AFLGO更快,這歸功于它更加高效的動(dòng)態(tài)能量調(diào)控方法以及混合符號(hào)執(zhí)行輔助通過(guò)復(fù)雜節(jié)點(diǎn)能力。

表2 補(bǔ)丁測(cè)試時(shí)間Table 2 Patch test time min

通過(guò)上述實(shí)驗(yàn)可以看出,使用了混合符號(hào)執(zhí)行的AFL-Ant能夠提高對(duì)目標(biāo)區(qū)域的覆蓋率,發(fā)現(xiàn)更多的程序狀態(tài)變換,同時(shí)能夠覆蓋目標(biāo)區(qū)域,更加高效地去挖掘漏洞。

4 結(jié)束語(yǔ)

本文對(duì)混合符號(hào)執(zhí)行技術(shù)在導(dǎo)向式模糊測(cè)試中的應(yīng)用進(jìn)行研究,提出一種新的導(dǎo)向式模糊測(cè)試策略,即使用混合符號(hào)執(zhí)行輔助導(dǎo)向式模糊測(cè)試的測(cè)試用例生成的方法,幫助導(dǎo)向式模糊測(cè)試到達(dá)一些脆弱的區(qū)域。實(shí)驗(yàn)結(jié)果表明,該方法能夠提高導(dǎo)向式模糊測(cè)試對(duì)目標(biāo)區(qū)域的覆蓋率,加快到達(dá)并覆蓋整個(gè)目標(biāo)區(qū)域的速度,提高發(fā)現(xiàn)目標(biāo)區(qū)域漏洞的概率。本文導(dǎo)向式模糊測(cè)試中使用CG和CFGs來(lái)進(jìn)行種子的距離計(jì)算,但未考慮到間接調(diào)用關(guān)系,導(dǎo)致間接調(diào)用的函數(shù)間距離計(jì)算不夠準(zhǔn)確,在未來(lái)工作中將通過(guò)改進(jìn)靜態(tài)分析方法識(shí)別程序中的間接調(diào)用關(guān)系來(lái)完善種子的距離計(jì)算過(guò)程。同時(shí),可將靜態(tài)分析技術(shù)和本文提出的混合符號(hào)執(zhí)行引擎結(jié)合,以更大概率地去觸發(fā)程序漏洞。