模式匹配算法在入侵檢測中的應用

預處理階段，模式樹的各個節點作為狀態，根節點作為初態，標簽為模式的節點作為終態，利用轉向函數g和失效函數f作為轉移函數，將模式樹擴展成一個樹型有限自動機。
由模式樹擴展所得的AC自動機M是1個6元組：

M=(Q,∑，g，f，q0，F)
其中：
(1)Q是有限狀態集(模式樹上的節點)；
(2)∑是有窮的輸入字符表(數據包中可能出現的所有字符)；
(3)g是轉移函數，該函數定義如下：g(s，a)：從當前狀態s開始，沿著邊上標簽為a的路徑所到的狀態。假如(u，v)邊上的標簽為a，那么g(u，a)=v；如果根節點上出來的邊上的標簽沒有a，則g(0，a)=O，即如果沒有匹配的字符出現，自動機停留在初態；
(4)f(不匹配時自動機的狀態轉移)也是轉移函數，該函數定義如下：
f(s)：當w是L(s)最長真后綴并且w是某個模式的前綴，那么f(s)就是以w為標簽的那個節點；
(5)q0∈Q是初態(根節點，標識符為0)；
(6)XXXXX是終態集(以模式為標簽的節點集)。
這樣，在目標串中查找模式的過程轉化成在模式樹中的查找過程。查找一個串T時從模式樹的根節點開始，沿著以T中字符為標簽的路徑往下走：若自動機能夠抵達終態v，則說明T中存在模式L(v)；否則不存在模式。
AC算法模式匹配的時間復雜度是0(n)，并且與模式集中模式串的個數和每個模式串的長度無關。無論模式串P是否出現在目標串T中，T中的每個字符都必須輸入狀態機中，所以無論是最好情況還是最壞情況，AC算法模式匹配的時間復雜度都是O(n)，包括預處理時間在內，AC算法總時間復雜度是O(M+n)，其中M為所有模式串的長度總和。
2．3 AC―BM算法
對多模式串的匹配而言，雖然AC算法比BM算法高效得多，但AC算法必須逐一查看目標串的每個字符，即必須按順序輸入，不能實現跳躍，而BM算法則能夠利用“右滑”跳過目標串中的大段字符，從而提高搜索速度。如果將BM算法的這種啟發式搜索技術應用到AC算法中，則可大大提高多模式匹配算法的效率。許多人據此給出了各種改進的算法。Commentz―Walter最先將BM算法和AC算法結合在一起給出了Com―mentz―Walter算法；Baeza―Yates結合BMP算法和AC算法也給出了多模式匹配改進算法。
AC―BM算法是Jang―Jong在1993年結合Ac算法的有限自動機和BM算法的連續跳躍思想提出來的新算法，利用劣勢移動表和優勢跳轉表來實現跳躍式地并行搜索，算法的時間復雜度為0(mn)。該算法的思想是：首先把要查找的多個模式構成一個關鍵字樹，把相同的前綴作為樹的根節點。模式樹從目標串的右端向左移動，一旦模式樹確定在適當的位置，字符比較從左向右開始進行。模式樹移動時同時使用壞字符移動和好前綴移動。壞字符移動的策略為：如果出現不匹配的情況，移動模式樹，使得樹中其他模式的能與當前目標串正在比較的字符相匹配的那個字符移動到與當前目標串正在比較的字符的相同位置上，如果在當前的深度上，目標字符沒有出現在任何模式中，則模式樹的偏移量為樹中最短模式的長度。好前綴移動的移動策略為：將模式樹移動到一個已被發現是另一個模式子串完全前綴的下一個位置，或者移動到作為樹中另一個模式后綴能夠正確匹配目標串的某個前綴的下一個位置。在模式樹的移動過程中，必須確保模式樹的偏移量不能大于樹中最短的模式長度。
2．4 AC，AC―BM算法改進情況簡介
文獻中盧汪節等人針對AC算法在構造狀態機時空間冗余較大的情況，對狀態機各結點進行壓縮存儲，使空間性能和時間性能都有提高；文獻中萬國根等人對AC―BM算法的改進借鑒了BMH算法的思想，取消了原算法的好前綴跳轉，優化了壞字符跳轉，并修改了skip的計算方法，對大字符集的情況在平均情況下具有更優的性能；文獻對AC―BM的改進則是通過預處理思想實現的，在進行AC―BM匹配之前首先掃描首和(或)尾字符，確定其位置，再到相應位置進行匹配，相當于把目標串按模式串首、尾字符分成數段，每段進行比較，段間不含首字符的就直接跳過，不用比較，從而提高效率。

3 算法的實際執行效率
上述這些算法究竟哪種算法具有最好的執行效率呢?能不能僅通過時間復雜度來進行衡量呢?時間復雜度僅是一個度量的范圍，表示受幾個參數的影響，并不代表一個具體的值，還需要在具體的環境中進行測試。
文獻測試了包括上述算法在內的多種單模式和多模式匹配算法的性能。測試平臺為：硬件：CPUIntel Xeon 3．46 GHz X 2，內存2 GB DDR，硬盤200GB SCSI；軟件：windows 2003 Server，Intel IXASDK4．1。單模式匹配測試的規則集，使用隨機生成的8，16，32，48，128位具有代表意義的規則，可以對應端口、IP地址，MAC地址、IPv6地址等，對多模式匹配測試采用Snort系統2．4．3規則集。
單模式匹配算法主要測試模式長度與匹配時間、占用空間及預處理時間的變化關系。測試結果表明：各算法的測試指標在規則長度增長的情況下均呈遞增趨勢，但BM算法的增長速度最為緩慢，在不太在意存儲空間的情況下，BM可以作為優先考慮的算法，同時對IPV6地址也更為合適。
多模式匹配算法的測試項目為規則數與單位匹配時間、占用儲存單元、單位預處理時間的變化關系。測試結果表明AC―BM算法在上述3項測試中取得了很好的性能平衡。這也是新版的Snort系統中選用AC―BM算法的重要原因。

4 入侵檢測系統中模式匹配算法的研究方向
常用的模式匹配算法所采用的思想主要有基于字符比較、基于自動機、基于hash查找、基于位邏輯運算和基于Tries樹型機構搜索。鑒于目前網絡的實際狀況，多模式匹配算法更加適合于基于模式匹配的入侵檢測系統。這里認為應該從下面3個方面著手：一是繼續研究和改進精確的模式匹配，將快速的單模式匹配算法和多模式匹配算法相結合，充分借鑒同類算法的先進思想，如：引入Hash函數、引入自動機、對字符串分塊等來不斷提高多模式匹配算法的性能；二是嘗試采用模糊匹配的策略，國外對此已經開始進行相應的研究；三是對網絡數據包和入侵特征進行研究，總結出這兩類字符串特點，有針對性地對這兩類字符串的匹配問題進行研究。

5 結 語
網絡帶寬的不斷增加、日益嚴重的網絡安全狀況要求必須盡快提高網絡入侵檢測系統的性能。雖然入侵檢測系統可以采用很多技術，并且這些技術也在不斷的研究和發展中，但是目前主流的實用的入侵檢測技術仍然是基于模式匹配的。因此如何提高模式匹配的效率成為研究入侵檢測系統的一個關鍵所在。在此對已有的經典模式匹配算法進行了系統綜述，并對入侵檢測系統中模式匹配算法的未來研究方向給出了觀點。