面向鏈路層比特流數(shù)據(jù)頻繁統(tǒng)計(jì)的AC-IM算法

曹成宏，雷迎科，徐一鳴

1(解放軍電子工程學(xué)院，合肥 230037)2(武警工程大學(xué)，西安 710078)

1 引 言

在研究鏈路層未知協(xié)議時(shí)，如何解決從經(jīng)過(guò)物理層解調(diào)和譯碼后的海量比特流數(shù)據(jù)中高效準(zhǔn)確地提取關(guān)鍵頻繁序列并識(shí)別未知協(xié)議這一問(wèn)題是該文進(jìn)行算法探究的背景.尋找未知協(xié)議的特征序列，在沒(méi)有先驗(yàn)知識(shí)的情況下，需要快速對(duì)頻繁序列進(jìn)行提取，目前多模式匹配算法是主流，因其僅通過(guò)一次掃描就可以得到所有模式串的統(tǒng)計(jì)結(jié)果.在國(guó)內(nèi)外研究中，運(yùn)用經(jīng)典多模式匹配算法及其改進(jìn)算法進(jìn)行統(tǒng)計(jì)的相關(guān)研究很多，但對(duì)于鏈路層比特流數(shù)據(jù)進(jìn)行處理的算法研究卻很少，同時(shí)各算法由于自身設(shè)計(jì)的缺陷，導(dǎo)致計(jì)算復(fù)雜度高、效率低、漏檢情況多，這些都是亟待解決的問(wèn)題.文獻(xiàn)[1]中Fan JJ提出了AC_BM算法，實(shí)現(xiàn)了多模式串跳躍式地匹配，相比于AC算法每次僅1個(gè)字符，時(shí)間效率有了顯著提高，但算法的“壞字符”規(guī)則導(dǎo)致模式樹(shù)往往達(dá)不到最大跳躍距離.文獻(xiàn)[2]針對(duì)AC_BM算法的不足，提出了一種改進(jìn)的AC_QSS算法.AC_QSS算法采用正向有限狀態(tài)自動(dòng)機(jī)組織模式串和地址映射的方法查找字符串，從兩個(gè)方面提高了算法的時(shí)間效率，但最大跳躍距離仍為最短模式串長(zhǎng)度.文獻(xiàn)[3]結(jié)合了AC和BMH算法，只保留壞字符規(guī)則，該算法特別適合在大字符集文本串中查找小字符集模式串，但其模式樹(shù)最大跳躍距離仍沒(méi)有變.文獻(xiàn)[4]用AC多模式匹配算法進(jìn)行鏈路層比特流數(shù)據(jù)統(tǒng)計(jì)，實(shí)現(xiàn)一次掃描文本完成多個(gè)模式匹配，但匹配準(zhǔn)確率不高.文獻(xiàn)[5]針對(duì)比特流數(shù)據(jù)提出改進(jìn)AC算法的枚舉樹(shù)剪枝算法，能夠減少統(tǒng)計(jì)過(guò)程中的數(shù)據(jù)庫(kù)操作次數(shù)，提高統(tǒng)計(jì)的準(zhǔn)確率和效率，但閾值和反饋周期選取不當(dāng)會(huì)大大影響剪枝的效果.

該文的算法設(shè)計(jì)面向?qū)ο笫擎溌穼佣M(jìn)制數(shù)據(jù)流，即考慮到數(shù)據(jù)具有二元性和連續(xù)重復(fù)性的特點(diǎn).文章的主要?jiǎng)?chuàng)新有以下3點(diǎn)：

1)改進(jìn)了經(jīng)典多模式匹配AC算法，構(gòu)造出AC-IM(Improved AC)算法，首先構(gòu)建1個(gè)字符串跳躍表和2個(gè)哈希表，后采用多層跳躍規(guī)則依次查找這3個(gè)表，降低了漏檢率，增大了最大跳躍距離.

2)發(fā)現(xiàn)并采用這種高效的AC-IM算法解決鏈路層二進(jìn)制比特流數(shù)據(jù)的頻繁統(tǒng)計(jì)問(wèn)題，為下一步鏈路層未知協(xié)議的分析奠定了基礎(chǔ).

3)從算法對(duì)比特流數(shù)據(jù)環(huán)境的適應(yīng)性、高效性和正確性三個(gè)方面進(jìn)行了大量的對(duì)比實(shí)驗(yàn)，得出了理想的實(shí)驗(yàn)結(jié)果.

該文的結(jié)構(gòu)安排如下：第2節(jié)介紹了算法的基本原理；第3節(jié)給出算法的理論分析；第4節(jié)介紹頻繁統(tǒng)計(jì)理論；第5節(jié)給出算法數(shù)據(jù)適應(yīng)性、高效性、正確性的實(shí)際數(shù)據(jù)對(duì)比測(cè)試結(jié)果；最后總結(jié)全文.

2 算法原理

2.1 AC算法

AC算法兼顧了有限狀態(tài)自動(dòng)機(jī)和字典樹(shù)[6]的優(yōu)點(diǎn)，匹配復(fù)雜度與模式串?dāng)?shù)量無(wú)關(guān)，可以僅用一次掃描獲得所有模式串的匹配結(jié)果[7]，復(fù)雜度為Θ(n)[8].因這一特性，目前AC算法及其改進(jìn)的AC-BM算法、AC-BMH算法等被廣泛應(yīng)用于數(shù)據(jù)統(tǒng)計(jì)和匹配中.AC算法分為預(yù)處理和匹配兩個(gè)階段：

預(yù)處理階段：包括生成3個(gè)函數(shù)即goto(轉(zhuǎn)移)函數(shù)、failure(失效)函數(shù)和output(輸出)函數(shù)[9].首先構(gòu)造有限狀態(tài)自動(dòng)機(jī)：從狀態(tài)0開(kāi)始，讀取第1個(gè)模式串的第1個(gè)字符，生成新?tīng)顟B(tài)；再?gòu)男聽(tīng)顟B(tài)開(kāi)始，讀取第1個(gè)模式串的第2個(gè)字符，生成新的后繼狀態(tài)，以此類(lèi)推，直到處理完所有字符；處理完第1個(gè)模式串之后，再?gòu)?狀態(tài)處理第2個(gè)，直到處理完所有模式串.例如，P={nb，tnb，nit，nbrs}的goto函數(shù)如圖1所示.

圖1 {nb，tnb，nit，nbrs}的goto函數(shù)Fig.1 Goto function of {nb，tnb，nit，nbrs}

狀態(tài)轉(zhuǎn)移函數(shù)goto，在自動(dòng)機(jī)中，對(duì)于狀態(tài)q，若讀入字符c，生成狀態(tài)q′，那么q′=fail，若讀入字符c后，沒(méi)有后繼狀態(tài)，那么g(q，c)=fail.如圖1所示，g(1，i)=6，g(1，q)=0.

失效函數(shù)f用來(lái)指明當(dāng)某個(gè)字符與文本不匹配時(shí)，應(yīng)處理的下一狀態(tài).f的構(gòu)造方法為：所有第一層狀態(tài)的失效函數(shù)為0，如f(3)=0；對(duì)于其他狀態(tài)q，若其父狀態(tài)為m，即存在字符a，使得f(q)=g(f(m)，a).如f(4)=g(f(3)，n)=g(0，n)=1.

輸出函數(shù)output的作用是在匹配過(guò)程中輸出已經(jīng)匹配的模式串.output的構(gòu)造分兩步，第一步是在構(gòu)造轉(zhuǎn)移函數(shù)g時(shí)，每處理完一個(gè)模式串，則將該模式串加入到當(dāng)前狀態(tài)q的輸出函數(shù)中，如output(1)={n}，output(5)={tnb}.第二步是構(gòu)造失效函數(shù)f時(shí)，若f(q)=q′，如output(q)=output(q)∪output(q′)，output(5)=output(5)∪output(2)={tnb，nb}.

匹配階段：假定模式串指針為w指向首字符，當(dāng)前狀態(tài)q=0具體步驟如圖2所示.

2.2 AC-IM算法

AC-IM算法也分為預(yù)處理和匹配階段[10]兩個(gè)階段.算法用1個(gè)字符串最大跳躍距離表和2個(gè)哈希表來(lái)確定發(fā)生失配時(shí)距離.設(shè)串集P={123，145，11145}，當(dāng)前匹配窗口前3個(gè)字符分別為a，b，c，如圖3所示.AC-IM算法模式樹(shù)規(guī)則描述如下：

圖2 AC算法匹配階段Fig.2 Matching phase of AC algorithm

1)若c=模式樹(shù)首層字符，偏移距離為1.

2)若bc在模式樹(shù)minlength(最短模式串長(zhǎng)度)深度內(nèi)出現(xiàn)，使之對(duì)齊(查找字符串最大跳躍距離表).

3)若ab=任一串第minlength-1和第minlength層字符組成的字符串，距離為minlength+1(查找哈希表LTST).

4)若a=任一串第minlength層字符，距離為minlength+2(查找哈希表LCT).

5)若以上均不滿足，距離為minlength+3.

圖3 AC-IM匹配過(guò)程Fig.3 Matching process of AC algorithm

具體步驟如下：

1)創(chuàng)建字符串最大跳躍距離表SST.將模式樹(shù)minlength深度內(nèi)兩兩相鄰字符組成字符串.SST用來(lái)記錄字符串在模式樹(shù)中的位置，用到模式樹(shù)首層字符的距離來(lái)表示，記為dis(S).S=Pi[k]Pi[k+1](1≤i≤r，1≤k≤minlength-1)為任一字符串，dis(S)=Pi(k)到模式樹(shù)首字符距離等于k-1.若某個(gè)字符串多次出現(xiàn)，取其最小值.SST表創(chuàng)建算法偽代碼如下：

Algorithm1. Create SST

Input：P={p1，p2，…，pr}，minlength

Output： SST

1.Initialize the string table SST；

2.for(i=1；i<=r；i++)/*Loop through each pattern string*/

3.{

4.for(j=1；j<=minlength-1；j++)

5. {

6.if(StringPi[j]Pi[j+1]exist in table SST)

7.{ /*StringPi[j]Pi[j+1]appears multiple times，take the depth of the smaller*/

8.if(The dis value in the SSTtable

9.Keep the value of dis；

10.else the value of dis=dis(Pi[j]Pi[j+1])；

11.}

12.else

13.the value of dis=dis(Pi[j]Pi[j+1])；

14. }

15.}

16.Returns the string table SST；

如模式集P={123，145，11145}，p1={123}，p2={145}，p3={11145}，minlength=3.minlength度內(nèi)所有兩兩相鄰字符構(gòu)成的字符串集合S={12，23，14，45，11}.以“11”為例，在minlength深度內(nèi)出現(xiàn)了2次，均在p3中.選深度較小的位置計(jì)算，因p3[1]=1，k=1，所以dis(11)=0.由P創(chuàng)建的SST表如表1所示.

表1 SST表Table 1 SST

2)創(chuàng)建第一個(gè)末層字符串哈希表LTST.LTST表存儲(chǔ)每個(gè)模式串第minlength-1個(gè)字符及第minlength個(gè)字符組成的字符串.LTST表創(chuàng)建算法偽代碼如下：

Algorithm2. Create LTST

Input：P={p1，p2，...，pr}，minlength

Output： LTST

1.Initialize the string table LTST；

2.for(i=1；i<=r；i++)

3.{

4.if(Pi[minlength-1]Pi[minlength]not exist in LTST)

5.{

6.if(addPi[minlength-1]Pi[minlength]to LTST)

7.}

8.}

9.Returns to LTST；

同上，模式集P={123，145，11145}對(duì)應(yīng)的LTST如表2所示.

3)創(chuàng)建第二個(gè)末層字符串哈希表LCT.LCT表存儲(chǔ)每個(gè)模式串第minlength層的字符.LCT表創(chuàng)建算法偽代碼如下：

Algorithm3. Create LCT

Input：P={p1，p2，...，pr}，minlength

Output： LCT

1.Initialize the string table LCT；

2.for(i=1；i<=r；i++)

3.{

4.if(Pi[minlength]not exist in LCT)

5.{

6.if(addPi[minlength]to LCT)

7.}

8.}

9.Returns to LCT；

同理，模式集P={123，145，11145}對(duì)應(yīng)的LCT如表3所示.

4)匹配階段：

初始狀態(tài).模式樹(shù)的首層節(jié)點(diǎn)對(duì)齊文本串的倒數(shù)第minlength個(gè)字符，第minlength層節(jié)點(diǎn)對(duì)齊文本串的末字符，模式樹(shù)方向從右向左，字符比較方向從左向右.

表2 LTST表

Table 2 LTST

PatternsetDatastringp1[1]p1[2]12p2[1]p2[2]14p3[1]p3[2]11

表3 LCT表

Table 3 LCT

PatternsetDatastringp1[2]2p2[2]5p3[2]1

字符比較.在當(dāng)前匹配窗口內(nèi)，從左向右逐個(gè)讀入文本串字符，利用goto函數(shù)進(jìn)行狀態(tài)轉(zhuǎn)移，當(dāng)output函數(shù)不為空時(shí)，輸出匹配成功的字符串；當(dāng)發(fā)生失配時(shí)，計(jì)算距離shiftlength，并將模式樹(shù)左移shiftlength位.距離計(jì)算算法偽代碼如下：

Algorithm4. Calculate the moving distance

Input： SST，LTST，LCT，x，y，z，minlength

Output：shiftlength

1.if(z= =first character)

2.shiftlength=1；

3.else if(yz∈SST)

4.shiftlength=dis(yz)+2；

5.else if(hash(xy)->LTST==true)

6.shiftlength=minlength+1；

7.else if(hash(x)->LCT==true)

8.shiftlength=minlength+2；

9.else

10.shiftlength=minlength+3；

11.Returnshiftlength；

重復(fù)字符比較步驟，直到模式樹(shù)和文本串的首字符對(duì)齊，匹配過(guò)程結(jié)束.

3 算法分析

3.1 匹配速度分析

模式串的匹配效率即匹配過(guò)程中的模式樹(shù)的跳躍距離量，該文通過(guò)分析AC-IM算法的原理，和AC_BM、AC_BMH、AC_QSS算法的對(duì)比，在不發(fā)生漏檢的情況下，總結(jié)各算法模式樹(shù)的最大跳躍距離如表4所示.

表4 最大跳躍距離Table 4 Maximum jump distance

AC-IM算法最好情況下能跳過(guò)當(dāng)前匹配窗口前3個(gè)字符，使得模式樹(shù)最大跳躍距離為最短模式串長(zhǎng)度加3.最大跳躍距離的增大，則減少了字符比較次數(shù)，提高了匹配效率.

3.2 匹配時(shí)間效率分析

一個(gè)匹配算法的時(shí)間效率主要考量指標(biāo)是算法的時(shí)間復(fù)雜度，該文算法通過(guò)和AC_BM、AC_BMH、AC_QSS算法的對(duì)比，如表5所示(r為模式串?dāng)?shù)量，n為文本串長(zhǎng)度)，可以發(fā)現(xiàn)AC-IM算法最大跳躍距離大，且采用字符塊判斷規(guī)則，故達(dá)到超過(guò)minlength距離的概率也大，所以匹配階段時(shí)間效率優(yōu)于上述其他算法.

表5 時(shí)間復(fù)雜度Table 5 Time complexity

4 頻繁序列統(tǒng)計(jì)

利用多模式匹配算法從大量的鏈路層比特流數(shù)據(jù)中匹配出指定的特征序列，例如在以太網(wǎng)幀格式中類(lèi)型字段為“10000000”表示IP協(xié)議，“10000110”表示ARP協(xié)議等.緊接著就要判斷其是否為頻繁序列[10]，頻繁序列是指頻繁地出現(xiàn)在數(shù)據(jù)集中的模式串，結(jié)合比特流數(shù)據(jù)定義即：目標(biāo)比特流中T的長(zhǎng)度為n，那么S中包含的長(zhǎng)度為m的模式串P的個(gè)數(shù)記為r，r=n-m+1.若T中模式串P的出現(xiàn)頻數(shù)為k，那么P的支持度為k/r，記為Supp(P).當(dāng)Supp(P)大于或等于預(yù)先定義好的最小支持度，則認(rèn)為P是頻繁序列，否則為非頻繁序列.正確的發(fā)現(xiàn)比特流數(shù)據(jù)中的頻繁序列對(duì)于鏈路層未知協(xié)議的判定至關(guān)重要，而找出頻繁序列的正確與否很大程度上受統(tǒng)計(jì)算法高效性和漏檢率的影響.

5 實(shí)驗(yàn)驗(yàn)證

實(shí)驗(yàn)環(huán)境：Windows 7系統(tǒng)，因特爾Core-i5處理器，1.5GHZ，3GB內(nèi)存，軟件CodeBlocks16.01和Wireshark2.2.3.

5.1 算法的“01”比特流適應(yīng)性驗(yàn)證

鏈路層比特流數(shù)據(jù)集相比于普通字符串文本集有兩個(gè)特點(diǎn)，即“01”二元性和連續(xù)重復(fù)性.AC-IM算法從上述算法原理分析可以看出，算法用1個(gè)字符串最大跳躍距離表和2個(gè)哈希表來(lái)確定發(fā)生失配時(shí)距離，其能夠識(shí)別連續(xù)出現(xiàn)的重復(fù)數(shù)據(jù)并統(tǒng)計(jì)、快速跳躍略過(guò)，再進(jìn)行接下來(lái)的匹配；同時(shí)數(shù)據(jù)就01兩種出現(xiàn)可能性，搜索匹配步驟少，匹配效率提高，進(jìn)而能夠更快的達(dá)到最大跳躍距離匹配.為驗(yàn)證這一性質(zhì)，實(shí)驗(yàn)用 Wireshark軟件抓取存儲(chǔ)100M的無(wú)線網(wǎng)鏈路協(xié)議二進(jìn)制比特流文本集和100M的英國(guó)BBC新聞文本集作對(duì)比.隨機(jī)從兩個(gè)樣本集中抽取8位、16位的數(shù)據(jù)串各500和1000個(gè)，實(shí)驗(yàn)結(jié)果如表6所示.

由表6可以看出，AC-IM算法在對(duì)二進(jìn)制比特流文本集處理上耗時(shí)優(yōu)勢(shì)很明顯，驗(yàn)證了其對(duì)“01”數(shù)據(jù)流的適應(yīng)性.

5.2 算法的高效性驗(yàn)證

為了驗(yàn)證該文提出算法在數(shù)據(jù)匹配應(yīng)用中的效率，實(shí)驗(yàn)數(shù)據(jù)是使用Wireshark軟件抓取一段時(shí)間內(nèi)手持電話無(wú)線網(wǎng)的協(xié)議數(shù)據(jù)，整理出鏈路層部分協(xié)議PPP、HDLC、ATM大小分別為4.7M、2.3M、4.2M的.txt文件集，整合在一起形成約11 M的16進(jìn)制比特流數(shù)據(jù)集.從中任意取長(zhǎng)度分別8位、16位、32位的比特流串各200個(gè).首先固定模式串長(zhǎng)度，改變模式串?dāng)?shù)量(50、100、200)進(jìn)行實(shí)驗(yàn)；再固定模式串?dāng)?shù)量，改變模式串長(zhǎng)度(8、16、32)進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)中測(cè)試了AC_BM、AC_BMH、AC_QSS、AC-IM四種匹配算法的耗時(shí)，如表7、表8所示.(單位/s)

表6 算法匹配耗時(shí)Table 6 Time-consuming of matching

表7 算法匹配耗時(shí)1Table 7 Time-consuming of matching1

從表7、表8中可以看出，隨著模式串的長(zhǎng)度增加，算法匹配速度呈上升趨勢(shì)；隨著模式串?dāng)?shù)量的增加，算法匹配速度

表8 算法匹配耗時(shí)2Table 8 Time-consuming of matching2

成下降的趨勢(shì)，但是由于AC-IM算法采用了新的最大跳躍距離方式，相比AC_BM，AC_BMH、AC_QSS算法具有更大的最大跳躍距離間距，因此其匹配速度比AC_BM 和AC_BMH、AC_QSS更快，充分論證了該算法的高效性.

5.3 算法的頻繁統(tǒng)計(jì)準(zhǔn)確性驗(yàn)證

實(shí)驗(yàn)仍采用Wireshark抓取的鏈路層PPP、HDLC、ATM協(xié)議并將其轉(zhuǎn)換成二進(jìn)制比特流后分別保存為PPP.txt、HDLC.txt、ATM.txt格式數(shù)據(jù)包.文本集大小分別為1.8M、0.9M、1.3M.該文將AC-IM算法與AC_BM、AC_BMH、AC_QSS三者算法作對(duì)比，利用四種算法統(tǒng)計(jì)出8位、16位比特的特征序列，然后根據(jù)頻繁序列的判定方法篩選出頻繁序列(閾值設(shè)定為0.7)，比照已知的三種協(xié)議特征序列，計(jì)算出篩選的頻繁序列的正確率，從而得出四種算法的統(tǒng)計(jì)正確率差異.頻繁序列篩選率及正確率如表9、表10所示.

表9 8比特頻繁序列統(tǒng)計(jì)結(jié)果Table 9 Statistical results of 8-bit frequent sequence

從表9、表10中可以看出，特征序列比特位越長(zhǎng)，頻繁序列的篩選率和正確率越高.相比于AC_BM、AC_BMH、AC_QSS算法，AC-IM算法從頻繁序列的篩選率以及篩選出的頻繁序列的正確率兩個(gè)方面考量都具有一定的優(yōu)勢(shì).

表10 16比特頻繁序列統(tǒng)計(jì)結(jié)果Table 10 Statistical results of 16-bit frequent sequence

6 結(jié)束語(yǔ)

該文提出的基于AC-IM算法的鏈路層比特流數(shù)據(jù)頻繁統(tǒng)計(jì)方法旨在解決經(jīng)典的多模式匹配算法如AC算法及其改進(jìn)算法等計(jì)算復(fù)雜度高、效率低，同時(shí)不能適用于二元性比特流數(shù)據(jù)這些問(wèn)題.通過(guò)算法結(jié)構(gòu)設(shè)計(jì)的理論分析和實(shí)驗(yàn)驗(yàn)證表明，該算法能夠較好的適應(yīng)二進(jìn)制比特流數(shù)據(jù)環(huán)境，準(zhǔn)確地統(tǒng)計(jì)出頻繁序列，并且消耗時(shí)間更少、效率更高.為下一步鏈路層未知協(xié)議的分析奠定了基礎(chǔ)，具有一定的實(shí)際應(yīng)用價(jià)值.