中國(guó)聯(lián)合網(wǎng)絡(luò)通信有限公司江蘇省分公司 顏 蕾 吳 斌東南大學(xué) 信息科學(xué)與工程學(xué)院 宋宇波

基于狀態(tài)機(jī)比對(duì)的狀態(tài)機(jī)推斷方案

中國(guó)聯(lián)合網(wǎng)絡(luò)通信有限公司江蘇省分公司 顏 蕾 吳 斌東南大學(xué) 信息科學(xué)與工程學(xué)院 宋宇波

簡(jiǎn)要介紹了協(xié)議逆向工程，提出協(xié)議逆向工程狀態(tài)機(jī)推斷部分存在的問(wèn)題（即理想化地認(rèn)為逆向結(jié)果是正確且完整的）。針對(duì)發(fā)現(xiàn)的問(wèn)題，結(jié)合狀態(tài)機(jī)推斷的傳統(tǒng)方法，提出狀態(tài)機(jī)比對(duì)的解決方案并給出該解決方案的示例。該方案基于狀態(tài)機(jī)狀態(tài)轉(zhuǎn)換的可比較性，通過(guò)用四元組表示狀態(tài)轉(zhuǎn)換并利用字符串相似度檢測(cè)的方法對(duì)比狀態(tài)機(jī)，獲得狀態(tài)機(jī)的原始信息。

協(xié)議逆向； 狀態(tài)機(jī)； 狀態(tài)機(jī)比對(duì)

1 協(xié)議逆向

在對(duì)網(wǎng)絡(luò)協(xié)議進(jìn)行分析的過(guò)程中，需要用到各種技術(shù)，其中網(wǎng)絡(luò)協(xié)議逆向工程是一門(mén)經(jīng)常被用來(lái)逆向分析網(wǎng)絡(luò)協(xié)議流從而獲得協(xié)議信息的技術(shù)。協(xié)議逆向工程[1]是指在不依賴(lài)協(xié)議描述的情況下，通過(guò)對(duì)協(xié)議實(shí)體網(wǎng)絡(luò)數(shù)據(jù)的輸入輸出、系統(tǒng)行為和指令執(zhí)行流程進(jìn)行監(jiān)控和分析，從而提取協(xié)議格式以及協(xié)議狀態(tài)機(jī)信息的過(guò)程。網(wǎng)絡(luò)協(xié)議逆向分為兩個(gè)部分，它們分別是消息格式提取和狀態(tài)機(jī)推斷。

消息格式提取是指逆向分析出消息的格式。協(xié)議一般是由多個(gè)會(huì)話(huà)組成的分層的結(jié)構(gòu)，每個(gè)會(huì)話(huà)由許多消息序列組成，而消息序列由域組成，域的定義是最小的有一定意義的連續(xù)數(shù)據(jù)序列。大部分協(xié)議都包括分隔符、長(zhǎng)度域及其目標(biāo)域、關(guān)鍵詞，所以協(xié)議格式的推斷一般首先提取這三種域，然后再根據(jù)它們分離出消息序列的其他域。

網(wǎng)絡(luò)協(xié)議逆向分析的另一個(gè)部分是狀態(tài)機(jī)推斷[2]，傳統(tǒng)狀態(tài)機(jī)推斷方法一般包括三個(gè)步驟，即：

1）利用前期采樣到的會(huì)話(huà)數(shù)據(jù)，根據(jù)會(huì)話(huà)集構(gòu)建狀態(tài)前綴樹(shù)；

2）根據(jù)消息序列的特性對(duì)不同的狀態(tài)機(jī)進(jìn)行標(biāo)注；

3）使用狀態(tài)機(jī)化簡(jiǎn)算法合并和化簡(jiǎn)狀態(tài)機(jī)。

2 問(wèn)題描述

在前期狀態(tài)機(jī)推斷的研究工作中都理想化研究結(jié)果，認(rèn)為利用協(xié)議逆向技術(shù)推斷出的狀態(tài)機(jī)是該協(xié)議的完整狀態(tài)機(jī)，但是協(xié)議逆向工程推斷出的狀態(tài)機(jī)有可能不是協(xié)議的原始狀態(tài)機(jī)，因?yàn)檩斎氲臅?huì)話(huà)集合可能沒(méi)有完全遍歷協(xié)議狀態(tài)機(jī)的各條路徑，或者在狀態(tài)機(jī)推斷過(guò)程中存在某些偏差使得推斷的狀態(tài)機(jī)并不是一個(gè)完全正確的協(xié)議狀態(tài)機(jī)。以這個(gè)不完整的甚至帶有某些錯(cuò)誤的狀態(tài)機(jī)為基礎(chǔ)進(jìn)行后續(xù)工作，產(chǎn)生的結(jié)果與預(yù)期的結(jié)果會(huì)有偏差。基于以上的原因，協(xié)議逆向推斷的狀態(tài)機(jī)需要進(jìn)一步處理以獲得完整正確的協(xié)議狀態(tài)機(jī)。

3 狀態(tài)機(jī)推斷

針對(duì)發(fā)現(xiàn)的問(wèn)題，本文提出了狀態(tài)機(jī)比對(duì)的思想，比對(duì)推斷出的狀態(tài)機(jī)與已有狀態(tài)機(jī)，從而獲得狀態(tài)機(jī)的完整信息，便

于后續(xù)的漏洞挖掘工作的進(jìn)行。所以本文狀態(tài)機(jī)推斷的完整流程為：

1）根據(jù)輸入的會(huì)話(huà)集構(gòu)造狀態(tài)機(jī)的泛化前綴樹(shù)接收器；

2）使用算法確定報(bào)文類(lèi)型之間的順序特征，確定先決條件，利用先決條件標(biāo)注狀態(tài)；

3）利用DFA（有窮自動(dòng)機(jī)）化簡(jiǎn)算法化簡(jiǎn)合并前綴樹(shù)；

4）利用字符串相似度算法比對(duì)推斷出的狀態(tài)機(jī)與現(xiàn)有狀態(tài)機(jī)，確定逆向協(xié)議狀態(tài)機(jī)的完整信息。

流程圖如圖1所示。

圖1 狀態(tài)機(jī)推斷完整流程圖

本文忽略狀態(tài)機(jī)推斷的其他步驟，著重討論狀態(tài)機(jī)比對(duì)部分。狀態(tài)機(jī)比對(duì)是指將推斷出的狀態(tài)機(jī)與現(xiàn)有協(xié)議的狀態(tài)機(jī)做比對(duì)，根據(jù)狀態(tài)機(jī)的相似性確定推斷出的狀態(tài)機(jī)的所屬協(xié)議?？紤]到狀態(tài)機(jī)整體比較的困難性，那么可以將狀態(tài)機(jī)分作多個(gè)元素，取其中的決定性元素作為比對(duì)參照物。狀態(tài)機(jī)是由多個(gè)狀態(tài)和狀態(tài)轉(zhuǎn)換組成的，狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換就可以作為比對(duì)參照物。利用一些轉(zhuǎn)換將狀態(tài)轉(zhuǎn)換化為字符串，這樣就可以使用字符串序列比對(duì)的方法來(lái)比對(duì)各條狀態(tài)轉(zhuǎn)換，從而比對(duì)各個(gè)狀態(tài)機(jī)。字符串比對(duì)一般都是利用字符串的相似度作為度量，所以本文的狀態(tài)機(jī)比對(duì)以字符串相似度算法為核心。

3.1 最長(zhǎng)公共子序列算法

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

圖2 LCS算法流程圖

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

1）獲得兩個(gè)字符串的長(zhǎng)度L1（S1）和L2（S2），此時(shí)如果L1或者L2中任意一個(gè)數(shù)字為0，則最大公共子串長(zhǎng)度為0。

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

3）在計(jì)算ai, j時(shí)的值已經(jīng)被計(jì)算出來(lái)了，利用遞歸式（1）計(jì)算矩陣A的每一行每一列的參數(shù)，矩陣中最大的一個(gè)數(shù)值就是最長(zhǎng)公共子串的長(zhǎng)度，用符號(hào)LCS表示，

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

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

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

根據(jù)圖3可知最大的公共子序列為X＝abd，最大公共子序列長(zhǎng)度為3，根據(jù)這個(gè)長(zhǎng)度可以得到兩個(gè)字符串的相似度為

3.2 狀態(tài)機(jī)比對(duì)

將協(xié)議的狀態(tài)轉(zhuǎn)換表示為一個(gè)四元組 〈初始狀態(tài)，動(dòng)作，消息模式，結(jié)束狀態(tài)〉 ，表示為矢量t＝〈Si, action, M, Sj〉，其中action有兩種：發(fā)送（send）和接收（recv），M表示消息的格式，這里為了后續(xù)比對(duì)的方便，簡(jiǎn)略地將消息用分隔符和關(guān)鍵詞表示，省略掉消息中的其他域。例如一個(gè)消息序列是由兩個(gè)關(guān)鍵詞和兩個(gè)分隔符組成的，那么M為關(guān)鍵詞1加分隔符1加關(guān)鍵詞2加分隔符2，關(guān)鍵詞和分隔符按在消息序列中的順序排列。整個(gè)狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換就表示為 〈t1，t2，t3… 〉 ，一個(gè)協(xié)議的狀態(tài)機(jī)用這種轉(zhuǎn)換方式構(gòu)成一個(gè)轉(zhuǎn)換矩陣。因?yàn)楦鶕?jù)標(biāo)記訓(xùn)練集推斷出的狀態(tài)機(jī)是完整狀態(tài)機(jī)的一個(gè)部分，所以可以從完整狀態(tài)機(jī)矢量矩陣中尋找推斷出的狀態(tài)機(jī)矢量，能夠?qū)ふ业皆摖顟B(tài)機(jī)的矩陣就是該狀態(tài)機(jī)所屬的協(xié)議。狀態(tài)轉(zhuǎn)換包括四個(gè)參數(shù)，這4個(gè)參數(shù)中有2個(gè)可以用來(lái)作為比較內(nèi)容區(qū)分轉(zhuǎn)換（因?yàn)闋顟B(tài)的表述不一定完全相同），那就是action和M。

稱(chēng)協(xié)議逆向出來(lái)的狀態(tài)機(jī)為協(xié)議P的狀態(tài)機(jī)，狀態(tài)機(jī)比對(duì)的具體步驟如下：

1）將協(xié)議的狀態(tài)轉(zhuǎn)換按照動(dòng)作分為send組合recv組，先在recv組別中比對(duì)；

2）取協(xié)議P狀態(tài)機(jī)中狀態(tài)轉(zhuǎn)換recv組的一個(gè)狀態(tài)轉(zhuǎn)換ti的消息序列（包含關(guān)鍵詞和分隔符），與已知的協(xié)議狀態(tài)轉(zhuǎn)換分在recv組的消息序列做對(duì)比，這里使用LCS算法計(jì)算相似度，與新推斷狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換ti相似度最高的協(xié)議記為Pn；

3）取新推斷狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換ti+1，與已知的協(xié)議狀態(tài)轉(zhuǎn)換分在recv組的消息序列做對(duì)比，相似度最高的協(xié)議若是與Pn相同，記為Pn，否則記為Pn+1；

4） 重復(fù)步驟2）和3），直到協(xié)議P的recv組中的狀態(tài)轉(zhuǎn)換比對(duì)完畢，然后比對(duì)協(xié)議P的send組中狀態(tài)轉(zhuǎn)換，重復(fù)步驟2）和3）（將其中的recv替換為send）；

5）計(jì)算被記錄相同協(xié)議符號(hào)的個(gè)數(shù)，最多的就是新推斷協(xié)議狀態(tài)機(jī)所屬協(xié)議的狀態(tài)機(jī)。

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

表1 三個(gè)協(xié)議的序列表示

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

隨著科學(xué)技術(shù)的發(fā)展，網(wǎng)絡(luò)協(xié)議逆向工程的應(yīng)用將會(huì)越來(lái)越廣泛，因?yàn)楝F(xiàn)代技術(shù)的發(fā)展更加看重自動(dòng)化的技術(shù)。為了更加深入地對(duì)協(xié)議進(jìn)行逆向，就需要解決協(xié)議逆向工程中的種種問(wèn)題，狀態(tài)機(jī)的推斷是協(xié)議逆向的一大難點(diǎn)，很多研究都規(guī)避此類(lèi)研究，這無(wú)助于協(xié)議逆向技術(shù)的發(fā)展。本文針對(duì)狀態(tài)機(jī)推斷過(guò)程中可能出現(xiàn)的理想化問(wèn)題提出解決方案，其中還存在一些不足，但是相信對(duì)未來(lái)的協(xié)議逆向技術(shù)發(fā)展會(huì)有一些積極的作用。

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

[2]張釗, 溫巧燕, 唐文. 協(xié)議規(guī)范挖掘研究綜述[J]. 計(jì)算機(jī)工程與應(yīng)用, 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.