雙向AC算法及其在入侵檢測系統(tǒng)中

經(jīng)過眾多偉大科學(xué)家不斷地研究，我國在算法領(lǐng)域有了進(jìn)一步的發(fā)展，當(dāng)前相關(guān)的科學(xué)家已經(jīng)在經(jīng)典的多模式字符串匹配算法-AC算法的基礎(chǔ)上提出了雙向AC算法。這種雙向算法的提出能夠在預(yù)處理階段建立正向和反向兩種狀態(tài)的自動機(jī)，這種自動機(jī)在掃描的過程中使用正向有限自動機(jī)從中間向右進(jìn)行，而反向有限自動機(jī)從中間向左進(jìn)行。這種算法與之前相比具有更高的效率，因此得到了更廣泛的使用。

【關(guān)鍵詞】AC算法 串匹配算法 入侵檢測系統(tǒng)

一般情況下，網(wǎng)絡(luò)入侵檢測系統(tǒng)的模式匹配算法的主要功能就是判斷攻擊模式串是否在截獲的網(wǎng)絡(luò)數(shù)據(jù)包有效負(fù)載中出現(xiàn)。一般情況下，我們將模式匹配算法分為兩種，一種是單模式匹配，還有一種是多模式匹配。單模式算法中最經(jīng)典的是跳躍式配算法，其在匹配的過程中能夠自動的跳過不許匹配的字符。而多模式算法中最經(jīng)典的是AC算法，這種算法在執(zhí)行過程中不會受到模式長度以及文本特征的影響，因此使用的比較廣泛。

1 雙向AC算法的工作流程

雙向AC算法在運(yùn)行的過程中，首先進(jìn)行的工作就是對模式串進(jìn)行預(yù)處理，并且在處理的過程中生成正向、反向兩種樹狀有限狀態(tài)自動機(jī)，其在匹配的過程中由正向、反向自動機(jī)分別從中間向左右兩側(cè)掃描，從而將所有的模式串匹配出來。

1.1 模式串集合的預(yù)處理過程

進(jìn)行模式串集合的預(yù)處理工作時，相關(guān)工作人員的主要工作就是將模式串集合轉(zhuǎn)換成正向和反向有限自動機(jī)。在這個階段，工作人員需要注意的是將正向有限自動機(jī)與AC算法結(jié)合，從左向右進(jìn)行掃描。另外，在預(yù)處理的過程中，首先進(jìn)行的就是對Goto函數(shù)，與此同時注意生成一部分Output函數(shù)，工作的時候從0開始，對字符的順序及重復(fù)性進(jìn)行考慮，同時增加一些新的狀態(tài)及路徑，直到將所有的模式串都處理完。另外，在處理模式串的過程中，還應(yīng)該將其狀態(tài)進(jìn)行記錄，使整個算法能夠有條不紊的進(jìn)行。

1.2 AC算法的文本匹配過程

AC算法在進(jìn)行的過程中，文本串及模式串集合一般情況下是已經(jīng)給定的，因此工作人員在匹配的過程中就應(yīng)該將文本串的中心點(diǎn)作為基礎(chǔ)，而匹配過程中的重復(fù)區(qū)域使用最長模式串充當(dāng)，并且將正向和反向匹配的起點(diǎn)確定下來，將正向處理過程與反向處理過程進(jìn)行對比，使AC算法的文本匹配過程能夠順利的進(jìn)行。

1.3 雙向AC算法在Snort系統(tǒng)中的使用

雙向AC算法在當(dāng)今的社會中使用的十分廣泛，其在Snort系統(tǒng)中的應(yīng)用十分的普遍。將其應(yīng)用在Snort系統(tǒng)中能夠精確的完成實(shí)時流量分析以及網(wǎng)絡(luò)的測試，除此之外還能夠完成協(xié)議分析、內(nèi)容查找以及匹配等工作。還有一點(diǎn)最重要的是雙向AC算法在Snort系統(tǒng)中的使用能夠完成最后的模式匹配，提前發(fā)現(xiàn)數(shù)據(jù)包中可能含有的入侵信息，避免系統(tǒng)受到不良的侵害。

2 系統(tǒng)的測試與分析

AC算法在使用的過程中，為了保證其安全性，相關(guān)的工作人員還應(yīng)該對其進(jìn)行測試。一般情況下，工作人員對其進(jìn)行測試的時候通常是與BM算法、WM算法以及原始的AC算法進(jìn)行比較。在本文中，我們主要將一臺PC作為模擬攻擊主機(jī)作為例子進(jìn)行說明。一般情況下，發(fā)送攻擊封包的時候主要由仿真攻擊軟件Tcpreplay進(jìn)行，在檢測DEFCON錄制的封包數(shù)據(jù)的時候使用Snort V2.6規(guī)則集中的6718條規(guī)則，并且在測試的時候要分別以同的規(guī)則數(shù)和算法去測試，同時還應(yīng)該對不同算法下的系統(tǒng)入侵檢測侵效率進(jìn)行統(tǒng)計(jì)。一般情況下，工作人員對其進(jìn)行檢測的時候通常是在Snort主機(jī)為CPU Intel CORE 2DUO 3.0GHz、內(nèi)存2G DDRIII，操作環(huán)境為Windows2000server的環(huán)境下進(jìn)行，之所以選擇在這種環(huán)境下測試，最主要的原因就是因?yàn)樵谶@種環(huán)境下AC算法運(yùn)行比較穩(wěn)定，因此檢測的結(jié)果更加的穩(wěn)定，得到的數(shù)據(jù)具有更高的信服力。

另外，在檢測的過程中相關(guān)工作人員還需要注意，如果在檢測過程中使用的TCPreplay，那么第一次在攻擊端使用DEFCON數(shù)據(jù)包的大小為24.5MByte，其內(nèi)部含有20筆攻擊特征。在這20筆攻擊特征中，封包傳輸協(xié)議TCP占了百分之八十二，UPD占百分之十五，而ICMP只占了百分之三，并且在進(jìn)行的過程中其是以8000個每秒的速度發(fā)送到Snort主機(jī)上的，Snort則以14000個每秒的速度進(jìn)行封包統(tǒng)計(jì)。除此之外，為了避免進(jìn)程調(diào)度對檢測帶來干擾，每一次檢測的數(shù)據(jù)都是取十次檢測的平均值，這就能夠有效的避免數(shù)據(jù)的不準(zhǔn)確性以及隨機(jī)性，使實(shí)驗(yàn)數(shù)據(jù)更加的具有說服力。

相關(guān)的工作人員通過進(jìn)行一系列的實(shí)驗(yàn)?zāi)軌蚩闯?，隨著規(guī)則數(shù)的不斷增加，每一次實(shí)驗(yàn)中使用到的算法都具有效率比較低的情況，但是通過使用多種算法進(jìn)行對比能夠得出AC算法的穩(wěn)定性要遠(yuǎn)遠(yuǎn)的高于其他的算法，使用發(fā)現(xiàn)攻擊即停止匹配方式進(jìn)行檢測的時候，雙向AC算法處理的數(shù)據(jù)量往往是一般算法的1.5倍。通過分析，AC算法之所以具有更高的效率，最主要的原因就是其將文本串分為兩個部分，雙向?qū)ξ谋具M(jìn)行處理。但是需要注意的一點(diǎn)是，在使用的過程中由于其需要同時建立正向和反向狀態(tài)機(jī)，所以占用的空間相對其他的算法來說就比較大，在這種情況下，這種算法就不能使用到內(nèi)存資源比較小的嵌入式入侵檢測系統(tǒng)當(dāng)中。

3 結(jié)束語

從上面文章的描述中國我們就能夠知道，雙向AC算法在最近的幾年取得了突破性的進(jìn)步，并且通過一系列的測試能夠知道，AC算法的性能要遠(yuǎn)遠(yuǎn)優(yōu)于其他的算法，AC算法的使用不僅能夠與多模式匹配算法進(jìn)行結(jié)合，還能夠優(yōu)化時空開銷。因此相關(guān)的工作人員必須對其進(jìn)行足夠的重視，并且投入更大的精力對其進(jìn)行研究，只有這樣才能夠使其獲得進(jìn)一步的發(fā)展，讓其成為世界范圍的領(lǐng)導(dǎo)者。

（通訊作者：潘華偉）

參考文獻(xiàn)

[1]張慶平.一種基于Snort的入侵檢測系統(tǒng)的實(shí)現(xiàn)和應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件，2016（08）：134-137.

[2]高平麗，任金呂.基于Snort的入侵檢測系統(tǒng)的分析與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與軟件，2016（03）：108-111.

[3]楊超.雙向AC算法及其在入侵檢測系統(tǒng)中應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2015（03）：222-225.

[4]宮正.入侵檢測系統(tǒng)中模式匹配算法的改進(jìn)及應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2013（12）：96-99.

[5]王奇敏.基于入侵檢測系統(tǒng)的正則表達(dá)式匹配引擎設(shè)計(jì)[D].杭州：杭州電子科技大學(xué)，2014（08）：13-17.

[6]劉鑫.網(wǎng)絡(luò)入侵檢測系統(tǒng)中模式匹配算法的應(yīng)用研究[D].大連：大連海事大學(xué)，2013（06）：88-91.

作者簡介

潘華偉（1990-），男，安徽省人。湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院碩士研究生。研究方向?yàn)榫W(wǎng)絡(luò)防火墻中多模式匹配算法的應(yīng)用研究。

作者單位

1.湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 湖北省武漢市 430068

2. 武漢軟件工程職業(yè)學(xué)院計(jì)算機(jī)學(xué)院 湖北省武漢市 430205