基于狀態機比對的狀態機推斷方案

中國聯合網絡通信有限公司江蘇省分公司 顏 蕾 吳 斌東南大學 信息科學與工程學院 宋宇波

基于狀態機比對的狀態機推斷方案

中國聯合網絡通信有限公司江蘇省分公司 顏 蕾 吳 斌東南大學 信息科學與工程學院 宋宇波

簡要介紹了協議逆向工程，提出協議逆向工程狀態機推斷部分存在的問題（即理想化地認為逆向結果是正確且完整的）。針對發現的問題，結合狀態機推斷的傳統方法，提出狀態機比對的解決方案并給出該解決方案的示例。該方案基于狀態機狀態轉換的可比較性，通過用四元組表示狀態轉換并利用字符串相似度檢測的方法對比狀態機，獲得狀態機的原始信息。

協議逆向； 狀態機； 狀態機比對

1 協議逆向

在對網絡協議進行分析的過程中，需要用到各種技術，其中網絡協議逆向工程是一門經常被用來逆向分析網絡協議流從而獲得協議信息的技術。協議逆向工程[1]是指在不依賴協議描述的情況下，通過對協議實體網絡數據的輸入輸出、系統行為和指令執行流程進行監控和分析，從而提取協議格式以及協議狀態機信息的過程。網絡協議逆向分為兩個部分，它們分別是消息格式提取和狀態機推斷。

消息格式提取是指逆向分析出消息的格式。協議一般是由多個會話組成的分層的結構，每個會話由許多消息序列組成，而消息序列由域組成，域的定義是最小的有一定意義的連續數據序列。大部分協議都包括分隔符、長度域及其目標域、關鍵詞，所以協議格式的推斷一般首先提取這三種域，然后再根據它們分離出消息序列的其他域。

網絡協議逆向分析的另一個部分是狀態機推斷[2]，傳統狀態機推斷方法一般包括三個步驟，即：

1）利用前期采樣到的會話數據，根據會話集構建狀態前綴樹；

2）根據消息序列的特性對不同的狀態機進行標注；

3）使用狀態機化簡算法合并和化簡狀態機。

2 問題描述

在前期狀態機推斷的研究工作中都理想化研究結果，認為利用協議逆向技術推斷出的狀態機是該協議的完整狀態機，但是協議逆向工程推斷出的狀態機有可能不是協議的原始狀態機，因為輸入的會話集合可能沒有完全遍歷協議狀態機的各條路徑，或者在狀態機推斷過程中存在某些偏差使得推斷的狀態機并不是一個完全正確的協議狀態機。以這個不完整的甚至帶有某些錯誤的狀態機為基礎進行后續工作，產生的結果與預期的結果會有偏差。基于以上的原因，協議逆向推斷的狀態機需要進一步處理以獲得完整正確的協議狀態機。

3 狀態機推斷

針對發現的問題，本文提出了狀態機比對的思想，比對推斷出的狀態機與已有狀態機，從而獲得狀態機的完整信息，便

于后續的漏洞挖掘工作的進行。所以本文狀態機推斷的完整流程為：

1）根據輸入的會話集構造狀態機的泛化前綴樹接收器；

2）使用算法確定報文類型之間的順序特征，確定先決條件，利用先決條件標注狀態；

3）利用DFA（有窮自動機）化簡算法化簡合并前綴樹；

4）利用字符串相似度算法比對推斷出的狀態機與現有狀態機，確定逆向協議狀態機的完整信息。

流程圖如圖1所示。

圖1 狀態機推斷完整流程圖

本文忽略狀態機推斷的其他步驟，著重討論狀態機比對部分。狀態機比對是指將推斷出的狀態機與現有協議的狀態機做比對，根據狀態機的相似性確定推斷出的狀態機的所屬協議。考慮到狀態機整體比較的困難性，那么可以將狀態機分作多個元素，取其中的決定性元素作為比對參照物。狀態機是由多個狀態和狀態轉換組成的，狀態機的狀態轉換就可以作為比對參照物。利用一些轉換將狀態轉換化為字符串，這樣就可以使用字符串序列比對的方法來比對各條狀態轉換，從而比對各個狀態機。字符串比對一般都是利用字符串的相似度作為度量，所以本文的狀態機比對以字符串相似度算法為核心。

3.1 最長公共子序列算法

字符串相似度有很多種算法，比如編輯距離算法[3]、最長公共子序列（LCS）算法和貪婪字符串比對算法（GST）等，其中編輯距離算法只能針對順序的匹配，算法的時間復雜度較大，貪婪算法采用了逐字符比較的方法，算法的時間復雜度也較大。另外這里的字符串比對環境更適合使用LCS算法，所以這里選擇LCS算法作為比對算法。

圖2 LCS算法流程圖

LSC算法是在不改變字符順序的情況下將兩個給定的字符串分別刪掉其中的零個或者幾個字符，得到長度最大的相同字符序列的算法。也就是說，給定字符串P、T，計算它們的最長公共子序列X。這種算法有多種解析方式，但是一般使用遞歸的方法，分為自上而下遞歸與自下而上遞歸兩種，這兩種遞歸方式并沒有本質上的差別，本文選用自上而下的遞推法，算法具體的步驟描述如下：

1）獲得兩個字符串的長度L1（S1）和L2（S2），此時如果L1或者L2中任意一個數字為0，則最大公共子串長度為0。

2） L1和L2皆不為零的情況下構造一個矩陣a，其大小為（L1＋1）×（L2＋1），矩陣的第一行與第一列置零，也就是ai, 0＝0，a0, j＝0，其中0≤i≤L1，0≤j≤L2。

3）在計算ai, j時的值已經被計算出來了，利用遞歸式（1）計算矩陣A的每一行每一列的參數，矩陣中最大的一個數值就是最長公共子串的長度，用符號LCS表示，

相似度用δ表示，其計算方法如公式（2）所示。

主要的步驟如流程圖2所示。

例如計算字符串T＝abcdefgh和字符串P＝xyzabpd的相似度，根據遞歸公式構造出的矩陣如圖3所示。

根據圖3可知最大的公共子序列為X＝abd，最大公共子序列長度為3，根據這個長度可以得到兩個字符串的相似度為

3.2 狀態機比對

將協議的狀態轉換表示為一個四元組 〈初始狀態，動作，消息模式，結束狀態〉 ，表示為矢量t＝〈Si, action, M, Sj〉，其中action有兩種：發送（send）和接收（recv），M表示消息的格式，這里為了后續比對的方便，簡略地將消息用分隔符和關鍵詞表示，省略掉消息中的其他域。例如一個消息序列是由兩個關鍵詞和兩個分隔符組成的，那么M為關鍵詞1加分隔符1加關鍵詞2加分隔符2，關鍵詞和分隔符按在消息序列中的順序排列。整個狀態機的狀態轉換就表示為 〈t1，t2，t3… 〉 ，一個協議的狀態機用這種轉換方式構成一個轉換矩陣。因為根據標記訓練集推斷出的狀態機是完整狀態機的一個部分，所以可以從完整狀態機矢量矩陣中尋找推斷出的狀態機矢量，能夠尋找到該狀態機的矩陣就是該狀態機所屬的協議。狀態轉換包括四個參數，這4個參數中有2個可以用來作為比較內容區分轉換（因為狀態的表述不一定完全相同），那就是action和M。

稱協議逆向出來的狀態機為協議P的狀態機，狀態機比對的具體步驟如下：

1）將協議的狀態轉換按照動作分為send組合recv組，先在recv組別中比對；

2）取協議P狀態機中狀態轉換recv組的一個狀態轉換ti的消息序列（包含關鍵詞和分隔符），與已知的協議狀態轉換分在recv組的消息序列做對比，這里使用LCS算法計算相似度，與新推斷狀態機的狀態轉換ti相似度最高的協議記為Pn；

3）取新推斷狀態機的狀態轉換ti+1，與已知的協議狀態轉換分在recv組的消息序列做對比，相似度最高的協議若是與Pn相同，記為Pn，否則記為Pn+1；

4） 重復步驟2）和3），直到協議P的recv組中的狀態轉換比對完畢，然后比對協議P的send組中狀態轉換，重復步驟2）和3）（將其中的recv替換為send）；

5）計算被記錄相同協議符號的個數，最多的就是新推斷協議狀態機所屬協議的狀態機。

例如表1列出的新推斷出的協議狀態轉換序列與現有協議1和協議2的轉換序列，根據LCS算法計算出新推斷協議的各條狀態轉換序列與協議1和協議2的狀態轉換序列相似度中，與序列AabBc相似度最大的是協議1的AabBFc（91%），與序列Cac相似度最大的是協議2的Cac（100%），與序列DdEc相似度最大的是協議1的DdEc（100%），所以新推斷協議與協議1有兩條狀態轉換相似度最大，占新推斷協議狀態轉換的2/3，所以可以確定新推斷的協議狀態機隸屬于協議1的狀態機，也就是說協議1是逆向分析的協議。

表1 三個協議的序列表示

4 結束語

隨著科學技術的發展，網絡協議逆向工程的應用將會越來越廣泛，因為現代技術的發展更加看重自動化的技術。為了更加深入地對協議進行逆向，就需要解決協議逆向工程中的種種問題，狀態機的推斷是協議逆向的一大難點，很多研究都規避此類研究，這無助于協議逆向技術的發展。本文針對狀態機推斷過程中可能出現的理想化問題提出解決方案，其中還存在一些不足，但是相信對未來的協議逆向技術發展會有一些積極的作用。

[1]潘瑤, 吳禮發, 杜有翔, 等. 協議逆向工程研究進展[J]. 計算機應用研究, 2011,28(8): 2 801-2 806.

[2]張釗, 溫巧燕, 唐文. 協議規范挖掘研究綜述[J]. 計算機工程與應用, 2013,49(9): 1-9.

[3]LEVENSHTEIN V I. Binary codes capable of correcting deletions, insertions and reversals[J]. Soviet physics doklady, 1966,10(8): 707-710.