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

【摘要】：隨著網(wǎng)絡(luò)技術(shù)的高速發(fā)展和互聯(lián)網(wǎng)的日益開放，網(wǎng)絡(luò)應用日趨普及。與此同時，網(wǎng)絡(luò)帶來的攻擊行為也引發(fā)了人們對網(wǎng)絡(luò)安全問題的關(guān)注。作為維護網(wǎng)絡(luò)安全的重要手段，入侵檢測系統(tǒng)得到了廣泛的應用。而模式匹配是入侵檢測系統(tǒng)中最重要的一種檢測技術(shù)，其創(chuàng)新性和有效性將成為提高入侵檢測系統(tǒng)性能和效率的關(guān)鍵。 論文對入侵檢測系統(tǒng)進行了一個簡單的概述，介紹了入侵檢測的一般過程和分類，并闡述了模式匹配在入侵檢測中的應用。此外，論文還對幾種經(jīng)典的模式匹配算法作了詳細的介紹，其中包括BF、KMP、BM等單模式匹配算法和AC、AC_BM等多模式匹配算法。 論文介紹了Bloom Filter的原理及應用。Bloom Filter是一種基于多個哈希函數(shù)映射壓縮空間的數(shù)據(jù)結(jié)構(gòu)，通過尋找一種優(yōu)化的哈希查找算法可以提高Bloom Filter的性能。針對現(xiàn)有哈希算法中鏈地址法處理沖突時存在查找效率低的問題，論文設(shè)計了一種改進的哈希表查詢算法。經(jīng)分析和實際測試表明，該算法在不增加消耗的同時降低了沖突時執(zhí)行查詢的查找長度，從而縮短了查詢響應時間。 針對經(jīng)典AC算法構(gòu)建的狀態(tài)機內(nèi)存利用率低且需要頻繁訪問外存的問題，論文設(shè)計了一種改進的K步長狀態(tài)機。設(shè)計算法主要由以下四個模塊組成：改進的AC算法、文本轉(zhuǎn)換、映射機制和匹配查詢。其中，改進的AC算法對原AC狀態(tài)機中各個狀態(tài)的輸出進行了重新定義，映射機制則負責將改進的AC狀態(tài)機中相應的狀態(tài)信息映射到K步長狀態(tài)機中。通過這種映射機制，最終生成的K步長狀態(tài)機中只包含跳轉(zhuǎn)和輸出信息，沒有失效函數(shù)。而且在狀態(tài)存儲時，改進的K步長狀態(tài)機在原有鏈式存儲的基礎(chǔ)上，只保留出現(xiàn)過的子串輸入，對于鏈表中未出現(xiàn)的子串，則借助查詢算法進行處理。因此，和原來的K步長狀態(tài)機相比，改進的K步長狀態(tài)機占據(jù)更高的內(nèi)存優(yōu)勢。 盡管改進的K步長狀態(tài)機解決了一些問題，，但并沒有達到最優(yōu)的內(nèi)存資源利用率。為此，在它的基礎(chǔ)上，論文提出了一種基于位分割的K步長多模式匹配方法，即從位的角度出發(fā)，將原先的一個狀態(tài)機分割成八個小狀態(tài)機，每個狀態(tài)機可以同時讀取K個輸入字符的K個比特位，當所有子狀態(tài)機都輸出匹配信號時才確定匹配。該算法有兩個優(yōu)點：首先，子狀態(tài)機的每個狀態(tài)最多只有2K種輸入選擇，這使得內(nèi)存更加緊湊；其次，幾個子狀態(tài)機可以獨立并行工作，加快了模式查詢的速度。同時，為了避免一些不必要的查詢，待匹配的字符可以先進入Bloom Filter引擎過濾出可疑字符，由于Bloom Filter存在假陽性誤判，過濾后的字符要進行精確匹配。在文中，精確匹配由位分割狀態(tài)機來完成。二者的結(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.
【學位授予單位】：杭州電子科技大學
【學位級別】：碩士
【學位授予年份】：2014
【分類號】：TP393.08

【參考文獻】

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

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

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

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

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

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

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

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

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

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

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

本文編號：1562789