基于最大似然概率的協議關鍵詞長度確定方法

羅建楨，余順爭，蔡君

?

基于最大似然概率的協議關鍵詞長度確定方法

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

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

提出非齊次左—右型級聯隱馬爾可夫模型，用于應用層網絡協議報文建模，描述狀態之間的轉移規律和各狀態的內部相位變化規律，刻畫報文的字段跳轉規律和字段內的馬爾可夫性質，基于最大似然概率準則確定協議關鍵詞的長度，推斷協議關鍵詞，自動重構協議的報文格式。實驗結果表明，所提出方法能有效地識別出協議關鍵詞和重構協議報文格式。

隱馬爾可夫模型；協議逆向工程；網絡安全；報文格式

1 引言

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

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

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

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

2 相關工作

網絡協議逆向工程[15]的目的是，在不需要協議規范先驗知識的條件下，通過分析協議的流量或協議的可執行代碼，還原協議的報文格式，重構協議的交互狀態機。協議逆向工程技術大致可分為3種：人工分析、網絡流量分析和動態二進制分析。

1) 人工分析

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

2) 網絡流量分析

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

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

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

3) 動態二進制分析

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

然而，未知協議或網絡攻擊的可執行代碼難以獲取，某些加入防逆向技術的程序不能在可控環境下正確運行，諸如此類的限制條件導致動態二進制分析方法只能局限在特定的應用場景中。相比而言，基于數據分組分析的方法只需要捕獲待分析的網絡應用的流量，其實現和部署都要比基于二進制分析的方法容易。因此，本文只關注基于數據分組分析的協議逆向分析方法。

3 模型描述

3.1 應用層網絡協議規范

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

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

3.2 非齊次左—右型級聯隱馬爾可夫模型

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

狀態間的轉移概率還滿足

(2)

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

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

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

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

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

狀態轉移概率矩陣定義為

觀測概率矩陣定義為

(7)

字段的相位轉移概率矩陣定義為

初始狀態的概率分布定義為

(9)

4 基于LRIHMM的報文模型

4.1 報文模型參數估計

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

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

LRIHMM參數的初始化過程如下。

觀測概率的初始化為

相位轉移概率的初始化為

(11)

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

首先，定義前向變量

(13)

前向變量的初始化條件

(15)

(16)

(17)

(18)

進而可得

再定義后向變量

(21)

由于

(22)

其中，

后向變量初始化條件為

(24)

為了更新模型的狀態轉移概率矩陣，定義以下中間變量

(26)

隨機過程在時刻的狀態的概率為

由于

(28)

可推導得以下遞歸式

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

(31)

報文模型的參數更新公式

(33)

(34)

4.2 基于Viterbi算法的字段劃分

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

Viterbi變量的初始化為

(37)

(39)

(40)

Viterbi反推最佳狀態序列的回溯過程。

首先，令=，那么最佳狀態序列的最后一個狀態為

該狀態的長度為

(43)

各狀態對應的字段為

最佳狀態序列上的其他時刻的狀態以及字段可由以下Viterbi 的遞歸過程推導

(46)

(47)

(49)

(51)

對于任意=1,2,…,，當時，為一個關鍵詞字段，其中，為對應的協議關鍵詞。否則，當時，為一個數據字段，是一個非協議關鍵詞的普通字符串。

5 實驗結果

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

5.1 實驗數據

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

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

表1 實驗數據集

5.2 評價標準

真陽性()是指被正確識別的協議關鍵詞數量。

假陽性()是指被錯誤識別的協議關鍵詞數量。

假陰性()是指沒有被識別的協議關鍵詞數量。

本文從準確率、召回率和1值3個指標評價推斷協議關鍵詞的實驗結果，定義如下。

1值()：=。

報文格式的評價指標為報文格式的覆蓋率，定義如下。

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

5.3 結果分析

5.3.1 舉例

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

表2 LRIHMM輸出的HTTP消息格式

表3 Discoverer輸出的HTTP消息格式

表4 PI輸出的HTTP消息格式

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

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

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

5.3.2 準確率與召回率

實驗結果的準確率和召回率分別如表5和表6所示。需要說明的是，在計算準確率和召回率時，真實關鍵詞指的是實驗數據集里出現過的協議關鍵詞，任何在實驗數據集里沒出現過的協議關鍵詞將不作考慮。從實驗結果來看，LRIHMM的準確率和召回率都比 Discoverer和PI系統的要高。

表5 協議關鍵詞的準確率/%

表6 協議關鍵詞的召回率/%

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

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

如圖3所示，LRIHMM的1值比Discoverer和PI系統都要高。這意味著，LRIHMM挖掘協議關鍵詞的結果要比2個對比算法的結果要好得多。

5.3.3 報文格式覆蓋率

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

5.3.4 復雜度分析

綜上所述，LRIHMM學習算法的總復雜度為(2+)。

6 結束語

本文提出一種新型的隱半馬爾可夫模型（非齊次左—右型級聯隱馬爾可夫模型）。傳統的隱半馬爾可夫模型只能刻畫不同狀態之間的轉移規律以及狀態的持續時間長度分布規律。與傳統的隱半馬爾可夫模型不同，本文所提出的LRIHMM模型不但能刻畫狀態之間的轉移規律，還能描述各狀態的內部相位變化規律。

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

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

[1] 趙詠, 姚秋林, 張志斌, 等. TPCAD: 一種文本類多協議特征自動發現方法[J]. 通信學報, 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] 張樹壯, 羅浩, 方濱興. 面向網絡安全的正則表達式匹配技術[J]. 軟件學報, 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] 李偉明, 張愛芳, 劉建財, 等. 網絡協議的自動化模糊測試漏洞挖掘方[J]. 計算機學報, 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] 肖明明, 余順爭. 基于文法推斷的協議逆向工程[J]. 計算機研究與發展, 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] 游翔, 葛衛麗. 飛信協議識別與多元通聯關系提取方法[J]. 現代電子技術, 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]. 計算機應用研究, 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] 琚玉建, 謝紹斌, 張薇. 網絡協議幀切分優化過程研究與仿真[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] 石小龍, 祝躍飛, 劉龍, 等. 加密通信協議的一種逆向分析方法[J]. 計算機應用研究, 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

國家自然科學基金資助項目（No.61571141, No.61272381）；廣東省自然科學基金資助項目（No.2014A030313637, No.2016A030311013）；廣東省教育廳特色創新項目（自然科學）基金資助項目（No.2014KTSCX149）；廣東省高校優秀青年教師基金資助資助項目（YQ2015105）；廣東省應用型科技研發專項基金資助項目（No.2015B010131017）；廣東省科技計劃基金資助項目（No.2014A010101156）；廣東省教育廳省級重大基金資助項目（No.2014KZDXM060）；廣東省普通高校國際合作重大基金資助項目（No.2015KGJHZ021）；廣東省公益研究與能力建設專項基金資助項目（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-），男，廣東陽春人，博士，廣東技術師范學院講師，主要研究方向為協議逆向工程、未來網絡。

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

蔡君（1981-），男，湖南邵陽人，博士，廣東技術師范學院副教授，主要研究方向為流量優化、未來網絡。