一種新的應用于數(shù)據(jù)流關聯(lián)分析的多模式匹配算法

王瑞瑩，邱 亮

(1.哈爾濱友盛科技有限公司，黑龍江哈爾濱150090;2.聯(lián)通系統(tǒng)集成有限公司 黑龍江省分公司，黑龍江 哈爾濱150090;3.東北電力大學信息工程學院，吉林吉林132012)

隨著電力企業(yè)信息化工作的不斷深入，國家電網(wǎng)公司“SGl86”工程的實施，電力企業(yè)的信息化程度得到了空前的提升，為了確保電網(wǎng)業(yè)務數(shù)據(jù)的安全以及信息系統(tǒng)安全穩(wěn)定的運行，電力企業(yè)先后在網(wǎng)絡邊界和信息內(nèi)網(wǎng)部署了防病毒系統(tǒng)、防火墻、入侵檢測系統(tǒng)、漏洞掃描系統(tǒng)等安全設備。但是這些安全系統(tǒng)都只能阻止單一的安全威脅，彼此之間缺乏有效而統(tǒng)一的管理調(diào)度機制，導致各個安全設備的效能難以得到充分地發(fā)揮［1］。此外，這些設備產(chǎn)生的海量日志事件中，可能隱含了新的更嚴重的安全事件，因此必須采用有效的分析手段對這些海量日志信息進行處理，以減少誤報、避免重復報警、發(fā)現(xiàn)新的安全事件?；跀?shù)據(jù)流技術的安全事件關聯(lián)分析引擎則可以達到這個目的。

本文主要對基于數(shù)據(jù)流技術的安全事件關聯(lián)分析引擎中的模式匹配算法進行研究。

1 基于數(shù)據(jù)流技術的關聯(lián)分析引擎

基于數(shù)據(jù)流技術的關聯(lián)分析引擎將經(jīng)過歸一化處理后的海量日志信息形成的數(shù)據(jù)流在內(nèi)存中采用基于滑動窗口模型的關聯(lián)分析算法進行關聯(lián)規(guī)則挖掘，然后利用多模式匹配算法將得到的關聯(lián)規(guī)則與規(guī)則庫中規(guī)則進行匹配，以便實時地發(fā)現(xiàn)異常行為，為后續(xù)告警響應及安全風險分析等提供依據(jù)。

為滿足數(shù)據(jù)流關聯(lián)分析實時、高速的要求，關聯(lián)分析引擎不僅要有高效的數(shù)據(jù)流關聯(lián)分析算法，還要有高效、快速的模式匹配算法。Aho-Corasick算法(AC算法)和Wu-Manber(WM算法)算法是兩種經(jīng)典的高效多模式匹配算法。

圖1 基于數(shù)據(jù)流技術的關聯(lián)分析引擎結構

2 多模式匹配算法

2.1 AC 算法

AC算法是基于有限自動機的多模式匹配算法，在進行匹配之前先對模式串集合進行預處理，形成樹型有限狀態(tài)自動機，然后只需對文本串掃描一次就可以找出與其匹配的所有模式串。

AC算法在預處理階段生成三個函數(shù):轉(zhuǎn)移函數(shù)g，失效函數(shù)f和輸出函數(shù)output。轉(zhuǎn)移函數(shù)g(s，a)指出在當前狀態(tài)為s、輸入字符a時自動機進入的下一狀態(tài);如輸入字符不為a，則產(chǎn)生一個失效消息fail。失效函數(shù)f(s)表明當轉(zhuǎn)移函數(shù)g(s，a)=fail時自動機應該進入的下一狀態(tài)。輸出函數(shù)output(s)記錄了自動機進入每個狀態(tài)時發(fā)生匹配的模式子集(可能為空)，用于在匹配過程中輸出發(fā)生匹配的模式。

匹配過程從初始狀態(tài)開始，依次讀取文本T的一個字符，根據(jù)當前狀態(tài)和當前輸入字符，利用轉(zhuǎn)移函數(shù)g和失效函數(shù)f進入下一狀態(tài)。當某個狀態(tài)的輸出函數(shù)output不為空時輸出其值，表示在文本T中找到該模式串，匹配成功［2］。

AC算法由于在對文本串進行匹配時完全按照順序輸入字符，無法跳過不必要的比較，因此在模式串數(shù)目不是很多的情況下性能并不是很好。

2.2WM 算法

Wu-Manber算法采用BM算法進行跳躍的思想和hash散列的方法。算法包括預處理和查找兩個階段。

在預處理階段，將針對模式集合建立3個表shift表、hash表和prefix表。其中，shift表存儲的是初次匹配字符串X時模式移動的距離。當shift表中對應的值為0時，初次匹配成功，再使用hash表和prefix表來驗證這些模式是否真的匹配［3］。

首先需要計算模式集合中最短模式的長度，記為m，在初次匹配時只考慮每個模式的前m個字符。將文本串以B個字符長度分塊，每次嘗試匹配時，都比較一個“塊”，即比較B個字符，根據(jù)這B個字符的匹配情況來決定模式的移動距離。比如，當文本中由B個字符組成的字符串X不在任何一個模式中出現(xiàn)時，模式集合可以安全地向后移動m-b+1個字符的距離。Wu-Manber算法用B個字符組成的字符塊X來代替單個字符，降低了字符塊在模式串中出現(xiàn)的概率，使匹配入口點減少，從而字符比較的次數(shù)減少，是一種效率比較高的多模式匹配算法。但是該算法未能充分利用匹配過程中不匹配時的有用信息［4］，跳過一些不匹配字符，因而還有改進之處。

3AC-WMN算法

根據(jù)以上分析，借鑒袁世忠等人提出的WMN算法思想，提出一種新的多模式匹配算法——AC-WMN算法，該算法利用改進的Wu-Manber算法的啟發(fā)式搜索策略產(chǎn)生字符跳躍，增加盡可能多的位移，獲得最大步長，同時應用AC算法的有限狀態(tài)自動機構造模式樹，匹配過程中移動模式樹，減少規(guī)則匹配次數(shù)［5］。AC-WMN算法仍包括預處理和匹配兩個階段。

3.1AC-WMN算法的預處理

3.1.1 構造位移表

在預處理階段，同樣生成前綴索引Prefix表、后綴索引Hash表及跳躍距離Shift表。Prefix表和Hash表的計算方法與原WM算法相同。

將文本串以B個字符長度分塊，通過一個散列函數(shù)將字符塊映射為一個整數(shù)，并將該整數(shù)作為Hash表和Shift表的索引值。設模式串的最小長度為m，構造位移表時將所有模式串以最后一個字符對齊，在預處理階段只考慮每個模式串的最后m個字符。

對于所有可能的字符塊B，按照下列規(guī)則生成 Shift跳躍表［6］:

(1)如果字符塊B不出現(xiàn)在任何模式串中，則Shift［h］=m-B+1，其中h為字符塊B的散列值。

(2)如果字符塊B出現(xiàn)在某些模式串中，且在所有模式串中最右的非最后一個字符塊的結束位置為q，則Shift［h］=m-q，若字符塊B僅在某些模式串的最后一個字符塊的位置處，則Shift［h］=m-B+1。

3.1.2 構造有限狀態(tài)自動機

有限狀態(tài)自動機的構造借鑒王永成提出的反向跳躍自動機思想［7］，把模式串集合轉(zhuǎn)換成反向有限自動機，從模式串集的右端向左逆向匹配。

轉(zhuǎn)移函數(shù)g和輸出函數(shù)output按照如下方法生成:初始狀態(tài)為0;然后依次取出模式集中的每一個模式串執(zhí)行如下操作:

從模式串的最后一個字符開始從后向前，逐個取出模式串的每個字符，從狀態(tài)0出發(fā)，由當前狀態(tài)和新取出的字符決定下一狀態(tài)。如果下一狀態(tài)不為空，則將下一狀態(tài)賦為當前狀態(tài);否則，添加一個標號比已有狀態(tài)標號大1的新狀態(tài)，并用一條矢線從當前狀態(tài)指向新加入的狀態(tài)，并將新加入的狀態(tài)賦為當前狀態(tài)。每處理完一個模式串，將該模式串加入到當前狀態(tài)的output函數(shù)中［8］。

對于模式集{they，she，his，hers}，圖 2 顯示了有限狀態(tài)自動機的轉(zhuǎn)移函數(shù)g。表2顯示了output函數(shù)。

表 2 (they，she，his，hers)output的函數(shù)

圖 2 (they，she，his，hers)goto 的函數(shù)

3.2 AC-WMN算法的匹配過程

AC-WMN算法的匹配過程如下:

步驟1使用當前窗口的最后B個字符計算散列值h1，使用當前窗口的最后B-1個字符和當前窗口的下一個字符(從右向左)計算散列值h2。

步驟2如果 Hash［h1］表項為空，若 Shift［h1］-1≥Shift［h2］，則窗口向左跳躍Shift［h1］并轉(zhuǎn)步驟1，否則，窗口向左跳躍Shift［h2］并轉(zhuǎn)步驟1;否則，轉(zhuǎn)步驟3。

步驟3計算當前匹配窗口后綴的散列值rear_hash。

步驟4對于Hash［h1］指向的列表中的每個指針，檢查Hash［h1］指向的模式串最右的B個字符的哈希值是否等于rear_hash，如果相等，則轉(zhuǎn)至步驟5，否則轉(zhuǎn)至步驟6。

步驟5利用有限狀態(tài)自動機進行字符串比較。從T的當前字符開始，從后向前逐個取出T的每個字符，從狀態(tài)0出發(fā)，根據(jù)轉(zhuǎn)移函數(shù)g進入下一狀態(tài);當某個狀態(tài)的output函數(shù)不為空時輸出其值，表示在文本串中找到該模式串。

步驟6如果Shift［h1］- 1≥Shift［h2］，則窗口向左跳躍Shift［h1］并轉(zhuǎn)步驟1，如果Shift［h1］-1＜Shift［h2］，則窗口向左跳躍Shift［h2］，然后轉(zhuǎn)步驟1，直至掃描完全部文本。

下面是AC-WMN算法匹配過程的程序偽代碼:

4 實驗及結果分析

實驗選取1 301 560B的英文文本，測試在不同模式串長度下，算法的性能，因此每組內(nèi)模式串的長度是一致的。在實驗中，每組分別取1到7個模式串，形成模式串集合進行查找，這些比較是為了測試在相同模式串長度但不同模式串數(shù)目下算法的性能。實驗在CPU2.0GHz，2G內(nèi)存，Windows XP下進行，算法用C++實現(xiàn)。實驗結果如表3所示。

表3 不同算法的模式串查找時間

5 結束語

對電力企業(yè)信息內(nèi)網(wǎng)安全事件進行關聯(lián)分析能有效地管理各種異構安全設備及其產(chǎn)生的海量安全事件。模式匹配是實現(xiàn)安全事件關聯(lián)分析的關鍵技術之一。因此提高模式匹配的效率是提高關聯(lián)分析系統(tǒng)檢測能力的關鍵。本文提出AC-WMN算法將改進的Wu-Manber算法的啟發(fā)式搜索技術和AC算法的有限狀態(tài)自動機相結合進行同時匹配。實驗結果表明，AC-WMN算法能夠顯著提高模式匹配的效率。

［1］吳慶，胥光輝，張晶晶.安全事件關聯(lián)分析系統(tǒng)的研究與設計［J］.軍事通信技術，2007，28(01):26-29.

［2］高朝勤，陳元琰，黎蕓.入侵檢測中一種節(jié)約內(nèi)存的多模式匹配算法［J］.計算機工程與應用，2009，45(11):107-110.

［3］王艷秋，蘭巨龍.基于Wu-Manber的快速跳躍多模式匹配算法［J］.四川大學學報(工程科學版)，2007，39(1):58-61.

［4］楊東紅，徐恪，崔勇.改進的Wu-Manber多模式匹配算法［J］.清華大學學報(自然科學版)，2006，46(04):555-558.

［5］宋明秋，張國權，鄧貴仕.IDS中新的快速多模式匹配算法及其設計［J］.計算機工程與應用，2005，21(10):158-162.

［6］袁世忠，曹旻，王燕燕.基于WM算法的多模式匹配改進算法WMN［J］.計算機工程與應用，2007，43(15):128-130.