時(shí)空高效的正則表達(dá)式匹配算法研究.pdf

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

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

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

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