雙向AC算法及其在入侵檢測系統中

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

【關鍵詞】AC算法 串匹配算法 入侵檢測系統

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

1 雙向AC算法的工作流程

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

1.1 模式串集合的預處理過程

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

1.2 AC算法的文本匹配過程

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

1.3 雙向AC算法在Snort系統中的使用

雙向AC算法在當今的社會中使用的十分廣泛，其在Snort系統中的應用十分的普遍。將其應用在Snort系統中能夠精確的完成實時流量分析以及網絡的測試，除此之外還能夠完成協議分析、內容查找以及匹配等工作。還有一點最重要的是雙向AC算法在Snort系統中的使用能夠完成最后的模式匹配，提前發現數據包中可能含有的入侵信息，避免系統受到不良的侵害。

2 系統的測試與分析

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

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

相關的工作人員通過進行一系列的實驗能夠看出，隨著規則數的不斷增加，每一次實驗中使用到的算法都具有效率比較低的情況，但是通過使用多種算法進行對比能夠得出AC算法的穩定性要遠遠的高于其他的算法，使用發現攻擊即停止匹配方式進行檢測的時候，雙向AC算法處理的數據量往往是一般算法的1.5倍。通過分析，AC算法之所以具有更高的效率，最主要的原因就是其將文本串分為兩個部分，雙向對文本進行處理。但是需要注意的一點是，在使用的過程中由于其需要同時建立正向和反向狀態機，所以占用的空間相對其他的算法來說就比較大，在這種情況下，這種算法就不能使用到內存資源比較小的嵌入式入侵檢測系統當中。

3 結束語

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

（通訊作者：潘華偉）

參考文獻

[1]張慶平.一種基于Snort的入侵檢測系統的實現和應用[J].計算機應用與軟件，2016（08）：134-137.

[2]高平麗，任金呂.基于Snort的入侵檢測系統的分析與實現[J].計算機應用與軟件，2016（03）：108-111.

[3]楊超.雙向AC算法及其在入侵檢測系統中應用[J].計算機系統應用，2015（03）：222-225.

[4]宮正.入侵檢測系統中模式匹配算法的改進及應用[J].計算機系統應用，2013（12）：96-99.

[5]王奇敏.基于入侵檢測系統的正則表達式匹配引擎設計[D].杭州：杭州電子科技大學，2014（08）：13-17.

[6]劉鑫.網絡入侵檢測系統中模式匹配算法的應用研究[D].大連：大連海事大學，2013（06）：88-91.

作者簡介

潘華偉（1990-），男，安徽省人。湖北工業大學計算機學院碩士研究生。研究方向為網絡防火墻中多模式匹配算法的應用研究。

作者單位

1.湖北工業大學計算機學院 湖北省武漢市 430068

2. 武漢軟件工程職業學院計算機學院 湖北省武漢市 430205