基于前導(dǎo)碼挖掘的未知協(xié)議幀切分算法

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

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

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

基于前導(dǎo)碼挖掘的未知協(xié)議幀切分算法

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

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

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

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

前導(dǎo)碼挖掘；頻繁序列；幀切分；未知協(xié)議；比特流

0 引言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展和應(yīng)用，通信雙方為保證通信內(nèi)容的安全性，開始使用私有的未知協(xié)議進(jìn)行傳輸，這給網(wǎng)絡(luò)的安全運(yùn)行以及監(jiān)管帶來挑戰(zhàn)。在電子對抗環(huán)境中，監(jiān)聽者通過截獲目標(biāo)通信的物理信號(hào)，再解調(diào)得到協(xié)議未知的鏈路層比特流數(shù)據(jù)。如何對未知協(xié)議進(jìn)行識(shí)別與分析，并對其有用信息進(jìn)行提取，是現(xiàn)有研究的一個(gè)重要課題[1]。而未知協(xié)議的幀切分技術(shù)，即從截獲的比特流中切分出一個(gè)個(gè)完整的幀，是該研究的首要工作[2]。

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

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

針對現(xiàn)有研究存在的問題，本文提出一種快速挖掘標(biāo)識(shí)協(xié)議數(shù)據(jù)幀起始的頻繁序列挖掘算法，能夠高效準(zhǔn)確地挖掘出未知協(xié)議鏈路幀的前導(dǎo)碼，并完成幀的切分。

1 鏈路層幀切分原理

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

1.1 研究對象

目標(biāo)數(shù)據(jù)的來源一般捕獲自某一特定環(huán)境下、某一段時(shí)間內(nèi)的協(xié)議交互數(shù)據(jù)，這使得其具有以下特點(diǎn)[11]：

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

2)獲得的目標(biāo)比特流中，鏈路幀格式是相同的，因?yàn)橥粭l鏈路上采用的鏈路協(xié)議是固定的。

當(dāng)具有相同鏈路幀格式的未知協(xié)議比特流數(shù)據(jù)大量匯聚時(shí)，尋找其中的規(guī)律便成為可能。

1.2 基于前導(dǎo)碼的幀切分原理

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

前導(dǎo)碼由一段偽隨機(jī)序列構(gòu)成，具有一定的特性，比如連續(xù)的比特“1”或“0”，或者交替出現(xiàn)。對經(jīng)典的以太網(wǎng)和802.11幀格式及其前導(dǎo)碼分析如下：

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

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

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF05CF

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

圖1 以太網(wǎng)幀格式

Fig.1 Format of Ethernet frame

圖2 802.11數(shù)據(jù)幀格式

Fig.2 Format of 802.11 data frame

2 基于前導(dǎo)碼挖掘的幀切分技術(shù)

前導(dǎo)碼的挖掘，是基于模式匹配算法的頻繁序列挖掘。首先對模式匹配算法進(jìn)行簡單介紹。

2.1 模式匹配算法

要從大量協(xié)議比特流數(shù)據(jù)中挖掘出頻繁出現(xiàn)的前導(dǎo)碼序列，基本方法是模式匹配算法，即從目標(biāo)比特流S中統(tǒng)計(jì)出指定模式P的出現(xiàn)頻數(shù)與位置的算法，根據(jù)查找的候選模式的數(shù)量可分為單模式匹配與多模式匹配。

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

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

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

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

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

2.2.1 候選序列的選取

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

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

2.2.2 候選序列頻數(shù)統(tǒng)計(jì)

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

現(xiàn)有文獻(xiàn)大多數(shù)都是采用該方法進(jìn)行頻繁序列的挖掘，但是都無法回避其存在的缺陷。

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

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

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

現(xiàn)有方法采用了剪枝的策略以減少字典樹對空間復(fù)雜度的需求，即在挖掘統(tǒng)計(jì)過程中，根據(jù)實(shí)時(shí)統(tǒng)計(jì)的結(jié)果，剪掉一些出現(xiàn)頻數(shù)明顯較低的節(jié)點(diǎn)。但是該方法是在字典樹建立之后，并沒有從源頭上降低字典樹的空間復(fù)雜度，如果字典樹因?yàn)榭臻g復(fù)雜度太大而無法建立，此方法將失效。

2.3.2 短頻繁序列挖掘結(jié)果易受用戶數(shù)據(jù)影響

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

若目標(biāo)比特流S是一個(gè)完全隨機(jī)的比特序列，那么其中長度為m的候選序列出現(xiàn)的概率是相同的，均為1/2m。對于用戶數(shù)據(jù)部分，當(dāng)m每減小1 bit，候選序列P出現(xiàn)在其中的概率就將增加一倍，對挖掘結(jié)果的影響將增大；同理，m每增加1 bit，候選序列P出現(xiàn)在用戶數(shù)據(jù)部分的概率將減半。

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

2.4 基于AC算法的未知幀前導(dǎo)碼挖掘

針對上述分析的現(xiàn)有基于AC算法的頻繁序列挖掘方法無法直接挖掘長頻繁序列的問題，結(jié)合前導(dǎo)碼長度較長且長度未知特點(diǎn)，對其進(jìn)行改進(jìn)。

2.4.1 候選序列集合的選取

現(xiàn)有方法在構(gòu)建字典樹時(shí)，將所有可能的候選序列枚舉出來，構(gòu)成一個(gè)完全二叉樹。但在實(shí)際挖掘的過程中，對于長度較長的候選序列，大部分序列在目標(biāo)比特流S中出現(xiàn)次數(shù)極少，甚至部分序列在S中不出現(xiàn)，浪費(fèi)了存儲(chǔ)空間，可見這種枚舉的方法過于盲目。

改進(jìn)1 從目標(biāo)比特流S中發(fā)現(xiàn)候選序列。

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

無論是直接枚舉所有候選序列的方法，還是改進(jìn)方法1，都可以統(tǒng)計(jì)出目標(biāo)比特流S中存在的所有的候選序列出現(xiàn)的頻數(shù)，而本文只需要挖掘前導(dǎo)碼這一項(xiàng)，因此只需要確保候選序列集合中存在前導(dǎo)碼這一項(xiàng)。由于前導(dǎo)碼在目標(biāo)比特流S中的每個(gè)幀頭都會(huì)出現(xiàn)，因此，候選序列集合的選取在改進(jìn)方法1的基礎(chǔ)上，再進(jìn)行改進(jìn)。

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

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

1)從目標(biāo)比特流S的任意部位開始對其進(jìn)行掃描，每發(fā)現(xiàn)一個(gè)序列，將其加入候選序列集合T，并且集合的大小Tn加1。

2)如果掃描發(fā)現(xiàn)的新序列在T中已經(jīng)存在，則集合T的大小Tn保持不變。

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

一個(gè)好的候選序列集合的選取應(yīng)能在保證挖掘結(jié)果準(zhǔn)確性的基礎(chǔ)上，大幅降低算法的空間復(fù)雜度，提高挖掘效率。實(shí)驗(yàn)4將對基礎(chǔ)的枚舉方法，以及提出的改進(jìn)方法1、2進(jìn)行對比分析。

2.4.2 前導(dǎo)碼長度的判定及挖掘

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

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

結(jié)合上述有效的候選序列結(jié)合方法，提出前導(dǎo)碼長度的判別方法：

1)利用改進(jìn)方法2從S中選取長度為MByte的候選序列，并統(tǒng)計(jì)其中出現(xiàn)頻數(shù)較多的序列KMi及其頻數(shù)NMi，結(jié)果記為RM。

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

3)當(dāng)頻數(shù)保持不變的序列在RM+i中是唯一的頻數(shù)最高的序列，且在RM+i+1中不再出現(xiàn)，則該序列即為前導(dǎo)碼，M+i即為前導(dǎo)碼的長度；否則跳轉(zhuǎn)到步驟2繼續(xù)挖掘。

在挖掘得到前導(dǎo)碼之后，便可通過前導(dǎo)碼對目標(biāo)比特流S進(jìn)行準(zhǔn)確的幀切分。實(shí)驗(yàn)5將對該方法進(jìn)行驗(yàn)證。

3 實(shí)驗(yàn)結(jié)果與分析

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

實(shí)驗(yàn)所用數(shù)據(jù)來自以太網(wǎng)，捕獲某一主機(jī)在一段時(shí)間內(nèi)使用同種協(xié)議的交互數(shù)據(jù)包，并經(jīng)過處理使其轉(zhuǎn)換成為帶幀頭的連續(xù)比特流數(shù)據(jù)，其中S2數(shù)據(jù)量足夠大，如表1所示。

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

3.2 從目標(biāo)比特流S中發(fā)現(xiàn)候選序列

實(shí)驗(yàn)1以數(shù)據(jù)量較小的S1為研究對象，采用從目標(biāo)比特流S中發(fā)現(xiàn)候選序列并構(gòu)建字典樹的方法，分別查找其中8、16、32以及48bit長度的候選序列集合，統(tǒng)計(jì)該過程中掃描長度(在S1中掃描多少比特即可發(fā)現(xiàn)所有候選序列)、發(fā)現(xiàn)個(gè)數(shù)(掃描完S1發(fā)現(xiàn)的候選序列個(gè)數(shù))以及該過程的耗時(shí)，結(jié)果如表2所示。

表2 從目標(biāo)比特流中發(fā)現(xiàn)候選序列的結(jié)果

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

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

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

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

對4個(gè)不同長度的候選序列發(fā)現(xiàn)結(jié)果進(jìn)行對比可知，候選序列長度較短，易受協(xié)議用戶數(shù)據(jù)的影響，導(dǎo)致候選序列集合大小變化特征不明顯，而對于長度較長的32、48以及64bit的候選序列集合，其受協(xié)議用戶數(shù)據(jù)的影響較小，能更加清晰地顯示候選序列集合大小的變化特征。

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

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

表3 改進(jìn)方法2的候選序列選取

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

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

3.4 前導(dǎo)碼長度的判定及挖掘

實(shí)驗(yàn)4中為了驗(yàn)證選取候選序列的準(zhǔn)確性，使用了已知條件，即以太網(wǎng)前導(dǎo)碼的長度為64bit，僅挖掘了長度為64bit的頻繁序列，而實(shí)際情況是捕獲到的數(shù)據(jù)協(xié)議未知，實(shí)驗(yàn)5以包含1 000個(gè)數(shù)據(jù)幀的S3數(shù)據(jù)為研究對象，對提出的前導(dǎo)碼長度的判定及挖掘方法進(jìn)行了驗(yàn)證。

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

表5 不同長度頻繁序列挖掘結(jié)果

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

圖5 候選序列頻數(shù)隨長度的變化

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

4 結(jié)語

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

)

[1]EDWARDW.信息戰(zhàn)原理與實(shí)戰(zhàn)[M].吳漢平,譯.北京:電子工業(yè)出版社,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] 金陵.面向比特流的未知幀頭識(shí)別技術(shù)研究[D].上海:上海交通大學(xué),2011:29-39.(JINL.Studyonbitstreamorientedunknownframeheadidentification[J].Shanghai:ShanghaiJiaoTongUniversity, 2011: 29-39.)

[6] 王和洲,薛開平,洪佩琳,等.基于頻繁統(tǒng)計(jì)和關(guān)聯(lián)規(guī)則的未知鏈路協(xié)議比特流切割算法[J].中國科技大學(xué)學(xué)報(bào),2013,43(7):554-560.(WANGHZ,XUEKP,HONGPL,etal.Anunknownlinkprotocolbitstreamsegmentationalgorithmbasedonfrequentstatisticsandassociationrules[J].JournalofUniversityofScienceandTechnologyofChina, 2013, 43(7): 554-560.)

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

[8] 琚玉建,謝紹斌,張薇.基于自適應(yīng)權(quán)值的數(shù)據(jù)報(bào)指紋特征識(shí)別與發(fā)現(xiàn)[J].計(jì)算機(jī)測量與控制,2014,22(7):2288-2290.(JUYJ,XIESB,ZHANGW.Identificationofdatafingerprintcharacteristicsbasedonself-adaptiveweights[J].ComputerMeasurement&Control, 2014, 22(7): 2288-2290.)

[9] 鄭潔,朱強(qiáng).未知單協(xié)議數(shù)據(jù)幀的地址分析與研究[J].計(jì)算機(jī)科學(xué),2015,42(11):184-187.(ZHENGJ,ZHUQ.Analysisandresearchonaddressmessageofunknownsingleprotocoldataframe[J].ComputerScience, 2015, 42(11): 184-187.)[10] RICHARD S W.TCP/IP詳解卷1:協(xié)議[M].范建華,胥光輝,張濤,等譯.北京: 機(jī)械工業(yè)出版社,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] 吳艷梅.無線環(huán)境下比特流協(xié)議幀定位與特征分析[D].成都: 電子科技大學(xué), 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.計(jì)算機(jī)網(wǎng)絡(luò)[M].嚴(yán)偉,潘愛民,譯.5版.北京: 清華大學(xué)出版社, 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] 鮑震.高速網(wǎng)絡(luò)入侵監(jiān)測系統(tǒng)模式匹配算法的研究與實(shí)現(xiàn)[D].長沙:國防科學(xué)技術(shù)大學(xué),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] 王和洲.面向比特流的鏈路協(xié)議識(shí)別與分析技術(shù)[D].合肥:中國科學(xué)技術(shù)大學(xué),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ìn)的多模式字符串匹配算法[J].計(jì)算機(jī)應(yīng)用,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] 萬國根,秦志光.改進(jìn)的AC-BM字符串匹配算法[J].電子科技大學(xué)學(xué)報(bào),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] 張鑫,譚建龍,程學(xué)旗.一種改進(jìn)的Wu-Manber多關(guān)鍵詞匹配算法[J].計(jì)算機(jī)應(yīng)用,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。 基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(61272491，61309021)。

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

1001- 9081(2017)02- 0440- 05

10.11772/j.issn.1001- 9081.2017.02.0440

TN915.04

A