面向深度包檢測(cè)的存儲(chǔ)高效的正則表達(dá)式匹配算法研究.pdf

1、隨著網(wǎng)絡(luò)及其應(yīng)用的迅猛發(fā)展，網(wǎng)絡(luò)安全已變得越來越重要。網(wǎng)絡(luò)入侵檢測(cè)和防御系統(tǒng)是網(wǎng)絡(luò)安全防御的主要手段，即通過實(shí)時(shí)監(jiān)測(cè)網(wǎng)絡(luò)流量，檢查和阻止網(wǎng)絡(luò)攻擊。而深度包檢測(cè)(DPI，Deep Packet Inspection)是網(wǎng)絡(luò)入侵檢測(cè)和防御系統(tǒng)的核心，它定義了一組特征規(guī)則集，不僅檢查數(shù)據(jù)包頭，也檢查數(shù)據(jù)包的有效荷載。由于正則表達(dá)式具有靈活、高效等特點(diǎn)，目前已廣泛用于表示特征規(guī)則集。傳統(tǒng)的正則表達(dá)式匹配算法實(shí)現(xiàn)方式主要基于非確定有限自動(dòng)機(jī)(NF

2、A，Nondeterministic Finite Automaton)和確定有限自動(dòng)機(jī)(DFA，Deterministic Finite
　　 Automaton)。
　　 正則表達(dá)式匹配算法面臨高性能挑戰(zhàn)。一方面，為了達(dá)到數(shù)據(jù)包線速匹配，研究者利用現(xiàn)代嵌入式存儲(chǔ)器，提出了面向硬件實(shí)現(xiàn)的正則表達(dá)式匹配算法。另一方面，基于硬件的正則表達(dá)式匹配算法實(shí)現(xiàn)存在嵌入式片上存儲(chǔ)空間受限的問題，難以適應(yīng)日益增大的特征規(guī)則集。因此，設(shè)

3、計(jì)一種快速且存儲(chǔ)高效的正則表達(dá)式匹配算法是高性能深度包檢測(cè)的關(guān)鍵。
　　 本文詳細(xì)闡述了正則表達(dá)式匹配算法的研究現(xiàn)狀，分析了傳統(tǒng)正則表達(dá)式匹配算法NFA和DFA無法滿足高性能需求的原因，并研究了現(xiàn)有一些存儲(chǔ)高效的正則表達(dá)式匹配算法的特點(diǎn)。針對(duì)目前缺乏相關(guān)工作對(duì)已有正則表達(dá)式匹配算法進(jìn)行綜合性能評(píng)估的問題，本文采用C++實(shí)現(xiàn)了DFA、mDFA、D2FA、CD2FA和XFA等算法，建立了一個(gè)正則表達(dá)式匹配算法的性能評(píng)估平臺(tái)。同時(shí)，采

4、用Snort的規(guī)則集綜合評(píng)估了這些算法的存儲(chǔ)空間、匹配效率以及可伸縮性。評(píng)估實(shí)驗(yàn)結(jié)果顯示XFA是最好的存儲(chǔ)空間和匹配效率的折衷算法。在正則表達(dá)式匹配算法評(píng)估工作基礎(chǔ)上，本文提出了一種基于字母表壓縮的擴(kuò)展有限自動(dòng)機(jī)(ACFA，Alphabet-Compressed—Based Extend Finite Automaton)，即采用啟發(fā)式策略合理劃分XFA的狀態(tài)集合，對(duì)所劃分的各個(gè)狀態(tài)集分別建立一張字母壓縮表，并利用這些字母壓縮表壓縮XF