基于OBDD的模式匹配算法研究.pdf

1、目前，計算機(jī)和網(wǎng)絡(luò)發(fā)展越來越迅速，隨之而來的網(wǎng)絡(luò)安全問題也越來越突出。現(xiàn)代網(wǎng)絡(luò)安全應(yīng)用通常采用深層數(shù)據(jù)包檢測來識別惡意流量，如基于網(wǎng)絡(luò)的入侵檢測系統(tǒng)(NIDS)和防火墻。防火墻是被動防御保護(hù)技術(shù)，無法滿足大量復(fù)雜變化的數(shù)據(jù)。入侵檢測系統(tǒng)作為防火墻的補(bǔ)充，在網(wǎng)絡(luò)安全領(lǐng)域發(fā)揮著越來越重要的作用。
　　在入侵檢測系統(tǒng)中，檢測的性能依賴于攻擊簽名的準(zhǔn)確性與多樣性，因此攻擊簽名是入侵檢測實(shí)現(xiàn)的關(guān)鍵。在網(wǎng)絡(luò)安全中理想的模式匹配算法應(yīng)用必須滿足

2、兩個要求:時間效率和空間效率。由于入侵檢測系統(tǒng)和防火墻通常部署在高速的網(wǎng)絡(luò)節(jié)點(diǎn)上，要求處理每個數(shù)據(jù)的時間很小以便于滿足高速網(wǎng)絡(luò)的數(shù)據(jù)包處理速度，而空間效率要求算法運(yùn)行使用的存儲器空間盡量小。同時，目前大部分模式匹配只考慮包含非捕獲組的正則表達(dá)式，不支持子匹配提取。子匹配提取的現(xiàn)有的解決方案是基于非確定性有限自動機(jī)(Nondeterministic FiniteAutomaton，NFA)或遞歸回溯的。NFA空間復(fù)雜度低，并且能夠提取緊湊

3、的內(nèi)存足跡子匹配，但是時間復(fù)雜度高。
　　有序二元決策圖(Ordered Binary Decision Diagram，OBDD)可以對信息進(jìn)行高效壓縮，從而有效地處理大規(guī)模問題。本文結(jié)合OBDD的數(shù)據(jù)結(jié)構(gòu)特點(diǎn)和模式匹配算法處理簽名匹配。
　　本文重點(diǎn)研究了模式匹配算法的問題，主要工作為以下幾個方面:
　　使用三個向量布爾變量→x，→y和→i為NFA(Q，∑，δ，q0，F(xiàn)in)定義四個布爾函數(shù)，然后使用OBDD來表示

4、和操作布爾函數(shù)，對基于不確定有限自動機(jī)(NFA)的模式匹配進(jìn)行改進(jìn)，提出NFA-OBDD，提高基于NFA的簽名匹配的時間效率。
　　使用標(biāo)記來區(qū)分正則表達(dá)式中的捕獲組，并擴(kuò)展Thompson的NFA構(gòu)造方法來支持正則表達(dá)式。
　　用布爾函數(shù)表示標(biāo)記的NFA，并采用OBDD來操作布爾函數(shù)，提出Submatch-OBDD，提高子匹配提取的時間效率，以滿足部署在高速的網(wǎng)絡(luò)上的Snort入侵檢測系統(tǒng)實(shí)現(xiàn)快速匹配惡意流量的需求。