羅建楨，余順爭(zhēng)，蔡君

?

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

羅建楨1，余順爭(zhēng)2，蔡君1

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

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

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

1 引言

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

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

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

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

2 相關(guān)工作

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

1) 人工分析

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

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

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

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

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

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

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

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

3 模型描述

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

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

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

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

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

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

(2)

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

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

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

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

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

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

觀測(cè)概率矩陣定義為

(7)

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

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

(9)

4 基于LRIHMM的報(bào)文模型

4.1 報(bào)文模型參數(shù)估計(jì)

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

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

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

觀測(cè)概率的初始化為

相位轉(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ī)過(guò)程在時(shí)刻的狀態(tài)的概率為

由于

(28)

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

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

(31)

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

(33)

(34)

4.2 基于Viterbi算法的字段劃分

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

Viterbi變量的初始化為

(37)

(39)

(40)

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

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

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

(43)

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

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

(46)

(47)

(49)

(51)

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

5 實(shí)驗(yàn)結(jié)果

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

5.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)集

5.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

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

1值()：=。

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

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

5.3 結(jié)果分析

5.3.1 舉例

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

表2 LRIHMM輸出的HTTP消息格式

表3 Discoverer輸出的HTTP消息格式

表4 PI輸出的HTTP消息格式

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

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

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

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

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

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

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

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

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

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

5.3.3 報(bào)文格式覆蓋率

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

5.3.4 復(fù)雜度分析

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

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

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

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

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

[1] 趙詠, 姚秋林, 張志斌, 等. TPCAD: 一種文本類多協(xié)議特征自動(dòng)發(fā)現(xiàn)方法[J]. 通信學(xué)報(bào), 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] 張樹(shù)壯, 羅浩, 方濱興. 面向網(wǎng)絡(luò)安全的正則表達(dá)式匹配技術(shù)[J]. 軟件學(xué)報(bào), 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] 李偉明, 張愛(ài)芳, 劉建財(cái), 等. 網(wǎng)絡(luò)協(xié)議的自動(dòng)化模糊測(cè)試漏洞挖掘方[J]. 計(jì)算機(jī)學(xué)報(bào), 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] 肖明明, 余順爭(zhēng). 基于文法推斷的協(xié)議逆向工程[J]. 計(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é)議識(shí)別與多元通聯(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ì)算機(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)化過(guò)程研究與仿真[J]. 計(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ì)算機(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

余順爭(zhēng)，syu@mail.sysu.edu.cn

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61571141, No.61272381）；廣東省自然科學(xué)基金資助項(xiàng)目（No.2014A030313637, No.2016A030311013）；廣東省教育廳特色創(chuàng)新項(xiàng)目（自然科學(xué)）基金資助項(xiàng)目（No.2014KTSCX149）；廣東省高校優(yōu)秀青年教師基金資助資助項(xiàng)目（YQ2015105）；廣東省應(yīng)用型科技研發(fā)專項(xiàng)基金資助項(xiàng)目（No.2015B010131017）；廣東省科技計(jì)劃基金資助項(xiàng)目（No.2014A010101156）；廣東省教育廳省級(jí)重大基金資助項(xiàng)目（No.2014KZDXM060）；廣東省普通高校國(guó)際合作重大基金資助項(xiàng)目（No.2015KGJHZ021）；廣東省公益研究與能力建設(shè)專項(xiàng)基金資助項(xiàng)目（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-），男，廣東陽(yáng)春人，博士，廣東技術(shù)師范學(xué)院講師，主要研究方向?yàn)閰f(xié)議逆向工程、未來(lái)網(wǎng)絡(luò)。

余順爭(zhēng)（1958-），男，江西南昌人，博士，中山大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樾畔踩?、信?hào)處理、無(wú)線網(wǎng)絡(luò)。

蔡君（1981-），男，湖南邵陽(yáng)人，博士，廣東技術(shù)師范學(xué)院副教授，主要研究方向?yàn)榱髁績(jī)?yōu)化、未來(lái)網(wǎng)絡(luò)。