基于聚類和新覆蓋信息的模糊測試改進①

程 亮, 王化磊, 張 陽, 孫曉山

1(中國科學院大學, 北京 100049)

2(中國科學院 軟件研究所 可信計算與信息保障實驗室, 北京 100190)

1 引言

隨著計算機和網絡技術的發展, 軟件與我們的生活和工作的關系越來越密切. 然而軟件復雜的功能使得軟件中不可避免地存在漏洞. 在模糊測試首次被提出的論文[1]中提到“常用系統中可能會潛伏著嚴重的漏洞”. 比如: 2010年披露的震網蠕蟲漏洞[2]是第一種攻擊工業控制系統的病毒; 2015年6月, 三星被爆出了高危的輸入法漏洞. 該漏洞影響全球超過6億的三星手機用戶[3]. 2015年7月Android被爆出存在Stagefright高危漏洞, 約95%的安卓設備受到該漏洞影響[3].2020年8月, 研究人員發現CSP繞過漏洞(CVE-2020-6519[4]), 該漏洞使攻擊者可以完全繞過Chrome 73版至83版的CSP規則, 數十億的用戶可能會受到影響.

軟件安全一直是安全人員研究的重點, 當前主流的程序安全分析方法有: 污點分析、符號執行、代碼審計和模糊測試等. 如何高效地發掘軟件可能存在的漏洞一直是這些主流安全分析方法研究的重點.

污點分析技術[5]可以分為動態污點分析和靜態污點分析, 靜態污點在無法獲取源代碼時, 靜態污點分析的精確性將會大大降低. 動態污點分析在運行時具有很大的開銷, 難以實際分析規模較大的軟件. 符號執行系統地探索許多可能的執行路徑, 而不需要具體的輸入, 通過抽象地將輸入表示為符號, 利用約束求解器來構造可能滿足條件的輸入. 符號執行的缺點是處理像循環這樣的語言結構時可能會成倍地增加執行狀態的數量, 從而出現路徑爆炸的問題[6-8]. 代碼審計是一種對源代碼的全面分析技術, 但是代碼審計非常依賴安全人員自身的經驗. 綜上分析, 符號執行等方法雖然通過提取豐富的代碼細節達到程序分析的功能, 但是由于其效率等方面的原因, 在程序安全性分析方面存在較多的局限. 模糊測試[9]通過隨機變異種子或者基于規則生成種子對程序進行測試. 模糊測試通常分為白盒模糊測試、灰盒模糊測試和黑盒模糊測試[10-13]. 白盒模糊測試提取程序詳細的運行時信息, 但是開銷很大,總體效率很低. 黑盒模糊測試完全忽略了程序的內在信息, 雖然具有較快的運行速度, 但是準確性很低, 總體漏洞發現能力較弱. 而灰盒模糊測試兼顧了兩者的優勢, 通過靜態代碼插樁的方式獲取程序運行時覆蓋情況, 并用獲得的信息指導種子變異方式, 以盡快擴大測試的覆蓋率, 相較于其他方法能夠更快地發現程序潛在的漏洞. 因此, 灰盒模糊測試已成為目前主流的模糊測試方法, 其中典型工具—AFL (American fuzzy loop)[14]已成為學術界和工業界進行模糊測試的事實標準工具, 我們的工作也基于AFL實現.

雖然灰盒模糊測試在發現漏洞方面具有一定的優勢. 但是其采用的隨機性算法具有極大的盲目性, 所以仍然存在進一步改進的空間.

現有的針對基于AFL灰盒模糊測試的改進工具將全部或過多的能量集中非確定性變異階段, 加大了變異的盲目性, 使其難以求解復雜的條件約束;并且在種子能量分配階段忽視了種子探索新分支的能力, 使得過多的能量消耗在沒有價值的種子.

針對上述問題, 我們在模糊測試工具AFL 2.52b進行了改進, 通過對關鍵變異位置持續性變異和能量分配策略的優化, 提高模糊測試發現程序覆蓋和程序潛在漏洞的能力, 我們的設計有以下幾個特點:

1)提取有效變異位置. 在種子變異階段, 首先對種子執行非確定性變異. 對于產生新覆蓋的非確定性變異種子, 我們提取變異的組合位置并認為該組合位置中存在有效變異位置(我們定義變異后能夠產生有效新覆蓋的單一位置是有效變異位置), 再利用聚類算法確定組合變異中有效變異位置, 最后針對有效變異位置以及其后續位置進行持續的細粒度變異.

2)利用新覆蓋信息評估種子. 對于每個發現新覆蓋的種子, 保留新發現覆蓋的信息. 在種子評分階段,根據種子的新覆蓋信息對種子進行評分.

3)提取程序靜態信息. 模糊測試改進往往是在缺少程序信息的前提下進行的策略上的優化, 這種優化存在局限性; 而使用污點分析或者符號執行等方式提取程序信息的方法[15-18], 往往因為分析效率較低而影響模糊測試工具總體的效率. 因此我們提取了輕量級的程序靜態信息, 在模糊測試階段結合靜態信息對種子的能量分配策略進行更加準確的計算.

我們在主流的模糊測試工具AFL的設計思路上完成了改進, 并實現了改進后的模糊測試工具AgileFuzz經過實驗驗證, AgileFuzz能夠在相同的時間內發現更多的程序分支覆蓋, 并且能夠挖掘到新的程序漏洞.

2 背景

本節主要以AFL為例介紹典型灰盒模糊測試的工作流程以及路徑統計方式.

2.1 AFL工作流程

AFL主函數是一個條件為true的while循環, 只有用戶主動停止模糊測試工作, 測試才會結束. AFL的工作流程如圖1所示, 核心步驟如下: 1)待測目標程序和程序的輸入文件作為AFL啟動時的原始輸入, 初始輸入經過運行后會加入種子庫中參與后續的模糊測試. 2) AFL每次執行測試, 都會從種子隊列中選擇1個種子, 根據該種子的執行時間、種子大小、路徑覆蓋數量、執行次數等進行種子評分, 評分越高的種子在非確定性變異階段會進行更多次的變異. 并且, AFL根據路徑不同保存了很多種子, 但是AFL會將單一分支執行最快的種子標記為favored, 在種子被選擇后, 不是favored標記的種子會以較大的概率跳過執行. 3)種子經過變異后, 得到的新種子作為待測程序的輸入,AFL監視每個種子執行過程中程序是否發生崩潰, 如果待測程序發生崩潰, 則種子被保存在crash種子隊列. 4) AFL還記錄每個種子在程序執行過程中的路徑覆蓋情況, 如果產生新的覆蓋則將種子加入正常樣本隊列, 然后參與后續的模糊測試工作.

圖1 AFL工作流程圖

2.2 AFL路徑統計方式

AFL通過插樁方式獲取程序運行時的執行路徑信息. 對于有源碼的程序, AFL在編譯程序時將插樁代碼插入程序的每個基本塊中, 具體流程如下: AFL在每個基本塊入口處插入0-65535范圍的隨機數以及特定功能的函數afl_maybe_log;如果程序執行了該基本塊,afl_maybe_log函數會將插入基本塊的隨機數與前一個執行的基本塊的隨機數進行異或操作, 運算的結果作為覆蓋信息寫入共享內存. 共享內存是一塊64 KB的內存空間, 可以統計65 536條分支轉移信息, AFL不僅記錄分支轉移是否發生, 還會記錄分支轉移執行的次數, 因為同一個分支轉移, 可能因為不同的執行次數出現不用的程序狀態. 對于沒有源碼的程序, AFL使用運行時插樁技術統計程序執行路徑, 插樁的邏輯與靜態插樁方式相同.

3 方案設計

如圖2所示, 其中實線方框為AFL的標準功能模塊, 使用虛線方框的部分是我們增加或改進的模塊, 主要包括3個部分: 第1部分是對模糊測試變異策略的改進, 第2部分是利用聚類算法確定關鍵變異位置, 第3部分是結合靜態分析和新覆蓋信息的種子評分策略調整.

圖2 改進后的模糊測試工作流程

3.1 變異策略改進

AFL在種子變異階段分為確定性變異和非確定性變異. 每個被選中的種子都會執行一次確定性變異, 在確定性變異階段會對種子進行比特位粒度的變異, 所以在確定性變異階段十分耗時. 事實上, 種子的很多位置都是無效的變異位置, 即無論進行何種變異都無法產生新的覆蓋. MOPT和EcoFuzz考慮到確定性變異耗時, 所以選擇直接跳過了確定性變異, 但是只通過非確定性變異, 將會使得模糊測試變異更加盲目和隨機.

(1) 確定種子關鍵變異位置. 在調整后的變異策略中, 種子變異階段只對種子的部分關鍵位置進行確定性變異. 核心步驟是確定種子的關鍵位置. 具體來說,當選中一個種子后, 首先進行非確定性變異, 如果非確定性變異生成的種子訪問了新的分支覆蓋, 并不會在保存種子后直接進行下一次變異操作, 而是分析產生該種子的變異過程. 通過分析, 可以確定組合變異位置中有效的變異位置, 而有效的變異位置將會記作新種子的關鍵位置.

(2) 選擇性確定性變異. 在確定關鍵位置w后, 變異前的種子和變異后的種子會針對關鍵位置進行不同的變異操作. 對變異前的種子的w位置進行與AFL相同的確定性變異, 對于記錄關鍵位置的新種子, 如果關鍵位置的字段長度小于m個字節, 那么當該種子被選中進行變異時, 首先對該關鍵位置的后續n個位置進行更加細粒度的確定性變異, 與AFL原有的確定性變異不同, 細粒度的確定性變異會將選中的位置(字節)變異成所有可能的結果. 經過多次實驗測試, m和n的值取2時, 總體效果較好.

3.2 聚類確定關鍵變異位置

關鍵位置的長度直接影響變異的效率. 如果將產生新覆蓋的種子變異過程中的所有組合變異位置都看作關鍵位置, 然后對這些進行確定性變異, 仍然存在較多的無效變異.

為了縮小關鍵位置的長度, 使用聚類算法對離散的組合變異位置進行聚類. 在文件結構中, 字段是連續的一段內容, 所以在一個文件中, 距離越近的位置越可能屬于同一字段. 如圖3所示, 文件A的組合變異M個位置(其中包括藍色標記和紅色位置標記的位置,而且紅色位置為關鍵變異位置)得到的種子B訪問了新的覆蓋, 對種子B變異的位置進行聚類操作-將離散的變異位置聚類為N個字段, 根據N個字段生成N個新的種子, 每個新種子只有對應字段的內容與原文件不同. 如果種子Ni訪問了新的覆蓋, 那么Ni種子對應的變異字段就是關鍵的變異字段.

圖3 對組合變異位置進行聚類

為了完成變異位置聚類, 我們使用Meanshift算法.使用該算法的原因有兩點: 1)該算法是基于密度的聚類算法, 2)聚類之前不需要指定類的數量. Meanshift算法的核心思想是通過不斷移動樣本點, 使其向密度更大的區域移動, 直到滿足某一條件, 此時該點就是樣本點的收斂點, 收斂到同一點則被認為屬于同一族類.對于變異位置p, 其偏移向量計算方式如式(1)所示,其中, pi表示所有變異位置點集中到p點距離小于l的所有點.

聚類算法具體步驟如下:

1)隨機選擇未被分類的變異位置, 作為中心點P.

2)找出離中心點P距離L范圍的所有變異點, 這些點記作集合M.

3)計算中心點P與集合M中所有點的向量, 將這些向量相加得到偏移向量M.

4)將中心點P加上向量M得到新的中心點.

5)重復步驟2)-4), 直到偏移向量滿足設定的閾值,保存此時的中心點.

6)重復步驟1)-5)直到所有點都完成分類.

7)根據每個類, 對每個點的訪問頻率, 取訪問頻率最大的那個類, 作為當前點集的所屬類.

算法1. 基于聚類的確定性變異優化方法輸入: 非確定性變異后產生新覆蓋的種子seed_son和變異前的種子seed輸出: 確定性變異產生的新覆蓋的種子1 diff_points=get_diff_point(seed, seed_son)2 cluster_points=cluster(diff_ponts)3 for cluster in cluster_points:4 seed_single_cluster=generate_seed_by_cluster(cluster):5 if(is_new_path(seed_single)):6 seeds_deter=deter_variate(cluster, seed):7 while seed_deter in seeds_deter:8 fuzzy_run(seed_deter)9 end while 10 end if 11 end for

3.3 新覆蓋與靜態分析進行種子評分

在AFL的種子評分中, 會根據種子的總分支覆蓋數量進行能量分配, 這種方式導致能量分配不合理. 我們調整種子評分策略, 將種子新發現的分支數量作為評分依據. 并且我們對待測二進制程序進行靜態分析,提取基本塊轉移信息. 這樣做的目的是因為并不是每個分支轉移都存在潛在未發現的分支轉移.

如圖4所示, 對于每個基本塊轉移, 如: branch 1,我們記錄通過該分支轉移到達基本塊后, 可能存在的后續基本塊轉移, 即對于branch 1, 我們記錄branch 1-1和branch 1-2的信息, 我們把branch 1-1和branch 1-2記作分支branch 1的子分支轉移. 注意的是, 雖然基本塊是連續指令的集合, 但是branch 1-1或branch 1-2可能并不同時存在或都不存在. 這種情況發生在某基本塊子節點的父節點超過一個時, 其子節點即使只有一個, 但是仍然是一個獨立的基本塊. 通過靜態分析, 我們可以得到每個基本塊轉移的子分支轉移, 如果某個分支的子分支轉移數量為2, 我們認為該分支轉移對發現新覆蓋是有價值的, 將會對種子評分產生增益效果.

圖4 基本塊轉移示意圖

所以在種子評分階段, 具體步驟如下:

1) 對于待測程序, 通過靜態分析獲取每個基本塊轉移的子分支轉移信息, 保存在文件中, 在啟動模糊測試測試時, 該文件作為分支附加信息提供.

2) 對于每個新加入隊列的種子, 比較其分支覆蓋與總分支覆蓋的差異, 得到新發現的分支覆蓋數量和具體分支編號.

3) 在種子評分階段, 計算種子分支覆蓋中是新覆蓋且對應分支有兩個子分支的數量, 記作value_branch_num.

4) 種子A的評分使用式(2)進行計算, 使用log函數是為了避免分支覆蓋數量對種子能量進行成倍的增益, 并且經過多次實驗驗證, ln函數作為計算種子能量總體實驗效果較好. 根據公式可知, 當種子的新覆蓋數量為0時, 最低能量值為1.

4 實驗評估

我們在AFL 2.52b的基礎上實現了改進策略, 得到了改進后的模糊測試工具AgileFuzz. 我們的評估主要回答下面4個問題:

1) 產生新覆蓋的非確定性變異的組合位置中是否存在關鍵位置? 如果存在, 存在的比例是多少? 對關鍵位置進行確定性變異, 是否能夠發現新的覆蓋?

2) 與非確定性變異相比, 對聚類得到關鍵位置進行細粒度持續變異如何能夠更快地發現新覆蓋?

3) AgileFuzz在實際程序中發現程序覆蓋的能力與現有的模糊測試改進工具對比如何?

4) AgileFuzz是否能夠發現真實程序程序中的漏洞?

4.1 “關鍵位置”分析與統計

非確定性變異階段對種子的隨機組合位置進行變異, 變異后的種子產生新覆蓋可能有兩個原因: 1)組合變異產生新覆蓋, 單一位置變異并不能產生; 2)組合變異中, 變異了“關鍵位置”, 而且即使只變異該位置, 也可以產生新覆蓋. 其中, 我們稱這種“關鍵位置”為單一有效變異位置. 我們統計在模糊測試過程中, 產生新覆蓋的非確定性變異包括多少“關鍵位置”以及針對“關鍵位置”變異仍然能夠產生新覆蓋的數量. 實驗測試選擇libxml2 (xmllint)、binutils (readelf)和harfbuzz(test)這3組程序, 這3組程序常用作模糊測試工具的測評, 比較具有代表性. 在相同的實驗環境下, 對3個程序進行3組重復性實驗, 每組實驗進行72 h, 最終取平均結果. 統計結果如表1所示, 從結果中可以看出, 產生新覆蓋的非確定性變異次數中, 具有“關鍵位置”的非確定性變異比例較高(分別為59%、45%和36%), 并且90%以上的“關鍵位置”經過確定性變異后仍然能夠產生新覆蓋.

4.2 新覆蓋發現效率的分析

在本小節, 我們解釋為什么針對“關鍵位置”進行細粒度變異相比非確定性變異能夠更快地發現新覆蓋.我們以libxml2的xmllint程序為例, 將我們的模糊測試工具AgileFuzz與AFL 2.52b、關閉確定性變異的AFL 2.52b -d以及關閉確定性變異的模糊測試改進工具EcoFuzz進行24 h實驗比較, 覆蓋率對比結果如圖5所示, 圖中可以看出AgileFuzz在相同的時間內發現了更多的路徑. 我們將對這一實驗結果進行詳細的分析,并展示我們的模糊測試工具的優勢.

圖5 xmllint程序覆蓋率對比

為了分析覆蓋率差異, 我們使用afl-cov[19]分析4個模糊測試工具所發現的程序覆蓋的差異. 分析結果顯示, AgileFuzz不僅發現了EcoFuzz等工具所發現的全部程序代碼, 還發現了更多的難以發現的程序代碼.其中hash.c文件的代碼, AgileFuzz覆蓋率為56.3%,而EcoFuzz等工具為0%, 這是導致程序覆蓋率出現較大差異的主要原因. 我們進一步分析產生現象的原因,通過程序分析發現如圖6所示的調用序列以及條件判斷. 這里簡單介紹一下CMP9函數, 這是xmllint實現的定長字符串匹配宏定義, 與C語言自帶的strcmp函數不同的是, “<”和“

圖6 xmllint程序hash.c調用依賴

EcoFuzz通過24 h的變異無法產生滿足條件約束的字符串-“

AgileFuzz在通過非確定性變異產生了包含字符串“<**”種子時, 觸發了cmp9函數新的覆蓋, 此時AgileFuzz利用聚類算法確定單一有效變異位置, 確定新覆蓋是由于變異了“<”字符所在的位置. 保存的新種子記錄了關鍵位置, 能夠對關鍵位置的后繼位置進行持續性的細粒度變異, 從而保證了產生“

圖7 種子變異過程

4.3 程序覆蓋率對比

為了驗證我們改進的模糊測試工具AgileFuzz在通用程序上的測試效果, 我們與近年來效果比較好的Eco-Fuzz、AFLFast以及原始的AFL 2.52b進行了實驗, 實驗以覆蓋率作為對比指標, 選擇了libxml2、binutils等常用的程序作為測試對象. 在相同的硬件和軟件環境中進行了3次實驗, 每次實驗的時間為72 h, 3次實驗的覆蓋率的平均值作為實驗結果, 然后計算覆蓋率對比圖, 如圖8所示. 通過實驗對比可以看出, AgileFuzz能夠更快地發現程序的覆蓋, 并且在不同的程序中效果較為穩定.

圖8 多個程序72 h的覆蓋率比較

4.4 漏洞挖掘能力

如表2所示, 為體現工具的普適性, 我們使用Agile-Fuzz對字體解析、html解析等多種類型的程序進行漏洞挖掘工作, 如: fontforge、harfbuzz、htmlcss、ffjpeg等軟件, 在挖掘工作中發現了大量的未知漏洞, 經過分析確定了漏洞類型, 并將漏洞崩潰樣本以及漏洞分析結果反饋給作者. 通過在實際程序中發現的未知漏洞,證明了AgileFuzz具有發現實際程序漏洞的能力.

表2 程序漏洞挖掘結果統計

5 相關工作

國際很多研究工作都針對AFL進行了改進. 這些針對AFL的改進主要在種子變異、能量分配方面進行了改進[20-23], 在確定性變異改進方面, FairFuzz[21]根據是否包括稀有分支跳過部分確定性變異, MOPT[22]詳細分析了確定性變異效率低對變異的影響, 并只保留了極少數的確定性變異, EcoFuzz[19]直接跳過了所有的確定性變異. 在種子評分改進方面, AFLFast[20]使用馬爾科夫鏈對種子能量分配進行建模, 被選次數更多的和被執行次數較少的種子分配的能量較高. EcoFuzz[19]使用多臂老虎機對模糊測試進行更準確的建模以完成能量分配. 但是這些模糊測試改進存在以下兩個問題:

1)變異更加盲目和隨機. 這些模糊測試工具認為確定性變異效率較低, 采取的策略是直接跳過全部或大部分確定性變異, 但是只保留非確定性變異的模糊測試在對種子進行變異時更加盲目和隨機, 無法對產生新覆蓋的變異位置進行持續的變異.

2)忽視了種子產生的新分支覆蓋數量對模糊測試的影響. 種子評分階段根據種子大小、種子運行速度和種子總分支覆蓋數量對種子進行評分, 但是總分支覆蓋數量越多的種子新發現的分支覆蓋數量并不一定越多, 所以新分支數量多的種子評分可能很低, 這導致模糊測試將大量的能量消耗在已經經過多次變異的分支覆蓋, 發現新覆蓋的能力受到限制, 并且作為影響種子評分的分支信息缺少程序的靜態分析.

6 結束語

模糊測試是一種高效的漏洞挖掘工具, 能夠發現程序真實的漏洞. 本文設計了一種基于聚類算法和新覆蓋的模糊測試改進工具, 能夠針對單一有效位置進行持續性細粒度變異, 并且利用待測程序的靜態分析結果與新覆蓋信息結合對種子評分進行調整, 使得更多的能量分配給新分支, 降低了變異的盲目性. 總體來看, 我們的改進取得了較好的效果.模糊測試仍然存在很多的工作需要進一步研究, 在將來的工作中, 我們將研究如何針對程序的長字符串和整數匹配進行拆分,提高針對關鍵位置進行細粒度變異的適用性和效率.