基于前導碼挖掘的未知協議幀切分算法

雷 東，王 韜，王曉晗，馬云飛

(軍械工程學院 信息工程系，石家莊 050003)

(*通信作者電子郵箱ldd_lw@163.com)

基于前導碼挖掘的未知協議幀切分算法

雷 東*，王 韜，王曉晗，馬云飛

(軍械工程學院 信息工程系，石家莊 050003)

(*通信作者電子郵箱ldd_lw@163.com)

針對未知協議幀切分技術存在的效率較低的問題，提出基于前導碼挖掘的未知協議幀切分技術。首先介紹前導碼作為標識鏈路幀起始位置的原理，分析候選序列選取問題是現有頻繁序列挖掘方法無法對長度較長的前導碼進行挖掘的原因，并針對該原因以及前導碼挖掘的特點提出從目標比特流中發現候選序列、基于候選序列集合大小變化特征的候選序列選取等改進方法；然后提出未知前導碼長度的判定與挖掘方法,從挖掘的眾多頻繁序列中找出前導碼序列，進而對幀進行切分；最后通過采集的真實數據對所提方法的有效性進行了驗證。實驗結果表明，所提方法能夠快速準確地挖掘未知協議比特流中的前導碼序列，相比現有方法降低了空間與時間復雜度。

前導碼挖掘；頻繁序列；幀切分；未知協議；比特流

0 引言

隨著網絡技術的發展和應用，通信雙方為保證通信內容的安全性，開始使用私有的未知協議進行傳輸，這給網絡的安全運行以及監管帶來挑戰。在電子對抗環境中，監聽者通過截獲目標通信的物理信號，再解調得到協議未知的鏈路層比特流數據。如何對未知協議進行識別與分析，并對其有用信息進行提取，是現有研究的一個重要課題[1]。而未知協議的幀切分技術，即從截獲的比特流中切分出一個個完整的幀，是該研究的首要工作[2]。

通常，在鏈路協議已知的情況下，通信雙方可通過幀同步功能從比特流中提取出幀數據。但是對于監聽方而言，無法準確地得知所捕獲數據的鏈路協議，需要通過數據挖掘等手段，從大量的協議比特流數據中找出標志幀起始的特征序列前導碼，然后對幀進行切分。

目前，已有相關文獻對該技術進行了研究。文獻[3]利用相關濾波區分信息碼和幀同步碼，使用哈達瑪變換(Hadamard Transform)[4]壓縮數據識別出幀長，進一步識別出幀同步碼的起始位；但是該識別方法僅適用于少量數據的處理，對于大量的比特流數據效率不高。大部分的研究多是采用基于AC(Aho-Corasick)算法的頻繁序列挖掘方法，統計獲得比特流數據中頻繁出現的前導碼序列；但由于AC算法的空間復雜度隨著頻繁序列長度的增加呈指數增長，導致其無法直接挖掘長度較長的頻繁序列，金陵[5]通過實驗驗證其方法僅對長度為3～8 bit的頻繁序列有較好的效果。文獻[6-7]中通過拼接短頻繁序列挖掘長頻繁序列，然后識別提取出標志幀起始的特征序列及關聯規則序列，給出可能的切分建議，但大量的短頻繁序列拼接過程會產生組合爆炸問題，且拼接結果的準確性依賴于短頻繁序列的準確性。文獻[8]同樣基于頻繁序列與關聯規則挖掘，提取出數據特征序列，尋找其最小位置差對幀進行定界，定界方法只能估算幀的最小長度，并不能進行準確幀切分。文獻[9]在將未知混合多協議分離為單協議的基礎上，通過研究找到協議的地址信息，最后將單協議的數據幀按地址分為點對點數據幀，為研究數據的獲取打下了基礎。

針對現有研究存在的問題，本文提出一種快速挖掘標識協議數據幀起始的頻繁序列挖掘算法，能夠高效準確地挖掘出未知協議鏈路幀的前導碼，并完成幀的切分。

1 鏈路層幀切分原理

無論是OSI的七層協議體系結構，還是得到廣泛應用的TCP/IP體系結構，數據鏈路層作為其中的底層結構，都發揮著不可替代的作用。除了檢錯糾錯外，其另一主要功能是將比特流拆分成多個離散的幀，為每個幀計算校驗和，并將該校驗和放入幀中一起傳輸[10]。本文研究的主要內容便是模仿數據鏈路層，對捕獲到的未知協議比特流數據進行準確幀切分，以便對協議數據進行更進一步的分析與利用。

1.1 研究對象

目標數據的來源一般捕獲自某一特定環境下、某一段時間內的協議交互數據，這使得其具有以下特點[11]：

1)大量的數據幀前后相接，組成一個長的比特流，因此需要對其進行幀切分；

2)獲得的目標比特流中，鏈路幀格式是相同的，因為同一條鏈路上采用的鏈路協議是固定的。

當具有相同鏈路幀格式的未知協議比特流數據大量匯聚時，尋找其中的規律便成為可能。

1.2 基于前導碼的幀切分原理

為了高效安全地傳輸，許多數據鏈路層協議綜合使用了字節計數法、字節填充的標志字節法以及比特填充的標志比特法[12]等成幀方法。分析現有已知協議，發現多數通信協議都采用相同的分界模式，即用一個定義良好的比特模式來標識一個幀的開始，該比特模式即為前導碼(preamble)。這種定界的模式一般較長，是為了提醒接收方準備接收數據。

前導碼由一段偽隨機序列構成，具有一定的特性，比如連續的比特“1”或“0”，或者交替出現。對經典的以太網和802.11幀格式及其前導碼分析如下：

以太網幀格式如圖1所示，其前導碼由8 Byte組成，其中前7 Byte為同步碼，每個字節均為比特序列“10101010”，最后一個字節為“10101011”，該字節被稱為幀起始定界符(Start Of Frame, SOF)，表示幀頭從其后開始。因此以太網幀的前導碼十六進制表示為：AAAAAAAAAAAAAAAB。

802.11幀格式如圖2所示，其前導碼長度較長，達18 Byte。其中，同步碼長度為16 Byte，由128位的全“1”比特組成，SOF長2 Byte，比特序列為“0000 0101 1100 1111 (0x50CF)”。因此802.11幀的前導碼用十六進制表示為：

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF05CF

通過以上分析可知，大多數鏈路幀都存在一段長度較長的前導碼作為幀的起始單元，以保證幀的同步并進行準確切分，那么如何在協議未知，即前導碼未知的情況下從大量比特流數據中挖掘出未知幀的前導碼是本文研究的重點。

圖1 以太網幀格式

Fig.1 Format of Ethernet frame

圖2 802.11數據幀格式

Fig.2 Format of 802.11 data frame

2 基于前導碼挖掘的幀切分技術

前導碼的挖掘，是基于模式匹配算法的頻繁序列挖掘。首先對模式匹配算法進行簡單介紹。

2.1 模式匹配算法

要從大量協議比特流數據中挖掘出頻繁出現的前導碼序列，基本方法是模式匹配算法，即從目標比特流S中統計出指定模式P的出現頻數與位置的算法，根據查找的候選模式的數量可分為單模式匹配與多模式匹配。

單模式匹配是指在S中只查找一個特定的模式串P的過程，經典的算法有BF(BruceForce)算法[13]、KMP(KnuthMorrisPratt)算法[14]和BM(BoyerMoore)[15]算法等。文獻[16]中詳細分析對比了這幾種算法的效率。由于單模式匹配算法只能查找一個模式串，對于捕獲到的未知協議的比特流數據，鏈路幀的前導碼是未知的，因此該方法并不適用。

多模式匹配則是指在目標比特流S中同時查找候選模式集合P中所有的候選模式串的過程，多模式匹配并不是單模式匹配的簡單重復，其效率更高。多模式匹配算法有AC算法[17]、AC-BM算法[18]、WM(WuandManber)算法[19]等。

由于AC算法在多模式匹配算法研究中的奠基作用，被視為經典算法，多數面向比特流的頻繁模式挖掘方法均基于AC多模式匹配算法進行研究。

2.2 基于AC算法的頻繁序列挖掘

AC算法兼具有限狀態自動機和字典樹的優點，使得其匹配的時間復雜度僅為O(n)。由于其匹配時間不取決于候選序列數量，使其非常適合于候選序列數量巨大的比特流頻繁序列挖掘；而且AC算法可以在一次掃描過程中匹配不同長度的候選序列。

2.2.1 候選序列的選取

假設從目標比特流S中挖掘長度為mbit的候選序列，由于目標序列未知，所以枚舉出所有可能的2m個模式串作為候選序列，并以完全二叉樹的方式表示出來，即字典樹，如圖3所示。圖中是一個長度僅為3bit的候選序列字典樹，每一個從根節點到葉子節點的路徑都表示一個候選模式串，如000、001、111等。

圖3 1～3 bit候選序列字典樹

2.2.2 候選序列頻數統計

建立好字典樹后，便是對目標比特流S進行掃描并統計其中候選序列出現的頻數，即字典樹中的候選序列與比特流S進行匹配的過程。匹配過程從字典樹的根節點開始，遇到葉子節點時，表明從根節點到該葉子節點的路徑所代表的候選序列在S中出現一次，對其進行計數。匹配到葉子節點后，并不是直接返回根節點重新匹配，而是按照計算好的fail表(如圖3中虛線所示)找到一個最佳的匹配位置，這也是AC算法的精髓所在，減少匹配過程中重復匹配的現象，大大提高匹配效率。

現有文獻大多數都是采用該方法進行頻繁序列的挖掘，但是都無法回避其存在的缺陷。

2.3 基于AC算法的頻繁序列挖掘缺陷

2.3.1 無法直接挖掘長頻繁序列

該算法生成的字典樹是一個完全二叉樹，挖掘長度為m的頻繁序列，所需的節點個數為2m+1-1，所需空間著隨著m的增加呈指數增長。當候選序列的長度m較大時，其所需的節點個數是無法想象的。AC算法是一個典型的用空間換取時間的算法。以挖掘以太網幀前導碼為例，前導碼長度為8Byte(64bit)，用字典樹表示出所有的候選序列，需要265-1(約3.69×1019)個節點空間，所需空間極大。

現有方法采用了剪枝的策略以減少字典樹對空間復雜度的需求，即在挖掘統計過程中，根據實時統計的結果，剪掉一些出現頻數明顯較低的節點。但是該方法是在字典樹建立之后，并沒有從源頭上降低字典樹的空間復雜度，如果字典樹因為空間復雜度太大而無法建立，此方法將失效。

2.3.2 短頻繁序列挖掘結果易受用戶數據影響

協議交互比特流數據主要包括協議頭部字段和協議用戶數據部分。頻繁出現的序列是來自協議頭部字段中類似于前導碼的一些固定字段，相比頭部字段中的固定字段，用戶數據部分的比特序列則可視為隨機序列。而大多數協議數據(如TCP、UDP等)中，用戶數據部分占有極大比例。如果候選序列P的長度m較短，那么P很有可能同時出現在頭部字段與用戶數據部分，導致挖掘的結果偏大。

若目標比特流S是一個完全隨機的比特序列，那么其中長度為m的候選序列出現的概率是相同的，均為1/2m。對于用戶數據部分，當m每減小1 bit，候選序列P出現在其中的概率就將增加一倍，對挖掘結果的影響將增大；同理，m每增加1 bit，候選序列P出現在用戶數據部分的概率將減半。

本文要挖掘的鏈路幀前導碼長度都較長，因此在挖掘過程中受到的影響較小。

2.4 基于AC算法的未知幀前導碼挖掘

針對上述分析的現有基于AC算法的頻繁序列挖掘方法無法直接挖掘長頻繁序列的問題，結合前導碼長度較長且長度未知特點，對其進行改進。

2.4.1 候選序列集合的選取

現有方法在構建字典樹時，將所有可能的候選序列枚舉出來，構成一個完全二叉樹。但在實際挖掘的過程中，對于長度較長的候選序列，大部分序列在目標比特流S中出現次數極少，甚至部分序列在S中不出現，浪費了存儲空間，可見這種枚舉的方法過于盲目。

改進1 從目標比特流S中發現候選序列。

候選序列的選取不再盲目枚舉，而是從目標比特流S中選取。對于長頻繁序列的挖掘，采用邊發現邊統計的策略對S進行掃描，每發現一個新的序列，便將其加入字典樹并進行計數，直到S掃描完畢。如此，構建的是一個非完全二叉樹，將大大減少字典樹所需空間。但是該方法使用具有很大的局限性：1)對于短頻繁序列挖掘空間復雜度的減小沒有幫助，反而增加挖掘時間；2)對于較長的頻繁序列挖掘，空間復雜度降低程度不夠，發現的候選序列仍然過多。實驗1將對該方法進行實驗分析。

無論是直接枚舉所有候選序列的方法，還是改進方法1，都可以統計出目標比特流S中存在的所有的候選序列出現的頻數，而本文只需要挖掘前導碼這一項，因此只需要確保候選序列集合中存在前導碼這一項。由于前導碼在目標比特流S中的每個幀頭都會出現，因此，候選序列集合的選取在改進方法1的基礎上，再進行改進。

改進2 基于候選序列集合大小變化特征的候選序列選取。

同樣是從目標比特流S中選取候選序列集合，從S的頭部(或任意位置)開始掃描，由于數據捕獲時機的隨機性，S的頭部不一定從前導碼開始，掃描至少一個幀的最大長度(例如以太網幀的最大傳輸單元(MaximumTransmissionUnit,MTU)為1 500Byte)，以確保選取的候選序列中包含前導碼，才可對其出現頻數進行統計并挖掘。但是，由于目標數據協議未知的特性，幀的最大長度也是未知的。可以根據候選序列選取過程中候選序列集合大小的變化特點快速發現前導碼是否已經被加入候選集合。具體思路如下：

1)從目標比特流S的任意部位開始對其進行掃描，每發現一個序列，將其加入候選序列集合T，并且集合的大小Tn加1。

2)如果掃描發現的新序列在T中已經存在，則集合T的大小Tn保持不變。

3)由于最初集合T為空，因此剛開始階段Tn一直呈線性增長，在該過程中包括前導碼在內的某個幀頭中的頻繁序列也被加入，當在S中發現下一個幀頭時，包括前導碼等頻繁序列已被加入T中，Tn的大小將保持不變。當該幀頭掃描過后，Tn又將繼續增長。整個過程中，Tn隨著對S的掃描，呈階梯形增長，而Tn在階梯形中的拐點就是候選序列集合最合適的大小。實驗2將展示候選序列選取過程中集合大小的變化特征，而實驗3將驗證改進方法2的有效性。

一個好的候選序列集合的選取應能在保證挖掘結果準確性的基礎上，大幅降低算法的空間復雜度，提高挖掘效率。實驗4將對基礎的枚舉方法，以及提出的改進方法1、2進行對比分析。

2.4.2 前導碼長度的判定及挖掘

由于捕獲數據協議未知，其幀前導碼也未知，前導碼長度的判斷就顯得尤為重要，可以使前導碼的挖掘更具有方向性，如已知前導碼的長度為m，則只需要在目標比特流S中直接挖掘長度為m的頻繁序列即可。

方法原理：對于某一長度為m的前導碼K，其在目標比特流S中頻繁出現，其子序列(K中包含的長度小于m的序列)必然頻繁出現[18]，但當長度增加時，其出現的概率與頻數都將大大降低，通過這一變化，可以判定前導碼的長度。

結合上述有效的候選序列結合方法，提出前導碼長度的判別方法：

1)利用改進方法2從S中選取長度為MByte的候選序列，并統計其中出現頻數較多的序列KMi及其頻數NMi，結果記為RM。

2)候選序列長度M增加1 Byte，再次統計其中出現頻數最多的序列及其頻數，記為RM+1，對比RM+1與RM中序列頻數的變化，隨著M的增加，部分序列的頻數在減少，而部分序列的頻數則保持不變。

3)當頻數保持不變的序列在RM+i中是唯一的頻數最高的序列，且在RM+i+1中不再出現，則該序列即為前導碼，M+i即為前導碼的長度；否則跳轉到步驟2繼續挖掘。

在挖掘得到前導碼之后，便可通過前導碼對目標比特流S進行準確的幀切分。實驗5將對該方法進行驗證。

3 實驗結果與分析

3.1 實驗數據

實驗所用數據來自以太網，捕獲某一主機在一段時間內使用同種協議的交互數據包，并經過處理使其轉換成為帶幀頭的連續比特流數據，其中S2數據量足夠大，如表1所示。

表1 實驗所用數據

3.2 從目標比特流S中發現候選序列

實驗1以數據量較小的S1為研究對象，采用從目標比特流S中發現候選序列并構建字典樹的方法，分別查找其中8、16、32以及48bit長度的候選序列集合，統計該過程中掃描長度(在S1中掃描多少比特即可發現所有候選序列)、發現個數(掃描完S1發現的候選序列個數)以及該過程的耗時，結果如表2所示。

表2 從目標比特流中發現候選序列的結果

由表2可知，在發現8、16bit長度較短的候選序列時，未掃描完S1便已發現所有可能的候選序列，并沒有減少候選序列的個數，與枚舉法結果相同，反而會在掃描S1上消耗時間，說明該方法對于短頻繁序列挖掘空間復雜度的減小沒有幫助。在發現32bit長度的候選序列時，掃描完整個S1從中找出約100萬個候選序列，相比枚舉法的232個,減少為原來的約1/4 000。但是，在對48bit的候選序列發現過程中，對S1掃描到約95%位置時，由于構建字典樹深度更大，導致內存空間不足，此時發現約100萬候選序列。

綜上所述，該方法不適用于長度較短的候選序列發現(可直接用枚舉法)，而對于長度較長的候選序列的發現，雖然已經大幅減小了候選序列的數量，但是減少后的候選序列個數依舊太多，無法構建字典樹，仍需新的方法大力削減。

3.3 基于候選序列集合大小變化特征的候選序列選取

實驗2首先驗證候選序列集合大小的變化特征。以比特流S2為研究對象，從其任意位置開始(本實驗從2 000bit位開始)掃描發現長度為16、32、48、64bit的候選序列，統計候選序列集合大小隨掃描比特數增加的變化特點，如圖4所示(圖中四條曲線由下至上分別是16、32、48以及64bit長度的候選序列集合大小)。由圖4可知：掃描初期，隨著掃描比特數的增加，候選序列集合的大小(記作K)線性增長，直到虛線a所標識的位置(895bit)時，K不再變化，掃描到虛線b所標識的位置(1 050bit)之后K又開始增長，在a～b區域內停止增長，說明該區域內的序列在之前0～b的范圍內已經出現并加入到候選序列集合，根據協議數據幀頭中有包含前導碼在內的序列頻繁且連續性出現，說明在0～b范圍內至少有一個包含前導碼的幀頭出現。因此，從2 000bit位開始，0～b范圍內進行候選序列的查找即可發現包含前導碼的幀頭。

對4個不同長度的候選序列發現結果進行對比可知，候選序列長度較短，易受協議用戶數據的影響，導致候選序列集合大小變化特征不明顯，而對于長度較長的32、48以及64bit的候選序列集合，其受協議用戶數據的影響較小，能更加清晰地顯示候選序列集合大小的變化特征。

圖4 候選序列集合大小變化特征

為了驗證上述方法的準確性與高效性，進行實驗3。分別從S2數據的0、2 000以及20 000bit位置出發，按照實驗2所提方法發現長度為64bit的候選序列，所得結果如表3所示。由表3可知，從S2的不同位置開始選取候選序列，選取的候選序列的個數平均值在1 000左右，相比枚舉法以及改進方法1有了顯著減少，很好地控制了構造字典樹所需的存儲空間；并且保證該方法能夠發現至少一個包含前導碼的幀頭。分別使用三個不同起始位置選取的候選序列對S2中的頻繁序列進行挖掘，得到的出現頻數最高的序列相同，均為：AAAAAAAAAAAAAAAB，頻數均為1 000，與已知以太網幀的前導碼一致，保證了該方法的準確性。

表3 改進方法2的候選序列選取

實驗4以比特流S1為研究對象，挖掘其中長度為32bit的候選序列，將三種候選序列選取方法：枚舉法、改進方法1以及改進方法2進行對比，結果如表4所示。由表4可知，枚舉法并不從S中選取候選序列，其枚舉所有的候選序列，當候選序列長度較長時，其候選序列數量太大，構建的字典樹節點空間更大，難以實現；改進方法1與2都是從S中選取，改進方法1掃描完整個S發現其中所有的長度為32bit的候選序列有106個，字典樹節點有1.3×107個，相比枚舉法，分別縮減為原來的約1/4 000和1/600，但是該方法并沒有遺漏任何一個候選序列，可見枚舉法對空間的巨大浪費；改進方法2在改進法1的基礎上繼續改進，僅掃描包含一個前導碼的小范圍，大大縮減了字典樹空間，并且達到挖掘前導碼的要求。

表4 候選序列選取方法對比

3.4 前導碼長度的判定及挖掘

實驗4中為了驗證選取候選序列的準確性，使用了已知條件，即以太網前導碼的長度為64bit，僅挖掘了長度為64bit的頻繁序列，而實際情況是捕獲到的數據協議未知，實驗5以包含1 000個數據幀的S3數據為研究對象，對提出的前導碼長度的判定及挖掘方法進行了驗證。

實驗初始參數候選序列長度M設置為6Byte，即48bit，因為前導碼在設計時為了避免其與協議用戶數據的沖突，其長度設計一般大于幀頭中最長的固定字段的長度，即MAC地址的長度(6Byte)，因此本實驗從6Byte開始挖掘前導碼，挖掘得到的出現頻數最高的序列(十六進制表示)及其頻數如表5所示。由表5可以看出，挖掘得到的頻數較高的頻繁序列主要包括以下三種：全為5的十六進制序列，用“555”表示;全為A的十六進制序列，用“AAA”表示;以及除了最后一位為B其余全為A的十六進制序列，用“AAB”表示。圖5清晰地顯示了候選序列頻數隨長度的變化特點。

表5 不同長度頻繁序列挖掘結果

由圖5可知，隨著候選序列長度的增加，序列“555”與“AAA”的頻數急速下降到0；而序列“AAB”的頻數一直固定為1 000，長度增長為8Byte時，“AAB”成為唯一的頻數最高的序列，且其在9Byte的頻繁序列挖掘結果中消失，可以得出要挖掘的前導碼的長度即為8Byte，前導碼為序列“AAB”即AAAAAAAAAAAAAAAB，與已知以太網幀前導碼相同。此外，前導碼的出現頻數1 000即為比特流中包含的鏈路層幀的個數。

圖5 候選序列頻數隨長度的變化

本文方法通過掃描僅包含一個前導碼的小范圍選取候選序列，大大減小了構建字典樹所需的節點空間，因此可以直接對長度較長的前導碼進行挖掘。與現有的先挖掘短頻繁序列再拼接得到長頻繁序列的方法相比，具有以下優點：1)效率更高。短頻繁序列挖掘兩兩拼接后得到的長頻繁序列不一定頻繁，需要重新掃描一次目標比特流判斷其是否頻繁，而大量的短頻繁序列兩兩拼接，再與拼接而成的長頻繁序列繼續拼接，會產生大量的組合結果，需要對目標比特流進行大量掃描以判斷新得到的長頻繁序列是否頻繁，且該過程前導碼的長度很難判斷。2)準確率更高。本文分析得知短頻繁序列的挖掘結果易受協議用戶數據的影響，導致其挖掘的短頻繁序列準確率不高，那么由短頻繁序列拼接的長頻繁序列也會受其影響，而本文方法直接對長頻繁序列進行挖掘，不存在該問題。

4 結語

本文分析了鏈路層基于前導碼進行幀切分的原理，面對現有的頻繁序列挖掘方法存在的無法對長度較長的頻繁序列進行挖掘的問題，針對前導碼挖掘的特點，提出了高效的挖掘未知協議前導碼的方法，并通過實驗驗證了該方法的準確性與高效性。最后，通過挖掘得到的前導碼完成對未知協議鏈路幀的切分。本文的研究為未知協議的識別與分析打下了良好的基礎，下一步研究重心將放在未知協議格式的推斷方面，通過頻繁序列挖掘以及關聯規則挖掘等方法，推斷出未知協議的大致格式，以及其格式中不同字段所代表的語義，進而對捕獲到的數據內容進行猜測、利用等探索性研究。

)

[1]EDWARDW.信息戰原理與實戰[M].吳漢平,譯.北京:電子工業出版社,2003:1-20.(EDWARDW.InformationWarfare:PrinciplesandOperations[M].WUHP,translated.Beijing:PublishingHouseofElectronicsIndustry, 2003: 1-20.)

[2]LIF,LIT,ZHANGC-R,etal.Lengthidentificationofunknowndataframe[C]//ICCIS2012:ProceedingsoftheEighthInternationalConferenceonComputationalIntelligenceandSecurity.Washington,DC:IEEEComputerSociety, 2012: 674-677.

[3]BAIY,YANGXJ,ZHANGY.Arecognitionmethodofm-sequencesynchronizationcodesusinghigher-orderstatisticalprocessing[J].JournalofElectronicsandInformationTechnology, 2012, 34(1): 33-37.

[4]MATSUZAWAA,HIGUCHIM,JONAHG,etal.Thejudgmentofdocumentsimilaritiesorthogonaltransformationsandimprovementoftheproperty[J].InternationalJournalofCircuits,SystemsandSignalProcessing, 2012, 6(1): 65-74.

[5] 金陵.面向比特流的未知幀頭識別技術研究[D].上海:上海交通大學,2011:29-39.(JINL.Studyonbitstreamorientedunknownframeheadidentification[J].Shanghai:ShanghaiJiaoTongUniversity, 2011: 29-39.)

[6] 王和洲,薛開平,洪佩琳,等.基于頻繁統計和關聯規則的未知鏈路協議比特流切割算法[J].中國科技大學學報,2013,43(7):554-560.(WANGHZ,XUEKP,HONGPL,etal.Anunknownlinkprotocolbitstreamsegmentationalgorithmbasedonfrequentstatisticsandassociationrules[J].JournalofUniversityofScienceandTechnologyofChina, 2013, 43(7): 554-560.)

[7] 溫愛霞.比特流數據未知協議特征發現技術研究[D].成都:電子科技大學,2016:33-45.(WENAX.Thetechnologyresearchoffeatureselectionforunknownprotocolintheformofbitstream[D].Chengdu:UniversityofElectronicScienceandTechnology, 2015: 33-45.)

[8] 琚玉建,謝紹斌,張薇.基于自適應權值的數據報指紋特征識別與發現[J].計算機測量與控制,2014,22(7):2288-2290.(JUYJ,XIESB,ZHANGW.Identificationofdatafingerprintcharacteristicsbasedonself-adaptiveweights[J].ComputerMeasurement&Control, 2014, 22(7): 2288-2290.)

[9] 鄭潔,朱強.未知單協議數據幀的地址分析與研究[J].計算機科學,2015,42(11):184-187.(ZHENGJ,ZHUQ.Analysisandresearchonaddressmessageofunknownsingleprotocoldataframe[J].ComputerScience, 2015, 42(11): 184-187.)[10] RICHARD S W.TCP/IP詳解卷1:協議[M].范建華,胥光輝,張濤,等譯.北京: 機械工業出版社,2008:1-13.(RICHARD S W.TCP/IP Illustrated Volume 1: The Protocols [M].FAN J H, XU G H, ZHANG T, et al, translated.Beijing: China Machine Press, 2008: 1-13.)

[11] 吳艷梅.無線環境下比特流協議幀定位與特征分析[D].成都: 電子科技大學, 2014: 10-11.(WU Y M.The frame location and protocol feature analysis from the bit-stream in the wireless network [D].Chengdu: University of Electronic Science and Technology, 2014: 10-11.)

[12] TANENBAUM A S, WETHERALL D J.計算機網絡[M].嚴偉,潘愛民,譯.5版.北京: 清華大學出版社, 2012: 153-156.(TANENBAUM A S, WETHERALL D J.Computer Networks[M].YAN W, PAN A M, translated.5th ed.Beijing: Tsinghua University Press, 2012: 153-156.)

[13] 鮑震.高速網絡入侵監測系統模式匹配算法的研究與實現[D].長沙:國防科學技術大學,2007:10-20.(BAO Z.Research and implementation of pattern matching algorithms based high-speed network intrusion detection system [D].Changsha: National University of Defense Technology, 2007: 10-20.)

[14] KNUTH D E, MORRIS J H, Jr, PRATT V R.Fast pattern matching in strings [J].SIAM Journal on Computing 1977, 6(2): 323-350.

[15] BOYER R S, MOORE J S.A fast string searching algorithm [J].Communications of the ACM, 1977, 20(10): 762-772.

[16] 王和洲.面向比特流的鏈路協議識別與分析技術[D].合肥:中國科學技術大學,2014:16-17.(WANG H Z.Research on bit-stream oriented link protocol identification and analysis techniques [D].Hefei: University of Science and Technology of China, 2014: 16-17.)

[17] 蔡曉妍,戴冠中,楊黎斌.改進的多模式字符串匹配算法[J].計算機應用,2007,27(6):1415-1418.(CAI X Y, DAI G Z, YANG L B.Improved multiple patterns string matching algorithm [J].Journal of Computer Applications, 2007, 27(6): 1415-1418.)

[18] 萬國根,秦志光.改進的AC-BM字符串匹配算法[J].電子科技大學學報,2006,35(4):531-534.(WAN G G, QIN Z G.Improved AC-BM algorithm for matching multiple strings [J].Journal of University of Electronic Science and Technology of China, 2006, 35(4): 531-534.)

[19] 張鑫,譚建龍,程學旗.一種改進的Wu-Manber多關鍵詞匹配算法[J].計算機應用,2003,23(7):29-32.(ZHANG X,TAN J L,CHEGN X Q.An improved Wu-Manber multiple patterns match algorithm [J].Journal of Computer Applications,2003,23(7):29-32.)

This work is partially supported by the National Natural Science Foundation of China (61272491, 61309021).

LEI Dong, born in 1992, M.S.candidate.His research interest include network protocol identification.

WANG Tao, born in 1964, Ph.D., professor.His research interests include information security, side-channel analysis in cryptography.

WANG Xiaohan, born in 1992, Ph.D.candidate.His research interest include network protocol identification.

MA Yunfei, born in 1992, M.S.candidate.His research interest include cube attack on block ciphers.

Unknown protocol frame segmentation algorithm based on preamble mining

LEI Dong*, WANG Tao, WANG Xiaohan, MA Yunfei

(DepartmentofInformationEngineering,OrdnanceEngineeringCollege,ShijiazhuangHebei050003,China)

Concerning the poor efficiency in unknown protocol frame segmentation, an unknown protocol frame segmentation algorithm based on preamble mining was proposed.Firstly, the principle of the preamble being used as the start of frame was introduced.As the cause that the existing frequent sequence mining algorithm cannot mine long preamble directly, the problems in candidate sequence selection were analyzed.Combining with the characteristics of preamble, two methods for selecting candidate sequences from the target bit streams and selecting candidate sequence based on the variation of the size of candidate sequence set were given.Secondly, an algorithm inferring the length of preamble and mining the preamble was put forward for unknown protocol frame segmentation.Finally, experiments were conducted with real bit streams captured from the Ethernet.The experimental results show that the proposed algorithm can rapidly and accurately mine the preamble sequence in the bit stream of the unknown protocol with lower space and time complexity.

preamble mining; frequent sequence; frame segmentation; unknown protocol; bit stream

2016- 07- 22;

2016- 08- 28。 基金項目:國家自然科學基金資助項目(61272491，61309021)。

雷東(1992—)，男，陜西咸陽人，碩士研究生，主要研究方向：網絡協議識別； 王韜(1964—)，男，河北石家莊人，教授，博士，主要研究方向：信息安全、密碼旁路分析； 王曉晗(1992—)，男，河北衡水人，博士研究生，主要研究方向：網絡協議識別； 馬云飛(1992—)，男，吉林德惠人，碩士研究生，主要研究方向：分組密碼立方攻擊。

1001- 9081(2017)02- 0440- 05

10.11772/j.issn.1001- 9081.2017.02.0440

TN915.04

A