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

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

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

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

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