范永陳

（四川大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，成都 610065）

0 引言

模糊測(cè)試技術(shù)（fuzzing）是當(dāng)前最流行的漏洞檢測(cè)技術(shù)。其基本原理是將種子文件進(jìn)行隨機(jī)變異，生成大量新的程序輸入，然后在目標(biāo)程序中執(zhí)行，跟蹤目標(biāo)程序運(yùn)行狀態(tài)信息，最后對(duì)目標(biāo)程序崩潰信息進(jìn)行分析來(lái)發(fā)現(xiàn)程序漏洞。然而傳統(tǒng)的模糊測(cè)試技術(shù)由于缺乏引導(dǎo)，嚴(yán)重影響了漏洞檢測(cè)效率。由此誕生了灰盒模糊測(cè)試技術(shù)（gray-box fuzzing），灰盒模糊測(cè)試借助輕量級(jí)的程序分析，獲取程序運(yùn)行時(shí)信息，借助運(yùn)行時(shí)信息對(duì)模糊測(cè)試過(guò)程進(jìn)行引導(dǎo)，提升漏洞檢測(cè)效率。

當(dāng)前模糊測(cè)試技術(shù)可以劃分為基于生成的模糊測(cè)試和基于突變的模糊測(cè)試?；谏傻哪：郎y(cè)試通常需要測(cè)試人員提供目標(biāo)程序輸入的格式信息或語(yǔ)法知識(shí)。模糊測(cè)試程序根據(jù)輸入的格式信息或相關(guān)語(yǔ)法自動(dòng)生成程序輸入進(jìn)行漏洞檢測(cè)。這種方式使得程序輸入能夠通過(guò)目標(biāo)程序校驗(yàn)代碼，到達(dá)目標(biāo)程序深層代碼區(qū)域。但這種方式需要人工編寫(xiě)規(guī)則來(lái)描述程序輸入的格式，并且目標(biāo)程序不同需要的格式描述文件也不相同。因此這種方式適用于結(jié)構(gòu)化的程序輸入，如HTML、Java Script 等，代表模糊器有AFLsmart?；谕蛔兊哪：郎y(cè)試則不需要熟悉輸入文件的格式。模糊測(cè)試工具通過(guò)一組預(yù)定義的變異規(guī)則來(lái)生成新的程序輸入，代表模糊器有AFL、AFLFast、EcoFuzz等。

本文基于突變的灰盒模糊測(cè)試進(jìn)行研究。該方法認(rèn)為能夠探索到新的執(zhí)行路徑的測(cè)試用例具有較高的價(jià)值，將其保存到種子隊(duì)列進(jìn)行后續(xù)測(cè)試，不能探索到新的執(zhí)行路徑的測(cè)試用例直接丟棄。AFL 為此類(lèi)模糊器的代表，它在漏洞檢測(cè)方面取得了非常好的效果。AFL 在進(jìn)行種子選擇后，會(huì)立即進(jìn)行能量調(diào)度。能量調(diào)度的目的是在模糊過(guò)程中為種子分配能量，從而確定種子的變異次數(shù)。近年來(lái)的研究表明，能量調(diào)度對(duì)模糊測(cè)試系統(tǒng)至關(guān)重要，合理的能量分配可以有效地提高新路徑的發(fā)現(xiàn)速度。如果一個(gè)種子的能量被過(guò)度分配，會(huì)導(dǎo)致其占用過(guò)多的測(cè)試時(shí)間，使得其他種子的測(cè)試時(shí)間不足。相反，如果種子的能量分配不足，就會(huì)不利于新路徑的發(fā)現(xiàn)和潛在的漏洞檢測(cè)。

目前AFL 存在能量分配不合理的問(wèn)題。具體來(lái)講，AFL 的能量分配取決于種子執(zhí)行時(shí)間、位圖大小、種子文件的平均大小等因素，沒(méi)有將種子執(zhí)行路徑與控制流圖相結(jié)合來(lái)考慮種子的能量分配，并且沒(méi)有考慮種子的突變有效性，導(dǎo)致變異潛力大的種子能量分配不足或者變異潛力小的種子分配過(guò)多能量，影響模糊測(cè)試效率。

1 背景

由于本文的方法是在AFL 上實(shí)現(xiàn)的，因此本節(jié)首先介紹覆蓋率引導(dǎo)的灰盒模糊測(cè)試的通用流程，然后對(duì)AFL的相關(guān)背景進(jìn)行介紹。

1.1 覆蓋率引導(dǎo)的灰盒模糊測(cè)試

覆蓋率引導(dǎo)的模糊測(cè)試工具測(cè)試流程如圖1所示。

圖1 覆蓋率引導(dǎo)的模糊測(cè)試工具基本流程

在模糊測(cè)試開(kāi)始之前，需要將目標(biāo)程序中每一個(gè)基本塊進(jìn)行插樁。然后將初始種子集和插樁后的目標(biāo)程序送入模糊器進(jìn)行測(cè)試。測(cè)試開(kāi)始時(shí)，測(cè)試工具中只包含初始種子集，模糊測(cè)試工具按照種子選擇策略進(jìn)行種子選擇。選取種子文件之后，會(huì)為選擇的種子文件分配相應(yīng)的能量，即變異的次數(shù)。然后種子進(jìn)行變異生成大量測(cè)試用例，將生成的測(cè)試用例用于執(zhí)行目標(biāo)程序，并且跟蹤目標(biāo)程序的運(yùn)行狀態(tài)。根據(jù)目標(biāo)程序的運(yùn)行狀態(tài)和測(cè)試用例的執(zhí)行路徑，來(lái)判斷當(dāng)前輸入是否是有趣的測(cè)試用例，有趣的測(cè)試用例將被加入到種子隊(duì)列，其它測(cè)試用例將被丟棄。當(dāng)一個(gè)種子文件測(cè)試完成之后，繼續(xù)從種子隊(duì)列中選擇下一個(gè)種子進(jìn)行測(cè)試。模糊測(cè)試工具按照上述流程循環(huán)進(jìn)行測(cè)試，直到到達(dá)規(guī)定的時(shí)間或者接收到停止指令。

1.2 AFL介紹

在覆蓋率引導(dǎo)的模糊測(cè)試工具中，AFL 是最具代表性的一款模糊測(cè)試工具。近年來(lái)，大量的模糊測(cè)試工具都在AFL 的基礎(chǔ)上進(jìn)行改進(jìn)，如Fairfuzz、FuzzFactory等。AFL 使用了大量的系統(tǒng)底層編程技巧，提高了測(cè)試過(guò)程的執(zhí)行效率，并且AFL 使用了邊覆蓋作為代碼覆蓋率的度量方式。相較于基本塊作為代碼覆蓋率的度量方式，邊覆蓋方式能記錄更加豐富的程序執(zhí)行信息，更容易發(fā)現(xiàn)目標(biāo)程序的潛在漏洞。

在模糊測(cè)試開(kāi)始之前，AFL 首先會(huì)插樁編譯目標(biāo)程序。插樁是指向目標(biāo)程序的每一個(gè)基本塊中插入一段樁代碼用于記錄相關(guān)信息。具體過(guò)程如下：

其中cur_block 和pre_block 分別代表當(dāng)前基本塊和前一個(gè)基本塊的ID?；緣K的樁代碼中包含一個(gè)0-65535 的隨機(jī)值，表示每個(gè)基本塊的ID。當(dāng)測(cè)試用例的執(zhí)行路徑從一個(gè)基本塊跳轉(zhuǎn)另一個(gè)基本塊時(shí)，會(huì)將這兩個(gè)基本塊的ID 進(jìn)行異或得到一個(gè)哈希值，這個(gè)哈希值就表示這兩個(gè)基本塊之間的邊。為了區(qū)分兩個(gè)基本塊的執(zhí)行順序，AFL 在計(jì)算當(dāng)前邊的哈希值時(shí)會(huì)對(duì)前一個(gè)基本塊的標(biāo)識(shí)值右移一位。vergin_map 是一個(gè)64KB 長(zhǎng)度的共享內(nèi)存。它由模糊測(cè)試主程序和目標(biāo)程序共享，模糊測(cè)試主程序能夠通過(guò)共享內(nèi)存及時(shí)獲取目標(biāo)程序執(zhí)行過(guò)程中的相關(guān)信息。AFL只需將vergin_map中的信息與測(cè)試用例執(zhí)行路徑信息進(jìn)行比對(duì)，就能知道當(dāng)前測(cè)試用例是否有新的邊覆蓋。如果有新的邊覆蓋產(chǎn)生則將該測(cè)試用例添加到種子隊(duì)列，如果沒(méi)有新的邊覆蓋則將該測(cè)試用例丟棄。

2 方法

本文通過(guò)變異潛力適應(yīng)度函數(shù)和突變有效性能量回收算法來(lái)進(jìn)行種子的能量分配與回收，提高模糊測(cè)試效率。

2.1 變異潛力適應(yīng)度函數(shù)

變異潛力適應(yīng)度函數(shù)用來(lái)衡量種子文件變異潛力，本文將根據(jù)種子的變異潛力為種子分配能量。根據(jù)實(shí)驗(yàn)和漏洞挖掘經(jīng)驗(yàn)，本文總結(jié)出兩條模糊測(cè)試過(guò)程中的啟發(fā)式規(guī)則。

（1）啟發(fā)式規(guī)則1。如果一個(gè)種子的執(zhí)行路徑上有更多未探索鄰邊，那么這條路徑上的突變更可能會(huì)帶來(lái)新的邊覆蓋。

（2）啟發(fā)式規(guī)則2。如果一個(gè)種子的執(zhí)行路徑上有更多新探索的邊，那么這條路徑上的突變更可能會(huì)帶來(lái)新的邊覆蓋。

根據(jù)上述啟發(fā)式規(guī)則，定義種子變異潛力適應(yīng)度函數(shù)如公式（1）所示。

其中，表示種子執(zhí)行路徑上所有未探索鄰邊的和，表示種子執(zhí)行路徑上所有的鄰邊之和。表示執(zhí)行路徑上發(fā)現(xiàn)的新邊數(shù)量，即執(zhí)行路徑上執(zhí)行次數(shù)為1 的邊的數(shù)量，表示種子執(zhí)行路徑上總的邊數(shù)量。

圖2表示程序的控制流圖，下面使用圖中的實(shí)例解釋基于變異潛力的適應(yīng)度的計(jì)算方法。假設(shè)有a1、a2、a3 三個(gè)種子，它們的執(zhí)行路徑按照順序分別為a-g-n-l-j-k-m、a-g-h-i-j-km 和a-b-c-d-k-m。a1 執(zhí)行路徑上新發(fā)現(xiàn)的邊為g-n、n-l、l-j。a2 執(zhí)行路徑上新發(fā)現(xiàn)的邊為g-h、h-i、i-j。a3 執(zhí)行路徑上新發(fā)現(xiàn)的邊為ab、b-c、c-d、d-k。由此，可以得到三個(gè)種子的變異潛力的種子適應(yīng)度。

圖2 變異潛力適應(yīng)度計(jì)算

2.2 基于變異潛力適應(yīng)度的能量分配

將AFL 給種子分配的能量表示為energy（），factor表示基于變異潛力適應(yīng)度的能量調(diào)節(jié)因子，取值范圍為［1，16］。energy（）表示最終種子獲得的能量，其計(jì)算方式如公式（2）所示。

2.3 基于突變有效性的能量回收

能量回收算法回收變異效率低下的種子文件的剩余能量，將變異機(jī)會(huì)分配給隊(duì)列中其他種子，提高模糊測(cè)試效率。

種子突變有效性定義為突變產(chǎn)生的有趣測(cè)試用例數(shù)除以種子突變產(chǎn)生的測(cè)試用例總數(shù)，計(jì)算方式如公式（4）所示。

由于模糊測(cè)試工具在一開(kāi)始很容易生成有趣的測(cè)試用例，但隨著時(shí)間的推移新路徑的發(fā)現(xiàn)越來(lái)越困難，導(dǎo)致了生成有趣測(cè)試用例的難度增加。通過(guò)以往的模糊測(cè)試經(jīng)驗(yàn)發(fā)現(xiàn)AFL 路徑發(fā)現(xiàn)速度的倒數(shù)基本上隨測(cè)試時(shí)間呈指數(shù)增長(zhǎng)，所以通過(guò)補(bǔ)償權(quán)重compen 對(duì)后續(xù)測(cè)試的種子突變有效性進(jìn)行補(bǔ)償。compen 的計(jì)算方式如公式（5）所示，取值范圍為［1，64］。

其中，表示當(dāng)前模糊測(cè)試的執(zhí)行時(shí)間，單位為分鐘，是系數(shù)，可以根據(jù)不同的應(yīng)用程序進(jìn)行設(shè)置，本文默認(rèn)為1。

補(bǔ)償之后種子突變有效性計(jì)算方式如公式（6）所示。

當(dāng)前測(cè)試過(guò)程中已經(jīng)進(jìn)行模糊測(cè)試的種子的平均突變有效性則通過(guò)公式（7）進(jìn)行計(jì)算。

基于突變有效性的能量回收方法如算法1所示：

能量回收算法

算法1的執(zhí)行流程如下。

（1）首先通過(guò)calculateEnergy 函數(shù)按照公式（2）為種子分配能量energy。

（2）當(dāng)前種子消耗的能量達(dá)到energy 的75%時(shí)，通過(guò)getAverEffect 函數(shù)按照公式（7）計(jì)算當(dāng)前已經(jīng)進(jìn)行過(guò)測(cè)試的種子的平均突變有效性。通過(guò)getCurEffect函數(shù)按照公式（6）計(jì)算當(dāng)前種子的突變有效性。

（3）如果當(dāng)前種子的突變有效性大于總體平均突變有效性，即curEffect＞averEffect。表示當(dāng)前種子有較大的突變價(jià)值，需要繼續(xù)測(cè)試。

（4）如果當(dāng)前種子的突變有效性小于等于總體平均突變有效性，即curEffect≤averEffect。表示當(dāng)前種子突變價(jià)值不足，則直接跳過(guò)當(dāng)前種子，減少不必要的能量消耗。

2.4 系統(tǒng)總體流程

本文模糊測(cè)試系統(tǒng)中能量調(diào)度優(yōu)化總體流程如圖3所示，整個(gè)系統(tǒng)的工作步驟如下。

圖3 能量調(diào)度優(yōu)化總體流程

（1）首先根據(jù)種子選擇策略選取用于測(cè)試的種子文件，然后根據(jù)選擇的種子采集變異潛力適應(yīng)度函數(shù)所需的相關(guān)信息，再進(jìn)行變異潛力適應(yīng)度計(jì)算。

（2）將變異潛力適應(yīng)度與AFL 原有的能量公式結(jié)合，根據(jù)公式（2）計(jì)算種子能量。

（3）分配能量后，將能量回收算法與能量消耗過(guò)程相結(jié)合，防止種子在探索具有復(fù)雜約束條件的程序分支的過(guò)程中產(chǎn)生過(guò)多的無(wú)效變異，影響測(cè)試效率。

（4）若沒(méi)有收到停止測(cè)試指令，則跳轉(zhuǎn)到步驟（1）。

3 實(shí)驗(yàn)及分析

本文在AFL 2.52b 的基礎(chǔ)上實(shí)現(xiàn)了模糊測(cè)試工具EnFuzzer，使用EnFuzzer 與AFL 2.52b 進(jìn)行了對(duì)比實(shí)驗(yàn)。本實(shí)驗(yàn)的運(yùn)行環(huán)境為64 位Ubuntu16.04 操作系統(tǒng)，內(nèi)存為4 GB，CPU 為AMD Ryzen 5-4600G。每個(gè)程序每次運(yùn)行時(shí)間為24 小時(shí)，測(cè)試結(jié)果取5 次測(cè)試的平均值。選取了xmllint、cxxfilt、swftophp、objdump、nm-new這5個(gè)程序作為實(shí)驗(yàn)對(duì)象。

針對(duì)這5個(gè)目標(biāo)程序，對(duì)應(yīng)的實(shí)驗(yàn)結(jié)果如表1所示。

表1 實(shí)驗(yàn)結(jié)果對(duì)比及參數(shù)信息

實(shí)驗(yàn)結(jié)果表明，EnFuzzer 在這5個(gè)目標(biāo)程序上的路徑發(fā)現(xiàn)數(shù)量和崩潰發(fā)現(xiàn)數(shù)量相較于AFL都有一定的提升。其中，對(duì)于xmllint 總路徑數(shù)量提升了32.36%， 獨(dú)特崩潰數(shù)量提升了39.06%；對(duì)于cxxfilt 總路徑數(shù)量提升了19.20%，獨(dú)特崩潰數(shù)量提升了19.75%；對(duì)于swftophp 總路徑數(shù)量提升了15.47%，獨(dú)特崩潰數(shù)量提升了26.60%；對(duì)于objdump 總路徑數(shù)量提升了9.53%，獨(dú)特崩潰數(shù)量提升了6.67%；對(duì)于nmnew 總路徑數(shù)量提升了18.40%，獨(dú)特崩潰數(shù)量提升了66.66%?？傮w來(lái)說(shuō)，Enfuzzer 能提高灰盒模糊測(cè)試的路徑發(fā)現(xiàn)數(shù)量和獨(dú)特崩潰數(shù)量，證明了本文方法的有效性。

4 結(jié)語(yǔ)

灰盒模糊測(cè)試是當(dāng)前最為流行的漏洞挖掘方法。針對(duì)AFL 模糊測(cè)試工具能量分配不合理的問(wèn)題，本文提出基于變異潛力適應(yīng)度函數(shù)的能量分配策略和基于突變有效性的能量回收算法，并基于該方法實(shí)現(xiàn)了EnFuzzer。實(shí)驗(yàn)結(jié)果表明本文所提方法具有一定的有效性。在下一步的研究中，將考慮與污點(diǎn)分析、符號(hào)執(zhí)行等技術(shù)相結(jié)合，對(duì)模糊測(cè)試變異策略進(jìn)行改進(jìn)，降低隨機(jī)變異的盲目性，提升灰盒模糊測(cè)試工具的漏洞檢測(cè)能力。