HybridFA：一種基于統(tǒng)計的AC自動機空間優(yōu)化技術(shù)

熊剛，何慧敏，于靜，劉燕兵，郭莉

（1. 中國科學院 信息工程研究所，北京 100093；2. 中國移動（深圳）有限公司，深圳 518031）

1 引言

多模式串匹配是計算機科學領(lǐng)域最經(jīng)典的問題之一，目的是在任意字符串文本中找出已知的一組特定字符串集合出現(xiàn)的所有位置。網(wǎng)絡(luò)內(nèi)容安全處理主要采用串匹配算法對網(wǎng)絡(luò)分組的內(nèi)容負載進行檢測、分析和過濾。典型的網(wǎng)絡(luò)內(nèi)容安全應用軟件的入侵檢測/防御系統(tǒng)和反病毒反垃圾郵件檢測系統(tǒng)都采用串匹配算法來檢測惡意數(shù)據(jù)[1～3]?；谧詣訖C的串匹配算法是多模式串匹配采用的主要研究方法之一，它以自動機作為數(shù)據(jù)結(jié)構(gòu)，在搜索過程中通過搜索文本中自動機所能識別的語言來實現(xiàn)匹配，該類方法性能相對穩(wěn)定，因而在實際系統(tǒng)中被廣泛使用。但該類方法空間開銷較大，匹配速度較慢。

Aho-Corasick (AC) 自動機[4]是最經(jīng)典、實際應用最廣的自動機之一，開源病毒檢測系統(tǒng) ClamAV和開源入侵檢測系統(tǒng)Snort均使用AC自動機作為其基本的數(shù)據(jù)結(jié)構(gòu)?；贏C自動機的串匹配算法稱為AC算法，其思想是使用Trie樹存儲所有的模式串，然后從Trie樹的根節(jié)點開始層次遍歷，構(gòu)造節(jié)點間的后綴鏈（supply link）[5]。在匹配過程中，若當前狀態(tài)無法識別輸入字符時，就沿著后綴鏈回溯（也稱為失效轉(zhuǎn)移），直到能夠識別該字符的狀態(tài)為止。該算法可以在O(n)時間復雜度內(nèi)找到文本中的所有目標模式（n為給定文本長度），而與模式集合的規(guī)模無關(guān)。但其突出的問題是數(shù)據(jù)流在匹配時往往需要進行多次回溯才能跳轉(zhuǎn)到有效狀態(tài)繼續(xù)匹配，嚴重影響了匹配速度。

高級AC自動機是在AC自動機的基礎(chǔ)上，將后綴鏈進行改進，直接指向當前狀態(tài)的后繼狀態(tài)。也就是說，所有狀態(tài)對于字母表的每一個字符都有相應的轉(zhuǎn)移，稱為一個完全的自動機。在匹配過程中無需沿著后綴鏈回溯，而是直接跳轉(zhuǎn)到它的后繼狀態(tài)，因而匹配速度更快。但高級AC自動機的空間復雜度為O(|P| |Σ|)（其中P是模式串集合，Σ是字符集），存在巨大的空間浪費。

為解決自動機因為存儲空間引發(fā)的性能瓶頸，國內(nèi)外學者提出了許多經(jīng)典的壓縮方案。1984年Dencker等[6]最早提出了一種行壓縮方法，使狀態(tài)轉(zhuǎn)移表中每一行只存儲非空的轉(zhuǎn)移邊對應的讀入字符和下一跳狀態(tài)，但該方法僅對稀疏的狀態(tài)轉(zhuǎn)移表具有良好的壓縮效果，當狀態(tài)轉(zhuǎn)移表相對稠密時，該方法的效果變差，甚至會超過壓縮前的存儲空間。文獻[7～9]使用一個一維數(shù)組重疊排列狀態(tài)轉(zhuǎn)移表中所有的行，但必須保證各行的非空元素不得相互沖突，另外用2個數(shù)組分別存儲每一行的偏移位置和一維數(shù)組中每個元素所屬的行。該方法具有較好的壓縮效果，并且可以達到O(1)的狀態(tài)轉(zhuǎn)移速度，但處理過程中峰值內(nèi)存太大，導致其不能處理大規(guī)模的串匹配問題。此外，劉燕兵等[10]利用suffix-trie和雙數(shù)組相結(jié)合的數(shù)據(jù)結(jié)構(gòu)來存儲模式串，該方法在壓縮存儲空間的同時也保持了快速的訪問速度。實驗表明該方法比較適合關(guān)鍵詞規(guī)模為10 000～20 000的應用環(huán)境。

上述自動機壓縮方法的基本思想大都是針對自動機的狀態(tài)轉(zhuǎn)移表，刪除以空轉(zhuǎn)移為主的冗余狀態(tài)轉(zhuǎn)移邊，只保存有用的信息，在搜索過程中通過計算來查找下一跳狀態(tài)。此類方法都不能適用于無空轉(zhuǎn)移狀態(tài)的高級AC自動機的壓縮。而高級AC自動機空間開銷大的主要原因是它將每個節(jié)點都完全化，而在實際應用系統(tǒng)中并不是所有節(jié)點都具有較高的訪問頻率，將訪問頻率相對較低的節(jié)點完全化會占用大量存儲空間，而不會帶來匹配速度的顯著提升。本文將充分分析待處理數(shù)據(jù)流量的特征，提出基于數(shù)據(jù)訪問特征的混合自動機構(gòu)建算法HybridAC。根據(jù)不同的數(shù)據(jù)流特征，分別研究了按訪問頻率完全化和按層次完全化的2種混合自動機的構(gòu)建算法HybridAC_1和HybridAC_2，并進一步綜合考慮數(shù)據(jù)流量的特征，結(jié)合上述2種方法的優(yōu)點，提出改進算法 HybridAC_3。在 Snort、 ClamAV、URL等真實數(shù)據(jù)集上的實驗表明，本算法在保證匹配速度的同時，大大降低了高級AC自動機的存儲空間。

2 算法設(shè)計

2.1 算法提出的依據(jù)

AC自動機作為最經(jīng)典、實際應用最廣的自動機之一，廣泛應用于入侵檢測/防御系統(tǒng)和反病毒反垃圾郵件檢測系統(tǒng)。根據(jù)自動機構(gòu)造的程度，AC自動機可以分為基本的AC自動機和高級AC自動機（完全化的AC自動機）。基本的AC自動機只保存模式串的Trie結(jié)構(gòu)和每個節(jié)點的回溯狀態(tài)，在搜索過程中，如果狀態(tài)轉(zhuǎn)移不成功，則需要回溯；高級AC自動機對于字符集中的每個字符，所有的狀態(tài)都有相應的轉(zhuǎn)移，在搜索過程中不需要回溯，因而匹配速度更快。但在高級AC算法中，自動機的所有狀態(tài)節(jié)點都被完全化，每個節(jié)點具有相同的地位。然而在實際應用中，自動機的每個節(jié)點的訪問頻率各不相同，把一個數(shù)據(jù)訪問頻率為零或者接近于零的節(jié)點完全化，存在很大的空間浪費。

數(shù)據(jù)流量對自動機不同節(jié)點的訪問頻率各不相同，下面以開源入侵檢測系統(tǒng)Snort中的模式串規(guī)則為例，分析數(shù)據(jù)流量對自動機各狀態(tài)節(jié)點的訪問特征，本實驗中待掃描的文本數(shù)據(jù)來自MIT公開的一組真實的網(wǎng)絡(luò)數(shù)據(jù)，所采用的實驗方法如下。

1) 按頻率統(tǒng)計方法

統(tǒng)計高級AC自動機各個節(jié)點的訪問頻率，按照訪問頻率從大到小對自動機的各個節(jié)點排序，依次對訪問頻率累計求和，分別統(tǒng)計每個頻率界限內(nèi)的節(jié)點數(shù)目。統(tǒng)計結(jié)果如表1所示，可見，前408個節(jié)點的累計訪問頻率已經(jīng)達到91%，節(jié)點數(shù)目所占比例不超過 1%；前3% 的節(jié)點累計訪問頻率達到98%。

表1 高級AC自動機各節(jié)點的訪問頻率統(tǒng)計

2) 按層次統(tǒng)計方法

把高級AC自動機的Trie樹結(jié)構(gòu)圖的根節(jié)點標記為第一層節(jié)點，按照廣度優(yōu)先搜索的方式，根節(jié)點的后續(xù)未標記節(jié)點為第2層節(jié)點，以此類推。分別統(tǒng)計各層節(jié)點的訪問頻率，實驗結(jié)果如表2所示?？梢钥闯觯S著層次的增大，每層節(jié)點的訪問頻率逐漸降低。根據(jù)統(tǒng)計，前3層節(jié)點的累計訪問頻率已經(jīng)超過95%，第8層及以后的節(jié)點訪問頻率幾乎為零。

表2 高級AC自動機各層訪問頻率統(tǒng)計

統(tǒng)計結(jié)果表明，大部分數(shù)據(jù)流只訪問小部分節(jié)點，大多數(shù)節(jié)點幾乎未被訪問過；其次，數(shù)據(jù)流量傾向于訪問靠近根節(jié)點的低層節(jié)點，離根節(jié)點較遠的高層節(jié)點的訪問頻率接近于0。根據(jù)數(shù)據(jù)流量的這些顯著特征，本文將把訪問頻率高的節(jié)點和層次完全化，其余節(jié)點只保存基本的Trie樹結(jié)構(gòu)和回溯狀態(tài)。根據(jù)表1和表2的統(tǒng)計分析，需要完全化的節(jié)點比例很小，所以該算法可以大幅度降低存儲空間。

2.2 HybridFA算法的基本思想

HybridFA算法是根據(jù)數(shù)據(jù)流量的訪問特征，分別按訪問頻率完全化（HybridFA_1算法）和按層次完全化（HybridFA_2算法）2種方式來改善高級AC自動機的空間浪費問題。按訪問頻率完全化是根據(jù)大部分數(shù)據(jù)流量只訪問小部分節(jié)點的特征，把訪問頻率高的節(jié)點完全化；按層次完全化則根據(jù)數(shù)據(jù)流量傾向于訪問靠近根節(jié)點的低層節(jié)點的特征，把低層節(jié)點完全化。2種算法的流程如圖1所示。

圖1 基于訪問層次完全化和訪問頻率完全化構(gòu)建HybridFA的流程

2.3 HybridFA算法的設(shè)計與實現(xiàn)

HybridFA算法在數(shù)據(jù)訓練階段統(tǒng)計各狀態(tài)節(jié)點的訪問頻率，確定完全化的訪問頻率界限和層次界限，然后根據(jù)按訪問頻率完全化和按層次完全化2種算法分別構(gòu)建由完全化節(jié)點和不完全節(jié)點混合構(gòu)成的自動機HybridFA，并實現(xiàn)數(shù)據(jù)掃描。

2.3.1 數(shù)據(jù)訓練

數(shù)據(jù)訓練階段的主要任務是分析數(shù)據(jù)流量的訪問特征，統(tǒng)計自動機各狀態(tài)節(jié)點的訪問頻率，分別確定按訪問頻率完全化和按訪問層次完全化2種方法所需要完全化的節(jié)點。具體步驟如下。

Step1對模式串規(guī)則構(gòu)造高級AC自動機。首先對模式串規(guī)則構(gòu)建Trie樹，然后為每個節(jié)點計算其回溯狀態(tài)，并把所有節(jié)點都完全化，也就是使所有節(jié)點包含對任意字符的下一跳狀態(tài)，至此完成對高級AC自動機的構(gòu)建。

Step2掃描訓練數(shù)據(jù)，在高級AC自動機對數(shù)據(jù)進行匹配的過程中，統(tǒng)計自動機每個節(jié)點的訪問頻率。

Step3按照訪問頻率的遞減順序，對自動機的每個節(jié)點排序，并對排序后節(jié)點的訪問頻率累計求和。選擇合適的訪問頻率作為訪問頻率界限fre，把在訪問頻率界限范圍內(nèi)的所有節(jié)點標記為Hybrid_1算法需要完全化的節(jié)點，其他節(jié)點仍按照AC自動機的構(gòu)造方式保留失效轉(zhuǎn)移。

圖2 按照訪問頻率完全化構(gòu)建HybridFA自動機示意

Step4廣度優(yōu)先遍歷高級AC自動機，從根節(jié)點開始，按層次遞增順序統(tǒng)計每層節(jié)點的累計訪問頻率，并計算累計層次的訪問頻率之和占所有節(jié)點訪問頻率之和的比值，選擇合適的比值作為訪問層次界限level，把層次界限范圍內(nèi)的所有節(jié)點標記為Hybrid_2算法需要完全化的節(jié)點，其他節(jié)點仍保存可識別字符的跳轉(zhuǎn)和失效轉(zhuǎn)移。

2.3.2 按訪問頻率完全化算法

按訪問頻率完全化的方法在預處理過程中，首先對模式串規(guī)則構(gòu)建Trie樹，然后為每個節(jié)點計算其回溯狀態(tài)，并把在訪問頻率界限fre范圍內(nèi)的節(jié)點完全化，即對任意字符，計算該節(jié)點的下一跳狀態(tài)，稱此算法為HybridAC_1。圖2是按照訪問頻率完全化構(gòu)建的混合自動機示意。編號為{0，1，2，3}的灰色節(jié)點表示被完全化的節(jié)點，節(jié)點上的表格表示該節(jié)點存儲的對任意字符的跳轉(zhuǎn)狀態(tài)；標號為{4，5，6，7}的白色節(jié)點表示未被完全化的節(jié)點，節(jié)點上的表格表示該節(jié)點存儲的可識別字符的跳轉(zhuǎn)和失效轉(zhuǎn)移。圖3是該自動機的構(gòu)建過程的偽代碼（其中Trie(P)采用文獻[11]中的Trie(P)算法）。

圖4為HybridFA算法掃描過程的偽代碼，在掃描過程中，逐個讀入文本字符，此時可能出現(xiàn) 2種情況。

1) 如果當前狀態(tài)Current為完全化的狀態(tài)，則根據(jù)當前讀入字符c，直接從狀態(tài)轉(zhuǎn)移表中查找其對應的下一跳狀態(tài)GoTo(Current,c)，并令Current←GoTo(Current,c)。

2) 如果當前狀態(tài)Current為未完全化的狀態(tài)，首先查找當前狀態(tài)的狀態(tài)轉(zhuǎn)移表，查看GoTo(Current,c)是否為NULL，如果GoTo(Current, c) ≠ NULL，則 令Current ← GoTo(Current, c) ， 如 果GoTo(Current, c) = NULL，則根據(jù)其回溯狀態(tài)回溯，直到 找 到Current使GoTo(Current,c)≠ NULL ， 令Current← GoTo(Current,c)。

圖3 HybridFA自動機構(gòu)建過程偽代碼

圖4 HybridFA算法掃描過程偽代碼

處理完當前讀入字符，判斷當前狀態(tài)Current是否為終止狀態(tài)，如果為終止狀態(tài)則輸出所有的匹配結(jié)果，否則，讀入下一個文本字符，繼續(xù)對文本進行掃描。

2.3.3 按訪問層次完全化算法

按訪問層次完全化的算法在預處理過程中，首先對模式串規(guī)則構(gòu)建Trie樹，然后為每個節(jié)點計算其回溯狀態(tài)，然后把在層次界限 level范圍內(nèi)所有層的節(jié)點完全化，即對任意字符，計算該節(jié)點的下一跳狀態(tài)。其中，根節(jié)點的level為0，level值隨著樹的深度變化逐層增加 1，稱此算法為HybridAC_2。圖 5是按照訪問層次完全化生成的HybridFA自動機的示意。其中自動機的第1、2、3層包含的全部節(jié)點被完全化，其他層的節(jié)點僅保留可識別字符的跳轉(zhuǎn)和失效轉(zhuǎn)移。HybridAC_2算法在構(gòu)建自動機過程中，除了選擇完全化的節(jié)點不同，其他過程與 HybridFA_1算法相同，而數(shù)據(jù)掃描過程與HybridFA_1算法一致。

2.3.4 綜合考慮數(shù)據(jù)流量特征的完全化算法

根據(jù)2.1節(jié)對數(shù)據(jù)流量的統(tǒng)計分析，得到數(shù)據(jù)流量的2種訪問特征：大部分的數(shù)據(jù)只訪問小部分的節(jié)點；數(shù)據(jù)傾向于訪問靠近根節(jié)點的低層節(jié)點。據(jù)此，上文分別按訪問頻率完全化和按層次完全化2種方法構(gòu)建符合數(shù)據(jù)流量訪問特征的自動機。按頻率完全化的方法，完全化的最小單位為節(jié)點，對數(shù)據(jù)流量的統(tǒng)計更精確，所以需要完全化的節(jié)點相對較少，自動機所需要存儲空間越少；但是當數(shù)據(jù)流量有較大變化時，當前訪問頻率高的節(jié)點可能變成未完全化的節(jié)點，從而會導致匹配速度下降。按層次完全化的方法，完全化靠近根節(jié)點的所有低層節(jié)點，當數(shù)據(jù)流量發(fā)生變化時，盡管訪問頻率高的節(jié)點可能發(fā)生變化，但大部分高訪問頻率節(jié)點仍偏向集中在低層節(jié)點，所以對匹配速度的影響相對較小；但是當部分訪問頻率高的節(jié)點出現(xiàn)在較高層次時，由于完全化的最小單位為一層，若想進一步提高匹配速度，需增多完全化的層數(shù)。因此，在提高相同匹配速度時，基于訪問層次完全化算法增加的存儲開銷將超過基于訪問頻率完全化算法。

圖5 按照層次完全化構(gòu)建HybridFA自動機示意

綜合考慮數(shù)據(jù)流量的特征，結(jié)合按訪問頻率完全化和按層次完全化2種方法的特點，本節(jié)提出進一步的改進方案。首先將靠近根節(jié)點的低層節(jié)點完全化，再把層次相對較高且訪問頻率較高的節(jié)點也完全化，如此便不會陷入因某條模式串的命中率較高而使完全化的層次增多或者因數(shù)據(jù)流量發(fā)生變化而使匹配速度大幅度下降的問題，稱這種構(gòu)建自動機的算法為HybridAC_3。構(gòu)建HybridAC_3的具體步驟如下。

Step1通過掃描訓練數(shù)據(jù)并統(tǒng)計自動機中每個節(jié)點的訪問頻率，確定需要完全化的訪問層次界限level和訪問頻率界限fre，并把在level范圍內(nèi)所有層次的節(jié)點標記為需要完全化的節(jié)點，另外標記在fre范圍內(nèi)而不在level范圍內(nèi)的節(jié)點為需要完全化的節(jié)點。

Step2確定完全化節(jié)點后，自動機構(gòu)建過程和數(shù)據(jù)掃描過程與HybridFA_1算法相同。

2.4 空間復雜度分析

自動機存儲空間的大小與狀態(tài)轉(zhuǎn)移邊的數(shù)目成正比。由于按頻率完全化和按照層次完全化的方法根據(jù)數(shù)據(jù)流量的特點，僅需要完全化一部分狀態(tài)節(jié)點，所以與高級AC算法相比，二者的狀態(tài)轉(zhuǎn)移邊更少，存儲空間更小。具體存儲空間的大小與完全化的節(jié)點數(shù)目相關(guān)。下面分析完全化的節(jié)點比率與所需存儲空間的關(guān)系。

已知有限字符集合記作Σ(本文數(shù)據(jù)集中字符集大小|Σ|均為256)，構(gòu)建的自動機中所有狀態(tài)集合記作M，被完全化的節(jié)點（狀態(tài)）占所有節(jié)點（狀態(tài)）的比率記作k(0＜k＜1)。當完全化比率為k時，所構(gòu)建自動機存儲空間的上限占高級 AC自動機存儲空間的比率為

3 實驗結(jié)果與分析

本節(jié)將通過一系列實驗對本文提出的HybridFA算法的性能進行系統(tǒng)驗證，3種HybridFA算法的存儲空間（MB）和匹配速度（Mbit/s）將與高級AC算法在3個真實數(shù)據(jù)集上進行比較。

1) ClamAV規(guī)則+MIT數(shù)據(jù)

Clam Antivirus[12]是一個開源的防病毒檢測軟件，病毒庫特征不斷更新，抽取了 ClamWin Free AntiVirus 0.90.1版本中的部分精確模式串作為本實驗的規(guī)則。待掃描的文本數(shù)據(jù)來自MIT公開的一組真實的網(wǎng)絡(luò)數(shù)據(jù)[13]，它的原始目的是用來對網(wǎng)絡(luò)入侵檢測系統(tǒng)進行評估，使用 mit_1999_training_week1_friday_inside.dat（約62.7 MB）作為待掃描文本，選取部分（約32.4 MB）作為訓練數(shù)據(jù)，剩余部分作為測試數(shù)據(jù)。

2) Snort規(guī)則+MIT數(shù)據(jù)

Snort[14]是一套開源代碼的網(wǎng)絡(luò)入侵預防軟件與網(wǎng)絡(luò)入侵檢測軟件，規(guī)則庫定期發(fā)布。抽取了2009.06版本中的部分精確模式串作為本實驗的規(guī)則。待掃描的文本數(shù)據(jù)與ClamAV相同。

3) URL規(guī)則+URL數(shù)據(jù)

從骨干路由器上采集了約100 GB的URL數(shù)據(jù)，對采集數(shù)據(jù)去重后，得到 2.60 GB、約 2 000萬條URL。從中隨機抽取了50 000條URL（URL長度大于4）作為規(guī)則，抽取了約2.3 GB作為待掃描文本，其中1.09 GB作為訓練數(shù)據(jù)，剩余部分作為測試數(shù)據(jù)。

3.1 實驗結(jié)果與分析

3.1.1 數(shù)據(jù)流量訪問特征

按照 2.1節(jié)中數(shù)據(jù)流量的統(tǒng)計方法，分別統(tǒng)計Snort規(guī)則、ClamAV規(guī)則和URL規(guī)則上高級AC自動機不同訪問頻率下包含的節(jié)點數(shù)目所占的百分率（如圖6所示）和各層節(jié)點下的累計訪問頻率（如圖7所示）。由圖6可見，在98%的訪問頻率界限下，數(shù)據(jù)流僅訪問了基于Snort規(guī)則的高級AC自動機不足2.5%的節(jié)點，ClamAV規(guī)則對應節(jié)點的累計訪問比率不足 1%，而 URL規(guī)則上的相應比例僅為0.51%。其次，數(shù)據(jù)流量傾向于訪問靠近根節(jié)點的低層節(jié)點，Snort規(guī)則前 3層的節(jié)點累計訪問頻率為88.9%，ClamAV規(guī)則為89.3%，URL規(guī)則為86.5%。由此，在真實數(shù)據(jù)集上，按照訪問頻率完全化和按照層次完全化的方法符合數(shù)據(jù)流量的訪問特征。

圖6 高級AC自動機以頻率為界限的數(shù)據(jù)流量統(tǒng)計結(jié)果

圖7 高級AC自動機以層次為界限的數(shù)據(jù)流量統(tǒng)計結(jié)果

3.1.2 存儲空間和匹配速度測試

1) 按訪問頻率完全化和層次完全化2種算法

2種完全化算法在3個數(shù)據(jù)集上的性能將分別與高級AC算法進行對比，高級AC算法在相應數(shù)據(jù)集上的存儲空間與匹配速度如表3所示。

本節(jié)首先測試訪問頻率界限在 90%～98%變化時（變化間隔為1%），算法HybridFA_1的存儲空間和匹配速度的變化情況，實驗結(jié)果如圖8中相應曲線所示?？梢婋S著訪問頻率界限的增高，在3種真實數(shù)據(jù)集上HybridFA_1算法的存儲空間均逐漸增大，這是由于訪問頻率界限越高，需要完全化的節(jié)點越多，從而使存儲空間增大；在匹配速度方面，隨著訪問頻率界限的提高，在3種真實數(shù)據(jù)集上HybridFA_1算法的匹配速度也逐漸提高，這是由于完全化的節(jié)點數(shù)目越多，在匹配過程中狀態(tài)需要回溯的次數(shù)越少，因而匹配速度越快。當訪問頻率界限為 98%時，HybridFA_1算法在Snort、ClamAV和URL上的存儲空間分別為2.22 MB、10.25 MB和8.60 MB，僅占高級AC自動機存儲空間的3.96%、1.86%和4.58%，而匹配速度分別是高級AC自動機的82.78%、106.06%和 79.98%?？梢?，該算法在保證匹配速度的同時，大大降低了存儲空間。

訪問層次界限在2～10層變化時（變化間隔為1層），算法HybridFA_2的存儲空間和匹配速度隨層次界限的變化結(jié)果如圖8中相應曲線所示。

圖8 HybridFA_1算法，HybridFA_2算法在Snort、ClamAV、URL 3個真實數(shù)據(jù)集上匹配速度與存儲空間的關(guān)系

在 3種數(shù)據(jù)集上，當訪問層次界限提高時，HybridFA_2算法的存儲空間均逐漸增大，相應的匹配速度也逐漸增快，與 HybridFA_1具有相似的實驗結(jié)果。但隨著完全化的層次界限的提高，HybridFA_2算法的匹配速度增長速度逐漸減慢，而存儲空間卻增長迅速，尤其當訪問層次界限設(shè)為 3層以上時，這種變化趨勢更加明顯。當訪問層次界限設(shè)為3層時，HybridFA_2算法在Snort、ClamAV和URL上的存儲空間分別為2.22 MB、13.29 MB和8.22 MB，僅分別占高級AC自動機存儲空間的3.95%、2.42%和 4.38%，而匹配速度分別是高級AC自動機匹配速度的62.13%、90%和56.22%。另外，與HybridFA_1算法相比，在存儲空間相近時，HybridFA_1算法均具有更快的匹配速度。

綜合上述分析，從存儲空間和匹配速度的測試結(jié)果表明，當訪問頻率界限為98%時，HybridFA_1算法在3種數(shù)據(jù)集上存儲空間的平均值僅為AC自動機存儲空間的3.47%，且最高比率為4.58%，而匹配速度的平均值為 AC自動機匹配速度的89.61%，且最低比率為79.98%；當訪問層次界限為3時，HybridFA_2算法的在3種數(shù)據(jù)集上的存儲空間的平均值僅為AC自動機存儲空間的3.58%，且最高比率為4.38%，而匹配速度的平均值為AC自動機匹配速度的69.45%，且最低比率為56.22%。可見，2種算法在匹配速度不低于高級AC的50%時，存儲空間已降低到高級AC的5%以下。

2) 綜合考慮數(shù)據(jù)流量特征的完全化算法

由圖 8可知，當完全化的訪問頻率界限設(shè)為95%或更大時，HybridFA_1算法存儲空間的增長速度逐漸增快，本文將 HybridFA_3算法的頻率界限設(shè)為 98%；另外，隨著完全化層次界限的增大，HybridFA_2算法在匹配速度增長的同時，存儲空間也增長迅速，而當層次界限設(shè)為3層時，存儲空間小于高級AC的5%，且匹配速度均超過高級AC算法的50%，所以將HybridFA_3算法的層次界限設(shè)為 3。表3顯示了HybridFA_1算法、HybridFA_2算法、HybridFA_3算法、高級AC算法在3個真實數(shù)據(jù)集上存儲空間與匹配速度的對比結(jié)果。

由表3分析可見，HybridFA_3算法的存儲空間略大于HybridFA_1算法和HybridFA_2算法，但匹配速度都快于二者。同時，HybridFA_3算法在Snort、ClamAV和URL這3個數(shù)據(jù)集上的存儲空間分別為2.75 MB、14.55 MB和8.70 MB，僅占高級AC自動機存儲空間的4.90%、2.65%和4.63%，而匹配速度分別是高級AC自動機的85.80%、120.05%和83.81%?？梢?，存儲空間均小于高級AC算法的5%；匹配速度在 Snort規(guī)則和 URL規(guī)則上與高級AC算法相當，在ClamAV規(guī)則上快于高級AC算法。

實驗結(jié)果表明，按訪問頻率完全化和按訪問層次完全化2種方法在構(gòu)建HybridFA時都具有較好的壓縮效果。對比而言，按頻率完全化的方法，完全化的最小單位為節(jié)點，對數(shù)據(jù)流量的統(tǒng)計更精確，所以需要完全化的節(jié)點相對較少，自動機所需要存儲空間也更少，但是對數(shù)據(jù)流量變化適應性不強。按層次完全化的方法，完全化靠近根節(jié)點的所有低層節(jié)點，當數(shù)據(jù)流量發(fā)生變化時，訪問頻率高的節(jié)點可能發(fā)生變化，但大部分高訪問頻率的節(jié)點仍集中在低層節(jié)點中，對數(shù)據(jù)流量的變化適應性相對較強。在實際應用中，隨著完全化層次的增加，存儲空間也相應迅速增長，因此需要根據(jù)具體需求權(quán)衡存儲空間與匹配速度的關(guān)系。最后提出的結(jié)合數(shù)據(jù)流訪問頻率和訪問層次特征的混合自動機構(gòu)建算法在存儲空間、匹配速度和數(shù)據(jù)適應性等綜合性能上獲得了最好效果。

4 結(jié)束語

本文根據(jù)數(shù)據(jù)流對自動機節(jié)點的訪問特征，提出基于訪問頻率完全化和基于訪問層次完全化的 2種構(gòu)建混合自動機的算法，并綜合分析以上2種算法的優(yōu)勢，進一步提出改進的自動機完全化算法。真實數(shù)據(jù)集上的實驗結(jié)果表明，與高級AC算法相比，3種算法在保證匹配速度的同時，存儲空間降低到高級 AC算法的5%左右。同時，結(jié)合數(shù)據(jù)流訪問頻率和訪問層次特征的自動機完全化算法在匹配速度和數(shù)據(jù)適應性方面都獲得了最好效果。未來工作將考慮對訪問頻率和訪問層次這2個重要參數(shù)的選擇進行優(yōu)化。

表3 HybridFA_1、HybridFA_2、HybridFA_3和高級AC算法在3組真實數(shù)據(jù)集上存儲空間和匹配速度對比

[1] ME L, HEYE L, KURI J,et al. A pattern matching based filter for audit reduction and fast detection of potential intrusions[A]. The 3rd International Workshop on the Recent Advances in Intrusion Detection[C]. Toulouse, France, 2000.17-27.

[2] NAVARRO G, KURI J. Fast Multipattern Search Algorithms for Intrusion Detection[R]. Technical Report TR/DCC-99-11, Dept. of Computer Science, Univ of Chile.1999.

[3] VARGHESE G, FIST M. Applying Fast String Matching to Intrusion Detection[R]. Technical Report In preparation, successor to UCSD TR CS2001-0670. University of California, San Diego. 2002.

[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]. SIAM Publishing, 2002.

[6] 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.

[7] AHO A V, SETHI R, ULLMAN J D. Compilers: Principles, Techniques, and Tools[M]. Addison-Wesley Publishing, 2006.

[8] ZIEGLER S. Smaller faster table driven parser[EB/OL]. http://www.researchgate.net/publication/242522203_Smaller_faster_table_driven_parser. Unpublished manuscript. Madison Academic Computing Center, 1977.

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

[10] 劉燕兵, 劉萍, 譚建龍等. 基于存儲優(yōu)化的多模式串匹配算法[J].計算機研究與發(fā)展, 2009, 46(10): 1768-1776.LIU Y B, LIU P, TAN J L,et al. A multiple string matching algorithm based on memory optimization[J].Journal of Computer Research and Development,2009,46(10):1768-1776.

[11] NAVARRO G, RAFFINOT M. Fast and flexible string matching by combining bit-parallelism and suffix automata[J]. Experimental Algorithmics, 2000, 5(4): DOI:10.1145/351827.384246.

[12] Clam Antivirus, an anti virus detection software[EB/OL]. http://www.clamav.net/binary.html#pagestar.

[13] Free real network data for string matching test released by MIT[EB/OL].http://www.ll.mit.edu/IST/ideval/

[14] Snort, a free and open source network intrusion detection and prevention system[EB/OL]. http://www.snort.org/snort-rules/?#rules