面向網絡入侵檢測的正則表達式DFA優(yōu)化技術研究
本文關鍵詞:面向網絡入侵檢測的正則表達式DFA優(yōu)化技術研究,由筆耕文化傳播整理發(fā)布。
【摘要】:近些年,隨著網絡的迅猛發(fā)展,網絡逐漸大眾化,特別是近兩年,網絡的速度不斷增快,很多網絡程序不斷開發(fā)出來。伴隨多種多樣的網絡程序的出現(xiàn),也出現(xiàn)了更多的針對網絡應用層的攻擊。2013年,知名度高、用戶數(shù)量龐大的支付寶和財付通均遭遇了黑客攻擊,引發(fā)了人們對網絡安全防范的重視。以往,利用防火墻抵抗入侵是最為普遍的入侵防御手段。這種方式應用在內網與外網之間,進行防御,對網絡數(shù)據進行檢測。但是,面對多樣和多方面的新型網絡攻擊,防火墻技術并不能進行有效的防御和抵抗,容易導致?lián)砣蛘咭绯?而且如果網絡入侵是通過合法端口而進行的也很難進行有效的防御,對待內部主動發(fā)起連接的入侵一般很難防御等缺點。因此,近年來,主要應用于應用層上的網絡入侵檢測方式由此產生。近年來,網絡安全領域的研究人員越來越多的將研究方向集中在如何提高深度包檢測的效率。正則表達式由于其敏捷性與適應性慢慢地代替了原有的匹配方式因而被廣泛地應用于各種入侵檢測系統(tǒng)中。正則表達式匹配分為基于確定性的正則表達式匹配和基于非確定性的正則表達式匹配。兩相比較,DFA匹配速度更快,但需要占用更大的空間,NFA可以節(jié)省空間,但匹配的速度卻不盡人意。但是,由于NFA的匹配是不確定的,因此結果也可能的多種情況同時存在,匹配效率會大大降低,DFA的匹配是確定的,其結果也是唯一的,而在現(xiàn)實的網絡世界中,匹配效率是十分關鍵的,因此,DFA由于其高效率的匹配過程而得到了廣泛的應用,但是由于DFA的匹配與NFA不同,DFA是確定化的匹配,因此,DFA在匹配過程中需要包含全部的可能性,因此DFA狀態(tài)轉移圖中的每一個結點均包含了全部可能的狀態(tài)轉移邊。另外由于正則表達式的長度限制會使DFA的狀態(tài)數(shù)量呈指數(shù)增長,導致狀態(tài)爆炸,同時對存儲空間的需求也會增加。本文深入分析了DFA算法的原理,得出了該算法的優(yōu)點與缺點,根據該算法的缺點分析了優(yōu)化的方向,設計高性能的正則表達式壓縮算法,在上述前期工作的基礎上,著重研究了DDFA算法,并且編程實現(xiàn)了DDFA算法,并通過對規(guī)則集的實驗比較了DDFA算法與DFA算法之間的異同,并且通過實驗發(fā)現(xiàn)了該算法存在著匹配效率較低的缺點,隨后,本文將DFA算法所具備的優(yōu)點與DDFA算法所具備的優(yōu)點融合在了一起,設計并實現(xiàn)了一種基于DFA的正則表達式優(yōu)化算法,對DFA進行了有效的壓縮,同時也盡可能地保證了算法的匹配效率不會下降太多。最后,我們通過實驗驗證了該算法的匹配效率,該算法對空間的占用情況,該算法的運行時間,并分別與DFA算法進行了對比,得出最后的結論。
【關鍵詞】:網絡入侵檢測 正則表達式 DFA優(yōu)化技術
【學位授予單位】:吉林大學
【學位級別】:碩士
【學位授予年份】:2016
【分類號】:TP393.08
【目錄】:
- 摘要4-6
- Abstract6-11
- 第1章 緒論11-15
- 1.1 研究背景11-12
- 1.2 國內外研究現(xiàn)狀12-13
- 1.3 論文主要工作13-14
- 1.4 論文組織結構14-15
- 第2章 正則表達式15-22
- 2.1 概述15
- 2.2 正則表達式15-16
- 2.3 自動機16-17
- 2.4 非確定性有限自動機17-19
- 2.5 確定性有限自動機19-20
- 2.6 NFA與DFA的對比20-21
- 2.7 本章小結21-22
- 第3章 入侵檢測系統(tǒng)22-27
- 3.1 入侵檢測系統(tǒng)22-25
- 3.1.1 入侵檢測系統(tǒng)結構22-23
- 3.1.2 入侵檢測系統(tǒng)原理23-25
- 3.2 Snort25-26
- 3.3 Bro26
- 3.4 本章小結26-27
- 第4章 基于延遲匹配的正則表達式匹配算法27-38
- 4.1 DFA不足的分析27
- 4.2 DFA優(yōu)化方法27-30
- 4.3 算法流程圖30-32
- 4.4 算法描述32
- 4.5 實驗與結果分析32-37
- 4.5.1 狀態(tài)轉移圖實驗32-34
- 4.5.2 算法的壓縮性能測試34-37
- 4.6 本章小結37-38
- 第5章 DFA壓縮算法38-52
- 5.1 引言38
- 5.2 正則表達式壓縮算法38-44
- 5.2.1 算法背景與設計思想38-40
- 5.2.2 算法流程40-43
- 5.2.3 算法描述43-44
- 5.3 系統(tǒng)結構設計與實現(xiàn)44-48
- 5.3.1 正則表達式轉NFA模塊45-48
- 5.3.2 NFA轉換DFA模塊48
- 5.3.3 DFA優(yōu)化壓縮模塊48
- 5.4 實驗與結果48-51
- 5.4.1 實驗環(huán)境48-49
- 5.4.2 實驗一:算法匹配效果測試49-50
- 5.4.3 實驗二:算法空間壓縮性能測試50-51
- 5.4.4 實驗三:算法運行時間測試51
- 5.5 本章小結51-52
- 第6章 總結與展望52-54
- 6.1 本文工作總結52
- 6.2 展望52-54
- 參考文獻54-56
- 作者簡介及在學期間取得的科研成果56-57
- 致謝57
【相似文獻】
中國期刊全文數(shù)據庫 前10條
1 王甲春;;正則表達式的五個良好習慣[J];中文信息;2003年11期
2 白紅哲,馬立勇;基于正則表達式的話務報告處理軟件的實現(xiàn)[J];通信管理與技術;2005年02期
3 孟巖;;一夫當關——《精通正則表達式》書評[J];程序員;2007年08期
4 ;新書上架[J];程序員;2007年10期
5 路個的;;請個伙伴,助你成長為正則表達式高手[J];電腦愛好者;2008年23期
6 余晟;;正則表達式隨筆[J];程序員;2008年03期
7 余晟;;正則表達式隨筆(續(xù))[J];程序員;2008年09期
8 周健鋒;;正則表達式的強大功能[J];電腦知識與技術;2009年16期
9 夏陽陽;李建華;;新疆勘探生產經營管理系統(tǒng)中正則表達式的應用[J];辦公自動化;2009年20期
10 李國晶;王景強;;淺析正則表達式[J];科技資訊;2010年04期
中國重要會議論文全文數(shù)據庫 前4條
1 管杰裕;;正則表達式在氣象信息處理中的應用[A];2005年廣西氣象學會學術年會論文集[C];2005年
2 劉琪;牛文靜;;正則表達式在惡意代碼動態(tài)分析中的應用[A];2009通信理論與技術新發(fā)展——第十四屆全國青年通信學術會議論文集[C];2009年
3 王輝;丁明君;楊進;;正則表達式在企業(yè)信息管理開發(fā)中的應用[A];2010年MIS/S&A學術交流會議論文集(中國造船工程學會學術論文集)[C];2010年
4 田珂;趙國鴻;;利用TCAM與正則表達式對郵件協(xié)議進行二次識別的思想研究[A];第十六屆計算機工程與工藝年會暨第二屆微處理器技術論壇論文集[C];2012年
中國重要報紙全文數(shù)據庫 前1條
1 彭福祥 張鈞;ASP.NET基本數(shù)值處理技巧[N];計算機世界;2006年
中國博士學位論文全文數(shù)據庫 前1條
1 彭坤楊;基于TCAM的高速可擴展的正則表達式匹配技術[D];中國科學技術大學;2013年
中國碩士學位論文全文數(shù)據庫 前10條
1 韓家寶;圖數(shù)據搜索引擎Trinity中正則表達式匹配子系統(tǒng)的設計與實現(xiàn)[D];哈爾濱工業(yè)大學;2015年
2 徐成成;基于兩級存儲的正則表達式匹配技術研究[D];國防科學技術大學;2013年
3 宮陽陽;面向網絡安全的多維正則表達式匹配算法研究[D];解放軍信息工程大學;2014年
4 邵翔宇;正則表達式匹配存儲優(yōu)化技術研究[D];解放軍信息工程大學;2015年
5 歷博源;面向網絡入侵檢測的正則表達式DFA優(yōu)化技術研究[D];吉林大學;2016年
6 李哲夫;正則表達式在電信業(yè)務處理中的應用研究[D];暨南大學;2008年
7 范慧萍;基于正則表達式的協(xié)議識別研究與實現(xiàn)[D];國防科學技術大學;2007年
8 段海生;基于正則表達式的深度包壓縮算法研究[D];西安電子科技大學;2010年
9 姜英杰;支持正則表達式的文本匹配優(yōu)化算法[D];東北大學;2012年
10 張潔坤;時空高效的正則表達式匹配算法研究[D];湖南大學;2010年
本文關鍵詞:面向網絡入侵檢測的正則表達式DFA優(yōu)化技術研究,由筆耕文化傳播整理發(fā)布。
,本文編號:417622
本文鏈接:http://sikaile.net/guanlilunwen/ydhl/417622.html