計算機網絡入侵檢測系統匹配算法

曾宏志

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

在現代互聯網不斷發展的過程中，網絡規模不斷擴大，網絡應用也朝著全球化方向發展。在這樣的背景下，網絡入侵攻擊事件發生的幾率也在提高。傳統的防火墻技術已經無法保證網絡的安全，為了解決計算機網絡中網絡入侵以及網絡攻擊等不安全因素，我們應用了大量的網絡安全技術，計算機網絡入侵檢測系統就是其中之一。計算機網絡入侵檢測系統的應用，能夠進一步提高計算機網絡的安全性，讓人們在使用計算機網絡時能夠更加安心。本文對網絡入侵檢測系統模式匹配算法的設計進行全面分析。

1 網絡入侵檢測基本模型介紹

1.1 網絡入侵檢測基本過程

網絡入侵檢測的基本過程，可以分為匹配，分析以及過濾三個部分。匹配是指在網絡數據包中進行偵查匹配，來查找當前網絡中是否有網絡攻擊以及非法的網絡入侵。其次，分析是指分析數據以及規則板塊是否吻合。過濾是指在查找到網絡攻擊以及網絡入侵時，或者是說在網絡入侵檢測查找到不安全的信息，以及不安全的因素，或者是安全隱患時，不能夠及時將這些不安全的信息過濾掉，提升網絡使用的安全性。入侵檢測系統是網絡的保護機制，它能夠實時監測我們的網絡行為，保護我們日常使用的網絡，提高網絡使用的安全性。同時，網絡入侵檢測機制的使用，能夠幫助抵抗網絡內部的不定時攻擊以及網絡外部的攻擊與網絡外部的入侵。

1.2 網絡入侵檢測基本模型結構

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

除了以上的結構構成之外，網絡入侵檢測系統也可以分為數據采集、數據分析以及結果處理三個部分。數據采集板塊正如它的名稱一樣，主要負責網絡上各種數據的收集工作。數據分析這一板塊，是入侵檢測系統中的重要板塊，他可以說是入侵檢測系統的核心部分。如今現代網絡入侵檢測裝置在進行數據分析時，往往會選擇模式匹配這一方法，因為模式匹配的原理較為簡單，簡模式匹配的工作效率較高，能夠較好的分析處理網絡入侵。在數據分析完成之后，數據分析板塊將會將這一事件發送給結果處理板塊，由結果處理板塊決定某行為是否構成網絡入侵，并采取相應的解決措施。

1.3 網絡入侵檢測系統評價

在網絡入侵檢測系統創建成功之后，我們需要根據網絡入侵檢測系統的性能，對其成功與否進行評價。首先，我們需要判斷該入侵檢測系統是否能夠讓管理人員及時的掌握網絡中系統的變化，判斷該入侵檢測系統是否能夠及時的查找到網絡中所存在的異常信息。在對該入侵檢測系統進行評價時，我們也需要考慮該系統是否夠在事故發生時，對計算機網絡采取全方位的保護，能夠保護網絡系統免受攻擊，或者是免受網絡入侵。

2 計算機網絡入侵檢測系統匹配算法

2.1 模式匹配算法分析

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

（1）當進一步提升當前提取模式的質量，在網絡入侵檢測裝置檢測到入侵時或者是檢測到攻擊時，應當展現出鮮明的特征，能夠提醒使用者已經檢測到入侵。同時要注意，在提取模式設置以及提升的過程當中，要注意模式與模式之間的配合，避免沖突或者是漏洞的出現。

（2）為了提高模式匹配算法，我們需要在原有的基礎上增添或者是刪除一些模式匹配，因為攻擊手段以及攻擊方法始終處于不斷的變化當中，為了適應這些不斷的變化，我們需要對模式匹配進行一定的變更。

（3）我們需要解決增量匹配與完全匹配這一問題，增量匹配的應用，能夠減輕處理系統的壓力，提高入侵檢測系統的工作效率。我們對網絡入侵檢測系統進行一定的升級，能夠使得匹配機制更加全面，能夠解決更多的匹配問題，檢測到更多的網絡攻擊以及網絡入侵。

2.2 傳統網絡入侵檢測算法（BM算法）

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

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

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

2.3 改進的BM算法

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

如今所改進的算法在運算過程中的主要思想是：首先，我們在探究主要思想前，先假設模式的第一次匹配字符與最后一次匹配字符為變量x，在進行算法匹配時，如若出現不匹配，那就能夠實現T[k+1]的判斷。如若出現T[k+1]的判斷結果，我們就可以將這一模式的移動距離設為c，與此同時，我們規定c=max{dist[t[k+1]],di st[T[a]]}+1, 在這一公式中，a 的含義與前文中所規定的相同，我們所規定的這一表達式主要是用于比對T[k+1]與dist[T[a]]的大小。在二者進行對比之后，就可以找到正文與模式的最大移動距離，進而來進行接下來的匹配。

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

2.4 多模式匹配算法

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

若我們獲得的隨機數為1，并且我們所使用的模式的對應階數是零，在這時，我們就會使零階概率模式中的0、1 這兩種符號他們所對應的概率值進行互換。如果當時使用的是1 階模式，那么我們需要將與之對應的概率值進行交換。但是如若我們在選取隨機數時，所獲得的隨機數為0，那么多模式就要按照正常多模式匹配模式來進行。在多模式匹配算法運用過程當中，我們可以發現，多模式匹配算法的匹配，信號符號之間的關聯性較強，在匹配時能夠采取大量記憶匹配，該匹配模式較以往的匹配算法來說，具有記憶性，這能夠進一步提高匹配的效率。

2.5 改進的多模式匹配算法

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

3 網絡入侵檢測系統模式匹配算法的優化

網絡入侵檢測系統能夠實現執行數據包的深入檢測，還能夠對負載沒有或者已經實現定義的規則集相互匹配模式串進行掃描，從而對其是否具有入侵檢測事件進行檢測。從理論方面進行分析，BM 算法比較嚴謹，但在實際應用過程中性能并不理想。因此要對好后綴規則中的不足進行修改。此實驗需要測試的指標為：

（1）BM 和BMH 算法運行的時間。

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

（3）BM 算法中字符比較數量及使用好后綴規則數量。

因為入侵檢測的模式串長度在20~30 字符。因此可以發現BM算法和BMH 算法的總字符數量相同，但是在時間復雜度方面，BMH 算法的性能更好。

改進算法的主要思想是大部分規則匹配內容后綴和前綴都相同，所以改進算法只要能夠滿足入侵檢測系統模式匹配。單模式匹配算法及模式對其文本字符進行偏移量計算，另外就是通過下一個字符對偏移量進行計算。本文所改進的算法將兩者相互結合，從而形成全新的算法。對算法的改進實現步驟主要分為兩個階段，第一階段，預處理對兩個字符集進行計算，得到計算結果，第二個階段為初始位置及匹配方向，在開始匹配的時候要求模式串左端和待測文本左端相互對齊，字符對比通過模式串末端對齊，文本開始從右到左開始，如果匹配失敗，模式串就要移動到右端。使用改進方法只移動了兩次，一共匹配了三次，就能夠尋找到模式串，說明本文所設計的改進方法能夠提高預處理時間，并且計算方法比較簡單，提高網絡入侵檢測系統處理性能，能滿足大流量網絡環境的需求，改進的匹配模式算法能夠有效滿足網絡使用需求，提高系統檢測的效率。

4 小結

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