一種面向入侵檢測系統(tǒng)的模式匹配算法的改進(jìn)

杜廣林 顧炳根

桂林理工大學(xué)信息科學(xué)與工程學(xué)院 廣西 541004

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，人們在享受其帶來的越來越多的便利的同時(shí)，也遭受著日趨增多的針對(duì)企業(yè)公司和網(wǎng)絡(luò)用戶的攻擊。黑客事件頻頻發(fā)生，企業(yè)和用戶的重要數(shù)據(jù)及財(cái)產(chǎn)安全面臨嚴(yán)重威脅。據(jù)報(bào)道，全球平均每 20秒鐘就有一次入侵事件發(fā)生，僅美國每年造成的損失就高達(dá)100億美元。為了確保網(wǎng)絡(luò)上主機(jī)的安全，通常使用如下的幾種防范技術(shù)如：數(shù)據(jù)加密技術(shù)，數(shù)字簽名技術(shù)，訪問控制技術(shù)，防火墻技術(shù)和入侵檢測技術(shù)等等。這其中，入侵檢測技術(shù)作為一種主動(dòng)防御技術(shù)，相較于其他被動(dòng)防御技術(shù)發(fā)揮著更為重要的作用。目前，入侵檢測技術(shù)已經(jīng)成為網(wǎng)絡(luò)安全工具的主要研究和發(fā)展方向。

所謂入侵檢測技術(shù)是指對(duì)外來入侵行為進(jìn)行防范和檢測的一種技術(shù)，通過采集系統(tǒng)日志和網(wǎng)絡(luò)中數(shù)據(jù)來進(jìn)行分析比對(duì)，從而檢測出威脅網(wǎng)絡(luò)安全的行為。如圖1所示一般的入侵檢測系統(tǒng)(Intrusion Detection System，IDS)通常由以下幾個(gè)部分組成：事件產(chǎn)生器(Event-Box)，分析引擎(Analysis-Engine)，事件數(shù)據(jù)庫(Database-Box)和響應(yīng)單元(Response-Box)。分析引擎是 IDS的核心模塊，負(fù)責(zé)對(duì)原始數(shù)據(jù)的采集和分析，通過檢測算法比對(duì)判斷是否是入侵行為。在IDS的實(shí)現(xiàn)中，許多研究都集中于對(duì)于分析引擎的改進(jìn)，以期望提高入侵檢測的效率和準(zhǔn)度。改進(jìn)模式匹配算法是提高分析引擎效率的就是一種可行性很高的方法。

圖1 IDS結(jié)構(gòu)圖

1 介紹和分析幾種經(jīng)典的模式匹配算法

模式匹配算法是指在長度為n的正文T串中找出長度為m的模式串S第一次出現(xiàn)的位置，一旦找到就稱產(chǎn)生一次匹配。在實(shí)際應(yīng)用中，有的系統(tǒng)可能需要找出所有匹配。IDS中使用的模式匹配算法，按照每次能夠匹配的模式串的個(gè)數(shù)主要分兩類：單模式匹配算法和多模式匹配算法。

所謂單模式匹配算法指的是在模式匹配中，一次只對(duì)一個(gè)模式串進(jìn)行匹配。而多模式匹配算法則是在模式匹配中，能同時(shí)對(duì)多個(gè)模式串進(jìn)行匹配。常用的單模式匹配算法有：BM算法，BMH算法和BMHS算法等。常用的多模式匹配算法有：WM算法，AC算法等。在入侵檢測系統(tǒng)中，通常較多采用單模式的BM 算法或多模式的WM算法。相比較而言，BM算法在空間性能上要優(yōu)于WM算法，其在內(nèi)存空間的消耗更小。

1.1 BM算法

BM(Boyer-Moore)算法是 Boyer和 Moore在 1977年提出的一種經(jīng)典的單模式匹配算法。它是一種基于后綴搜索的算法，也就是說此算法從右向左進(jìn)行逐字符的比較。如果字符相等，則左移一位，繼續(xù)進(jìn)行比較；如果在比較中，出現(xiàn)了某個(gè)字符的不匹配，則會(huì)觸發(fā)兩種啟發(fā)性規(guī)則之一即：壞字符(Badcharcter)和好后綴(Goodsuffix)，并取兩者的最大值進(jìn)行位置偏移。

(1) 壞字符(Badcharcter)規(guī)則

所謂壞字符規(guī)則是指若文本串T和模式串S在某個(gè)位置出現(xiàn)了不匹配，則根據(jù)T串在不匹配位置的字符c是否出現(xiàn)

在S串中的原則進(jìn)行位移，壞字符的右移公式：公式(1)

(2) 好后綴(Goodsuffix)規(guī)則

好后綴規(guī)則是針對(duì)模式串S中的子串r，r是文本串T與模式串S已匹配的一段字符串，它分為如下兩種情況：

① 若已匹配的子串r在S串的中間某個(gè)位置重復(fù)出現(xiàn)，則將S串右移移動(dòng)到r最右端出現(xiàn)的位置與T串中的r對(duì)齊。

② 若已匹配的子串r在S中不再出現(xiàn)，但是r的一個(gè)子串r′在S串的前綴出現(xiàn)，則將S右移，使得S串和T串中的r′對(duì)齊。

好后綴的右移公式如公式(2)所示：

1.2 BMH算法

盡管在BM算法在理論上很完備，但是由于其比較復(fù)雜，尤其是好后綴規(guī)則計(jì)算復(fù)雜且難以理解。在實(shí)際應(yīng)用中，它也并不是最快的匹配算法。因此在實(shí)踐中，IDS通常采用它的簡化算法。

BMH(Boyer-Moore-Horspool)算法是首個(gè)對(duì) BM 算法的改進(jìn)算法，是Horspool于1980年提出的一種簡化算法。它僅僅保留了 BM 算法中的壞字符(Badcharcter)規(guī)則，并對(duì)其做了一定的修改。其修改后的規(guī)則如下：若模式串S與字符串T在某個(gè)字符發(fā)生了不匹配，則壞字符是模式串S末尾所對(duì)應(yīng)文本串T中的字符c，并根據(jù)c在S串中是否出現(xiàn)向右移動(dòng)。若c在S串中不存在，則S直接右移m長度；反之，則使S右移至c在S串中最右出現(xiàn)的位置與T串中的c對(duì)齊。

1.3 BMHS算法

BMHS(Boyer-Moore-Horspool-Sunday)算法是 Sunday于1990年在BMH算法的基礎(chǔ)上的一種改進(jìn)算法，利用文本窗口的下一位字符進(jìn)行啟發(fā)，即一位啟發(fā)規(guī)則，可實(shí)現(xiàn)最大為m+1的偏移量。BMHS算法的思想具體如下：當(dāng)文本串T與模式串 S出現(xiàn)失配時(shí)，則判斷文本窗口的下一位，即啟發(fā)位字符c是否在S串中出現(xiàn)。若c不存在于S串中，則S就可進(jìn)行一個(gè)偏移量為m+1的一個(gè)右移；反之，若c存在于S中，則右移S串使S串中c出現(xiàn)的最右邊的位置與T串中的c對(duì)齊。于是可以看出，當(dāng)啟發(fā)字符不存在與S串中的時(shí)候，BMHS算法的移動(dòng)距離是要高于BM算法和BMH算法的，從而實(shí)現(xiàn)了一個(gè)更高的效率。

2 對(duì)于BMHS算法提出的一種改進(jìn)算法BMHSN

雖然BMHS算法可以實(shí)現(xiàn)最大值為m+1的偏移量，但是它的缺點(diǎn)也很明顯，就是若啟發(fā)位的字符存在于模式串 S中的時(shí)候，BMHS算法的移動(dòng)距離是要小于BMH算法的。因此，假如啟發(fā)位的字符在S串中出現(xiàn)的頻率較高的話，那么BMHS的效率將大大降低，反而會(huì)低于BMH算法。怎樣更好的保證最大距離m+1出現(xiàn)的頻率，就成為了下一步算法改進(jìn)的重點(diǎn)。

當(dāng)啟發(fā)字符c不存在于S串時(shí)，右移量即為m+1，所以BMHS算法的這一部分保留不做改動(dòng)。而所需要改動(dòng)的部分就是當(dāng)c存在于S串中，右移量計(jì)算的方法。因此提出了如下幾點(diǎn)改進(jìn)策略：

(1) 若啟發(fā)字符c存在于S串中，首先判斷c首次出現(xiàn)的位置是否是S串的第一個(gè)字符，如果是則右移 m位使 S串的第一個(gè)字符與c對(duì)齊；否則對(duì)比T串中c的前一個(gè)字符與S串中c的前一個(gè)字符是否相同。

(2) 若不相同，則右移S串m+1個(gè)位置；如果相同，則判斷c是否是S串的最后一個(gè)字符。

(3) 若c是S串的最后一個(gè)字符，則將S串右移一個(gè)位置；否則，判斷S串中c后一字符與啟發(fā)字符后一個(gè)字符是否相同。

(4) 若不相同，則右移S串m+1個(gè)位置；若相同則將S串右移使S串中的c與T中的啟發(fā)字符對(duì)齊繼續(xù)比較。

圖2 BMHSN算法流程圖

改進(jìn)后算法BMHSN的流程圖如圖2。下面來看一個(gè)三種算法一次移步后的例子，如表1。

表1 三種算法一次移步后的例子

通過表1可以看出，BMH算法的位移量為m，而BMHSN為 m+1；假如啟發(fā)位的字符存在于模式串中，那么 BMHS的位移量要小于BMH算法；BMHSN算法與BMHS算法相比m+1位移量的出現(xiàn)幾率要大于BMHS算法。

3 結(jié)束語

本文重點(diǎn)分析了單模式匹配算法中的幾種經(jīng)典算法：BM，BMH和BMHS，指出了幾種算法的優(yōu)點(diǎn)和缺點(diǎn)。結(jié)合幾種算法的優(yōu)缺點(diǎn)，提出了一種更高效的算法—BMHSN算法。此算法提高了最大位移量m+1的出現(xiàn)幾率，并且大大減小了當(dāng)啟發(fā)位字符存在于模式串時(shí)，位移量小于BMH算法的幾率。

[1]雒明世,張群良.淺析網(wǎng)絡(luò)的入侵檢測.電信減緩.2005.

[2]唐正軍,李建華.入侵檢測技術(shù)[M].北京:清華大學(xué)出版社.2004.

[3]Robert S.Boyer,J.Strother Moore.A fast string searching algorithm[J].Communication of the ACM.1997.

[4]Horspool R N.Practical fast searching in strings [J].Software-Practics&Experience.1980.

[5]Sunday D M.A very fast substring search algorithm[J].Comm unications of the ACM.1990.