入侵檢測系統(tǒng)中多模式匹配算法的研究.pdf

1、隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展,計(jì)算機(jī)網(wǎng)絡(luò)在國民經(jīng)濟(jì)中發(fā)揮了日益重要的作用,已成為人們?nèi)粘Ｉ畈豢扇鄙俚囊徊糠?。同時(shí),網(wǎng)絡(luò)安全也日益引起人們的關(guān)注,而防火墻或入侵檢測系統(tǒng)作為維護(hù)網(wǎng)絡(luò)安全的重要措施,得到了廣泛的應(yīng)用。對于防火墻或入侵檢測系統(tǒng)技術(shù)來說,數(shù)據(jù)包過濾是其核心,而模式匹配算法卻是數(shù)據(jù)包過濾的關(guān)鍵技術(shù)之一,它直接影響到系統(tǒng)的實(shí)時(shí)性。因此,研究一種高效的模式匹配算法對提高防火墻或入侵檢測系統(tǒng)的性能具有十分重要的意義。
　　 在事件

2、分析模塊中包括單模式及多模式匹配,其中典型單模式匹配算法包括Brute Force算法、克努特一莫里斯—普拉特算法(簡稱KMP算法)和Boyer-Moore算法(BM算法);多模式匹配算法包括Aho-Corasick自動機(jī)算法(AC算法)、通過AC算法和BM算法結(jié)合后的AC_BM算法以及AC_BMH算法,這些算法中,單模式匹配算法無法在同一次匹配中同時(shí)匹配多個(gè)模式串,多模式匹算法的AC算法無法實(shí)現(xiàn)跳躍功能。雖然AC_BM算法和AC_BM

3、H算法借鑒了單模式匹配算法中的跳躍功能,但是其跳躍的長度受到多模式串中的最短模式串長度限制,而且建立狀態(tài)樹時(shí)采用256個(gè)空間用于存儲跳轉(zhuǎn)的狀態(tài),其空間利用效率非常低。
　　 本文針對這些缺陷,提出了一種改進(jìn)的多模式匹配算法AC_SLYNDAY算法,該算法應(yīng)用了AC算法的有限自動機(jī)原理構(gòu)成模式樹,同時(shí)結(jié)合類似AC_BM算法的構(gòu)思,將SUNDAY算法的大幅度跳躍式搜索思想融合入AC算法中(SUNDAY算法的最大跳躍長度能超過其本身的

4、模式串長度),減少了匹配次數(shù),然而改進(jìn)后的算法在某些特殊情況下例如skip[I+m-1]＜skip[I+m]時(shí)可能出現(xiàn)低效,因而再次借鑒BMH算法的構(gòu)思對AC_SUNDAY算法進(jìn)行修正。無論是改進(jìn)的算法還是AC_BM算法,初始化后首先都需要構(gòu)造一個(gè)狀態(tài)樹,在構(gòu)造狀態(tài)樹時(shí),開辟的空間中多為O而真正儲存用于跳轉(zhuǎn)的狀態(tài)卻不多。由于此缺陷,在建立狀態(tài)樹時(shí)白白消耗了大量的系統(tǒng)內(nèi)存,因此勢必需要對這些空間進(jìn)行壓縮,本文中利用稀疏矩陣的存儲原理對存儲

5、模式進(jìn)行了改進(jìn),只需要犧牲微量的時(shí)間來換取大量的內(nèi)存空間釋放。
　　 最后利用隨機(jī)生成的模式串和文本串,分別在固定模式串?dāng)?shù)量,改變模式串長度、固定模式串長度,改變模式串?dāng)?shù)量以及空間性能進(jìn)行測試,實(shí)驗(yàn)測試表明改進(jìn)后的AC_SUNDAY算法具有如下優(yōu)勢:1)可以不受最大移動距離不能超過前綴樹中最短模式串的長度的限制,增大了不匹配時(shí)的跳躍距離;2)當(dāng)文本字符串中的字符并不存在于模式樹的任意子模式中時(shí),可以跳過這一字符,而從該字符的前面