張萍，何慧敏，張春燕，曹聰，劉燕兵，譚建龍

(1.中國科學(xué)院信息工程研究所，北京 100093；2.中國科學(xué)院大學(xué)，北京 100049；3.信息內(nèi)容安全技術(shù)國家工程實(shí)驗(yàn)室，北京 100093；4.中國移動（深圳）有限公司，深圳 518031)

FilterFA：一種基于字符集規(guī)約的模式串匹配算法

張萍1,2,3，何慧敏4，張春燕1,3，曹聰1,3，劉燕兵1,3，譚建龍1,3

(1.中國科學(xué)院信息工程研究所，北京 100093；2.中國科學(xué)院大學(xué)，北京 100049；3.信息內(nèi)容安全技術(shù)國家工程實(shí)驗(yàn)室，北京 100093；4.中國移動（深圳）有限公司，深圳 518031)

多模式串匹配技術(shù)是入侵檢測系統(tǒng)的核心技術(shù)之一，Aho-Corasick算法廣泛應(yīng)用于其中。針對AC自動機(jī)內(nèi)存開銷巨大影響算法性能的問題，提出一種基于字符集規(guī)約的改進(jìn)算法——FilterFA。利用字符集映射函數(shù)將原字符集壓縮為多個像字符集，針對像字符集構(gòu)造新的自動機(jī)FilterFA，將空間復(fù)雜度降至。在隨機(jī)數(shù)據(jù)集和真實(shí)數(shù)據(jù)集ClamAV上的測試結(jié)果表明，當(dāng)像字符集大小為8，且保證誤識別率小于2%時，F(xiàn)ilterFA算法消耗的存儲空間僅為AC算法的3%左右。

入侵檢測；多模式串匹配；字符集規(guī)約；字符集映射

1 引言

字符串匹配問題是網(wǎng)絡(luò)入侵檢測系統(tǒng)的核心技術(shù)之一，在近幾十年的發(fā)展中研究非常廣泛。它廣泛應(yīng)用于信息安全、文本檢索和計算生物學(xué)等領(lǐng)域。著名的入侵檢測系統(tǒng) Snort[1]包含多種規(guī)則匹配算法，如Boyer-Moore(BM)[2]、Wu-Manber(WM)[3]和Aho-Corasick (簡稱AC)[4]算法。其中，BM算法適合單模式串匹配問題，AC算法和WM算法適用于多模式串匹配。

自20世紀(jì)70年代以來，字符串匹配技術(shù)有著顯著的發(fā)展，國內(nèi)外多位研究者相繼提出了上百種模式串匹配算法。根據(jù)其搜索方式的差異性，Gonalo Navarro和Mathieu Raffinot[5]將字符串匹配算法分為3類：基于前綴的模式串匹配算法、基于后綴的模式串匹配算法和基于子串搜索的模式串匹配算法。其中，基于前綴的模式串匹配算法在搜索窗口內(nèi)搜索既是窗口中文本的后綴，同時也是模式串子串的字符串，這類算法可以達(dá)到亞線性的平均時間復(fù)雜度?；舅枷胧牵涸谒阉鞔翱趦?nèi)從左向右逐個讀入文本字符，搜索窗口中文本和模式串的最長公共前綴，其代表算法包括Multiple Shift-AND[6]和AC。Multiple Shift-AND算法利用位并行來模擬前綴識別的過程，但其應(yīng)用范圍受制于機(jī)器字長；AC算法使用AC自動機(jī)識別模式串的前綴。理論分析表明，AC算法具有線性的搜索時間復(fù)雜度，AC自動機(jī)的性能穩(wěn)定，因而在實(shí)際中應(yīng)用十分廣泛。

然而在AC算法中，AC自動機(jī)的每個狀態(tài)節(jié)點(diǎn)都需要|Σ|個指針來存儲其狀態(tài)轉(zhuǎn)移表，空間復(fù)雜度為(各符號定義見下文)。在處理大規(guī)模的串匹配問題時，AC算法存儲空間帶來的瓶頸，使其匹配速度大幅度降低。

因此，如何降低AC自動機(jī)的存儲空間開銷，成為擴(kuò)大其應(yīng)用范圍的關(guān)鍵因素之一。本文提出一種基于字符集規(guī)約的AC改進(jìn)算法——FilterFA算法，通過字符集映射函數(shù)將大小為|Σ|的字符集映射到大小為|Σ′|的字符集上，使空間復(fù)雜度降低至原來的，大大降低了AC算法的存儲空間開銷。與此同時，該算法采用隨機(jī)取模和字符概率均勻分布2種字符集映射策略，利用啟發(fā)式的思想對字符概率進(jìn)行了統(tǒng)計，構(gòu)造出字符集映射函數(shù)，并在隨后的隨機(jī)數(shù)據(jù)和真實(shí)數(shù)據(jù)上進(jìn)行測試，該算法在存儲空間和匹配速度方面均取得了不錯的效果。

為統(tǒng)一下文所用的相關(guān)符號，現(xiàn)定義如下：給定一組特定的字符串集合P={p(1),p(2),…,p(r)}，對于任意的一個字符串T=t1t2…tn，找出P中所有字符串在T中的所有出現(xiàn)位置。P為模式串集合，P中的元素p(i)為模式串（或關(guān)鍵詞），T為文本。其中，是定義在有限字母表∑上的字符串，r表示模式串的個數(shù)，表示所有模式串的長度之和，n=|T|表示待匹配文本的長度，Σ表示字母表（或字符集），σ=|Σ|表示字母表的大小。假設(shè)Σ上的字符之間相互獨(dú)立，服從概率分布X～ (xi,pi)，xi∈Σ。以下分析均基于字符間相互獨(dú)立的假設(shè)。

2 相關(guān)工作

多模式串匹配算法中與壓縮算法相關(guān)的國內(nèi)外的代表性工作介紹如下。

Aho和Corasick提出了基于前綴搜索的多模式串匹配算法——AC算法，從模式串集合構(gòu)建AC自動機(jī)，通過對自動機(jī)的訪問進(jìn)行匹配。該算法匹配的時間復(fù)雜度正比于待掃描文本長度，不受關(guān)鍵詞長度和文本統(tǒng)計特征的影響，性能比較穩(wěn)定。但因其存儲空間巨大帶來的瓶頸，使算法匹配速度大幅度降低。為了解決自動機(jī)的存儲空間引發(fā)的性能瓶頸，國內(nèi)外研究者提出了多種壓縮方案，目前比較常用的壓縮方案有行壓縮方法[7]、Banded-Row方法[8]、位圖表示法[9]、雙數(shù)組方法[10～12]和散列方法[13]等。

在行壓縮方法狀態(tài)轉(zhuǎn)移表中，每個狀態(tài)下的一行中只存儲非空的狀態(tài)轉(zhuǎn)移邊對應(yīng)的讀入字符及下一跳狀態(tài)。當(dāng)自動機(jī)的狀態(tài)轉(zhuǎn)移表非常稀疏時，該方法具有很好的壓縮效果，但是狀態(tài)自動機(jī)比較稠密時，該方法的壓縮效果變差，甚至?xí)^壓縮前的存儲空間。

Banded-Row方法應(yīng)用于Snort中，用來優(yōu)化AC算法，其核心思想是：對存儲矩陣的每一行，只存儲從第一個非空元素到最后一個非空元素之間的元素。若用數(shù)組BV[]表示，則BV[0]中存儲第一個非空元素的位置，BV[1]中存儲“帶寬(bandwidth)”(即第一個非空元素和最后一個非空元素之間的元素的個數(shù))，BV[2,3,…,1+bandwidth]存儲第一個非空元素到最后一個非空元素之間的所有元素。該算法同樣也不適用于狀態(tài)自動機(jī)比較稠密的情況。

位圖表示法中，狀態(tài)轉(zhuǎn)移表中每一行用一個與字符集大小相等的比特向量表示該行任意字符對應(yīng)的下一跳狀態(tài)是否為空，轉(zhuǎn)移表中每一行只按照前述比特向量的順序存儲非空的轉(zhuǎn)移邊。該方法具有極好的壓縮效果，但是搜索過程中狀態(tài)轉(zhuǎn)移邊的查找需要硬件支持，不適合軟件實(shí)現(xiàn)，不利于推廣實(shí)現(xiàn)。

雙數(shù)組方法使用一個一維數(shù)組重疊排列狀態(tài)轉(zhuǎn)移表中所有的行，但必須保證各行的非空元素不得相互沖突，另外用2個數(shù)組分別存儲每一行的偏移位置和一維數(shù)組中每個元素所屬的行。該方法具有較好的壓縮效果，并且可以達(dá)到O(1)的狀態(tài)轉(zhuǎn)移速度，但處理過程中峰值內(nèi)存太大，導(dǎo)致其不能處理大規(guī)模的串匹配問題。

散列方法的核心思想是用盡可能小的存儲空間S來組織存儲矩陣T，使在盡可能短的時間內(nèi)(用探測S的次數(shù)來度量)來查找元素q在S中位置。Fredman等[14]給出了基于完美散列的解決辦法，算法具有O( n)的空間復(fù)雜度,O(1)的最壞時間復(fù)雜度。實(shí)際應(yīng)用中，計算完美散列函數(shù)的代價很大，會極大地影響算法的性能，故不具有實(shí)用性。

楊毅夫[15]等將上述幾種壓縮方法實(shí)現(xiàn)的AC算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果表明，在存儲空間方面，在多數(shù)情況下，行壓縮方法占用的存儲空間最小，空間壓縮率達(dá)到95%以上，其次是雙數(shù)組方法、Banded-Row方法和散列方法；匹配時間方面，雙數(shù)組方法具有最優(yōu)的匹配時間，Banded-Row 方法次之，行壓縮方法較慢，位圖方法和散列方法最慢。文獻(xiàn)[15]還指出，幾種方法的存儲空間與稀疏性有關(guān)，位圖方法、行壓縮方法和散列方法的存儲空間隨稀疏率的增大而線性增加。在稀疏率小于5%時，Banded-Row隨稀疏率的增加逐漸接近原AC算法的存儲空間。而行偏移方法隨稀疏率的變化很大。

除上述常見的壓縮方案，近年來，對串匹配算法的壓縮算法也不斷更新。Nieves[16,17]提出了一種k2-tree的方法，用來解決網(wǎng)絡(luò)圖結(jié)構(gòu)中關(guān)聯(lián)矩陣的壓縮問題。它的主要思想是利用rank-select操作將矩陣按照樹的結(jié)構(gòu)存儲從而減少不必要的0的個數(shù)。由于采用了位操作，該算法的壓縮效果極好。但查詢速度與壓縮之前相比，有所降低。

HashTrie算法[18]利用rank操作與散列函數(shù)結(jié)合的方法，預(yù)處理階段將字符串及其前綴經(jīng)散列函數(shù)轉(zhuǎn)化為某個值，存儲在B表和F表中，同時M表存儲與F表相對應(yīng)的字符串鏈表；匹配階段，能快速定位文本串的散列函數(shù)值，若散列表中存在此散列值，則去M表進(jìn)行校驗(yàn)，從而判斷是否真正匹配。HashTrie算法的空間復(fù)雜度僅為O(| P|)，優(yōu)于經(jīng)典多模式串匹配算法AC的空間復(fù)雜度。但HashTrie算法更適合于模式串集合規(guī)模較大、模式串長度較短的多模式串實(shí)時匹配問題。

綜上所述，針對存儲空間進(jìn)行壓縮的多種算法在處理串匹配問題時各有優(yōu)缺點(diǎn)，而且同一種方法在不同數(shù)據(jù)集上差別也很大。除HashTrie算法采用位向量的形式存儲模式串信息之外，傳統(tǒng)算法多采用二維狀態(tài)轉(zhuǎn)移矩陣存儲模式串信息，內(nèi)存消耗巨大。已有的壓縮方法沒有考慮到針對字符集壓縮的方法，而AC自動機(jī)適用于小字符集的應(yīng)用場景。因此，本文將從字符集方面入手，設(shè)計更加高效的多模式串匹配壓縮算法，這具有重要的理論和實(shí)際意義。

3 FilterFA：基于字符集歸約的模式串匹配算法

AC算法是串匹配的經(jīng)典算法，是目前應(yīng)用最廣泛的算法之一。AC自動機(jī)的空間復(fù)雜度為，與字符集大小成正比。當(dāng)字符集較大時，存儲空間會迅速增長，成為影響算法性能的一個重要因素，是處理大規(guī)模串匹配問題的一個瓶頸。Gonalo Navarro和Mathieu Raffinot[5]在隨機(jī)數(shù)據(jù)集上，對多種串匹配算法進(jìn)行比較。實(shí)驗(yàn)表明，基于前綴搜索的AC算法、基于后綴搜索的WM算法和基于子串搜索的SBOM算法是最為有效的算法。由圖1可以看出，相對于大字符集應(yīng)用場景，AC自動機(jī)更適用于小字符集的應(yīng)用場景。

圖1 搜索1 000個模式串最有效的算法圖譜

針對AC算法適用于小字符集這一特點(diǎn)，F(xiàn)ilterFA算法從字符集出發(fā)，利用啟發(fā)式的字符集變換策略，將大字符集轉(zhuǎn)化成小字符集，并利用轉(zhuǎn)化后的小字符集構(gòu)造自動機(jī)FilterFA，最終降低算法的存儲空間開銷。FilterFA算法的自動機(jī)壓縮基本原理如圖2所示。

圖2 FilterFA算法的自動機(jī)壓縮基本原理

定義1設(shè)Σ為原字符集（大小為σ），Σ′為新定義的字符集（大小為σ′），且|Σ′|＜|Σ|，將由模式串集合在像字符集Σ′上構(gòu)建的確定自動機(jī)稱為FilterFA。設(shè)f∶Σ→Σ′是字符集Σ到Σ′的映射。記映射前字母的概率分布為si(0≤i＜|Σ|)，映射后字母仍然服從某一概率分布為qi(0≤i＜|Σ′|)，則稱f為從字符集Σ到字符集Σ′的映射函數(shù)。

FilterFA算法主要包含3個階段：數(shù)據(jù)訓(xùn)練階段、預(yù)處理階段和掃描階段。

在數(shù)據(jù)訓(xùn)練階段，依據(jù)訓(xùn)練文本數(shù)據(jù)，統(tǒng)計每個字符出現(xiàn)的概率信息。按照字符概率均勻分布的原則，求解使誤識別率最小的字符集映射函數(shù)。利用該映射函數(shù)，將大字符集壓縮為多個像字符集。在訓(xùn)練數(shù)據(jù)集上求解字符集映射函數(shù)時，基于字符獨(dú)立假設(shè)，像字符集服從依概率均勻分布，把FilterFA算法誤識別率降到最低，從而將因誤匹配而產(chǎn)生的多余校驗(yàn)對算法匹配速度的影響降至最低。

在預(yù)處理階段，主要任務(wù)是FilterFA自動機(jī)的構(gòu)造。根據(jù)模式串集合在小字符集范圍上，構(gòu)建Trie樹，再由Trie樹構(gòu)建FilterFA自動機(jī)。

在掃描階段，利用預(yù)處理階段得到的FilterFA自動機(jī)對文本進(jìn)行掃描，最終輸出所有正確匹配的結(jié)果。

FilterFA算法的基本處理流程如圖3所示。

3.1 誤識別率和像字符集Σ′大小的選擇

在利用字符集映射函數(shù)將一個大的字符集映射到一個較小的字符集上時，有很多種方法，如隨機(jī)取模。隨機(jī)取模的方法簡單易操作，卻存在著多對一映射沖突的問題。即不同的字符經(jīng)過字符集函數(shù)映射之后，變成相同的字符。例如，若字符i和字符o通過f映射之后，變?yōu)橄嗤淖址?，在掃描階段，就會出現(xiàn)將“string”和“strong”誤識別的情況。因此，在利用字符集映射函數(shù)在小字符集范圍內(nèi)構(gòu)造FilterFA，進(jìn)行匹配的過程中，會出現(xiàn)誤匹配的情況。

定義2設(shè)f∶Σ→Σ′是字符集Σ到Σ′的映射函數(shù)，p(i)是定義在有限字母表（字符集）Σ上長度為mi的模式串。T=t0t1…tn?1是長度n的文本串。稱通過此字符集映射函數(shù)f變換得到的FilterFA自動機(jī)掃描文本T后引起的對該模式串錯誤識別的概率（即誤匹配的次數(shù)與報告的總匹配次數(shù)之比）為模式串p(i)的誤識別率。

圖3 FilterFA算法的基本處理流程

設(shè)p=p0p1…pm?1是長度為m的模式串，t=t0t1…tm?1是長度m的文本串，假設(shè)字符間相互獨(dú)立，則p與t的誤匹配的概率Prfalse為

其中，C為常數(shù)，和已知的訓(xùn)練數(shù)據(jù)集有關(guān)。

根據(jù)上述公式推導(dǎo)過程，當(dāng)q1=q2=…=qm，即通過字符集映射之后得到的像字符集滿足依概率均勻分布時，因字符集映射而引起的誤識別率最小，為。因此，在具體實(shí)現(xiàn)時，采用字符集映射函數(shù)減少計算代價、提高算法效率，同時，按照依概率均勻分布原則選取字符集映射函數(shù)，從而將FilterFA自動機(jī)誤識別率降至最低。

字符集Σ在通過字符集函數(shù)f映射之后，得到一個較小的字符集Σ′。存儲空間與字符集的大小成正比，字符集越小，存儲空間越小。FilterFA自動機(jī)的存儲空間也因此降低，字符集變化前后二者的存儲空間比為。字符集映射函數(shù)f不同，映射得到的像字符集Σ′大小不同，對模式串匹配速度的影響也不同。

在式(1)的推導(dǎo)過程中，可以看出，隨著字符集的減小，存儲空間開銷減小，誤識別率反而增大。對于同一個文本來說，F(xiàn)ilterFA自動機(jī)誤識別率越大，需要校驗(yàn)的次數(shù)越多，從而使匹配系統(tǒng)的性能降低。

在算法設(shè)計時，選取不同的字符集映射函數(shù)在大小不同的像字符集上測試，考察誤識別率對匹配速度的影響。由表1可以看出，字符集映射函數(shù)的選取對算法的性能影響差異顯著；在像字符集大小固定時，誤識別率越大，匹配速度越小。因此，字符集映射函數(shù)的選取對算法性能的影響至關(guān)重要。一方面要盡可能降低存儲空間開銷，另一方面要控制誤識別率以減少校驗(yàn)工作量。綜合以上2方面，在FilterFA算法中，選取合適的使算法誤識別率較小的字符集映射函數(shù)對算法性能影響巨大。

表1 誤識別率對匹配速度的影響

3.2 字符集映射函數(shù)求解

依據(jù)訓(xùn)練數(shù)據(jù)集統(tǒng)計得到原字符集中字符的概率分布，求解字符集映射函數(shù)，問題抽象如下。

已知字符集Σ，Σ上的字符服從概率分布X～ (xi,pi)，xi∈Σ，p(i)是定義在有限字母表（字符集）Σ上長度為mi的模式串。T=t0t1…tn-1是長度n的文本串。求字符集映射函數(shù)f，使通過該字符集映射函數(shù)f變換得到像字符集Σ′，滿足在Σ′上構(gòu)造的FilterFA自動機(jī)掃描文本T后引起的識別率Prfalse最小。

由上節(jié)分析可知，當(dāng)像字符集服從等概率均勻分布時，由字符集映射函數(shù)壓縮字符集而引起的誤識別率最小。因此，原問題進(jìn)一步抽象為按照字符依概率均勻分布的原則求字符集映射函數(shù)問題，如下。

已知字符集Σ，Σ上的字符服從概率分布X～ (xi,pi)，xi∈Σ。求字符集映射函數(shù)f，使經(jīng)f映射之后得到的像字符集Σ′，Σ′上的字符服從等概率均勻分布。

進(jìn)一步，可將上述問題轉(zhuǎn)化為如下組問題。

如何把原字符集Σ分為σ′組，使分組后的字符子集服從等概率分布，即。

上述字符集分組問題是一個NP問題，利用啟發(fā)式方法近似求得最優(yōu)解：統(tǒng)計原字符集中所有字符出現(xiàn)的概率，并將字符集的所有字符按其概率大小進(jìn)行排序；將出現(xiàn)概率大于等于的字符單獨(dú)分為一組，把其余字符依次添加到當(dāng)前概率最小的分組；通過交換任意2個元素的分組，使分組后的概率盡可能均勻。

近似最優(yōu)映射函數(shù)求解算法具體實(shí)施過程見算法1。

算法1近似最優(yōu)映射函數(shù)求解算法

3.3 FilterFA自動機(jī)的構(gòu)建與掃描過程

在預(yù)處理階段，主要任務(wù)是FilterFA自動機(jī)的構(gòu)造。讀入模式串，利用算法1得到的字符集映射函數(shù)將模式串映射為新的模式串；針對映射后得到的像模式串，采用AC算法中Trie樹的構(gòu)造算法，構(gòu)建對應(yīng)的Trie樹；將Trie樹完全化，得到FilterFA自動機(jī)。

FilterFA算法中FilterFA自動機(jī)的具體構(gòu)造過程如算法2所示（其中，算法2中Trie的構(gòu)造采用文獻(xiàn)[5]中的Trie算法）。

算法2FilterFA自動機(jī)的構(gòu)造

在掃描過程中，讀入文本，對文本中的字符進(jìn)行逐個掃描。每掃描一個字符，經(jīng)字符集映射函數(shù)映射，并將映射后得到的字符傳送至FilterFA自動機(jī)。自動機(jī)根據(jù)當(dāng)前狀態(tài)節(jié)點(diǎn)和字符進(jìn)行跳轉(zhuǎn)，每跳轉(zhuǎn)至一個新的狀態(tài)節(jié)點(diǎn)，同時判斷其是否為終止?fàn)顟B(tài)。若當(dāng)前狀態(tài)為終止?fàn)顟B(tài)，說明當(dāng)前位置出現(xiàn)可能匹配。鑒于字符集映射函數(shù)可能將不同的字符映射為同一字符，需要對匹配結(jié)果進(jìn)行進(jìn)一步校驗(yàn)。把該終止?fàn)顟B(tài)對應(yīng)的模式串同對應(yīng)位置的文本串后綴中的字符進(jìn)行一一比較，驗(yàn)證是否為正確匹配結(jié)果。校驗(yàn)至模式串最后一個字符，校驗(yàn)過程結(jié)束。校驗(yàn)完成，讀入下一個字符，開始新一輪搜索；若當(dāng)前狀態(tài)為非終止?fàn)顟B(tài)，則直接讀入下一個字符，開始新一輪搜索，直至整個文本掃描一遍為止，返回最終匹配結(jié)果。

FilterFA算法的具體掃描過程見算法3。

算法3FilterFA算法的掃描過程

以模式串集合{he,hers,she}為例，其對應(yīng)的AC自動機(jī)和FilterFA自動機(jī)分別如圖4和圖5所示。

3.4 空間和時間復(fù)雜度分析

下面分析FilterFA算法的空間復(fù)雜度和時間復(fù)雜度。

定理1FilterFA算法的空間復(fù)雜度為，數(shù)據(jù)訓(xùn)練階段的時間復(fù)雜度為，預(yù)處理階段的時間復(fù)雜度為，搜索階段的平均時間復(fù)雜度為O(n)。

證明

1) 空間復(fù)雜度：FilterFA算法的數(shù)據(jù)存儲結(jié)構(gòu)為FilterFA自動機(jī)。自動機(jī)有個狀態(tài)，每個狀態(tài)節(jié)點(diǎn)需要|Σ′|個指針來存儲其狀態(tài)轉(zhuǎn)移表。因此，F(xiàn)ilterFA算法的空間復(fù)雜度為。

2) 數(shù)據(jù)訓(xùn)練階段的時間復(fù)雜度：在數(shù)據(jù)訓(xùn)練階段，主要任務(wù)為字符依概率排序和分組。在對原字符集依概率排序時，采用快速排序算法所需時間為。將原字符集分為組，對于任一字符，查找當(dāng)前概率最小的分組，需要，最終分組需要時間為。因此，數(shù)據(jù)訓(xùn)練階段的時間復(fù)雜度為。

圖4 模式串{he,hers,she}對應(yīng)的AC自動機(jī)

圖5 模式串{he,hers,she}對應(yīng)的FilterFA自動機(jī)

3) 預(yù)處理時間復(fù)雜度：在預(yù)處理階段，需要將原字符集映射為較小字符集，通過字符集映射函數(shù)進(jìn)行字符集變換僅需要O(1)的時間。其余處理流程和AC相同，構(gòu)造FilterFA自動機(jī)所需時間為。因此，F(xiàn)ilterFA算法預(yù)處理階段的時間復(fù)雜度為。

4) 搜索時間復(fù)雜度：在搜索階段，對于每個文本位置i，需要從當(dāng)前位置開始搜索，查找所有可能出現(xiàn)的模式串。因此，F(xiàn)ilterFA算法搜索階段的平均時間復(fù)雜度為O(n)。

表2是FilterFA算法同經(jīng)典的AC算法[2]、HashTrie算法[12]的空間和時間復(fù)雜度比較。

表2 FilterFA算法和AC算法、HashTrie算法復(fù)雜度對比

在存儲空間方面，AC算法的空間開銷主要用于存儲狀態(tài)轉(zhuǎn)移的二維矩陣，算法空間復(fù)雜度與字符集大小σ成正比。FilterFA算法將原字符集壓縮成較小的字符集，再以Trie樹的結(jié)構(gòu)存儲，優(yōu)于傳統(tǒng)的AC算法。HashTrie算法采用位向量和散列表結(jié)合的方式存儲模式串集和的信息，空間復(fù)雜度，優(yōu)于AC和FilterFA算法。

在預(yù)處理時間方面，AC算法的預(yù)處理時間與模式串規(guī)模|P|和字符集大小σ相關(guān)；HashTrie算法預(yù)處理階段的時間復(fù)雜度為，與字符集大小σ無關(guān)；FilterFA算法復(fù)雜度和HashTrie算法的預(yù)處理時間復(fù)雜度一致，僅與模式串規(guī)模|P|線性相關(guān)，與字符集大小σ無關(guān)，優(yōu)于傳統(tǒng)的AC算法。

在搜索時間方面，F(xiàn)ilterFA算法和AC算法一致，只需將文本掃描一遍，查找所有的匹配位置即可，平均時間復(fù)雜度為O(n)。而HashTrie算法的最壞時間復(fù)雜度與最長模式串的長度lmax線性相關(guān)，高于AC算法和FilterFA算法。FilterFA算法在搜索階段，要優(yōu)于HashTrie算法。

綜上，由理論分析可知，F(xiàn)ilterFA算法不僅降低了自動機(jī)空間存儲開銷，同時，還保持了AC的線性搜索時間復(fù)雜度。

4 實(shí)驗(yàn)評估

本節(jié)通過在真實(shí)數(shù)據(jù)集和隨機(jī)數(shù)據(jù)集上測試，從存儲空間和匹配速度2個方面，將FilterFA算法和AC算法、HashTrie算法進(jìn)行對比。此外，在2種數(shù)據(jù)集上對FilterFA算法的誤識別率進(jìn)行實(shí)驗(yàn)性分析，分別考察模式串規(guī)模、字符集規(guī)模同誤識別率之間的關(guān)系。

實(shí)驗(yàn)硬件環(huán)境如下：CPU AMD Processor 8378 2.41 GHz，內(nèi)存3.25 GB。

實(shí)驗(yàn)軟件環(huán)境如下：Windows 7 32位，編譯平臺Microsoft Visual Studio 2010。

實(shí)驗(yàn)選取的測試數(shù)據(jù)集包括2部分：開源系統(tǒng)中提取的真實(shí)數(shù)據(jù)集和隨機(jī)生成的數(shù)據(jù)集。其中，真實(shí)數(shù)據(jù)集包括MIT入侵檢測數(shù)據(jù)集[19]、Snort規(guī)則集[1]、ClamAV規(guī)則集[20]、URL數(shù)據(jù)集[21]。隨機(jī)數(shù)據(jù)集為系統(tǒng)隨機(jī)生成的模式串集合和文本數(shù)據(jù)集。

ClamAV規(guī)則集+MIT入侵檢測數(shù)據(jù)集：從開源反病毒系統(tǒng)ClamAV 0.90.1版本中抽取的部分精確模式串，作為待匹配的模式串集合。來自MIT公開的網(wǎng)絡(luò)入侵檢測數(shù)據(jù)集mit_1999_training_week1_ friday_inside.dat（約62.7 MB）作為待掃描文本，抽取其中一部分（約32.4 MB）作為訓(xùn)練數(shù)據(jù)集，剩余部分作為測試數(shù)據(jù)集。

Snort規(guī)則集+MIT入侵檢測數(shù)據(jù)集：從開源入侵檢測系統(tǒng)Snort2009.06中提取部分精確模式串，作為待匹配的模式串集合。同樣將MIT數(shù)據(jù)集作為待掃描文本和訓(xùn)練數(shù)據(jù)集。

URL規(guī)則集+URL數(shù)據(jù)集：從網(wǎng)絡(luò)骨干路由器流量中采集的約2 000萬（2.60 GB）條URL規(guī)則。從中隨機(jī)抽取25 000條長度大于4的URL作為待匹配模式串。抽取約2.3 GB作為待掃描文本，并從中抽取1.09 GB作為訓(xùn)練數(shù)據(jù)，剩余的URL為測試數(shù)據(jù)。

隨機(jī)數(shù)據(jù)集：隨機(jī)生成模式串集合和待掃描文本。模式串個數(shù)由1 000增加到1 000 000，模式串和文本中的字符服從等概率獨(dú)立同分布，生成每個字符的概率為。

4.1 存儲空間

算法的存儲空間消耗與模式串的個數(shù)、長度和字符集大小等因素密切相關(guān)，由算法所采用的數(shù)據(jù)結(jié)構(gòu)決定。

在存儲空間方面，從圖6中的實(shí)驗(yàn)結(jié)果可以看出，在隨機(jī)數(shù)據(jù)集上，模式串規(guī)模從1 000增加到20 000。隨著模式串規(guī)模的增大，AC算法的空間開銷線性增長，F(xiàn)ilterFA算法的空間開銷變化幅度較小。當(dāng)像字符集大小為8，且保證誤識別率小于2%的條件下，F(xiàn)ilterFA算法消耗的存儲空間僅為AC算法的3%左右。FilterFA算法消耗的存儲空間遠(yuǎn)低于AC算法，二者存儲空間比僅為3%左右，這與理論分析值4%基本相符。

圖6 在隨機(jī)數(shù)據(jù)集上，F(xiàn)ilterFA算法和AC算法的存儲空間與模式串規(guī)模的關(guān)系（固定像字符集大小為10 ）

將FilterFA算法和AC算法、HashTrie算法對比，在真實(shí)數(shù)據(jù)集ClamAV上進(jìn)行測試，將最短模式串長度控制在8～22。從表3中的實(shí)驗(yàn)結(jié)果可以看出，HashTrie算法的存儲空間最低，F(xiàn)ilterFA算法的存儲空間次之，但均優(yōu)于AC算法。FilterFA算法與AC算法，二者存儲空間比約3%，即FilterFA算法消耗的存儲空間僅為AC算法的3%左右，與隨機(jī)數(shù)據(jù)集上的測試結(jié)果一致。相較于AC算法和HashTrie算法，F(xiàn)ilterFA算法存儲空間高于HashTrie算法，但提供了一種不同于已有算法的新機(jī)制。將大字符集映射之后再構(gòu)造自動機(jī)的策略，在節(jié)約內(nèi)存空間開銷上效果顯著。通過對字符集的直接作用，很好地壓縮了算法自動機(jī)的內(nèi)存開銷。

表3 FilterFA算法和AC算法、HashTrie算法的存儲空間對比

4.2 匹配速度

在隨機(jī)數(shù)據(jù)集上，固定像字符集大小為10，模式串規(guī)模從1 000變化到20 000。隨著模式串規(guī)模的增大，2種算法的匹配速度均下降。在下降的過程中，F(xiàn)ilterFA算法匹配速度仍快于AC算法，約為AC算法的1.4～2.2倍。實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 在隨機(jī)數(shù)據(jù)集上，F(xiàn)ilterFA算法和AC算法的匹配速度對比（固定像字符集大小為10）

在真實(shí)數(shù)據(jù)集ClamAV上，固定新定義的字符集大小為8，保證誤識別率不超過2%，將最短模式串長度控制在8到22變化，同樣將FilterFA算法和AC算法、HashTrie算法進(jìn)行對比測試。從表4中的實(shí)驗(yàn)結(jié)果可以看出，F(xiàn)ilterFA算法的匹配速度略低于AC算法，略優(yōu)于HashTrie算法。3種算法匹配速度基本維持在同一個數(shù)量級，與理論分析一致。這是因?yàn)樵谡鎸?shí)數(shù)據(jù)集上，字符并不一定完全服從等概率分布，對于某些概率分布偏差較大的數(shù)據(jù)，F(xiàn)ilterFA算法造成的誤識別率較大，從而使FilterFA算法在校驗(yàn)過程中，增加了校驗(yàn)工作量，整體相對損失了一部分性能。

4.3 誤識別率

誤識別率是由字符集映射函數(shù)的引入而產(chǎn)生的。字符集映射函數(shù)將字符集映射成一個較小的字符集，必然存在2個不同的字符映射為同一個字符的情況，使FilterFA自動機(jī)在匹配過程中，可能產(chǎn)生誤識別。

表4 FilterFA算法和AC算法、HashTrie算法的匹配速度對比

在真實(shí)數(shù)據(jù)集和隨機(jī)數(shù)據(jù)集2種數(shù)據(jù)集上對FilterFA算法的誤識別率進(jìn)行實(shí)驗(yàn)性分析，考察模式串規(guī)模和誤識別率之間的關(guān)系。

表5 FilterFA算法誤識別率和像字符集規(guī)模大小的關(guān)系

在隨機(jī)數(shù)據(jù)集上，所有字符等概率分布。選取隨機(jī)取模為字符集映射函數(shù)，理論上由隨機(jī)數(shù)據(jù)集取模得到的像字符集亦是等概率均勻分布的。由表5的測試結(jié)果可以看出，隨著像字符集規(guī)模的增大，像字符集大小由2增大到11，誤識別率逐漸減小。當(dāng)像字符集大小為11時，誤識別率趨于0。這也是解釋了為何在之前的實(shí)驗(yàn)中，采用的是新定義的字符集大小為10時的字符集映射函數(shù)。和理論分析的結(jié)果一致，像字符集規(guī)模越大，將不同字符映射為同一字符的概率越小，誤識別率越小。

表6是固定像字符集大小為10時，誤識別率隨模式串規(guī)模變化而變化的情況。當(dāng)模式串規(guī)模不斷增大時，誤識別率隨之增大。模式串規(guī)模由2 000逐漸增加至1 000，誤識別率由0增加至0.005。增加幅度相當(dāng)小，在6%之內(nèi)，誤識別率始終維持在合理的范圍之內(nèi)。

表6 FilterFA算法誤識別率和像模式串規(guī)模大小的關(guān)系

此外，在3種真實(shí)數(shù)據(jù)集上，分別采用2種字符集映射函數(shù)對字符集進(jìn)行變換，測試字符集映射函數(shù)對FilterFA自動機(jī)誤識別率的影響。

映射函數(shù)一：隨機(jī)取模函數(shù)（modN，N為任意小于σ的自然數(shù)）；

映射函數(shù)二：依概率均勻分布得到的字符集映射函數(shù)，即由算法1中的算法得出的映射函數(shù)。

從表7可以看出，在所有測試的數(shù)據(jù)集上，隨著字符集規(guī)模不斷增大，數(shù)據(jù)集大小從6變化到20，2種映射函數(shù)下的FilterFA算法的誤識別率均逐漸變小。在數(shù)據(jù)集規(guī)模較大時，真實(shí)數(shù)據(jù)集Snort和ClamAV上的測試結(jié)果表明，依概率均勻分布得到的字符集映射函數(shù)方法產(chǎn)生的誤識別率遠(yuǎn)小于隨機(jī)取模函數(shù)產(chǎn)生的誤識別率。基于依概率均勻分布的字符集映射函數(shù)優(yōu)于基于隨機(jī)取模的字符集映射函數(shù)方法，這種優(yōu)勢在真實(shí)數(shù)據(jù)集ClamAV上，表現(xiàn)更為顯著。在這2種數(shù)據(jù)集上，更適合采用基于依概率均勻分布的字符集映射函數(shù)。在URL數(shù)據(jù)集上，依概率均勻分布的方法產(chǎn)生的誤識別率要高于隨機(jī)取模方法產(chǎn)生的誤識別率。當(dāng)字符集規(guī)模較大時，兩者差異顯著。這可能是由URL數(shù)據(jù)集與依概率均勻分布方法字符間相互獨(dú)立的假設(shè)前提相沖突導(dǎo)致的。因此，在URL數(shù)據(jù)集上，基于依概率均勻分布的字符集映射函數(shù)并不適合，需要進(jìn)一步尋找更加適合、高效的字符集映射函數(shù)。

表7 隨機(jī)取模函數(shù)與依概率均勻分布函數(shù)對FilterFA算法誤識別率的影響對比

5 結(jié)束語

本文提出了一種基于基于字符集規(guī)約的模式串匹配算法——FilterFA算法。與經(jīng)典的多模式串匹配算法AC算法相比，F(xiàn)ilterFA算法大大減少了自動機(jī)存儲空間消耗，同時保持了AC的線性搜索時間復(fù)雜度。與HashTrie算法相比，F(xiàn)ilterFA算法空間復(fù)雜度高于前者，在搜索階段優(yōu)于前者。不同于HashTrie算法的遞歸散列機(jī)制，F(xiàn)ilterFA算法從字符集出發(fā)，利用字符集映射函數(shù)，將原字符集壓縮為多個像字符集，針對像字符集構(gòu)造新的自動機(jī)FilterFA，將空間復(fù)雜度降至。在定義字符集映射函數(shù)時，給出一種基于字符概率均勻分布求解字符集映射函數(shù)的算法——基于字符獨(dú)立假設(shè)，求解當(dāng)像字符集服從等概率分布，且FilterFA誤識別率最小的近似最優(yōu)解。將FilterFA算法產(chǎn)生的誤識別率控制在盡量不影響算法匹配速度的小概率范圍內(nèi)。

在隨機(jī)數(shù)據(jù)集、Snort數(shù)據(jù)集和ClamAV數(shù)據(jù)集上，F(xiàn)ilterFA算法均取得了較好的實(shí)驗(yàn)效果。在隨機(jī)數(shù)據(jù)集和真實(shí)數(shù)據(jù)集ClamAV上的測試結(jié)果表明，當(dāng)像字符集大小為8，且保證當(dāng)誤識別率小于2%時，F(xiàn)ilterFA算法的存儲空間遠(yuǎn)低于AC算法，F(xiàn)ilterFA算法消耗的存儲空間僅為AC算法的 3%左右。2種算法存儲空間比約3%，同時2種算法的匹配速度相當(dāng)。對于URL數(shù)據(jù)集來說，測試結(jié)果表明，基于依概率均勻分布的字符集映射函數(shù)并不適合。

依概率均勻分布方法中字符間相互獨(dú)立的假設(shè)并不適用于所有的真實(shí)數(shù)據(jù)集，字符間相互獨(dú)立的假設(shè)具有一定的局限性，研究字符間相互關(guān)系的情況下字符集映射函數(shù)的求解策略具有一定的現(xiàn)實(shí)意義。在規(guī)則和文本數(shù)據(jù)不同分布的情況下，字符間不相互獨(dú)立的情況下，字符集映射函數(shù)又該如何設(shè)計。在下一步工作中，將研究更加普遍意義下的字符集映射函數(shù)求解方法以及更加高效的自動機(jī)壓縮方法。

[1]Snort.Org [EB/OL].https:// www.snort.org/.

[2]BOYER R S,MOORE J S.A fast string searching algorithm [J].Communications of the ACM,1977,20(10):762-772.

[3]KHARBUTLI M,ALDWAIRI M,MUGHRABI A.Function and data parallelization of Wu-Manber pattern matching for intrusion detection systems[J].Network Protocols and Algorithms,2012,4(3):46-61.

[4]AHO A V,CORASICK M J.Efficient string matching:an aid to bibliographic search[J].Communications of the ACM,1975,18(6):333-340.

[5]NAVARRO G,RAFFINOT M.Flexible pattern matching in strings:practical on-line search algorithms for texts and biological sequences [M].Oxford City:Cambridge University Press,2002.

[6]BAEZA-YATES R A,GONNET G H.A new approach to text searching[C]//12th International Conference on Research and Development in Information Retrieval.1989:168-175.

[7]DENCKER P,DORRE K,HEUFT J.Optimization of parser tables for portable compilers[J].ACM Transactions on Programming Languages and Systems,1984,6(4):546-572.

[8]NORTON M.Optimizing pattern matching for intrusion detection[EB/OL].http://www.idsresearch.org,2004.

[9]TUCK N,SHERWOOD T,CALDER B,et al.Deterministic memory-efficient string matching algorithms for intrusion detection[C]// IEEE INFOCOM.2004.

[10]AHO V,SETHI R,ULLMAN J D.Compilers:principles,techniques,and tools[M].New Jersey:Addison-Wesley.1985.

[11]AOE J,MORIMOTO K,SATO T.An efficient implementation of trie structures[J].Software-Practice &Experience,1992,22(9):695-721.

[12]ZIEGLER S.Smaller faster table driven parser,unpublished manuscript[Z].Madison Academic Computing Center,1977.

[13]TARJAN R E,YAO A C.Storing a sparse table[J].Communications of the ACM,1979,22:606-611.

[14]FREDMAN M,KOML′OS J,SZEMER′EDI E.Storing a sparse table with O(1) worst case access time[J].Journal of the ACM,1984,31(3):538-544.

[15]楊毅夫,劉燕兵,劉萍,等.串匹配算法中的自動機(jī)緊縮存儲技術(shù)[J].計算機(jī)工程,2009,35(21):39-41.YANG Y F,LIU Y B,LIU P,et al.Automation compact representation technology in string matching algorithm[J].Computer Engineering,2009,35(21):39-41.

[16]NIEVES R,LADRA B S.K2-trees for compact web graph representation[C]//String Processing and Information Retrieval Lecture Notes in Computer Science,2009,5721:18-30.

[17]NIEVES R,LADRA B.S.Compact representation of web graphs with extended functionality[J].Information Systems,2014,39(1):152-174.

[18]張萍,劉燕兵,于靜,等.HashTrie:一種空間高效的多模式串匹配算法[J].通信學(xué)報,2015,36(10):172-180.ZHANG P,LIU Y B,YU J,et al.HashTrie:a space-efficient multiple string matching algorithm[J].Journal on Communication,2015,36(10):172-180.

[19]Available online[EB/OL].http://www.ll.mit.edu/IST/ideval/.

[20]Available online[EB/OL].http://www.clamav.org/.

[21]Available online[EB/OL].http://urlblacklist.com/.

張萍（1987-），女，河南唐河人，中國科學(xué)院信息工程研究所博士生，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全、內(nèi)容過濾等。

何慧敏（1987-），女，山東菏澤人，中國移動（深圳）有限公司工程師，主要研究方向?yàn)榇ヅ渌惴ā?/p>

張春燕（1989-），女，河北衡水人，中國科學(xué)院信息工程研究所實(shí)習(xí)研究員，主要研究方向?yàn)樾畔?nèi)容安全和高性能計算。

曹聰（1987-），男，山東棗莊人，博士，中國科學(xué)院信息工程研究所助理研究員，主要研究方向?yàn)閿?shù)據(jù)挖掘、文本抽取、常識知識獲取。

劉燕兵（1981-），男，湖北麻城人，博士，中國科學(xué)院信息工程研究所副研究員，主要研究方向?yàn)槲谋舅惴ㄔO(shè)計、圖數(shù)據(jù)管理與挖掘、網(wǎng)絡(luò)流識別與處理等。

譚建龍（1974-），男，湖南長沙人，博士，中國科學(xué)院信息工程研究所研究員、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)數(shù)據(jù)流管理、算法設(shè)計、海量正則表達(dá)式匹配、圖像匹配算法等。

FilterFA:a multiple string matching algorithm based on specification of character set

ZHANG Ping1,2,3,HE Hui-min4,ZHANG Chun-yan1,3,CAO Cong1,3,LIU Yan-bing1,3,TAN Jian-long1,3
(1.Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China;2.University of Chinese Academy of Sciences,Beijing 100049,China;3.National Engineering Laboratory for Information Security Technologies,Beijing 100093,China;4.China Mobile (Shenzhen) Co.,Ltd.,Shenzhen 518031,China)

Multiple string matching is one of the core techniques of intrusion detection system,where Aho-Corasick algorithm is widely used.To solve the problem that huge storage overhead of AC would influence performance deeply,an improved algorithm ——FilterFA,based on specification of character set was proposed.This algorithm compressed large character by the character set mapping function,and constructed a new automata based on the mapped character set,then space complexity decreased to.Experiments on synthetic datasets and real-world datasets (such as ClamAV) show that the storage overhead of FilterFA is only about 3% of that of AC,while the size of the character set is 8,and the false recognition rate is less than 2%.

intrusion detection,multiple string matching,specification of character set,character set mapping

s:The Strategic Priority Research Program of the Chinese Academy of Sciences (No.XDA06031000),Xinjiang Uygur Autonomous Region Science and Technology Project(No.201230123)

TN925

A

10.11959/j.issn.1000-436x.2016277

2016-08-11；

2016-10-11

張萍，zhangping@iie.ac.cn

中國科學(xué)院戰(zhàn)略性科技先導(dǎo)專項基金資助項目(No.XDA06031000)；新疆自治區(qū)科技專項基金資助項目（No.201230123）