時空高效的正則表達式匹配算法研究.pdf

1、網絡入侵檢測與防御系統(tǒng)(Network Intrusion Detection and Prevention Systems,NIDS/NIPS)是網絡安全防御的重要手段,即通過實時監(jiān)測網絡流量,檢查每個數(shù)據(jù)包的頭部信息和有效載荷(即數(shù)據(jù)包內容),識別和阻斷網絡可疑行為。NIDS/NIPS的核心是深度數(shù)據(jù)包檢測(Deep Packet Inspection,DPI),即采用特征匹配算法,將每個數(shù)據(jù)包內容與一組預定義的特征進行匹配。DPI

2、技術不僅應用于NIDS/NIPS,而且還應用于應用層數(shù)據(jù)包分類、P2P流量識別、基于內容的流量管理等。
　　 由于正則表達式具有更強的表達能力和靈活性,特征匹配已采用正則表達式匹配算法替代字符串匹配算法。正則表達式匹配算法采用有限自動機來表示多個正則表達式特征。有限自動機分為非確定型有限自動機(Nondeterministic Finite Automata,NFA)和確定型有限自動機(Deterministic Finite

3、Automata,DFA)。NFA具有存儲空間高效等優(yōu)點,但是存在匹配速度慢等缺點；而DFA具有時間高效等優(yōu)點,即匹配速度快,但是存在存儲空間開銷大等缺點。因此,正則表達式匹配算法的關鍵問題是如何設計時空高效的有限自動機。
　　 首先,本文提出了一種基于遷移邊融合DFA的正則表達式匹配算法,即在狀態(tài)融合DFA基礎上,采用優(yōu)先級將其有限自動機中的遷移邊進行融合,從而減少了DFA存儲空間開銷。實驗結果表明,與狀態(tài)融合DFA和原始DF

4、A相比,遷移邊融合DFA在存儲空間開銷方面分別減少15％～31％和25％～42％,并確保了正則表達式的匹配效率。其次,本文提出了一種基于智能有限自動機(SmartFiniteAutomata,SFA)的正則表達式匹配算法,即在擴展有限自動機(Extended Finite Automata,XFA)的分支遷移邊上增加額外的判斷操作指令,消除XFA的回退遷移邊,從而避免不必要的狀態(tài)遷移。實驗結果表明,與XFA相比,SFA在存儲空間開銷上減