本文選題：模式匹配 + 布爾函數�。� 參考：《哈爾濱理工大學》2017年碩士論文

【摘要】：目前,計算機和網絡發(fā)展越來越迅速,隨之而來的網絡安全問題也越來越突出�，F代網絡安全應用通常采用深層數據包檢測來識別惡意流量,如基于網絡的入侵檢測系統(NIDS)和防火墻。防火墻是被動防御保護技術,無法滿足大量復雜變化的數據。入侵檢測系統作為防火墻的補充,在網絡安全領域發(fā)揮著越來越重要的作用。在入侵檢測系統中,檢測的性能依賴于攻擊簽名的準確性與多樣性,因此攻擊簽名是入侵檢測實現的關鍵。在網絡安全中理想的模式匹配算法應用必須滿足兩個要求:時間效率和空間效率。由于入侵檢測系統和防火墻通常部署在高速的網絡節(jié)點上,要求處理每個數據的時間很小以便于滿足高速網絡的數據包處理速度,而空間效率要求算法運行使用的存儲器空間盡量小。同時,目前大部分模式匹配只考慮包含非捕獲組的正則表達式,不支持子匹配提取。子匹配提取的現有的解決方案是基于非確定性有限自動機(Nondeterministic Finite Automaton,NFA)或遞歸回溯的。NFA空間復雜度低,并且能夠提取緊湊的內存足跡子匹配,但是時間復雜度高。有序二元決策圖(Ordered Binary Decision Diagram,OBDD)可以對信息進行高效壓縮,從而有效地處理大規(guī)模問題。本文結合OBDD的數據結構特點和模式匹配算法處理簽名匹配。本文重點研究了模式匹配算法的問題,主要工作為以下幾個方面:使用三個向量布爾變量(?),(?)和(?)為NFA (Q,Σ,δ,q0,Fin)定義四個布爾函數,然后使用OBDD來表示和操作布爾函數,對基于不確定有限自動機(NFA)的模式匹配進行改進,提出NFA-OBDD,提高基于NFA的簽名匹配的時間效率。使用標記來區(qū)分正則表達式中的捕獲組,并擴展Thompson的NFA構造方法來支持正則表達式。用布爾函數表示標記的NFA,并采用OBDD來操作布爾函數,提出Submatch-OBDD,提高子匹配提取的時間效率,以滿足部署在高速的網絡上的Snort入侵檢測系統實現快速匹配惡意流量的需求。實驗結果表明,提出的NFA-OBDD是正確且高效的,優(yōu)于現有的方法約一至三個數量級,同時避免內存爆炸和抵抗已知算法復雜度的攻擊。同時,Submatch-OBDD有效提高子匹配提取效率,通過網絡流量,合成的流量,和企業(yè)的事件日志來測試Submatch-OBDD的時間效率和空間效率,當把模式組合的時候,Submatch-OBDD達到了理想的性能。在最好的情況下,Submatch-OBDD的速度比RE2和PCRE快一到兩個數量級。
[Abstract]:At present, computers and networks are developing more and more rapidly, and the problems of network security are becoming more and more prominent. Modern network security applications usually use deep packet detection to identify malicious traffic, such as network based intrusion detection systems (NIDSs) and firewalls. Firewall is a passive defense protection technology, can not meet a large number of complex changes of data. Intrusion detection system (IDS), as a supplement of firewall, plays a more and more important role in the field of network security. In intrusion detection systems, the performance of detection depends on the accuracy and diversity of attack signatures, so attack signatures are the key to the implementation of intrusion detection. The application of the ideal pattern matching algorithm in network security must meet two requirements: time efficiency and spatial efficiency. Because intrusion detection systems and firewalls are usually deployed on high-speed network nodes, the time required to process each data is very small in order to meet the packet processing speed of high-speed networks. Space efficiency requires that the memory space used by the algorithm is as small as possible. At present, most pattern matching only considers regular expressions containing uncaptured groups, and does not support submatching extraction. The existing solutions for submatching extraction are based on nondeterministic Finite automaton (NFAs) or recursive backtracking. NFA has a low space complexity, and it can extract compact memory footprint submatches, but the time complexity is high. Ordered Binary Decision Diagram can efficiently compress information and deal with large-scale problems effectively. This paper deals with signature matching based on OBDD data structure and pattern matching algorithm. This paper focuses on the problem of pattern matching algorithm. The main work is as follows: using three vector Boolean variables. ) Four Boolean functions are defined for NFA Q, 危, 未 Q 0, and then OBDD is used to express and manipulate Boolean functions. The pattern matching based on uncertain finite automata is improved. NFA-OBDDs are proposed to improve the time efficiency of signature matching based on NFA. Use tags to distinguish capture groups in regular expressions and extend Thompson's NFA constructor to support regular expressions. The marked NFAs are represented by Boolean functions, and Boolean functions are operated by OBDD. Submatch-OBDDs are proposed to improve the time efficiency of submatch extraction, so as to meet the requirements of Snort intrusion detection system deployed on high-speed networks to quickly match malicious traffic. Experimental results show that the proposed NFA-OBDD is correct and efficient, which is superior to the existing methods about one to three orders of magnitude, while avoiding memory explosion and resisting attacks of known algorithm complexity. At the same time, Submatch-OBDD can improve the extraction efficiency of submatch-OBDD, and test the time efficiency and spatial efficiency of Submatch-OBDD through network traffic, synthetic traffic, and enterprise event log. When the patterns are combined, Submatch-OBDD achieves the ideal performance. In the best case, the speed of submatch-OBDD is one or two orders of magnitude faster than that of RE2 and PCRE.
【學位授予單位】：哈爾濱理工大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP393.08

【相似文獻】

相關期刊論文 前10條

1 劉省賢;;模式匹配算法及其在農作物嫁接中的作用[J];安徽農業(yè)科學;2009年19期

2 宋華,戴一奇;入侵檢測中一類允許誤差的多模式匹配算法[J];清華大學學報(自然科學版);2003年07期

3 伊靜,劉培玉;入侵檢測中模式匹配算法的研究[J];計算機應用與軟件;2005年01期

4 彭詩力,譚漢松;基于特征值的多模式匹配算法及硬件實現[J];計算機工程與應用;2005年01期

5 張春生;張曉英;王國忠;;字符串隨機探測模式匹配算法[J];內蒙古民族大學學報(自然科學版);2007年06期

6 林南暉;張國軍;;對模式匹配算法的存儲優(yōu)化研究[J];中國海洋大學學報(自然科學版);2008年S1期

7 王杰;劉亞賓;孫珂珂;;一種快速高效的模式匹配算法的應用研究[J];計算機工程與應用;2008年32期

8 周延森;汪永好;;網絡入侵檢測系統模式匹配算法研究[J];計算機工程與設計;2008年07期

9 劉磊;;多模式匹配算法的研究與優(yōu)化[J];濰坊學院學報;2008年02期

10 任叢美;阮冬茹;郭彥穎;;入侵檢測模式匹配算法的研究與改進[J];中國新技術新產品;2008年16期

相關會議論文 前10條

1 張曉利;周榮輝;;多模式匹配算法在協議識別中的應用[A];中國電子學會第十六屆信息論學術年會論文集[C];2009年

2 佟冰;張忠平;宋麗;;一種改進的多源模式匹配算法[A];2005年全國理論計算機科學學術年會論文集[C];2005年

3 王德正;;網絡入侵檢測系統中模式匹配算法的研究與改進[A];計算機技術與應用進展·2007——全國第18屆計算機技術與應用（CACIS）學術會議論文集[C];2007年

4 朱艷;許家s，

本文編號：1970592