潘向榮，王 婷

(1.中國(guó)西南電子技術(shù)研究所，成都 610036；2.電子科技大學(xué) 通信抗干擾技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室，成都 611730)

0 引 言

公開通信協(xié)議的數(shù)據(jù)幀結(jié)構(gòu)是確定并易知的，但在某些特殊場(chǎng)景尤其是軍事應(yīng)用環(huán)境中，為提高數(shù)據(jù)傳輸?shù)陌踩?，通信方通常不?huì)采用公開的通信協(xié)議，而是采用專用的通信協(xié)議進(jìn)行數(shù)據(jù)傳輸，這些專用通信協(xié)議通常是不公開的。因此，在電子對(duì)抗中，數(shù)據(jù)幀格式對(duì)非合作接收方而言是未知的，從偵查截獲的通信比特流中識(shí)別出幀結(jié)構(gòu)進(jìn)而識(shí)別通信協(xié)議，將協(xié)議幀頭與數(shù)據(jù)載荷區(qū)分開來，從而進(jìn)一步對(duì)截獲的數(shù)據(jù)載荷進(jìn)行破譯等分析，對(duì)分析網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、識(shí)別信息流目標(biāo)以及網(wǎng)絡(luò)抗干擾通信具有重要意義。

目前，國(guó)內(nèi)外對(duì)數(shù)據(jù)鏈路層未知協(xié)議的識(shí)別領(lǐng)域的研究進(jìn)展較為緩慢[1-10]?！拔粗獏f(xié)議”是指具有一定固定幀頭格式的未公開協(xié)議。比特流未知協(xié)議識(shí)別的一般思路是：基于統(tǒng)計(jì)理論挖掘出比特流的特征序列等協(xié)議特征，根據(jù)一般通信協(xié)議的基本特征來進(jìn)一步確定比特流的幀頭位置，進(jìn)而分析出比特流的幀格式。對(duì)于未知的通信協(xié)議，分析者并沒有可以參考的特征序列，必須通過枚舉和統(tǒng)計(jì)方法來篩選、比對(duì)等步驟挖掘出特征序列。從比特流中如何快速、準(zhǔn)確的分析出特征序列是識(shí)別未知通信協(xié)議的關(guān)鍵。

一般說來，未知通信協(xié)議識(shí)別包括數(shù)據(jù)預(yù)處理、頻繁序列提取(統(tǒng)計(jì)與篩選)、特征序列挖掘和特征序列關(guān)聯(lián)分析4個(gè)主要步驟。

數(shù)據(jù)預(yù)處理是指將獲取的數(shù)據(jù)轉(zhuǎn)換為01比特流，頻繁序列提取是指對(duì)模式序列進(jìn)行準(zhǔn)確計(jì)數(shù)，并通過預(yù)設(shè)閾值，根據(jù)一定的篩選規(guī)則篩選出頻繁序列，然后通過拼接等手段獲得較長(zhǎng)的頻繁序列，從而得到候選特征序列集合。最后，應(yīng)用關(guān)聯(lián)規(guī)則挖掘技術(shù)對(duì)候選特征序列進(jìn)行關(guān)聯(lián)規(guī)則挖掘，由此確定未知通信協(xié)議的特征序列和可能的協(xié)議幀結(jié)構(gòu)。

文獻(xiàn)[2]采用AC(Aho-Corasick)統(tǒng)計(jì)算法完成頻繁序列的提取(包括統(tǒng)計(jì)與篩選)。該算法基于二叉樹來實(shí)現(xiàn)對(duì)模式序列出現(xiàn)位置的存儲(chǔ)。在對(duì)模式序列進(jìn)行統(tǒng)計(jì)計(jì)數(shù)時(shí)需要遍歷整棵二叉樹節(jié)點(diǎn)，其遍歷代價(jià)很大。本文在分析出AC快速統(tǒng)計(jì)算法[2]的這一缺陷后，改進(jìn)了模式序列的統(tǒng)計(jì)方式，采用數(shù)組代替二叉樹存儲(chǔ)比特流中模式序列的位置信息，并構(gòu)造了使得數(shù)組下標(biāo)值與二叉樹節(jié)點(diǎn)值保持一致的關(guān)系式，有效降低了對(duì)模式序列進(jìn)行計(jì)數(shù)及篩選的時(shí)間復(fù)雜度。進(jìn)一步，本文將存儲(chǔ)各頻繁序列位置信息的數(shù)組依次連接成一個(gè)長(zhǎng)數(shù)組，并按頻繁序列出現(xiàn)位置的先后順序重新排列該數(shù)組元素，進(jìn)而改進(jìn)了基于位置差的特征序列挖掘算法。與原算法相比，改進(jìn)算法大幅度減少了算法迭代次數(shù)，將頻繁序列拼接時(shí)間減少了至少一個(gè)數(shù)量級(jí)，快速挖掘出了比特流中的特征序列。

1 相關(guān)概念

設(shè)有長(zhǎng)度為n的隨機(jī)比特流序列S，對(duì)于S中的任意一個(gè)模式序列P，不妨給出如下定義：

定義1 假定P中包括m個(gè)比特，則稱P的長(zhǎng)度為m。

定義2 假定P為長(zhǎng)度m的模式序列，Q為長(zhǎng)度q的模式序列，q≤m，且P的1～q位均與Q的對(duì)應(yīng)位置比特相同，則稱Q是P的子序列，P是Q的父序列。

定義3 假定S中共有r個(gè)長(zhǎng)為m的模式序列，其中模式序列P出現(xiàn)了k次，則P的支持度supp(P)為k/r。

定義4 假定supp(P)不小于用戶規(guī)定的最小支持度，那么P為頻繁序列；反之，為非頻繁序列。

2 基于位置差的特征序列挖掘快速算法

2.1 AC快速統(tǒng)計(jì)算法的改進(jìn)

AC算法是于1975年由貝爾實(shí)驗(yàn)室的Aho和Corasick兩位研究人員提出的一種多模式匹配算法，該算法是模式匹配領(lǐng)域的經(jīng)典算法之一。金陵等人[2]提出的AC快速統(tǒng)計(jì)算法是基于AC算法的一種改進(jìn)，該算法將二叉樹存儲(chǔ)結(jié)構(gòu)改為使用數(shù)組結(jié)構(gòu)進(jìn)行比特流中模式序列的存儲(chǔ)，可以實(shí)現(xiàn)對(duì)比特流中出現(xiàn)的所有模式序列統(tǒng)計(jì)完全。

顯然，比特流序列的元素取值為0或1。因此，長(zhǎng)為m的模式序列P有且僅有兩個(gè)長(zhǎng)為m+1的父序列。窮舉長(zhǎng)度取值為[1，m]的所有模式序列可構(gòu)成一棵完全二叉樹。圖1表示由長(zhǎng)度區(qū)間為[1，4]b的所有模式序列構(gòu)成的二叉樹。

圖1 長(zhǎng)為1～4 b的模式序列所構(gòu)成的完全二叉樹

AC快速統(tǒng)計(jì)算法基于二叉樹來實(shí)現(xiàn)對(duì)模式序列出現(xiàn)位置的存儲(chǔ)。在對(duì)模式序列進(jìn)行計(jì)數(shù)時(shí)需要遍歷整棵二叉樹節(jié)點(diǎn)，其遍歷代價(jià)很大。

經(jīng)過對(duì)二叉樹存儲(chǔ)結(jié)構(gòu)和相關(guān)存儲(chǔ)結(jié)構(gòu)特點(diǎn)的深入分析，采用數(shù)組代替二叉樹存儲(chǔ)比特流中模式序列的位置信息，并構(gòu)造了使得數(shù)組下標(biāo)值與二叉樹節(jié)點(diǎn)值相等的關(guān)系式，基于此給出了一種復(fù)雜度更低的模式序列統(tǒng)計(jì)算法。該算法的創(chuàng)新之處在于，通過對(duì)所截獲的比特流的存儲(chǔ)結(jié)構(gòu)的修改，使得在對(duì)模式序列的計(jì)數(shù)過程中極大降低了對(duì)模式序列的掃描次數(shù)，進(jìn)而極大減少了統(tǒng)計(jì)過程中所需的計(jì)算時(shí)間和存儲(chǔ)空間。

本文對(duì)文獻(xiàn)[2]中的AC快速統(tǒng)計(jì)算法進(jìn)行了改進(jìn)，通過分析各模式序列與數(shù)組下標(biāo)之間的邏輯關(guān)系，構(gòu)造了使得存儲(chǔ)模式序列對(duì)應(yīng)的數(shù)組下標(biāo)值與二叉樹節(jié)點(diǎn)值相等的表達(dá)式，具體為

Index= dec(x)+2Length(x)-1

(1)

式中：x表示模式序列，dec(x)表示x對(duì)應(yīng)的十進(jìn)制數(shù)，Length(x)表示x的長(zhǎng)度，Index表示x在存儲(chǔ)其位置信息的數(shù)組中的下標(biāo)值。

根據(jù)式(1)，所有的模式序列均與存儲(chǔ)其位置的數(shù)組的下標(biāo)值對(duì)應(yīng)。將圖1中的二叉樹采用式(1)列出模式序列與存儲(chǔ)其位置的數(shù)組的下標(biāo)號(hào)之間的對(duì)應(yīng)關(guān)系,如表1所示。

表1 模式序列與數(shù)組下標(biāo)的映射關(guān)系

將表1和圖1進(jìn)行比較，不難發(fā)現(xiàn)如下事實(shí)：比特流中各模式序列在數(shù)組中的下標(biāo)值與這些模式序列在二叉樹中的節(jié)點(diǎn)值完全對(duì)應(yīng)。這一事實(shí)可以更為直觀地比較模式序列在二叉樹結(jié)構(gòu)和數(shù)組結(jié)構(gòu)下的存儲(chǔ)特征。

2.2 基于閾值的頻繁序列篩選

在無任何先驗(yàn)信息情況下，假設(shè)對(duì)長(zhǎng)度為m的模式序列進(jìn)行計(jì)數(shù)，不失一般性，假定0和1等概率出現(xiàn)在每一個(gè)比特位置上，那么，長(zhǎng)為m的模式序列的種數(shù)為2m。不妨假定待識(shí)別的比特流S的隨機(jī)性良好，那么每種長(zhǎng)為m的模式序列的出現(xiàn)概率均為1/2m。根據(jù)支持度的定義，則長(zhǎng)度為m的模式序列的平均支持度等于1/2m。不難得知，長(zhǎng)為n的比特流S中存在(n-m+1)個(gè)長(zhǎng)度為m的模式序列。因此，長(zhǎng)為m的模式序列出現(xiàn)的平均次數(shù)為(n-m+1)/2m。

通常，篩選閾值Th被設(shè)置為

(2)

式中：參數(shù)α的作用為調(diào)節(jié)閾值大小，n表示序列S的長(zhǎng)度，m表示模式序列的長(zhǎng)度。

在所有的模式序列的計(jì)數(shù)和閾值設(shè)置完成以后，根據(jù)對(duì)比模式序列的計(jì)數(shù)值與篩選閾值的大小以及篩選規(guī)則，可將所有的模式序列劃分為頻繁序列和非頻繁序列，所有被列為頻繁序列的模式序列構(gòu)成頻繁序列集合。

2.3 基于位置差的長(zhǎng)序列拼接改進(jìn)算法

一般來講，子序列的出現(xiàn)次數(shù)均大于其父序列的出現(xiàn)次數(shù)。因此，子序列被篩選為頻繁序列的機(jī)會(huì)大于其父序列。換句話說，頻繁序列集合中更多的是長(zhǎng)度較短的模式序列。但在實(shí)際協(xié)議中，也會(huì)存在長(zhǎng)度較大的特征序列。序列拼接是獲得較長(zhǎng)模式序列的一種主要方法之一，即將滿足一定要求的較短的頻繁序列通過拼接的方式獲得較長(zhǎng)的模式序列。

文獻(xiàn)[2]介紹了一種基于位置差的長(zhǎng)序列拼接方案，但該方案在對(duì)短序列進(jìn)行拼接的過程中需要大量的重復(fù)迭代操作。經(jīng)分析，該序列拼接算法存在如下三個(gè)不足：第一，復(fù)雜度高；第二，存在特征序列挖掘誤差；第三，序列重疊度高。本文從這些分析結(jié)果出發(fā)，對(duì)基于位置差的長(zhǎng)序列拼接算法進(jìn)行了改進(jìn)。改進(jìn)算法充分利用了各頻繁序列在比特流中出現(xiàn)位置的先后順序這一信息，在對(duì)頻繁序列集合進(jìn)行存儲(chǔ)表示時(shí)，改進(jìn)算法按照各頻繁序列的出現(xiàn)位置來進(jìn)行存儲(chǔ)。這一改進(jìn)大幅簡(jiǎn)化了拼接過程中的迭代次數(shù)。

在文獻(xiàn)[2]中，將同種頻繁序列出現(xiàn)的多個(gè)位置信息存儲(chǔ)在同一個(gè)數(shù)組中，如表2所示。

表2 頻繁序列與其出現(xiàn)位置對(duì)應(yīng)表

在表2中，xi(i=1,2,…,N)表示第i種頻繁序列，而pi,j表示第i種頻繁序列的第j個(gè)出現(xiàn)位置。這種頻繁序列與表示其出現(xiàn)次數(shù)位置的數(shù)組之間的對(duì)應(yīng)關(guān)系，不能準(zhǔn)確刻畫出這兩個(gè)頻繁序列間的出現(xiàn)位置的先后順序。例如，無法直接判斷出模式序列p1,1和p2,1的大小關(guān)系，只能分別將這兩個(gè)模式序列的數(shù)值取出并進(jìn)行比較才能做出判定。這直接導(dǎo)致了該拼接算法的復(fù)雜度較高。

基于對(duì)AC快速統(tǒng)計(jì)算法的不足的分析，本文提出了改進(jìn)算法。改進(jìn)算法在基于表2所示的存儲(chǔ)方式上，將各模式序列對(duì)應(yīng)的所有數(shù)組依次首尾連接成一個(gè)數(shù)組P，如表3所示。顯然，此時(shí)頻繁序列出現(xiàn)位置的總數(shù)，即為頻繁序列集合的元素個(gè)數(shù)。

表3 頻繁序列與其出現(xiàn)位置一一對(duì)應(yīng)表

進(jìn)一步，將數(shù)組P中的元素按照相應(yīng)頻繁序列出現(xiàn)位置的先后順序從左到右進(jìn)行排序，然后，進(jìn)行基于位置差的長(zhǎng)序列拼接，其拼接算法流程如圖2所示。

圖2 基于位置差的長(zhǎng)序列拼接算法流程

將滿足如下拼接條件的兩條頻繁序列xi和xj進(jìn)行拼接，然后對(duì)拼接后的長(zhǎng)序列進(jìn)行篩選，判斷其是否為頻繁序列。拼接條件仍然為[2]

pos(xj)- pos(xi)=Length(xi) 。

(3)

式中：pos(xi)和pos(xj)分別表示序列xi和xj在輸入比特流中的出現(xiàn)位置。這里需要指出的是，因?yàn)楦倪M(jìn)算法的拼接條件與原算法一致，因此，拼接而成的長(zhǎng)序列的輸出結(jié)果與原算法也完全相同。

基于位置差的長(zhǎng)序列拼接改進(jìn)算法的偽代碼如下：

1 初始化XS=?,P=?;

2 fori=1 to length(Xs) do

6 end for

7 end for

8 對(duì)P進(jìn)行由小到大的排序，并對(duì)X進(jìn)行對(duì)應(yīng)的元素交換；

9 初始化i←1,j←i+1,Xtemp=?;

10 while true do

11 ifP[j]-P[i]=length(X[i])then

12xnew←splice(X[i],X[j]);

13 ifxnex?Xtempthen

14Xtemp←Xtemp∪xnew,pos(xnew)←pos(xnew)∪i;

15 else

16 pos(xnew)←pos(xnew)∪i;

17 end if

18i←i+1,j←j+1;

19 else ifP[j]-P[i]>length(X[i])then

20i←i+1;

21 else

22j←j+1

23 end if

24 if j=length(X)+1 then

25 ifXtemp=? then

26 break;

27 else

28 篩選Xtemp中滿足閾值的頻繁序列，并將篩選出的序列集合展開為Xsel以及其出現(xiàn)位置集合Psel;

29 ifXsel=? then

30 break;

31 end if

32 對(duì)Psel進(jìn)行排序，Xsel也對(duì)應(yīng)進(jìn)行排序；

33 初始化k←1,l←1;

34 while true do

35 ifP[k]=Psel[l] then

36X[k]←Xsel[l],k←k+1,l←l+1;

37 else

38k←k+1;

39 end if

40 ifl=length(Psel)+1 then

3 算法分析及算法有效性驗(yàn)證

與原算法[2]相比，本文提出的改進(jìn)算法采用一個(gè)數(shù)組來存儲(chǔ)所有頻繁序列的位置信息，且數(shù)組元素依照對(duì)應(yīng)頻繁序列出現(xiàn)位置的先后順序從左到右依次排列，該存儲(chǔ)方式極大減少了算法的迭代次數(shù)。在原算法[2]中，需要掃描所有可能的位置差來判斷拼接條件(式(3))是否滿足，極大增加了算法中的迭代操作，導(dǎo)致原算法的復(fù)雜度較高。改進(jìn)算法在拼接過程中只需要遍歷頻繁序列集合一次，極大減少了迭代地進(jìn)行拼接條件的判斷操作，使得改進(jìn)算法的復(fù)雜性大大低于原算法。

為驗(yàn)證算法的有效性，我們采用Visual C++開發(fā)平臺(tái)編寫程序?qū)崿F(xiàn)算法，使用Wireshark抓包軟件截取數(shù)據(jù)包完成了算法性能有效性測(cè)試實(shí)驗(yàn)。測(cè)試環(huán)境為Windows 7操作系統(tǒng)，Intel?CoreTMi5 7400處理器，CPU主頻3 GHz。

測(cè)試實(shí)驗(yàn)方案的步驟如下：

Step1 使用Wireshark抓包軟件截取ARP包(200幀以上)進(jìn)行測(cè)試，以包含100幀ARP協(xié)議幀的比特流作為實(shí)驗(yàn)數(shù)據(jù)。

Step2 設(shè)置5組篩選閾值，分別為0.5、1.0、1.5、2.0和2.5。

Step3 對(duì)Step 1得到的實(shí)驗(yàn)數(shù)據(jù)分別采用原算法[2]和本文的改進(jìn)算法完成對(duì)實(shí)驗(yàn)數(shù)據(jù)的比特流分析。

Step4 對(duì)比兩種算法下的時(shí)間復(fù)雜度。

表4給出了在不同閾值下上述兩種長(zhǎng)序列拼接算法的仿真運(yùn)行時(shí)間。

表4 不同閾值系數(shù)下兩種序列拼接算法的運(yùn)行時(shí)間

從表4中的仿真數(shù)據(jù)可以得到以下結(jié)論:第一，隨著篩選閾值從0.5到2.5以0.5為步長(zhǎng)逐漸增大，兩種拼接算法的計(jì)算時(shí)間均逐漸減少；第二，改進(jìn)算法的時(shí)間復(fù)雜度遠(yuǎn)低于原算法，表明對(duì)頻繁序列出現(xiàn)位置進(jìn)行排序后再進(jìn)行拼接的方案極大降低了拼接算法的時(shí)間復(fù)雜度，驗(yàn)證了改進(jìn)算法的有效性。圖3形象地展示了兩種算法的時(shí)間性能對(duì)比。

圖3 兩種序列拼接算法的時(shí)間復(fù)雜度比較

4 結(jié) 論

鏈路層中基于比特流的幀結(jié)構(gòu)分析是進(jìn)一步獲取情報(bào)信息的關(guān)鍵環(huán)節(jié)。金陵等人[2]提出的基于位置差的長(zhǎng)序列拼接算法是面向比特流未知協(xié)議識(shí)別的主要算法。本文在深入研究該算法基礎(chǔ)上，提出了基于位置差的特征序列挖掘改進(jìn)算法。改進(jìn)算法采用數(shù)組來替代原算法中的二叉樹來存儲(chǔ)頻繁序列的出現(xiàn)位置信息，且數(shù)組元素依照對(duì)應(yīng)頻繁序列出現(xiàn)位置的先后順序從左到右依次排列，這種存儲(chǔ)方式極大減少了算法的迭代次數(shù)。最后，使用Wireshark截取ARP包完成了算法的有效性測(cè)試。仿真結(jié)果表明，與原算法相比，本文的改進(jìn)算法大幅度減少了算法迭代次數(shù)，將頻繁序列拼接時(shí)間減少了至少一個(gè)數(shù)量級(jí)，快速挖掘出了比特流中的特征序列，為進(jìn)一步挖掘比特流的幀內(nèi)結(jié)構(gòu)奠定了基礎(chǔ)。