本文關(guān)鍵詞：正則表達式匹配存儲優(yōu)化技術(shù)研究，由筆耕文化傳播整理發(fā)布。

【摘要】：網(wǎng)絡安全問題成為關(guān)乎我國國計民生的大事,基于深度包檢測(Deep Packet Inspection,DPI)技術(shù)的入侵檢測系統(tǒng)(Intrusion Detection System, IDS)作為網(wǎng)絡防護的重要手段,近年來得到廣泛應用。正則表達式因其強大的功能和靈活表達手段成為DPI的核心算法。隨著網(wǎng)絡安全攻防雙方的發(fā)展,攻擊模式的不斷復雜化和網(wǎng)絡業(yè)務及應用的日新月異,IDS中正則表達式匹配技術(shù)仍存在諸多問題,其中最重要的是高速低存儲的正則表達式匹配算法的設(shè)計。基于確定型有限狀態(tài)自動機(Deterministic Finite Automata, DFA)的正則表達式算法因其線性的匹配速度得到廣泛應用,但存在部分類型的規(guī)則編譯時會產(chǎn)生狀態(tài)爆炸問題、存儲空間急劇增長的情況。本文從DFA的構(gòu)建過程出發(fā),分析當前算法的改進思路和存在的不足,對DFA算法進行存儲優(yōu)化,設(shè)計高速低存儲的正則表達式算法。本文主要工作如下：多維立方體自動機(Multi-dimensional Finite Automata, MFA)利用多維結(jié)構(gòu)的對稱性,僅保留坐標軸和當前所處位置信息,通過狀態(tài)的實時更新,降低存儲空間。針對MFA適用規(guī)則類型較少問題,結(jié)合入侵檢測系統(tǒng)克林閉包規(guī)則的特點,設(shè)計了擴展多維有限自動機算法(eXtend Multi-dimensional Finite Automata, XMFA)。對不滿足對稱性的結(jié)構(gòu),進行結(jié)構(gòu)調(diào)整,增加輔助變量,增加適用的規(guī)則類型；為了完成快速狀態(tài)更新,設(shè)計簡單完備的狀態(tài)跳轉(zhuǎn)指針。理論分析和仿真實驗表明,XMFA與DFA數(shù)量級相當?shù)钠ヅ鋾r間,同時占用存儲空間比基于DFA算法大大減少。采用分組算法解決DFA狀態(tài)爆炸問題,隨著分組數(shù)目的增加,時間效率大大降低。基于正則表達式引擎輸入驅(qū)動特性理論,提出了驅(qū)動特性有限自動機(Drive Character Finite Automata, DCFA)分組算法。DCFA分組算法將規(guī)則類型作為正則表達式分組的依據(jù),根據(jù)規(guī)則類型確定各分組采用的改進算法,保證各個類型的規(guī)則集不出現(xiàn)狀態(tài)爆炸問題。實驗表明,在簡單規(guī)則情況下,DCFA用更少的分組數(shù)目達到Multiple DFAs(mDFA)算法存儲壓縮效果,提高了匹配效率。與經(jīng)典的改進算法相比,DCFA預處理時間和存儲空間比Hybrid-FA、D2FA算法降低了2～3個數(shù)量級；匹配時間與DFA算法相當。分析當前入侵檢測系統(tǒng)Perl兼容的正則表達式(Perl Compatible Regular Expressions, PCRE)規(guī)則特點,基于驅(qū)動特性的分組方案和擴展多維有限自動機結(jié)構(gòu),設(shè)計一種可以應用于當前入侵檢測系統(tǒng)的模板有限自動機(Templates Based Finite Automata, TFA)匹配算法。TFA算法根據(jù)IDS規(guī)則類型特點,設(shè)計規(guī)則分組模板,然后根據(jù)規(guī)則模板將規(guī)則集劃分為若干個規(guī)則子集,各個規(guī)則子集根據(jù)系統(tǒng)結(jié)構(gòu)分別構(gòu)建高速低存儲的匹配引擎。實驗表明,與經(jīng)典的改進算法相比,TFA預處理時間和存儲空間比Hybrid-FA、D2FA算法降低了幾個數(shù)量級；匹配時間與DFA算法數(shù)量級相當。
【關(guān)鍵詞】：入侵檢測系統(tǒng) 正則表達式匹配 確定性有限自動機 擴展多維有限自動機 分組算法 規(guī)則驅(qū)動特性 驅(qū)動特性有限自動機 模板有限自動機
【學位授予單位】：解放軍信息工程大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP393.08
【目錄】：

• 摘要4-6
• Abstract6-12
• 第一章 緒論12-24
• 1.1 課題研究背景及研究意義12-14
• 1.2 正則表達式匹配相關(guān)研究14-16
• 1.2.1 正則表達式與有限自動機14-15
• 1.2.2 正則表達式匹配15-16
• 1.3 問題描述及研究現(xiàn)狀16-21
• 1.3.1 DFA狀態(tài)爆炸問題16-18
• 1.3.2 DFA改進算法綜述18-21
• 1.4 論文的主要內(nèi)容和章節(jié)安排21-24
• 1.4.1 主要內(nèi)容21-22
• 1.4.2 章節(jié)安排22-24
• 第二章 多維擴展有限自動機XMFA24-38
• 2.1 引言24
• 2.2 多維立方體有限自動機MFA24-26
• 2.2.1 MFA簡介24-25
• 2.2.2 MFA規(guī)則受限問題25-26
• 2.3 擴展多維有限自動機模型26-30
• 2.3.1 字符重疊26-27
• 2.3.2 克林閉包27-29
• 2.3.3 精確字符串29
• 2.3.4 起始標記29-30
• 2.4 XMFA算法設(shè)計30-35
• 2.4.1 XMFA激活狀態(tài)設(shè)計31-32
• 2.4.2 規(guī)則預處理32-34
• 2.4.3 字符匹配過程34-35
• 2.5 仿真分析35-37
• 2.6 本章小結(jié)37-38
• 第三章 基于驅(qū)動特性的分組算法DCFA38-48
• 3.1 引言38
• 3.2 正則匹配引擎的驅(qū)動特性38-40
• 3.3 DCFA算法設(shè)計40-44
• 3.3.1 規(guī)則分組42
• 3.3.2 匹配引擎構(gòu)造42-43
• 3.3.3 匹配過程43-44
• 3.4 仿真分析44-46
• 3.5 本章小結(jié)46-48
• 第四章 模板有限自動機TFA48-58
• 4.1 引言48
• 4.2 PCRE規(guī)則48-50
• 4.3 TFA算法設(shè)計50-54
• 4.3.1 規(guī)則模板制定與規(guī)則分組51-52
• 4.3.2 引擎構(gòu)造和存儲空間52-53
• 4.3.3 字符匹配過程53-54
• 4.4 仿真分析54-56
• 4.5 本章小結(jié)56-58
• 第五章 結(jié)束語58-60
• 5.1 論文主要的創(chuàng)新點和貢獻58-59
• 5.2 下一步工作59-60
• 致謝60-62
• 參考文獻62-68
• 作者簡歷68

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前6條

1 賀煒;郭云飛;扈紅超;;基于狀態(tài)約束的大規(guī)模正則表達式匹配算法[J];通信學報;2013年10期

2 喬登科;王卿;柳廳文;孫永;郭莉;;基于狀態(tài)分組的高效i-DFA構(gòu)造技術(shù)[J];通信學報;2013年08期

3 張大方;張潔坤;黃昆;;一種基于智能有限自動機的正則表達式匹配算法[J];電子學報;2012年08期

4 張樹壯;羅浩;方濱興;云曉春;;一種面向網(wǎng)絡安全檢測的高性能正則表達式匹配算法[J];計算機學報;2010年10期

5 楊毅夫;劉燕兵;劉萍;郭牧怡;郭莉;;正則表達式的DFA壓縮算法[J];通信學報;2009年S1期

6 徐乾;鄂躍鵬;葛敬國;錢華林;;深度包檢測中一種高效的正則表達式壓縮算法[J];軟件學報;2009年08期

中國博士學位論文全文數(shù)據(jù)庫 前1條

1 張樹壯;面向網(wǎng)絡安全的高性能特征匹配技術(shù)研究[D];哈爾濱工業(yè)大學;2011年

  本文關(guān)鍵詞：正則表達式匹配存儲優(yōu)化技術(shù)研究，由筆耕文化傳播整理發(fā)布。

，

本文編號：317434