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

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

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

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

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

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

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

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

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 誤識(shí)別率對(duì)匹配速度的影響

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

FilterFA算法的具體掃描過(guò)程見(jiàn)算法3。

算法3FilterFA算法的掃描過(guò)程

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

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

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

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

證明

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

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

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

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

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

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

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

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

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

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

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

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

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

本節(jié)通過(guò)在真實(shí)數(shù)據(jù)集和隨機(jī)數(shù)據(jù)集上測(cè)試，從存儲(chǔ)空間和匹配速度2個(gè)方面，將FilterFA算法和AC算法、HashTrie算法進(jìn)行對(duì)比。此外，在2種數(shù)據(jù)集上對(duì)FilterFA算法的誤識(shí)別率進(jìn)行實(shí)驗(yàn)性分析，分別考察模式串規(guī)模、字符集規(guī)模同誤識(shí)別率之間的關(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位，編譯平臺(tái)Microsoft Visual Studio 2010。

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

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

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

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

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

4.1 存儲(chǔ)空間

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

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

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

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

表3 FilterFA算法和AC算法、HashTrie算法的存儲(chǔ)空間對(duì)比

4.2 匹配速度

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

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

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

4.3 誤識(shí)別率

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

本文提出了一種基于基于字符集規(guī)約的模式串匹配算法——FilterFA算法。與經(jīng)典的多模式串匹配算法AC算法相比，F(xiàn)ilterFA算法大大減少了自動(dòng)機(jī)存儲(chǔ)空間消耗，同時(shí)保持了AC的線(xiàn)性搜索時(shí)間復(fù)雜度。與HashTrie算法相比，F(xiàn)ilterFA算法空間復(fù)雜度高于前者，在搜索階段優(yōu)于前者。不同于HashTrie算法的遞歸散列機(jī)制，F(xiàn)ilterFA算法從字符集出發(fā)，利用字符集映射函數(shù)，將原字符集壓縮為多個(gè)像字符集，針對(duì)像字符集構(gòu)造新的自動(dòng)機(jī)FilterFA，將空間復(fù)雜度降至。在定義字符集映射函數(shù)時(shí)，給出一種基于字符概率均勻分布求解字符集映射函數(shù)的算法——基于字符獨(dú)立假設(shè)，求解當(dāng)像字符集服從等概率分布，且FilterFA誤識(shí)別率最小的近似最優(yōu)解。將FilterFA算法產(chǎn)生的誤識(shí)別率控制在盡量不影響算法匹配速度的小概率范圍內(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上的測(cè)試結(jié)果表明，當(dāng)像字符集大小為8，且保證當(dāng)誤識(shí)別率小于2%時(shí)，F(xiàn)ilterFA算法的存儲(chǔ)空間遠(yuǎn)低于A(yíng)C算法，F(xiàn)ilterFA算法消耗的存儲(chǔ)空間僅為AC算法的 3%左右。2種算法存儲(chǔ)空間比約3%，同時(shí)2種算法的匹配速度相當(dāng)。對(duì)于URL數(shù)據(jù)集來(lái)說(shuō)，測(cè)試結(jié)果表明，基于依概率均勻分布的字符集映射函數(shù)并不適合。

依概率均勻分布方法中字符間相互獨(dú)立的假設(shè)并不適用于所有的真實(shí)數(shù)據(jù)集，字符間相互獨(dú)立的假設(shè)具有一定的局限性，研究字符間相互關(guān)系的情況下字符集映射函數(shù)的求解策略具有一定的現(xiàn)實(shí)意義。在規(guī)則和文本數(shù)據(jù)不同分布的情況下，字符間不相互獨(dú)立的情況下，字符集映射函數(shù)又該如何設(shè)計(jì)。在下一步工作中，將研究更加普遍意義下的字符集映射函數(shù)求解方法以及更加高效的自動(dòng)機(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]楊毅夫,劉燕兵,劉萍,等.串匹配算法中的自動(dòng)機(jī)緊縮存儲(chǔ)技術(shù)[J].計(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é)報(bào),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-），女，河南唐河人，中國(guó)科學(xué)院信息工程研究所博士生，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全、內(nèi)容過(guò)濾等。

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

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

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

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

譚建龍（1974-），男，湖南長(zhǎng)沙人，博士，中國(guó)科學(xué)院信息工程研究所研究員、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)數(shù)據(jù)流管理、算法設(shè)計(jì)、海量正則表達(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

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