AFL能量調(diào)度優(yōu)化方法研究

范永陳

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

0 引言

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

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

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

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

1 背景

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

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

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

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

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

1.2 AFL介紹

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

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

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

2 方法

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

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

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

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

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

根據(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 三個種子，它們的執(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。由此，可以得到三個種子的變異潛力的種子適應(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ī)會分配給隊(duì)列中其他種子，提高模糊測試效率。

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

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

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

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

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

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

能量回收算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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