潘向榮，王 婷

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

0 引 言

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

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

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

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

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

1 相關(guān)概念

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

定義1 假定P中包括m個比特，則稱P的長度為m。

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

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

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

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

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

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

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

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

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

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

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

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

(1)

式中：x表示模式序列，dec(x)表示x對應(yīng)的十進制數(shù)，Length(x)表示x的長度，Index表示x在存儲其位置信息的數(shù)組中的下標值。

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

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

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

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

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

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

(2)

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

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

2.3 基于位置差的長序列拼接改進算法

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

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

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

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

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

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

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

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

圖2 基于位置差的長序列拼接算法流程

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

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

(3)

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

基于位置差的長序列拼接改進算法的偽代碼如下：

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

2 fori=1 to length(Xs) do

6 end for

7 end for

8 對P進行由小到大的排序，并對X進行對應(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 對Psel進行排序，Xsel也對應(yīng)進行排序；

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 算法分析及算法有效性驗證

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

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

測試實驗方案的步驟如下：

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

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

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

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

表4給出了在不同閾值下上述兩種長序列拼接算法的仿真運行時間。

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

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

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

4 結(jié) 論

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