基于位分割的K步長(zhǎng)多模式匹配算法的研究.pdf

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

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

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

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

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