基于改進投票專家算法的專有協議模糊測試方法

劉津霖，付光遠，李海龍，汪洪橋

火箭軍工程大學 信息工程系，西安 710025

1 引言

近年來，專有協議（proprietary protocol）的應用越來越廣泛，尤其是在工業控制領域。工控系統在逐漸變得更加信息化、自動化和智能化的同時，也埋下了安全隱患。工業控制系統不同于傳統信息系統，一旦遭受攻擊，會對國家安全造成重大打擊，如：核電站爆炸、電力系統癱瘓、城市交通停運等。因此，研究工控系統安全關乎國家的戰略安全，研究意義重大。提升工控系統安全的主要方法是漏洞挖掘，防患于未然。其中，模糊測試被公認為是最有效的漏洞挖掘方法，但是由于工控系統涉及的協議組成十分復雜，存在大量廠商自己定義的專有協議[1]，這些專有協議沒有公開的資料說明，對協議的結構和會話過程等信息無法輕易獲悉，給模糊測試造成了巨大的挑戰[2-3]。

針對專有協議的問題，可以采用協議逆向技術，獲得專有協議的報文格式和協議狀態機，將專有協議轉化成“公有協議”，再結合模糊測試技術對被測目標進行漏洞挖掘。對于協議逆向技術的研究已經有了很多豐碩的成果，如：PI工程和它的改進方法Discoverer[4]采用生物信息學序列比對算法逆向協議的報文格式，為專有協議逆向解析提供了新思路，但是得到的分析結果缺少語義信息；Prospex[5]、ScriptGen[6]等方法充分考慮到了報文的語義信息，定義報文的關鍵字作為協議的語義信息，使逆向的報文格式和協議狀態機更加完整。因此，協議關鍵字提取質量的好壞直接影響協議的逆向結果。目前提取關鍵字應用最多的方法是n-gram算法[7]，即用一個大小為n的滑動窗口將報文劃分成等長的子序列。然而，這種方法會使大于n字節的協議關鍵字被分割，或者使小于n字節的協議關鍵字混入噪聲，從而影響協議逆向的效果。

本文提出的專有協議模糊測試方法，首先需要對流量數據進行流測度和分類預處理，并且提取協議關鍵字。為解決n-gram方法只能將所有報文劃分為等長子序列的局限性，本文利用投票專家（Voting Expert，VE）算法提供更為準確的關鍵字提取，并且針對VE算法在處理協議數據時存在節點空間爆炸的問題，基于有損計數算法對VE算法進行了改進。在成功獲取協議的關鍵字后，采用因果態分割重建算法重建未知專有協議的報文格式ε機。然后從每個會話中提取可以代表該會話的報文類型，將會話過程表示為一個報文類型序列，將所有的狀態轉換序列融合成一個確定有窮自動機，即協議的狀態機。最后，根據逆向得到的有關協議的報文結構和協議狀態機信息生成模糊測試用例，并對測試目標進行模糊測試。

2 改進的投票專家算法

2.1 投票專家算法

投票專家算法[8]，屬于局部貪心算法，主要是通過一個相對較小的滑動窗口，選擇最有可能的邊界位置對單詞分區。本文利用VE算法代替傳統的n-gram算法，提取被測專有協議的關鍵字。

為了實現滑動窗口大小為L的VE算法，用一個深度為(L+1)的單詞查找樹（Trie）來保存數據流中所有可能發生的字節組合。

例如，字符序列為“abcabd”，窗口大小為2時，可以生成深度為3的樹，如圖1所示。從圖中可以看出子字符串ab出現兩次，并且每次a出現時，b都是緊隨其后。bc和bd各出現一次。

圖1 單詞查找樹示意圖

VE算法根據兩項指標劃分單詞，一個是內部熵（Internal entropy）用HI表示，代表該子序列在數據流中總是作為一個整體出現，應作為整體得到保留，表達式如式（1）所示：

其中，w代表子序列，而P(w)則表示該子序列出現的概率。HI的值越小，代表子序列w越常作為一個整體出現。

另外一個指標是邊界熵（Boundary entropy）用HB(w)表示，若后續字節序列經常變化，則認定該字節后為一個詞之間的邊界，表達式如式（2）所示：

為了計算不同長度的子序列，需要對表達式進行標準化。

VE算法可以分為兩個階段，第一個階段為投票階段（Voting phase），在大小為L的滑動窗口內對可能是邊界的位置進行投票。xIi和xBi分別表示在i處的內部投票點（internal voting point）和邊界投票點（boundary voting point），j在0到L之間取值：

每個點x存在一個選票分數（Vote Score）用V(x)表示，其計算規則如式（7）所示，1（·）代表一個指示函數，如果x=y函數的值為1，否則為0。

第二個階段為判決階段（Decision phase），在判斷點x處為詞邊界時遵循以下兩條規則：

（1）點x得到的票數比相鄰點更多；

（2）得票數大于設定的閾值T。

通過VE算法可以得到字節序列中可能的詞邊界，將字節序列按一定的語義信息進行劃分。

2.2 存在的局限性

雖然VE算法在自然語言處理中得到了很好的分詞效果，但是在處理網絡流量時存在一些缺陷。如，節點空間爆炸問題。在處理自然語言時，由于傳統的組合習慣會限制某些子序列的發生，以英語為例，如當出現“tio”時，后續的字符極有可能是“n”，這在某種程度上減少了子樹的數量，節省了存儲空間。但是在處理網絡協議數據，特別是純二進制數據時，網絡流量中子序列的分布概率更稀疏，往往會產生更多新的字節組合，從而導致占用大量存儲空間。

2.3 改進方法

盡管VE算法在處理協議時會導致節點空間爆炸，但是通過觀察發現，大多數節點的頻率非常低。因此，雖然捕獲所有節點需要一個巨大的存儲空間，但是只需要關注有足夠高的頻率的子集即可。

為了解決VE算法在處理協議時存在的問題，本文通過有損計數算法（Lossy Counting Algorithm，LCA）[9]對單詞查找樹進行剪枝操作，刪除頻率非常低，不太可能是關鍵詞的后繼節點，從而節省空間。

LCA算法是一種近似計算算法，可以通過定期消除低頻數據的方式，利用有限的內存從數據流中返回高頻率數據項，在處理實時大數據流上的頻率統計問題中得到了廣泛的應用。本文的方法是利用LCA算法在修剪期內，對出現頻率低于設定閾值的子序列進行剔除。LCA算法最為關鍵的參數就是最大錯誤率e，低錯誤率會保留更多的子序列但是會增加內存的壓力，高錯誤率可以減少超出內存的風險但是可能會在剪枝操作中剔除一些有用的子序列，因此需要在兩者之間找到平衡。另外，雖然通過剪枝操作可以在單詞查找樹中剔除低頻的子序列，但是在計算選票分數時需要考慮所有子序列，因此，本文增加了補償環節，即將沒有出現在單詞查找樹中的子序列的出現頻率統一設定為e/2。

文中已給出改進的投票專家算法ImproveVE的偽代碼（圖2）。算法的參數分別為P：流量數據；M：剪枝期處理字節數；L：滑動窗口大小；T：決定階段閾值。ImproveVE函數首先調用BuildTrie函數計算子序列的頻率（第6～16行），在各個剪枝期對低于頻率閾值的子序列節點進行剔除（第17～21行）。構建單詞查找樹，然后計算樹中所有子序列的熵值（第28～29行），并且補償被剪切子序列（第33行），計算相應的熵值（第34行）。最后計算投票分數，確實可能的詞邊界（第36～41行），提取所有的候選關鍵字到集合W中（第42行）。

3 模糊測試

3.1 提取關鍵字

通過ImproveVE算法得到的只能稱之為候選關鍵字集合，所謂的關鍵字是指那些可以區分應用協議的字節子序列。目標是根據權值對候選關鍵字集合中的關鍵字進行降序排序，提取排名靠前的子序列作為協議的關鍵字。因此，排序規則對特征詞的選取起決定性作用。

本文利用信息檢索與數據挖掘的常用加權技術——詞頻逆文檔頻率TF-IDF[10-11]（Term Frequency-Inverse Document Frequency）作為特征詞排序的評判標準。該標準需綜合考慮頻率與位置兩方面的信息。因為，在報文格式中，存在如源地址、目的地址等信息，雖然出現的頻率會很高，但是對報文格式的表達沒有任何意義。

通過TF-IDF計算所有候選特征詞的權值后，選取排名在前k的子序列作為協議的關鍵字，用于協議的逆向解析過程。

3.2 協議逆向分析

3.2.1 報文格式

圖2 改進的投票專家算法ImproveVE的偽代碼

在得到目標協議的關鍵字集合后，利用ε機表示協議的報文格式。因為協議可以看作是一個隨機過程，構成協議的字符串以一定的概率出現，協議的內部狀態與某些字符串的集合之間存在對應關系。而隱馬爾科夫模型（Hidden Markov Mode，HMM）是一種只通過可觀察狀態就能求得系統隱藏的內部狀態的統計模型。因此，可以運用求解HMM的思想得到專有協議的報文結構狀態機模型。ε機是一種特殊的隱馬爾科夫模型，可以對隨機過程進行最小最優預測，由因果態方程ε和狀態轉移矩陣T構成[11]。所謂的因果態方程指的是歷史與歷史集合之間的一種映射關系。其定義如式（8）所示：

其中，和分別代表一個隨機過程的歷史和未來兩個部分，SL和SL分別表示歷史狀態的最后L個字符和未來狀態的最初L個字符。

目前，有幾種重建算法可以用于推斷ε機。如，因果態分割重建算法[12]（Causal-State Splitting Reconstruction，CSSR）、狀態合并ε機推斷算法（State-merging ε-Machine Inference Algorithm）等。因果態分割重建算法與狀態合并ε機推斷算法最主要的區別是CSSR會利用一些關于因果態的狀態屬性來指導搜索和自動機建設，并且收斂速度更快。CSSR的核心思想是分割——將一個有限的符號集分割成多個因果態。其偽代碼如圖3。

圖3 CSSR偽代碼

其總體思路：首先做零假設（Null Hypothesis），假設該隨機過程中的所有事件屬于同一個狀態。然后計算下一個事件的未來分布，通過Kolmogorov-Smirnov對零假設進行假設檢驗，如果假設不被拒絕，新的分配被認為與現有分布狀態相同，該事件被添加到這個狀態，如果有任意一個事件不滿足于假設條件，則被分離出來構成新的狀態。最后得到的狀態有可能數量十分龐大，但其中大部分是瞬時狀態。通過刪除瞬時狀態，保留循環狀態，得到最終的報文格式ε機。

具體過程如偽代碼所示，首先Initialization函數初始化（第1行），然后Sufficiency函數構建因果態（第11～28行），最后Recursion函數用于消除瞬時狀態，確定因果狀態機并填充轉換表（第11～28行）。在Sufficiency和Recursion函數中均調用了TEXT函數（第30～37行）和MOVE函數（第39～43行），分別用于進行測試零假設和狀態的移動、合并操作。參數W代表用于構建報文格式馬爾科夫模型的字母表，即提取的協議關鍵字集合；xˉ表示從W中提取的長度為N的序列，Lmax表示估計因果態時最大的歷史長度，α表示假設檢驗的置信度。通過該算法可以重建協議的報文格式ε機。

3.2.2 協議狀態機

網絡通信是由一個潛在的狀態機驅動，當某些事件觸發某些反應時進行狀態交換。報文格式信息僅僅可以反映協議的語法和語義信息，缺少揭示協議行為特征的時序信息。推斷協議的狀態機模型可以了解報文之間的相互關聯，進一步完善模糊測試器。

獲得協議報文格式后，需要對所有會話（Session）進行分析，從每個會話中提取可以代表該會話的報文類型，將會話過程表示為一個報文類型序列，構建APTA（Augmented Prefix Tree Acceptor）樹。

然后采用紅藍節點框架[13-15]對APTA樹進行簡化，最后最小化馬爾科夫模型為一個有限狀態自動機（Deterministic Finite Automaton，DFA），即如果將所有的狀態轉換序列融合成一個確定有窮自動機，那么這就是協議的狀態機。

另外，對于只能解決單項報文的專有協議模糊測試器，得到的協議狀態機顯然是不全面的。為了能夠應對雙向報文，本文對事件序列進行標記，用以區分是來自客戶端或者是服務器端。將來自同方向的報文構成一個轉換條件或者一個狀態，這樣可以把會話中的消息看作是一個狀態轉換序列。例如，將服務器端到客戶端的方向的報文定為狀態機模型的邊（edge），將客戶端到服務器端的方向的報文定義為狀態機模型的節點（node），反之亦可。具體的做法是采用大小為k的序列滑動窗口進行標記，例如，假設觀察到的事件序列為a、b、c、d，并且是從客戶端和服務器端交替生成的，則k=2時，得到的結果如式（9）所示：

3.3 生成模糊測試用例

模糊測試是通過向測試目標輸入非預期的數據并監測輸出數據中的異常來發現測試目標中可能存在的漏洞的方法[16]。生成測試用例就是產生這些用于測試的輸入數據的過程。

協議逆向階段可以得到有關協議的報文結構和協議狀態機信息，這些信息可以用來生成模糊測試階段的測試用例。報文結構可以用于構造完整的數據包，對于報文中的固定部分通常不會造成漏洞，更多的是關注變長部分，確定生成模糊測試用例的測試點。而協議狀態機可以明確協議的交互行為，控制協議的接收與發送。協議逆向工程與模糊測試技術的完美結合可以針對特定協議生成模糊測試用例，并且對測試目標進行漏洞挖掘。

本文采用基于文法驅動[17-18]的模糊測試用例生成技術，根據逆向得到的專有協議報文格式及狀態機信息，利用文法模型自動化生成測試用例。其流程如圖4所示。

圖4 生成測試用例流程圖

根據數據格式規范構建文法模型，結合通過協議逆向工程得到的協議信息構建文法分析樹。再利用模型中的屬性規則對文法元素實施選擇變異，進而生成測試用例進行模糊測試[19]。

4 實驗分析

本文從三個方面進行實驗分析驗證：首先，利用公有協議FTP、HTTP和SMTP對ImproveVE算法提取關鍵字的性能進行實驗分析；其次，通過逆向Modbus TCP協議，并與已有協議規范比對，檢驗逆向的效果；最后，用本文方法對專有協議WDB RPC進行逆向分析，并且針對WDB RPC協議對嵌入式實時操作系統VxWorks進行漏洞挖掘。

首先利用ImproveVE算法和傳統的n-gram算法分別對協議規范已知的公有協議FTP、HTTP和SMTP提取關鍵字，統計在一系列候選關鍵字集合排名前k項中提取的關鍵字數量，根據提取的關鍵字與真正關鍵字之間的百分比評判算法的優劣。在實驗參數的選取上，選擇最為常用的n=3作為n-gram算法的窗口大小，VE算法的滑動窗口大小、閾值以及剪枝期處理字節數分別取值10、6和10 000 000。

如圖5的實驗結果所示，ImproveVE算法相較于n-gram算法對報文子序列的劃分更為合理，提取的協議關鍵字更接近于真實情況。尤其是對FTP協議關鍵字的提取，其準確率已接近98%，準確地提取協議關鍵字更有利于對協議進行逆向分析。

另外，針對VE算法處理協議數據時存在節點空間爆炸，占用大量內存的問題，本文利用LCA算法對VE算法進行了改進。圖6是分別采用VE算法和改進后的ImproveVE算法處理SMTP協議時所產生的節點數量比對。從直觀上不難發現，改進后的算法明顯降低了節點數量。值得注意的是，雖然改進后的算法ImproveVE和VE算法相比減少了生成的節點數量，但是和n-gram相比，所占用的內存空間仍然較大，這就需要在準確性和資源占用兩者之間做權衡。根據本文的目的，對專有協議進行模糊測試，顯然提取關鍵字的準確性是首要因素。另外，通過對VE算法的改進，節省了大量內存，對內存資源的占用完全在可承受的范圍之內。因此，準確性這一指標更為重要，ImproveVE算法能較好地完成針對專有協議的關鍵字提取任務。

對改進的VE算法的性能進行對比實驗分析后，需要進一步驗證本文方法對專有協議的逆向效果。首先對公有協議Modbus TCP進行逆向分析。

Modbus是用于工業現場的總線協議，屬于應用層報文傳輸協議。Modbus TCP屬于Modbus標準的一種，屬于工業控制網絡范圍，是一種公有協議，Modbus TCP的報文格式與通過本文方法得到的報文格式ε機如圖7所示。

圖5 提取關鍵字的準確率

圖6 ImproveVE算法減少節點數量

圖7 Modbus TCP報文格式與ε機

根據已有的Modbus TCP的報文格式，可以獲悉該協議由事務標識符、協議標識符、長度字段、功能字段、單元標識符和負載構成。該協議對應的隱馬爾科夫模型由報文頭創建的6個狀態和相鄰狀態之間的轉換構成，其中Σn代表n個連續的字節，EOM代表消息是完整的，并準備轉發。接下來通過300條流量數據對Modbus TCP協議進行逆向分析，得到該協議的ε機。可以發現，前三個字段被分配到了同一狀態，這是因為它們的取值是固定的，因此在學習過程中自然被分配到同一狀態。雖然得到的ε機與真實的報文格式有所差異，不完全匹配，但卻是一個合理的分組，是完全基于觀察到的統計信息得到的結果。因為本文的方法是一個增量學習的過程，如果有足夠多的訓練數據，字節將被分配到正確的字段。

另外，可以觀察到，通過因果態分割重建算法不僅很好地重建了Modbus TCP協議的報文結構ε機，并且區分出了不同的功能字段，如表1所示。

接下來利用本文的方法對專有協議WDB RPC進行實驗分析。WDB RPC屬于嵌入式實時操作系統VxWorks的專有協議，利用WDB RPC協議既能直接訪問系統的內存，又能對VxWorks所有組件的工作狀態進行監控，如果組件發生異常，TAgent會利用WDB RPC協議自動告知當前連接的調試器。WDB RPC屬于典型的專有協議，沒有公開的文檔說明，公司外部人員對該協議的結構一無所知。WDB RPC目前有兩個版本，本文所研究的是WDB RPCv2，用于VxWorks 6.6及以上版本。本文通過500條WDB RPC流量數據對報文結構進行逆向分析，得到WDB RPC報文結構的ε機如圖8所示。

表1 Modbus TCP部分字符與相對應的功能

圖8 WDB RPC的ε機

通過協議逆向分析，可以獲得協議的報文格式和協議狀態機等信息，這些信息可以用于協議識別、異常檢測和智能模糊測試等諸多領域。本文主要是將協議逆向分析用于模糊測試，以解決由于工控領域存在大量專有協議給模糊測試帶來的實際困難。利用協議逆向階段得到的有關協議信息，生成模糊測試階段的測試用例，并對測試目標實施漏洞挖掘。本文利用上述的VxWorks專有協議WDB RPC對嵌入式實時操作系統進行模糊測試。VxWorks是由美國風河（Wind River）開發的一款嵌入式實時操作系統，該操作系統以其良好的可靠性和卓越的實時性被廣泛應用于工業控制領域。

通過本文的專有協議模糊測試方法成功發現，WDB RPC存在整數溢出漏洞，允許攻擊者修改設備內存，存在安全隱患。當攻擊者不斷地進行寫內存操作會造成系統崩潰。圖9為VxWorks操作系統正常的啟動畫面，以及當利用WDB RPC的漏洞寫入大量的內存后，造成系統的崩潰。造成圖中所示現象的原因可能是在顯示的過程中正好出現了系統的崩潰。

圖9 VxWorks系統正常啟動及造成崩潰的畫面

5 總結與展望

本文將自然語言處理的知識拓展到網絡協議領域，采用投票專家算法替代傳統的n-gram算法，使協議關鍵字的提取過程更加精確。另外，利用有損計數算法對投票專家算法進行了改進，節省了對內存資源的占用。本文的方法提升了關鍵字提取精度，使逆向的協議信息更接近于真實值。并且，通過與協議逆向工程技術的結合運用，克服了模糊測試中專有協議缺少協議規范的問題，適用于存在大量專有協議的環境，如工業控制系統，有助于提升工業控制系統的安全性和防護能力。但本文的方法仍存在一些不足，需要在今后的研究中加以完善，如ImproveVE算法處理文本協議時效果十分理想，但在處理純二進制協議時關鍵字的提取精度有待進一步加強。另外，在內存資源占用方面也可以進一步優化。

[1]熊琦，彭勇，伊勝偉，等.工控網絡協議Fuzzing測試技術研究綜述[J].小型微型計算機系統，2015，36（3）：497-502.

[2]Gascon H，Wressnegger C，Yamaguchi F，et al.Pulsar：Stateful black-box fuzzing of proprietary network protocols[M]//Security and Privacy in Communication Networks.[S.l.]：Springer International Publishing，2015.

[3]Bermudez I，Tongaonkar A，Iliofotou M，et al.Towards automatic protocol field inference[J].Computer Communications，2016，84（C）：40-51.

[4]Cui W，Kannan J，Wang H J.Discoverer：Automatic protocol reverse engineering from network traces[C]//Usenix Security Symposium，2007.

[5]Comparetti P M，Wondracek G，Kruegel C，et al.Prospex：Protocol specification extraction[C]//IEEE Symposium on Secuity&Privacy，2009：110-125.

[6]Leita C，Mermoud K，Dacier M.ScriptGen：An automated script generation tool for Honeyd[C]//Computer Security Applications Conference，2005：203-214.

[7]Jamdagni A，Tan Z，He X，et al.Review article：RePIDS：A multitier real-time payload-based intrusion detection system[J].International Journal of Computer&Telecommunications Networking，2013，57（3）：811-824.

[8]Cohen P，Adams N，Heeringa B.Voting experts：An unsupervised algorithm forsegmenting sequences[J].Intelligent Data Analysis，2007，11（6）：607-625.

[9]艾佳.海量數據上基于抽樣的模式挖掘研究[D].哈爾濱：哈爾濱工業大學，2014.

[10]Fang H，Tao T，Zhai C X.A formal study of information retrievalheuristics[C]//InternationalACM SIGIR Conference on Research and Development in Information Retrieval，2004：49-56.

[11]Zhang Y，Xu T，Wang Y，et al.A Markov random field approach to automated protocol signature inference[M]//Security and Privacy in Communication Networks.[S.l.]：Springer International Publishing，2015.

[12]張淑清，李盼，師榮艷，等.復雜系統建模的ε機理論方法及應用研究[J].儀器儀表學報，2014（8）：1758-1765.

[13]孫芳慧.基于Net-Trace的未知協議格式逆向技術研究[D].哈爾濱：哈爾濱工業大學，2015.

[14]Bahr A，Thompson J D，Thierry J C，et al.BAliBASE（Benchmark Alignment dataBASE）：Enhancements for repeats，transmembrane sequences and circular permutations[J].Nucleic Acids Research，2001，29（1）：323-326.

[15]Lang K J.Faster algorithms for finding minimal consistent DFAs[J].oai：CiteSeerX.psu：10.1.1.29.7130，1999.

[16]薩頓，格林，阿米尼.模糊測試：強制發掘安全漏洞的利器[M].北京：電子工業出版社，2013.

[17]梁姝瑞.基于FSM的Zigbee協議模糊測試算法[D].北京：北京郵電大學，2014.

[18]侯瑩，洪征，潘璠，等.基于模型的Fuzzing測試腳本自動化生成[J].計算機科學，2013，40（3）：206-209.

[19]吳禮發，洪征，潘璠.網絡協議逆向分析及應用[M].北京：國防工業出版社，2016.