入侵檢測系統中模式匹配算法的研究

閆宏麗 趙麗

摘要：結合模式匹配的概念，提出模式匹配在入侵檢測系統中使用的原理及特點在分析了常見的單模式匹配和多模式匹配算法之后，將模式匹配方法應用在誤用入侵檢測系統中，去完成對已知攻擊的檢測.基于模式匹配的入侵檢測系統具有較低的虛警率，但要想提高入侵檢測系統的性能，必須對模式匹配算法做進一步的改進

關鍵詞：入侵檢測;模式匹配;誤用入侵檢測;攻擊;虛警率

中圖分類號：TP393

文獻標識碼：A

文章編號：1006-8228（2020）09-81-03

Research on pattern matching algorithm in intrusion detection system

Yan Hongli， Zhao Li

（School of Information Technology and Engineering， Jinzhong University，Jinzhong，Shanxi 010619，China）

Abstract： Combined with the concept of pattern matching， the principle and characteristics of pattern matching used in intrusiondetection system are put forward. After analyzing comrrion single-mode matching and multi-mode matching algorithms， the patternmatching method is applied to the misuse intrusion detection system to complete the detection of known attacks. The intrusiondetection system based on pattern matching has low false positive rate. but in order to improve the performance of intrusiondetection system， the pattern matching algorithm must be further improved.

Key words： intrusion detection; pattern matching; misuse intrusion detection; attack; false positive rate

0引言

根據檢測方法不同，入侵檢測系統可以分為誤用入侵檢測系統和異常檢測系統。在誤用檢測系統中，模式匹配算法由于其方法簡單、易于實現而受到較多關注。模式匹配檢測技術主要優點是檢測過程簡單，無須訓練，檢測效率高，一般情況下不存在誤檢測。因此模式匹配在網絡入侵檢測中有著非常重要的影響。

1模式匹配

1.1模式匹配的概念

模式匹配是指：已知一長度為n的文本字符串T=T1T2…Tn，和一長度為m（m≤n）的模式字符串P=P1P2…Pm，看T中是否存在長度為m的子串。

模式匹配系統主要是用一定的模式描述來提取攻擊的主要特征，其基本任務就是把存放在入侵檢測規則集中的已知入侵模式與系統正在檢測的網絡包或者重構的TCP流中的文本進行匹配，如果匹配成功，則可以斷定發生了入侵。這個過程是不斷循環前進的。

1.2模式匹配原理

模式匹配是由入侵檢測領域的大師Kumar在1995年提出的，首先，Kumar提出了入侵信號的層次性概念。依據底層的審計事件，可以從中提取出高層的事件;由高層的事件構成入侵信號，并依照高層事件之間的結構關系，劃分入侵信號的抽象層次并對其分類。其次，Kumar將入侵信號分成四個層次，每一層對應相應的匹配模式。

（1）存在（Existence）

這種入侵信號表示只要存在這樣一種審計事件就足以說明發生了入侵行為或入侵企圖，它所對應的匹配模式稱為存在模式（ Existence Pattern）。存在模式可以理解為在一個固定的時間對系統的某些狀態進行檢查，并對系統的狀態進行判定。

（2）序列（ Sequence）

有些入侵是由一些按照一定順序發生的行為所組成的，它具體可以表現為一組事件的序列。其對應的模式就是序列模式（Sequence Pattern）。序列模式在檢測入侵時需要特別關注間隔和持續時間。

（3）規則表示（Regular Expressions）

規則表示模式（Regular Expressions Patterns）是指用一種擴展的規則表達式方式構造匹配模式，規則表達式是由用AND邏輯表達式連接一些描述事件的原語構成的。適用這種模式的攻擊信號通常由一些相關的活動組成，而這些活動間沒有什么事件順序的關系。

（4）其他

其他模式（ Other Pattern）是指一些不能用前面的方法進行表示的攻擊。

在具體的實現中，很難做到對所有入侵信號進行模式匹配，一般只是部分實現。

1.3模式匹配系統的特點

把攻擊信號看成一種模式進行匹配檢測有以下一些特點。

（1）事件來源獨立：模式的描述并不包含對事件來源的描述，模式只需要了解事件可以提供什么數據，而不管事件如何提供這些數據。

（2）描述和匹配相分離：描述入侵信號的模式主要是定義什么需要匹配，而不是如何去匹配。

（3）動態的模式生成：描述攻擊的模式可以在需要的時候被動態生成。

（4）可移植性：入侵模式可以被輕易地移植，而不需要重新生成。

2常用的模式匹配算法

2.1單模式匹配

單模式匹配算法：對文本T的一次掃描，只能處理一個模式串。

（1） Brute Force算法

此算法的實質是將模式P和文本T從左到右逐個搜索，若在某一位匹配失敗，則將模式P向右移動一位，仍從模式P的第一位開始搜索，直到將文本T搜索完為止。在最壞的情況下，要執行（n-m+l）×m次字母的匹配，因此，其時間復雜度為O（m×n）。所以，當n不大時，可以采用這種算法。

（2） KMP算法[1]

Brute Force搜索算法在一次字符比較失敗后，只是簡單地把模式向右移動一個字符位置。這樣做的缺點是完全丟棄了前面已經做過的字符匹配中得到的信息，實際上這些匹配信息是可以利用的。

KMP算法是Knuth，Morris，Pratt提出的。和簡單算法不同，當某次匹配不成功時，模式串不一定只能右移一格，右移后也不一定必須從模式起點處開始匹配。具體算法描述如下。

在某次試匹配成功時，若Tj≠Pj，即模式的前j-l個字符全能匹配，如果事先知道子模式P1P2……Pj-1有一個最長的真首子串和它的尾子串相等，即P1P2……Pk-1=Pj-k+1Pj-k+2……Pj-1，那么，下一次試匹配時，就可把模式串右移next[j]位置，next[j]表示當模式串中第j個字符與主串中相應字符“失配”時，在模式中需重新和主串中該字符進行比較的字符的位置。next[j]可以在預處理時計算。

為了不遺漏可能完全匹配的情況，上述的真首子串必須是最長的。故對于任—個子模式P1P2……Pj（1≤j≤n），“自匹配”的真首子串是唯一的，它只和模式自身的結構有關。

KMP算法采取的方法是一次把模式向右移動多個位置，這就使得在匹配過程中完全不需要回溯。在最好的情況下，KMP算法的時間復雜度為O（n+m）。計算next[j]的時間復雜度為O（m）。

（3） Boyer_Moore（BM）算法[2]

①匹配自右向左進行;

②若匹配失敗發生在Pi≠Ti，且Ti不出現在模式P中，則將模式右移直到Pi位于匹配失敗位Ti的右邊第一位（即Ti+1位），若Ti在P中有若干地方出現，則應選擇j=max{k|Pk=Ti};

③模式P后面K位和文本T中一致的部分，有一部分在T中其他地方出現，則可以將T向右移動，直接使這部分對齊，且要求這部分盡可能的大。

BM算法采用“跳躍式”查找策略，在多數情況下不需要對文本進行一次完整的掃描，其時間復雜度為O（n/m）。

2.2多模式匹配

多模式匹配算法：對文本T的一次掃描，能夠同時處理多個模式串的集合。

（1） Aho_Corasick（AC）算法[3]

AC算法是同時搜索多個模式的經典算法。AC算法使用了有限狀態自動機的結構來接收集合中所有的字符串。自動機是結構化的，這樣每個前綴都可用惟一的狀態來標識，甚至是那些多個模式的前綴。當文本中下一個字符不是模式中預期的，則會有一條失敗鏈指向那個狀態，代表最長的模式前綴，同時也是當前狀態的相應后綴。AC算法的復雜性是O（n），預處理階段的復雜性是O（m）。

在用AC算法構造的有限狀態自動機中，可以發現這樣一個現象：離自動機根較近的地方，結點比較密集，即這時自動機的各個分枝中的結點都比較密集;相反，離根越遠，結點越稀疏，這是由于模式串的長度不同而引起的。在AC算法中，要為每一個模式串的每一個字符建立一個結點，這樣無疑算法空間使用很多，為了壓縮AC算法的空間使用率，可以將稀疏的結點合并成一個結點，即AC-Path算法。但是AC-Path算法在節省了空間的同時，卻也增加了模式匹配時的難度，其運行所需要的時間也隨之增加。

（2） Wu-Manber（WM）算法[4]

Wu-Manber算法是BM算法處理多模式匹配問題的派生形式，是一種快速實用的多模式匹配算法。它采用了BM算法的基本框架，但不同于BM，它不是使用一個字符來計算壞字符移動的距離表，而是使用塊字符來計算壞字符移動的距離表（shift[]）。此外，在進行模式匹配時它使用哈希表選擇模式串集合中的一個子集與當前的文本進行匹配，以減少無謂的匹配運算。Wu-Manber算法不會隨著模式串集合的增加而成比例的增長，而且遠少于使用每一個模式和BM算法對文本進行匹配的時間總和。Wu-Manber算法的時間復雜度在最好的情況下能達到O（B×n/m）（B是塊字符的長度，是算法在每一個入口點計算塊字符的時間）。

3模式匹配系統的具體實現

（1）模式的提取：必須使提取的模式具有很高的質量，能夠充分表示入侵信號的特征，同時模式之間不能有沖突。

（2）匹配模式的動態增加和刪除：為了適應不斷變化的攻擊手段，匹配模式必須具有動態變更的能力。

（3）增量匹配和優先級匹配：在事件流對系統處理能力產生很大壓力的時候，要求系統采取增量匹配的方法來提高系統效率，或者可以對高優先級的事件先行處理，暫緩對低優先級事件的處理。

（4）完全匹配：匹配機制必須能夠提供對所有模式進行匹配的能力。

4結束語

之前的調查結果表明[5]，基于模式匹配的入侵檢測系統中，30%的處理時間都在進行模式匹配，除了運行時間，網絡入侵檢測系統同時需要較小的內存空間，所以需要找到一種好的模式匹配算法[6]，才能更好地提高入侵檢測系統的性能。

參考文獻（References）：

[1]D.E. Knuth.J. H.Morris，V.R.Pratt. Fast pattern matching instrings[J]. SIAM J.Comput，1977.6（2）：323-350

[2] R.S. Boyer. A Fast String SerachingAlgorithm[J].Communication of the ACM，1977.20（10）：762-772

[3]Aho A，Corasick M.Efficientstring matching： an aid tobibliographic search[J]. Communications of the ACM，1975.18（6）：33-40

[4]S. Wu and U.Manber.A fast algorithm for muti-patternsearching. Department of Computer Science， universityof Arizona， Tucscn， Az. Rep. Tr-94-17，1994.

[5]M. Roesch， Snort： Lightweight intrusion detection fornetworks. In Proceedings ofthe 1999 USENIX LISASystems Administration Conference[C].

[6]趙麗.面向入侵檢測的高效模式匹配算法研究[J].計算機與數字工程，2017.45（8）：1592-1596

收稿日期：2020-04-23

基金項目：晉中學院“1331工程”創客團隊（jzxycktd2019029）; 2018晉中學院優秀教學團隊（2018）

作者簡介：閆宏麗（1971-），女，山西晉中人，實驗師，主要研究方向：計算機網絡。

通訊作者：趙麗（1973-），女，山西晉中人，碩士，副教授，主要研究方向：計算機網絡，網絡安全。