Ｗｅｂ入侵檢測系統高效多模式匹配算法

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

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

關鍵詞：入侵檢測系統；多模式匹配；Web

中圖分類號：TP393.08文獻標志碼：A

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

Efficient multi-pattern matching algorithm for Web intrusion detection systems

FAN Xuan-miao1，ZHENG Ning1，FAN 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 引言

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

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

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

1 多模式匹配算法MPMA

1.1 問題描述

對于檢測的數據包形成的字符串，定義為T，T內每個字符表示為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并不直接進行模式比較，而是先將模式轉換為（模式，偏移）信息對，然后從比較樹的樹根開始進行比較。此時所有的（模式，偏移）對均為候選項，即所有的（模式，偏移）對都可能出現在T上。接著讀取當前所在節點的信息決定要對比的位置，經過比較后，根據結果跳轉到特定的子節點上，重復上述比較步驟直到葉子節點，便可知T中可能包含哪些（模式，偏移）對。最后再針對這些可能符合的（模式，偏移）對進行檢測匹配。

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

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



針對上述第一個問題，MPMA將采用虛擬節點壓縮方式減少計算量和空間開銷。針對第二個問題，MPMA采用兩種不同的節點構建方法來處理：以速度優先的節點算法（Speed-MPMA）；以空間大小優先的節點算法（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）設定為樹根的候選項candidate（pattern，offset）。其中偏移offset的最大值為max_offset。接著把樹根壓棧，并對棧進行檢查，取出棧中節點，用子節點位置構建算法Posparse產生節點位置。將該節點與所有的候選項進行比較，如果該（pattern，offset）在Posparse產生節點的位置上，則將其放入候選數組candidate_array[]中；否則將其存入默認的候選項default_candidate中。然后將candidate_array與default_candidate的候選項與對應的子節點進行關聯。最后將所有非葉子節點壓棧，得到構建的比較樹CT。

子節點位置構建算法Posparse如下：

輸入：節點node

輸出：節點位置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

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

Speed-MPMA-search搜索算法實現字符串的模式匹配功能。Speed-MPMA-search根據Speed-MPMA算法建立的比較樹CT，從字符串T的起始位置開始，對每個節點，根據T[pos+node.offset]的字符決定選擇該節點的對應子節點，直到找到葉子節點為止。當到達葉子節點時，將當前的T與該葉子節點的候選模式進行比較，直到找出所有的匹配模式為止。

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

輸入：數據包字符串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的最大區別在于候選項的產生方式。在Speed-MPMA中，如果子節點位置構建算法Posparse所選定的位置上有任何候選項沒有字符存在時，就會指定到默認子節點上。這將導致所有的子節點被復制，這種方法將產生巨大的空間消耗。Size-MPMA則針對該缺陷，將原來分布在每個子節點上的候選項集中到一個特殊的默認子節點上，并把一個節點的候選項candidate（pattern，offset）根據子節點位置構建算法產生的位置分為兩部分：一部分是該位置有字符的candidate（pattern，offset）；另一部分是該位置無字符的candidate（pattern，offset）。有字符的候選項作為一般子節點處理，無字符的部分作為默認子節點處理。這種方式可以大量降低比較樹占用的空間消耗。

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

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

輸入：數據包字符串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的構建上，如前所述，其差異僅僅在子節點候選項的設定上。當子節點位置構建算法Posparse所選定的位置上有任何候選項無字符時，兩種算法的處理方式不同：Speed-MPMA會把這些候選項復制到所有的子節點內，而Size-MPMA則把這些候選項集中放入默認子節點中。在搜索算法中，Speed-MPMA經過一個節點時，只需要其位置pos與T相比，即可知道下一個要處理的節點；而Size-MPMA除了要處理系統的子節點外，還需要處理默認子節點。因此混合算法Hybrid-MPMA充分利用兩個算法的優點，對常用的節點使用Speed-MPMA，而對少用的節點使用Size-MPMA。由于處理比較樹CT的順序是從根節點開始，假設T內的字符服從統一分布，則每個子節點被處理的概率為父節點的1/256，當節點越深，其被處理的概率越小。因此，在Hybrid-MPMA中，只需要設定一個合適的深度L作為閾值，當深度小于等于L時，采用Speed-MPMA構建節點；否則采用Size-MPMA構建節點。

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

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

3 實驗分析

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

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

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

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

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

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

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

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

4 結束語

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

參考文獻：

［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.