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

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

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

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

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

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