1、隨著網(wǎng)絡(luò)技術(shù)的高速發(fā)展和互聯(lián)網(wǎng)的日益開放,網(wǎng)絡(luò)應(yīng)用日趨普及。與此同時,網(wǎng)絡(luò)帶來的攻擊行為也引發(fā)了人們對網(wǎng)絡(luò)安全問題的關(guān)注。作為維護(hù)網(wǎng)絡(luò)安全的重要手段,入侵檢測系統(tǒng)得到了廣泛的應(yīng)用。而模式匹配是入侵檢測系統(tǒng)中最重要的一種檢測技術(shù),其創(chuàng)新性和有效性將成為提高入侵檢測系統(tǒng)性能和效率的關(guān)鍵。
　　論文對入侵檢測系統(tǒng)進(jìn)行了一個簡單的概述,介紹了入侵檢測的一般過程和分類,并闡述了模式匹配在入侵檢測中的應(yīng)用。此外,論文還對幾種經(jīng)典的模式匹配算法

2、作了詳細(xì)的介紹,其中包括BF、KMP、BM等單模式匹配算法和AC、AC_BM等多模式匹配算法。
　　論文介紹了Bloom Filter的原理及應(yīng)用。Bloom Filter是一種基于多個哈希函數(shù)映射壓縮空間的數(shù)據(jù)結(jié)構(gòu),通過尋找一種優(yōu)化的哈希查找算法可以提高Bloom Filter的性能。針對現(xiàn)有哈希算法中鏈地址法處理沖突時存在查找效率低的問題,論文設(shè)計了一種改進(jìn)的哈希表查詢算法。經(jīng)分析和實際測試表明,該算法在不增加消耗的同時降低了

3、沖突時執(zhí)行查詢的查找長度,從而縮短了查詢響應(yīng)時間。
　　針對經(jīng)典AC算法構(gòu)建的狀態(tài)機(jī)內(nèi)存利用率低且需要頻繁訪問外存的問題,論文設(shè)計了一種改進(jìn)的K步長狀態(tài)機(jī)。設(shè)計算法主要由以下四個模塊組成:改進(jìn)的AC算法、文本轉(zhuǎn)換、映射機(jī)制和匹配查詢。其中,改進(jìn)的 AC算法對原 AC狀態(tài)機(jī)中各個狀態(tài)的輸出進(jìn)行了重新定義,映射機(jī)制則負(fù)責(zé)將改進(jìn)的AC狀態(tài)機(jī)中相應(yīng)的狀態(tài)信息映射到K步長狀態(tài)機(jī)中。通過這種映射機(jī)制,最終生成的K步長狀態(tài)機(jī)中只包含跳轉(zhuǎn)和輸出信

4、息,沒有失效函數(shù)。而且在狀態(tài)存儲時,改進(jìn)的K步長狀態(tài)機(jī)在原有鏈?zhǔn)酱鎯Φ幕A(chǔ)上,只保留出現(xiàn)過的子串輸入,對于鏈表中未出現(xiàn)的子串,則借助查詢算法進(jìn)行處理。因此,和原來的K步長狀態(tài)機(jī)相比,改進(jìn)的K步長狀態(tài)機(jī)占據(jù)更高的內(nèi)存優(yōu)勢。
　　盡管改進(jìn)的K步長狀態(tài)機(jī)解決了一些問題,但并沒有達(dá)到最優(yōu)的內(nèi)存資源利用率。為此,在它的基礎(chǔ)上,論文提出了一種基于位分割的K步長多模式匹配方法,即從位的角度出發(fā),將原先的一個狀態(tài)機(jī)分割成八個小狀態(tài)機(jī),每個狀態(tài)機(jī)可

5、以同時讀取K個輸入字符的K個比特位,當(dāng)所有子狀態(tài)機(jī)都輸出匹配信號時才確定匹配。該算法有兩個優(yōu)點:首先,子狀態(tài)機(jī)的每個狀態(tài)最多只有2K種輸入選擇,這使得內(nèi)存更加緊湊;其次,幾個子狀態(tài)機(jī)可以獨立并行工作,加快了模式查詢的速度。同時,為了避免一些不必要的查詢,待匹配的字符可以先進(jìn)入Bloom Filter引擎過濾出可疑字符,由于Bloom Filter存在假陽性誤判,過濾后的字符要進(jìn)行精確匹配。在文中,精確匹配由位分割狀態(tài)機(jī)來完成。二者的結(jié)合