計(jì)算機(jī)網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)匹配算法

曾宏志

（江西工程學(xué)院智能制造與能源工程學(xué)院 江西省新余市 338000）

在現(xiàn)代互聯(lián)網(wǎng)不斷發(fā)展的過程中，網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，網(wǎng)絡(luò)應(yīng)用也朝著全球化方向發(fā)展。在這樣的背景下，網(wǎng)絡(luò)入侵攻擊事件發(fā)生的幾率也在提高。傳統(tǒng)的防火墻技術(shù)已經(jīng)無法保證網(wǎng)絡(luò)的安全，為了解決計(jì)算機(jī)網(wǎng)絡(luò)中網(wǎng)絡(luò)入侵以及網(wǎng)絡(luò)攻擊等不安全因素，我們應(yīng)用了大量的網(wǎng)絡(luò)安全技術(shù)，計(jì)算機(jī)網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)就是其中之一。計(jì)算機(jī)網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的應(yīng)用，能夠進(jìn)一步提高計(jì)算機(jī)網(wǎng)絡(luò)的安全性，讓人們?cè)谑褂糜?jì)算機(jī)網(wǎng)絡(luò)時(shí)能夠更加安心。本文對(duì)網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)模式匹配算法的設(shè)計(jì)進(jìn)行全面分析。

1 網(wǎng)絡(luò)入侵檢測(cè)基本模型介紹

1.1 網(wǎng)絡(luò)入侵檢測(cè)基本過程

網(wǎng)絡(luò)入侵檢測(cè)的基本過程，可以分為匹配，分析以及過濾三個(gè)部分。匹配是指在網(wǎng)絡(luò)數(shù)據(jù)包中進(jìn)行偵查匹配，來查找當(dāng)前網(wǎng)絡(luò)中是否有網(wǎng)絡(luò)攻擊以及非法的網(wǎng)絡(luò)入侵。其次，分析是指分析數(shù)據(jù)以及規(guī)則板塊是否吻合。過濾是指在查找到網(wǎng)絡(luò)攻擊以及網(wǎng)絡(luò)入侵時(shí)，或者是說在網(wǎng)絡(luò)入侵檢測(cè)查找到不安全的信息，以及不安全的因素，或者是安全隱患時(shí)，不能夠及時(shí)將這些不安全的信息過濾掉，提升網(wǎng)絡(luò)使用的安全性。入侵檢測(cè)系統(tǒng)是網(wǎng)絡(luò)的保護(hù)機(jī)制，它能夠?qū)崟r(shí)監(jiān)測(cè)我們的網(wǎng)絡(luò)行為，保護(hù)我們?nèi)粘Ｊ褂玫木W(wǎng)絡(luò)，提高網(wǎng)絡(luò)使用的安全性。同時(shí)，網(wǎng)絡(luò)入侵檢測(cè)機(jī)制的使用，能夠幫助抵抗網(wǎng)絡(luò)內(nèi)部的不定時(shí)攻擊以及網(wǎng)絡(luò)外部的攻擊與網(wǎng)絡(luò)外部的入侵。

1.2 網(wǎng)絡(luò)入侵檢測(cè)基本模型結(jié)構(gòu)

網(wǎng)絡(luò)入侵檢測(cè)基本模型主要有兩種形態(tài)，第一種形態(tài)是網(wǎng)絡(luò)入侵檢測(cè)基本模型分為審計(jì)記錄、網(wǎng)絡(luò)數(shù)據(jù)包，事件發(fā)生器，行為特征模塊以及規(guī)則模塊四個(gè)部分，網(wǎng)絡(luò)數(shù)據(jù)包主要就是儲(chǔ)存各種各樣的網(wǎng)絡(luò)數(shù)據(jù)，以供之后匹配算法的使用。事件發(fā)生器主要作用是抽取一些網(wǎng)絡(luò)上的有安全隱患的行為；行為特征模塊主要是記錄異常行為，除了記錄異常行為之外，行為特征模塊還具備自我更新以及學(xué)習(xí)的能力，該模塊可以定期自我革新，并且可以通過學(xué)習(xí)增加其他的性能。規(guī)則模塊兒是判斷數(shù)據(jù)能否入侵的基礎(chǔ)，規(guī)則模塊會(huì)將變量域值傳輸給行為特征模塊。

除了以上的結(jié)構(gòu)構(gòu)成之外，網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)也可以分為數(shù)據(jù)采集、數(shù)據(jù)分析以及結(jié)果處理三個(gè)部分。數(shù)據(jù)采集板塊正如它的名稱一樣，主要負(fù)責(zé)網(wǎng)絡(luò)上各種數(shù)據(jù)的收集工作。數(shù)據(jù)分析這一板塊，是入侵檢測(cè)系統(tǒng)中的重要板塊，他可以說是入侵檢測(cè)系統(tǒng)的核心部分。如今現(xiàn)代網(wǎng)絡(luò)入侵檢測(cè)裝置在進(jìn)行數(shù)據(jù)分析時(shí)，往往會(huì)選擇模式匹配這一方法，因?yàn)槟Ｊ狡ヅ涞脑磔^為簡單，簡模式匹配的工作效率較高，能夠較好的分析處理網(wǎng)絡(luò)入侵。在數(shù)據(jù)分析完成之后，數(shù)據(jù)分析板塊將會(huì)將這一事件發(fā)送給結(jié)果處理板塊，由結(jié)果處理板塊決定某行為是否構(gòu)成網(wǎng)絡(luò)入侵，并采取相應(yīng)的解決措施。

1.3 網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)評(píng)價(jià)

在網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)創(chuàng)建成功之后，我們需要根據(jù)網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的性能，對(duì)其成功與否進(jìn)行評(píng)價(jià)。首先，我們需要判斷該入侵檢測(cè)系統(tǒng)是否能夠讓管理人員及時(shí)的掌握網(wǎng)絡(luò)中系統(tǒng)的變化，判斷該入侵檢測(cè)系統(tǒng)是否能夠及時(shí)的查找到網(wǎng)絡(luò)中所存在的異常信息。在對(duì)該入侵檢測(cè)系統(tǒng)進(jìn)行評(píng)價(jià)時(shí)，我們也需要考慮該系統(tǒng)是否夠在事故發(fā)生時(shí)，對(duì)計(jì)算機(jī)網(wǎng)絡(luò)采取全方位的保護(hù)，能夠保護(hù)網(wǎng)絡(luò)系統(tǒng)免受攻擊，或者是免受網(wǎng)絡(luò)入侵。

2 計(jì)算機(jī)網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)匹配算法

2.1 模式匹配算法分析

針對(duì)字符串模式匹配算法的研究是當(dāng)今計(jì)算機(jī)領(lǐng)域的重要研究內(nèi)容，針對(duì)字符串匹配模式的研究被廣泛應(yīng)用到語言應(yīng)用、拼寫檢測(cè)等多個(gè)領(lǐng)域。在網(wǎng)絡(luò)入侵檢測(cè)當(dāng)中，模式匹配算法是指，在給定入侵規(guī)則庫中模式字符串后，在網(wǎng)絡(luò)數(shù)據(jù)包中查找這一字符串，進(jìn)而確定該模式字符串是否在網(wǎng)絡(luò)數(shù)據(jù)包中出現(xiàn)，確定該字符串出現(xiàn)在網(wǎng)絡(luò)數(shù)據(jù)包中的哪個(gè)位置。網(wǎng)絡(luò)入侵檢測(cè)主要包括三個(gè)部分，首先是指獲取數(shù)據(jù)包，其次是數(shù)據(jù)以及字符串的預(yù)處理，第三是檢測(cè)攻擊。在網(wǎng)絡(luò)入侵檢測(cè)過程當(dāng)中，數(shù)據(jù)源就是我們所獲得的網(wǎng)絡(luò)數(shù)據(jù)包，我們可以采取檢測(cè)網(wǎng)絡(luò)數(shù)據(jù)包的方式，來發(fā)現(xiàn)當(dāng)前計(jì)算機(jī)網(wǎng)絡(luò)中的入侵以及攻擊。為了提高模式匹配算法在入侵檢測(cè)中的利用率以及利用效果，我們應(yīng)當(dāng)對(duì)當(dāng)前的模式匹配算法進(jìn)行一定的提升。

（1）當(dāng)進(jìn)一步提升當(dāng)前提取模式的質(zhì)量，在網(wǎng)絡(luò)入侵檢測(cè)裝置檢測(cè)到入侵時(shí)或者是檢測(cè)到攻擊時(shí)，應(yīng)當(dāng)展現(xiàn)出鮮明的特征，能夠提醒使用者已經(jīng)檢測(cè)到入侵。同時(shí)要注意，在提取模式設(shè)置以及提升的過程當(dāng)中，要注意模式與模式之間的配合，避免沖突或者是漏洞的出現(xiàn)。

（2）為了提高模式匹配算法，我們需要在原有的基礎(chǔ)上增添或者是刪除一些模式匹配，因?yàn)楣羰侄我约肮舴椒ㄊ冀K處于不斷的變化當(dāng)中，為了適應(yīng)這些不斷的變化，我們需要對(duì)模式匹配進(jìn)行一定的變更。

（3）我們需要解決增量匹配與完全匹配這一問題，增量匹配的應(yīng)用，能夠減輕處理系統(tǒng)的壓力，提高入侵檢測(cè)系統(tǒng)的工作效率。我們對(duì)網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)進(jìn)行一定的升級(jí)，能夠使得匹配機(jī)制更加全面，能夠解決更多的匹配問題，檢測(cè)到更多的網(wǎng)絡(luò)攻擊以及網(wǎng)絡(luò)入侵。

2.2 傳統(tǒng)網(wǎng)絡(luò)入侵檢測(cè)算法（BM算法）

BM 算法是單模型精確匹配算法，該匹配算法是由Boyer 和Moore 共同設(shè)計(jì)的，這也就是為何這種匹配算法被命名為BM 算法。BM 算法運(yùn)算效率較高，在計(jì)算機(jī)網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)中有著十分重要的應(yīng)用，BM 算法再進(jìn)行運(yùn)算時(shí)，在對(duì)字符串進(jìn)行匹配時(shí)，會(huì)舍棄，或者說跳過那些沒有用處的字符，這樣的匹配方式能夠進(jìn)一步提高BM 算法的運(yùn)算速度，減少運(yùn)算時(shí)間的浪費(fèi)，BM 算法有著很高的運(yùn)算效率。

BM 算法的主要運(yùn)作過程:比如說在當(dāng)前的文章中，要求從a位置起，讓這字符串與運(yùn)算模式進(jìn)行從左向右的匹配比較，我們可以發(fā)現(xiàn)，如若再匹配比較過程當(dāng)中，Wa 將不會(huì)在這一運(yùn)算模式中出現(xiàn)，或者是在運(yùn)算完成之后，出現(xiàn)在運(yùn)算模式的末端。如若算法運(yùn)行過程當(dāng)中，沒有發(fā)現(xiàn)匹配內(nèi)容，那么正文當(dāng)中的許多字符就不會(huì)出現(xiàn)在模式串中。在之后的運(yùn)算以及匹配時(shí)，應(yīng)當(dāng)從正文的a+dist[Wa]處再次進(jìn)行匹配。

在算法的字符串與模式匹配過程當(dāng)中，可以選擇跳過一定數(shù)量的字符，這些字符無需進(jìn)行比較，直接略過這些字符來進(jìn)行字符串與模式的匹配。因?yàn)锽M 算法在運(yùn)算過程中，常常會(huì)跳過一些字符，并不是所有位置都會(huì)進(jìn)行匹配，因而BM 算法在運(yùn)算以及匹配時(shí)速度更快，因此有著更高的實(shí)用性。BM 算法在匹配以及查找過程當(dāng)中，使用的是“跳躍式”查找策略，如果在匹配過程當(dāng)中，相同的字符在模式串中反復(fù)出現(xiàn)，那在大多數(shù)情況下，我們就不需要對(duì)完整的這一文本進(jìn)行全方面的掃描，這在一定程度上減少了工作量，減輕了工作負(fù)擔(dān)。

2.3 改進(jìn)的BM算法

在BM 算法運(yùn)算時(shí)，如若執(zhí)行文字串或者是正文中從a 位置開始的“返前”匹配模式，并在這一匹配模式下進(jìn)行從左到右的匹配檢查，如若在匹配過程中發(fā)現(xiàn)不匹配，那么文本串的指針就會(huì)出現(xiàn)回溯這一現(xiàn)象，在某些情況下，會(huì)導(dǎo)致死循環(huán)的出現(xiàn)，這會(huì)影響匹配工作的進(jìn)行。因此，為糾正BM 算法中出現(xiàn)的問題，以及BM算法的局限性，需要在bm 算法的基礎(chǔ)上進(jìn)行一定的改進(jìn)，為此Horspool 在1980年提出了bmH 算法。BMH 算法在BM 算法的基礎(chǔ)上進(jìn)行了優(yōu)化，簡化了原有的bm 算法，匹配效率相比于bm 算法有了更大的提高。改進(jìn)過后的bm 算法，相比于圓心的bm 算法，不匹配過程中的模式與正文移動(dòng)距離相較于之前有所增加。除此之外，與bm 算法不同，不再只是關(guān)注沒有匹配的字符，而是將關(guān)注的焦點(diǎn)放在了匹配文本的每一次匹配失敗的最后一個(gè)字符。在算法的匹配過程中，會(huì)根據(jù)這最后一個(gè)字符在文本中是否出現(xiàn)，根據(jù)這最后一個(gè)字符在文本中出現(xiàn)的位置來決定匹配時(shí)所跳躍的步數(shù)，進(jìn)而決定跳躍模板的長度。如若在匹配過程中，最后一個(gè)字符在模式中并未出現(xiàn)，那模式的長度就會(huì)被作為跳躍的步數(shù)，也就是決定了跳躍模板的長度。

如今所改進(jìn)的算法在運(yùn)算過程中的主要思想是：首先，我們?cè)谔骄恐饕枷肭?，先假設(shè)模式的第一次匹配字符與最后一次匹配字符為變量x，在進(jìn)行算法匹配時(shí)，如若出現(xiàn)不匹配，那就能夠?qū)崿F(xiàn)T[k+1]的判斷。如若出現(xiàn)T[k+1]的判斷結(jié)果，我們就可以將這一模式的移動(dòng)距離設(shè)為c，與此同時(shí)，我們規(guī)定c=max{dist[t[k+1]],di st[T[a]]}+1, 在這一公式中，a 的含義與前文中所規(guī)定的相同，我們所規(guī)定的這一表達(dá)式主要是用于比對(duì)T[k+1]與dist[T[a]]的大小。在二者進(jìn)行對(duì)比之后，就可以找到正文與模式的最大移動(dòng)距離，進(jìn)而來進(jìn)行接下來的匹配。

在這一匹配過程當(dāng)中，我們按照從右到左這樣一種匹配模式來進(jìn)行正文與模式之間的匹配，模式右邊的字符匹配將會(huì)大于左邊的字符匹配。如若在匹配過程中存在常模式這一特殊情況，在匹配過程當(dāng)中，將其與左邊不匹配的時(shí)候進(jìn)行對(duì)比，會(huì)消耗更多的時(shí)間。為了節(jié)約時(shí)間，提高算法的匹配效率，我們可以運(yùn)用上文所說的方法來進(jìn)行匹配對(duì)比，刪除或者是避免一些不必要的匹配過程，這樣子的方式可以提高匹配的速度，減少匹配所要使用的時(shí)間，提高匹配的效率。

2.4 多模式匹配算法

計(jì)算機(jī)網(wǎng)絡(luò)中的多模式匹配算法，也就是RAC 算法。該算法相比于其他算法的顯著特征是指算法在預(yù)處理階段總共包括三個(gè)函數(shù)，分別是無效函數(shù)、輸出函數(shù)、和跳轉(zhuǎn)函數(shù)。在該多模式匹配算法中，使用以上所說的三種函數(shù)對(duì)計(jì)算機(jī)網(wǎng)絡(luò)進(jìn)行匹配以及遍歷。計(jì)算機(jī)網(wǎng)絡(luò)中的這一多模式匹配算法是根據(jù)密鑰控制模式是否置換來進(jìn)行計(jì)算機(jī)網(wǎng)絡(luò)的檢測(cè)。多模式匹配算法的檢測(cè)目標(biāo)，主要依靠以下所說的方式來實(shí)現(xiàn)：在算法匹配開始之前，首先應(yīng)當(dāng)通過基數(shù)生成器來隨機(jī)獲得256 位隨機(jī)數(shù)，這些隨機(jī)數(shù)可能是1 也可能是0，我們通過采取這樣的方式，來實(shí)現(xiàn)模式的有效控制。

若我們獲得的隨機(jī)數(shù)為1，并且我們所使用的模式的對(duì)應(yīng)階數(shù)是零，在這時(shí)，我們就會(huì)使零階概率模式中的0、1 這兩種符號(hào)他們所對(duì)應(yīng)的概率值進(jìn)行互換。如果當(dāng)時(shí)使用的是1 階模式，那么我們需要將與之對(duì)應(yīng)的概率值進(jìn)行交換。但是如若我們?cè)谶x取隨機(jī)數(shù)時(shí)，所獲得的隨機(jī)數(shù)為0，那么多模式就要按照正常多模式匹配模式來進(jìn)行。在多模式匹配算法運(yùn)用過程當(dāng)中，我們可以發(fā)現(xiàn)，多模式匹配算法的匹配，信號(hào)符號(hào)之間的關(guān)聯(lián)性較強(qiáng)，在匹配時(shí)能夠采取大量記憶匹配，該匹配模式較以往的匹配算法來說，具有記憶性，這能夠進(jìn)一步提高匹配的效率。

2.5 改進(jìn)的多模式匹配算法

針對(duì)多模式匹配算法中存在的問題，我們將多模式匹配算法進(jìn)行了進(jìn)一步的改進(jìn)，提出了多模式匹配算法，也被稱為NBM 算法。NBM 算法的核心思想是指如若模式串中的dm 個(gè)字符與文本串中三用的字符再進(jìn)行匹配時(shí)，出現(xiàn)匹配失敗這一情況，那么我們將按照bm 的算法向右滑過dist[c]=m-j 段距離；如若在匹配過程當(dāng)中，并未出現(xiàn)匹配失敗這一情況，那么需要考慮在模式串中是否出現(xiàn)了導(dǎo)致匹配失敗的字符，考慮導(dǎo)致匹配失敗的當(dāng)前字符的下一個(gè)字符是否與模式串a(chǎn) 相等。如若相等的話，則需要將它們對(duì)齊，嬰進(jìn)而考慮下一個(gè)字符。如若不相等的話，則需要按照從右到左的順序依次比較每個(gè)字符。

3 網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)模式匹配算法的優(yōu)化

網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)能夠?qū)崿F(xiàn)執(zhí)行數(shù)據(jù)包的深入檢測(cè)，還能夠?qū)ω?fù)載沒有或者已經(jīng)實(shí)現(xiàn)定義的規(guī)則集相互匹配模式串進(jìn)行掃描，從而對(duì)其是否具有入侵檢測(cè)事件進(jìn)行檢測(cè)。從理論方面進(jìn)行分析，BM 算法比較嚴(yán)謹(jǐn)，但在實(shí)際應(yīng)用過程中性能并不理想。因此要對(duì)好后綴規(guī)則中的不足進(jìn)行修改。此實(shí)驗(yàn)需要測(cè)試的指標(biāo)為：

（1）BM 和BMH 算法運(yùn)行的時(shí)間。

（2）BM 和BMH 算法的字符比較數(shù)量。

（3）BM 算法中字符比較數(shù)量及使用好后綴規(guī)則數(shù)量。

因?yàn)槿肭謾z測(cè)的模式串長度在20~30 字符。因此可以發(fā)現(xiàn)BM算法和BMH 算法的總字符數(shù)量相同，但是在時(shí)間復(fù)雜度方面，BMH 算法的性能更好。

改進(jìn)算法的主要思想是大部分規(guī)則匹配內(nèi)容后綴和前綴都相同，所以改進(jìn)算法只要能夠滿足入侵檢測(cè)系統(tǒng)模式匹配。單模式匹配算法及模式對(duì)其文本字符進(jìn)行偏移量計(jì)算，另外就是通過下一個(gè)字符對(duì)偏移量進(jìn)行計(jì)算。本文所改進(jìn)的算法將兩者相互結(jié)合，從而形成全新的算法。對(duì)算法的改進(jìn)實(shí)現(xiàn)步驟主要分為兩個(gè)階段，第一階段，預(yù)處理對(duì)兩個(gè)字符集進(jìn)行計(jì)算，得到計(jì)算結(jié)果，第二個(gè)階段為初始位置及匹配方向，在開始匹配的時(shí)候要求模式串左端和待測(cè)文本左端相互對(duì)齊，字符對(duì)比通過模式串末端對(duì)齊，文本開始從右到左開始，如果匹配失敗，模式串就要移動(dòng)到右端。使用改進(jìn)方法只移動(dòng)了兩次，一共匹配了三次，就能夠?qū)ふ业侥Ｊ酱f明本文所設(shè)計(jì)的改進(jìn)方法能夠提高預(yù)處理時(shí)間，并且計(jì)算方法比較簡單，提高網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)處理性能，能滿足大流量網(wǎng)絡(luò)環(huán)境的需求，改進(jìn)的匹配模式算法能夠有效滿足網(wǎng)絡(luò)使用需求，提高系統(tǒng)檢測(cè)的效率。

4 小結(jié)

如今我們正處于一個(gè)信息化時(shí)代，網(wǎng)絡(luò)化以及信息化的快速發(fā)展，指的我們當(dāng)前的生活以及工作已經(jīng)離不開計(jì)算機(jī)網(wǎng)絡(luò)，計(jì)算機(jī)已經(jīng)成為我們生活和工作必不可少的一部分。計(jì)算機(jī)網(wǎng)絡(luò)的應(yīng)用進(jìn)一步提高了我們的工作效率，但是與此同時(shí)，計(jì)算機(jī)網(wǎng)絡(luò)的應(yīng)用也有這一定的安全隱患，計(jì)算機(jī)網(wǎng)絡(luò)的安全性不能夠得到充分保障，常會(huì)受到一些網(wǎng)絡(luò)攻擊或是網(wǎng)絡(luò)入侵。網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的應(yīng)用，能夠幫助提高計(jì)算機(jī)網(wǎng)絡(luò)的安全性，而匹配算法又是計(jì)算機(jī)檢測(cè)系統(tǒng)的重要組成部分，匹配算法的優(yōu)化以及提升能夠使得計(jì)算機(jī)網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的性能更加完善。