有狀態協議模糊測試的種子調度算法

摘 要：為了探索有狀態協議的程序漏洞，AFL-NET提出了有狀態協議模糊測試。在有狀態協議模糊測試中，種子的選擇對路徑的探索有著重大的貢獻。然而，目前的有狀態協議模糊測試往往重復執行幾個相同的種子，導致不能很好地探索更多的路徑。為了緩解該問題，從種子的收益入手，提出了一種有效的基于有狀態協議的種子動態調度算法。利用種子的潛在收益和實際收益以及成本作為收益，利用收益來進行動態的種子調度，并分配種子的執行次數。實驗表明，該方法在漏洞發現數量上有顯著提升，在提高覆蓋率方面也有一定的提升，說明此收益定義以及種子調度算法能有效選擇種子，探索更多的路徑以及漏洞。

關鍵詞：模糊測試； 灰盒； 協議測試； 漏洞挖掘

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

文章編號：1001-3695（2024）10-033-3119-05

doi：10.19734/j.issn.1001-3695.2024.01.0053

Seed scheduling algorithm for fuzzing stateful protocols

Xie Yuhao， Xu Xianghua

（School of Computer Science， Hangzhou Dianzi University， Hangzhou 310018， China）

Abstract：In order to investigate vulnerabilities in stateful protocols， AFL-NET has put forward stateful protocol fuzz testing. In such fuzz testing， the selection of seeds makes a major contribution to the exploration of paths. However， current stateful protocol fuzz testers often repeatedly execute the same several seeds， resulting in an inability to effectively explore more paths. To alleviate this problem， starting from the gain of seeds， this paper proposed an effective seed dynamic scheduling algorithm based on stateful protocols. The algorithm utilized the potential gain， actual gain， and cost of seeds as the gain， using this gain to dynamically schedule seeds and allocate the number of times seeds. Experiments show that this method significantly improves the number of vulnerabilities found and also has a certain degree of improvement in increasing coverage， indicating that the definition of this gain and the seed scheduling algorithm can effectively select seeds and explore more paths and vulnerabilities.

Key words：fuzz testing; grey box; protocol testing; vulnerability mining

基于覆蓋的灰盒模糊測試使用的方法主要是遺傳算法，通過遺傳算法來探索路徑。主要思想是：將一個輸入作為一個種子，通過大量變異算子變異后進行迭代，將其輸入到程序中，再通過對程序的覆蓋統計等方法判斷該種子是否探索了新的執行路徑。探索了新執行路徑的種子會被添加到種子池中進行下一輪的選擇，如此反復，不斷繁衍。有狀態協議模糊測試還需要考慮到程序的不同狀態，需要到達程序的不同狀態，再進行種子的輸入［1］。由于有狀態的灰盒協議模糊測每次執行需要重啟服務器，并且種子的輸入是通過socket套接字，所以效率低于基于覆蓋的灰盒模糊測試。對于基于覆蓋的灰盒模糊測試已經有很多相關工作，例如定向模糊測試［2］、嵌入式模糊測試［3］、工控協議模糊測［4］等。

對于有狀態協議模糊測試如何優化，目前主要的研究方向有四點：a）對變異算法的改進；b）對狀態選擇的改進；c）對種子的選擇；d）提高效率。

當前的有狀態協議模糊測試對于種子的選擇主要考慮種子收益，即種子探索新路徑的能力。一般從路徑的轉移概率、種子中新路徑數量、種子中獨特的狀態個數、種子執行時間來進行考慮，并且通過這些數據來計算給種子分配的能量（即該種子執行多少次變異）。然后，將增加了新覆蓋的種子加入到種子池中。然而，這種方式無法進行種子的動態選擇，比如，一個種子在執行過程中產生了新的覆蓋，那么理所當然該種子的收益更大，選擇該種子的概率越大。然而，這種方式在第一次執行時就確定了該種子的收益，無法根據程序的執行動態增加或者減少該種子的收益。因此，動態計算種子收益、動態選擇種子、動態能量分配十分重要。

針對上述問題，本文提出了一種輕量級的動態種子調度算法和能量分配算法SCFuzzer。SCFuzzer利用種子潛在收益、實際收益、成本進行動態概率分配和能量分配，通過在模糊執行過程中動態計算種子的收益來調度種子，實現種子調度的優化。

本文主要貢獻如下：

a）提出了一種基于種子潛在收益、實際收益和成本來動態計算收益并調度種子的算法。從多方面考慮種子探索新路徑的能力，并給出了一種有效性度量，實現動態的種子調度。

b）基于該度量實現了種子的動態能量分配策略，對重點種子執行更多次數的變異，使其能夠有更多時間進行對程序空間的探索。

c）基于AFLNET［5］實現了SCFuzzer，并在廣泛使用的RTSP和DTLS協議中進行了實驗測試。在24 h的實驗中，對覆蓋率的提升約2%，對漏洞發現數量提升約50%。

1 背景和動機

1.1 研究動機

在本節中，通過一個例子來說明種子的選擇對模糊器在路徑探索中的影響。在算法中，使用靜態的種子選擇策略，假設有兩個種子S1和S2，種子S1的執行路徑為7->11->12，種子S2的執行路徑為7->8->2->4。假設在先前的執行中，S2更有可能被選中，那么S2會持續執行，但是最終S2會一直執行到代碼行4的判斷語句，因為該判斷語句很難被突破，它是字符串的比較，那么在很長的一段時間內S2都不會探索新的路徑。而種子S1在先前的執行中被選中的概率較小，但它更有可能探索新的路徑。

算法1 不同種子執行路徑的探索

1 bool isCompare（string str）{

2 if （str.size（）>5）

3 retum false;

4 if （str[0]=='a' && str[1]=='b' && str[2]=='c'&& str[3]=='d'&& str[4]=='e'

5 return true;

6 }

7 if （flag==1）{

8 if （isCompare（str））

9 …

10 }

11 else {

12 …

13 }

因此，如果使用靜態的種子調度算法，那么就不能很好地反映種子在執行過程中不斷變化發現新執行路徑的能力。

1.2 研究背景

如上所述，AFL-NET在種子調度上并沒有很好地利用程序執行過程中的信息，導致可能會長時間選擇同一個很難探索新路徑的種子，而且選擇的種子大多執行的都是相同的路徑。事實上，已經有許多研究表明，種子的選擇對于模糊測試來說非常重要。

有狀態協議模糊測試中，對于種子調度尚未有充分的研究。而在基于覆蓋的灰盒模糊測試中，已經有許多對于種子調度的研究，它們考慮了影響種子收益的不同影響因子，大致可以分為兩類：

a）基于歷史信息。在基于歷史信息的相關研究中，確定一個種子的收益主要基于該種子的歷史執行信息。EcoFuzz［6］通過多臂老虎機確定一個獎勵概率，該獎勵概率基于該種子的自轉移概率和加入種子池的時間來確定。EcoFuzz將自轉移概率定義為該種子進行變異以后，探索路徑和未變異時的探索路徑相同的次數和總次數的比值，并將模糊測試階段分為三個階段，只有在每個種子都選擇過一遍以后，才會通過獎勵概率來選擇種子，并且提出了一種基于探索新路徑需要的平均執行次數來確定種子執行次數的能量分配方案。AFL-FAST［7］提出了利用馬爾可夫鏈說明更深層次的路徑需要更多執行過程，因此AFL-FAST給低頻路徑分配了更多的收益和能量。DiPri［8］提出了基于種子距離的種子調度算法，其依據是應該模糊整個程序代碼不同位置，探索不同代碼位置的新路徑。DiPri通過位圖計算種子與其他種子的距離之和，該種子距離越遠，則種子的收益越高，因為該種子的執行路徑位于代碼塊的不同位置。Truzz［9］認為具有更多新發現路徑的種子收益更大。然而這些方法并不能完全表明種子探索新路徑的能力，如果該種子遇到的分支很難被突破，那么這些方法將會浪費大量的時間執行很難突破的分支。

b）基于程序控制流圖。在基于控制流圖的相關研究中，確定一個種子選取的概率和能量主要基于該種子的執行路徑上有多少未探索的路徑。K-Scheduler［10］利用圖的中心性對一個種子計算得分，分數越高的種子收益越高。K-Scheduler提出了一種方法，將程序控制流圖轉換為邊緣視界圖，通過該圖計算一個種子的得分。BELIEFFUZZE［11］提出了一種平衡收益和成本的種子調度算法。一個種子的收益是基于程序控制流圖中該種子變異之后可能覆蓋的潛在路徑的數量來計算的，而成本定義為該種子的執行次數。BELIEFFUZZE綜合考慮了一個種子的收益和成本，收益高的種子優先執行，但是如果對該種子付出了難以接受的成本，而該種子并未探索新的路徑，那么就應該放棄該種子。基于程序控制流圖的方法需要得到程序的控制流圖，然而，在有狀態的協議模糊測試中，在不同狀態下，程序的走向不同，那么程序的控制流圖也會不同。因此，在有狀態的協議模糊測試中使用該方法會導致更多額外的開銷。

為了解決有狀態的協議模糊測試中，種子調度和能量分配的問題，使得選取的種子能更加有效地探索新路徑，并給其分配適應的能量。本文提出了一種在有狀態的協議模糊測試下，能夠動態調度種子并分配能量的輕量級算法。

2 方法概述

2.1 種子收益的影響因子

本文目標是對更能探索新路徑的種子進行更多變異測試，因此應該選擇更能探索新路徑的種子。本文將能夠探索新路徑的能力映射為種子的收益。

種子收益的影響因子主要有探索新的路徑的數量、執行路徑旁的未探索路徑的數量、執行路徑中低頻路徑的數量、種子的執行次數等因子。

種子執行路徑旁的未探索路徑表明了該種子還可以探索的路徑數量，因此其可以表示為種子的潛在收益。而種子探索新路徑的數量表明了該種子探索新路徑的能力，本文認為其可以表示為種子的實際收益。種子的執行次數表明了該種子探索新路徑所花費的時間，其可以表示為所需要的成本。因此可以定義一個種子的收益，包含其未探索路徑的能力，將探索路徑轉換為已探索路徑的能力以及探索的成本。

2.2 種子距離算法

DiPri提出了一種種子距離的算法，可以很好地計算種子執行路徑在程序空間中的分布。DiPri通過記錄覆蓋率的位圖來計算種子和其他種子的距離。其中，記錄覆蓋率的位圖是將程序的每一個基本塊通過哈希映射到位圖中的一位，如果該位為1，那么就表明該基本塊已經被探索過。因此，種子之間的距離就很好地反映了該種子執行經過的基本塊與其他種子執行經過的基本塊的距離，也即程序中的不同位置。通過計算種子的距離，可以避免探索密集的區域，并為很少探索的區域節省資源。

2.3 使用種子距離的動機

使用程序控制流圖計算種子收益的缺點已在1.2節詳細闡述。因此，本文更傾向于使用歷史信息來計算一個種子的收益。其中，種子的距離能更好地體現出一個種子的潛在收益，即一個種子能探索新路徑的潛在能力。以圖1為例，假設有5個種子，其中S1、S2、S3、S4的執行路徑都集中在程序代碼空間的一部分，而S5在程序代碼空間的其他部分。那么直觀地發現S5周圍可以探索的空間比其他四個種子都要大，因此種子S5的潛在收益更大。然而，由于只是將種子距離近似為程序控制流圖中一個種子可能探索的新路徑，有的路徑可能很難被突破，所以將其認為是該種子潛在的收益。

2.4 框架

本文的設計方案工作流程如圖2所示，其中紅色框中的內容即為本文的主要內容，其主要分為收益調度和能量分配兩個模塊。由這兩個模塊共同組成本文的動態種子調度算法和能量分配算法，通過這兩個模塊，可以動態地選擇種子和切換種子，動態地改變一個種子的能量分配。

2.5 收益調度模塊

如2.1節，本文目標是對更能探索新路徑的種子進行更多變異測試，因此，種子收益即為種子探索新路徑的能力。種子執行路徑旁的未探索路徑的數量表明了該種子還可以探索多少條新路徑。種子實際探索路徑的數量表明該種子將未探索路徑轉換為已探索路徑的能力。種子執行花費的時間表明該種子探索新路徑花費的時間成本。這三元組規定了種子探索新路徑的潛在能力，探索新路徑的實際能力和探索新路徑的成本，因此該三元組即可很好地表明一個種子探索新路徑的能力。綜上所述，將一個種子的收益定義成潛在收益、實際收益和成本三個方面。

a）潛在收益。將潛在收益定義為種子能夠探索到多少新路徑的能力，并將其解釋為種子距離。種子距離可以很好地表示種子在程序代碼空間中與其他種子的位置，該位置與其他種子位置越遠，那么該種子可以探索的潛在路徑就更多，也就是潛在收益越高。

潛在收益的計算：將潛在收益定義為種子的距離，其計算方法和DiPri類似，使用海明距離通過位圖來計算種子與其他種子的距離，將其距離之和作為種子的潛在收益。與DiPri不同的是，首先DiPri沒有狀態的概念，在AFL-NET中一個種子對應于多個報文，首先需要發送前序報文到達指定狀態，然后才能發送需要變異的報文，其中的一個報文對應于DiPri中的一個種子。因此，在AFL-NET中所關注的種子距離會受到前序報文的影響。如果兩個種子到達該狀態時執行的路徑距離很遠，然而執行變異報文而探索的路徑距離幾乎一致，則認為這兩個種子距離相近。因為需要考慮的是到達同一個狀態之后種子的距離，而DiPri就沒有考慮到狀態，導致所發送的前序報文會污染種子的距離。因此，本文提出的種子距離的計算需要剔除掉前序報文的影響，單獨計算變異報文探索路徑的距離。此外，如果每次單獨計算種子的距離，如果有n個種子，那么每次添加一個種子都需要計算n次再次求和。因此提出了一種優化的種子距離算法，通過海明距離計算，其公式如下：

distance（s，S）=∑k1（si^（s0i，S1i））

其中：s表示為需要計算種子的位圖；S0和S1記錄其他所有種子位圖中每一位的0出現的次數和1出現的次數。因此每次計算一個種子的距離時，只需要判斷位圖中的每一位，如果該位是1，那么distance（s，S）就加上位圖中該位0出現的次數，反之亦然，然后更新S1和S2。這樣每次添加一個種子需要n次求和降低到了1次求和。種子距離算法如算法2所示。

算法2 距離計算模塊

輸入： 當前的種子s；位圖S0，S1；位圖的長度size。

輸出： 種子s的距離。

pre=get_pre_message（s） //獲取種子的前序報文路徑

trace_bit_pre=exec_pre_message（pre） //計算前序報文的路徑

trace_bit=exec_message（s） //計算整個種子的路徑

for j=0 to size do

trace_bit_bef［j］=trace_bit［j］ ^ trace_bit_pre［j］

//計算后續報文路徑

end for

for i=0 to size do //計算路徑距離

if （race_bit_bef［i］==0）

distance=distance + S1［i］

else

distance = distance + S0［i］

end if

end for

b）實際收益。將實際收益定義為該種子探索新路徑的數量。實際收益能夠表明種子將潛在收益轉換為收益的能力，即探索潛在路徑的能力。通過實際收益可以解決先前工作可能會將大量時間浪費在很難產生新覆蓋的種子上，并進行種子的動態調度。

c）成本。將成本定義為種子的執行時間。先前的工作將成本定義為種子的執行次數，在基于覆蓋的灰盒測試中，例如BELIEFFUZZE，提出了以執行次數作為成本，這是可行的，因為每個種子執行的時間都很快，而且都大致相同。而在有狀態的協議模糊測試中，每個種子的執行時間可能相差很大。這是因為在有狀態的協議模糊測試中，每個種子中的報文數量也不盡相同，有的種子的前序報文很短，可能很快就能執行完成，有的種子的前序報文可能很長，所有需要更多的執行時間，因此使用執行時間來衡量種子的成本。本文基于以下的事實，即潛在收益是固定的，根據種子距離表明該種子能探索新路徑的潛在能力，而實際收益根據該種子是否真正探索了新路徑，表明該種子的真正能力，而成本根據種子的執行時間，表明付出的成本是否得到了預期的收益，因此定義種子的收益為

Benefit=Benefitp×l1+Benefitr×l2-cost×l3

d）動態的種子調度算法。基于上述收益公式，定義如算法3所示的動態種子選擇算法。首先，將初始種子進行執行，并將其（即種子s）添加到相應狀態下的種子池中，并計算每個種子的距離，更新每個狀態下的位圖S0和S1，其中S0和S1分別記錄該狀態下的所有種子每個基本塊被執行次數。然后，每次在一個狀態下有一個變異的種子探索了新的路徑時，將其加入到該狀態下的種子池中，并且計算其種子距離和相應的執行時間，同時更新S0和S1。當一個種子執行完畢時，需要從種子池中選擇下一個種子，通過收益選取種子，如算法4所示。具體地，計算所有種子的收益，以及種子集合S的收益總和，然后計算出每個種子收益的占比，將此占比作為種子選擇的概率，通過此概率依概率選擇下一個種子。

算法3 種子選擇模塊

輸入：當前的種子s；初始種子集合S。

輸出： 選中的種子s。

benefit_sum=calculate_benefit_sum（S）;

//計算總收益

for s in S

benefit_rate_s = benefit_s / benefit_sum;

//計算每個種子的收益占比，將其作為概率

end for

s=choose_seed_by_benefit_rate（S）;//依概率選擇選中

算法4 收益調度模塊

輸入：當前的種子s；初始種子集合S。

輸出：null。

s=choose_seed（S） //根據收益選取一個種子

power=calculate_power（s， benefit（s）） //計算能量

while power do

mutate_exec_seed（s）

if find_new_path（）

add_power（update_benefit（s）） //增加能量

update_bitmap（s， S0， S1）

add_to_seed_pool（s）

end if

decrease_power（power）

update_benefit（s）

if is_choose_next_seed（benefit（s）， S） /*如果付出過多成本而沒有預期的收益，那么本文選擇下一個種子*/

choose_next_seed（S）

end if

end while

能量分配模塊給選出的種子分配相應的能量。在該種子的執行過程中，每次執行都會付出相應的成本（即執行時間），如果該種子經過多次執行并未探索新的路徑，那么其收益由于付出的成本就會降低，能量分配模塊就會降低給其分配的能量。而如果該種子執行過程中探索了新的路徑，那么該種子的實際收益就會變高，導致整體的收益增加，能量分配模塊就會增加其分配的能量。當為該種子付出的成本而沒有得到預期收益的時候，那么就會切換種子，轉而執行下一個種子。

2.6 能量分配模塊

基于種子的收益進行能量的分配，將能量定義為分配給種子的執行時間。在有狀態協議模糊測試中，每個種子的執行時間不盡相同，因此，基于執行次數的能量分配偏差較大，而執行時間更能公平地分配能量。本文基于一個動態平均值分配能量，即每次發現新路徑需要的種子執行時間，如圖3所示。

隨著測試時間增加，需要更多的執行時間才能夠探索新的路徑，因此，平均的能量應該基于模糊的進行而改變，當前探索一條新路徑所需要的時間作為基準。收益較高的種子初始分配的能量略高于平均值，因為希望它們能有更多的時間探索新的路徑。在種子每次執行之后，將減少其能量，而如果該種子探索了新路徑，那么就會增加該種子的能量。當一個種子始終沒有探索新的路徑，就認為付出了過多的成本，而沒有獲得相應的收益，則會切換到下一個種子。

因此，根據這個當前時間的平均值來分配能量。每次選取種子時根據種子收拾增加或者減少分配的能量。在種子執行時能量會不斷減少，在種子獲得新的收益時，那么種子的能量就會增加。如果在執行過程中，該種子付出了太多的成本而沒有探索新的路徑，那么就會轉而選擇下一個種子進行執行。

3 實驗評估

3.1 實驗設置

為了對本文方法進行效果驗證，對幾款使用不同收益影響因子進行種子選擇的工具進行比較，即AFL-FAST［7］、DiPri［8］、BELIEFFUZZER［11］。AFL-FAST將執行次數作為種子收益，執行次數越少的種子收益越高；DiPri僅僅利用種子的距離作為收益；而BELIEFFUZZER使用程序控制流圖計算種子可以到達的邊，以到達的邊數作為收益，執行時間作為成本。由于這三款工具都沒有公開源碼，而且它們實現時基于覆蓋的灰盒模糊測試，所以在AFL-NET上面簡單地實現了這三種方法，使用其收益定義的方法依收益選擇種子，并進行了對覆蓋率和漏洞數量檢測的實驗。

實驗時長：24 h×5×2×3=576 h，設備參數：Intel CoreTM i7-8750H CPU @ 2.20 GHz 2.21 GHz，內存設置4 GB，操作系統版本：Ubuntu 18.04.6 LTS。

本文的單個測試實驗都設定為24 h，測試在24 h內能夠發現的漏洞數與覆蓋率情況。實驗方式：單組實驗做三次，取這三次平均的情況作為單組實驗結果進行記錄。表1記錄發現的漏洞數量，表2記錄覆蓋的邊數。

圖4記錄RTSP和DTLS的覆蓋率變化，圖5記錄RTSP和DTLS協議的漏洞發現數量的變化。

3.2 實驗結果

通過實驗結果可以發現，SCFuzzer在漏洞發現數量和覆蓋率上都優于其他的模糊測試工具。對于RTSP協議，SCFuzzer能夠覆蓋6 166條邊，相較于AFL-NET提高了大約1%，SCFuzzer能夠發現151個漏洞，相較于AFL-NET提高了大約57%。而其他使用不同收益影響因子的算法，DiPri能夠覆蓋6 032條邊，發現122個漏洞，AFL-FAST能覆蓋6 127條邊，發現105個漏洞，BELIEFFUZZER能夠覆蓋6 140條邊，發現102個漏洞。

對于DTLS協議，SCFuzzer能夠覆蓋1 893條邊，相較于AFL-NET提高了大約2%，SCFuzzer能夠發現23個漏洞，相較于AFL-NET提升了大約91%。而其他使用不同收益影響因子的算法，DiPri能夠覆蓋1 834條邊，發現18個漏洞，AFL-FAST能覆蓋1 861條邊，發現15個漏洞，BELIEFFUZZER能夠覆蓋1 880條邊，發現14個漏洞。在方案開銷方面，SCFuzzer的開銷要大于AFL-NET和AFL-FAST，但是小于DiPri和BELIEFFUZZER。

因此，SCFuzzer在覆蓋率方面有一些提升，在發現漏洞方面提升較為明顯。

3.3 結果分析

通過結果可以發現，SCFuzzer在漏洞發現數量上面有明顯的提升，是因為收益影響因子的方案會優先選擇與其他種子距離更遠的種子，這些種子由于其路徑的獨特性，更有可能潛藏著漏洞。其次，由于AFL-NET等模糊測試工具主要模糊的都是比較相似的路徑，所以就更難發現在其他代碼位置上的其他種子。還可以發現，DiPri的方案雖然發現的漏洞數量有較大的提升，然而其覆蓋率卻沒有提升反而有所下降。由于DiPri的種子距離計算方法開銷較大，所以導致該模糊測試效率降低。此外，由于DiPri的種子調度方案是靜態的，只考慮了種子的距離，所以經常會執行一些很難探索新路徑的種子，導致在這些種子上面浪費了大量的能量。而且由于DiPri沒有考慮到狀態的因素，導致該方案的種子距離計算不夠準確，也就導致了其覆蓋率的降低。AFL-FAST由于收益由低頻路徑的數量來決定，那么可能導致會經常執行很難突破的路徑分支，產生大量浪費。BELIEFFUZZER在漏洞和覆蓋率這兩方面相較于AFL-NET都有一定的提升。主要是因為其綜合考慮了成本和收益，不會在一個很難探索新路徑的種子上浪費大量的能量。但是經過分析發現，BELIEFFUZZER的主要問題在于該方案生成的程序控制流圖中沒有考慮狀態的因素，即有些邊可能只有在某個狀態才能被突破，因此對該種子收益的計算不夠準確，會將在該狀態下不能被突破的邊也計算進入收益。此外，收益高一些的種子一般都執行一些相似的路徑，所以導致BELIEFFUZZER經常執行這些高頻路徑。

本文方案相較于DiPri，根據有狀態的協議模糊測試的特點，將種子距離的計算改為了對到達該狀態后的后續報文的距離計算，并且優化了種子距離算法。但是由于考慮到了狀態，在每次添加一個種子時，需要在不同狀態的種子池中添加該種子，并計算距離，導致了額外的開銷，所以本文方案的執行速度低于AFL-NET。此外，本文使用種子距離作為潛在收益，然而種子距離并不代表可能探索的新路徑。由于根據不同狀態得到不同的程序控制流圖可能導致更多的額外開銷，所以只能選擇將可能探索的新路徑近似為種子間的距離，導致了覆蓋率的提升不夠明顯。此外，本文使用了平均探索一條新的路徑所需要的執行時間來作為能量分配的基線，通過執行時間作為成本，考慮到了有狀態的協議模糊測試中種子執行時間不盡相同的問題。總的來說，SCFuzzer在有狀態的協議模糊測試中對比先前兩種算法，考慮到了更多的影響因子，通過動態的種子調度算法和合理的收益計算以及可以接受的額外開銷，發現更多的漏洞，對于覆蓋率的提升有限。

4 相關工作

有狀態的協議模糊測試由AFL-NET首次提出，其在AFL的基礎上考慮了狀態的因素，并將其被測程序改為網絡應用程序。AFL-NET可以支持多種協議，繼承了AFL等基于覆蓋的灰盒模糊測試的特點。AFL-NET對狀態的定義是基于報文的響應碼，根據不同協議的不同響應碼人為定義狀態，然而這種方式并不能真正地表示服務器的狀態。因此，文獻［12］提出了StateFuzz，StateFuzz利用一般服務器會利用一些枚舉變量表示服務器狀態的特性，通過追蹤這些枚舉變量的改變來確定當前服務器的狀態。NSFuzz［13］與其類似，通過服務器中的狀態變量定義服務的狀態，并且檢測服務器是否完成一個收發循環，完成一個收發循環之后則立馬進行下一次測試，提高了效率。Natella［14］更進一步提出了StateAFL，StateAFL會自動推斷服務器的狀態，StateAFL通過追蹤被測服務程序內存中的長生存周期的變量來自動推斷服務器的狀態。SNPSFuzzer［15］通過快照機制，保存服務器的各種狀態，下次需要模糊該狀態時只需要通過快照恢復該服務器的狀態，減少了需要發送前序報文的操作，加快了模糊測試的執行速度。Snapfuzz［16］考慮了將緩慢的Socket異步網絡通信轉換為基于UNIX域套接字的快速同步通信。PAVFuzz［17］提出在不同狀態下應該進行針對性突變，此想法來源于傳統的模糊器對每個數據元素或字節/比特都一視同仁，在每次模糊迭代中具有相同的變異概率。但是，考慮到不同協議狀態之間的復雜關系，協議狀態會受到之前發送數據包的影響，因此狀態中受影響的數據元素應給予較高的變異機會。

5 結束語

針對當前有狀態的協議模糊測試調度和能量分配的問題，本文提出了一種基于種子距離的種子調度算法。本文優化了種子距離的計算算法，并且將種子距離近似為種子的潛在收益，將種子探索的新路徑近似為實際收益，將種子執行時間近似為成本，通過這些輸入進行種子的調度，并使用平均探索一條新路徑的執行時間作為基線來動態分配能量。本文方案在同等的實驗環境下，對比其他的方案覆蓋率和漏洞發現數量都有提升，說明了其效果。

參考文獻：

［1］徐威， 李鵬， 張文鑌， 等. 網絡協議模糊測試綜述［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.）

［2］楊克， 賀也平， 馬恒太， 等. 有效覆蓋引導的定向灰盒模糊測試［J］. 軟件學報， 2021， 33（11）： 3967-3982. （Yang Ke， He Yeping， Ma Hengtai， et al. Effective cover-guided directional gray-box fuzzing［J］. Journal of Software， 2021， 33（11）： 3967-3982.）

［3］盧昊良， 鄒燕燕， 彭躍， 等. 基于物聯網設備局部仿真的反饋式模糊測試技術［J］. 信息安全學報， 2023， 8（1）： 78-92. （Lu Hao-liang， Zou Yanyan， Peng Yue， et al. Feedback-driven fuzzing tech-nology based on partial simulation of IoT devices［J］. Journal of Cyber Security， 2023， 8（1）： 78-92.）

［4］張冠宇， 尚文利， 張博文， 等. 一種結合遺傳算法的工控協議模糊測試方法［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.）

［5］Pham V T， Bhme M， Roychoudhury A. AFLNET： a greybox fuzzer for network protocols［C］//Proc of the 13th IEEE International Conference on Software Testing， Validation and Verification. Piscataway， NJ： IEEE Press， 2020： 460-465.

［6］Yue Tai， Wang Pengfei， Tang Yong， et al. EcoFuzz： adaptive energy-saving greybox fuzzing as a variant of the adversarial multi-armed bandit［C］//Proc of the 29th USENIX Conference on Security Symposium.［S.l.］： USENIX Association，2020： 2307-2324.

［7］Bhme M， Pham V T， Roychoudhury A. Coverage-based greybox fuzzing as Markov chain［C］//Proc of ACM SIGSAC Conference on Computer and Communications Security. New York ：ACM Press， 2016： 1032-1043.

［8］Qian Ruixiang， Zhang Quanjun， Fang Chunrong， et al. DiPri： distance-based seed prioritization for greybox fuzzing（registered report）［C］//Proc of the 2nd International Fuzzing Workshop. New York： ACM Press， 2023： 21-30.

［9］Zhang Kunpeng， Xiao Xi， Zhu Xiaogang， et al. Path transitions tell more： optimizing fuzzing schedules via runtime program states［C］//Proc of the 44th International Conference on Software Engineering. Piscataway， NJ： IEEE Press， 2022： 1658-1668.

［10］She Dongdong， Shah A， Jana S. Effective seed scheduling for fuzzing with graph centrality analysis［C］//Proc of IEEE Symposium on Security and Privacy. Piscataway， NJ： IEEE Press， 2022： 2194-2211.

［11］Huang Heqing， Chiu H C， Shi Qingkai， et al. Balance seed scheduling via Monte Carlo planning［J］. IEEE Trans on Dependable and Secure Computing， 2024， 21（3）： 1469-1483.

［12］Zhao Bodong， Li Zheming， Qin Shisong， et al. StateFuzz： system call-based state-aware Linux driver fuzzing［C］//Proc of the 31st USENIX Security Symposium. 2022： 3273-3289.

［13］Qin Shisong， Hu Fan， Ma Zheyu， et al. NSFuzz： towards efficient and state-aware network service fuzzing［J］. ACM Trans on Software Engineering and Methodology， 2023，32（6）：1-26.

［14］Natella R. StateAFL： greybox fuzzing for stateful network servers［J］. Empirical Software Engineering， 2022， 27（7）： 191.

［15］Li Junqiang， Li Senyi， Sun Gang， et al. SNPSFuzzer： a fast greybox fuzzer for stateful network protocols using snapshots［J］. IEEE Trans on Information Forensics and Security， 2022， 17： 2673-2687.

［16］Andronidis A， Cadar C. SnapFuzz： high-throughput fuzzing of network applications［C］//Proc of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis. New York： ACM Press， 2022： 340-351.

［17］Zuo Feilong， Luo Zhengxiong， Yu Junze， et al. PAVFuzz： state-sensitive fuzz testing of protocols in autonomous vehicles［C］//Proc of the 58th ACM/IEEE Design Automation Conference. Piscataway， NJ： IEEE Press， 2021： 823-828.