一種針對大規模URL關鍵字的多模匹配算法

摘要： 針對網絡信息安全中大規模ＵＲＬ關鍵字匹配過程中自動機內存占用過大問題，提出一種基于分類思想的多模匹配算法，將ＵＲＬ關鍵字按照模式長度和匹配要求進行分類，分別使用Ｗｕ－Ｍａｍｂｅｒ算法和自動機類多模匹配增效算法ＧＦＡＭ進行匹配。實驗結果表明，經過分類后，大規模配置（＞１０ｗ）情況下，算法能夠將占用內存降低為只使用ＧＦＡＭ算法的內存的５％以內。

關鍵詞：

中圖分類號： ＴＰ３０１．６ 文獻標識碼：Ａ 文章編號：２０９５－２１６３（２０１１）０１－００２０－０４

０引言

字符串匹配問題是計算機科學中的一個經典研究領域。信息安全領域中，ＵＲＬ關鍵字匹配是入侵檢測系統、防火墻系統、反釣魚防御系統等的最基礎也是最核心的部分。然而隨著ＵＲＬ域名數量的不斷增長，網絡安全威脅不斷升級，尤其是數據規模驚人增長的情況下，大規模ＵＲＬ關鍵字多模匹配算法的性能已經成為系統的瓶頸，同時針對ＵＲＬ關鍵字的匹配不再是簡單的精確匹配，還包含了如“與”表達式匹配、模糊匹配等多種匹配需求。傳統的字符串匹配算法已經不能適用于大規模ＵＲＬ關鍵字的匹配，可以說提高大規模ＵＲＬ關鍵字匹配的效率，降低ＵＲＬ關鍵字匹配部分的系統開銷，提高算法的適應性和健壯性將對消除系統瓶頸起到至關重要的作用。

１研究現狀

從多模匹配算法的特點來說，可以將多模匹配算法分為基于前綴搜索的匹配算法、基于后綴搜索的匹配算法、基于子串搜索的匹配算法、基于位并行的匹配算法以及基于硬件的匹配算法。目前在字符串匹配領域的研究工作主要集中在對經典算法的改進上，由于基于位并行的匹配算法和基于硬件的匹配算法不適用于大規模ＵＲＬ關鍵字匹配，以下主要介紹其他三類中最具代表性的算法。

（１）基于前綴搜索的ＡＣ[１]算法。ＡＣ算法是經典的多模匹配算法，至今大部分的多模匹配算法都是針對ＡＣ算法進行改進。ＡＣ算法對所有關鍵字建立有限自動機，利用該自動機對輸入文本進行掃描。自動機建立過程建立三個函數：狀態跳轉函數ｇｏｔｏ，輸出函數ｏｕｔｐｕｔ，失效函數ｆａｉｌｕｒｅ。

匹配過程是從零狀態出發，每次掃描文本中的一個字符，在當前狀態情況下，查看掃描到的字符，利用ｇｏｔｏ函數、ｆａｉｌｕｒｅ函數跳轉到下一個狀態。如果跳轉到的狀態的ｏｕｔｐｕｔ函數不為空，表示命中了某個關鍵字，輸出該關鍵字。

（２）基于后綴搜索的Ｗｕ－Ｍａｍｂｅｒ算法[２]。Ｗｕ－Ｍａｍｂｅｒ算法基于單模匹配中ＢＭ[３]算法的壞字符跳轉思想，維護一個固定長度的掃描窗口，能夠實現對文本的跳躍式掃描。算法初始化階段首先確定所有規則的最短長度ｍ，并建立三個表，分別是跳轉表Ｓｈｉｆｔ、后綴哈希表Ｈａｓｈ、前綴表Ｐｒｅｆｉｘ。通過Ｓｈｉｆｔ表確定掃描窗口內后綴的跳轉距離；Ｈａｓｈ表存儲的是指針，指針指向具有相同后綴哈希值的所有模式串組成的鏈表，同時指向具有相同后綴哈希值的模式串的前綴鏈表；Ｐｒｅｆｉｘ表存儲了模式串的前綴哈希值，以提高匹配速度。

（３）基于子串搜索的ＳＢＯＭ算法[４]。ＳＢＯＭ算法采用一種稱為Ｆａｃｔｏｒ Ｏｒａｃｌｅ[５]自動機的數據結構，可以識別模式串集合的超集，利用自動機，在長度為ｌｍｉｎ的文本窗口內，從后向前逐個識別字符。

ＡＣ算法具有與關鍵字特征無關，匹配速度穩定的優勢，但內存消耗高，初始化時間長。ＳＢＯＭ算法的匹配速度快，但效率不夠穩定，并且對最短串長度敏感，內存和預處理時間與ＡＣ基本相同。Ｗｕ－Ｍａｍｂｅｒ算法的預處理時間短，內存消耗少，且模式串規模越大，預處理時間和內存優勢越明顯，但匹配速度不穩定，對最短串長度敏感。

ＡＣ算法以其匹配效率穩定，適應性強的優勢成為目前大多數信息安全系統的首選算法，如ＳＮＯＲＴ系統使用的基于ＡＣ的改進算法ＡＣ＿ＢＭ。但隨著ＵＲＬ關鍵字規模的持續高速增長，ＡＣ算法內存消耗過高，自動機啟動時間過長的問題逐漸突顯，已經成為系統瓶頸，必須進行優化。

２基于分類思想的多模匹配算法ＰＭＵＣ

２．１大規模ＵＲＬ關鍵字的特征

針對目前一般的信息安全系統普遍使用的特征庫中ＵＲＬ配置（不少于１０萬條）的統計，ＵＲＬ關鍵字長度分布在４～２５６之間，平均長度為４０個字節左右。長度在４～１０的關鍵字較少，而長度在１１～５０之間的關鍵字占到接近所有關鍵字的８５％左右。另外由于ＵＲＬ配置由數據庫進行維護，數據庫對ＵＲＬ關鍵字長度有一定的限制，因此存在“與”表達式匹配的需求，即將較長的ＵＲＬ關鍵字分割成多個小關鍵字，對每個小關鍵字添加一個“＆”屬性，借此表示該關鍵字具有“與”表達式匹配需求，而只有當所有“與”表達式關鍵字均命中，才能報告整體關鍵字的命中。從對配置文件的統計結果來看，“與”表達式最多被“＆”分割成４段，具有“與”表達式匹配要求的關鍵字較少，只占到總規則條數的１．２５％左右。

２．２ＰＭＵＣ算法的理論基礎

２．２．１Ｗｕ－Ｍａｍｂｅｒ算法的思想

假設模式串集合Ｐ中最短的模式長度為ｍ，Ｗｕ－Ｍａｍｂｅｒ算法在后面僅考慮所有模式的前ｍ個字符組成的模式串。預處理階段將建立三個表格：

（１）移動表（Ｓｈｉｆｔ表）：該表用來決定掃描文本的過程中，可以跳過多少個字符。存在兩種情況。其中，ｘ為ＵＲＬ關鍵字字符串，ｉ為每Ｂ個字符映射成的哈希值。

① Ｘ和任何模式中的子串都不匹配，這種情況下，可以移動文本的ｍ－Ｂ＋１個字符。記錄移動表ＳＨＩＦＴ[ｉ]的值為ｍ－Ｂ＋１。

② Ｘ出現在一些模式中，找出Ｘ在所有模式中的最右出現。假設Ｘ在模式Ｐｊ的位置ｑ處結束，并且Ｘ并不結束在任何其他模式中比ｑ大的位置，記錄ＳＨＩＦＴ[ｉ]的值為ｍ－ｑ。

（２）哈希表（Ｈａｓｈ表）：指向后綴ｈａｓｈ值相同的模式鏈表和前綴表。表項與ｓｈｉｆｔ表有相同的哈希值。

（３）前綴表（Ｐｒｅｆｉｘ表）：存放字符串的前綴哈希值，提高匹配效率。

例如，假設模式集合為?邀ｆｒｏｍ， ｆｒｏｎｔ， ｂｏｏｍｅｄ?妖，最短串的長度是４，設字符塊大小Ｂ為２。為該模式集合建立的Ｓｈｉｆｔ表如表１所示。

Ｗｕ－Ｍａｍｂｅｒ算法的匹配過程：

（１）計算所有模式中最短串的長度；

（２）掃描模式集合，建立三個表；

（３）如果Ｓｈｉｆｔ表對應表項的值不為０，按照ｓｈｉｆｔ值向后移動窗口，繼續執行步驟（３），為零時轉步驟（４）；

（４）查找Ｈａｓｈ表，找出ｓｈｉｆｔ值為零的Ｂ個字符在模式集合中出現的位置以及每個位置上的模式，執行步驟（５）；全部掃描結束，轉步驟（３）繼續掃描剩余文本；

（５）查找該模式的前綴表項，與當前窗口中的文本前綴值比較，相等則逐個比較，如果全部匹配，報告一個成功匹配，否則轉下一個位置，繼續執行步驟（５）。

２．２．２ＧＦＡＭ算法的思想

ＣＦＡＭ 算法[６]是對ＡＣ算法的改進，采用字頻映射技術分類壓縮列，采用位圖檢索技術[７]提高檢索效率。在匹配過程中，根據映射規則轉換輸入字符，高頻字符在保留列中查找跳轉狀態；低頻字符利用位圖信息獲得跳轉狀態。根據輸入字符ｃ 計算轉移狀態的偽碼如下：

ｉｆ Ｆ（ｃ） ＝＝ ０

ｒｅｔｕｒｎ ０；

ｅｌｓｅ ｉｆ Ｆ（ｃ） ＞ ０

ｒｅｔｕｒｎ ｔｈｅ ｄａｔａ ｉｎ ｕｎｃｏｍｐｒｅｓｓｅｄ ａｒｒａｙ （Ｆ（ｃ）， ｃ）；

ｅｌｓｅ

ｉｆ ＣＨＥＣＫ＿ＢＩＴ（ｃ， ｐｂｉｔｍａｐ） ＝＝ ０

ｒｅｔｕｒｎ ０；

ｅｌｓｅ

ｒｅｔｕｒｎ ｔｈｅ ｄａｔａ ｉｎ ｃｏｍｐｒｅｓｓｅｄ ａｒｒａｙ ｗｉｔｈ ｉｎｄｅｘ ｃｏｍｐｕｔｅｄ ｂｙ ｂｉｔｍａｐ；

２．３ＰＭＵＣ算法

２．３．１基本思想

從對大規模（不低于１０萬條配置）ＵＲＬ關鍵字的統計結果來看，長度較長的關鍵字占多數，較為適合Ｗｕ－Ｍａｍｂｅｒ算法，而通過長度過濾后，其余短關鍵字適合自動機類算法。算法專門針對大規模ＵＲＬ關鍵字匹配進行性能優化，命名為ＰＭＵＣ算法（Ｍｕｌｔｉ－ｐａｔｔｅｒｎ Ｍａｔｃｈｉｎｇ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ＵＲＬ ｂａｓｅｄ ｏｎ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ）。

ＰＭＵＣ算法利用Ｗｕ－Ｍａｍｂｅｒ算法來匹配長度較長的ＵＲＬ關鍵字，長度范圍在１０以上的關鍵字占總關鍵字條數的９０％以上，并且命中率較低，實際匹配過程中命中率在１０％以下，這部分關鍵字非常適用于Ｗｕ－Ｍａｍｂｅｒ類算法，產生較大跳躍距離的同時，大大節省了內存空間。

ＰＭＵＣ算法同時采用了基于字頻特征和位圖壓縮ＧＦＡＭ，該算法對ＡＣ算法進行了改進。長度較短的關鍵字以及具有“與”表達式匹配需求的關鍵字使用ＧＦＡＭ算法進行匹配，經過Ｗｕ－Ｍａｍｂｅｒ算法對長關鍵字以及具有“與”表達式需求的關鍵字進行過濾后，利用ＧＦＡＭ算法進行匹配的關鍵字只占很小一部分，且相比于ＡＣ算法來說，ＧＦＡＭ算法能夠進一步壓縮自動機占用的內存。

ＰＭＵＣ算法結合這兩個改進算法，將ＵＲＬ關鍵字按照關鍵字特征進行分類匹配，在保證匹配效率的基礎上，達到了明顯的內存優化效果。實驗表明，ＰＭＵＣ算法占用的內存可壓縮為原只使用ＡＣ算法的５％以下，并且關鍵字規模越大，優化效果越明顯。同時初始化時間有了明顯降低，這對于經常進行配置更新的信息安全系統來說，將明顯提高系統的啟動速度。圖３所示的偽代碼表明了ＰＭＵＣ算法的初始化與匹配過程。其中Ｓ表示分類條件。

２．３．２算法匹配條件

目前，ＵＲＬ關鍵字匹配規模在１０ｗ條以上，且未來規模將越來越大。每條關鍵字的長度一般在４～１ ０２４之間變化，其中長度大于１０的關鍵字占總關鍵字比例的９０％以上。另外在入侵檢測中，存在一種稱為“與”表達式匹配的匹配規則，只有當規則中的所有模式都匹配到的情況才宣告匹配成功。

根據以上ＵＲＬ關鍵字匹配特點，將關鍵字按照如下條件分類。其中，關鍵字的長度用Ｌ表示，臨界長度用ｍ表示，為關鍵字添加屬性ｂｄｓ，關鍵字的ｂｄｓ＝１時，說明該關鍵字是一條“與”表達式規則的關鍵字。

Ｗｕ－Ｍａｍｂｅｒ算法的匹配條件：

ｐａｔｔｅｒｎ．Ｌ＞＝ｍ＆＆ｐａｔｔｅｒｎ．ｂｄｓ＝０；

ＧＦＡＭ算法的匹配條件：

ｐａｔｔｅｒｎ．Ｌ＜ｍ｜｜ｐａｔｔｅｒｎ．ｂｄｓ＝１。

２．３．３參數對算法性能的影響

ｍ：Ｗｕ－Ｍａｍｂｅｒ算法對所有模式的最短串長度敏感，因此使用Ｗｕ－Ｍａｍｂｅｒ算法進行匹配的模式的最短長度不能太短，ｍ表示所有模式的最短串長度。文獻[２]給出了Ｗｕ－Ｍａｍｂｅｒ算法的時間復雜度為Ｏ（ＢＮ/ｍ），在模式較為隨機的情況下，ｍ越大，跳躍距離越大，匹配速度越快。但對于ＰＭＵＣ算法來說，ｍ增大也就意味著模式中使用ＧＦＡＭ算法進行匹配的模式增多，因此將導致內存的增大。

Ｄ：ＧＦＡＭ算法在自動機的前Ｄ層仍然用二維數組來記錄跳轉狀態，且層數越低，出度越大，保證了高頻字符的查找速度。而層數大于Ｄ后，跳轉狀態使用鏈表來實現，由于此時Ｄ層后的字符出現頻率較低，出度較小，因此在盡可能保證查找速度的條件下，壓縮了內存空間。由于所有關鍵字中長度大于ｍ的關鍵字已經使用Ｗｕ－Ｍａｍｂｅｒ進行匹配，因此，Ｄ的設置應當小于ｍ。一般來說，Ｄ越小，越節省內存，但匹配速度有所下降。

３實驗結果與分析

３．１測試環境與數據

實驗的測試環境為８核ＣＰＵ，主頻為２．６Ｈｚ，操作系統采用ＧｒｅａｔＴｕｒｂｏ ＥｎｔｅｒｐｒｉｓｅＳｅｒｖｅｒ１０，內存總量為１６ＧＢ。文本集采用離線網絡數據包，分別包含１００萬條ｈｔｔｐ包、２００萬條、３００萬條、４００萬條。關鍵字采用真實ＵＲＬ中提取的部分連續字符串作為測試集合。

３．２實驗結果與分析

首先測試調整參與“與”匹配時間的關系，分別選取含有１００ｗ、２００ｗ、３００ｗ，４００ｗ包的ｃａｐ包，使用ＧＦＡＭ算法和ＰＭＵＣ進行匹配，記錄精確到ｕｓ的匹配時間。測試匹配時間時，選用１４萬條的配置規模，實驗結果如圖４所示。

圖４中，橫坐標表示ｍ和Ｄ的不同值組合。其中，ｍ初始值設置為１１，Ｄ設置為８，ｍ初始測試值根據對規則長度的統計結果進行設置。可以看出，整體的匹配時間是呈現下降趨勢的，小范圍內有波動。最左側的時間也比較短， 而在 右側的曲線內，ｍ＝８，Ｄ＝６的點以及ｍ＝７，Ｄ＝４的點匹配時間較短。如果考慮內存因素，那么必然是選擇ｍ＝７，Ｄ＝４比較好。

圖５說明了調整參數ｍ和Ｄ對內存的影響。從內存占用情況來看，Ｄ值相同的情況下，ｍ＞＝９時，ｍ每減小１，內存減小１Ｍｂ左右；而當ｍ＜９時，ｍ值的減小對內存占用基本沒有影響。但是在固定ｍ的情況下，Ｄ每減小１，內存相應減小約１０Ｍｂ，因此，在選定ｍ的情況下，如果匹配時間沒有明顯的變短，那么Ｄ可以盡可能減小，以節省內存。

圖６給出了兩者內存對比情況，結果表明與ＧＦＡＭ相比，ＰＭＵＣ的內存占用明顯較低，此時選取的參數是Ｄ＝４，ｍ＝７，則ＰＭＵＣ將獲得更好的內存性能。

圖７表明，模式規模越大，ＰＭＵＣ的內存優化的效果越明顯。

４結束語

本文針對信息安全領域中ＵＲＬ配置量不斷加大，內存消耗巨大，造成系統產生瓶頸的問題，提出使用分類思想的多模匹配算法ＰＭＵＣ，通過調整分類參數使得ＰＭＵＣ算法達到速度與內存的最佳結合點，從而在匹配速度可接受的情況下，大幅降低自動機匹配部分的消耗。實驗表明，ＰＭＵＣ算法占用的內存，可降低為原只使用ＧＦＡＭ算法時的５％以下，這為今后系統的高效穩定運行提供了有力的保證，并為未來應用于不斷增長的數據留下了更大的空間，使得系統的可擴展性提升。同時，針對特定匹配，選擇合適的算法進行分類匹配的思想，也為研究高效的串匹配算法提供了開闊思路。

參考文獻：

[１] ＡＨＯ Ａ Ｖ，ＣＯＲＡＳＩＣＫ Ｍ Ｊ． Ｅｆｆｉｃｉｅｎｔ ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ：ａｎ ａｉｄｔｏ ｂｉｏｌｏｇｉｇｒａｐｈｉｃ ｓｅａｒｃｈ． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ，１９７５，１８ （６）：３３３－３４０．

[２] ＷＵ Ｓ，ＭＡＮＢＥＲ Ｕ． Ａ ｆａｓｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｕｌｔｉ－ｐａｔｔｅｒｎ ｓｅａｒｃｈ－ ｉｎｇ． Ｒｅｐｏｒｔ ＴＲ－９４－１７，Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｕｎｉｖ－ ｅｒｓｉｔｙ ｏｆ Ａｒｉｚｏｎａ，Ｔｕｃｓｏｎ，ＡＺ，１９９４．

[３] ＢＯＹＥＲ Ｒ Ｓ，ＭＯＯＲＥ Ｊ Ｓ． Ａ Ｆａｓｔ Ｓｔｒｉｎｇ Ｓｅａｒｃｈｉｎｇ Ａｌｇｏｒｉｔｈｍ [Ｊ]． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ，１９７７，１０（１０）：７６２－７７２．

[４] ＣＲＯＣＨＥＭＯＲＥ Ｃ Ａ Ｍ，ＲＡＦＦＩＮＯＴ Ｍ． Ｆａｃｔｏｒ Ｏｒａｃｌｅ： Ａ Ｎｅｗ Ｓｔｒｕｃｔｕｒｅ ｆｏｒ Ｐａｔｔｅｒｎ Ｍａｔｃｈｉｎｇ[Ｒ]． Ｉｎｓｔｉｔｕｔｅ Ｇａｓｐａｒｄ－Ｍｏｎｇｅ， Ｕ－ ｎｉｖｅｒｓｉｔｅ ｄｅ Ｍａｒｎｅ－ｌａ－Ｖａｌｌｅｅ，１９９９．

[５] ＡＬＬＡＵＺＥＮ Ｃ，ＲＡＦＦＩＮＯＴ Ｍ． Ｆａｃｔｏｒ Ｏｒａｃｌｅ ｏｆ ａ Ｓｅｔ ｏｆ Ｗｏｒ－ ｄｓ[Ｒ]． Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ ９９－１１，Ｉｎｓｔｉｔｕｔｅ Ｇａｓｐａｒｄ－Ｍｏｎｇｅ，Ｕｎｉｖ－ ｅｒｓｉｔｅ ｄｅ Ｍａｒｎｅ－ｌａ－Ｖａｌｌｅｅ，１９９９．

[６] 李超，張宏莉，楚國鋒． 基于字頻特征的自動機多模匹配增效 算法[Ｊ]． 微計算機信息，２００９，２９（３）：２０６－２０８．

[７] 張元競，張偉哲． 一種基于位圖的多模匹配算法[Ｊ]． 哈爾濱工 業大學學報，２００８，３６（６）：１１０－１１４．