基于多步投機(jī)的正則表達(dá)式匹配算法的研究.pdf

1、網(wǎng)絡(luò)防御系統(tǒng)(IPS)是維護(hù)網(wǎng)絡(luò)安全的有效方式。IPS的核心是深度數(shù)據(jù)包檢測(DPI)?，F(xiàn)在網(wǎng)絡(luò)在以極快的速度發(fā)展。IPS的性能要跟上線速需要借助多核或者硬件技術(shù)。
　　 由于正則表達(dá)式的表達(dá)能力更強(qiáng)更靈活,特征規(guī)則多用正則表達(dá)式匹配算法實(shí)現(xiàn)匹配。正則表達(dá)式匹配算法用有限自動機(jī)來完成。有限自動機(jī)分為確定有限自動機(jī)(DFA)和非確定有限自動機(jī)(NFA)。DFA較NFA匹配速率更快,更常用。但是DFA的處理速率還是難以滿足線速處理的

2、要求,特別是DFA每次只能匹配一個字符產(chǎn)生延時(shí)成為IPS的性能瓶頸。因此,研究基于DFA的高效正則表達(dá)式匹配算法具有重要意義。接著,本文介紹了幾種基于硬件的正則表達(dá)式匹配算法,如基于多核技術(shù)的投機(jī)正則表達(dá)式匹配算法(SPPM)等,并分析了它們的理論依據(jù)及算法關(guān)鍵,還指明了各自的優(yōu)點(diǎn)及不足。
　　 針對上述算法的不足之處,通過分析和實(shí)驗(yàn)驗(yàn)證Snort規(guī)則集特征,本文在正則表達(dá)式匹配算法中運(yùn)用到“投機(jī)”的概念,輔以多核技術(shù),將輸入字

3、符串分為多段并行匹配,如果投機(jī)失敗會在后期進(jìn)行糾正。圍繞提高投機(jī)成功率這個算法關(guān)鍵問題,本文提出了基于多步投機(jī)的正則表達(dá)式匹配算法(MSPPM),有效提高投機(jī)成功率,縮短了并行匹配外對DFA的訪問次數(shù),減少延時(shí)。通過仿真比較實(shí)驗(yàn)可見,MSPPM的并行迭代次數(shù)和訪問DFA的次數(shù)相對SPPM減少約15％,從而進(jìn)一步縮短匹配時(shí)由訪問DFA產(chǎn)生的內(nèi)存延時(shí)。時(shí)間性能方面,MSPPM相對傳統(tǒng)DFA算法的加速率平均提高約15％,算法匹配速率更高。所以