基于正則表達式的多模式匹配算法研究.pdf

1、隨著計算機和Intemet技術(shù)的普及與發(fā)展,網(wǎng)絡在人們?nèi)粘Ｉ钪邪l(fā)揮越來越重要的作用,但是隨之而來的網(wǎng)絡安全問題也日益突出。入侵檢測系統(tǒng)作為保障網(wǎng)絡安全的重要防護措施得到了廣泛應用,模式匹配作為入侵檢測系統(tǒng)中的一項關(guān)鍵技術(shù),其性能優(yōu)劣關(guān)系到整個入侵檢測系統(tǒng)的效率,提高模式匹配的效率是提高這類系統(tǒng)檢測能力的關(guān)鍵所在。
　　 本文簡單介紹了入侵檢測系統(tǒng),分析了多模式匹配算法在其中的應用,并對AC、AC_BM和WM算法做了詳細說明。但

2、是,隨著網(wǎng)絡技術(shù)的發(fā)展和規(guī)則集復雜性的增加,這些傳統(tǒng)的字符串匹配引擎正逐漸被先進的正則表達式引擎所替代。
　　 正則表達式匹配引擎一般是基于非確定的有限自動機(Nondetenninistic Finite Automaton，NFA)和確定的有限自動機(Deterministic Finite Automaton,DFA)的?；贜FA的匹配引擎匹配速度慢,但存儲空間相對較小?；贒FA的匹配引擎具有先天的速度優(yōu)勢,但是消耗的

3、存儲空間過大,并且隨著規(guī)則集規(guī)模的增大,其對存儲空間的需求更大。本文從減少構(gòu)造的自動機的狀態(tài)數(shù)出發(fā),提出了一種有效的DFA合并算法(稱為COM DFA算法)。在自動機構(gòu)造過程中,將各個正則表達式分開處理,避免合并自動機時狀態(tài)和遷移邊之間的交互重疊情況的出現(xiàn),能夠大大地減少自動機的狀態(tài)數(shù)。并且,通過引入空轉(zhuǎn)移合并DFA,構(gòu)造一個具有最小狀態(tài)數(shù)的自動機,從而減少存儲空間需求。最后,引入壓縮率CR(Compressed Rate)的概念來描述

4、合并算法對自動機狀態(tài)數(shù)的壓縮比率。實驗結(jié)果表明算法對DFA狀態(tài)數(shù)具有較好的壓縮效果。
　　 針對NFA和DFA的匹配速度和內(nèi)存需求之間的矛盾,提出一種基于DFA-NFA結(jié)構(gòu)有限自動機的正則表達式匹配算法(稱為D N算法)。算法采用DFA-NFA結(jié)構(gòu)實現(xiàn)自動機的構(gòu)造,分開處理引起DFA空間爆炸的狀態(tài),以降低存儲需求。由于網(wǎng)絡中的數(shù)據(jù)只有很少一部分是惡意數(shù)據(jù),而大部分是正常數(shù)據(jù),DFA部分在NFA部分之前的設計可以實現(xiàn)數(shù)據(jù)過濾功能,