閆宏麗 趙麗

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

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

中圖分類號：TP393

文獻(xiàn)標(biāo)識碼：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引言

根據(jù)檢測方法不同，入侵檢測系統(tǒng)可以分為誤用入侵檢測系統(tǒng)和異常檢測系統(tǒng)。在誤用檢測系統(tǒng)中，模式匹配算法由于其方法簡單、易于實(shí)現(xiàn)而受到較多關(guān)注。模式匹配檢測技術(shù)主要優(yōu)點(diǎn)是檢測過程簡單，無須訓(xùn)練，檢測效率高，一般情況下不存在誤檢測。因此模式匹配在網(wǎng)絡(luò)入侵檢測中有著非常重要的影響。

1模式匹配

1.1模式匹配的概念

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

模式匹配系統(tǒng)主要是用一定的模式描述來提取攻擊的主要特征，其基本任務(wù)就是把存放在入侵檢測規(guī)則集中的已知入侵模式與系統(tǒng)正在檢測的網(wǎng)絡(luò)包或者重構(gòu)的TCP流中的文本進(jìn)行匹配，如果匹配成功，則可以斷定發(fā)生了入侵。這個(gè)過程是不斷循環(huán)前進(jìn)的。

1.2模式匹配原理

模式匹配是由入侵檢測領(lǐng)域的大師Kumar在1995年提出的，首先，Kumar提出了入侵信號的層次性概念。依據(jù)底層的審計(jì)事件，可以從中提取出高層的事件;由高層的事件構(gòu)成入侵信號，并依照高層事件之間的結(jié)構(gòu)關(guān)系，劃分入侵信號的抽象層次并對其分類。其次，Kumar將入侵信號分成四個(gè)層次，每一層對應(yīng)相應(yīng)的匹配模式。

（1）存在（Existence）

這種入侵信號表示只要存在這樣一種審計(jì)事件就足以說明發(fā)生了入侵行為或入侵企圖，它所對應(yīng)的匹配模式稱為存在模式（ Existence Pattern）。存在模式可以理解為在一個(gè)固定的時(shí)間對系統(tǒng)的某些狀態(tài)進(jìn)行檢查，并對系統(tǒng)的狀態(tài)進(jìn)行判定。

（2）序列（ Sequence）

有些入侵是由一些按照一定順序發(fā)生的行為所組成的，它具體可以表現(xiàn)為一組事件的序列。其對應(yīng)的模式就是序列模式（Sequence Pattern）。序列模式在檢測入侵時(shí)需要特別關(guān)注間隔和持續(xù)時(shí)間。

（3）規(guī)則表示（Regular Expressions）

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

（4）其他

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

在具體的實(shí)現(xiàn)中，很難做到對所有入侵信號進(jìn)行模式匹配，一般只是部分實(shí)現(xiàn)。

1.3模式匹配系統(tǒng)的特點(diǎn)

把攻擊信號看成一種模式進(jìn)行匹配檢測有以下一些特點(diǎn)。

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

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

（3）動(dòng)態(tài)的模式生成：描述攻擊的模式可以在需要的時(shí)候被動(dòng)態(tài)生成。

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

2常用的模式匹配算法

2.1單模式匹配

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

（1） Brute Force算法

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

（2） KMP算法[1]

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

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

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

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

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

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

①匹配自右向左進(jìn)行;

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

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

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

2.2多模式匹配

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

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

AC算法是同時(shí)搜索多個(gè)模式的經(jīng)典算法。AC算法使用了有限狀態(tài)自動(dòng)機(jī)的結(jié)構(gòu)來接收集合中所有的字符串。自動(dòng)機(jī)是結(jié)構(gòu)化的，這樣每個(gè)前綴都可用惟一的狀態(tài)來標(biāo)識，甚至是那些多個(gè)模式的前綴。當(dāng)文本中下一個(gè)字符不是模式中預(yù)期的，則會有一條失敗鏈指向那個(gè)狀態(tài)，代表最長的模式前綴，同時(shí)也是當(dāng)前狀態(tài)的相應(yīng)后綴。AC算法的復(fù)雜性是O（n），預(yù)處理階段的復(fù)雜性是O（m）。

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

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

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

3模式匹配系統(tǒng)的具體實(shí)現(xiàn)

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

（2）匹配模式的動(dòng)態(tài)增加和刪除：為了適應(yīng)不斷變化的攻擊手段，匹配模式必須具有動(dòng)態(tài)變更的能力。

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

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

4結(jié)束語

之前的調(diào)查結(jié)果表明[5]，基于模式匹配的入侵檢測系統(tǒng)中，30%的處理時(shí)間都在進(jìn)行模式匹配，除了運(yùn)行時(shí)間，網(wǎng)絡(luò)入侵檢測系統(tǒng)同時(shí)需要較小的內(nèi)存空間，所以需要找到一種好的模式匹配算法[6]，才能更好地提高入侵檢測系統(tǒng)的性能。

參考文獻(xiàn)（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].計(jì)算機(jī)與數(shù)字工程，2017.45（8）：1592-1596

收稿日期：2020-04-23

基金項(xiàng)目：晉中學(xué)院“1331工程”創(chuàng)客團(tuán)隊(duì)（jzxycktd2019029）; 2018晉中學(xué)院優(yōu)秀教學(xué)團(tuán)隊(duì)（2018）

作者簡介：閆宏麗（1971-），女，山西晉中人，實(shí)驗(yàn)師，主要研究方向：計(jì)算機(jī)網(wǎng)絡(luò)。

通訊作者：趙麗（1973-），女，山西晉中人，碩士，副教授，主要研究方向：計(jì)算機(jī)網(wǎng)絡(luò)，網(wǎng)絡(luò)安全。