入侵檢測(cè)系統(tǒng)中基于正則表達(dá)式的匹配算法研究.pdf

1、入侵檢測(cè)系統(tǒng)(Intrusion Detection System，IDS)是當(dāng)前最有效的網(wǎng)絡(luò)安全防御系統(tǒng)，它能夠準(zhǔn)確高效地識(shí)別各種網(wǎng)絡(luò)入侵行為。IDS依賴于基于正則表達(dá)式的特征庫(kù)，它通過(guò)數(shù)據(jù)收集引擎把收集到的網(wǎng)絡(luò)數(shù)據(jù)流和特征庫(kù)中的特征進(jìn)行匹配，根據(jù)匹配的結(jié)果來(lái)確定是否存在著網(wǎng)絡(luò)入侵行為。但在IDS中，匹配的時(shí)間通常會(huì)占用整個(gè)檢測(cè)時(shí)間的90％以上，所以高性能的基于正則表達(dá)式匹配算法成為了當(dāng)前研究的重點(diǎn)。
　　 使用正則表達(dá)式來(lái)描

2、述各種網(wǎng)絡(luò)威脅，在匹配時(shí)通常需要將表達(dá)式轉(zhuǎn)換成確定的有限自動(dòng)機(jī)(Deterministic Finite Automata，DFA)。面對(duì)當(dāng)今高速的網(wǎng)絡(luò)，傳統(tǒng)的基于DFA的正則表達(dá)式匹配算法已經(jīng)很難適用于當(dāng)前的環(huán)境，針對(duì)DFA存儲(chǔ)空間過(guò)大的問(wèn)題，我們分別從DFA的狀態(tài)和轉(zhuǎn)移邊進(jìn)行優(yōu)化。
　　 為了減少DFA的狀態(tài)，本文提出了一種基于局部查找分組(Local Seeking Grouping，LSG)的正則表達(dá)式匹配算法。為了能更

3、好的描述我們的算法，我們對(duì)正則表達(dá)式的矛盾進(jìn)行了定義，證明了當(dāng)表達(dá)式之間處于矛盾為正和矛盾獨(dú)立狀態(tài)的時(shí)候，正則表達(dá)式集合的最優(yōu)k分組問(wèn)題實(shí)際上就是最小邊缺失的k分割問(wèn)題，而最小邊缺失的k分割問(wèn)題也就是最大k分割問(wèn)題，即NP-hard問(wèn)題。最后用LSG算法來(lái)解決分組問(wèn)題，并證明了對(duì)于最大k分割問(wèn)題，LSG算法的近似比為k/(k-1)。實(shí)驗(yàn)表明，與正則表達(dá)式不分組、分為一組相比，正則表達(dá)式分若干組在狀態(tài)總數(shù)、匹配時(shí)間和存儲(chǔ)空間上遠(yuǎn)遠(yuǎn)小于另外

4、兩種方式;與Becchi、REGADR和Fang Yu分組算法相比，LSG分組算法在分組數(shù)、分組時(shí)間、狀態(tài)總數(shù)、匹配時(shí)間和存儲(chǔ)空間上的性能遠(yuǎn)遠(yuǎn)優(yōu)于另外三種算法。
　　 為了減少DFA的轉(zhuǎn)移邊，本文提出了一種基于緊密的可擴(kuò)展的有限自動(dòng)機(jī)（Inseparable Extended Finite Automation，IXFA）的正則表達(dá)式匹配算法。IXFA是一種基于XFA的有限自動(dòng)機(jī)，同時(shí)也是一種基于DFA的有限自動(dòng)機(jī)，DFA、XF

5、A和IXFA從本質(zhì)上來(lái)說(shuō)并無(wú)區(qū)別，只是結(jié)構(gòu)略有不同而已。在IXFA構(gòu)造過(guò)程中，本文提出了基于優(yōu)先級(jí)的轉(zhuǎn)移邊壓縮算法，即壓縮相同后續(xù)狀態(tài)最多的轉(zhuǎn)移邊，設(shè)置優(yōu)先級(jí)來(lái)解析轉(zhuǎn)移邊，已達(dá)到減少存儲(chǔ)空間的目的;在IXFA匹配過(guò)程中，本文提出了基于位圖的轉(zhuǎn)移邊查找算法，即采用位圖來(lái)并行查找不同優(yōu)先級(jí)的轉(zhuǎn)移邊子集，輸出優(yōu)先級(jí)最高的匹配轉(zhuǎn)移邊，從而確保轉(zhuǎn)移邊查找的匹配效率。實(shí)驗(yàn)表明，與XFA相比，IXFA在轉(zhuǎn)移邊數(shù)上、存儲(chǔ)空間和匹配時(shí)間上的性能遠(yuǎn)遠(yuǎn)優(yōu)于X