面向深度包檢測的存儲高效的正則表達式匹配算法研究.pdf

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

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

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

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