計算機網絡入侵檢測系統的多模式匹配算法

2024年3月15日發(作者：秋天的雨仿寫句子)

計算機系統應用 ISSN 1003-3254, CODEN CSAOBN

Computer Systems & Applications,2021,30(4):210?215 [doi: 10.15888/.007947]

?中國科學院軟件研究所版權所有.

E-mail:

Tel: +86-10-62661041

計算機網絡入侵檢測系統的多模式匹配算法

①

薛　芳

1

, 林　麗

2

1

2

(集美大學 信息化中心, 廈門 361021)

(集美大學 計算機工程學院, 廈門 361021)

通訊作者: 林　麗

摘　要: 為了使網絡入侵檢測系統能夠在高速網絡環境中有效的開展工作, 實現計算機網絡入侵檢測系統的多模式

匹配算法優化設計. 首先, 對網絡入侵檢測的算法與原理進行全面分析. 其次, 對網絡入侵檢測系統多模式匹配算法

的優化思想進行描述, 描述多模式匹配算法, 對算法進行實現, 使模式匹配算法效率得到提高, 以此提高系統檢測能

力. 通過測試結果表示, 優化后多模式匹配算法能夠使網絡檢測系統的檢測性能得到提高.

關鍵詞: 計算機網絡; 網絡入侵檢測; 多模式匹配算法

引用格式: 薛芳,林麗.計算機網絡入侵檢測系統的多模式匹配算法.計算機系統應用,2021,30(4):210–215. /1003-

3254/

Multi-Pattern Matching Algorithm of Computer Network Intrusion Detection System

XUE Fang

1

, LIN Li

2

1

2

(Informatization Center, Jimei University, Xiamen 361021, China)

(Computer Engineering College, Jimei University, Xiamen 361021, China)

Abstract: This study optimizes the multi-pattern matching algorithm for the intrusion detection system in the computer

network, so that the system can be in operation in the high-speed environment. First, we comprehensively analyze the

algorithm and principle for network intrusion detection. Second, we elaborate the idea of optimizing the multi-pattern

matching algorithm for its implementation, so that the algorithm efficiency is incread and then the detection system is

improved. In summary, the optimized algorithm can enhance the network detection system.

Key words: computer network; network intrusion detection; multi-pattern matching algorithm

1 引言

隨著現代互聯網的不斷發展, 網絡規模持續擴大,

網絡的使用也開始發展為全球化的方向. 在此背景下,

網絡入侵攻擊事件頻發. 傳統的防火墻技術無法對網

絡安全性進行保證, 所以需要實現網絡入侵檢測系統

(IDS)的設計. 網絡入侵檢測系統指的是主動積極的安

全防護技術, 其逐漸發展為網絡安全領域研究的重點

內容

[1]

. 在網絡入侵檢測系統工作過程中, 大部分為被

動的監聽, 利用關鍵網段得出網絡傳輸數據包, 通過多

種檢測分析的方式對數據包進行分析, 從而尋找入侵

的痕跡. 在網絡入侵檢測系統檢測的時候, 并不會對網

絡性能造成影響, 還能夠提高網絡攻擊事件定位的效

果. 現代分析網絡入侵檢測系統的主要方法為基于特征、

異常的檢測, 由于異常檢測過程中的學習時間比較長,

所以一般利用基于模式匹配特征檢測

[2]

. 以此, 本文就

對網絡入侵檢測系統的多模式匹配算法進行全面分析.

2 網絡入侵檢測

2.1 網絡入侵檢測的原理

因為傳統的安全策略無法有效滿足安全的實際需

① 收稿時間: 2020-08-19; 修改時間: 2020-09-15, 2020-11-06; 采用時間: 2020-11-17; csa在線出版時間: 2021-03-30

210

2021

年 第

30

卷 第

4

期

計算機系統應用

求, 從而產生了入侵檢測系統, 并且在發展過程中逐漸

成為動態安全技術的代表, 使計算機安全領域的發展

與研究有所促進. 入侵檢測系統為計算機系統與網絡

中的安全事件檢測的技術, 主要包括數據采集、分析

與結果處理3個功能. 圖1為入侵檢測系統基本的結構.

數據

數據采集

數據

數據分析

事件

結果處理

事件

圖1 入侵檢測系統的基本結構

在網絡入侵檢測系統中, 數據分析模塊是核心模

塊, 由于模式匹配原理簡單、可擴展性好, 現代網絡入

侵檢測系統利用廣泛采用模式匹配的方法進行數據分

析. 隨著科技的日新月異, 網絡的規模也不斷擴大, 網

絡帶寬量也逐漸增加, 要求網絡入侵檢測性能處理的

效率得到改進, 否則會導致出現入侵漏報的情況, 也就

無法充分發揮網絡入侵檢測系統的優勢.

模式匹配算法應用于入侵檢測領域, 是將攻擊模

式庫中的攻擊模式與待檢測網絡數據進行匹配, 若匹

配成功則系統判斷出現了網絡攻擊. 目前的模式匹配

算法分為單模式和多模式匹配, 其中典型單模式匹配

算法包括KMP算法和BM算法, 多模式匹配算法包

括AC算法和AC-BM算法

[3]

.

2.2 傳統網絡入侵檢測算法

在1977年, Boyer和Moore提出了BM算法

[4]

, 促

進了模式匹配算法的發展. 此算法在進行匹配時包含

兩個并行算法, 壞字符和好后綴算法, 目的是讓模式串

每次向右移動盡可能大的距離.

多模式匹配即在一個文本串中同時查找多個模式

串, 較之單模式匹配更易應對不斷擴大的入侵特征庫,

因此現今主流的IDS使用的基本都是多模式匹配算

法. AC (Aho-Corasick) 算法作為最經典的多模式匹配

算法被許多IDS采用, 該算法包含預處理和匹配兩個

階段, 將待匹配的入侵特征模式串轉換為樹狀有限狀

態自動機, 然后進行掃描匹配.

BM算法是一種性能較好的模式匹配算法, 該算法

在不匹配的情況下可以產生跳躍, 從而減少匹配次數,

但無法滿足日益復雜的網絡入侵類型; AC算法記錄的

自動機耗費了大量的存儲空間. 此外, AC與BM網絡

入侵檢測算法具有較大的漏配量和無效配的情況, 降

低系統的檢測精準率與匹配速度, 所以就要對網絡入

侵檢測算法進行改進

[5]

.

3 檢測系統模式匹配算法優化

3.1 單模式匹配算法的改進

1980年, Horspool提出了改進的BM算法

[6]

, 也就

是BMH算法. 簡化了BM算法, 執行方便, 效率也有

所提高. 有n長度的文本字符串T 與m長度的模式字

符串P. 在改進BM算法過程中, 不匹配過程中的正文

與模式移動距離有所擴大. 它不再像BM算法一樣關

注失配的字符, 它的關注的焦點在于匹配文本每一次

匹配失敗的最后一個字符X, 根據這個字符X是否在

模板出現過來決定跳躍的步數, 否則跳躍模板的長度.

如果字符X不在模式P中, 則跳躍的步數為模式P的

長度, 字符X在模式P中, 跳躍的步數為字符X距離

離尾部最近的字符X的距離(不包括最后一個字符).

{

dist[X]=

m;X字符在P中未出現

}

m

j=max{j|P

[

?

j

]

j;X字符在P中出現

=x,1≤j≤m?1}(1)

利用dist函數的分析表示,

dist[T[j]]≤m

. 以此看

出來, 模式在所設置的長度中最大距離的對右移動. 模

式正文匹配的結構詳見圖2, 在

T[j]??P[j]

時, 此模式

通過BM算法在

dist[T[j]]

個位置中移動. 利用正文的

i+dist[T[j]]

位置實現重新匹配檢查, 忽視T[i+v+1]

模式串的檢查. 如果模式中沒有

T[i+v+1]

, 那么使模

式P對右移動距離為m+1, 不對

T[i+v+1]

進行匹配

檢查

[7]

.

正文 T

iui+v+1

模式 P

ju

圖2 模式正文匹配示例

211

計算機系統應用

2021

年 第

30

卷 第

4

期

本文改進算法的主要思想為:

首先, 假設變量k為模式第一次與最后一次的匹

配字符, 將BM算法作為基礎, 在出現不匹配的時候, 能

夠實現T [k+1]的判斷. 如果出現T [k+1], 那么模式移動

距離假設為L, 規定

L=max{dist[T[k+1]],dist[T[j]]}+1

,

其中的變量i和前文相同, 詞表達式的含義就是對

T[k+1]

和

dist[T[j]]

的大小對比, 實現正文與模式最大移動距

離的進行接下來的匹配. 通過L的賦值表示, 在對是否

存在

T[k+1]

模式判斷過程中, 能夠提高下一次匹配的

移動模式距離. 以此匹配移動模式, 假如完全匹配, 表

示已經成功地進行匹配. 如果沒有完全匹配, 移動模式

就不發生改變, 直到正文結束

[8]

.

全面考慮從右到左的正文與模式匹配, 模式右邊

的字符匹配大于左邊. 假如具有長模式的情況, 和左邊

不匹配時候進行對比, 需要的時間成本量比較大. 為了

方便算法的實現, 在本文中實現針對性方案的設計. 在

算法改進之前對比正文位置字符與模式首字符, 如果

不匹配直接判斷T [k+1], 繼續下個匹配過程. 之后根據

以上改進算法實現匹配對比, 降低不必要匹配過程, 從

而節約匹配時間

[9]

.

3.2 多模式匹配算法的改進

網絡入侵檢測系統能夠深入檢測執行數據包, 并

且全面掃描負載或者已經定義規則集的匹配模式串,

檢測是否具備入侵檢測事件

[10]

.

3.2.1 分析算法的后綴函數

在BM算法中, 在匹配過程中比較了一個模式的

長度, 而且存在之前匹配的結果, 在后面的匹配過程中

被“遺忘”的情況, 模式串長度越長效率越低. 本文使改

進的BMH算法和傳統BM算法實現實驗對比, 此實

驗主要包括的測試指標為BM與改進BMH算法字符

數量、運行的時間和BM算法字符比較數量和使用后

綴規則數量.

因為入侵檢測實現自檢, 其模式串的長度設置為

20–30字符. 本文通過隨機的選擇開展實驗, BM與改

進BMH算法的運行時間比詳見表1. 通過表可以看出

來, 兩種算法的總字符數量是相同的, 但是基于時間復

雜度中, 改進BMH的性能更加良好.

3.2.2 算法描述

基于傳統BM算法, 充分考慮文本串中的字符T [j]

并不會出現在模式串中, 如果其下個字符T [j+1]和模

式串中的首字符P[1]相同, 也就是T [j+1]=P[1], 以此

212

創建滑動距離函數2, 簡化判斷的過程, 使比較次數降

低, 提高匹配的效率. 在分析傳統BM模式匹配算法過

程中, 模式串中出現重復字符的時候會導致指針回溯

的問題, 那么在本文函數中使用“取子串”的方法能夠

避免出現指針回溯的問題

[11]

. 算法流程如算法1.

表1 BM與改進BMH算法運行的總時間對比(單位: s)

模式串長度

BMBMH

524.521118.9525

1924.521118.4152

1128.524221.6251

1532.526424.6254

2036.352125.6255

2239.542226.9452

2644.625430.6242

2850.625430.3642

3052.62535.9142

3561.25440.2541

算法1. FBM模式匹配算法

輸入: 文本串T, 模式串P

輸出: 文本串T中模式串P的出現起始位置

1. 假如此文本串中從位置j開始往左一個子串和模式串開展從右到

左對比, 如果出現不匹配的情況, 就要調用滑動距離函數

Slidel(T[j])

;

2. 假如T [j]在P, 在算法過程中重新匹配正文中的

j+Slidel(T[j])

位置;

3. 假如T[j]并沒有處于P中, 那么j=j+1并且對滑動距離函數

Slide2(T[j])調動;

4. 對步驟3反復的進行, 直到對匹配位置尋找后才能夠進行匹配, 或

者匹配的過程失敗;

5. 將文本串T中的模式串輸出P的起始位置

[12]

.

BMH算法在改進過程中的重點為定義給定模式

P=P

1

P

2

···P

m

從字母到正整數的映射:

Slide: C→{1,2,…,m}

其中, c∈∑(假設∑指的是所有英文字母集合)

Slide1指的是滑動距離函數設置為1, 其給出正文

中的任意字符c在模式中的距離, 具體定義為:

?

?

?

?

?

?

如果任意字符C不出現P中

?

?

?

?

Slide1[c]=

?

?

?

?1,

或者c=P

j

(

j=m

)

?

?

但是c??P

j

(1

≤j≤m?1)

?

?

?

?

?

?

?

?

?

?

m?j,

j=max(j:P

j

=c,1≤j≤m?i?1)

i指的是模式串失配的位置

(2)

Slide2指的是滑動距離函數2, 其能夠給出正文中

會出現的任意字符位置, 具體定義為:

{

Slide2[c]=

?1,若任意字符c??P

i

m?1,若任意字符c=p

j

P

i

為模式串首(3)

2021

年 第

30

卷 第

4

期

計算機系統應用

3.3 算法實現

預處理階段在讀入規則文件的時候, 使模式組劃

分成為多字節模式組與單字節模式組, 將兩者添加到

相應模式組中. 針對單字節模式串組, 預處理階段不進

行處理. 改進算法以多字節模式串組計算前綴和后綴

索引、跳躍距離Shift表, 計算的方法為: 得出最短模

式長度m, 使其成為匹配窗口大小. 取每個模式最后

B個字符對Hash值計算, B個字符指的是一個塊字符.

Shift表中將字符串中全部塊字符在T時的移動距離進

行計算. 針對每個出現的多字節模式串中字符塊, 使二

維位圖EXIST_P中的位置標記成為1, 其他標記成為

0. 以此, 在匹配的時候如果查找文本字符塊處于位圖

EXIST_P標記成為0, 那么此字符串并不會在多字節模

式串組任何模式串中出現. 二維圖計算方法為:

EXIS

{

T_P(char1char2)=

1,char1char2在模式串中

0,char1char2不在模式串中

(4)

以改進算法思想, 圖3為改進算法的實現流程. 為

了能夠有效地簡化流程, 數組下標為字符的位置

[13]

.

Start

k=m, min=m?1

k<=n

i=k

T [i?min]=P[1]k=k+m+1

N

j=m

T [k+1]在 p 中出現

N

N

T[i]=P[j]

k=k+L

N

i=i?1; j=j?1

j=1

Writeln pattern matched at i

End

圖3 改進算法的實現流程

具體的流程為:

1) 對K≤n (n為待檢測字符串T的長度)是否成立

判斷, 如果k

要小, 此時就要對其進行匹配檢查, 模式和正文對其, 對

比正文位置字符和首字符. 假如出現不匹配的情況, 就

到最后一步. 假如k>n, 匹配的過程失敗, 程序就結束.

2) 從左到右匹配模式和正文, 并且對比, 如果模式

字符串和正文字符串進行匹配, 對匹配的位置進行記

錄, 以此說明能夠成功匹配, 結束程序. 假如某位置的

字符串出現不匹配的情況, 就進入到步驟3).

3) 對目前的匹配操作進行判斷, 模式中的正文和

模式最后一位對應位置是否有下位字符, 以判斷結果

變量k值計算, 之后轉到步驟1)

[14]

.

處理階段時間復雜度為O(m+σ), 其中σ為x與已

匹配部分在P中的位置, 搜索階段最壞情況下時間復

雜度為O(mn), 模式字符串的長度大小將影響到時間

復雜度, 一般文本字符的平均比較數在1σ和2/(σ+1)

之間.

圖4為改進算法的匹配過程, 算法以二維圖判斷

某字符串是否在模式串中出現, 首先讀入字符串“st”,

EXIST_P(st)為0, 使窗口向后移動一位. EXIST_P(tr)

值為0, 繼續使窗口向右移動一位. EXIST_P(rc)值為1,

此處會出現匹配, 通過本文算法實現匹配, 查找Shift

表, 后續文本串根據同樣方法進行匹配.

1

s

t

rcmatecadnarchofShift

2

1

Output

3

2

4

0

5

1

0

{Search}

6

4

{Arch}

圖4 改進算法的匹配過程

通過上述匹配可以看出來, 使用原本算法匹配的

時候, 要計算9次Hash值并且查找Shift表實現跳躍.

改進算法能夠以位圖判斷此字符串是否處于模式串中.

在以上匹配過程中一共計算6次Hash值, 并且查找

Shift表實現跳躍.

4 算法的實驗和分析

為了對今后算法性能進行校驗, 本文用改進后算

法和傳統BM算法實現實驗對比. 在Win 7環境中實

驗, 系統配置2.66 GHz Intel CPU. 實驗過程中使用官

網中的模式串, 以Snort匹配過程, 使所有規則文件規

則字符串作為模式組, 在實驗過程中依次使用此模式

213

計算機系統應用

2021

年 第

30

卷 第

4

期

組對改進算法實現校驗. 在查找文本通過MIT Lincoln

實驗室中的DARPA99數據集的數據構成, 通過

DARPA99測試數據集中選擇4 MB測試數據. 圖5為

在不同最小模式中的算法性能對比. 通過圖5可知, 在

模式串組中具備單字節模式串與兩個字節模式串時,

改進算法性能有所提高.

150

傳統算法

145

改進算法

140

)

s

m

(

135

e

m

T

i

130

125

120

Min length of rule

圖5 不同最小模式中的算法性能對比

圖6為不同模式串集的算法性能, 通過圖6可知,

在模式串集模式串數量不斷增加的過程中, 改進算法

與原算法的性能相同. 但是在模式串數量比較少的時

候, 改進算法的匹配運行時間比原算法的匹配運行時

間要短. 在入侵檢測系統中, 匹配規模集中規則數量不

超過400條, 改進算法的應用價值良好. 增加到1200條

時, 兩種算法應用價值相當. 在2000條時, 改進算法使

用價值良好. 實際應用情況中, 檢測條目越多, 將嚴重

影響網絡訪問時延, 導致用戶上網體驗差; 檢測條目越

少, 匹配到的威脅少, 對網絡安全危害增大, 一般檢測

條目約在500–800之間.

400

350

傳統算法

改進算法

300

)

s

m

(

250

e

m

200

T

i

150

100

016002000

Mun of rule

圖6 不同模式串集的算法性能

本文也對改進算法在不同數據包時的情況, 模式

串組使用Snort規則文件. 通過圖7表示, 數據

214

包越大, 改進算法所消耗時間短與原本算法, 能夠提高

其性能. 本文改進算法的測試平均查詢時間為0.38 s,

傳統算法需要2.16 s, 以此表示能夠實現快速查詢, 滿

足用戶的實際使用需求.

1100

1000

傳統算法

改進算法

900

800

)

s

m

(

700

e

m

600

T

i

500

400

300

51015202530

Size of packsts (MB)

圖7 不同數據包大小的算法性能

通過實驗結果表示, 改進之后的BM算法性能提

高, 匹配效率比傳統算法要高. 通過本文中的改進算法

能夠使入侵檢測系統性能得到提高, 實用價值良好.

5 結束語

網絡帶寬在網絡技術持續發展過程中不斷增加,

入侵監測系統處理的性能也要相應不斷得到提高, 使

得大流量網絡環境的需求得到滿足. 本文對模式匹配

算法進行全面的研究, 并且對傳統模式匹配算法進行

改進. 通過實例測試可以看出來, 改進的多模式匹配算

法能夠有效滿足網絡使用過程中的需求, 并且提高系

統檢測效率. 另外, 改進算法還能夠降低冗余移動, 使

匹配速度與查找速率得到提高, 對入侵檢測系統的性

能進行改進.

參考文獻

1

于粉娟. 基于多模式匹配算法的計算機網絡入侵檢測研

究. 自動化與儀器儀表, 2018, 15(5): 159–161.

2

周小松, 劉帥. 多網絡環境下的差異化入侵特征檢測平臺

的設計與實現. 現代電子技術, 2017, 40(10): 149–152.

3

呂峰, 葉東海, 楊宏, 等. 模糊數據挖掘和遺傳算法的網絡

入侵檢測方法. 電子技術與軟件工程, 2017, 18(4): 185–186.

4

Boyer RS, Moore JS. A fast string arching algorithm.

Communications of the ACM, 1977, 10: 762–772.

5

劉達. 基于樸素貝葉斯分類算法的數據庫入侵檢測系統.

2021

年 第

30

卷 第

4

期

計算機系統應用

網絡空間安全, 2017, 8(8-9): 32–34.

6

Horspool NR. Practical fast arching in strings. Software

Practice and Experience, 1980(6): 50–56.

7

關麗. 基于模式匹配的計算機網絡入侵防御系統. 電子制

作, 2019, 18(13): 81–82, 96. [doi: 10.3969/.1006-5059.

2019.13.032]

8

鮑海燕. 基于K-means算法的入侵檢測系統研究. 現代計

算機, 2019, 19(23): 9–13. [doi: 10.3969/.1007-1423.

2019.23.002]

9

朱平哲. 網絡入侵檢測與防護算法系統的實現. 安徽電子

信息職業技術學院學報, 2019, 18(3): 7–12. [doi: 10.3969/

.1671-802X.2019.03.002]

10

常剛, 羅作民. 基于聚類算法的入侵檢測系統設計. 自動化

與儀器儀表, 2018, 15(9): 110–113.

11

吳志福. 基于一次判斷雙字符比較的模式匹配算法. 科技

通報, 2018, 34(4): 240–242, 261.

12

劉建. 基于改進神經網絡的網絡入侵檢測. 科技創新與應

用, 2018, 16(2): 11–12, 14.

13

Chen JL, Li QY, Li JQ, et al. DOA estimation of MIMO

Radar bad on covariance matching SL0 algorithm. Radar

Science and Technology, 2019, 17(1): 19–24.

14

王子玲, 賈舒宜, 修建娟, 等. 基于人工神經網絡的多模型

目標跟蹤算法. 海軍航空工程學院學報, 2019, 34(4): 343–

348.

215