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

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

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

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

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