基于協(xié)議狀態(tài)機(jī)遍歷的模糊測(cè)試優(yōu)化方法

張洪澤，洪 征，周勝利，馮文博

1.中國(guó)人民解放軍陸軍工程大學(xué) 指揮控制工程學(xué)院，南京210000

2.浙江警察學(xué)院 計(jì)算機(jī)與信息技術(shù)系，杭州310000

1 引言

協(xié)議漏洞挖掘是保證網(wǎng)絡(luò)通信安全的重要手段。模糊測(cè)試是目前最常用的協(xié)議漏洞挖掘方法，它通過(guò)向協(xié)議實(shí)體輸入變異的報(bào)文，監(jiān)控協(xié)議實(shí)體的運(yùn)行狀況，分析協(xié)議實(shí)體發(fā)生的異常，從而發(fā)現(xiàn)潛在的安全漏洞。模糊測(cè)試具有自動(dòng)化程度高、發(fā)現(xiàn)的漏洞實(shí)際可用等優(yōu)點(diǎn)[1]。

根據(jù)輸入報(bào)文相互之間是否存在關(guān)聯(lián)關(guān)系，網(wǎng)絡(luò)通信協(xié)議可分為無(wú)狀態(tài)協(xié)議（Stateless Protocol）和有狀態(tài)協(xié)議（Stateful Protocol）兩類[2]。無(wú)狀態(tài)協(xié)議是指報(bào)文發(fā)送方輸出的各個(gè)報(bào)文之間沒(méi)有關(guān)聯(lián)性，例如ICMP協(xié)議的每個(gè)請(qǐng)求報(bào)文各自獨(dú)立，相互之間沒(méi)有關(guān)聯(lián)關(guān)系。而對(duì)于有狀態(tài)協(xié)議，協(xié)議實(shí)體會(huì)記錄所接收到的報(bào)文信息，在處理報(bào)文后可能會(huì)出現(xiàn)協(xié)議狀態(tài)的變化，例如FTP協(xié)議與SMTP協(xié)議都屬于有狀態(tài)協(xié)議。相比于無(wú)狀態(tài)協(xié)議模糊測(cè)試，對(duì)有狀態(tài)協(xié)議進(jìn)行模糊測(cè)試更復(fù)雜。因?yàn)楫?dāng)測(cè)試用例與協(xié)議實(shí)體狀態(tài)不匹配時(shí)，測(cè)試用例會(huì)被直接丟棄，為了保證測(cè)試用例盡可能被協(xié)議實(shí)體接受，測(cè)試時(shí)需要依賴協(xié)議的狀態(tài)模型，根據(jù)協(xié)議實(shí)體所處的協(xié)議狀態(tài)輸入測(cè)試用例[3]。

網(wǎng)絡(luò)通信協(xié)議的模糊測(cè)試最早可追溯到1999年芬蘭Oulu大學(xué)研發(fā)的網(wǎng)絡(luò)協(xié)議安全測(cè)試軟件PROTOS[4]。PROTOS發(fā)現(xiàn)了不少的協(xié)議實(shí)體程序的安全漏洞，但是它不是通用的測(cè)試框架，軟件靈活性較差，應(yīng)用范圍狹窄。2002年，Aitel開(kāi)發(fā)了一款通用協(xié)議測(cè)試框架工具SPIKE[5]。SPIKE是一款可以定制的模糊測(cè)試器框架，能夠方便地實(shí)現(xiàn)代碼重用，但是不能靈活描述報(bào)文中字段之間的約束關(guān)系，并且SPIKE只適用于無(wú)狀態(tài)網(wǎng)絡(luò)協(xié)議的測(cè)試，應(yīng)用范圍受限。2013年，IOACTIVE發(fā)布了著名模糊測(cè)試框架Peach 3.0[6]。Peach 3.0是一個(gè)靈活的模糊測(cè)試框架，使用XML文件作為測(cè)試腳本來(lái)定義測(cè)試對(duì)象以及測(cè)試方法，充分利用了XML文件低耦合、易分離的優(yōu)點(diǎn)，促進(jìn)了模糊測(cè)試代碼的重用。除了上述測(cè)試工具，研究者也提出不少模糊測(cè)試的優(yōu)化方法。例如Kitagawa等人提出狀態(tài)級(jí)（State-Level）變異的模糊測(cè)試方法AspFuzz[7]。AspFuzz可以自動(dòng)構(gòu)造與正常報(bào)文交互順序相違背的測(cè)試序列，發(fā)現(xiàn)報(bào)文異常輸入順序引起的協(xié)議缺陷，但是其測(cè)試方法存在組合爆炸的問(wèn)題。Zhao等人提出基于回歸協(xié)議狀態(tài)機(jī)的模糊測(cè)試方法RFSM-Fuzzing[8]。該方法通過(guò)狀態(tài)引導(dǎo)對(duì)每個(gè)協(xié)議狀態(tài)進(jìn)行測(cè)試，對(duì)協(xié)議漏洞挖掘有較好的效果，但是測(cè)試過(guò)程存在冗余交互較多、測(cè)試效率低下的問(wèn)題。Pan等人提出一種基于文法驅(qū)動(dòng)的協(xié)議測(cè)試方法[9]。該方法利用高階屬性文法建立數(shù)據(jù)模型，通過(guò)遍歷語(yǔ)義樹(shù)指導(dǎo)測(cè)試用例生成，有效避免了協(xié)議字段的漏測(cè)或者重復(fù)測(cè)試。Ma等人提出基于規(guī)則的狀態(tài)機(jī)（Rule-Based State Machine）與狀態(tài)規(guī)則樹(shù)（Stateful Rule Tree）來(lái)指導(dǎo)模糊測(cè)試序列生成的方法[10]。作者認(rèn)為如果某個(gè)狀態(tài)遷移對(duì)應(yīng)的輸入不會(huì)引發(fā)協(xié)議實(shí)體異常，那么則認(rèn)為該遷移是安全遷移，在測(cè)試期間可以將其移除從而縮小測(cè)試空間，但是這種方法可能出現(xiàn)測(cè)試不完全的問(wèn)題。總體上看，現(xiàn)有的模糊測(cè)試技術(shù)沒(méi)有充分利用協(xié)議狀態(tài)轉(zhuǎn)換關(guān)系開(kāi)展測(cè)試，也沒(méi)有對(duì)輸入報(bào)文和響應(yīng)報(bào)文進(jìn)行必要的相關(guān)性分析，在測(cè)試實(shí)施過(guò)程中較為盲目，測(cè)試效率低下，測(cè)試的覆蓋率偏低。

本文旨在提高測(cè)試效率與測(cè)試覆蓋率，提出一種針對(duì)有狀態(tài)協(xié)議的模糊測(cè)試優(yōu)化方法。

2 問(wèn)題分析

2.1 有狀態(tài)網(wǎng)絡(luò)協(xié)議的模糊測(cè)試

有狀態(tài)網(wǎng)絡(luò)通信協(xié)議通常采用確定有限狀態(tài)機(jī)（Deterministic Finite Automaton，DFA）作為協(xié)議交互的形式化描述模型。確定有限狀態(tài)機(jī)的定義如下所示[11]。

定義1（確定有限狀態(tài)機(jī)）定義為一個(gè)六元組M=(S,I,O,δ,β,T)，其中：

S={s0,s1,…,sn}是有限狀態(tài)集合，s0∈S表示M的初始狀態(tài)，且在任意時(shí)刻，M只能處于某一狀態(tài)si，有限狀態(tài)機(jī)由s0狀態(tài)開(kāi)始接收輸入；

I={i1,i2,…,im}是有限輸入符號(hào)集合；

O={o1,o2,…,om}是有限輸出符號(hào)集合；

δ:S×I→S是狀態(tài)遷移函數(shù)，它是一對(duì)一的映射；

β:S×I→O是狀態(tài)輸出函數(shù)；

T是終結(jié)狀態(tài)集合。

當(dāng)DFA應(yīng)用于網(wǎng)絡(luò)協(xié)議描述時(shí)，I={i1,i2,…,im}表示協(xié)議實(shí)體可接受并正常處理的輸入報(bào)文集合，O={o1,o2,…,om}表示協(xié)議實(shí)體輸出的報(bào)文集合，以M表示協(xié)議狀態(tài)機(jī)。以FTP協(xié)議[12]狀態(tài)機(jī)為例，其輸入輸出報(bào)文類型的抽象符號(hào)如表1所示，M包括7個(gè)狀態(tài)，狀態(tài)集合S={s1,s2,s3,s4,s5,s6,s7}。狀態(tài)機(jī)M如圖1所示，其中s0到s1的遷移表示為i1/o1，它表示協(xié)議實(shí)體處于s0狀態(tài)時(shí)，如果接受USER類型報(bào)文（用i1表示），將輸出331類型報(bào)文（用o1表示），同時(shí)協(xié)議實(shí)體狀態(tài)遷移至s1狀態(tài)。

表1 FTP協(xié)議輸入輸出報(bào)文類型的抽象符號(hào)列表

圖1 FTP協(xié)議狀態(tài)機(jī)

對(duì)于有狀態(tài)協(xié)議模糊測(cè)試，為了提高測(cè)試覆蓋率，通常需要使協(xié)議實(shí)體處于某一指定狀態(tài)，然后輸入與狀態(tài)相對(duì)應(yīng)的測(cè)試用例進(jìn)行測(cè)試。測(cè)試時(shí)需要依賴網(wǎng)絡(luò)協(xié)議交互規(guī)則，根據(jù)協(xié)議狀態(tài)機(jī)構(gòu)造測(cè)試序列。傳統(tǒng)的有狀態(tài)協(xié)議模糊測(cè)試過(guò)程[8，13-14]主要包括三個(gè)步驟：首先，通過(guò)正常的報(bào)文交互，將協(xié)議實(shí)體引導(dǎo)至某個(gè)待測(cè)協(xié)議狀態(tài)，這些正常交互報(bào)文所構(gòu)成的序列稱為前置引導(dǎo)序列。然后，向協(xié)議實(shí)體輸入與被測(cè)狀態(tài)相對(duì)應(yīng)的變異報(bào)文，所涉及的變異報(bào)文被稱為測(cè)試用例。如果檢測(cè)到協(xié)議實(shí)體在處理測(cè)試用例后出現(xiàn)系統(tǒng)崩潰或者停止響應(yīng)等異常情況，則需保存錯(cuò)誤現(xiàn)場(chǎng)并進(jìn)一步分析。最后，如果未檢測(cè)到異常，還需按照特定順序輸入正常報(bào)文將協(xié)議實(shí)體引導(dǎo)至終止?fàn)顟B(tài)，準(zhǔn)備下一輪測(cè)試。這些正常報(bào)文所構(gòu)成的序列被稱為回歸序列。前置引導(dǎo)序列、測(cè)試用例與回歸序列共同組成測(cè)試序列。如對(duì)于圖1所示的FTP協(xié)議狀態(tài)機(jī)，生成測(cè)試序列如表2所示，其中，～i表示測(cè)試用例。

表2 測(cè)試序列示例

2.2 現(xiàn)有方法測(cè)試不足

評(píng)價(jià)模糊測(cè)試方法的優(yōu)劣可以采用測(cè)試效率與測(cè)試覆蓋率兩個(gè)評(píng)價(jià)指標(biāo)?，F(xiàn)有的模糊測(cè)試方法進(jìn)行有狀態(tài)協(xié)議的模糊測(cè)試時(shí)，主要存在以下三方面的不足：

（1）輔助類型報(bào)文交互時(shí)間耗費(fèi)高，測(cè)試效率低下。

網(wǎng)絡(luò)協(xié)議模糊測(cè)試需要將報(bào)文通過(guò)網(wǎng)絡(luò)傳輸?shù)絽f(xié)議實(shí)體程序，報(bào)文在傳輸節(jié)點(diǎn)的等待、處理以及在網(wǎng)絡(luò)中的傳輸都需要時(shí)間，每個(gè)發(fā)送的報(bào)文時(shí)間耗費(fèi)是不可忽略的問(wèn)題[15]。現(xiàn)有的測(cè)試方法通常只側(cè)重于提高測(cè)試用例的有效性，沒(méi)有考慮測(cè)試流程的優(yōu)化，導(dǎo)致測(cè)試序列中只有少部分報(bào)文屬于測(cè)試用例，其他大部分是前置引導(dǎo)序列、回歸序列等輔助報(bào)文，這些輔助報(bào)文會(huì)產(chǎn)生額外的時(shí)間開(kāi)銷，使得單位時(shí)間內(nèi)成功完成測(cè)試的測(cè)試用例數(shù)量很少，引發(fā)協(xié)議實(shí)體異常概率相應(yīng)偏小，測(cè)試效率偏低。

（2）不能保證所有的狀態(tài)遷移都進(jìn)行測(cè)試，測(cè)試覆蓋率不高。

在對(duì)有狀態(tài)協(xié)議進(jìn)行模糊測(cè)試時(shí)，需要考慮被測(cè)協(xié)議實(shí)體程序的代碼覆蓋率，程序代碼覆蓋得越充分，表明測(cè)試越完善[16]。對(duì)于程序源碼未知的協(xié)議實(shí)體進(jìn)行模糊測(cè)試，難以確定代碼覆蓋率，因此通常利用協(xié)議狀態(tài)遷移覆蓋率對(duì)測(cè)試方法進(jìn)行評(píng)估，協(xié)議狀態(tài)遷移覆蓋得越充分，表明測(cè)試越完善。然而，現(xiàn)有的方法難以保證對(duì)所有的狀態(tài)遷移都進(jìn)行測(cè)試，協(xié)議實(shí)體程序代碼測(cè)試覆蓋不夠充分，影響漏洞挖掘效果。

（3）無(wú)法保證輸入報(bào)文與協(xié)議實(shí)體狀態(tài)相對(duì)應(yīng)，產(chǎn)生無(wú)效的報(bào)文交互。

協(xié)議實(shí)體程序在處理報(bào)文時(shí)，需要經(jīng)過(guò)語(yǔ)法解析、語(yǔ)義解析與程序執(zhí)行三個(gè)步驟[17]。測(cè)試用例觸發(fā)協(xié)議實(shí)體程序異?；蛘哒Ｌ幚磔斎雸?bào)文必須首先通過(guò)前兩步，即測(cè)試用例或者正常報(bào)文需要滿足兩個(gè)條件：協(xié)議格式語(yǔ)法約束以及與協(xié)議實(shí)體狀態(tài)相對(duì)應(yīng)。而目前模糊測(cè)試采用的主要是固定模式的測(cè)試方法，即在每次測(cè)試之前預(yù)先生成測(cè)試序列，測(cè)試時(shí)不再對(duì)測(cè)試序列進(jìn)行調(diào)整。這種方法存在盲目性。因?yàn)闇y(cè)試用例被協(xié)議實(shí)體直接拋棄還是接收處理是不確定的，輸入測(cè)試用例后協(xié)議實(shí)體狀態(tài)是無(wú)法預(yù)知的，可能出現(xiàn)后續(xù)報(bào)文（例如回歸序列）與協(xié)議實(shí)體狀態(tài)不對(duì)應(yīng)的情形，這導(dǎo)致報(bào)文交互是無(wú)效的。

針對(duì)上述分析，本文提出一種基于協(xié)議狀態(tài)遷移遍歷的模糊測(cè)試優(yōu)化方法。首先將尋找遍歷狀態(tài)機(jī)所有遷移的路徑問(wèn)題轉(zhuǎn)化為有向圖的中國(guó)郵路問(wèn)題，通過(guò)求解有向圖的中國(guó)郵路問(wèn)題獲取協(xié)議狀態(tài)機(jī)的最優(yōu)遍歷路徑；然后遵循最優(yōu)遍歷路徑的所有遷移依次進(jìn)行測(cè)試；測(cè)試時(shí)根據(jù)響應(yīng)報(bào)文信息推斷協(xié)議實(shí)體狀態(tài)，動(dòng)態(tài)選擇合適的測(cè)試用例或者正常報(bào)文，確保測(cè)試過(guò)程中發(fā)給協(xié)議實(shí)體的報(bào)文與其協(xié)議狀態(tài)相對(duì)應(yīng)，避免無(wú)效的報(bào)文交互，進(jìn)而提高測(cè)試效率。此外，通過(guò)精心構(gòu)造的唯一輸入/輸出序列（Unique Input/Output Sequences，UIO）檢測(cè)協(xié)議實(shí)體異常，及時(shí)發(fā)現(xiàn)協(xié)議狀態(tài)的異常遷移。

3 模糊測(cè)試優(yōu)化策略

3.1 基本概念

在實(shí)施模糊測(cè)試時(shí)，協(xié)議實(shí)體對(duì)每個(gè)測(cè)試用例會(huì)給出相應(yīng)的反饋信息，例如當(dāng)測(cè)試用例不能被正確地接收處理時(shí)，協(xié)議實(shí)體會(huì)通過(guò)響應(yīng)報(bào)文的形式告知。例如，F(xiàn)TP服務(wù)器會(huì)反饋包含“500 Syntax error unknown command”信息的報(bào)文；SMTP服務(wù)器會(huì)反饋包含“503 Bad sequence of commands”信息的報(bào)文。為方便表述，當(dāng)協(xié)議實(shí)體處于狀態(tài)si，輸入報(bào)文im，將協(xié)議實(shí)體處理報(bào)文im后輸出的響應(yīng)報(bào)文on稱為由輸入im與狀態(tài)si確定的期望響應(yīng)報(bào)文。如果得到的輸出不是正常的響應(yīng)報(bào)文on，而是諸如提示輸入報(bào)文語(yǔ)法錯(cuò)誤、錯(cuò)誤命令序列、命令未實(shí)現(xiàn)、動(dòng)作未完成等負(fù)面回答信息的報(bào)文，或者是非狀態(tài)si的響應(yīng)報(bào)文，統(tǒng)一稱之為由輸入im與狀態(tài)si確定的非期望響應(yīng)報(bào)文，表示為-on。需要說(shuō)明的是，在測(cè)試時(shí)，若在設(shè)定時(shí)間閾值內(nèi)未返回任何報(bào)文，也視為得到的是非期望響應(yīng)報(bào)文。

網(wǎng)絡(luò)協(xié)議模糊測(cè)試過(guò)程主要是為了發(fā)現(xiàn)能夠觸發(fā)協(xié)議實(shí)體異常的測(cè)試用例。然而很多測(cè)試用例并不會(huì)觸發(fā)協(xié)議實(shí)體異常，這些測(cè)試用例主要可以分為兩類：一類是由于測(cè)試用例存在畸形數(shù)據(jù)，如果測(cè)試用例無(wú)法通過(guò)語(yǔ)法驗(yàn)證，它們會(huì)被協(xié)議實(shí)體直接拋棄，沒(méi)有進(jìn)行程序執(zhí)行，一般不會(huì)引發(fā)協(xié)議實(shí)體程序異常和狀態(tài)的跳轉(zhuǎn)，此時(shí)協(xié)議實(shí)體會(huì)輸出非期望響應(yīng)報(bào)文。另一類是測(cè)試用例符合協(xié)議格式規(guī)范，能夠正常被程序執(zhí)行處理，可以引發(fā)狀態(tài)跳轉(zhuǎn)并輸出期望響應(yīng)報(bào)文。例如，針對(duì)某些FTP協(xié)議實(shí)體程序進(jìn)行模糊測(cè)試時(shí)，如果對(duì)MKD（創(chuàng)建目錄）命令的參數(shù)變異生成的某些測(cè)試用例，這些測(cè)試用例可能仍屬于正常報(bào)文，程序輸出的是期望響應(yīng)報(bào)文。正是因?yàn)檫@兩類測(cè)試用例的存在，使得輸入測(cè)試用例之前無(wú)法預(yù)知在輸入測(cè)試用例之后協(xié)議實(shí)體狀態(tài)的變化。

3.2 協(xié)議實(shí)體狀態(tài)遷移檢測(cè)

協(xié)議模糊測(cè)試為了檢測(cè)協(xié)議實(shí)體程序能否正確處理畸形數(shù)據(jù)，判斷協(xié)議實(shí)體程序是否有足夠的健壯性，在模糊測(cè)試時(shí)，不僅需要利用調(diào)試器查看內(nèi)存使用情況等方法發(fā)現(xiàn)協(xié)議實(shí)體內(nèi)存訪問(wèn)異常等問(wèn)題，還要考慮協(xié)議狀態(tài)異常遷移問(wèn)題，發(fā)掘協(xié)議實(shí)體程序的安全缺陷。

以協(xié)議實(shí)體處于si狀態(tài)，輸入正常報(bào)文im后協(xié)議實(shí)體遷移至狀態(tài)sj為例。所謂的協(xié)議狀態(tài)異常遷移，在一致性測(cè)試領(lǐng)域[18]，指的是當(dāng)協(xié)議實(shí)體接收到im后，協(xié)議實(shí)體狀態(tài)未遵循協(xié)議狀態(tài)機(jī)遷移至sj狀態(tài)，而是其他非sj狀態(tài)。這種情形說(shuō)明協(xié)議實(shí)體間的交互存在偏差，是一種潛在錯(cuò)誤。在對(duì)協(xié)議進(jìn)行模糊測(cè)試時(shí)，當(dāng)發(fā)送由正常報(bào)文im變異生成的測(cè)試用例后，如果利用查看調(diào)試器等方法未發(fā)現(xiàn)異常，但是協(xié)議實(shí)體狀態(tài)既不處于si狀態(tài)也不處于sj狀態(tài)，說(shuō)明協(xié)議實(shí)體出現(xiàn)狀態(tài)異常遷移。這種由測(cè)試用例引發(fā)協(xié)議狀態(tài)異常遷移意味著協(xié)議實(shí)體程序不夠健壯，通信過(guò)程不可靠，是一種安全缺陷。因此，協(xié)議實(shí)體狀態(tài)異常遷移檢測(cè)非常必要。為了及時(shí)發(fā)現(xiàn)協(xié)議狀態(tài)是否異常遷移，需要在測(cè)試后準(zhǔn)確地對(duì)協(xié)議實(shí)體所處的狀態(tài)進(jìn)行判斷。

對(duì)于黑盒測(cè)試，無(wú)法通過(guò)觀察協(xié)議實(shí)體內(nèi)部動(dòng)作判斷協(xié)議實(shí)體狀態(tài)，可以采用向協(xié)議實(shí)體發(fā)送UIO序列[19]判斷協(xié)議實(shí)體所處的狀態(tài)。所謂UIO序列，指的是當(dāng)協(xié)議實(shí)體處于某一狀態(tài)si時(shí)，向協(xié)議實(shí)體發(fā)送一個(gè)報(bào)文序列，報(bào)文序列表示為P=(ix,iy,…,iz),ix,iy,iz∈I，協(xié)議實(shí)體輸出報(bào)文組成的序列與其他非si狀態(tài)下輸入P而得到的輸出報(bào)文組成的序列都不同，報(bào)文序列P稱為狀態(tài)si的UIO序列，記為UIO(si)。UIO序列可以唯一標(biāo)識(shí)協(xié)議狀態(tài)si。例如在圖1所示的狀態(tài)機(jī)中，當(dāng)協(xié)議實(shí)體處于s2狀態(tài)時(shí)，輸入報(bào)文序列(i3,i4)會(huì)輸出報(bào)文序列(o3,o4)，而在其他任何狀態(tài)下輸入(i3,i4)構(gòu)成的序列都不會(huì)輸出報(bào)文序列(o3,o4)，因此報(bào)文序列(i3,i4)為狀態(tài)s2的UIO序列。

文獻(xiàn)[8]利用UIO序列，通過(guò)觀察協(xié)議實(shí)體的輸出報(bào)文序列檢測(cè)協(xié)議實(shí)體所處的狀態(tài)。具體而言，其方法在輸入測(cè)試用例后，為了判斷協(xié)議實(shí)體是否處于si狀態(tài)，向協(xié)議實(shí)體輸入si狀態(tài)所對(duì)應(yīng)的UIO序列。如果協(xié)議實(shí)體輸出的報(bào)文序列與UIO序列對(duì)應(yīng)的輸出報(bào)文序列相符，則說(shuō)明協(xié)議實(shí)體處于si狀態(tài)，否則說(shuō)明協(xié)議實(shí)體不處于si狀態(tài)。這種方法在每次輸入測(cè)試用例之后，都需要輸入對(duì)應(yīng)的整個(gè)UIO序列，使得測(cè)試時(shí)不得不發(fā)送與接收額外的報(bào)文，影響測(cè)試效率。此外，文獻(xiàn)[8]方法也存在UIO序列與狀態(tài)不對(duì)應(yīng)而導(dǎo)致報(bào)文無(wú)效交互的問(wèn)題。為解決此問(wèn)題，本文提出了利用交叉迭代策略構(gòu)造UIO序列。

3.3 模糊測(cè)試優(yōu)化基本思想

模糊測(cè)試優(yōu)化基本思想如下：首先需要在協(xié)議狀態(tài)機(jī)上尋找遍歷狀態(tài)機(jī)所有狀態(tài)遷移，并且盡可能短的路徑，為方便敘述，該路徑以O(shè)PT表示。測(cè)試過(guò)程從OPT對(duì)應(yīng)的第一個(gè)狀態(tài)開(kāi)始實(shí)施，以協(xié)議狀態(tài)si為例，狀態(tài)si在OPT中鄰接的下一個(gè)協(xié)議狀態(tài)為sj，狀態(tài)si與狀態(tài)sj之間的遷移對(duì)應(yīng)的正常輸入報(bào)文為im。測(cè)試時(shí)向協(xié)議實(shí)體輸入由im變異生成的測(cè)試用例，檢測(cè)協(xié)議實(shí)體是否出現(xiàn)了異常，如果出現(xiàn)了異常，需要保存輸入數(shù)據(jù)待進(jìn)一步分析調(diào)試。如果沒(méi)有出現(xiàn)異常，需要推斷協(xié)議實(shí)體的狀態(tài)，以決定如何實(shí)施下一步的測(cè)試。協(xié)議實(shí)體的狀態(tài)推斷主要依據(jù)協(xié)議實(shí)體的響應(yīng)報(bào)文。對(duì)于輸入的測(cè)試用例，如果協(xié)議實(shí)體的響應(yīng)報(bào)文是協(xié)議狀態(tài)si和輸入im所對(duì)應(yīng)的期望響應(yīng)報(bào)文，那么表明測(cè)試用例被協(xié)議實(shí)體正常接收處理，協(xié)議實(shí)體狀態(tài)已經(jīng)處于sj狀態(tài)，可以輸入下一個(gè)狀態(tài)遷移所對(duì)應(yīng)的測(cè)試用例進(jìn)行下一步測(cè)試。如果協(xié)議實(shí)體的響應(yīng)報(bào)文屬于協(xié)議狀態(tài)si和輸入im所對(duì)應(yīng)的非期望響應(yīng)報(bào)文，那么協(xié)議實(shí)體仍可能處于si狀態(tài)，也可能由于測(cè)試用例的作用，跳轉(zhuǎn)至狀態(tài)si之外的狀態(tài)。在這種情況下，繼續(xù)需要輸入正常輸入報(bào)文im，觀察協(xié)議實(shí)體的響應(yīng)。如果響應(yīng)報(bào)文是狀態(tài)si和輸入im所對(duì)應(yīng)的非期望響應(yīng)報(bào)文，那么在輸入報(bào)文im之前，協(xié)議實(shí)體可能出現(xiàn)異常，需要保存輸入數(shù)據(jù)進(jìn)一步分析。如果響應(yīng)報(bào)文是狀態(tài)si和輸入im所對(duì)應(yīng)的期望響應(yīng)報(bào)文，那么此時(shí)協(xié)議實(shí)體已經(jīng)被引導(dǎo)至sj狀態(tài)，繼續(xù)輸入sj狀態(tài)與下一狀態(tài)的遷移對(duì)應(yīng)的測(cè)試用例進(jìn)行測(cè)試。為了檢測(cè)在輸入im變異生成測(cè)試用例之后協(xié)議實(shí)體狀態(tài)是否發(fā)生異常遷移，需要在輸入測(cè)試用例之后輸入狀態(tài)si對(duì)應(yīng)的UIO序列，那么在測(cè)試時(shí)輸入由im變異生成的測(cè)試用例之后，同時(shí)保證后續(xù)輸入的其他報(bào)文可以構(gòu)成狀態(tài)si對(duì)應(yīng)的UIO序列。如此依次推進(jìn)，直至OPT的終止?fàn)顟B(tài)完成一輪測(cè)試。

在模糊測(cè)試優(yōu)化實(shí)施過(guò)程中主要有兩個(gè)問(wèn)題：

（1）如何在協(xié)議狀態(tài)機(jī)上尋找遍歷協(xié)議狀態(tài)機(jī)所有遷移，并且盡可能短的路徑。

（2）在輸入由im變異生成的測(cè)試用例后，如何保證后續(xù)輸入的報(bào)文可以構(gòu)成狀態(tài)si對(duì)應(yīng)的UIO序列。

下文將依次進(jìn)行論述。

3.4 最優(yōu)遍歷路徑獲取

該節(jié)將解決3.3節(jié)提出的問(wèn)題（1）。需要說(shuō)明的是，之所以要在協(xié)議狀態(tài)機(jī)上尋找遍歷協(xié)議狀態(tài)機(jī)所有遷移，并且盡可能短的路徑，是因?yàn)槿绻罁?jù)OPT上狀態(tài)遷移的順序依次對(duì)每個(gè)狀態(tài)遷移進(jìn)行測(cè)試，可以保證所有狀態(tài)遷移都能夠被測(cè)試，盡可能短的路徑可以減小異常定位分析的工作量。

有向圖的中國(guó)郵路問(wèn)題（Digraph Chinese Postman Problem，DCPP）是尋找經(jīng)歷有向圖中每條有向邊至少一次并且長(zhǎng)度最短的遍歷路線，這種遍歷路線也被稱為最優(yōu)郵遞路線[20]?？蓪f(xié)議狀態(tài)機(jī)映射為有向圖，然后再基于DCPP，尋找一條經(jīng)歷有向圖中所有有向邊并且長(zhǎng)度最小的遍歷路線，根據(jù)獲取的有向圖遍歷路線，找到遍歷協(xié)議狀態(tài)機(jī)所有遷移的最短路徑。依據(jù)該遍歷路徑上狀態(tài)遷移的先后順序進(jìn)行測(cè)試，即可以對(duì)所有狀態(tài)遷移進(jìn)行測(cè)試，有效避免漏測(cè)問(wèn)題。下面先給出有向圖的定義。

定義2（有向圖）以二元組表示一個(gè)有向圖，記為DG=(V,E)，其中DG是有向圖的名稱，V={v0,v1,…,vn}是圖的頂點(diǎn)集合，E={e0,e1,…,em}是圖的有向邊集合。

協(xié)議狀態(tài)機(jī)M映射為有向圖DG的過(guò)程如下：將狀態(tài)集合S映射成有向圖的頂點(diǎn)集合V，使得任意狀態(tài)均有唯一頂點(diǎn)與其對(duì)應(yīng)。將狀態(tài)的遷移映射為有向邊，使得任意狀態(tài)si（對(duì)應(yīng)頂點(diǎn)為vi）至sj（對(duì)應(yīng)頂點(diǎn)為vj）的狀態(tài)遷移（輸入為ik∈I，輸出為ol∈O）均有唯一有向邊（以vi為頂點(diǎn)，vj為終點(diǎn)）與其對(duì)應(yīng)，并且該有向邊以輸入ik∈I和輸出ol∈O進(jìn)行標(biāo)記，進(jìn)而得到狀態(tài)機(jī)M唯一對(duì)應(yīng)的有向圖DG。

DCPP求解算法的適用條件是有向圖為強(qiáng)連通圖。強(qiáng)連通圖是指有向圖的每個(gè)頂點(diǎn)都可以到達(dá)其他任意頂點(diǎn)，然而協(xié)議狀態(tài)機(jī)映射而成的有向圖可能不是強(qiáng)連通圖。例如，圖1中FTP協(xié)議狀態(tài)機(jī)映射而成的有向圖中狀態(tài)s2所對(duì)應(yīng)的頂點(diǎn)v2無(wú)法到達(dá)s1對(duì)應(yīng)的頂點(diǎn)v1，該有向圖不滿足DCPP求解條件。為解決這一問(wèn)題，采用了如下策略：在模糊測(cè)試過(guò)程中，一次會(huì)話結(jié)束后需要啟動(dòng)新的會(huì)話，因此將狀態(tài)機(jī)M的終結(jié)狀態(tài)返回初始狀態(tài)作為一次狀態(tài)遷移，將其稱為虛擬遷移，將虛擬遷移添加到狀態(tài)機(jī)中，添加虛擬遷移后的狀態(tài)機(jī)用V-M表示，如圖2所示。在V-M中，每個(gè)狀態(tài)可以到達(dá)其他任意狀態(tài)，V-M所對(duì)應(yīng)的有向圖為強(qiáng)聯(lián)通圖，其對(duì)應(yīng)的DCPP可以求解。

圖2 添加虛擬遷移后的狀態(tài)機(jī)V-M

協(xié)議狀態(tài)機(jī)映射為有向圖DG后，將遍歷所有狀態(tài)遷移的最短路徑的問(wèn)題轉(zhuǎn)化為DCCP問(wèn)題進(jìn)行求解。DCCP問(wèn)題存在多項(xiàng)式時(shí)間解法。DCCP的經(jīng)典求解算法是在有向圖DG上增加有向邊，使得每個(gè)頂點(diǎn)的入度和出度都相等，得到一個(gè)有向歐拉圖DG'，歐拉圖DG'的歐拉回路就是遍歷DG中所有遷移的最短路徑。限于篇幅原因，算法細(xì)節(jié)不再贅述，詳見(jiàn)文獻(xiàn)[20]。在對(duì)V-M遍歷所有狀態(tài)遷移的最短路徑進(jìn)行求解的過(guò)程中，以狀態(tài)s0對(duì)應(yīng)的v0結(jié)點(diǎn)出發(fā)，優(yōu)先遍歷每個(gè)頂點(diǎn)的自循環(huán)邊。根據(jù)DCCP求解得到遍歷有向圖DG中所有有向邊的最短路線，進(jìn)而尋找到遍歷協(xié)議狀態(tài)機(jī)所有狀態(tài)遷移的最短路徑，稱之為最優(yōu)遍歷路徑（Optimal Traversal Path，OTP）。在模糊測(cè)試時(shí)，以遍歷協(xié)議狀態(tài)機(jī)對(duì)應(yīng)的OTP為基礎(chǔ)進(jìn)行模糊測(cè)試，可保證對(duì)協(xié)議狀態(tài)機(jī)中的所有狀態(tài)遷移進(jìn)行測(cè)試。

圖3 最優(yōu)遍歷路徑OTP

由圖2對(duì)應(yīng)的V-M狀態(tài)機(jī)求得最優(yōu)遍歷路徑OTP，如圖3所示。沿用協(xié)議狀態(tài)機(jī)的概念，OTP中包含協(xié)議狀態(tài)與狀態(tài)遷移，其中OTP的第一個(gè)協(xié)議狀態(tài)s0稱為OTP的初始狀態(tài)，最后一個(gè)協(xié)議狀態(tài)s7稱為OTP的終止?fàn)顟B(tài)。從OTP的初始狀態(tài)開(kāi)始遍歷至OTP的終止?fàn)顟B(tài)，期間經(jīng)歷了協(xié)議狀態(tài)機(jī)M的所有狀態(tài)遷移（包括虛擬遷移）。

3.5 利用交叉迭代策略構(gòu)造UIO序列

該節(jié)通過(guò)設(shè)計(jì)交叉迭代策略解決3.3節(jié)問(wèn)題（2）。交叉迭代策略基于這樣一種思想：由3.3節(jié)可知，當(dāng)協(xié)議實(shí)體處于狀態(tài)si，輸入相應(yīng)的測(cè)試用例之后，如果沒(méi)有發(fā)現(xiàn)協(xié)議實(shí)體異常，將遵循OPT繼續(xù)輸入正常報(bào)文與測(cè)試用例執(zhí)行測(cè)試。對(duì)于這些后續(xù)發(fā)送的報(bào)文，其中某些報(bào)文可組成報(bào)文序列P'，如果報(bào)文序列P'是狀態(tài)si的UIO序列，那么可利用P'檢測(cè)狀態(tài)si是否發(fā)生異常遷移，而無(wú)需再構(gòu)造獨(dú)立的UIO序列。

接下來(lái)介紹上述策略實(shí)施過(guò)程。以O(shè)TP的初始狀態(tài)為起點(diǎn)，以O(shè)TP的終止?fàn)顟B(tài)作為終點(diǎn)，OTP上相鄰的兩個(gè)狀態(tài)，以狀態(tài)si與sj為例，對(duì)狀態(tài)之間的遷移進(jìn)行如下判斷：查看OPT中狀態(tài)si與下一個(gè)si狀態(tài)或者M(jìn)的終止?fàn)顟B(tài)之間的遷移對(duì)應(yīng)的報(bào)文序列，該報(bào)文序列記作P。在實(shí)際測(cè)試過(guò)程中，在測(cè)試狀態(tài)si與sj之間遷移之后，如果未發(fā)現(xiàn)異常并繼續(xù)測(cè)試，那么后續(xù)輸入的報(bào)文序列P'是由報(bào)文序列P與測(cè)試用例構(gòu)成。如果報(bào)文序列P是狀態(tài)si對(duì)應(yīng)的UIO序列，由定理可知，報(bào)文序列si也是UIO序列，此時(shí)可以保證在測(cè)試狀態(tài)si與sj之間的遷移后，接下來(lái)會(huì)輸入相應(yīng)的UIO序列用于檢測(cè)協(xié)議實(shí)體是否發(fā)生異常遷移。為方便后續(xù)操作，此時(shí)需要對(duì)狀態(tài)si與sj之間遷移進(jìn)行標(biāo)記。如果報(bào)文序列P不是狀態(tài)si對(duì)應(yīng)的UIO序列，那么P'也不是UIO序列，狀態(tài)si與sj之間遷移測(cè)試后不會(huì)有UIO序列進(jìn)行檢測(cè)，那么不對(duì)狀態(tài)si與sj之間遷移進(jìn)行標(biāo)記。之所以查看OPT中狀態(tài)si與下一個(gè)si狀態(tài)或者M(jìn)的終止?fàn)顟B(tài)之間的遷移對(duì)應(yīng)的報(bào)文序列，是因?yàn)闋顟B(tài)si在被測(cè)后，在協(xié)議實(shí)體處于下一個(gè)si狀態(tài)或者會(huì)話結(jié)束前就要檢測(cè)是否出現(xiàn)異常遷移。

定理 如果P=(ix,iy,…,iz)是狀態(tài)si的UIO序列，那 么 P'=((～ix|-,ix)|～ix,(～iy|-,iy)|～iy,…,(～iz|-,iz)|～iz)也是狀態(tài)si的UIO序列，其中～ix|-表示要么輸入～ix要么無(wú)輸入，(～ix|-,ix)表示由～ix|-與ix組成的輸入序列。

證明 當(dāng)協(xié)議實(shí)體處于狀態(tài)si時(shí)，輸入狀態(tài)si的UIO序列P，由UIO定義可知，協(xié)議實(shí)體必會(huì)有唯一輸出(ox,oy,…,oz)。而同樣協(xié)議實(shí)體程序處于狀態(tài)si時(shí)，輸入P'，那么協(xié)議實(shí)體必然輸出((o,oy)|oy,…,(-,oz)|oz)，其中ox)|ox表示為o-與ox組成的輸出序列。又因?yàn)檩敵?ox,oy,…,oz)是唯一確定的，并且非期望響應(yīng)報(bào)文不會(huì)與其他任何期望響應(yīng)報(bào)文相同，所以-,oz)|oz)也是協(xié)議實(shí)體唯一確定的輸出，則P'也是狀態(tài)si的UIO序列。

上述策略實(shí)施過(guò)程也就是判斷OPT上任意兩個(gè)相鄰的狀態(tài)之間的遷移是否可以被標(biāo)記，對(duì)整個(gè)OPT而言，詳細(xì)的標(biāo)記步驟如下：

步驟1對(duì)于OTP中的某一個(gè)狀態(tài)si，以sj表示其鄰接狀態(tài)。首先判斷si是否為原始狀態(tài)機(jī)M中的終止?fàn)顟B(tài)，如果是終止?fàn)顟B(tài)，那么狀態(tài)si與狀態(tài)sj之間遷移是虛擬遷移，虛擬遷移不被標(biāo)記，跳至執(zhí)行步驟3；否則繼續(xù)執(zhí)行步驟2。

步驟2從狀態(tài)si出發(fā)順序遍歷，查看OTP中狀態(tài)si與其之后的第一個(gè)si狀態(tài)或者第一個(gè)原始狀態(tài)機(jī)M終止?fàn)顟B(tài)之間的最短遷移路徑。如果這段遷移路徑對(duì)應(yīng)的輸入序列是si狀態(tài)的UIO序列，那么對(duì)狀態(tài)si至鄰接狀態(tài)sj之間的遷移進(jìn)行標(biāo)記，然后執(zhí)行步驟3；否則，該步驟不進(jìn)行任何標(biāo)記，直接執(zhí)行步驟3。

步驟3判斷狀態(tài)sj是否為OTP的終止?fàn)顟B(tài)，如果狀態(tài)sj是OTP的終止?fàn)顟B(tài)，那么完成OTP的標(biāo)記；否則，跳至執(zhí)行步驟1，對(duì)狀態(tài)sj與其下一個(gè)鄰接狀態(tài)進(jìn)行遞歸操作。

例如對(duì)圖4最優(yōu)遍歷路徑OTP進(jìn)行標(biāo)記，第一個(gè)s4狀態(tài)至其之后第一個(gè)s4狀態(tài)（即OTP的第二個(gè)s4狀態(tài)）之間遷移需要輸入i5、i7、i11、i3與i4，依次經(jīng)過(guò)狀態(tài)s5、s6、s2與s3，并且輸出為o5、o5、o4、o3、o4，其中報(bào)文序列(i5,i7,i11,i3,i4)是狀態(tài)s4的UIO序列，因此對(duì)第一個(gè)s4至與其下一個(gè)鄰接狀態(tài)s5之間的遷移進(jìn)行標(biāo)記，然后再以同樣的方法繼續(xù)判斷狀態(tài)s5以及其下一個(gè)鄰接狀態(tài)之間遷移是否應(yīng)被標(biāo)記，直至對(duì)所有狀態(tài)都進(jìn)行判斷并標(biāo)記相應(yīng)遷移，標(biāo)記后的狀態(tài)遷移記作“|”，如圖4所示。

圖4 標(biāo)記后的最優(yōu)遍歷路徑

4 模糊測(cè)試過(guò)程

基于前期分析與準(zhǔn)備工作，本章將詳細(xì)闡述動(dòng)態(tài)模糊測(cè)試流程。遵循最優(yōu)遍歷路徑OTP，以si和其鄰接的下一個(gè)狀態(tài)sj之間的遷移為例，對(duì)應(yīng)遷移的合法輸入報(bào)文是im,期望響應(yīng)報(bào)文是om，非期望響應(yīng)報(bào)文記作報(bào)文im對(duì)應(yīng)的測(cè)試用例的集合記作Tim={～im1,～im2,…,～imn}，測(cè)試時(shí)，需要使用一個(gè)隊(duì)列Q用以保存包含輸入的報(bào)文信息。測(cè)試流程圖如圖5所示。

圖5 模糊測(cè)試流程

動(dòng)態(tài)模糊測(cè)試流程主要包括以下6個(gè)步驟：

步驟1判斷狀態(tài)si至狀態(tài)sj之間遷移是否被標(biāo)記過(guò)。如果該遷移被標(biāo)記，那么滿足后續(xù)輸入報(bào)文可構(gòu)成UIO序列的條件，執(zhí)行步驟2進(jìn)行測(cè)試；否則，執(zhí)行步驟5。

步驟2輸入測(cè)試用例～imj∈Tim，同時(shí)將測(cè)試用例信息記錄在隊(duì)列Q中，監(jiān)測(cè)協(xié)議實(shí)體在處理測(cè)試用例后是否發(fā)生內(nèi)存訪問(wèn)錯(cuò)誤、程序崩潰等異常。如果出現(xiàn)異常，依據(jù)記錄的測(cè)試用例信息進(jìn)一步分析調(diào)試；否則，繼續(xù)執(zhí)行步驟3。

步驟3判斷協(xié)議實(shí)體在處理測(cè)試用例后的輸出是否為om。如果輸出是om，說(shuō)明～imj可以被協(xié)議實(shí)體接受并正常處理，此時(shí)協(xié)議實(shí)體的狀態(tài)視為已遷移至sj狀態(tài)，跳轉(zhuǎn)執(zhí)行步驟5；否則，繼續(xù)執(zhí)行步驟4。

步驟4繼續(xù)輸入im，同時(shí)記錄im信息到隊(duì)列中，判斷此時(shí)輸出是否為om。如果輸出是om，說(shuō)明此時(shí)由于im的作用，協(xié)議實(shí)體的狀態(tài)已經(jīng)是sj，則執(zhí)行步驟5；否則，對(duì)于正常的輸入im沒(méi)有得到期望響應(yīng)報(bào)文om，說(shuō)明協(xié)議實(shí)體可能出現(xiàn)異常，可能是停止響應(yīng)或者狀態(tài)異常遷移，保存隊(duì)列內(nèi)輸入報(bào)文信息，進(jìn)一步分析調(diào)試。

步驟5首先判斷狀態(tài)sj是否為OTP的終止?fàn)顟B(tài)，如果是OTP的終止?fàn)顟B(tài)，那么執(zhí)行步驟6，否則，判斷狀態(tài)sj是否為狀態(tài)機(jī)M的終止?fàn)顟B(tài)；如果狀態(tài)sj是終止?fàn)顟B(tài)，此時(shí)清空隊(duì)列內(nèi)所有已記錄的報(bào)文信息，因?yàn)樾枰匦陆⑿碌臅?huì)話，舊會(huì)話階段輸入的報(bào)文對(duì)新會(huì)話的測(cè)試沒(méi)有影響，然后返回步驟1重復(fù)該方法對(duì)狀態(tài)sj和其下一個(gè)狀態(tài)之間的遷移進(jìn)行操作；否則，直接返回步驟1對(duì)狀態(tài)sj和其下一個(gè)狀態(tài)之間的遷移進(jìn)行操作。

步驟6由OTP遷移標(biāo)記過(guò)程可知，可能某兩個(gè)狀態(tài)之間的遷移沒(méi)有被標(biāo)記，導(dǎo)致存在遷移未能被測(cè)試。此時(shí)，為了解決這種漏測(cè)問(wèn)題，還需對(duì)未被測(cè)試的遷移進(jìn)行補(bǔ)充測(cè)試，參考2.1節(jié)介紹的方法，輸入前置引導(dǎo)序列將協(xié)議實(shí)體置于相應(yīng)狀態(tài)，再輸入未測(cè)試過(guò)的狀態(tài)遷移相應(yīng)測(cè)試用例，檢測(cè)協(xié)議實(shí)體是否異常。如果所有狀態(tài)遷移都被測(cè)試，那么以O(shè)TP的始發(fā)狀態(tài)作為狀態(tài)si，返回至步驟1開(kāi)始新一輪測(cè)試。

以圖1的FTP協(xié)議狀態(tài)機(jī)測(cè)試為例，對(duì)每個(gè)狀態(tài)遷移都進(jìn)行一次測(cè)試，需要向協(xié)議實(shí)體輸入的報(bào)文依次是～i1、i1|-、～i2、i2|-、～i3、i3|-、～i4、i4|-、～i5、i5|-、～i7、i7|-、～i11、i11|-、～i3、i3|-、～i4、i4|-、～i6、i6|-、～i10、i10|-、～i9、i9|-、～i3、i3|-、～i4、i4|-、～i6、i6|-、～i8、i8|-、～i3、i3|-、～i4、i4|-、～i5、i5|-、～i7、i7|-、～i12、i12|-。其中“|”表示選擇關(guān)系，“-”表示不輸入報(bào)文，如i1|-表示輸入i1或者不輸入報(bào)文。輸入該測(cè)試序列至多需要發(fā)送報(bào)文42次，最少需要交互21次，其中有21個(gè)測(cè)試用例進(jìn)行測(cè)試，完成一次所有狀態(tài)遷移的測(cè)試。

如果在進(jìn)行測(cè)試時(shí)，協(xié)議實(shí)體出現(xiàn)異常，如協(xié)議實(shí)體出現(xiàn)內(nèi)存訪問(wèn)錯(cuò)誤，或者達(dá)到一定條件，如測(cè)試用例數(shù)目或者時(shí)間達(dá)到上限，則停止測(cè)試。協(xié)議實(shí)體異常可能是最后輸入的測(cè)試用例所觸發(fā)，也可能是前期測(cè)試用例引發(fā)協(xié)議實(shí)體狀態(tài)異常遷移在此時(shí)才被檢測(cè)出來(lái)。例如，當(dāng)協(xié)議實(shí)體處于OPT上第一個(gè)s3狀態(tài)時(shí)，發(fā)送i4后并未返回期望響應(yīng)報(bào)文o4，可能是內(nèi)存錯(cuò)誤等問(wèn)題導(dǎo)致協(xié)議實(shí)體停止服務(wù)，也可能是協(xié)議實(shí)體此時(shí)出現(xiàn)狀態(tài)異常遷移，也可能是s3狀態(tài)（對(duì)應(yīng)UIO序列是i4）測(cè)試后出現(xiàn)狀態(tài)異常遷移，還可能是OPT上第一個(gè)s2狀態(tài)（對(duì)應(yīng)UIO序列是(i3,i4)）測(cè)試后出現(xiàn)狀態(tài)異常遷移。因此，在發(fā)現(xiàn)協(xié)議實(shí)體出現(xiàn)異常時(shí)，需要對(duì)保存前期輸入報(bào)文信息進(jìn)行分析，驗(yàn)證捕獲協(xié)議實(shí)體異常是否為誤報(bào)，并進(jìn)一步分析異常原因，判斷是否存在可利用的漏洞。

總體而言，本章動(dòng)態(tài)地調(diào)整后續(xù)輸入的報(bào)文類型，避免無(wú)效的報(bào)文交互，利用交叉迭代思想減少報(bào)文交互次數(shù)，進(jìn)而提高測(cè)試效率。在每次輸入測(cè)試用例或者正常報(bào)文之后，對(duì)協(xié)議實(shí)體的響應(yīng)報(bào)文進(jìn)行分析，依據(jù)分析結(jié)果調(diào)整后續(xù)的輸入是測(cè)試用例還是正常報(bào)文。如果后續(xù)輸入是測(cè)試用例，那么又可以測(cè)試下一個(gè)遷移；如果后續(xù)輸入是正常報(bào)文，那么充當(dāng)前置引導(dǎo)序列的一部分，將協(xié)議實(shí)體引導(dǎo)至下一個(gè)狀態(tài)繼續(xù)測(cè)試，同時(shí)充當(dāng)某些狀態(tài)的UIO序列的一部分，達(dá)到檢測(cè)協(xié)議實(shí)體是否發(fā)生狀態(tài)異常遷移的目的。例如，基于FTP協(xié)議狀態(tài)機(jī)進(jìn)行測(cè)試時(shí)，正常報(bào)文i4是狀態(tài)s2和s3的UIO序列一部分，可用于檢測(cè)協(xié)議實(shí)體是否發(fā)生狀態(tài)異常遷移，i4又可作為狀態(tài)s4、s5或者s6的前置引導(dǎo)序列的一部分，i4的一次輸入實(shí)際上發(fā)揮多個(gè)作用，減少了報(bào)文交互次數(shù)。

5 實(shí)驗(yàn)與結(jié)果分析

5.1 測(cè)試準(zhǔn)備

Peach3.0是目前較為成熟的模糊測(cè)試框架，RFSMFuzzing是目前對(duì)有狀態(tài)協(xié)議進(jìn)行模糊測(cè)試的完整測(cè)試方案。本文方法PSTT-Fuzzing將與Peach3.0和RFSMFuzzing進(jìn)行對(duì)比，三種方法采用的測(cè)試用例均以Peach 3.0變異策略生成，測(cè)試用例有效性相同。選取兩種代表性的有狀態(tài)協(xié)議作為測(cè)試對(duì)象——FTP與SMTP協(xié)議，其對(duì)應(yīng)的協(xié)議實(shí)體程序信息如表3所示。

表3 測(cè)試對(duì)象的版本信息

5.2 測(cè)試結(jié)果分析

首先對(duì)實(shí)際環(huán)境下的測(cè)試效率進(jìn)行評(píng)估，再以挖掘漏洞效率與挖掘能力統(tǒng)計(jì)結(jié)果進(jìn)行對(duì)比分析。

5.2.1 測(cè)試效率評(píng)估

在測(cè)試過(guò)程中，即便是發(fā)送測(cè)試用例總數(shù)與發(fā)送報(bào)文的總數(shù)的比值很高，測(cè)試效率也未必高。因?yàn)槿绻麥y(cè)試用例未能與協(xié)議狀態(tài)相對(duì)應(yīng)，測(cè)試用例難以觸發(fā)協(xié)議實(shí)體異常，僅僅考慮發(fā)送測(cè)試用例總數(shù)與發(fā)送報(bào)文總數(shù)的比值還不能準(zhǔn)確評(píng)估測(cè)試效率。為了準(zhǔn)確評(píng)估測(cè)試效率，本文引入有效測(cè)試報(bào)文發(fā)送效率概念。

假設(shè)某個(gè)測(cè)試用例～in對(duì)應(yīng)于狀態(tài)si，當(dāng)協(xié)議實(shí)體處于被測(cè)狀態(tài)si時(shí)，輸入～in進(jìn)行測(cè)試，那么稱該測(cè)試用例～in為有效完成測(cè)試的測(cè)試用例。有效測(cè)試報(bào)文發(fā)送效率是指向被測(cè)協(xié)議實(shí)體輸入有效完成測(cè)試的測(cè)試用例個(gè)數(shù)與發(fā)送報(bào)文的總數(shù)的比值，以β表示有效測(cè)試報(bào)文發(fā)送效率，∑Ac表示有效完成測(cè)試的測(cè)試用例總數(shù)，∑mj表示發(fā)送報(bào)文的總數(shù)，β的數(shù)學(xué)表達(dá)式為β=∑Ac/∑mj。β值越大，說(shuō)明發(fā)送輔助類型的報(bào)文越少，單位時(shí)間輸入與狀態(tài)相對(duì)應(yīng)的測(cè)試用例數(shù)量比值較高，測(cè)試效率越高，采用β評(píng)估測(cè)試效率更具有合理性。

以Quick’n Easy FTP Server作為FTP協(xié)議的被測(cè)協(xié)議實(shí)體，以Quick’n Easy Mail Server作為SMTP協(xié)議的被測(cè)協(xié)議實(shí)體。PSTT-Fuzzing、Peach3.0、與RFSMFuzzing有效完成測(cè)試的測(cè)試用例總數(shù)（即∑Ac）與時(shí)間的關(guān)系如圖6所示。

由圖可知，在任意時(shí)刻PSTT-Fuzzing方法對(duì)應(yīng)的有效完成測(cè)試用例數(shù)均要高于Peach3.0與RFSM-Fuzzing。Peach3.0盡管在測(cè)試時(shí)報(bào)文交互效率較高，單位時(shí)間輸出的測(cè)試用例數(shù)量較多，但是Peach輸入報(bào)文時(shí)盲目性較大，很多測(cè)試用例發(fā)送至協(xié)議實(shí)體時(shí)，協(xié)議實(shí)體狀態(tài)實(shí)際上并未與測(cè)試用例相對(duì)應(yīng)，∑Ac值相對(duì)較低。RFSM-Fuzzing盡管采用完善的引導(dǎo)機(jī)制，使得多數(shù)測(cè)試用例可以在協(xié)議實(shí)體處于對(duì)應(yīng)狀態(tài)進(jìn)行測(cè)試，但是測(cè)試期間前置引導(dǎo)序列等輔助報(bào)文的比重大，時(shí)間耗費(fèi)大，在單位時(shí)間內(nèi)的測(cè)試用例數(shù)目較少，∑Ac值也相對(duì)較低。PSTT-Fuzzing在分析響應(yīng)報(bào)文時(shí)存在時(shí)間耗費(fèi)，但是該方法使用更少的交互引導(dǎo)報(bào)文，使得測(cè)試用例可在對(duì)應(yīng)狀態(tài)有效地實(shí)施測(cè)試，單位時(shí)間內(nèi)有效完成測(cè)試用例比重更大，∑Ac值更高。測(cè)試用例未能真正有效地實(shí)現(xiàn)測(cè)試。

圖6 有效完成測(cè)試用例數(shù)與測(cè)試時(shí)間的關(guān)系

需要說(shuō)明的是，實(shí)際網(wǎng)絡(luò)環(huán)境、服務(wù)器性能會(huì)影響報(bào)文傳輸?shù)男?，因此有效完成測(cè)試用例數(shù)∑Ac值和時(shí)間的關(guān)系具有一定的隨機(jī)性。為了更客觀地評(píng)估測(cè)試效率，表4列出測(cè)試5小時(shí)有效測(cè)試報(bào)文發(fā)送效率β的統(tǒng)計(jì)結(jié)果。

表4 5小時(shí)報(bào)文交互有效率統(tǒng)計(jì) %

由表4可知，PSTT-Fuzzing對(duì)應(yīng)的β高于Peach3.0與RFSM-Fuzzing對(duì)應(yīng)的β。當(dāng)向協(xié)議實(shí)體發(fā)送報(bào)文的總數(shù)∑mj相同時(shí)，相同的網(wǎng)絡(luò)環(huán)境與服務(wù)器性能，發(fā)送時(shí)間耗費(fèi)大致相同。由β的數(shù)學(xué)表達(dá)式可知，PSTTFuzzing對(duì)應(yīng)有效完成測(cè)試的測(cè)試用例總數(shù)∑Ac更高。

5.2.2 漏洞挖掘效果

漏洞挖掘效率是指挖掘相同的漏洞所需時(shí)間耗費(fèi)，時(shí)間耗費(fèi)越少挖掘效率越高；漏洞挖掘能力是指在模糊測(cè)試正常執(zhí)行條件下挖掘漏洞的數(shù)目。測(cè)試時(shí)間為5小時(shí)，漏洞挖掘效果統(tǒng)計(jì)結(jié)果如表5所示。

從表5可知，PSTT-Fuzzing漏洞挖掘能力和挖掘效率好于Peach與RFSM-Fuzzing。PSTT-Fuzzing挖掘出6個(gè)漏洞，Peach3.0挖掘出5個(gè)漏洞，RFSM-Fuzzing挖掘出4個(gè)漏洞，挖掘每個(gè)漏洞對(duì)應(yīng)的時(shí)間耗費(fèi)，PSTT-Fuzzing均要低于其他兩種對(duì)比方法。

在挖掘能力方面，PSTT-Fuzzing效果好于Peach3.0與RFSM-Fuzzing。對(duì)于Quick Easy FTP Server V4.0.0服務(wù)器第二個(gè)未知漏洞，當(dāng)變異的PASV報(bào)文發(fā)送至服務(wù)器時(shí)，服務(wù)器反饋命令錯(cuò)誤的提示，然后輸入正常PASV報(bào)文，在輸入變異的LIST報(bào)文，再輸入正常LIST報(bào)文時(shí)，服務(wù)器未返回任何響應(yīng)報(bào)文，經(jīng)檢測(cè)此時(shí)服務(wù)器已經(jīng)停止服務(wù)；Peach與RFSM-Fuzzing兩種方法并未能挖掘該漏洞。對(duì)于Quick’n Easy Mail Server已知漏洞1，服務(wù)器短時(shí)間內(nèi)接收到一定數(shù)量包含長(zhǎng)字符串參數(shù)的多個(gè)HELO命令的報(bào)文時(shí)，程序本身沒(méi)有錯(cuò)誤提示，調(diào)試工具也未能捕獲到運(yùn)行異常，但是服務(wù)器未返回期望響應(yīng)報(bào)文，經(jīng)檢測(cè)發(fā)現(xiàn)服務(wù)器已近停止服務(wù)，Peach與RFSM-Fuzzing測(cè)試方法使用調(diào)試器檢測(cè)異常未能挖掘到該漏洞。在挖掘效率方面，從實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果對(duì)比可知，PSTT-Fuzzing的測(cè)試效率高于Peach與RFSMFuzzing方法，驗(yàn)證了5.2.1小節(jié)測(cè)試性能評(píng)估的正確性。對(duì)測(cè)試性能與挖掘漏洞效果進(jìn)行比較，相比于Peach與RFSM-Fuzzing測(cè)試方法，本文測(cè)試方法PSTT-Fuzzing具有明顯的優(yōu)勢(shì)，本文模糊測(cè)試優(yōu)化方法達(dá)到了預(yù)期的測(cè)試效果。

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

本文針對(duì)現(xiàn)有的有狀態(tài)協(xié)議的模糊測(cè)試技術(shù)測(cè)試時(shí)存在輔助類型報(bào)文交互時(shí)間比重大，測(cè)試效率低下，測(cè)試覆蓋率低等問(wèn)題，提出一種基于協(xié)議狀態(tài)遷移遍歷的模糊測(cè)試優(yōu)化方法。實(shí)驗(yàn)結(jié)果表明，在相同測(cè)試時(shí)間情形下，本文方法可以針對(duì)性地發(fā)送更多測(cè)試用例，更易觸發(fā)協(xié)議程序異常，測(cè)試效率更高。下一步研究將提高測(cè)試用例的有效性，結(jié)合本文優(yōu)化方法，更好地提高模糊測(cè)試效率。

表5 5小時(shí)漏洞挖掘效果統(tǒng)計(jì)結(jié)果 min