(1.杭州電子科技大學(xué) 計算機(jī)學(xué)院，杭州 310018；2.亞龍（安恒）信息科技（杭州）有限公司， 杭州 310035)

摘 要：針對Web入侵檢測系統(tǒng)中存在的攻擊模式誤匹配與效率問題，提出了一種高效的多模式匹配算法MPMA。MPMA通過構(gòu)建比較樹，并在比較樹的每個節(jié)點中記錄下次比較的字符位置以提高比較效率，并利用（模式，偏移）信息對來搜索可能符合的匹配模式。詳細(xì)的實驗以及與現(xiàn)有算法的比較表明，提出的MPMA不僅適合于Web入侵檢測系統(tǒng)，同時在時間、空間和匹配率性能上具有更高的效率。

關(guān)鍵詞：入侵檢測系統(tǒng)；多模式匹配；Web

中圖分類號：TP393.08文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2009)04-1528-04

Efficient multi-pattern matching algorithm for Web intrusion detection systems

FAN Xuan-miao1，ZHENG Ning1，F(xiàn)AN Yuan2

(1.School of Computer Science， Hangzhou Dianzi University， Hangzhou 310018， China；2.Hangzhou DB Appsecurity Information Technology Co.， Ltd， Hangzhou 310035， China)

Abstract:To overcome the defects of 1 pattern matching and time-and-space efficiency in Web intrusion detection systems (IDSs)，this paper proposed an efficient multi-pattern matching algorithm called MPMA.With building comparison tree， every tree node had a position value which could tell you where an octet comparison should be made next， and MPMA used(pattern，offset)pair to find possible matching patterns. Detailed experimental results and comparison with existed algorithms prove that the proposed MPMA not only fits Web IDS， but also outperforms current state-of-the-art schemes in terms of time efficiency， space efficiency and matching ratio.

Key words:intrusion detection systems(IDS); multi-pattern matching; Web

0 引言

由于管理者疏忽、系統(tǒng)漏洞、新的攻擊手法層出不窮等各種因素，使得Web服務(wù)器遭受網(wǎng)絡(luò)攻擊的事件頻繁發(fā)生[1]。其中以Web應(yīng)用類型的攻擊最多，而大部分Web應(yīng)用并沒有采取專門有效的防護(hù)措施來應(yīng)對。導(dǎo)致Web應(yīng)用進(jìn)一步面臨威脅的另一個因素是，Web服務(wù)器與應(yīng)用底層架構(gòu)的變化以及使用非安全開放源代碼組件現(xiàn)象的增加[2]。Web服務(wù)器與Web應(yīng)用已經(jīng)從最初提供簡單的靜態(tài)內(nèi)容演變到提供豐富的動態(tài)內(nèi)容；除了可以創(chuàng)建動態(tài)頁面與啟動應(yīng)用程序外，還可以與數(shù)據(jù)庫進(jìn)行通信以生成對用戶有用的內(nèi)容。大多數(shù)Web服務(wù)器平臺都將應(yīng)用程序與服務(wù)器捆綁在一起，即使最簡單的網(wǎng)站也會與Web應(yīng)用進(jìn)行交互，這就為攻擊提供了更多的機(jī)會。

由于Web服務(wù)通常會自動打開，訪問控制機(jī)制的應(yīng)用在有些情況下是不切實際的。此外Web服務(wù)器在結(jié)構(gòu)方面很復(fù)雜，在一個位置安裝所有保護(hù)機(jī)制也不可能達(dá)到理想效果，在那些防御機(jī)制有效的地方，需要的配置變化依賴于引起攻擊的根源和特殊的Web服務(wù)結(jié)構(gòu)。有一些策略可以使入侵者繞過IDS或使IDS不起作用。例如，入侵者可以試圖使網(wǎng)絡(luò)溢出或在虛擬包中插入一些新的惡意包來實現(xiàn)上述策略[3]。針對Web攻擊，目前主要的措施是采用入侵檢測系統(tǒng)（IDS）盡快、盡可能可靠地檢測出各種入侵行為[4]。IDS同時能對數(shù)據(jù)幀的幀頭與負(fù)載進(jìn)行檢測，并與已知的所有攻擊方式進(jìn)行比較，找出可能的攻擊方式。也就是說，如果將數(shù)據(jù)包流當(dāng)做一個很長的字符串，IDS的工作就是檢測該字符串中的子字符串是否與已知的攻擊模式相符，并根據(jù)預(yù)定的方案采取相應(yīng)的防范措施，以阻擋使用者或以報警的方式進(jìn)行處理。針對字符串掃描檢測，文獻(xiàn)［5，6]分別采用哈希與基于簽名的方式，雖然這些方法能快速地找出可能的攻擊模式，但是無法避免錯誤匹配問題。而Snort[7]方法在字符串檢測上花費高達(dá)70％的執(zhí)行時間和80％的指令執(zhí)行時間，效率并不理想。

本文針對Web入侵檢測系統(tǒng)中存在的攻擊模式誤匹配與效率問題，提出了一種高效的多模式匹配算法MPMA。該算法基于比較樹，利用（模式，偏移）信息對來搜索可能的匹配模式，比較樹通過每個節(jié)點存儲相應(yīng)的位置信息，記錄下次比較的字符位置以提高搜索效率。

1 多模式匹配算法MPMA

1.1 問題描述

對于檢測的數(shù)據(jù)包形成的字符串，定義為T，T內(nèi)每個字符表示為t1，t2，…，t|T|。其中|T|表示T的長度。查找的n個不同的模式定義為Pi(i∈[1，n])，Py=p(y)1

p(y)2…p(y)|py|(y∈[1，n])。多模式匹配算法MPMA的目的就是要找出上一個位置x和Py，滿足以下條件：

tx+i=pyi，i∈[1，|py|]（1）

MPMA并不直接進(jìn)行模式比較，而是先將模式轉(zhuǎn)換為（模式，偏移）信息對，然后從比較樹的樹根開始進(jìn)行比較。此時所有的（模式，偏移）對均為候選項，即所有的（模式，偏移）對都可能出現(xiàn)在T上。接著讀取當(dāng)前所在節(jié)點的信息決定要對比的位置，經(jīng)過比較后，根據(jù)結(jié)果跳轉(zhuǎn)到特定的子節(jié)點上，重復(fù)上述比較步驟直到葉子節(jié)點，便可知T中可能包含哪些（模式，偏移）對。最后再針對這些可能符合的（模式，偏移）對進(jìn)行檢測匹配。

以圖1（a）中所示的比較樹為例，其中P={FAT，F(xiàn)ARM，TUTOR}，偏移為0～2。比較樹每個節(jié)點內(nèi)的數(shù)字表示所要比較的字符在T中的位置，樹根的3表示開始時要比較的位置是T的第三個字符。當(dāng)對第三個字符比較完后，根據(jù)比較結(jié)果決定選擇哪個子節(jié)點。例如目前的第三個字符為A，則將選擇最左的子節(jié)點進(jìn)行比較，而此時可能達(dá)到的葉子節(jié)點有（1，1）和（0，1），即經(jīng)過第一次比較，過濾掉了（1，1）和（0，1）以外的（模式，偏移）對。接著比較第四個字符，如果為R，則只需檢測其是否與（1，1）符合即可。

很明顯，上述方法存在兩個缺陷：a）模式匹配量大，當(dāng)取偏移為0～2時，由圖1（b）可知，需要處理的（模式，偏移）對是原模式個數(shù)的3倍，因此計算量和空間開銷都將增加；b）在進(jìn)行（模式，偏移）對比較時，存在所有可能符合的（模式，偏移）對匹配不完全問題。由圖1（b）可知，當(dāng)要比較第一個字符時，只有（0，0）、（1，0）和（2，0）三個（模式，偏移）對能比較到。其他（模式，偏移）對由于沒有字符出現(xiàn)在該位置，將成為后續(xù)比較的候選項。



針對上述第一個問題，MPMA將采用虛擬節(jié)點壓縮方式減少計算量和空間開銷。針對第二個問題，MPMA采用兩種不同的節(jié)點構(gòu)建方法來處理：以速度優(yōu)先的節(jié)點算法（Speed-MPMA）；以空間大小優(yōu)先的節(jié)點算法（Size-MPMA）。

1.2 Speed-MPMA算法

Speed-MPMA比較樹CT建立算法偽代碼如下所示：

輸入：模式Pi(i∈[1，n])與最大偏移量max_offset

輸出：Speed比較樹CT

for all patterns Pi(i∈[1，n])

for j=0 to max_offset

root.candidate←((Pi，offsetj)←Pi)

end for

end for

Stack=，Stack←root

while stack is not empty

node←pop first element from stack; pos←Posparse(node)

for all (pattern， offset)

if get((pattern， offset)， pos) !=NULL

candidate_array[get((pattern， offset)， pos)]

else default_candidate←(pattern， offset)

end if

end for

for all candidate

if candidate_array[i] !=NULL

node.child[i].candidate←candidate_array[i]+default_candidate

else node.child[i].candidate←default_candidate

end if

end for

for all node.child

if (node.child[i] is not a leaf node)

Stack←Stack+node.child[i]

end if

end for

end while

算法的1~5行先將模式展開為（pattern，offset）形式，并把所有的（pattern，offset）設(shè)定為樹根的候選項candidate（pattern，offset）。其中偏移offset的最大值為max_offset。接著把樹根壓棧，并對棧進(jìn)行檢查，取出棧中節(jié)點，用子節(jié)點位置構(gòu)建算法Posparse產(chǎn)生節(jié)點位置。將該節(jié)點與所有的候選項進(jìn)行比較，如果該（pattern，offset）在Posparse產(chǎn)生節(jié)點的位置上，則將其放入候選數(shù)組candidate_array[]中；否則將其存入默認(rèn)的候選項default_candidate中。然后將candidate_array與default_candidate的候選項與對應(yīng)的子節(jié)點進(jìn)行關(guān)聯(lián)。最后將所有非葉子節(jié)點壓棧，得到構(gòu)建的比較樹CT。

子節(jié)點位置構(gòu)建算法Posparse如下：

輸入：節(jié)點node

輸出：節(jié)點位置pos

count[max_pattern_length + max_offset] =

for all (pattern， offset) po in node

for i=po.offset to (po.offset+po.pattern.length)

count[i]←count[i]+1

end for

end for

pos[]←sort(count[])

for i=0 to max_pattern_length+max_offset

if pos[i] can split (pattern， offset) from node

return pos[o]

end for

return-1

子節(jié)點位置構(gòu)建算法Posparse的主要功能是根據(jù)當(dāng)前的候選項candidate（pattern，offset），找出一個合適的位置作為建立子節(jié)點的依據(jù)。Posparse首先建立一個大小為最大偏移與最長模式的計數(shù)數(shù)組，接著檢查所有節(jié)點的候選項，并將該候選項對應(yīng)字符位置的計數(shù)加1；然后將該數(shù)組按從大到小排序，從字符最多的位置開始，如果該位置可將任意兩個候選項分開，則返回該位置。

Speed-MPMA-search搜索算法實現(xiàn)字符串的模式匹配功能。Speed-MPMA-search根據(jù)Speed-MPMA算法建立的比較樹CT，從字符串T的起始位置開始，對每個節(jié)點，根據(jù)T[pos+node.offset]的字符決定選擇該節(jié)點的對應(yīng)子節(jié)點，直到找到葉子節(jié)點為止。當(dāng)?shù)竭_(dá)葉子節(jié)點時，將當(dāng)前的T與該葉子節(jié)點的候選模式進(jìn)行比較，直到找出所有的匹配模式為止。

Speed-MPMA-search搜索算法如下：

輸入：數(shù)據(jù)包字符串T， 模式P，Speed-MPMA比較樹CT

輸出：T所有匹配的模式

pos←0

while pos

node←CT.size.root

while node is not a leaf node

node←node.child[T[[pos + node.offset]]]

end while

compare T+pos with all node.candidate

pos←pos+CT.size.max_offset

end while

1.3 Size-MPMA

Size-MPMA與Speed-MPMA的最大區(qū)別在于候選項的產(chǎn)生方式。在Speed-MPMA中，如果子節(jié)點位置構(gòu)建算法Posparse所選定的位置上有任何候選項沒有字符存在時，就會指定到默認(rèn)子節(jié)點上。這將導(dǎo)致所有的子節(jié)點被復(fù)制，這種方法將產(chǎn)生巨大的空間消耗。Size-MPMA則針對該缺陷，將原來分布在每個子節(jié)點上的候選項集中到一個特殊的默認(rèn)子節(jié)點上，并把一個節(jié)點的候選項candidate（pattern，offset）根據(jù)子節(jié)點位置構(gòu)建算法產(chǎn)生的位置分為兩部分：一部分是該位置有字符的candidate（pattern，offset）；另一部分是該位置無字符的candidate（pattern，offset）。有字符的候選項作為一般子節(jié)點處理，無字符的部分作為默認(rèn)子節(jié)點處理。這種方式可以大量降低比較樹占用的空間消耗。

Size-MPMA比較樹建立算法偽代碼與Speed-MPMA比較樹建立算法基本相同，只需要將Speed-MPMA比較樹建立算法偽代碼的第18行刪除即可。也就是說，當(dāng)候選項數(shù)組為空時，該子節(jié)點不會被設(shè)定為任何值。默認(rèn)候選項default_candidate會被節(jié)點設(shè)置到默認(rèn)子節(jié)點default_child上。

Size-MPMA-search搜索算法偽代碼如下:

輸入：數(shù)據(jù)包字符串T，模式P，Size-MPMA比較樹CT

輸出：T所有匹配的模式

pos←0， stack=

while pos

stack←CT.size.root

while stack is not empty

node←pop first element form stack 

while node is not a leaf

node←node.child[T[[pos+node.offset]]

stack←stack+node.default_child

end while

compare T+pos with all node.candidate

end while

pos←pos+CT.size.max_offset

end while

2 混合算法Hybrid-MPMA

Speed-MPMA與Size-MPMA具有很大的相似性，在比較樹CT的構(gòu)建上，如前所述，其差異僅僅在子節(jié)點候選項的設(shè)定上。當(dāng)子節(jié)點位置構(gòu)建算法Posparse所選定的位置上有任何候選項無字符時，兩種算法的處理方式不同：Speed-MPMA會把這些候選項復(fù)制到所有的子節(jié)點內(nèi)，而Size-MPMA則把這些候選項集中放入默認(rèn)子節(jié)點中。在搜索算法中，Speed-MPMA經(jīng)過一個節(jié)點時，只需要其位置pos與T相比，即可知道下一個要處理的節(jié)點；而Size-MPMA除了要處理系統(tǒng)的子節(jié)點外，還需要處理默認(rèn)子節(jié)點。因此混合算法Hybrid-MPMA充分利用兩個算法的優(yōu)點，對常用的節(jié)點使用Speed-MPMA，而對少用的節(jié)點使用Size-MPMA。由于處理比較樹CT的順序是從根節(jié)點開始，假設(shè)T內(nèi)的字符服從統(tǒng)一分布，則每個子節(jié)點被處理的概率為父節(jié)點的1/256，當(dāng)節(jié)點越深，其被處理的概率越小。因此，在Hybrid-MPMA中，只需要設(shè)定一個合適的深度L作為閾值，當(dāng)深度小于等于L時，采用Speed-MPMA構(gòu)建節(jié)點；否則采用Size-MPMA構(gòu)建節(jié)點。

根據(jù)比較樹CT的特點，可以采用虛擬節(jié)點壓縮方式在保障時間效率基本不受影響的前提下，提高空間效率。對于圖1（a）和（c）中所示的比較樹，樹根左半邊的兩個子節(jié)點的候選項candidate（pattern， offset）非常相似，其中pattern部分完全相同，只有offset有定差。此時只需要建立其中的一個節(jié)點，另一個節(jié)點則建立虛擬節(jié)點，如圖2所示。

圖2（a）為圖1（a）中所示的比較樹的左邊部分；（b）為經(jīng)過虛擬節(jié)點壓縮后的子樹。虛擬節(jié)點記錄了兩個信息，一是與其相似的節(jié)點的位置，二是兩者之間的偏移差。這種方式在很大程度上節(jié)省了空間消耗，而產(chǎn)生的時間額外開銷非常小。

3 實驗分析

為了驗證提出的Hybrid-MPMA的性能，實驗中對Path AC算法[8]、FNP算法[9]的性能進(jìn)行了分析。系統(tǒng)采用Linux，2.4 GHz CPU，內(nèi)存512 MB。測試數(shù)據(jù)為858 MB，分為2 000個數(shù)據(jù)流。模式采用Snort的默認(rèn)規(guī)則集。為了考察最短模式長度（LSP）的影響，將LSP分成1~4共四組。

實驗1 對Hybrid-MPMA是否采用虛擬節(jié)點壓縮及采用不同偏移情況下的內(nèi)存消耗性能，當(dāng)節(jié)點深度L設(shè)置為2~10時，算法的內(nèi)存消耗性能如圖3所示。

從圖3中可以看出，當(dāng)采用虛擬節(jié)點壓縮后，在偏移相同的情況下，Hybrid-MPMA的內(nèi)存消耗將大大減少。如偏移為2時，采用虛擬節(jié)點壓縮的內(nèi)存消耗比不采用壓縮時平均要少540 KB。當(dāng)偏移量增加時，Hybrid-MPMA的內(nèi)存消耗將有所增加。隨著節(jié)點深度的增加，對于虛擬節(jié)點壓縮情況下，偏移為2、3時內(nèi)存消耗的性能變化不大。但是有一點值得注意，當(dāng)不采用虛擬節(jié)點壓縮時，偏移為3的內(nèi)存消耗比偏移為4的小，當(dāng)節(jié)點深度為5~10時，兩種情況下的內(nèi)存消耗基本相同；但是采用壓縮后，如圖3中所示，當(dāng)節(jié)點深度為10、偏移為4時的內(nèi)存消耗比偏移為3時的內(nèi)存消耗小680 KB。這是因為虛擬節(jié)點壓縮是根據(jù)模式偏移對終端的偏移差建立虛擬節(jié)點，在最大偏移越大的情況下，可以找到的虛擬節(jié)點越多，所以當(dāng)這兩個樹經(jīng)過虛擬節(jié)點壓縮后，偏移為4的樹可以找到比偏移為3更多的虛擬節(jié)點。經(jīng)過壓縮后，節(jié)點深度為10時，偏移為4的內(nèi)存消耗反而比偏移為3的低680 KB。

圖4所示為節(jié)點深度L變化時，Hybrid-MPMA的吞吐量性能。從圖4中可以看出，隨著節(jié)點深度的增加，Hybrid-MPMA的吞吐量性能逐漸增大。偏移為2時，算法的吞吐量從18.3增加到22.1 MBps；偏移為3時，吞吐量從22.4增加到25 MBps；偏移為4時，從25.8增加到26.3 MBps。值得注意的是：當(dāng)節(jié)點深度L小于4時，三種偏移情況下的吞吐量增加迅速，而當(dāng)節(jié)點深度大于4后，吞吐量的增加并不明顯。這是因為當(dāng)節(jié)點深度增加時，搜索過程中節(jié)點被遍歷的概率越小，系統(tǒng)的吞吐量增加并不明顯。

實驗2 考慮三種算法在內(nèi)存消耗與吞吐量上的性能。

圖5所示為三種不同算法在最短模式長度變化時的內(nèi)存消耗性能。從圖5中可以看出，F(xiàn)NP消耗的內(nèi)存基本上保持在32 MB，是三種算法中內(nèi)存消耗最大的；而Path AC算法消耗的內(nèi)存保持在29 MB；提出的Hybrid-MPMA的內(nèi)存消耗為13 MB。這也證明了Hybrid-MPMA適合于不同最短模式長度情況下的Web入侵檢測系統(tǒng)，并能以較低的內(nèi)存消耗實現(xiàn)多模式的并發(fā)匹配。

圖6所示為三種算法在最短模式長度變化時的吞吐量性能。從圖6中可以看出，F(xiàn)NP算法的吞吐量基本上保持在4 MB，是三種算法中最低的；Path AC算法消耗的吞吐量保持在11 MB；提出的Hybrid-MPMA的吞吐量隨著最短模式長度的增加而呈增長趨勢，當(dāng)最短模式長度增加到4時，其吞吐量從18.3增加到29.8 MBps。這是因為最短模式長度越大，模式可以用來比較的字符越多，比較樹的節(jié)點就可以選擇較好的位置計算出子節(jié)點的位置，進(jìn)而過濾未匹配模式的效率增加。這證明了提出的Hybrid-MPMA適合于不同最短模式長度情況下的Web入侵檢測系統(tǒng)，并能以高吞吐量實現(xiàn)多模式的并發(fā)匹配，提高模式匹配的搜索效率。

實驗3 對三種算法在不同Web攻擊下的模式匹配正確率進(jìn)行性能比較。模擬器隨機(jī)產(chǎn)生不同數(shù)量的攻擊動作，并將時間設(shè)置為30 s，三種算法在黑客攻擊行為占正常行為不同百分比情況下的正確匹配率如圖7所示。從圖7中可以看出，當(dāng)攻擊動作所占比例增加時，F(xiàn)NP與Path AC算法的性能有所下降，當(dāng)攻擊動作所占比例達(dá)到15％時，這兩種算法的正確匹配率分別為93.1％和93％。當(dāng)攻擊動作所占比例變化時，提出的算法的正確匹配率始終保持在98％以上，是三種算法中正確匹配率最高的。這也充分證明了提出的算法對Web攻擊具有良好的正確匹配性能，同時也在很大程度上克服了誤匹配問題。

4 結(jié)束語

針對Web入侵檢測系統(tǒng)中存在的攻擊模式誤匹配與效率問題，提出了一種有效的多模式匹配算法。該算法基于比較樹，利用（模式，偏移）對來搜索可能的匹配模式，并通過比較樹上的每個節(jié)點存儲的位置信息，記錄下次比較的字符位置以提高搜索效率。為了克服模式匹配量大與模式匹配不完全的問題，MPMA采用虛擬節(jié)點壓縮方式減少計算量與空間開銷、以速度優(yōu)先和以空間大小優(yōu)先的混合節(jié)點構(gòu)建算法實現(xiàn)快速、低內(nèi)存開銷的模式匹配。實驗性能分析表明提出的多模式匹配算法不僅具有較低的內(nèi)存開銷與較高的吞吐量性能，同時具有良好的誤匹配性能。該算法易于在系統(tǒng)中實現(xiàn)，是一種切實可行的Web入侵檢測模式匹配算法。

參考文獻(xiàn)：

［1］GARCIA A，JUAN J，PIKATZA A，et al.Intrusion detection in Web applications using text mining [J].Engineering Applications of Artificial Intelligence，2007，20(4): 555-566.

［2］DJEMAIEL Y，REKHIS S，BOUDRIGA N.Intrusion detection and tolerance:a global scheme[J].International Journal of Communication Systems，2008，21(2):211-230.

［3］BRUSCHI D，PIGHIZZINI G.String distances and intrusion detection:bridging the gap between formal languages and computer security [J].Theoretical Informatics and Applications，2006， 40(2):303-313.

［4］KAI Hong-mei，ZHU Hong-bing，KEI E，et al.A novel intelligent intrusion detection， decision， response system[J].IEICE Trans on Fundamentals of Electronics， Communications and Computer Sciences，2006，E89-A(6):1630-1637.

［5］MARKATOS E P，ANTONATOS S.Exclusion-based signature matching for intrusion detection[C]//Proc of International Conference on Communications and Computer Networks.New Jersey：IEEE Press，2002: 146-152.

［6］DHARMAPURIKAR S， KRISHAMURTHY P. Deep packet inspection using parallel bloom filters[J].IEEE Micro，2004，24(1): 52-61.

［7］ANTONATOS S，ANAGNOSTAKIS K G.Generating realistic workloads for network intrusion detection systems[J].ACM SIGSOFT Software Engineering Notes，2004，29(1):207-215.

［8］TUCK N，CALDER T，VARGHESE B.Deterministic memory-efficient string matching algorithms for intrusion detection[C]//Proc of IEEE INFOCOM.New Jersey：IEEE Press，2004:2628-2639.

［9］LIU Rong-ting，HUANG Nan-fang.A fast string-matching algorithm for network processor-based intrusion detection system[J].ACM Trans on Embedded Computing Systems (TECS)，2004，3(3):614-633.