本文選題：模式匹配　切入點(diǎn)：入侵檢測　出處：《杭州電子科技大學(xué)》2014年碩士論文　論文類型：學(xué)位論文

【摘要】：隨著網(wǎng)絡(luò)技術(shù)的高速發(fā)展和互聯(lián)網(wǎng)的日益開放，網(wǎng)絡(luò)應(yīng)用日趨普及。與此同時(shí)，網(wǎng)絡(luò)帶來的攻擊行為也引發(fā)了人們對(duì)網(wǎng)絡(luò)安全問題的關(guān)注。作為維護(hù)網(wǎng)絡(luò)安全的重要手段，入侵檢測系統(tǒng)得到了廣泛的應(yīng)用。而模式匹配是入侵檢測系統(tǒng)中最重要的一種檢測技術(shù)，其創(chuàng)新性和有效性將成為提高入侵檢測系統(tǒng)性能和效率的關(guān)鍵。 論文對(duì)入侵檢測系統(tǒng)進(jìn)行了一個(gè)簡單的概述，介紹了入侵檢測的一般過程和分類，并闡述了模式匹配在入侵檢測中的應(yīng)用。此外，論文還對(duì)幾種經(jīng)典的模式匹配算法作了詳細(xì)的介紹，其中包括BF、KMP、BM等單模式匹配算法和AC、AC_BM等多模式匹配算法。 論文介紹了Bloom Filter的原理及應(yīng)用。Bloom Filter是一種基于多個(gè)哈希函數(shù)映射壓縮空間的數(shù)據(jù)結(jié)構(gòu)，通過尋找一種優(yōu)化的哈希查找算法可以提高Bloom Filter的性能。針對(duì)現(xiàn)有哈希算法中鏈地址法處理沖突時(shí)存在查找效率低的問題，論文設(shè)計(jì)了一種改進(jìn)的哈希表查詢算法。經(jīng)分析和實(shí)際測試表明，該算法在不增加消耗的同時(shí)降低了沖突時(shí)執(zhí)行查詢的查找長度，從而縮短了查詢響應(yīng)時(shí)間。 針對(duì)經(jīng)典AC算法構(gòu)建的狀態(tài)機(jī)內(nèi)存利用率低且需要頻繁訪問外存的問題，論文設(shè)計(jì)了一種改進(jìn)的K步長狀態(tài)機(jī)。設(shè)計(jì)算法主要由以下四個(gè)模塊組成：改進(jìn)的AC算法、文本轉(zhuǎn)換、映射機(jī)制和匹配查詢。其中，改進(jìn)的AC算法對(duì)原AC狀態(tài)機(jī)中各個(gè)狀態(tài)的輸出進(jìn)行了重新定義，映射機(jī)制則負(fù)責(zé)將改進(jìn)的AC狀態(tài)機(jī)中相應(yīng)的狀態(tài)信息映射到K步長狀態(tài)機(jī)中。通過這種映射機(jī)制，最終生成的K步長狀態(tài)機(jī)中只包含跳轉(zhuǎn)和輸出信息，沒有失效函數(shù)。而且在狀態(tài)存儲(chǔ)時(shí)，改進(jìn)的K步長狀態(tài)機(jī)在原有鏈?zhǔn)酱鎯?chǔ)的基礎(chǔ)上，只保留出現(xiàn)過的子串輸入，對(duì)于鏈表中未出現(xiàn)的子串，則借助查詢算法進(jìn)行處理。因此，和原來的K步長狀態(tài)機(jī)相比，改進(jìn)的K步長狀態(tài)機(jī)占據(jù)更高的內(nèi)存優(yōu)勢。 盡管改進(jìn)的K步長狀態(tài)機(jī)解決了一些問題，，但并沒有達(dá)到最優(yōu)的內(nèi)存資源利用率。為此，在它的基礎(chǔ)上，論文提出了一種基于位分割的K步長多模式匹配方法，即從位的角度出發(fā)，將原先的一個(gè)狀態(tài)機(jī)分割成八個(gè)小狀態(tài)機(jī)，每個(gè)狀態(tài)機(jī)可以同時(shí)讀取K個(gè)輸入字符的K個(gè)比特位，當(dāng)所有子狀態(tài)機(jī)都輸出匹配信號(hào)時(shí)才確定匹配。該算法有兩個(gè)優(yōu)點(diǎn)：首先，子狀態(tài)機(jī)的每個(gè)狀態(tài)最多只有2K種輸入選擇，這使得內(nèi)存更加緊湊；其次，幾個(gè)子狀態(tài)機(jī)可以獨(dú)立并行工作，加快了模式查詢的速度。同時(shí)，為了避免一些不必要的查詢，待匹配的字符可以先進(jìn)入Bloom Filter引擎過濾出可疑字符，由于Bloom Filter存在假陽性誤判，過濾后的字符要進(jìn)行精確匹配。在文中，精確匹配由位分割狀態(tài)機(jī)來完成。二者的結(jié)合從整體上提高了匹配查詢的效率。
[Abstract]:With the rapid development of network technology and the increasing opening of the Internet, network applications are becoming more and more popular. At the same time, the attacks brought by the network also arouse people's attention to network security issues. Intrusion detection system (IDS) has been widely used, and pattern matching is the most important detection technology in IDS. Its innovation and effectiveness will be the key to improve the performance and efficiency of IDS. This paper gives a brief overview of intrusion detection system, introduces the general process and classification of intrusion detection, and expounds the application of pattern matching in intrusion detection. Several classical pattern matching algorithms are also introduced in this paper, including single pattern matching algorithm such as BFN KMPBM and multi-pattern matching algorithm such as ACK / AC\ + BM\\\). This paper introduces the principle and application of Bloom Filter. Bloom Filter is a data structure based on multiple hash function maps. The performance of Bloom Filter can be improved by looking for an optimized hash lookup algorithm. An improved hashing table query algorithm is designed in this paper. The analysis and practical test show that the algorithm can reduce the query search length and shorten the query response time without increasing the consumption. Aiming at the problem of low memory utilization and frequent access to external memory of the state machine constructed by classical AC algorithm, an improved K-step state machine is designed in this paper. The algorithm is composed of the following four modules: the improved AC algorithm. Text conversion, mapping mechanism and matching query. Among them, the improved AC algorithm redefines the output of each state in the original AC state machine. The mapping mechanism is responsible for mapping the corresponding state information from the improved AC state machine to the K step state machine. Through this mapping mechanism, only jump and output information are included in the resulting K step state machine. There is no failure function. Moreover, in state storage, the improved K-step state machine only retains the existing sub-string input on the basis of the original chain storage, and the query algorithm is used to deal with the sub-string that does not appear in the linked list. Compared with the original K step state machine, the improved K step state machine occupies a higher memory advantage. Although the improved K-step state machine solves some problems, it does not achieve the optimal utilization of memory resources. Based on this, a K-step multi-pattern matching method based on bit segmentation is proposed in this paper. That is, from the point of view of bit, the original state machine is divided into eight small state machines. Each state machine can read K bits of K input characters at the same time. The algorithm has two advantages: first, there are at most 2K input choices for each state of the substate machine, which makes the memory more compact. Several sub-state machines can work independently and in parallel, which speeds up the speed of pattern query. At the same time, in order to avoid some unnecessary queries, the characters to be matched can be filtered into the Bloom Filter engine to filter out suspicious characters, because Bloom Filter has false positive misjudgment. In this paper, the exact matching is accomplished by bit segmentation state machine. The combination of the two methods improves the efficiency of matching query.
【學(xué)位授予單位】：杭州電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP393.08

【參考文獻(xiàn)】

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

1 涂俊英;;基于改進(jìn)的BM算法在Linux入侵檢測系統(tǒng)中的應(yīng)用[J];電腦編程技巧與維護(hù);2010年24期

2 劉威;郭淵博;黃鵬;;基于Bloom filter的多模式匹配引擎[J];電子學(xué)報(bào);2010年05期

3 王永成,沈州,許一震;改進(jìn)的多模式匹配算法[J];計(jì)算機(jī)研究與發(fā)展;2002年01期

4 王果,徐仁佐;結(jié)合哈希過濾的一種改進(jìn)多連接查詢優(yōu)化算法[J];計(jì)算機(jī)工程;2004年07期

5 楊武,方濱興,云曉春,張宏莉;入侵檢測系統(tǒng)中高效模式匹配算法的研究[J];計(jì)算機(jī)工程;2004年13期

6 馬如林;蔣華;張慶霞;;一種哈希表快速查找的改進(jìn)方法[J];計(jì)算機(jī)工程與科學(xué);2008年09期

7 張朝霞;劉耀軍;;有效的哈希沖突解決辦法[J];計(jì)算機(jī)應(yīng)用;2010年11期

8 李安寧;馬晨生;;入侵檢測技術(shù)探析[J];內(nèi)蒙古科技與經(jīng)濟(jì);2008年21期

9 李偉男;鄂躍鵬;葛敬國;錢華林;;多模式匹配算法及硬件實(shí)現(xiàn)[J];軟件學(xué)報(bào);2006年12期

10 方賢進(jìn);李龍澍;;多模式匹配算法的優(yōu)化研究[J];微計(jì)算機(jī)信息;2007年09期

本文編號(hào)：1562789