AFL能量調度優化方法研究

范永陳

（四川大學網絡空間安全學院，成都 610065）

0 引言

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

當前模糊測試技術可以劃分為基于生成的模糊測試和基于突變的模糊測試。基于生成的模糊測試通常需要測試人員提供目標程序輸入的格式信息或語法知識。模糊測試程序根據輸入的格式信息或相關語法自動生成程序輸入進行漏洞檢測。這種方式使得程序輸入能夠通過目標程序校驗代碼，到達目標程序深層代碼區域。但這種方式需要人工編寫規則來描述程序輸入的格式，并且目標程序不同需要的格式描述文件也不相同。因此這種方式適用于結構化的程序輸入，如HTML、Java Script 等，代表模糊器有AFLsmart。基于突變的模糊測試則不需要熟悉輸入文件的格式。模糊測試工具通過一組預定義的變異規則來生成新的程序輸入，代表模糊器有AFL、AFLFast、EcoFuzz等。

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

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

1 背景

由于本文的方法是在AFL 上實現的，因此本節首先介紹覆蓋率引導的灰盒模糊測試的通用流程，然后對AFL的相關背景進行介紹。

1.1 覆蓋率引導的灰盒模糊測試

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

圖1 覆蓋率引導的模糊測試工具基本流程

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

1.2 AFL介紹

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

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

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

2 方法

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

2.1 變異潛力適應度函數

變異潛力適應度函數用來衡量種子文件變異潛力，本文將根據種子的變異潛力為種子分配能量。根據實驗和漏洞挖掘經驗，本文總結出兩條模糊測試過程中的啟發式規則。

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

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

根據上述啟發式規則，定義種子變異潛力適應度函數如公式（1）所示。

其中，表示種子執行路徑上所有未探索鄰邊的和，表示種子執行路徑上所有的鄰邊之和。表示執行路徑上發現的新邊數量，即執行路徑上執行次數為1 的邊的數量，表示種子執行路徑上總的邊數量。

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

圖2 變異潛力適應度計算

2.2 基于變異潛力適應度的能量分配

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

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

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

種子突變有效性定義為突變產生的有趣測試用例數除以種子突變產生的測試用例總數，計算方式如公式（4）所示。

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

其中，表示當前模糊測試的執行時間，單位為分鐘，是系數，可以根據不同的應用程序進行設置，本文默認為1。

補償之后種子突變有效性計算方式如公式（6）所示。

當前測試過程中已經進行模糊測試的種子的平均突變有效性則通過公式（7）進行計算。

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

能量回收算法

算法1的執行流程如下。

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

（2）當前種子消耗的能量達到energy 的75%時，通過getAverEffect 函數按照公式（7）計算當前已經進行過測試的種子的平均突變有效性。通過getCurEffect函數按照公式（6）計算當前種子的突變有效性。

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

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

2.4 系統總體流程

本文模糊測試系統中能量調度優化總體流程如圖3所示，整個系統的工作步驟如下。

圖3 能量調度優化總體流程

（1）首先根據種子選擇策略選取用于測試的種子文件，然后根據選擇的種子采集變異潛力適應度函數所需的相關信息，再進行變異潛力適應度計算。

（2）將變異潛力適應度與AFL 原有的能量公式結合，根據公式（2）計算種子能量。

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

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

3 實驗及分析

本文在AFL 2.52b 的基礎上實現了模糊測試工具EnFuzzer，使用EnFuzzer 與AFL 2.52b 進行了對比實驗。本實驗的運行環境為64 位Ubuntu16.04 操作系統，內存為4 GB，CPU 為AMD Ryzen 5-4600G。每個程序每次運行時間為24 小時，測試結果取5 次測試的平均值。選取了xmllint、cxxfilt、swftophp、objdump、nm-new這5個程序作為實驗對象。

針對這5個目標程序，對應的實驗結果如表1所示。

表1 實驗結果對比及參數信息

實驗結果表明，EnFuzzer 在這5個目標程序上的路徑發現數量和崩潰發現數量相較于AFL都有一定的提升。其中，對于xmllint 總路徑數量提升了32.36%， 獨特崩潰數量提升了39.06%；對于cxxfilt 總路徑數量提升了19.20%，獨特崩潰數量提升了19.75%；對于swftophp 總路徑數量提升了15.47%，獨特崩潰數量提升了26.60%；對于objdump 總路徑數量提升了9.53%，獨特崩潰數量提升了6.67%；對于nmnew 總路徑數量提升了18.40%，獨特崩潰數量提升了66.66%。總體來說，Enfuzzer 能提高灰盒模糊測試的路徑發現數量和獨特崩潰數量，證明了本文方法的有效性。

4 結語

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