中國(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ì)
在對(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ī)。
在前期狀態(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ī)。
針對(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é)議的序列表示
隨著科學(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.