本文選題：模式匹配 + 布爾函數(shù)　； 參考：《哈爾濱理工大學(xué)》2017年碩士論文

【摘要】：目前,計(jì)算機(jī)和網(wǎng)絡(luò)發(fā)展越來越迅速,隨之而來的網(wǎng)絡(luò)安全問題也越來越突出�，F(xiàn)代網(wǎng)絡(luò)安全應(yīng)用通常采用深層數(shù)據(jù)包檢測來識別惡意流量,如基于網(wǎng)絡(luò)的入侵檢測系統(tǒng)(NIDS)和防火墻。防火墻是被動防御保護(hù)技術(shù),無法滿足大量復(fù)雜變化的數(shù)據(jù)。入侵檢測系統(tǒng)作為防火墻的補(bǔ)充,在網(wǎng)絡(luò)安全領(lǐng)域發(fā)揮著越來越重要的作用。在入侵檢測系統(tǒng)中,檢測的性能依賴于攻擊簽名的準(zhǔn)確性與多樣性,因此攻擊簽名是入侵檢測實(shí)現(xiàn)的關(guān)鍵。在網(wǎng)絡(luò)安全中理想的模式匹配算法應(yīng)用必須滿足兩個要求:時間效率和空間效率。由于入侵檢測系統(tǒng)和防火墻通常部署在高速的網(wǎng)絡(luò)節(jié)點(diǎn)上,要求處理每個數(shù)據(jù)的時間很小以便于滿足高速網(wǎng)絡(luò)的數(shù)據(jù)包處理速度,而空間效率要求算法運(yùn)行使用的存儲器空間盡量小。同時,目前大部分模式匹配只考慮包含非捕獲組的正則表達(dá)式,不支持子匹配提取。子匹配提取的現(xiàn)有的解決方案是基于非確定性有限自動機(jī)(Nondeterministic Finite Automaton,NFA)或遞歸回溯的。NFA空間復(fù)雜度低,并且能夠提取緊湊的內(nèi)存足跡子匹配,但是時間復(fù)雜度高。有序二元決策圖(Ordered Binary Decision Diagram,OBDD)可以對信息進(jìn)行高效壓縮,從而有效地處理大規(guī)模問題。本文結(jié)合OBDD的數(shù)據(jù)結(jié)構(gòu)特點(diǎn)和模式匹配算法處理簽名匹配。本文重點(diǎn)研究了模式匹配算法的問題,主要工作為以下幾個方面:使用三個向量布爾變量(?),(?)和(?)為NFA (Q,Σ,δ,q0,Fin)定義四個布爾函數(shù),然后使用OBDD來表示和操作布爾函數(shù),對基于不確定有限自動機(jī)(NFA)的模式匹配進(jìn)行改進(jìn),提出NFA-OBDD,提高基于NFA的簽名匹配的時間效率。使用標(biāo)記來區(qū)分正則表達(dá)式中的捕獲組,并擴(kuò)展Thompson的NFA構(gòu)造方法來支持正則表達(dá)式。用布爾函數(shù)表示標(biāo)記的NFA,并采用OBDD來操作布爾函數(shù),提出Submatch-OBDD,提高子匹配提取的時間效率,以滿足部署在高速的網(wǎng)絡(luò)上的Snort入侵檢測系統(tǒng)實(shí)現(xiàn)快速匹配惡意流量的需求。實(shí)驗(yàn)結(jié)果表明,提出的NFA-OBDD是正確且高效的,優(yōu)于現(xiàn)有的方法約一至三個數(shù)量級,同時避免內(nèi)存爆炸和抵抗已知算法復(fù)雜度的攻擊。同時,Submatch-OBDD有效提高子匹配提取效率,通過網(wǎng)絡(luò)流量,合成的流量,和企業(yè)的事件日志來測試Submatch-OBDD的時間效率和空間效率,當(dāng)把模式組合的時候,Submatch-OBDD達(dá)到了理想的性能。在最好的情況下,Submatch-OBDD的速度比RE2和PCRE快一到兩個數(shù)量級。
[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.
【學(xué)位授予單位】：哈爾濱理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP393.08

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

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

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

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

4 彭詩力,譚漢松;基于特征值的多模式匹配算法及硬件實(shí)現(xiàn)[J];計(jì)算機(jī)工程與應(yīng)用;2005年01期

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

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

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

8 周延森;汪永好;;網(wǎng)絡(luò)入侵檢測系統(tǒng)模式匹配算法研究[J];計(jì)算機(jī)工程與設(shè)計(jì);2008年07期

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

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

相關(guān)會議論文 前10條

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

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

3 王德正;;網(wǎng)絡(luò)入侵檢測系統(tǒng)中模式匹配算法的研究與改進(jìn)[A];計(jì)算機(jī)技術(shù)與應(yīng)用進(jìn)展·2007——全國第18屆計(jì)算機(jī)技術(shù)與應(yīng)用（CACIS）學(xué)術(shù)會議論文集[C];2007年

4 朱艷;許家s，

本文編號：1970592