基于擴展前綴樹的協議格式推斷方法

洪 征，田益凡，張洪澤，吳禮發

解放軍陸軍工程大學 指揮控制工程學院，南京 210000

1 引言

協議規范是對網絡協議語法、語義以及同步等信息的具體描述，在網絡安全領域扮演著重要角色。僵尸網絡中，攻擊者使用C&C（Command and Control）協議來控制存在漏洞的主機實施DDoS（Distributed Denial of Service）攻擊等惡意行為，網絡管理員需要依據C&C協議規范來發現和分析僵尸網絡[1]。入侵檢測系統中，需要基于協議規范從繁雜的網絡流量中辨識出惡意流量。在模糊測試過程中，可以利用協議規范指導測試用例生成以實現更加高效的自動化漏洞挖掘[2-3]。然而出于利益、版權、安全等因素，軟件廠商和個人往往不愿意公開協議細節，如微軟使用的網絡文件共享SMB（Server Message Block）協議，Oracle數據庫訪問的TNS（Transparence Network Substrate）協議以及微信、QQ等即時通信軟件所使用的協議都沒有公開協議細節，這些未知協議在網絡中的廣泛使用，給安全防護帶來了極大的阻礙。

對于未知協議而言，目前主要通過協議逆向分析方法[4]獲取其協議規范。依據分析對象的不同，逆向分析方法可分為兩類：基于網絡流量的分析方法和基于指令執行軌跡的分析方法。基于網絡流量的分析方法對截獲的網絡數據流進行分析，通過生物信息學、統計分析、數據挖掘等方法，對報文樣本進行聚類分析，依據相同格式報文在取值上的相似性，分析獲取協議語法、語義信息。基于指令執行軌跡的分析方法以協議解析過程中的指令執行軌跡為分析對象，將協議輸入數據作為污點數據源，利用動態污點分析（Dynamic Taint Analysis）方法[5]跟蹤數據解析過程，依據協議解析程序如何使用污點數據以及相應的上下文信息獲取協議規范。

基于指令執行軌跡的分析方法通常具有較高的準確率，能夠獲得更全面的語義信息，但這類分析方法的實施需要分析人員擁有協議終端的可執行程序，并要求依據協議解析環境進行分析，依賴于底層平臺，無法移植，通用性不強。基于網絡流量的分析方法以網絡數據流為輸入，雖然其準確率依賴于捕獲樣本的豐富程度，但實現靈活，適用于各種應用場景，能夠實施自動化分析。本文針對基于網絡流量的分析方法進行研究，重點關注協議語法以及語義信息的提取。

目前國內外已有一些針對協議格式提取的研究成果，PI（Protocol Information）項目[6]是最早提出的基于網絡流量的協議格式推斷方法，引入了生物學中的多序列比對算法，通過將報文樣本進行比對對齊的方式提取協議格式信息。Cui等人提出一種基于遞歸聚類的協議格式提取方案Discoverer[7]，按照文本和二進制兩種屬性對報文字節流進行標注，得到報文屬性序列，并對其進行序列比對得到初始聚類結果，隨后利用格式標志（Field Distinguish）字段進行遞歸聚類獲取協議格式。Krueger提出一種基于統計的格式推斷方法PRISMA[8]。該方法首先利用自然語言處理中的N-gram思想以及分隔符對報文序列進行分詞得到候選特征詞，進而使用統計學方法對候選特征詞進行篩選構建特征矩陣，并以特征詞為基礎描述報文序列。Zhang等人則提出一種基于專家投票算法的特征詞提取方法ProWord[9]，并將其應用于流量分類。Luo等人提出一種基于位置信息的協議格式推斷方法AutoReEngine[10]，采用Apriori算法獲取特征詞，利用位置信息對特征詞進行合并和篩選，得到協議關鍵詞集合，最終再次利用Apriori算法對協議關鍵詞進行組合提取協議格式及協議狀態機。

以上方案都存在一些缺陷：PI項目直接對整個報文樣本進行序列比對，時間復雜度較高。Discoverer雖然利用報文屬性序列和格式標志字段降低了時間復雜度，但其采用常見文本類分隔符對報文樣本進行劃分的處理方法并不適用于二進制協議。此外，對于未知協議而言哪些分隔符會在協議中被使用具有很大的不確定性。PRISMA中對文本協議使用分隔符方法進行劃分，也存在類似問題。且PRISMA在處理二進制協議時，采用N-gram方法選取固定長度的特征詞，而實際報文中特征詞的長度并不相同，固定長度的特征詞的權重也會受到隨機串的影響。AutoReEngine通過Apriori算法結合位置信息提取協議關鍵詞，對于字段位置可變的協議，如HTTP、SIP協議，可能遺失部分關鍵詞。

為了提高協議格式推斷方法的通用性以及準確率，本文提出一種基于擴展前綴樹的應用層未知協議格式推斷方法，實現了原型系統EPT-PFI（Extended Prefix Tree based Protocol Format Inference）。EPT-PFI以截獲的網絡報文作為輸入，通過N-gram方法對報文樣本進行分詞，結合點間互信息PMI（Point Mutual Information）對候選關鍵詞進行合并提取協議關鍵詞，在此基礎上對報文樣本進行標注獲得協議關鍵詞序列。而后構建擴展前綴樹（Extended Prefix Tree，EPT）描述協議關鍵詞序列，并基于擴展前綴樹實現分段的多序列比對。最后，依據協議報文結構對擴展前綴樹進行合并，獲取協議格式信息。

2 基于擴展前綴樹的協議格式推斷

2.1 問題定義

協議規范由協議格式和協議狀態機兩部分構成。協議狀態機指定了合法報文的傳送順序，通過特定的報文發送序列構成特定會話（Session）以實現所需的功能。協議格式指定了會話中每條報文的語法以及語義信息，只有符合協議格式的才是合法報文，才能被協議終端正確解析。協議語法規定了報文的字段、結構以及字段語義，定義了組成報文的每一個字段（Field）的關鍵詞、數據類型、位置以及長度等具體信息。協議語義則定義了每一個字段在協議解析過程中所代表的實際意義，如HTTP協議（Hyper Text Transfer Protocol）請求報文中的“HOST”字段指定了請求資源所在的主機和端口號。常見的協議報文主要涉及以下幾種形式[11]：

（1）二進制形式，即預先規定若干個固定比特位為一個字段，字段內容即代表該字段的取值，如DNS協議的前16個比特位標識DNS ID號。

（2）ASCII碼形式，即采用易于理解的ASCII字符表示字段含義，使用預定義的分隔符（空格、回車換行等）作為字段結束標志，如MIME協議報文中的協議版本字段“MIME-Version”。

（3）TLV（Type-Length-Value）形式，即使用固定長度字節表示字段類型，固定長度字節的Length表名該字段取值的字節數，而其后緊跟的指定長度內容即字段取值，如eDonkey協議格式。

（4）指針形式，即采用指針指出某一個字段的開始和結束，如DNS協議響應報文中的回答計數指定了回答區域的條目數。

通信報文中一些字段是固定字段，一些是可變字段。但由于協議規范以及使用條件的制約，同種協議中同類格式的報文樣本往往會體現出一些統計相似性或相關性，具體來說就是在報文樣本中有一些具有固定模式、頻繁出現的比特串或字符串。文獻[11]將這些具有固定模式的串統稱為協議關鍵詞。以圖1所示HTTP協議報文為例，請求報文中的請求方法字段“GET”和協議版本字段“HTTP/1.1”，響應報文中的響應碼“200 OK”，以及“Key-Value”格式的字段中起標識作用的字符串“Key”，如“Host”、“Connection”和“Date”等，這些能夠標識報文類型或者協議字段的字符串都可以被稱為協議關鍵詞。

圖1 HTTP協報文示例

另外，由于分隔符通常在單個報文中多次出現且位置變化較大，對于協議分析會造成較大困擾，所以本文在沿用文獻[11]定義的基礎上，將分隔符排除在協議關鍵詞之外。而分隔符通常為一到兩個字節，如逗號、回車換行符等，可以通過設置N-gram分詞方法中N的取值來過濾掉分隔符。

本文的協議格式提取方案建立在協議關鍵詞分析的基礎之上。現有研究采用分隔符對文本協議進行分詞以得到協議關鍵詞，但未知協議的分隔符存在較大不確定性。對于二進制協議，目前方法通常采用N-gram提取關鍵詞，但所得到的關鍵詞為固定長度N，而實際協議關鍵詞的長度往往不固定，所以這類方法與實際存在出入。論文提出一種基于點間互信息的協議關鍵詞提取方法，適用于二進制協議和文本協議。首先采用N-gram分詞方法對報文樣本進行處理，在得到固定長度的候選關鍵詞后，結合點間互信息對候選關鍵詞進行合并，推斷獲得不同長度的協議關鍵詞。

在信息論中，熵是對事物不確定性的度量，而點間互信息（Point Mutual Information）是在熵的基礎上提出來的概念，這一概念經常被用于自然語言處理以及數據挖掘領域來衡量兩個單詞間的相關程度。單詞wi,wj之間的互信息可以定義為：

p(wi,wj)表示單詞wi,wj同時出現在一個報文中的概率，p(wi)表示單詞wi出現在報文樣本中的概率，p(wj)表示單詞wj出現在報文樣本中的概率。PMI(wi,wj)衡量的是兩個單詞之間的相關性，即確定了一個單詞后另一個單詞的不確定性（即熵值）的減少量，PMI(wi,wj)越大，則兩個單詞之間的相關性越高。

對于通過分詞獲得的候選關鍵詞而言，如果兩個候選詞是一個協議關鍵詞的子串，那么它們之間將具有較大的相關性。本文引入點間互信息來衡量候選關鍵詞之間的相關性。如果兩個候選詞位置相鄰、存在N-1個連續的相同字符（如“HTT”和“TTP”）且相關性較大，則將兩者合并為一個長度大于N的候選詞，如此重復以獲得任意長度的協議關鍵詞。

獲取協議關鍵詞后，依據報文樣本對應的協議關鍵詞序列構建擴展前綴樹，實現報文樣本的初始聚類以及同類報文的分段。隨后，采用分段的多序列比對獲取報文的詳細格式信息。并通過對擴展前綴樹進行合并以減少冗余，得到最終協議格式。

2.2 方法概述

本文提出的協議格式推斷方法，主要包括4個處理階段：預處理階段、協議關鍵詞提取階段、報文結構提取階段以及協議格式合并階段，主要流程如圖2所示。其中預處理階段的主要工作是對原始數據流進行劃分獲取報文樣本集合。協議關鍵詞提取階段將利用N-gram分詞方法對報文樣本進行處理，結合互信息獲取協議關鍵詞序列。報文結構推斷階段依據協議關鍵詞序列構建擴展前綴樹，通過基于擴展前綴樹描述的分段多序列比對推斷協議格式。協議格式合并階段將基于報文結構對擴展前綴樹進行合并，得到詳細的協議格式信息。

2.2.1 預處理階段

圖2 原型系統EPT-PFI的主要處理流程

對于未知協議而言，分析對象是連續的網絡數據流，由于網絡分層結構以及分片機制，往往需要以會話和報文為粒度對數據流進行分割得到便于分析的報文樣本集合[12]，以會話為粒度的分割被稱為會話劃分，以報文為粒度的分割被稱為報文定界。

會話劃分是從連續的網絡數據流中分離出通信實體間的單次會話，主要依靠底層協議提供的信息實現。對于應用層協議而言，可以使用協議五元組<源IP地址，源端口號，目的IP地址，目的端口號，傳輸層協議類型>得到獨立的通信會話。

報文定界是從一次獨立會話中分離出單個協議報文。對于應用層協議而言，可以利用傳輸層協議的報文首部和首部的長度字段實現。定界之后得到的報文樣本作為后續階段的輸入。

2.2.2 協議關鍵詞提取階段

此階段的目的是從經過預處理的報文樣本中提取協議關鍵詞，并使用協議關鍵詞對報文進行標注得到協議關鍵詞序列。原始報文樣本集合可以表示為S={m1,m2,…,mi,…,ms}，其中mi為樣本集合中的某一個報文，表示報文mi中的第 j個字符。得到初始報文樣本后，采用N-gram分詞方法對報文樣本進行逐一處理，得到所有在樣本集合中出現過的長度為N的字符串，如對報文進行N-gram分詞，將得到等字符串。計算每一個字符串相對于完整報文樣本的出現頻率。在統計時，如果一個字符串在一個報文中出現多次，只進行一次統計，因為此階段處理的目的是獲取候選關鍵詞集合，而協議關鍵詞是對協議格式或者報文字段的一種標識，往往不會在同一樣本中重復出現。

在得到的字符串中，大部分字符串出現的頻率較低，它們通常對應著報文中的變值字段或者是變值字段的子串，這些字段取值不確定甚至完全隨機產生。協議格式提取希望確定的是相對穩定的協議報文構成結構，故設置閾值Tfreq，對這些出現頻率較低的字符串進行過濾。將頻率高于閾值的字符串作為候選關鍵詞添加到候選關鍵詞集合G中。

由于候選關鍵詞集合G中的元素都是通過N-gram分詞得到，其長度皆為N，而實際協議報文中，協議關鍵詞長度并不完全相同。對于長度大于N的協議關鍵詞，可以由長度為N的子串合并得到，如HTTP協議中的關鍵詞“Host”可以由“Hos”和“ost”合并得到。鑒于這種相關性，本文使用點間互信息對集合G中的候選詞進行合并，以得到不同長度的協議關鍵詞。

為了對候選關鍵詞進行合并，首先，需要依據候選關鍵詞集合G對報文樣本進行標注，得到對應的候選關鍵詞序列，其中表示報文mi中的第 j個候選關鍵詞，表示在報文樣本集合中出現的頻率，表示在報文mi中相對于報文起始位置的偏移。進而得到整個報文樣本對應的候選詞序列集合Seq={key_seq1,key_seq2,…,key_seqi,…}。

隨后，基于互信息對集合Seq中的每個候選關鍵詞序列key_seqi中的協議關鍵詞進行合并，具體步驟如下。

步驟1從左至右遍歷候選關鍵詞序列key_seqi，尋找位置相鄰且存在相同的連續N-1個字符（即滿足以下條件）的候選關鍵詞：

（1）候選詞，并且

（2）候選詞位置相鄰-=1。

（3）候選詞的后N-1個字符與的前N-1個字符相同：bg+lj-N+2…bg+lj-1=bh…bh+N-2。

步驟2對于滿足步驟1中條件的候選詞，搜索點間互信息集合PMI（初始為空），若其中存在PMI()則直接獲取其值，若不存在則計算它們之間的互信息PMI()并存入集合PMI中。得到候選詞之間的互信息后，若PMI()超過所設定的閾值TPMI，則合并候選詞1的重疊部分得到新的候選詞w：

步驟3從key_seqi中刪除，將值替換為w。隨后從繼續遍歷更新后的key_seqi，重復步驟1～3直至遍歷完key_seqi。

步驟4由于協議關鍵詞一般不會在同一報文中重復出現，故遍歷key_seqi，刪除在同一個關鍵詞序列中出現多次的元素，得到最終的協議關鍵詞序列以及更新后的關鍵詞序列集合Seq。

2.2.3 協議格式推斷階段

通過上述步驟能夠得到每個報文樣本對應的協議關鍵詞，而相同格式的報文對應的關鍵詞序列往往相同，因此可以依據協議關鍵詞序列對報文樣本進行聚類，將同種格式報文聚成一類，依據同類報文樣本在結構上的相似性提取協議格式信息。本文提出使用擴展前綴樹描述協議關鍵詞序列，擴展前綴樹中的每條路徑代表一種關鍵詞序列，節點對應協議關鍵詞，節點之間的邊代表報文樣本中對應關鍵詞之間的報文片段。采用擴展前綴樹的描述方法，一方面便于實現對報文樣本的初始聚類，另一方面便于實現分段的多序列比對。

2.2.3.1 構建擴展前綴樹

前綴樹（Prefix Tree）是一種有序多叉樹結構，通常以字符串為輸入，利用字符串的公共前綴來實現快速檢索以及字符串匹配等操作。本文對前綴樹進行擴展，將協議關鍵詞序列作為輸入，協議關鍵詞作為節點，按照順序將協議關鍵詞插入前綴樹中，以得到的擴展前綴樹描述報文樣本對應的協議關鍵詞序列。

為了構建擴展前綴樹，在得到協議關鍵詞序列集合Seq后，遍歷集合Seq，將其中的元素依次插入樹結構中。同時，為了排除樣本中的噪聲，在構建擴展前綴樹的過程中記錄每種關鍵詞序列對應的報文樣本總數，刪除樣本數小于閾值Tnum的關鍵詞序列。舉例說明，對于包含表1所示元素的集合Seq，首先構建根節點“Start”表示起始位置，隨后遍歷集合Seq，依據其中的協議關鍵詞序列將得到圖3所示的擴展前綴樹。

圖3 擴展前綴樹示例

擴展前綴樹中的每條路徑表示一種協議格式，圖中共有6種協議格式。樹中的每一個節點表示一個協議關鍵詞，節點之間的邊表示真實報文中對應協議關鍵詞之間的報文片段。例如，擴展前綴樹第1條和第2條路徑中“GET”節點與“HTTP”節點之間的邊，表示格式符合表1第1種或第3種關鍵詞序列的對應的報文樣本示例中協議關鍵詞“GET”和“HTTP”之間的報文片段“admin.php”和“index.php”。

構建擴展前綴樹的過程實際是對報文樣本進行聚類以及對聚類子類中的報文進行分段的過程，同種格式的報文會匯聚在同一條路徑上，并且依據節點對應的協議關鍵詞分為多個片段，這種表示方式有利于后續提取每個報文片段的結構以及語義信息。

2.2.3.2 序列比對

對于得到的擴展前綴樹，采用先深搜索遍歷每一條路徑，對同一路徑上相鄰兩節點之間的報文（即擴展前綴樹中的邊）采用Needleman-Wunsch多序列比對算法進行比對，以提取詳細的協議格式信息。包括協議字段取值類型（字符串、整數或二進制數等）、取值范圍（包含常量字段、枚舉字段、隨機字段）等，并在擴展前綴樹上做相應標注。

舉例來看，若圖3擴展前綴樹中第1條路徑所對應的報文如圖4所示，其協議關鍵詞序列為<“GET”，“HTTP”，“Host”，“User-Agent”>（圖中“_”表示報文中本身包含的空格，“--”表示序列比對填充的空格）。通過多序列比對能夠得到詳細的格式信息，如第2個片段取值為一個浮點數后接回車換行符，且浮點數取值為“1.1”或“1.0”。

圖4 報文示例

通過這種分段的多序列比對，能夠抽象出每個序列片段的報文結構，相對于PI項目等直接對整個報文進行序列比對，降低了時間復雜度。同時這種分段的格式提取方法，將報文依據協議關鍵詞進行劃段，也解決了多序列比對方法應用于結構復雜、報文過長的協議樣本效果不佳的問題。

2.2.4 協議格式合并階段

由于實際使用的通信協議往往具有較強的靈活性，完全依據協議關鍵詞序列進行協議格式提取容易產生較多的冗余格式，即一種協議格式在推斷時被劃分為多種不同的協議格式。過多的格式冗余將導致推斷結果的適用性降低。

一方面，一些報文字段的位置順序是可變的。如HTTP 協 議 中 ，“GET admin.php HTTP/1.1 Host：www.foobar.com User-Agent：Opera/9.20”和“GET index.php HTTP/1.1 User-Agent：Mozillia/5.0 Host：www.baidu.com ”兩條報文實際上對應于一種協議格式，其中“Host”關鍵詞和“User-Agent”關鍵詞的先后順序是可以變化的。但是在擴展前綴樹中，兩條報文對應的協議關鍵詞序列不同，將被作為不同的協議格式。另一方面，一些報文中的協議關鍵詞屬于枚舉類型。例如，HTTP請求方法字段可以在“GET”、“POST”、“HEAD”等協議關鍵詞組成的集合中枚舉。例如“GET admin.phpHTTP/1.1 Host：www.foobar.com User-Agent：Opera/9.20”和“POST/eapi/pl/count HTTP/1.1 Host：music.163.com User-Agent：Mozilla/5.0”兩條報文僅僅請求方法不同，實際隸屬于同一種協議格式。

表1 關鍵詞序列集合的示例

因此需要對得到的擴展前綴樹進行合并，本文提出以下合并策略：

（1）若擴展前綴樹中兩條路徑所包含的節點種類完全相同，或某一條路徑包含的協議關鍵詞是另一條路徑對應關鍵詞的子集，并且兩條路徑上相同節點對應的邊結構相似，則認為這兩條路徑對應著位置可變的協議格式，故將兩者合并為一種格式（保留節點數較多的路徑）。例如，圖3擴展前綴樹中路徑1和路徑2、路徑5和路徑6所包含的節點種類完全相同，只是部分節點位置不同，若兩條路徑中相同節點間的邊對應的結構相似，則可刪除其中任一條路徑，得到如圖5所示擴展前綴樹。

圖5 第一種格式合并策略的示例

（2）若兩條路徑僅有一個節點不同，且與此節點相關的邊在兩條路徑上結構相似，則認為這兩條路徑中的不同節點對應著同種協議格式的枚舉字段的兩種取值，故將兩節點合并為一個節點，兩條路徑合并為一種協議格式。譬如，采用方法（1）對圖3擴展前綴樹進行合并后，最左邊的路徑和最右邊的路徑中僅有一個節點“GET”和“POST”不同，中間兩條路徑中僅有一個節點“200 OK”和“404 Not found”不同，則可實施合并，得到如圖6所示的擴展前綴樹。

圖6 第二種格式合并策略的示例

通過格式合并得到的最終擴展前綴樹即代表了目標協議的詳細格式，每一條路徑對應一種協議格式。這種協議格式表示方式能夠有效減少冗余，提高協議格式結果的實用性。

3 實驗結果及分析

3.1 實驗方法

為了對本文提出的方法進行驗證，在重用Netzob[13]多序列比對代碼的基礎上，實現了原型系統EPT-PFI。實驗中，選取文本協議HTTP和FTP與二進制協議DNS和NetBIOS作為實驗對象。同時選取了現有的協議逆向工具Netzob、AutoReEngine進行對比試驗。本文采用文獻[7]中的準確率（Correctness）和精簡率（Conciseness）作為評價指標對實驗結果進行評估。準確率表示的是推斷所得格式與實際格式相符的報文樣本所占的比例，準確率越接近1說明推斷結果越接近實際格式。精簡率表示的是推斷所得格式的種類數目與實際樣本中包含的格式種類數的比值。由于是比值，精簡率沒有單位。精簡率越接近1說明所得結果越接近真實格式。由于協議格式推斷中常可能將同種格式報文劃分為多種格式造成冗余，因此精確率越小說明得到的協議格式種類越少，冗余越少。

3.2 結果分析

本文在配置為2.93 GHz的CPU、4 GB內存、操作系統為Windows 7的PC上基于Python語言實現了論文中提出的方法。考慮到AutoReEngine關鍵字識別方法實用性強，準確率高，并且具有代表性[5]，基于SPMF平臺[14]提供的Apriori算法實現了AutoReEngine方法，與本文方法進行比較。

原型系統EPT-PFI設定閾值Tfreq為0.6，設定閾值TPMI為0.8，依據文獻[15]N-gram分詞中N 取3。表2、表3是分別針對HTTP協議所獲得的協議關鍵詞（其中“_”表示空格）。分析實驗結果：（1）從表2可以看出，EPT-PFI得到的協議關鍵詞與實際基本吻合（所得關鍵詞附帶“ ”或“_”，因為它們總是同時出現，所以被合并），但受限于樣本的多樣性，可能將某些可變字段被識別成了固定字段，如協議版本字段“HTTP/1.1”，這是由于所捕獲的樣本中基本都是使用的1.1版本的HTTP協議。而其中的協議關鍵詞“HTTP/1.1”兩邊沒有攜帶空格換行等符號，是由于HTTP協議請求報文和應答報文中都包含版本號字段。（2）綜合分析表2和表3可知，相對于AutoReEngine，EPT-PFI提取的協議關鍵詞更加豐富，這是由于HTTP協議首部行中各個字段的位置是可變的，導致對應的關鍵詞位置偏移較大。依據這些關鍵詞結合擴展前綴樹描述，能夠獲取首部行中各個字段的報文結構，得到更加詳細的協議格式信息。

表2 EPT-PFI針對HTTP協議提取的協議關鍵詞

表3 AutoReEngine針對HTTP協議提取的協議關鍵詞

如圖7、圖8分別為采用EPT-PFI、Netzob、AutoReEngine對4種目標協議進行實驗所得結果。從實驗結果可以看出：（1）EPT-PFI在準確率上高于Netzob，稍低于AutoReEngine。AutoReEngine準確率幾乎都達到了100%，這是因為AutoReEngine只保留了位置相對固定的協議關鍵詞，對于字段位置可變的協議關鍵詞都會被Apriori算法剪枝，如HTTP協議中的“Host”、“Connection”等字段由于在報文樣本中出現的位置變化較大而被忽略。因此，AutoReEngine只能夠提取出位置相對固定的字段關鍵詞，但無法獲取詳細的格式信息。（2）在精簡率上Netzob明顯高于EPT-PFI和AutoReEngine，說明所得協議格式冗余較多，這是由于Netzob是在多序列比對的基礎上進行報文聚類的，可能將同種格式報文劃分為多種格式。而EPT-PFI由于采用了基于擴展前綴樹的格式合并，其精簡率略優于AutoReEngine。綜合來看，Netzob對于文本協議效果明顯優于二進制協議，而本文方法對于文本協議和二進制協議都能取得較好結果。

圖7 正確率實驗結果

圖8 精簡率實驗結果

通過上述實驗分析，可以看出原型系統MI-PFE能夠較好地完成文本協議以及二進制協議的格式推斷工作。

4 總結

本文提出了一種基于擴展前綴樹的協議格式推斷方法，通過N-gram分詞結合互信息獲取協議關鍵詞，依據協議關鍵詞序列構建擴展前綴樹，在擴展前綴樹描述的基礎上進行分段多序列比對，最終通過對報文結構的擴展前綴樹進行合并得到最終協議格式。實驗表明，本方法能夠適用于文本協議和二進制協議，并且與現有的協議格式推斷工具相比具有一定優勢。

[1]羅建楨，余順爭，蔡君.基于最大似然概率的協議關鍵詞長度確定方法[J].通信學報，2016，37（6）：119-128.

[2]Sija B D，Goo Y H，Shim K S，et al.A survey of automatic protocol reverse engineering approaches，methods，and tools on the inputs and outputs view[J].Security&Communication Networks，2018：1-17.

[3]Gascon H，Wressnegger C，Yamaguchi F，et al.Pulsar：Stateful black-box fuzzing of proprietary network protocols[M]//Security and Privacy in Communication Networks.Germany：Spring International Publishing，2015：330-347.

[4]Duchêne J，Guernic C L，Alata E，et al.State of the art of network protocol reverse engineering tools[J].Journal of Computer Virology&Hacking Techniques，2017：1-16.

[5]Narayan J，Shukla S K，Clancy T C.A survey of automatic protocol reverse engineering tools[J].ACM Computing Surveys，2015，48（3）：1-26.

[6]Marshall B.Protocol information project[EB/OL].（2004-10-05）[2017-12-24].http：//www.4tphi.net/～awalters/PI/PI.html.

[7]Cui W，Kannan J，Wang H J.Discoverer：Automatic protocolreverse engineering from network traces[C]//16th USENIX Security Symposium.Boston：USENIX Association，2007：199-212.

[8]Krueger T，Kraemer N.PRISMA：Protocol inspection and state machine analysis[J].Journal of the American Chemical Society，2015，98（25）：8101-8107.

[9]Zhang Zhuo，Zhang Zhibin，Lee P P C，et al.ProWord：An unsupervised approach to protocol feature word extraction[C]//Proceedings IEEE INFOCOM，2014：1393-1401.

[10]Luo J Z，Yu S Z.Position-based automatic reverse engineering of network protocols[J].Journal of Network&Computer Applications，2013，36（3）：1070-1077.

[11]黎敏，余順爭.抗噪的未知應用層協議協議格式最佳分段方法[J].軟件學報，2013，24（3）：604-617.

[12]李偉明，張愛芳，劉建財，等.網絡協議的自動化模糊測試漏洞挖掘方法[J].計算機學報，2011，34（2）：242-255.

[13]Bossert G，Hiet G.Towards automated protocol reverse engineering using semantic information[C]//ACM Symposium on Information，Computer and Communications Security，2014：51-62.

[14]Fournier-Viger P，Gomariz A，Gueniche T，et al.SPMF：A Java open-source pattern mining library[J].Journal of Machine Learning Research，2014，15（1）：3389-3393.

[15]Wang Y，Zhang Z，Yao D D，et al.Inferring protocol state machine from network traces：A probabilistic approach[C]//International Conference on Applied Cryptography and Network Security.Berlin：Springer-Verlag，2011：1-18.