基于最大似然概率的協(xié)議關(guān)鍵詞長度確定方法

羅建楨，余順爭，蔡君

?

基于最大似然概率的協(xié)議關(guān)鍵詞長度確定方法

羅建楨1，余順爭2，蔡君1

(1. 廣東技術(shù)師范學(xué)院電子與信息學(xué)院，廣東廣州 510665；2. 中山大學(xué)電子與信息工程系，廣東廣州 510006 )

提出非齊次左—右型級聯(lián)隱馬爾可夫模型，用于應(yīng)用層網(wǎng)絡(luò)協(xié)議報文建模，描述狀態(tài)之間的轉(zhuǎn)移規(guī)律和各狀態(tài)的內(nèi)部相位變化規(guī)律，刻畫報文的字段跳轉(zhuǎn)規(guī)律和字段內(nèi)的馬爾可夫性質(zhì)，基于最大似然概率準(zhǔn)則確定協(xié)議關(guān)鍵詞的長度，推斷協(xié)議關(guān)鍵詞，自動重構(gòu)協(xié)議的報文格式。實驗結(jié)果表明，所提出方法能有效地識別出協(xié)議關(guān)鍵詞和重構(gòu)協(xié)議報文格式。

隱馬爾可夫模型；協(xié)議逆向工程；網(wǎng)絡(luò)安全；報文格式

1 引言

在網(wǎng)絡(luò)管理和網(wǎng)絡(luò)安全領(lǐng)域中，網(wǎng)絡(luò)協(xié)議規(guī)范顯得尤其重要[1,2]。如網(wǎng)絡(luò)管理軟件需要整合各類協(xié)議的規(guī)范，以便能夠快速高效地識別和解析網(wǎng)絡(luò)中的各類應(yīng)用和協(xié)議；入侵檢測系統(tǒng)(IDS) 和網(wǎng)絡(luò)防火墻等網(wǎng)絡(luò)安全設(shè)備都需要獲取網(wǎng)絡(luò)應(yīng)用的協(xié)議規(guī)范并配置相應(yīng)的安全規(guī)則和安全策略；只有深入了解命令控制協(xié)議(C&C)才能有效檢測并防御僵尸網(wǎng)絡(luò)[3]。除此以外，要實現(xiàn)基于不同通信協(xié)議的多個系統(tǒng)之間的互操作，則必須清楚各協(xié)議的規(guī)范，才能設(shè)計和開發(fā)兼容多系統(tǒng)的平臺[4~6]。協(xié)議規(guī)范還可以與自動化模糊測試結(jié)合，以快速高效地發(fā)現(xiàn)軟件系統(tǒng)中的漏洞[7,8]。

常見的協(xié)議規(guī)范可以從協(xié)議開發(fā)者或IETF[9]發(fā)布的公開文檔中獲得，但是一些私有的網(wǎng)絡(luò)應(yīng)用或協(xié)議的開發(fā)者，往往會出于商業(yè)機(jī)密或者其他原因而拒絕提供有關(guān)的協(xié)議規(guī)范文檔。網(wǎng)絡(luò)攻擊或惡意軟件的制造者也不愿意公開相應(yīng)的協(xié)議規(guī)范。在這種情況下，網(wǎng)絡(luò)管理員或安全專家就必須依賴于協(xié)議逆向工程技術(shù)來重構(gòu)協(xié)議的規(guī)范。傳統(tǒng)的協(xié)議逆向工程主要依靠專家對網(wǎng)絡(luò)流量的人工分析，手工推斷協(xié)議的規(guī)范。人工分析方法的準(zhǔn)確性嚴(yán)重依賴于網(wǎng)絡(luò)專家的知識水平，而且非常耗時和容易出錯。

隨著Internet尤其是移動互聯(lián)網(wǎng)的飛速發(fā)展，新興的網(wǎng)絡(luò)應(yīng)用（如微博、微信以及各種App等）和新型網(wǎng)絡(luò)攻擊不斷呈現(xiàn)，越來越多的網(wǎng)絡(luò)應(yīng)用采用了私有的協(xié)議，以致大約40% 的網(wǎng)絡(luò)流量無法識別[10]。同時，網(wǎng)絡(luò)用戶數(shù)量持續(xù)攀升，網(wǎng)絡(luò)流量呈現(xiàn)多樣化的同時又具有數(shù)據(jù)海量化的特征，基于人工分析的協(xié)議逆向工程方法嚴(yán)重影響了網(wǎng)絡(luò)管理的運(yùn)作效率和妨礙了網(wǎng)絡(luò)安全應(yīng)用的發(fā)展。因此，在大數(shù)據(jù)背景下，研究能適應(yīng)目前網(wǎng)絡(luò)形勢和滿足當(dāng)今網(wǎng)絡(luò)安全需求的自動協(xié)議逆向分析方法成為研究熱點。

本文的主要貢獻(xiàn)是提出一種非齊次的左—右型級聯(lián)隱馬爾可夫模型，用于對應(yīng)用層網(wǎng)絡(luò)協(xié)議報文建模，并基于最大似然概率準(zhǔn)則確定協(xié)議關(guān)鍵詞的長度，最終自動重構(gòu)協(xié)議的報文格式。特別說明，本文只研究基于明文的協(xié)議報文。加解密過程需要增加時間和存儲的額外開銷，在不涉及敏感信息的情況下，網(wǎng)絡(luò)應(yīng)用選擇基于明文的通信協(xié)議，更有利于降低處理時間，提升用戶體驗[11~14]。因此，研究基于明文的協(xié)議報文依然具有必要性。

2 相關(guān)工作

網(wǎng)絡(luò)協(xié)議逆向工程[15]的目的是，在不需要協(xié)議規(guī)范先驗知識的條件下，通過分析協(xié)議的流量或協(xié)議的可執(zhí)行代碼，還原協(xié)議的報文格式，重構(gòu)協(xié)議的交互狀態(tài)機(jī)。協(xié)議逆向工程技術(shù)大致可分為3種：人工分析、網(wǎng)絡(luò)流量分析和動態(tài)二進(jìn)制分析。

1) 人工分析

Samba、Pidgin和Rdesktop等開源項目都是人工逆向分析的典型例子，其準(zhǔn)確性依賴于安全專家的知識水平，而且周期長、易出錯、效率低。

2) 網(wǎng)絡(luò)流量分析

該方法僅分析協(xié)議的網(wǎng)絡(luò)數(shù)據(jù)分組，一直以來備受國內(nèi)外眾多研究者所關(guān)注。PI項目[16]最早提出借助生物信息學(xué)的序列比對算法識別網(wǎng)絡(luò)報文的字段。Cui等[17]基于遞歸聚類算法提取報文的基本單元，還原協(xié)議的報文格式。Wang等[18]根據(jù)報文內(nèi)部的-gram特性識別報文關(guān)鍵字，再運(yùn)用序列比對算法分析協(xié)議的報文格式。Zhang等[19,20]采用基于Trie數(shù)據(jù)結(jié)構(gòu)的專家投票算法提取協(xié)議的特征字。He等[21]逆向分析TLV結(jié)構(gòu)的網(wǎng)絡(luò)數(shù)據(jù)分組，重構(gòu)其格式。Li等[22]和Tao等[23]基于多序列比對算法，提取二進(jìn)制協(xié)議的報文格式。Meng等[24,25]研究未知二進(jìn)制協(xié)議狀態(tài)機(jī)的推斷方法。Gascon等[26]通過逆向分析協(xié)議的交互狀態(tài)機(jī)，實現(xiàn)私有協(xié)議的有狀態(tài)的黑盒子模糊測試。在國內(nèi)，李偉明等[8]提出基于報文長度的報文格式提取方法，并將其應(yīng)用于自動化模糊測試；肖明明等[27]提出基于差錯糾正的文法推斷方法從應(yīng)用層協(xié)議交互過程中的報文序列反推協(xié)議狀態(tài)機(jī)；游翔等[28]提出一種將端口與正則表達(dá)式相結(jié)合的飛信協(xié)議識別方法，基于飛信通信序列關(guān)系從大量混雜的數(shù)據(jù)分組中快速定位飛信業(yè)務(wù)報文，獲取飛信的交互狀態(tài)機(jī)。

近年來，關(guān)于未知協(xié)議棧的幀切分研究也受到學(xué)術(shù)界的關(guān)注。例如，岳旸等[29]提出一種基于聚類的未知協(xié)議二進(jìn)制數(shù)據(jù)幀分離方法；琚玉建等[30]運(yùn)用位置差關(guān)聯(lián)規(guī)則推斷未知協(xié)議數(shù)據(jù)幀的幀頭位置及幀長，實現(xiàn)協(xié)議幀的切分；Li等[31]提出基于頻繁項挖掘的無線協(xié)議幀分離算法。

以上工作與本文的最大區(qū)別在于確定協(xié)議關(guān)鍵詞長度的方法。PI項目是基于LCS準(zhǔn)則來確定關(guān)鍵詞長度的，這種方法具有較明顯的經(jīng)驗性，缺乏嚴(yán)密的理論基礎(chǔ)。Wang等[18]基于-gram的方法將報文分割為相等長度的片段，其準(zhǔn)確率受的取值影響，也難以捕獲報文內(nèi)部的隱藏結(jié)構(gòu)。Discoverer提取的協(xié)議關(guān)鍵詞的長度決定于分隔符的選取，也是不夠嚴(yán)密的。而本文提出基于最大似然概率的方法來確定協(xié)議關(guān)鍵詞長度，具有嚴(yán)密的數(shù)學(xué)基礎(chǔ)，分析結(jié)果也更加合理。另外，Zhang等[19,20]為了減少內(nèi)存占用的空間，在構(gòu)造Trie結(jié)構(gòu)時、刪剪了頻率較小的分支，因而可能導(dǎo)致丟失部分特征字；Zhang等也沒有重構(gòu)協(xié)議的報文格式。

3) 動態(tài)二進(jìn)制分析

動態(tài)二進(jìn)制分析方法的核心思想是將協(xié)議的可執(zhí)行程序置于一個可控制的環(huán)境下運(yùn)行，跟蹤觀察程序處理報文的運(yùn)行時信息（包括指令序列、堆棧和寄存器使用信息等），據(jù)此反推協(xié)議的報文格式，如Polyglot[32]、Dispatcher[33,34]、Autoformat[35]以及Lin等[36]和Cui等[37]的工作。另外，動態(tài)二進(jìn)制分析方法可用于分析加密的安全協(xié)議和惡意程序[38~42]。

然而，未知協(xié)議或網(wǎng)絡(luò)攻擊的可執(zhí)行代碼難以獲取，某些加入防逆向技術(shù)的程序不能在可控環(huán)境下正確運(yùn)行，諸如此類的限制條件導(dǎo)致動態(tài)二進(jìn)制分析方法只能局限在特定的應(yīng)用場景中。相比而言，基于數(shù)據(jù)分組分析的方法只需要捕獲待分析的網(wǎng)絡(luò)應(yīng)用的流量，其實現(xiàn)和部署都要比基于二進(jìn)制分析的方法容易。因此，本文只關(guān)注基于數(shù)據(jù)分組分析的協(xié)議逆向分析方法。

3 模型描述

3.1 應(yīng)用層網(wǎng)絡(luò)協(xié)議規(guī)范

應(yīng)用層協(xié)議的會話（session）是Internet上2臺主機(jī)的進(jìn)程之間互相通信的基本形式。每個會話由它的五元組唯一確定，并由一對方向相反的流（flow）組成。流定義為2個進(jìn)程之間通信時傳輸?shù)淖止?jié)流，也可以認(rèn)為是2個進(jìn)程之間通信時在同一方向上傳遞的報文序列。圖1描述了應(yīng)用層協(xié)議會話的簡單實例，其中，m表示會話中的第個報文，報文序列1,3,5, …和2,4, …分別表示一個會話中2個方向傳輸?shù)?個報文序列。報文是應(yīng)用層協(xié)議進(jìn)行數(shù)據(jù)交換的基本單元。

網(wǎng)絡(luò)協(xié)議規(guī)范包括協(xié)議的報文格式和協(xié)議狀態(tài)機(jī)。報文格式刻畫了協(xié)議所使用的各種報文的組成結(jié)構(gòu)和各組成部分的語義信息，而協(xié)議狀態(tài)機(jī)則描述了會話過程中不同類型的報文之間交互的次序。報文格式可以采用不同的表現(xiàn)形式。在本文中，報文格式定義為字段序列。圖2給出了應(yīng)用層協(xié)議的報文格式，其中，關(guān)鍵詞字段的內(nèi)容（如“GET”、“HTTP/1.1”）為協(xié)議關(guān)鍵詞，數(shù)據(jù)字段的長度和內(nèi)容都是可變的字段。一個關(guān)鍵詞字段后面往往緊跟一個數(shù)據(jù)字段，此時數(shù)據(jù)字段的內(nèi)容通常是其緊跟的協(xié)議關(guān)鍵詞的數(shù)據(jù)值或參數(shù)值。不同類型的報文具有不同的協(xié)議關(guān)鍵詞和字段序列。因此，在提取報文格式時，只要挖掘出報文中的協(xié)議關(guān)鍵詞就可以將報文劃分為由一系列字段組成的序列。協(xié)議關(guān)鍵詞定義為協(xié)議采用的字符常量、協(xié)議的狀態(tài)碼或分隔符等。如在HTTP協(xié)議中，“GET”、“200”、“OK”等都是協(xié)議關(guān)鍵詞。

3.2 非齊次左—右型級聯(lián)隱馬爾可夫模型

隨著時間的推移，報文中的字段依次出現(xiàn)。假定協(xié)議的報文可以用一個隨機(jī)過程來描述，報文從一個字段向另一個字段轉(zhuǎn)移時，對應(yīng)的隨機(jī)過程也從一個隱狀態(tài)向另一個隱狀態(tài)轉(zhuǎn)移(隱狀態(tài)的狀態(tài)空間為{1,2,…,})。字段之間的轉(zhuǎn)移概率決定于隨機(jī)過程中隱狀態(tài)之間的轉(zhuǎn)移概率，即a，其中，,。a表示給定狀態(tài)的條件下，隨機(jī)過程從狀態(tài)向狀態(tài)的轉(zhuǎn)移概率，即

狀態(tài)間的轉(zhuǎn)移概率還滿足

(2)

字段內(nèi)部也會隨著時間的推移而在相位上發(fā)生某些改變，例如關(guān)鍵詞字段從左向右逐個出現(xiàn)關(guān)鍵詞的各個字符，直到一個關(guān)鍵詞的所有字符都按位置先后逐一出現(xiàn)，這時該字段的相位也進(jìn)化完畢; 數(shù)據(jù)字段的相位推進(jìn)則體現(xiàn)在字段長度從小至大逐一增長。因此，這種相位的改變可以用一個具有相位的從左到右型的馬爾可夫(left-to-right HMM)過程[43,44]表示。在從左到右型的馬爾可夫過程中，隨著時間從左向右推移，字段內(nèi)部的相位也從低向高推進(jìn)。

假定字段的最大長度為，那么對每個給定狀態(tài)定義個相位：={1,2,…,}，用(，) 表示隨機(jī)過程處于狀態(tài)的相位，相位代表一個字段的進(jìn)化程度，或者代表字段的馬爾可夫過程歷經(jīng)的程度。在一個狀態(tài)中，隨著時間的推移，狀態(tài)的相位只能從相位1 開始，并逐一向右轉(zhuǎn)移，即由轉(zhuǎn)變到+1，再從+1 轉(zhuǎn)變到+2，或者從某一相位直接向(代表消亡相位)相位轉(zhuǎn)移，因此，只有(,)(,+1)和(,)(,)的轉(zhuǎn)移概率不等于0，而其他相位之間的轉(zhuǎn)移概率定義為0。在給定(，) 的情況下，觀測到字符的概率為

其中，是當(dāng)前觀測值(報文中的一個字節(jié))，觀測值的集合為={0,1,2,…,255}，即一個字節(jié)的所有可能取值。

當(dāng)從某個狀態(tài)(不等于)轉(zhuǎn)移到狀態(tài)時，首先進(jìn)入狀態(tài)的相位1，在相位1時，以的概率觀察到觀測值，接著以相位轉(zhuǎn)移概率轉(zhuǎn)移到相位2，或者轉(zhuǎn)移概率結(jié)束當(dāng)前相位，并以狀態(tài)轉(zhuǎn)移概率轉(zhuǎn)移到下一個狀態(tài)；在相位時，以的概率觀察到觀測值，接著以相位轉(zhuǎn)移概率轉(zhuǎn)移到相位+1，或者以轉(zhuǎn)移概率結(jié)束當(dāng)前相位，然后以狀態(tài)轉(zhuǎn)移概率轉(zhuǎn)移到下一個狀態(tài)，依此類推。

然而，現(xiàn)有的模型不能完整地對應(yīng)用層協(xié)議報文結(jié)構(gòu)進(jìn)行建模。隱馬爾可夫模型只刻畫了隱狀態(tài)之間的狀態(tài)轉(zhuǎn)移規(guī)律，但并沒有刻畫狀態(tài)內(nèi)部的微觀特性。即使是隱半馬爾可夫模型也只是籠統(tǒng)地描述了隱狀態(tài)的持續(xù)時間長度，而沒有真正揭示狀態(tài)內(nèi)部的變化規(guī)律。因此，本文提出非齊次左—右型級聯(lián)隱馬爾可夫模型(LRIHMM, left-to-right inhomogeneous cascaded HMM)，用于對應(yīng)用層協(xié)議的報文結(jié)構(gòu)進(jìn)行建模，刻畫報文的字段間轉(zhuǎn)移規(guī)律和字段內(nèi)部的左右型馬爾可夫性質(zhì)。LRIHMM的模型參數(shù)記為，其中，為模型的狀態(tài)轉(zhuǎn)移概率矩陣，為觀測概率矩陣，為字段的相位轉(zhuǎn)移概率矩陣，為初始狀態(tài)的概率分布。

狀態(tài)轉(zhuǎn)移概率矩陣定義為

觀測概率矩陣定義為

(7)

字段的相位轉(zhuǎn)移概率矩陣定義為

初始狀態(tài)的概率分布定義為

(9)

4 基于LRIHMM的報文模型

4.1 報文模型參數(shù)估計

如果一個字符串是另一個字符串的子串，則記為：。設(shè)為頻繁項集合，那么的最長頻繁項集合定義為: 任意給定，不存在且，使。

本文在訓(xùn)練LRIHMM時，首先基于已有工作提取報文集里的頻繁字符串集[45]，再找出頻繁字符串集里的最長頻繁項，組成最長頻繁項集。令中的每個字符串都與一個狀態(tài)對應(yīng)，如果是狀態(tài)對應(yīng)的一個字符串，則記為，且的所有子字符串都可能是狀態(tài)的觀測值。因此，LRIHMM的關(guān)鍵詞狀態(tài)數(shù)目為。另外定義若干個新的狀態(tài)，代表數(shù)據(jù)狀態(tài)，它的觀測值是觀測序列集中所有可能的字符。關(guān)鍵詞狀態(tài)數(shù)目與數(shù)據(jù)狀態(tài)數(shù)目的總和為。

LRIHMM參數(shù)的初始化過程如下。

觀測概率的初始化為

相位轉(zhuǎn)移概率的初始化為

(11)

本文提出基于前向后向算法思想[46~48]的參數(shù)更新算法用于訓(xùn)練LRIHMM。

首先，定義前向變量

(13)

前向變量的初始化條件

(15)

(16)

(17)

(18)

進(jìn)而可得

再定義后向變量

(21)

由于

(22)

其中，

后向變量初始化條件為

(24)

為了更新模型的狀態(tài)轉(zhuǎn)移概率矩陣，定義以下中間變量

(26)

隨機(jī)過程在時刻的狀態(tài)的概率為

由于

(28)

可推導(dǎo)得以下遞歸式

為了更新模型的相位進(jìn)化概率，定義以下2個變量

(31)

報文模型的參數(shù)更新公式

(33)

(34)

4.2 基于Viterbi算法的字段劃分

通過使用大量報文集對LRIHMM訓(xùn)練得到模型的估計參數(shù)后，便可以基于Viterbi算法推斷具有最大似然概率的字段長度。因此，首先定義Viterbi變量

Viterbi變量的初始化為

(37)

(39)

(40)

Viterbi反推最佳狀態(tài)序列的回溯過程。

首先，令=，那么最佳狀態(tài)序列的最后一個狀態(tài)為

該狀態(tài)的長度為

(43)

各狀態(tài)對應(yīng)的字段為

最佳狀態(tài)序列上的其他時刻的狀態(tài)以及字段可由以下Viterbi 的遞歸過程推導(dǎo)

(46)

(47)

(49)

(51)

對于任意=1,2,…,，當(dāng)時，為一個關(guān)鍵詞字段，其中，為對應(yīng)的協(xié)議關(guān)鍵詞。否則，當(dāng)時，為一個數(shù)據(jù)字段，是一個非協(xié)議關(guān)鍵詞的普通字符串。

5 實驗結(jié)果

本文在配置為2.93 GHz的雙核CPU、2GB內(nèi)存、操作系統(tǒng)為Windows XP的PC上基于C/C++和Matlab實現(xiàn)了所提出的方法。為了評價LRIHMM 的有效性和準(zhǔn)確性，同時還實現(xiàn)了本文所提出的方法與2個經(jīng)典方法（文獻(xiàn)[16]方法和Discoverer方法[17]）做比較。

5.1 實驗數(shù)據(jù)

Discoverer處理長度大于2 048 byte的報文時，采用的方法是截尾，即只保留報文的前2 048 byte。這種處理方法是合理的，因為大多數(shù)報文的報文格式主要體現(xiàn)在報文的頭部，報文頭部之后的部分通常為用戶相關(guān)的數(shù)據(jù)，該部分?jǐn)?shù)據(jù)不但不能促進(jìn)，反而會妨礙報文格式的推斷。為了與Discoverer統(tǒng)一比較標(biāo)準(zhǔn)，以及降低系統(tǒng)處理數(shù)據(jù)的計算時間，LRIHMM也采用了相同的數(shù)據(jù)截尾處理。但是PI項目是保留了原有系統(tǒng)的處理方法，即對數(shù)據(jù)分組沒有作截尾處理。

本文所采用的實驗數(shù)據(jù)采集于真實網(wǎng)絡(luò)環(huán)境(中山大學(xué)信息科學(xué)與技術(shù)學(xué)院的網(wǎng)絡(luò)出口)，如表1所示。所采集的網(wǎng)絡(luò)流量首先經(jīng)過過濾噪音、重構(gòu)會話、重組報文和長報文截斷等處理，得到純凈無噪的報文集。

表1 實驗數(shù)據(jù)集

5.2 評價標(biāo)準(zhǔn)

真陽性()是指被正確識別的協(xié)議關(guān)鍵詞數(shù)量。

假陽性()是指被錯誤識別的協(xié)議關(guān)鍵詞數(shù)量。

假陰性()是指沒有被識別的協(xié)議關(guān)鍵詞數(shù)量。

本文從準(zhǔn)確率、召回率和1值3個指標(biāo)評價推斷協(xié)議關(guān)鍵詞的實驗結(jié)果，定義如下。

1值()：=。

報文格式的評價指標(biāo)為報文格式的覆蓋率，定義如下。

覆蓋率：實驗推斷的報文格式所覆蓋的報文占所有報文總數(shù)的比例。

5.3 結(jié)果分析

5.3.1 舉例

表2~表4分別列舉了3個系統(tǒng)輸出的 HTTP報文格式。LRIHMM推斷的報文格式是以字段序列的形式輸出，每個報文都可劃分為關(guān)鍵詞字段和緊接著關(guān)鍵詞字段的數(shù)據(jù)字段。關(guān)鍵詞字段的字段值為常量，在報文中頻繁出現(xiàn)，可作為報文中字段的分界標(biāo)志，還具備相關(guān)的語義信息，如某些關(guān)鍵詞指示當(dāng)前通信的狀態(tài)。

表2 LRIHMM輸出的HTTP消息格式

表3 Discoverer輸出的HTTP消息格式

表4 PI輸出的HTTP消息格式

Discoverer輸出的報文格式表現(xiàn)為 token 序列。有些 token 的值是常量，有些 token 的值和長度都是可變的。如表3所示，c(t,“GET”)、c(t,“HTTP/1.1”)、c(t,“ocspd”)和c(t,“(x86_64)”) 都是常量token，其中，前2個token 的值是本文定義的協(xié)議關(guān)鍵詞，后2個token 的值是報文中的用戶數(shù)據(jù)的一些參數(shù)值，在報文格式中并無意義，是冗余的token。

PI對輸入的報文執(zhí)行序列比對算法，得到的結(jié)果是多個報文的公共子字符串。由于PI所采用的序列比對算法處理的其他單元是字節(jié)，所以得到的結(jié)果是一個公共字節(jié)序列。表4為輸入的1 000個報文的序列比對結(jié)果，得到HTTP 請求報文的格式。該格式只包含一個協(xié)議關(guān)鍵詞(“GET”)和若干空格，而更多其他協(xié)議關(guān)鍵詞卻沒有出現(xiàn)。

從以上例子可看出，LRIHMM輸出的報文格式與 Discoverer輸出的報文格式相似，但是LRIHMM 輸出的報文格式比Discoverer輸出的報文格式更為簡潔，更為準(zhǔn)確。LRIHMM輸出的報文格式中出現(xiàn)的只有關(guān)鍵詞而沒有與用戶相關(guān)的參數(shù)等冗余數(shù)據(jù)，而Discoverer 輸出的報文格式則會出現(xiàn)一些與真實報文格式無關(guān)的token，例如$“ocspd”$和$“(x86\_64)”$。PI輸出的報文格式過于泛化，使報文格式退化為報文中的一個特征字符串，從而丟失了很多與格式密切相關(guān)的信息。

5.3.2 準(zhǔn)確率與召回率

實驗結(jié)果的準(zhǔn)確率和召回率分別如表5和表6所示。需要說明的是，在計算準(zhǔn)確率和召回率時，真實關(guān)鍵詞指的是實驗數(shù)據(jù)集里出現(xiàn)過的協(xié)議關(guān)鍵詞，任何在實驗數(shù)據(jù)集里沒出現(xiàn)過的協(xié)議關(guān)鍵詞將不作考慮。從實驗結(jié)果來看，LRIHMM的準(zhǔn)確率和召回率都比 Discoverer和PI系統(tǒng)的要高。

表5 協(xié)議關(guān)鍵詞的準(zhǔn)確率/%

表6 協(xié)議關(guān)鍵詞的召回率/%

從表5可看到，Discoverer的準(zhǔn)確率比LRIHMM要低得多。Discoverer遞歸地將token 序列聚類，然后在每一個子類中將相對頻繁的token作為協(xié)議關(guān)鍵詞。一些token在數(shù)據(jù)集里不是頻繁項，但是被聚類后，在子類中就變成了頻繁項，從而將過多的token 判為關(guān)鍵詞，導(dǎo)致假陽性過高，降低準(zhǔn)確率。

在PI系統(tǒng)中，雖然HTTP和FTP的準(zhǔn)確率高達(dá)100%，但是它們的召回率太低，不足5%。因為PI對實驗數(shù)據(jù)本身的結(jié)構(gòu)要求很高，即要求數(shù)據(jù)本身應(yīng)該具有某種對齊性，如ICMP協(xié)議的報文，對應(yīng)字段在不同的報文中出現(xiàn)的位置是一致的。但是對于HTTP和FTP這類的文本型協(xié)議而言，一些關(guān)鍵詞在報文中出現(xiàn)的位置是可變的，因此，PI對這類報文的處理效果較差。另外，還可以觀察到，PI的召回率太低，HTTP、FTP、SMTP 和POP的召回率不足10%，這是因為PI系統(tǒng)挖掘的關(guān)鍵詞個數(shù)太少，一般只有一個或幾個，導(dǎo)致召回率過低。

如圖3所示，LRIHMM的1值比Discoverer和PI系統(tǒng)都要高。這意味著，LRIHMM挖掘協(xié)議關(guān)鍵詞的結(jié)果要比2個對比算法的結(jié)果要好得多。

5.3.3 報文格式覆蓋率

如圖4所示，在LRIHMM中，HTTP、SSDP和BitTorrent的報文格式覆蓋率高達(dá)100%。在Discoverer中，SSDP和BitTorrent的報文格式覆蓋率也為100%，但是其他協(xié)議的報文格式覆蓋率卻比LRIHMM的要低。

5.3.4 復(fù)雜度分析

綜上所述，LRIHMM學(xué)習(xí)算法的總復(fù)雜度為(2+)。

6 結(jié)束語

本文提出一種新型的隱半馬爾可夫模型（非齊次左—右型級聯(lián)隱馬爾可夫模型）。傳統(tǒng)的隱半馬爾可夫模型只能刻畫不同狀態(tài)之間的轉(zhuǎn)移規(guī)律以及狀態(tài)的持續(xù)時間長度分布規(guī)律。與傳統(tǒng)的隱半馬爾可夫模型不同，本文所提出的LRIHMM模型不但能刻畫狀態(tài)之間的轉(zhuǎn)移規(guī)律，還能描述各狀態(tài)的內(nèi)部相位變化規(guī)律。

本文應(yīng)用LRIHMM于協(xié)議逆向工程中，對應(yīng)用層網(wǎng)絡(luò)協(xié)議報文建模，并推斷協(xié)議的報文格式。實驗證明，LRIHMM不但能描繪報文的字段跳轉(zhuǎn)規(guī)律，還能揭示不同字段內(nèi)部的性質(zhì)（即左—右型馬爾可夫性質(zhì)）。基于最大似然概率準(zhǔn)則可以確定協(xié)議關(guān)鍵詞的長度，并推斷協(xié)議關(guān)鍵詞，最終可以重構(gòu)協(xié)議的報文格式。與現(xiàn)有的相關(guān)工作對比可知，本文提出的方法具有很高的準(zhǔn)確率、召回率和覆蓋率，驗證了本文所提出方法的有效性和準(zhǔn)確性。

本文提出的基于最大似然概率的協(xié)議關(guān)鍵詞長度確定方法，具有嚴(yán)密的數(shù)學(xué)基礎(chǔ)，不管是理論分析還是實驗結(jié)果都比前人工作中基于經(jīng)驗的關(guān)鍵詞長度確定方法（例如基于最長公共子序列的方法）要合理得多。另外，與PI項目不同，本文提出的方法對協(xié)議關(guān)鍵詞在報文中出現(xiàn)的順序也沒有特殊的要求，大大提高了報文格式的準(zhǔn)確率。

[1] 趙詠, 姚秋林, 張志斌, 等. TPCAD: 一種文本類多協(xié)議特征自動發(fā)現(xiàn)方法[J]. 通信學(xué)報, 2009, 30(10A): 28-35.

ZHAO Y, YAO Q L, ZHANG Z B, et al. TPCAD: a text-oriented multi-protocol inference approach[J]. Journal on Communications, 2009, 30(10A):28-35.

[2] 張樹壯, 羅浩, 方濱興. 面向網(wǎng)絡(luò)安全的正則表達(dá)式匹配技術(shù)[J]. 軟件學(xué)報, 2011, 22(8): 1838-1854.

ZHANG S Z, LUO H, FANG B X. Regular expressions matching for network security[J]. Journal of Software, 2011, 22(8): 1838-1854.

[3] CABALLERO J, SONG D. Automatic protocol reverse-engineering: message format extraction and field semantics inference[J]. Computer Networks, 2013, 57(2): 451-474.

[4] TRIDGELL A. How samba was written[EB/OL]. Http://www.samba. org/ftp/tridge/misc/french_cafe.txt 2003.

[5] Pidgin[EB/OL]. http://www.pidgin.im/.2014.

[6] Rdesktop: a remote desktop protocol client[EB/OL]. http://www. rdesktop.org/.2014.

[7] KIM H, CHOI Y, LEE D. Efficient file fuzz testing using automated analysis of binary file format[J]. Journal of Systems Architecture, 2011, 57: 259-268.

[8] 李偉明, 張愛芳, 劉建財, 等. 網(wǎng)絡(luò)協(xié)議的自動化模糊測試漏洞挖掘方[J]. 計算機(jī)學(xué)報, 2011, 34(2): 242-255.

LI W M, ZHANG A F, LIU J C, et al. An automatic network protocol fuzz testing and vulnerability discovering method[J]. Chinese Journal of Computers, 2011, 34(2): 242-255.

[9] IETF[EB/OL]. http://www.ietf.org/.2014.

[10] Internet2 netflow statistic [EB/OL]. http://netflow.internet2.edu, 2012.

[11] WEI X, GOMEZ L, NEAMTIU I, et al. ProfileDroid: multi-layer profiling of android applications[C]//18th Annual International Conference on Mobile Computing and Networking. ACM, c2012: 137-148.

[12] DAI S, TONGAONKAR A, WANG X, et al. Networkprofiler: towards automatic fingerprinting of android apps[C]//2013 Proceedings IEEE, INFOCOM. c2013.809-817.

[13] LEE S W, PARK J S, LEE H S, et al. A study on smart-phone traffic analysis[C]// IEEE Network Operations and Management Symposium (APNOMS), c2011: 1-7.

[14] FALAKI H, LYMBEROPOULOS D, MAHAJAN R, et al. A first look at traffic on smartphones[C]//10th ACM SIGCOMM Conference on Internet Measurement. ACM, c2010: 281-287.

[15] NARAYAN J, SHUKLA S K, CLANCY T C. A survey of automatic protocol reverse engineering tools[J]. ACM Computing Surveys, 2016, 48(3):1-26.

[16] BEDDOE M A. Network protocol analysis using bioinformatics algorithms[EB/OL]. http://www.4tphi.net/~awalters/PI/PI.html, 2004.

[17] CUI W, KANNAN J, WANG H. Discoverer: automatic protocol reverse engineering from network traces[C]//16th USENIX Security Symposium on USENIX Security Symposium. Berkeley, CA , USA: USENIX Association, c2007:1-14.

[18] WANG Y, YUN X, SHAFIQ M. A semantics aware approach to automated reverse engineering unknown protocols[C]// 20th IEEE International Conference on Network Protocols (ICNP). c2012: 1-10.

[19] ZHOU Z, ZHANG Z, LEE P. Toward unsupervised protocol feature word extraction[J]. IEEE Journal on Selected Areas in Communications, 2014, 32(10): 1894-1906.

[20] ZHANG Z, ZHANG Z B, LEE P P, et al. ProWord: an unsupervised approach to protocol feature word extraction[C]//2014 Proceedings IEEE INFOCOM. c2014: 1393-1401.

[21] HE L, WEN Q, ZHANG Z. A TLV Structure semantic constraints based method for reverse engineering protocol packet formats[J]. Journal of Networking Technology, 2014, 5(1): 9.

[22] LI T, LIU Y, ZHANG C. A noise-tolerant system for protocol formats extraction from binary data[C]//2014 IEEE Workshop on Advanced Research and Technology in Industry Applications (WARTIA). c2014: 862-865.

[23] TAO S, YU H, LI Q. Bit-oriented format extraction approach for automatic binary protocol reverse engineering[J]. IET Communications, 2016,10(6):709-716.

[24] MENG F, LIU Y, ZHANG C. State reverse method for unknown binary protocol based on state-related fields[J]. Telecommunication Engineering, 2015, 55(4): 372-378.

[25] MENG F, LIU Y, ZHANG C. Inferring protocol state machine for binary communication protocol[C]//2014 IEEE Workshop on in Advanced Research and Technology in Industry Applications (WARTIA). c2014: 870-874.

[26] GASCON H, WRESSNEGGER C, YAMAGUCHI F. Pulsar: stateful black-box fuzzing of proprietary network protocols security and privacy in communication networks[M]//Springer International Publishing, 2015: 330-347.

[27] 肖明明, 余順爭. 基于文法推斷的協(xié)議逆向工程[J]. 計算機(jī)研究與發(fā)展, 2013, 50(10):2044-2058. XIAO M M, YU S Z. Protocol reverse engineering using grammatical inference[J]. Journal of Computer Research & Development, 2013, 50(10):2044-2058.

[28] 游翔, 葛衛(wèi)麗. 飛信協(xié)議識別與多元通聯(lián)關(guān)系提取方法[J]. 現(xiàn)代電子技術(shù), 2014(21): 19-23. YOU X, GE W L. Protocol identification and multi?conversation relationship extraction in Fetion[J]. Modern Electronics Technique, 2014(21): 19-23.

[29] 岳旸, 孟凡治, 張春瑞, 等. 面向二進(jìn)制數(shù)據(jù)幀的聚類系統(tǒng)[J]. 計算機(jī)應(yīng)用研究, 2015(3): 909-916. YUE Y, MENG F Z, ZHANG C R, et al. Cluster system for binary data frame[J]. Application Research of Computers, 2015(3): 909-916.

[30] 琚玉建, 謝紹斌, 張薇. 網(wǎng)絡(luò)協(xié)議幀切分優(yōu)化過程研究與仿真[J]. 計算機(jī)仿真, 2015(1): 318-321. JU Y J, XIE S B, ZHANG W. Research and simulation of optimization process for network protocol frame segmentation[J]. Computer Simulation, 2015(1): 318-321.

[31] LI T, LIU Y, ZHANG C. A novel method for delimiting frames of unknown protocol[C]//2014 IEEE Workshop on Electronics, Computer and Applications. c2014:552-555.

[32] CABALLERO J, YIN H, LIANG Z. Polyglot: automatic extraction of protocol message format using dynamic binary analysis[C]//14th ACM Conference on Computer and Communications Security. New York, NY, USA, ACM, c2007: 317-329.

[33] CABALLERO J, POOSANKAM P, KREIBICH C. Dispatcher: enabling active botnet infiltration using automatic protocol reverse-engineering[C]//16th ACM Conference on Computer and Communications Security. New York, NY, USA, ACM, c2009: 621-634.

[34] CABALLERO J, SONG D. Automatic protocol reverse-engineering: Message format extraction and field semantics inference[J]. Computer Networks, 2013, 57(2): 451-474.

[35] ZHAO L, REN X, LIU M. Collaborative reversing of input formats and program data structures for security applications[J]. China Communications, 2014, 11(9): 135-147.

[36] LIN Z, ZHANG X, XU D. Reverse engineering input syntactic structure from program execution and its applications[J]. IEEE Transactions on Software Engineering, 2010, 36(5): 688-703.

[37] CUI B, WANG F, HAO Y. A taint based approach for automatic reverse engineering of gray-box file formats[J]. Soft Computing. 2015:1-16.

[38] WANG Z, JIANG X, CUI W. ReFormat: automatic reverse engineering of encrypted messages[M]. Berlin: Springer, 2009.

[39] ZHAO R, GU D, LI J. Automatic detection and analysis of encrypted messages in malware[J]. Information Security and Cryptology, 2014, 8567: 101-117.

[40] LIN W, FEI J, ZHU, Y. A method of multiple encryption and sectional encryption protocol reverse engineering[C]//2014 Tenth International Conference on Computational Intelligence and Security (CIS). c2014: 420-424.

[41] LI M, WANG Y, HUANG Z. Reverse analysis of secure communication protocol based on taint analysis[C]//2014 Communications Security Conference, c2014:1-8.

[42] 石小龍, 祝躍飛, 劉龍, 等. 加密通信協(xié)議的一種逆向分析方法[J]. 計算機(jī)應(yīng)用研究, 2015(1): 214-221. SHI X L, ZHU Y F, LIU L, et al. Method of encrypted protocol reverse engineering[J].Application Research of Computers, 2015(01): 214-221.

[43] JELINEK F. Continuous speech recognition by statistical methods[J]. Proceedings of the IEEE, 1976, 64: 532-556.

[44] BAKIS R, Continuous speech recognition via centisecond acoustic states[J]. The Journal of the Acoustical Society of America, 1976, 59(S1): 97.

[45] LUO J Z, YU S Z, Position-based automatic reverse engineering of network protocols[J]. Journal of Network and Computer Applications, 2013, 36(3): 1070-1077.

[46] YU S Z, Hidden semi-Markov models[J]. Artificial Intelligence, 2010, 174(2): 215-243.

[47] RABINER L. A tutorial on hidden Markov models and selected applications in speech recognition[J]. Proceedings of the IEEE, 1989, 77(2): 257-286.

[48] YU S Z, KOBAYASHI H. An efficient forward-backward algorithm for an explicit-duration hidden Markov model[J]. IEEE Signal Processing Letters, 2003. 10(1):11-14.

Method for determining the lengths of protocol keywords based on maximum likelihood probability

LUO Jian-zhen1, YU Shun-zheng2, CAI Jun1

(1. School of Electronic and Information, Guangdong Polytechnic Normal University, Guangzhou 510665, China; 2. School of Information Science and Technology, Sun Yat-Sen University, Guangzhou 510006, China)

A left-to-right inhomogeneous cascaded hidden Markov modelwas proposed and applied to model application protocol messages. The proposed modeldescribed the transition probabilities between states and the evolution rule of phases inside the states,revealed the transition feature ofmessage fields and the left-to-right Markov characteristicsinside the fields. The protocol keywords were inferred by selecting lengths with maximum likelihood probability, and then the message format was recovered. The experimental results demonstrated that the proposed method perform well in protocol keyword extraction and message format recovery.

hidden Markov model, protocol reverse engineering, network security, message format

TP393

A

10.11959/j.issn.1000-436x.2016121

2015-02-10；

2016-05-10

余順爭，syu@mail.sysu.edu.cn

國家自然科學(xué)基金資助項目（No.61571141, No.61272381）；廣東省自然科學(xué)基金資助項目（No.2014A030313637, No.2016A030311013）；廣東省教育廳特色創(chuàng)新項目（自然科學(xué)）基金資助項目（No.2014KTSCX149）；廣東省高校優(yōu)秀青年教師基金資助資助項目（YQ2015105）；廣東省應(yīng)用型科技研發(fā)專項基金資助項目（No.2015B010131017）；廣東省科技計劃基金資助項目（No.2014A010101156）；廣東省教育廳省級重大基金資助項目（No.2014KZDXM060）；廣東省普通高校國際合作重大基金資助項目（No.2015KGJHZ021）；廣東省公益研究與能力建設(shè)專項基金資助項目（No.2014A010103032）

The National Natural Science Foundation of China (No.61571141, No.61272381), The Natural Science Foundation of Guangdong Province(No.2014A030313637, No.2016A030311013), Guangdong Provincial Department of Education Innovation Project (No.2014KTSCX149), The Excellent Young Teachers in Universities in Guangdong Province (No.YQ2015105), Guangdong Provincial Application-Oriented Technical Research and Development Special(No.2015B010131017), Science and Technology Planning Project of Guangdong Province(No.2014A010101156), Science and Technology Major Project of Education Department of Guangdong Province (No.2014KZDXM060), International Scientific and Technological Cooperation Projects of Education Department of Guangdong Province (No.2015KGJHZ021), Science and Technology Project of Guangdong Province (No.2014A010103032)

羅建楨（1984-），男，廣東陽春人，博士，廣東技術(shù)師范學(xué)院講師，主要研究方向為協(xié)議逆向工程、未來網(wǎng)絡(luò)。

余順爭（1958-），男，江西南昌人，博士，中山大學(xué)教授、博士生導(dǎo)師，主要研究方向為信息安全、信號處理、無線網(wǎng)絡(luò)。

蔡君（1981-），男，湖南邵陽人，博士，廣東技術(shù)師范學(xué)院副教授，主要研究方向為流量優(yōu)化、未來網(wǎng)絡(luò)。