摘 要：為了探索有狀態(tài)協(xié)議的程序漏洞，AFL-NET提出了有狀態(tài)協(xié)議模糊測(cè)試。在有狀態(tài)協(xié)議模糊測(cè)試中，種子的選擇對(duì)路徑的探索有著重大的貢獻(xiàn)。然而，目前的有狀態(tài)協(xié)議模糊測(cè)試往往重復(fù)執(zhí)行幾個(gè)相同的種子，導(dǎo)致不能很好地探索更多的路徑。為了緩解該問(wèn)題，從種子的收益入手，提出了一種有效的基于有狀態(tài)協(xié)議的種子動(dòng)態(tài)調(diào)度算法。利用種子的潛在收益和實(shí)際收益以及成本作為收益，利用收益來(lái)進(jìn)行動(dòng)態(tài)的種子調(diào)度，并分配種子的執(zhí)行次數(shù)。實(shí)驗(yàn)表明，該方法在漏洞發(fā)現(xiàn)數(shù)量上有顯著提升，在提高覆蓋率方面也有一定的提升，說(shuō)明此收益定義以及種子調(diào)度算法能有效選擇種子，探索更多的路徑以及漏洞。

關(guān)鍵詞：模糊測(cè)試； 灰盒； 協(xié)議測(cè)試； 漏洞挖掘

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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

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

對(duì)于有狀態(tài)協(xié)議模糊測(cè)試如何優(yōu)化，目前主要的研究方向有四點(diǎn)：a）對(duì)變異算法的改進(jìn)；b）對(duì)狀態(tài)選擇的改進(jìn)；c）對(duì)種子的選擇；d）提高效率。

當(dāng)前的有狀態(tài)協(xié)議模糊測(cè)試對(duì)于種子的選擇主要考慮種子收益，即種子探索新路徑的能力。一般從路徑的轉(zhuǎn)移概率、種子中新路徑數(shù)量、種子中獨(dú)特的狀態(tài)個(gè)數(shù)、種子執(zhí)行時(shí)間來(lái)進(jìn)行考慮，并且通過(guò)這些數(shù)據(jù)來(lái)計(jì)算給種子分配的能量（即該種子執(zhí)行多少次變異）。然后，將增加了新覆蓋的種子加入到種子池中。然而，這種方式無(wú)法進(jìn)行種子的動(dòng)態(tài)選擇，比如，一個(gè)種子在執(zhí)行過(guò)程中產(chǎn)生了新的覆蓋，那么理所當(dāng)然該種子的收益更大，選擇該種子的概率越大。然而，這種方式在第一次執(zhí)行時(shí)就確定了該種子的收益，無(wú)法根據(jù)程序的執(zhí)行動(dòng)態(tài)增加或者減少該種子的收益。因此，動(dòng)態(tài)計(jì)算種子收益、動(dòng)態(tài)選擇種子、動(dòng)態(tài)能量分配十分重要。

針對(duì)上述問(wèn)題，本文提出了一種輕量級(jí)的動(dòng)態(tài)種子調(diào)度算法和能量分配算法SCFuzzer。SCFuzzer利用種子潛在收益、實(shí)際收益、成本進(jìn)行動(dòng)態(tài)概率分配和能量分配，通過(guò)在模糊執(zhí)行過(guò)程中動(dòng)態(tài)計(jì)算種子的收益來(lái)調(diào)度種子，實(shí)現(xiàn)種子調(diào)度的優(yōu)化。

本文主要貢獻(xiàn)如下：

a）提出了一種基于種子潛在收益、實(shí)際收益和成本來(lái)動(dòng)態(tài)計(jì)算收益并調(diào)度種子的算法。從多方面考慮種子探索新路徑的能力，并給出了一種有效性度量，實(shí)現(xiàn)動(dòng)態(tài)的種子調(diào)度。

b）基于該度量實(shí)現(xiàn)了種子的動(dòng)態(tài)能量分配策略，對(duì)重點(diǎn)種子執(zhí)行更多次數(shù)的變異，使其能夠有更多時(shí)間進(jìn)行對(duì)程序空間的探索。

c）基于AFLNET［5］實(shí)現(xiàn)了SCFuzzer，并在廣泛使用的RTSP和DTLS協(xié)議中進(jìn)行了實(shí)驗(yàn)測(cè)試。在24 h的實(shí)驗(yàn)中，對(duì)覆蓋率的提升約2%，對(duì)漏洞發(fā)現(xiàn)數(shù)量提升約50%。

1 背景和動(dòng)機(jī)

1.1 研究動(dòng)機(jī)

在本節(jié)中，通過(guò)一個(gè)例子來(lái)說(shuō)明種子的選擇對(duì)模糊器在路徑探索中的影響。在算法中，使用靜態(tài)的種子選擇策略，假設(shè)有兩個(gè)種子S1和S2，種子S1的執(zhí)行路徑為7->11->12，種子S2的執(zhí)行路徑為7->8->2->4。假設(shè)在先前的執(zhí)行中，S2更有可能被選中，那么S2會(huì)持續(xù)執(zhí)行，但是最終S2會(huì)一直執(zhí)行到代碼行4的判斷語(yǔ)句，因?yàn)樵撆袛嗾Z(yǔ)句很難被突破，它是字符串的比較，那么在很長(zhǎng)的一段時(shí)間內(nèi)S2都不會(huì)探索新的路徑。而種子S1在先前的執(zhí)行中被選中的概率較小，但它更有可能探索新的路徑。

算法1 不同種子執(zhí)行路徑的探索

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 }

因此，如果使用靜態(tài)的種子調(diào)度算法，那么就不能很好地反映種子在執(zhí)行過(guò)程中不斷變化發(fā)現(xiàn)新執(zhí)行路徑的能力。

1.2 研究背景

如上所述，AFL-NET在種子調(diào)度上并沒(méi)有很好地利用程序執(zhí)行過(guò)程中的信息，導(dǎo)致可能會(huì)長(zhǎng)時(shí)間選擇同一個(gè)很難探索新路徑的種子，而且選擇的種子大多執(zhí)行的都是相同的路徑。事實(shí)上，已經(jīng)有許多研究表明，種子的選擇對(duì)于模糊測(cè)試來(lái)說(shuō)非常重要。

有狀態(tài)協(xié)議模糊測(cè)試中，對(duì)于種子調(diào)度尚未有充分的研究。而在基于覆蓋的灰盒模糊測(cè)試中，已經(jīng)有許多對(duì)于種子調(diào)度的研究，它們考慮了影響種子收益的不同影響因子，大致可以分為兩類(lèi)：

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

b）基于程序控制流圖。在基于控制流圖的相關(guān)研究中，確定一個(gè)種子選取的概率和能量主要基于該種子的執(zhí)行路徑上有多少未探索的路徑。K-Scheduler［10］利用圖的中心性對(duì)一個(gè)種子計(jì)算得分，分?jǐn)?shù)越高的種子收益越高。K-Scheduler提出了一種方法，將程序控制流圖轉(zhuǎn)換為邊緣視界圖，通過(guò)該圖計(jì)算一個(gè)種子的得分。BELIEFFUZZE［11］提出了一種平衡收益和成本的種子調(diào)度算法。一個(gè)種子的收益是基于程序控制流圖中該種子變異之后可能覆蓋的潛在路徑的數(shù)量來(lái)計(jì)算的，而成本定義為該種子的執(zhí)行次數(shù)。BELIEFFUZZE綜合考慮了一個(gè)種子的收益和成本，收益高的種子優(yōu)先執(zhí)行，但是如果對(duì)該種子付出了難以接受的成本，而該種子并未探索新的路徑，那么就應(yīng)該放棄該種子?；诔绦蚩刂屏鲌D的方法需要得到程序的控制流圖，然而，在有狀態(tài)的協(xié)議模糊測(cè)試中，在不同狀態(tài)下，程序的走向不同，那么程序的控制流圖也會(huì)不同。因此，在有狀態(tài)的協(xié)議模糊測(cè)試中使用該方法會(huì)導(dǎo)致更多額外的開(kāi)銷(xiāo)。

為了解決有狀態(tài)的協(xié)議模糊測(cè)試中，種子調(diào)度和能量分配的問(wèn)題，使得選取的種子能更加有效地探索新路徑，并給其分配適應(yīng)的能量。本文提出了一種在有狀態(tài)的協(xié)議模糊測(cè)試下，能夠動(dòng)態(tài)調(diào)度種子并分配能量的輕量級(jí)算法。

2 方法概述

2.1 種子收益的影響因子

本文目標(biāo)是對(duì)更能探索新路徑的種子進(jìn)行更多變異測(cè)試，因此應(yīng)該選擇更能探索新路徑的種子。本文將能夠探索新路徑的能力映射為種子的收益。

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

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

2.2 種子距離算法

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

2.3 使用種子距離的動(dòng)機(jī)

使用程序控制流圖計(jì)算種子收益的缺點(diǎn)已在1.2節(jié)詳細(xì)闡述。因此，本文更傾向于使用歷史信息來(lái)計(jì)算一個(gè)種子的收益。其中，種子的距離能更好地體現(xiàn)出一個(gè)種子的潛在收益，即一個(gè)種子能探索新路徑的潛在能力。以圖1為例，假設(shè)有5個(gè)種子，其中S1、S2、S3、S4的執(zhí)行路徑都集中在程序代碼空間的一部分，而S5在程序代碼空間的其他部分。那么直觀地發(fā)現(xiàn)S5周?chē)梢蕴剿鞯目臻g比其他四個(gè)種子都要大，因此種子S5的潛在收益更大。然而，由于只是將種子距離近似為程序控制流圖中一個(gè)種子可能探索的新路徑，有的路徑可能很難被突破，所以將其認(rèn)為是該種子潛在的收益。

2.4 框架

本文的設(shè)計(jì)方案工作流程如圖2所示，其中紅色框中的內(nèi)容即為本文的主要內(nèi)容，其主要分為收益調(diào)度和能量分配兩個(gè)模塊。由這兩個(gè)模塊共同組成本文的動(dòng)態(tài)種子調(diào)度算法和能量分配算法，通過(guò)這兩個(gè)模塊，可以動(dòng)態(tài)地選擇種子和切換種子，動(dòng)態(tài)地改變一個(gè)種子的能量分配。

2.5 收益調(diào)度模塊

如2.1節(jié)，本文目標(biāo)是對(duì)更能探索新路徑的種子進(jìn)行更多變異測(cè)試，因此，種子收益即為種子探索新路徑的能力。種子執(zhí)行路徑旁的未探索路徑的數(shù)量表明了該種子還可以探索多少條新路徑。種子實(shí)際探索路徑的數(shù)量表明該種子將未探索路徑轉(zhuǎn)換為已探索路徑的能力。種子執(zhí)行花費(fèi)的時(shí)間表明該種子探索新路徑花費(fèi)的時(shí)間成本。這三元組規(guī)定了種子探索新路徑的潛在能力，探索新路徑的實(shí)際能力和探索新路徑的成本，因此該三元組即可很好地表明一個(gè)種子探索新路徑的能力。綜上所述，將一個(gè)種子的收益定義成潛在收益、實(shí)際收益和成本三個(gè)方面。

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

潛在收益的計(jì)算：將潛在收益定義為種子的距離，其計(jì)算方法和DiPri類(lèi)似，使用海明距離通過(guò)位圖來(lái)計(jì)算種子與其他種子的距離，將其距離之和作為種子的潛在收益。與DiPri不同的是，首先DiPri沒(méi)有狀態(tài)的概念，在AFL-NET中一個(gè)種子對(duì)應(yīng)于多個(gè)報(bào)文，首先需要發(fā)送前序報(bào)文到達(dá)指定狀態(tài)，然后才能發(fā)送需要變異的報(bào)文，其中的一個(gè)報(bào)文對(duì)應(yīng)于DiPri中的一個(gè)種子。因此，在AFL-NET中所關(guān)注的種子距離會(huì)受到前序報(bào)文的影響。如果兩個(gè)種子到達(dá)該狀態(tài)時(shí)執(zhí)行的路徑距離很遠(yuǎn)，然而執(zhí)行變異報(bào)文而探索的路徑距離幾乎一致，則認(rèn)為這兩個(gè)種子距離相近。因?yàn)樾枰紤]的是到達(dá)同一個(gè)狀態(tài)之后種子的距離，而DiPri就沒(méi)有考慮到狀態(tài)，導(dǎo)致所發(fā)送的前序報(bào)文會(huì)污染種子的距離。因此，本文提出的種子距離的計(jì)算需要剔除掉前序報(bào)文的影響，單獨(dú)計(jì)算變異報(bào)文探索路徑的距離。此外，如果每次單獨(dú)計(jì)算種子的距離，如果有n個(gè)種子，那么每次添加一個(gè)種子都需要計(jì)算n次再次求和。因此提出了一種優(yōu)化的種子距離算法，通過(guò)海明距離計(jì)算，其公式如下：

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

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

算法2 距離計(jì)算模塊

輸入： 當(dāng)前的種子s；位圖S0，S1；位圖的長(zhǎng)度size。

輸出： 種子s的距離。

pre=get_pre_message（s） //獲取種子的前序報(bào)文路徑

trace_bit_pre=exec_pre_message（pre） //計(jì)算前序報(bào)文的路徑

trace_bit=exec_message（s） //計(jì)算整個(gè)種子的路徑

for j=0 to size do

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

//計(jì)算后續(xù)報(bào)文路徑

end for

for i=0 to size do //計(jì)算路徑距離

if （race_bit_bef［i］==0）

distance=distance + S1［i］

else

distance = distance + S0［i］

end if

end for

b）實(shí)際收益。將實(shí)際收益定義為該種子探索新路徑的數(shù)量。實(shí)際收益能夠表明種子將潛在收益轉(zhuǎn)換為收益的能力，即探索潛在路徑的能力。通過(guò)實(shí)際收益可以解決先前工作可能會(huì)將大量時(shí)間浪費(fèi)在很難產(chǎn)生新覆蓋的種子上，并進(jìn)行種子的動(dòng)態(tài)調(diào)度。

c）成本。將成本定義為種子的執(zhí)行時(shí)間。先前的工作將成本定義為種子的執(zhí)行次數(shù)，在基于覆蓋的灰盒測(cè)試中，例如BELIEFFUZZE，提出了以執(zhí)行次數(shù)作為成本，這是可行的，因?yàn)槊總€(gè)種子執(zhí)行的時(shí)間都很快，而且都大致相同。而在有狀態(tài)的協(xié)議模糊測(cè)試中，每個(gè)種子的執(zhí)行時(shí)間可能相差很大。這是因?yàn)樵谟袪顟B(tài)的協(xié)議模糊測(cè)試中，每個(gè)種子中的報(bào)文數(shù)量也不盡相同，有的種子的前序報(bào)文很短，可能很快就能執(zhí)行完成，有的種子的前序報(bào)文可能很長(zhǎng)，所有需要更多的執(zhí)行時(shí)間，因此使用執(zhí)行時(shí)間來(lái)衡量種子的成本。本文基于以下的事實(shí)，即潛在收益是固定的，根據(jù)種子距離表明該種子能探索新路徑的潛在能力，而實(shí)際收益根據(jù)該種子是否真正探索了新路徑，表明該種子的真正能力，而成本根據(jù)種子的執(zhí)行時(shí)間，表明付出的成本是否得到了預(yù)期的收益，因此定義種子的收益為

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

d）動(dòng)態(tài)的種子調(diào)度算法?；谏鲜鍪找婀剑x如算法3所示的動(dòng)態(tài)種子選擇算法。首先，將初始種子進(jìn)行執(zhí)行，并將其（即種子s）添加到相應(yīng)狀態(tài)下的種子池中，并計(jì)算每個(gè)種子的距離，更新每個(gè)狀態(tài)下的位圖S0和S1，其中S0和S1分別記錄該狀態(tài)下的所有種子每個(gè)基本塊被執(zhí)行次數(shù)。然后，每次在一個(gè)狀態(tài)下有一個(gè)變異的種子探索了新的路徑時(shí)，將其加入到該狀態(tài)下的種子池中，并且計(jì)算其種子距離和相應(yīng)的執(zhí)行時(shí)間，同時(shí)更新S0和S1。當(dāng)一個(gè)種子執(zhí)行完畢時(shí)，需要從種子池中選擇下一個(gè)種子，通過(guò)收益選取種子，如算法4所示。具體地，計(jì)算所有種子的收益，以及種子集合S的收益總和，然后計(jì)算出每個(gè)種子收益的占比，將此占比作為種子選擇的概率，通過(guò)此概率依概率選擇下一個(gè)種子。

算法3 種子選擇模塊

輸入：當(dāng)前的種子s；初始種子集合S。

輸出： 選中的種子s。

benefit_sum=calculate_benefit_sum（S）;

//計(jì)算總收益

for s in S

benefit_rate_s = benefit_s / benefit_sum;

//計(jì)算每個(gè)種子的收益占比，將其作為概率

end for

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

算法4 收益調(diào)度模塊

輸入：當(dāng)前的種子s；初始種子集合S。

輸出：null。

s=choose_seed（S） //根據(jù)收益選取一個(gè)種子

power=calculate_power（s， benefit（s）） //計(jì)算能量

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） /*如果付出過(guò)多成本而沒(méi)有預(yù)期的收益，那么本文選擇下一個(gè)種子*/

choose_next_seed（S）

end if

end while

能量分配模塊給選出的種子分配相應(yīng)的能量。在該種子的執(zhí)行過(guò)程中，每次執(zhí)行都會(huì)付出相應(yīng)的成本（即執(zhí)行時(shí)間），如果該種子經(jīng)過(guò)多次執(zhí)行并未探索新的路徑，那么其收益由于付出的成本就會(huì)降低，能量分配模塊就會(huì)降低給其分配的能量。而如果該種子執(zhí)行過(guò)程中探索了新的路徑，那么該種子的實(shí)際收益就會(huì)變高，導(dǎo)致整體的收益增加，能量分配模塊就會(huì)增加其分配的能量。當(dāng)為該種子付出的成本而沒(méi)有得到預(yù)期收益的時(shí)候，那么就會(huì)切換種子，轉(zhuǎn)而執(zhí)行下一個(gè)種子。

2.6 能量分配模塊

基于種子的收益進(jìn)行能量的分配，將能量定義為分配給種子的執(zhí)行時(shí)間。在有狀態(tài)協(xié)議模糊測(cè)試中，每個(gè)種子的執(zhí)行時(shí)間不盡相同，因此，基于執(zhí)行次數(shù)的能量分配偏差較大，而執(zhí)行時(shí)間更能公平地分配能量。本文基于一個(gè)動(dòng)態(tài)平均值分配能量，即每次發(fā)現(xiàn)新路徑需要的種子執(zhí)行時(shí)間，如圖3所示。

隨著測(cè)試時(shí)間增加，需要更多的執(zhí)行時(shí)間才能夠探索新的路徑，因此，平均的能量應(yīng)該基于模糊的進(jìn)行而改變，當(dāng)前探索一條新路徑所需要的時(shí)間作為基準(zhǔn)。收益較高的種子初始分配的能量略高于平均值，因?yàn)橄Ｍ鼈兡苡懈嗟臅r(shí)間探索新的路徑。在種子每次執(zhí)行之后，將減少其能量，而如果該種子探索了新路徑，那么就會(huì)增加該種子的能量。當(dāng)一個(gè)種子始終沒(méi)有探索新的路徑，就認(rèn)為付出了過(guò)多的成本，而沒(méi)有獲得相應(yīng)的收益，則會(huì)切換到下一個(gè)種子。

因此，根據(jù)這個(gè)當(dāng)前時(shí)間的平均值來(lái)分配能量。每次選取種子時(shí)根據(jù)種子收拾增加或者減少分配的能量。在種子執(zhí)行時(shí)能量會(huì)不斷減少，在種子獲得新的收益時(shí)，那么種子的能量就會(huì)增加。如果在執(zhí)行過(guò)程中，該種子付出了太多的成本而沒(méi)有探索新的路徑，那么就會(huì)轉(zhuǎn)而選擇下一個(gè)種子進(jìn)行執(zhí)行。

3 實(shí)驗(yàn)評(píng)估

3.1 實(shí)驗(yàn)設(shè)置

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

實(shí)驗(yàn)時(shí)長(zhǎng)：24 h×5×2×3=576 h，設(shè)備參數(shù)：Intel CoreTM i7-8750H CPU @ 2.20 GHz 2.21 GHz，內(nèi)存設(shè)置4 GB，操作系統(tǒng)版本：Ubuntu 18.04.6 LTS。

本文的單個(gè)測(cè)試實(shí)驗(yàn)都設(shè)定為24 h，測(cè)試在24 h內(nèi)能夠發(fā)現(xiàn)的漏洞數(shù)與覆蓋率情況。實(shí)驗(yàn)方式：?jiǎn)谓M實(shí)驗(yàn)做三次，取這三次平均的情況作為單組實(shí)驗(yàn)結(jié)果進(jìn)行記錄。表1記錄發(fā)現(xiàn)的漏洞數(shù)量，表2記錄覆蓋的邊數(shù)。

圖4記錄RTSP和DTLS的覆蓋率變化，圖5記錄RTSP和DTLS協(xié)議的漏洞發(fā)現(xiàn)數(shù)量的變化。

3.2 實(shí)驗(yàn)結(jié)果

通過(guò)實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，SCFuzzer在漏洞發(fā)現(xiàn)數(shù)量和覆蓋率上都優(yōu)于其他的模糊測(cè)試工具。對(duì)于RTSP協(xié)議，SCFuzzer能夠覆蓋6 166條邊，相較于AFL-NET提高了大約1%，SCFuzzer能夠發(fā)現(xiàn)151個(gè)漏洞，相較于AFL-NET提高了大約57%。而其他使用不同收益影響因子的算法，DiPri能夠覆蓋6 032條邊，發(fā)現(xiàn)122個(gè)漏洞，AFL-FAST能覆蓋6 127條邊，發(fā)現(xiàn)105個(gè)漏洞，BELIEFFUZZER能夠覆蓋6 140條邊，發(fā)現(xiàn)102個(gè)漏洞。

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

因此，SCFuzzer在覆蓋率方面有一些提升，在發(fā)現(xiàn)漏洞方面提升較為明顯。

3.3 結(jié)果分析

通過(guò)結(jié)果可以發(fā)現(xiàn)，SCFuzzer在漏洞發(fā)現(xiàn)數(shù)量上面有明顯的提升，是因?yàn)槭找嬗绊懸蜃拥姆桨笗?huì)優(yōu)先選擇與其他種子距離更遠(yuǎn)的種子，這些種子由于其路徑的獨(dú)特性，更有可能潛藏著漏洞。其次，由于AFL-NET等模糊測(cè)試工具主要模糊的都是比較相似的路徑，所以就更難發(fā)現(xiàn)在其他代碼位置上的其他種子。還可以發(fā)現(xiàn)，DiPri的方案雖然發(fā)現(xiàn)的漏洞數(shù)量有較大的提升，然而其覆蓋率卻沒(méi)有提升反而有所下降。由于DiPri的種子距離計(jì)算方法開(kāi)銷(xiāo)較大，所以導(dǎo)致該模糊測(cè)試效率降低。此外，由于DiPri的種子調(diào)度方案是靜態(tài)的，只考慮了種子的距離，所以經(jīng)常會(huì)執(zhí)行一些很難探索新路徑的種子，導(dǎo)致在這些種子上面浪費(fèi)了大量的能量。而且由于DiPri沒(méi)有考慮到狀態(tài)的因素，導(dǎo)致該方案的種子距離計(jì)算不夠準(zhǔn)確，也就導(dǎo)致了其覆蓋率的降低。AFL-FAST由于收益由低頻路徑的數(shù)量來(lái)決定，那么可能導(dǎo)致會(huì)經(jīng)常執(zhí)行很難突破的路徑分支，產(chǎn)生大量浪費(fèi)。BELIEFFUZZER在漏洞和覆蓋率這兩方面相較于AFL-NET都有一定的提升。主要是因?yàn)槠渚C合考慮了成本和收益，不會(huì)在一個(gè)很難探索新路徑的種子上浪費(fèi)大量的能量。但是經(jīng)過(guò)分析發(fā)現(xiàn)，BELIEFFUZZER的主要問(wèn)題在于該方案生成的程序控制流圖中沒(méi)有考慮狀態(tài)的因素，即有些邊可能只有在某個(gè)狀態(tài)才能被突破，因此對(duì)該種子收益的計(jì)算不夠準(zhǔn)確，會(huì)將在該狀態(tài)下不能被突破的邊也計(jì)算進(jìn)入收益。此外，收益高一些的種子一般都執(zhí)行一些相似的路徑，所以導(dǎo)致BELIEFFUZZER經(jīng)常執(zhí)行這些高頻路徑。

本文方案相較于DiPri，根據(jù)有狀態(tài)的協(xié)議模糊測(cè)試的特點(diǎn)，將種子距離的計(jì)算改為了對(duì)到達(dá)該狀態(tài)后的后續(xù)報(bào)文的距離計(jì)算，并且優(yōu)化了種子距離算法。但是由于考慮到了狀態(tài)，在每次添加一個(gè)種子時(shí)，需要在不同狀態(tài)的種子池中添加該種子，并計(jì)算距離，導(dǎo)致了額外的開(kāi)銷(xiāo)，所以本文方案的執(zhí)行速度低于AFL-NET。此外，本文使用種子距離作為潛在收益，然而種子距離并不代表可能探索的新路徑。由于根據(jù)不同狀態(tài)得到不同的程序控制流圖可能導(dǎo)致更多的額外開(kāi)銷(xiāo)，所以只能選擇將可能探索的新路徑近似為種子間的距離，導(dǎo)致了覆蓋率的提升不夠明顯。此外，本文使用了平均探索一條新的路徑所需要的執(zhí)行時(shí)間來(lái)作為能量分配的基線，通過(guò)執(zhí)行時(shí)間作為成本，考慮到了有狀態(tài)的協(xié)議模糊測(cè)試中種子執(zhí)行時(shí)間不盡相同的問(wèn)題?？偟膩?lái)說(shuō)，SCFuzzer在有狀態(tài)的協(xié)議模糊測(cè)試中對(duì)比先前兩種算法，考慮到了更多的影響因子，通過(guò)動(dòng)態(tài)的種子調(diào)度算法和合理的收益計(jì)算以及可以接受的額外開(kāi)銷(xiāo)，發(fā)現(xiàn)更多的漏洞，對(duì)于覆蓋率的提升有限。

4 相關(guān)工作

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

5 結(jié)束語(yǔ)

針對(duì)當(dāng)前有狀態(tài)的協(xié)議模糊測(cè)試調(diào)度和能量分配的問(wèn)題，本文提出了一種基于種子距離的種子調(diào)度算法。本文優(yōu)化了種子距離的計(jì)算算法，并且將種子距離近似為種子的潛在收益，將種子探索的新路徑近似為實(shí)際收益，將種子執(zhí)行時(shí)間近似為成本，通過(guò)這些輸入進(jìn)行種子的調(diào)度，并使用平均探索一條新路徑的執(zhí)行時(shí)間作為基線來(lái)動(dòng)態(tài)分配能量。本文方案在同等的實(shí)驗(yàn)環(huán)境下，對(duì)比其他的方案覆蓋率和漏洞發(fā)現(xiàn)數(shù)量都有提升，說(shuō)明了其效果。

參考文獻(xiàn)：

［1］徐威， 李鵬， 張文鑌， 等. 網(wǎng)絡(luò)協(xié)議模糊測(cè)試綜述［J］. 計(jì)算機(jī)應(yīng)用研究， 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］楊克， 賀也平， 馬恒太， 等. 有效覆蓋引導(dǎo)的定向灰盒模糊測(cè)試［J］. 軟件學(xué)報(bào)， 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］盧昊良， 鄒燕燕， 彭躍， 等. 基于物聯(lián)網(wǎng)設(shè)備局部仿真的反饋式模糊測(cè)試技術(shù)［J］. 信息安全學(xué)報(bào)， 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］張冠宇， 尚文利， 張博文， 等. 一種結(jié)合遺傳算法的工控協(xié)議模糊測(cè)試方法［J］. 計(jì)算機(jī)應(yīng)用研究， 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.