基于多目標支配分析和路徑動態修剪優化的定向模糊測試技術

摘 要：當前定向模糊測試技術的平均距離模型在多目標測試中缺乏對逐個目標的指向性，在導向同一目標時路徑多樣化不強，且未根據不同目標的覆蓋程度動態調整距離度量，導致多目標測試不均衡和效率降低，難以在結合靜態分析告警等多目標環境中開展漏洞挖掘。針對以上問題，提出了一種多目標定向探索的模糊測試技術MTDFuzz，識別待遍歷多目標的支配節點，利用基于多目標支配分析的測試用例優選，通過支配節點覆蓋評分激勵機制引導生成能夠覆蓋支配節點和目標的測試用例，實現在限定關鍵覆蓋要素的前提下，對目標路徑的多樣化和指向性探索；根據目標的覆蓋狀態進行路徑動態修剪優化，已被充分測試的路徑和目標不參與距離信息反饋，通過剪枝和全局支配節點修正動態調整支配節點和目標基本塊評分，利用支配節點覆蓋度優化種子調度策略，實現對多目標測試資源的有效分配。實驗結果表明：與常用的定向模糊測試工具對比，多目標下MTDFuzz的平均漏洞發現時間縮短了57.6%，且在Glibc、FFmpeg等4個開源程序中發現了12個未公開漏洞，顯著提高了定向模糊測試的多目標探索能力和漏洞挖掘效率。

關鍵詞：定向模糊測試； 漏洞挖掘； 多目標導向； 程序分析

中圖分類號：TP311 文獻標志碼：A

文章編號：1001-3695（2024）11-037-3455-09

doi： 10.19734/j.issn.1001-3695.2024.01.0060

Directional fuzzing based on multi-objective domination analysis andpath dynamic pruning optimization

Li Zeyuan， Yin Zhongxu^?， Zong Guoxiao， Sang Haiya

（School of Cyberspace Security， Information Engineering University， Zhengzhou 450001， China）

Abstract：Current directed fuzzing techniques suffer from a lack of specificity towards individual targets in multi-target testing， limited path diversity when aiming at the same target， and a failure to dynamically adjust distance metrics based on the coverage level of different targets， leading to imbalanced testing and reduced efficiency in environments that integrate static analysis alerts for vulnerability mining. To address these issues， this paper introduced MTDFuzz， a multi-target directed exploration fuzzing technique that identified dominating nodes for targeted traversal. By leveraging test case optimization through multi-objective dominance analysis and a coverage score incentive mechanism， MTDFuzz generated test cases that covered both dominating nodes and targets， enabling diversified and directed exploration of target paths within the constraints of key coverage elements. The technique dynamically pruned paths based on target coverage， excluding thoroughly tested paths and targets from distance metric feedback. Through pruning and global dominating node adjustment， it dynamically tuned the scores of dominating nodes and target basic blocks， optimizing seed scheduling strategies based on dominating node coverage to efficiently allocate multi-target testing resources. Experimental results demonstrate that MTDFuzz significantly reduces the average time to discover vulnerabilities by 57.6% compared to commonly used directed fuzzing tools， and has uncovered 12 0-day vulnerabilities in four open-source programs， including Glibc and FFmpeg， significantly enhancing the multi-target exploration capability and vulnerability mining efficiency of directed fuzzing.

Key words：directed fuzzing; vulnerability mining; multi-objective orientation; program analysis

0 引言

模糊測試^[1～3]作為一種自動化軟件測試技術，已經成為現代大規模軟件和系統中探索安全漏洞最有效的方法之一。定向模糊測試基于覆蓋率引導的灰盒模糊測試技術通過加入額外的目標或約束來引導測試的執行方向，以生成更為高效和具針對性的測試用例。AFLGo^[4]揭開了現代化定向模糊測試的序幕，通過預先標記代碼目標并預置控制流距離，對距離目標較近的種子賦予更多的能量，進而引導種子快速抵達目標并觸發漏洞。之后，定向模糊測試的研究延伸至與靜態分析、符號執行等技術的結合，以生成能達到更復雜程序結構（如覆蓋特定分支或語句）的測試用例。這些早期工作證明，定向模糊測試可以顯著提高漏洞挖掘以及復現的效率和準確性，并廣泛應用于補丁的有效性檢測、漏洞復現、crash可利用性評估、驗證靜態分析的結果從而消除誤報，以及一些獨特類型的漏洞挖掘等領域。盡管定向模糊測試技術不斷發展并取得了顯著進步，但現有技術主要側重于對單一或少量測試目標的針對性測試，在同時針對較多的目標進行測試時往往存在目標偏好的情況，缺乏均衡性，且難以將定向模糊測試的高效率和指向性直接用于未知漏洞挖掘。為滿足軟件漏洞挖掘的實際需求，需要一種能夠均衡導向至多個測試目標的模糊測試技術。

本文的主要貢獻如下：

a）提出一種基于多目標支配分析的測試用例優選方法，對執行到目標起著決定性作用的支配節點進行錨定，根據基于支配節點覆蓋度的種子調度策略，通過支配節點覆蓋評分激勵引導生成覆蓋支配節點和目標位置的種子，實現在限定關鍵覆蓋要素的前提下，對目標路徑進行多樣化和指向性探索。

b）提出一種基于目標覆蓋狀態的路徑修剪方法，能夠支撐隨測試過程和目標覆蓋情況，不采用已充分測試的目標路徑參與測試用例評分計算，對支配節點和目標基本塊的評分進行動態調整，該方法對逐個目標的針對性更強，實現了對多目標的高效探索和漏洞發現。

c）基于以上方法實現了多目標定向模糊測試原型系統MTDFuzz，與AFL++、AFLGo、LeoFuzz、SieveFuzz等模糊測試工具進行相關對比實驗并發現了12個未公開漏洞，證明本文工作的有效性與實用性。

1 背景

1.1 定向模糊測試

如圖1所示，現有的主流定向模糊測試方法在靜態分析階段使用程序分析方法，提取程序中與目標相關的導向信息（如到目標位置的距離、與目標相關的代碼以及執行路徑上的約束信息等），并將導向信息插樁到程序中，用于后續動態過程的針對性引導。在動態分析時，首先進入探索（exploration）階段，即利用代碼覆蓋率信息提升語料庫的覆蓋率，避免陷入局部最優，隨后進入利用（exploitation）階段，此時利用靜態分析得到的導向性信息，對種子的變異、調度，以及種子隊列進行調整，實現導向性測試。

現有的定向模糊測試方法主要分為三類：a）最小距離算法引導的定向模糊測試，如AFLGo、Hawkeye^[5]，這些方法通過感知種子與目標的距離，為“更接近”的種子提供更多調度和變異機會；b）修剪輸入空間或修剪代碼空間，例如Beacon^[6]前置路徑約束以提前截斷不可達路徑，FuzzGuard^[7]使用深度學習模型來過濾無效測試用例，而SieveFuzz^[8]引入一種跳閘機制，將模糊測試的搜索空間限制在只與達到指定目標位置相關的范圍內，WindRanger^[9]通過識別偏移基本塊以避免測試與目標無關的代碼區域；c）前置分析結果指導的綜合性優化，如AFLChurn^[10]運用蟻群算法優化目標相關的字節級變異，提高覆蓋最近更新或頻繁修改的代碼區域的種子能量，這類區域存在“回歸”漏洞的概率較高，SAVIOR^[11]、FISHFUZZ^[12]和ParmeSan^[13]通過Sanitizer標記大量潛在漏洞監測點后，設計不同的平均值距離算法來指導模糊測試優先探索這些監測點，但是未設計特定的多目標定向探索策略，仍然依賴于AFL的“遺傳進化”的思想，給隨機變異生成最終覆蓋目標位置的種子賦予更多的能量，未考慮目標之間的關系以及測試是否充分。

1.2 問題描述

雖然上述定向模糊測試方法在針對特定目標的測試上取得了一些進展，但仍然存在以下兩個方面的問題：

問題a）：現有方法針對多個目標采用平均距離描述路徑的接近程度，適合于同一目標多個路徑點位的場景設定，但是對不同分支差異較大的多個目標難以準確評判，造成測試對多目標的覆蓋性較差。

現有的定向距離模型計算目標距離時^{[4，5，9，14]}，過度關注執行路徑上距離最小的測試用例，導致最短路徑優先，不利于測試路徑的多樣性。在多目標環境下，當前種子距離計算算法過度關注與目標位置最近的執行路徑，對路徑多樣性缺乏適應性，缺少對能到達相同目標的其他路徑的關注。漏洞挖掘需要滿足完整的路徑約束以及合適的數據流和控制流關系，最短路徑并不一定是漏洞觸發路徑，給予距離最近的種子較高權重可能會導致實際能觸發漏洞的測試用例得不到足夠調度，甚至出現定向模糊測試（DGF）偏好無法覆蓋任何目標位置的種子的情況，以下舉例說明。

以圖2中的過程間控制流圖為例，按照AFLGo的距離算法計算w、x、y、z四個種子的距離并排序：四個種子的執行軌跡分別是Trace（w）=A→B→C→D，Trace（x）=A→F→G→H→I→J，Trace（y）=A→F→L→M→N→O→P→Q→R→T，Trace（z）=A→F→L→M→R→S。

在多目標環境下，基本塊的距離計算采用了調和平均值，比如基本塊A的距離Dist（A）=3/（1/5+1/3+1/5）=45/11=4.1，基本塊F的距離為Dist（F）=2/（1/4+1/4）=4。基于基本塊距離計算四個種子的距離：Dist（w）=（45/11+2+1）/3≈2.36，Dist（x）=（45/11+4+3+2+1）/5≈2.82，Dist（y）=（45/11+4+3+2+5+4+3+2+1）/9≈3.12，Dist（z）=（45/11+4+3+2+1）/5≈2.82。

根據定向模糊測試的期望特性^[5]，能覆蓋目標或者“距離”目標近的種子應獲得更高的能量和優先級。在這四個種子中，種子z沒有到達任何目標，理論上，max{Dist（w），Dist（x），Dist（y）}應小于Dist（z），然而Dist（z）=Dist（x）lt;Dist（y），表明未覆蓋任何目標的種子z比覆蓋了目標T的種子獲得了更多能量和更高優先級。

問題b）：沒有動態統籌考慮多個目標的測試情況，依賴靜態距離的方式，隨著已經遍歷過的目標逐漸增多，未隨著目標的遍歷情況動態調整，向未覆蓋目標傾斜測試資源。

在對測試資源進行分配時，關鍵在于如何高效地利用有限的資源來達成對多目標的充分測試。在程序探索過程中，某些目標可能比其他目標更易于達到，頻繁測試的區域可能已經得到了充分檢驗，其代碼更安全健壯，存在漏洞的可能性較低。傳統的定向模糊測試器對程序中的多個目標位置通過靜態距離賦予固定的優先級，未動態考慮目標的遍歷情況，難覆蓋的目標代碼區域在全局視角中處于劣勢，容易被忽略，從而出現調度“饑餓”的情況。

上述問題使得難以在多目標環境中應用定向模糊測試進行漏洞挖掘，因此為了更有效地利用測試資源，達到更好的多目標測試效果，需要一種能夠根據目標遍歷情況的變化，動態調整測試資源分配并探索多樣化路徑的方法。

2 方法設計

2.1 解決思路與方法概述

解決問題a）的關鍵在于如何全局分析不同目標的分布，并根據測試過程及多目標的覆蓋情況，對不同目標進行差異化的度量和逼近測試。本文基于支配樹^[15]概念，提出基于多目標支配分析的測試用例優選方法，旨在優化定向模糊測試的距離度量^{[4，5，9，14]}，并對所有預設定目標進行全局化分析追蹤。本文對測試目標構建路徑支配樹，識別并錨定對執行到多目標起著決定性作用的支配節點，并將這些支配節點作為多目標路徑探索的“驛站”。綜合考慮所有可能到達目標位置的路徑，在路徑對目標的執行接近程度評定上，將支配節點用于距離逼近程度評估，以解決由最小距離算法引導的定向模糊測試在多目標環境中遇到的測試路徑單一性和目標指向性問題。

針對問題b），需要隨著測試的進行，對每個目標的關注度進行動態調整，在測試用例優選過程中剔除已被充分測試的目標。本文提出基于目標覆蓋狀態的路徑動態修剪優化策略，計算支配節點的途徑情況來深入分析潛在目標的覆蓋狀態，通過剪枝和全局支配節點修正，實現計算資源的有效分配和對目標集合的均衡測試。

基于上述思路，本文提出基于多目標支配分析和路徑動態修剪優化的定向模糊測試技術并構建原型系統MTDFuzz。該系統可以接受程序中的多個目標位置作為輸入，圖3描述了MTDFuzz多目標模糊測試技術的整體工作流程，主要分為靜態分析和多目標定向模糊測試兩個階段，具體的優化方法包括以下四個方面（圖中灰色部分標示）：a）靜態分析，首先接受測試程序和多個目標位置作為輸入，給定一個種子語料庫，運行程序間靜態分析以識別能到達目標位置的相關基本塊，回溯標記必經的支配節點，并基于這些支配節點計算基本塊的初始評分，插樁基本塊評分信息編譯得到待測試的二進制程序；b）基于多目標支配分析的測試用例優選，記錄測試用例執行過程中經過的支配和目標節點，并將這些支配節點和目標節點的評分累加得到測試用例優選評分；c）基于目標覆蓋狀態的路徑動態修剪優化，隨著模糊測試的進行，多目標的覆蓋情況發生變化，采取運行時分析重新評估支配節點和目標的覆蓋狀態信息，動態修剪已充分測試的路徑和目標，動態調整支配節點評分；d）基于支配節點覆蓋度的種子調度策略，結合支配節點覆蓋度指導種子的選擇、能量分配以及變異階段，加速優選測試用例的生成和進化，通過支配節點的覆蓋激勵，擴大對多目標的探索面，實現具備路徑多樣性的多目標測試。

2.2 基于多目標支配分析的測試用例優選

本文提出了一種新的多目標種子評分機制，先靜態計算支配節點到各個目標之間的距離，并保留最小值以及其對應的目標。

2.2.1 支配節點（DomPoint）識別

定向模糊測試的測試空間不是整體程序，因此基于全程序空間的覆蓋率搜索的方法不再適用。將覆蓋增益與目標位置及其執行路徑不相關的種子加入隊列中，并不能提升DGF的效果。因此，本文提出尋找種子執行路徑上的指引性節點，即支配節點來引導測試。只有先到達支配樹DT上的支配節點，才能覆蓋后續的目標并獲取有效的反饋。

支配節點是本文的一個關鍵概念，如果樹中的每個節點只支配自己及其后代，則稱之為支配樹（DT）。當且僅當經過n的路徑必須先經過d時，節點d支配節點n，記作d dom n，根據定義，每個節點都支配自身。為了識別種子執行路徑上的支配節點，MTDFuzz在動態測試前進行靜態分析以識別程序中潛在的支配節點。在模糊測試期間，通過分析已執行的基本塊與潛在支配節點之間的關系確定執行路徑中的支配節點。以下是本文對支配節點的定義：

定義1 給定一個待測試的程序p和程序中的一個目標t，p的程序過程間控制流圖iCFG=（V，E），其中V代表基本塊集合，E代表邊的集合，T是待測試的多目標集合，b是程序中的基本塊，Target_DP（t）則表示目標t的支配節點集合：

Target_DP（t）={b∈V（p）|（b dom t ∩|iCFG_out（b）|gt;1）}

目標完全支配節點集合為

Target_DP′（t）=Target_DP（t）∪t

定義1可以解釋為：在基于程序間控制流圖iCFG構建的支配樹DT上，目標節點的前驅節點一定能到達后續的目標節點，但是全程序基本塊集合過大，標記所有執行路徑上與目標位置相關的父節點會嚴重增加運行時開銷。因此，本文僅保留iCFG中出度大于1的節點，從而得到支配節點集合All_DP（p）：

All_DP（p）={b∈V（p）|（?t∈T，b dom t ∩ iCFG_out（b）|gt;1）}

All_DP′（p）=All_DP（p）∪T

程序全局支配節點與目標節點一起構成程序p的完全支配節點集合All_DP′（p）。

在實際計算中，首先構建目標程序的過程間控制流圖iCFG，然后基于iCFG計算每個基本塊到目標位置的可達性，如果在iCFG上存在從基本塊到目標位置的路徑，則認為基本塊可以到達目標位置^[9]。動態執行過程中的支配節點引導種子逼近目標位置，只有覆蓋了目標路徑上的支配節點，滿足到達目標位置的前置條件，才能順利覆蓋后續的目標節點。

定義2 種子s執行軌跡中支配節點Seed_DP（s）表示：

Seed_DP（s）={b∈（ξ（s） ∩ All_DP′（p）}

其中：ξ（s）是種子s執行軌跡中所有的基本塊。

以圖4為例，圖4（a）是程序過程間控制流圖iCFG，程序中包含4個目標位置，T={R，H，L，Q}，iCFG經Lengauer-Tarjan算法^[16]構建支配樹DomiCFG，其中Target_DP（R）={A，C}，Target_DP（H）={A，C，D}，Target_DP（L）={A，J，K}，Target_DP（Q）={A，J，P}，因此，示例中的程序全局支配節點All_DP（p）和完全支配節點集合All_DP′（p）為：All_DP（p）={A，C，D，J，K，P}，All_DP′（p）={A，C，D，H，J，K，L，R，P，Q}。

為了使測試用例能夠到達目標位置甚至觸發漏洞，需要滿足特定的路徑特征。支配節點在控制流中起著推動DGF逼近目標位置的尋路作用，支配節點之間以及支配節點與目標之間均可能存在多條路徑，逐步覆蓋程序中的支配節點而不是只關注最短路徑，可以得到更加豐富的測試路徑，有利于漏洞的觸發。測試過程中覆蓋一個基本塊的直接后繼并不增加到達目標的可能性，因為基本塊和其唯一后繼基本塊到達目標的概率是相同的^[17]。因此，識別控制流中的支配節點變得至關重要，這些節點與目標位置存在支配關系，為目標的逼近過程提供了有效的控制流關系指引。

2.2.2 測試用例優選評分

本節利用2.2.1節中識別的支配節點來計算基本塊和種子的評分。對于每一個目標t，有一系列支配節點b在支配樹DT上，b∈Target_DP（t），利用執行路徑上的支配節點到所有目標基本塊的多目標距離dist（b，t）來計算基本塊評分W_b，T：

dist（b，T）=mint∈T{Dijkstra（b，t）}（1）

W_b，T=1dist（b，T）+C（2）

式（1）表示在程序間控制流圖iCFG中，支配節點b到目標位置t的距離，當b是目標本身時，距離為0，當b不可達t時，距離為∞，不參與計算。部分支配節點可以達到多個目標基本塊，這些支配節點在初始評分階段只存儲到最近目標的距離。式（2）中常數C是一個正值，用于控制距離dist（b，T）對基本塊評分的影響程度，目標基本塊的評分為1/C，因此權重最高，距離目標越遠的支配節點權重越低。

本文給予以下種子更高的優選評分：a）種子執行路徑經過了更多的支配節點；b）種子的執行路徑更加接近目標位置。種子的優選評分通過累加基本塊評分來計算，記錄種子執行過程中經過的支配節點和目標節點，并將這些支配節點和目標節點的評分相加。種子s的優選評分定義為執行過程中經過的支配節點以及目標的分數之和：

Score（s）=∑b∈Seed_DP（s）W_b，T（3）

優選評分Score（s）增加意味著種子執行軌跡中包含更多的支配節點或實現了更高的目標節點覆蓋率，因此該種子應獲得更多的測試資源和變異機會，并在調度中賦予更高的優先級。

2.3 基于目標覆蓋狀態的路徑動態修剪優化

為了解決定向模糊測試在目標選擇上的偏向性問題，本文提出一種動態的目標選擇方法，記錄多目標的覆蓋狀態，修剪已經充分測試的目標和路徑，平等地測試所有目標。

當對應目標執行次數達到閾值被充分測試時，將該目標從目標探索集合中剔除。若支配節點還有其他目標探索后繼，則支配節點的距離更新為支配節點到當前最近目標節點的距離；若當前支配節點無目標后繼，則將支配節點標記清除，轉向其他代碼區域的探索。記錄支配節點的覆蓋情況和執行次數，將支配節點和目標節點與三元組（hit_frequency， dominated_targets， is_reserve）相關聯，hit_frequency代表支配節點被執行的次數，dominated_targets代表支配節點的后繼節點中是否包含目標節點，is_reserve表示該支配節點及后續節點是否被保留。當hit_frequency超過f次時，表示該支配節點已被充分測試，生成了足夠能執行該支配節點的種子。當hit_frequency gt; f且dominated_targets=0時，is_reserve置0，表示此節點及后續分支需要被剔除，從iCFG中剔除該支配節點的評分及其后繼節點的評分不影響對于其他目標的測試，可以從支配節點集合All_DP（p）中刪除，不參與距離計算及評分信息反饋。

在初始階段會給支配節點插樁距離信息，基于上一節的基本塊和測試用例優選評分機制，計算基本塊評分，優選評分較高的目標，待目標被充分測試后，啟用修剪算法，向上遞歸更新支配節點中存儲的距離，實現基于動態的多目標種子優選評分?；谀繕烁采w狀態的路徑修剪算法1如下。

算法1 基于目標覆蓋狀態的路徑動態修剪算法

輸入：過程間控制流圖iCFG；目標節點集合T；完全支配節點集合All_DP′（p）；全局基本塊評分W；全局支配節點三元組信息（hit_frequency， dominated_targets， is_reserve）。

輸出：更新后的完全支配節點集合All_DP′（p）以及基本塊評分W。

1 function domPointCull（t）" // 支配節點修剪

2 for v in All_DP（p） do

3

if v dom t then

4 v. dominated_targets-= 1

5

end if

6

if v. dominated_targets == 0 then

7 All_DP′（p）.cull（v）

8 /* 在iCFG上修剪已被充分測試的支配節點 */

9 v.is_reserve=0

10

end if

11

for n in v.predecessor do

12 W= updateScore（dist（n，T））

13

end for

14 end for

15 return W，All_DP′（p）

16 end function

17 function traceCull（t） // 基于支配節點的路徑修剪

18 for v in All_DP′（p） do

19 if t.hit_frequency gt; f and t.dominated_targets = 0 do

20

T = T.delete（t）

21

domPointCull（t）

22 end if

23 end for

24 return W ， All_DP′（p）

25 end function

本文用目標狀態覆蓋表示在運行時檢測的支配節點和目標的覆蓋情況，已被充分測試的目標節點被修剪剔除，不參與測試用例優選評分的計算。若其對應的支配節點無后繼的目標節點，也進行剔除。因此再次覆蓋已充分測試的支配節點的種子無法獲取較高的種子優選評分。

圖5為修剪示例，初始控制流圖中，目標集合T={R，H，L，Q}，其支配節點集合All_DP（p）={A，C，D，J，K，P}，完全支配節點集合All_DP′（p）={A，C，D，H，J，K，L，R，P，Q}，當部分目標T′={R，H，L}被充分測試后，其is_reserve標志置0，從目標集合中剔除，K節點被修剪后，其All_DP（p）節點中的父節點J更新距離為到Q的距離，即距離更新為4，同樣A點距離更新為6。

2.4 基于支配節點覆蓋度的種子調度策略

本文在程序中識別并錨定多個支配節點，測試覆蓋新的支配節點或目標后獲得測試用例優選評分激勵，并賦予更高的優先級和能量，而覆蓋與目標以及相關路徑無關的代碼時無法獲取激勵。本方法的種子池是一個循環隊列，依據順序選擇種子，當種子池中加入新的測試用例時，根據式（3）計算的測試用例優選評分Score（s）對種子進行排序，隊列中靠前的種子由于覆蓋了較多的支配節點以及具備較深的執行路徑深度，這些種子得到較早的調度可以加快測試的多目標探索。

定義3 支配節點覆蓋度Q表示程序中完全支配節點的覆蓋情況：

Q=N_hitN_all（4）

其中：N_hit是累計被命中過的程序完全支配節點數量；N_all是所有程序完全支配節點All_DP′（p）的數量；Q的值越大代表程序由支配節點引導的多目標測試探索情況越好。

算法2 動態種子能量調度算法

輸入：已插樁完全支配節點信息的程序P′；初始種子池C；需要被賦予能量的種子s。

輸出：種子s的能量E^（s）。

1 Score（s）=Execute（P′，s）

2 S^（s）=Normalize（Score（s），C）

3 /*T_exp是模擬退火中的溫度*/

4 E（s）=Q*S^（s）*（1-T_exp ）+0.5*T_exp

5 E^（s）=E_afl（s）*2^{10*E（s）－5}

MTDFuzz的目的是通過支配節點的覆蓋逐步引導到程序中離散分布的多個目標節點，因此需要選擇能夠覆蓋完全支配節點的種子并賦予更高的優先級。算法2介紹了基于支配節點覆蓋度的種子能量策略，給定一個輸入s，以及包含完全支配節點信息的程序P′，根據式（3）種子優選評分的定義計算種子優選評分Score（s），為種子優選評分Score（s）越大的種子賦予越高的優先級。本文基于模擬退火算法來選擇種子，定義標準化種子優選評分：

S^（s）=Score（s）－Score_minScore（s）_max－Score_min（5）

其中：Score（s）_min和Score（s）_max表示種子池中種子優選評分的最小值和最大值；標準化種子評分S^（s）可以在搜索支配節點和目標時起到對開發和利用階段的平衡，S^（s）∈［0，1］。

基于標準化種子優選評分，本文設計了能量調節函數（算法2第4行）來解決探索和利用問題，其中T_exp是模擬退火的溫度函數，使用Q*S^（s）表示種子的測試演化進度，需要Q和S^（s）共同作用以參與種子能量分配的調節。測試的初始階段是探索階段，以覆蓋率探索為主，目的是充分搜索程序中的支配節點，并獲取初期的種子評分。隨著種子s被選擇的次數增加，能量調節函數E（s）開始降溫，并逼近于Q*S^（s），此時切換為開發階段，著重生成能覆蓋更多支配節點或能覆蓋目標位置的種子，實現基于支配節點覆蓋引導的測試聚焦。

算法2第5行為最終的種子能量賦予函數，其中E_afl（s）是AFL基于種子執行速度和種子文件大小來分配的種子能量基準。

模糊測試隨著測試推進會遭遇一定的測試瓶頸導致測試進度放緩^[18]，本文識別多目標定向模糊測試過程中的障礙點，與之前模糊測試方法中提到的障礙點（程序中的魔數字節和校驗和）^[19]不同，利用字節推斷來輔助穿透路徑約束，在程序中某些模塊的執行不僅與輸入的結構相關，還與程序的命令行參數密切相關，不同目標位置的代碼可能需要不同的命令行參數才能被執行。因此采取階段式的模糊測試方法，在一個模糊測試階段結束后，導出程序中完全支配節點集合All_DP′（p）的覆蓋情況，定義尚未被覆蓋的支配節點集合NoCov_DP（p） All_DP′（p），這個集合中的節點在測試過程中沒有被任何輸入數據或參數組合所執行，指示程序中那些不易達到或未被充分測試的部分。為了覆蓋這些難以達到的支配節點，可以采取以下方法：通過人工專家構造專門的測試用例，調整輸入生成策略，或者借助動態符號執行技術^[20，21]，以加強對這些存在覆蓋障礙的支配節點的測試。

3 實驗評估

本章首先介紹實驗的設置以及基準測試集的選擇，繼而闡述本研究所采用的對比基線和評估指標。最終，通過對比實驗驗證了本文方法的有效性，并在真實軟件構成的FuzzBench平臺上評估了漏洞挖掘效果。

3.1 實驗設置

本文根據上述的模糊測試框架構建了工具MTDFuzz，該工具主要通過C和Python實現，并使用SVF^[22]和Temporal-specialization^[23]工具進行過程間分析，以構建程序過程間控制流圖iCFG。為了評估實驗，在Magma^[24]基準測試集上測試MTDFuzz的漏洞挖掘性能和效率，Magma基準測試集通過補丁將多個1-day漏洞前向移植到一個版本的程序中，從而可以為DGF設置多個目標。本研究采用了Lee等人^[25]提出的定向模糊測試評估方法，通過Fuzzle自動生成的迷宮程序測試多目標探索能力，Fuzzle結合隨機創建的迷宮和歷史CVE漏洞中的路徑約束以生成測試程序。此外，使用了tcpreplay、logrotate、jpegoptim等五個接受不同類型輸入的真實程序組成FuzzBench^[26]，以測試MTDFuzz挖掘真實程序漏洞的能力。

對比基線：將MTDFuzz與以下模糊測試工具進行對比測試。

a）AFL++^[27]：git commit 981a90d；

b）AFLGo^[4]：git commit fa125da；

c）SieveFuzz^[8]：git commit 1fb90ff；

d）LeoFuzz^[28]：Docker SHA256 hash 60a1930。

AFL++是基于AFL持續開發的社區版，集成了眾多當前最先進的輔助分析和編譯優化技術，是當前主流的覆蓋率引導模糊測試工具。AFLGo首次提出了定向模糊測試方法，并實現了基于最小距離模型的定向測試工具。SieveFuzz是一個具有可達性感知的定向模糊測試工具，將靜態分析和動態分析相結合以提前終止不可達輸入，減小模糊測試的搜索空間；LeoFuzz通過分析目標序列與種子序列之間的多種關系，利用覆蓋率種子隊列和定向種子隊列，自適應地協調定向模糊測試的探索和利用階段。由于FuzzGuard^[7]和Hawkeye^[5]并未開源，所以本文未選取它們進行對比實驗。

實驗環境：本文實驗運行的硬件和軟件環境為Intel^?Xeon^?Silver 4216 CPU @ 2.10 GHz，128 GB內存，操作系統為64位Ubuntu 20.04.3 64，編譯器為Clang 12.0.1和gcc 11.4.0。

3.2 通用測試集性能評估

Magma v1.2.1測試集是一個廣泛用于評估模糊測試性能的基準測試集，它包含了多個程序庫中的漏洞：libpng（7個漏洞）、libtiff（14個漏洞）、libxml2（17個漏洞）、poppler（22個漏洞）、openssl（20個漏洞）、SQLite（20個漏洞）、PHP（16個漏洞），Lua（4個漏洞）、libsndfile（25個漏洞）。這些庫中包含的一些漏洞可以在十分鐘內被AFL++發現，這意味著它們可以在僅靠覆蓋率引導下迅速被模糊測試工具發現，這種特性并不足以證明多目標定向模糊測試方法的有效性，因此在本文的測試中，這些漏洞被剔除。

對于目標位置的確定，Magma為每個漏洞在被測試程序中插入了一個或多個MAGMA_LOG宏，以便在執行過程中記錄漏洞何時被覆蓋或觸發。本文將這些宏的位置指定為每個漏洞的目標位置。此外，Magma還對程序進行了補丁處理，以反轉修復錯誤的提交實現前向漏洞植入，并將這些位置也設置為目標，這些配置允許模糊測試工具更準確地定位和測試特定的漏洞位置，從而更有效地評估其對多目標定向模糊測試的性能。

本文使用Magma提供的默認語料庫作為初始種子，進行了10次每次24小時的實驗評估。使用Magma提供的分析腳本對實驗結果進行分析，實驗結果可分為以下兩個方面：a）模糊測試工具發現的漏洞數量，結果顯示在表1中；b）發現漏洞所需的平均時間（TTB），結果顯示在表2中。

在大多數情況下，MTDFuzz的表現優于其他的模糊測試工具。平均而言，使用幾何平均值計算平均漏洞挖掘數量發現漏洞的平均時間并進行比較，從表1和2中可以看出，MTDFuzz相較于AFL++（啟用cmplog選項），AFLGo、SieveFuzz和LeoFuzz，在libtiff、libxml2、php、poppler、libsndfile和lua中檢測的漏洞數量最多，平均漏洞發現時間縮短了57.6%、39.2%、43.9%和36.3%，在發現漏洞數量上分別增加了32%、59%、33%和18%。

3.3 多目標探索能力實驗

多目標定向模糊測試不再以覆蓋率的提升效果為主要衡量指標，而是需要快速聚焦目標位置集合。本實驗評估MTDFuzz的多目標探索能力，能否在相同的時間內到達更多的目標，基于Magma中的四個實驗程序libpng、libtiff、libxml2、libsndfile，并將其中每個軟件中的MAGMA_LOG宏數量擴充到每個軟件100個作為目標集合，構建多目標探索能力測試集，將MTDFuzz與AFLGo和AFL進行對比，每個程序上進行5輪實驗，每輪實驗24 h，實驗結果如圖6所示。

從圖6中可以看出，在實驗前期三個模糊測試工具的目標覆蓋情況差別不大，因為在實驗初期都采用了覆蓋率引導。由于AFLGo采取了最小距離引導，所以針對部分目標和路徑在測試前期能夠快速覆蓋，MTDFuzz前期生成了大量的種子用于覆蓋支配節點，然而隨著測試的深入，AFL和AFLGo的目標發現效率相對MTDFuzz放緩，由于MTDFuzz基于程序中的支配節點引導逐步逼近目標位置，且修剪已被充分測試的目標，轉而將能力傾斜于全覆蓋的目標站點，所以在24 h時，MTDFuzz相比AFLGo和AFL能夠覆蓋更多的目標，本文的方法對于多目標的探索效率更高。

為了進一步驗證本文方法對多目標測試路徑多樣性的提升，對本實驗中的路徑和崩潰數量進行了統計，以研究基于多目標支配分析的測試用例優選方法對測試路徑多樣性的影響。Q是2.4節中定義的支配節點覆蓋度5輪實驗平均值，Avg（Target_path）是5輪實驗中所有能執行到目標的測試用例數量（發現的目標相關路徑數量），結果如表3所示。

根據表3的結果可以看出，MTDFuzz在支配節點覆蓋度和發現的目標相關路徑數量上均優于AFL和AFLGo，在libsndfile實驗中，MTDFuzz發現的目標相關路徑數量是AFLGo的3.9倍。原因是MTDFuzz采用了多目標支配分析，比AFL和AFLGo更關注測試用例覆蓋執行覆蓋目標過程中的支配節點，因此發現了更多的目標相關路徑，提升了多目標測試路徑多樣性。

3.4 多漏洞復現效率實驗

為了驗證MTDFuzz在一個軟件中包含多個漏洞場景的有效性，使用了Multi-target Fuzzle^[29]生成兩個復雜度為20×20和30×30的迷宮合成程序，每個程序中均包含三個漏洞來進行多漏洞復現效率實驗。采用改進的Fuzzle來合成路徑長度相同的迷宮漏洞程序，對每個程序分別運行AFLGo、LeoFuzz、SieveFuzz和MTDFuzz，將三個漏洞都作為目標，并當作以上模糊測試工具的輸入，每個實驗都重復10次，每次運行12 h，TTE是暴露漏洞的平均時間。

實驗結果如圖7所示，從中可以看出在兩個迷宮程序中，MTDFuzz相比其他模糊測試工具探索bug1、bug2和bug3的平均時間開銷更小，在30×30的迷宮程序中，MTDFuzz的漏洞發現時間比AFLGo縮短了3.35 h，所需時間減少了71.4%。另外，MTDFuzz是唯一能在0.4 h內發現20×20迷宮中所有bug，并在1.5 h內發現30×30迷宮程序所有bug的模糊測試工具?？傮w來看，在多個目標漏洞引導環境下，MTDFuzz具有更強的多漏洞復現能力。

3.5 真實漏洞檢測能力實驗

本文選擇了5個真實程序來構建FuzzBench，以測試MTDFuzz的真實軟件漏洞挖掘能力。這些待測試程序涵蓋了不同的輸入格式，包括日志、圖像、二進制程序和網絡流量包等，具體的程序信息和測試命令詳見表4。這些復雜的輸入結構測試使得實驗更能體現通用性和代表性，盡管采取更長時間的階段性測試對MTDFuzz更加有利，本文仍然將所有實驗的運行時間設定在24 h。

本實驗與AFLGo、SieveFuzz、LeoFuzz進行了比較。實驗中，運行Clang Static Analyzer^[30]，并將其靜態分析報告中的結果作為多目標位置進行測試，即潛在存在漏洞的代碼位置，Clang Static Analyzer靜態分析報告的結果沒有經過可疑的過濾等處理，因此靜態分析報告中包含假陽性和不可達的目標。實驗旨在評估MTDFuzz及其他三個DGF工具在引導下觸發FuzzBench中漏洞的效率，并比較它們在此過程中的時間開銷。SieveFuzz在某些程序上無法編譯或正常運行，因此將這些條目標記為N/A，實驗結果詳見表5，μTTE表示平均首次觸發時間，Ratio是其他fuzzer與MTDFuzz在μTTE指標上的比值。

從表5可以看出，MTDFuzz發現真實漏洞所需的時間少于另外三種工具。在tcpreplay中，MTDFuzz表現出的加速效果最為出色，AFLGo、SieveFuzz、LeoFuzz所花的時間分別是MTDFuzz的15.13倍、28.49倍、5.79倍。從實驗結果可以看出，MTDFuzz相比其他幾個模糊測試工具能夠更快挖掘到真實漏洞。

此外，為了驗證多目標定向模糊測試工具MTDFuzz在實際開源軟件0-day漏洞挖掘中的應用效果，采用兩種方式標定需測試的目標位置集合：a）最近提交或頻繁變更的代碼區域（與長期未修改已經徹底測試的舊代碼相比，新提交的代碼中存在漏洞的風險更高）；b）利用靜態分析工具Clang Static Analyzer檢測可能存在漏洞的代碼。通過以上目標標定指引，MTDFuzz在Glibc、FFmpeg、logrotate和tinyexr四個開源軟件中發現了12個未公開漏洞，并得到了開發人員的確認，其中9個已獲取CVE編號，具體漏洞信息如表6所示。

發現的漏洞類型主要包括堆棧溢出等內存破壞性漏洞，其中FFmpeg是一個被廣泛使用的多媒體庫，它在OSS-Fuzz中經過了充分測試。使用傳統的模糊測試策略難以發現其中的crash，MTDFuzz則發現了2個堆溢出漏洞。此外，選取logrotate程序的CVE-2023-38795挖掘過程及漏洞成因進行簡要說明，logrotate程序是Linux操作系統中常用的日志文件處理程序，該漏洞的代碼片段如圖8所示。

發現glibc glob函數棧溢出漏洞后，檢索logrotate程序中所有調用glob函數的代碼位置作為MTDFuzz的目標進行測試并發現crash。ASAN^[31]內存崩潰報告顯示，config.c文件第1 849行調用glob函數時發生崩潰，glob由GNU C庫（libc）提供，用于擴展通配符模式匹配文件路徑，其第一個參數pattern是一個字符串，用于指定需匹配的文件名模式。logrotate讀取惡意構造日志文件，導致得到的pattern字符串包含大量目錄分隔符“/”，每個目錄分隔符會遞歸觸發一次mempcpy內存復制。由于glibc glob函數的實現未限制pattern字符串的長度，glob函數內部的深度遞歸調用導致了棧溢出。修復補丁位于1 842～1 847行（圖中灰色陰影部分代碼），開發人員限制glob函數的pattern參數長度為2 048，防止遞歸引發棧溢出。OSS-Fuzz等其他持續性模糊測試長期測試logrotate項目但是并未關注其中glob函數的調用，AFLGo等定向模糊測試方法難以對程序中的多個glob函數調用展開測試，因此難以發現該漏洞。

3.6 測試總結

通過對實驗結果分析可以發現：a）在通用的測試集Magma中，本文方法相比于AFL++、AFLGo、SieveFuzz和LeoFuzz表現出更高的目標漏洞檢測效率，同時還能夠揭示更多的漏洞，這表明本文的方法能夠顯著提升針對多目標的模糊測試性能；b）在多目標測試路徑多樣性上，從多目標探索能力實驗中可以看出， MTDFuzz發現的目標相關路徑數量相比AFLGo最高達3.9倍，得益于支配節點的指引作用，發現了更多的目標相關路徑，增強了多目標測試路徑多樣性；c）在多目標測試資源分配上，從多目標探索能力和多漏洞復現效率可以看出，本文的方法到達目標站點的速度和數量優于其他方法，由于采用了路徑動態修剪優化策略，及時將測試的關注度從已充分測試的目標轉向探索欠覆蓋目標，有效解決了未隨著目標的遍歷情況動態調整傾斜測試資源的問題，所以MTDFuzz更適合于針對多目標進行測試，且利于與靜態分析告警處理等方法相結合；d）在真實程序測試集FuzzBench中，MTDFuzz的漏洞發現數量高于其他模糊測試工具，且發現了12個未公開漏洞，證明了MTDFuzz在真實軟件漏洞中的漏洞驗證和挖掘潛力。

綜上，本文方法在漏洞的挖掘方面表現出色，不僅能夠充分地動態修剪目標實現對多目標的測試，還能通過支配節點的引導更快實現對目標位置的覆蓋以及漏洞的觸發。

4 結束語

為解決之前定向模糊測試中平均距離模型對不同分支的多目標適應性不強，以及未根據不同目標的覆蓋程度動態調整距離度量這兩個問題，本文提出了一種基于支配節點以及目標節點覆蓋狀態的路徑修剪方法，以基于支配節點覆蓋度的種子調度策略，并構建了MTDFuzz模糊測試工具。實驗結果表明，本文的方法在多目標環境下，提升了程序中多個漏洞的復現效率，在相同條件下與其他定向模糊測試工具相比具有更高的目標覆蓋效率，結合靜態分析報告的結果能更快復現真實漏洞。

下一步將探索如何在多目標定向模糊測試過程中對識別的關鍵障礙點進行突破。此外還計劃深入分析并整合靜態分析工具的輸出結果，以此來對本文提出的工具進行進一步的擴展和優化，提高定向模糊測試的效能和應用廣度，從而更有效地支持復雜軟件系統的安全性測試和評估。

參考文獻：

[1]任澤眾， 鄭晗， 張嘉元， 等. 模糊測試技術綜述 [J]. 計算機研究與發展， 2021， 58 （5）： 944-963. （Ren Zezhong， Zheng Han， Zhang Jiayuan， et al. A review of fuzzing techniques[J]. Journal of Computer Research and Development， 2021， 58 （5）： 944-963.）

[2]徐威， 李鵬， 張文鑌， 等. 網絡協議模糊測試綜述 [J]. 計算機應用研究，2023， 40 （8）： 2241-2249. （Xu Wei， Li Peng， Zhang Wenbin， et al. Survey of network protocol fuzzing [J]. Application Research of Computers， 2023， 40 （8）： 2241-2249.）

[3]張冠宇， 尚文利， 張博文， 等. 一種結合遺傳算法的工控協議模糊測試方法 [J]. 計算機應用研究， 2021， 38 （3）： 680-684. （Zhang Guanyu， Shang Wenli， Zhang Bowen， et al. Fuzzy test method for industrial control protocol combining genetic algorithm [J]. Application Research of Computers， 2021， 38 （3）： 680-684.）

[4]B?hme M， Pham V T， Nguyen M D， et al. Directed greybox fuzzing[C]// Proc of ACM SIGSAC conference on Computer and Communications Security. New York：ACM Press， 2017： 2329-2344.

[5]Chen Hongxu， Xue Yinxing， Li Yuekang， et al. Hawkeye： towards a desired directed grey-box fuzzer[C]// Proc of ACM SIGSAC Confe-rence on Computer and Communications Security. New York：ACM Press， 2018： 2095-2108.

[6]Huang Heqing， Guo Yiyuan， Shi Qingkai， et al. Beacon： directed grey-box fuzzing with provable path pruning[C]//Proc of IEEE Symposium on Security and Privacy. Piscataway，NJ：IEEE Press， 2022： 36-50.

[7]Zong Peiyuan， Lyu Tao， Wang Dawei， et al. FuzzGuard： filtering out unreachable inputs in directed grey-box fuzzing through deep learning[C]//Proc of the 29th USENIX Security Symposium. Berkeley， CA： USENIX Association，2020： 2255-2269.

[8]Srivastava P， Nagy S， Hicks M， et al. One Fuzz doesn’t fit all： optimizing directed fuzzing via target-tailored program state restriction[C]// Proc of the 38th Annual Computer Security Applications Conference. New York：ACM Press， 2022： 388-399.

[9]Du Zhengjie， Li Yuekang， Liu Yang， et al. WindRanger： a directed greybox fuzzer driven by deviation basic blocks[C]//Proc of the 44th International Conference on Software Engineering. New York：ACM Press， 2022： 2440-2451.

[10]Zhu Xiaogang， B?hme M. Regression greybox fuzzing[C]// Proc of ACM SIGSAC Conference on Computer and Communications Security. New York：ACM Press， 2021： 2169-2182.

[11]Chen Yaohui， Li Peng， Xu Jun， et al. SAVIOR： towards bug-driven hybrid testing[C]//Proc of IEEE Symposium on Security and Privacy. Piscataway，NJ：IEEE Press， 2020： 1580-1596.

[12]Zheng Han， Zhang Jiayuan， Huang Yuhang， et al. FISHFUZZ： catch deeper bugs by throwing larger nets[C]//Proc of the 32nd USENIX Security Symposium. Berkeley， CA： USENIX Association， 2023： 1343-1360.

[13]sterlund S， Razavi K， Bos H，et al. ParmeSan： Sanitizer-guided greybox fuzzing[C]//Proc of the 29th USENIX Security Symposium. Berkeley， CA： USENIX Association， 2020： 2289-2306.

[14]Wang Shen， Jiang Xunzhi， Yu Xiangzhan， et al. KCFuzz： directed fuzzing based on keypoint coverage[C]// Pro of the 7th International Conference，ICAIS. Cham： Springer， 2021： 312-325.

[15]Sreedhar V C， Gao Guang， Lee Y F. Incremental computation of dominator trees [J]. ACM Trans on Programming Languages and Systems， 1997， 19 （2）： 239-252.

[16]Lengauer T， Tarjan R E. A fast algorithm for finding dominators in a flowgraph [J]. ACM Trans on Programming Languages and Systems， 1979， 1（1）： 121-141.

[17]Luo Changhua， Meng Wei， Li Penghui. SelectFuzz： efficient directed fuzzing with selective path exploration[C]//Proc of IEEE Symposium on Security and Privacy. Piscataway，NJ：IEEE Press， 2023： 2693-2707.

[18]Gao Wentao， Pham V T， Liu Dongge， et al. Beyond the coverage plateau： a comprehensive study of fuzz blockers （registered report）[C]//Proc of the 2nd International Fuzzing Workshop.New York： ACM Press， 2023： 47-55.

[19]Stephens N， Grosen J， Salls C，et al. Driller： augmenting fuzzing through selective symbolic execution[C]// Proc of Network and Distributed System Security Symposium. 2016.

[20]Poeplau S， Francillon A. Symbolic execution with SymCC： don’t interpret， compile！[C]//Proc of the 29th USENIX Security Symposium. Berkeley， CA： USENIX Association， 2020： 181-198.

[21]Triton： a dynamic binary analysis library [EB/OL]. （2023-12-04）. https：//triton-library. github. io/.

[22]SVF-tools. SVF-tools/SVF [EB/OL]. （2023-12-06）. https：//github. com/SVF-tools/SVF.

[23]Ghavamnia S， Palit T， Mishra S， et al. Temporal system call speciali-zation for attack surface reduction[C]//Proc of the 29th USENIX Security Symposium.Berkeley， CA： USENIX Association， 2020： 1749-1766.

[24]Hazimeh A， Herrera A， Payer M. Magma： a ground-truth fuzzing benchmark [C]// Proc of ACM Conference on Measurement and Analysis of Computing Systems.New York：ACM Press， 2020： 1-29.

[25]Lee H， Kim S， Cha S K.Fuzzle： making a puzzle for fuzzers[C]//Proc of the 37th IEEE/ACM International Conference on Automated Software Engineering. New York： ACM Press， 2022： 1-12.

[26]Metzman J， Szekeres L， Simon L， et al. FuzzBench： an open fuzzer benchmarking platform and service[C]// Proc of the 29th ACM Joint Meeting on European Software Engineering Conference and Sympo-sium on the Foundations of Software Engineering. New York：ACM Press，2021： 1393-1403.

[27]TheAFL+fuzzing framework [EB/OL]. AFLplusplus [EB/OL]. （2023-11-27）. https：//aflplus. plus/.

[28]Liang Hongliang， Yu Xinglin， Cheng Xianglin， et al. Multiple targets directed greybox fuzzing [J]. IEEE Trans on Dependable and Secure Computing， 2024，21（1）：325-339.

[29]SoftSec-KAIST/Fuzzle at multi-target [EB/OL]. （2024-01-16）. https：//github. com/SoftSec-KAIST/Fuzzle/tree/multi-target.

[30]Clang Static Analyzer—Clang 18.0.0 git documentation [EB/OL]. （2023-11-26）. https：//clang. llvm. org/docs/ClangStaticAnalyzer. html.

[31]Serebryany K， Bruening D， Potapenko A， et al. AddressSanitizer： a fast address sanity checker[C]//Proc of USENIX Annual Technical Conference. Berkeley， CA： USENIX Association， 2012： 309-318.