一種基于分類存儲的空間高效Aho-Corasick算法

汪泓才 李訓根

(杭州電子科技大學電子信息學院 浙江 杭州 310018)

一種基于分類存儲的空間高效Aho-Corasick算法

汪泓才 李訓根

(杭州電子科技大學電子信息學院 浙江 杭州 310018)

針對經典Aho-Corasick算法存在空間開銷大，存儲效率低的問題，提出一種改進的空間高效Aho-Corasick算法。新算法在預處理階段根據狀態轉移函數、輸出函數的不同特性，靈活選擇不同的方式存儲狀態結點，實現對Aho-Corasick算法狀態機的壓縮。實驗表明，新算法與經典Aho-Corasick算法、Bitmapped AC算法相比，以匹配階段較小的時間性能為代價，極大幅度地壓縮狀態機的存儲空間。

AC算法 模式匹配 空間高效

0 引 言

Aho-Corasick(簡稱AC)算法是一種經典的多模式匹配算法，有著良好的時間復雜度，在許多領域得到了廣泛應用。AC算法的一個典型應用就是誤用入侵檢測。誤用入侵檢測，指的是通過監視網絡或計算機內部的流量數據，根據預先設定好的規則庫，用模式匹配算法深度檢測流量數據，判斷數據是否為惡意數據。入侵檢測系統的規則庫通常比較龐大。Snort是一個被廣泛使用的入侵檢測系統，它的規則庫就多達3 000余條。使用AC算法去匹配如此大量的規則庫，需要大量的空間開銷，更難以用硬件直接實現?；谶@種狀況，本文提出了一種分類存儲的AC算法，旨在降低算法的空間開銷。

1 AC算法介紹

AC算法分為預處理與匹配兩個階段，它在預處理階段構建一個有限狀態自動機，然后在匹配階段用狀態間的轉移操作取代字符比較操作，減少不必要的字符比較操作[1]。

預處理的對象是模式串集合，目的是構造有窮狀態自動機。在構造的狀態機中，每個狀態結點都有三個功能函數，分別是轉移函數goto、輸出函數output與失效函數failure[2]。如有模式串集合P={every, job, enjoy}，可以構建圖1所示的狀態機。

圖1 {every, job, enjoy}構建的狀態機

在圖1中，實線箭頭代表的轉移函數。轉移函數goto(src, c)= tar表示在狀態src輸入字符c，就轉移到狀態tar。在這里，狀態tar被稱為狀態src的轉移狀態。例如，當前狀態是圖1中的“state8”，輸入字符“o”，則當前狀態更新為“state9”。

圖1中的虛線箭頭代表的是失效函數。失效函數處理匹配過程中使用轉移函數失敗的情況。若狀態tar與狀態src滿足failure(src)= tar，即狀態tar是狀態src的供給狀態，則表示如果在狀態src輸入某個字符后無對應的轉移函數，就更新狀態為tar。例如，當前狀態是圖1中的“state8”，輸入字符“a”，無法使用轉移函數更新狀態，就必須使用失效函數更新狀態為“state11”。還需說明的是，在狀態機的構建中，狀態的默認供給狀態為初始狀態。為了簡潔起見，圖1沒有繪制這種默認的供給關系。

輸出函數output(s)={pattern}則意味著在狀態s匹配到了模式串pattern。

AC算法匹配階段的實現高效而簡潔，具體邏輯為：從狀態機的初始狀態出發，依次讀入被搜索文本的字符，根據讀入的字符，選擇使用轉移函數或失效函數更新狀態，如果使用了轉移函數更新為新的狀態，還需要檢查新的狀態是否有輸出，若有，則輸出的模式串就是被匹配的。

AC算法時間復雜度較低，即使同時匹配大量的模式串，搜索階段的時間開銷也比較穩定。另一方面，AC算法的空間開銷與模式串的總長度呈非線性正比的關系，這就使得在一些模式串總長度較長的場景，狀態機的空間占用過大[3]。

2 AC算法的存儲效率及其改進

在AC算法的狀態機中，每個狀態節點都需要存儲轉移函數、失效函數與輸出函數的信息。轉移函數的信息可以用表格保存，這張表格稱為轉移表。表1是圖1中“state1”的轉移表。在這張轉移表中，字符“n”與“v”的ASCII值為110與118，對應在轉移表中編號為110與118的項存儲goto(state1, “n”)與goto(state1, “v”)的值。對于“state1”，輸入除“n”與“v”以外的其他字符，都不存在相應的轉移函數，對應轉移表中其余項的值為一個特殊的無效值，用以表示使用轉移函數失敗。在表1中，這個無效值為“0”。

表1 “state1”的轉移表

轉移表通常用指針數組實現。在32位機中，存儲一張規模為256的轉移表需要使用1 024個字節。而在實際應用中，這張轉移表通常只有少數的幾個有效值。過多的無效值占據了大量的空間，造成了AC算法狀態機存儲效率低下。為了解決這一問題，已有大量的工作嘗試通過壓縮轉移函數信息以提高AC算法的存儲效率。

2.1 基于稀疏向量壓縮的改進

基于稀疏向量壓縮的思想，Norton提出了Banded-Row AC算法[4]。Banded-Row AC算法在AC算法的基礎上，壓縮了轉移表中首尾的無效值。Banded-Row格式的轉移表可以使用向量表示，“state1”對應的Banded-Row格式向量為{9, 110, state7, 0, 0, 0, 0, 0, 0, 0, state2}。這個向量分為三部分解讀。從第三個元素開始的內容，即“state7, 0, 0, 0, 0, 0, 0, 0, state2”，被稱為一個的“有效元素帶”。向量的第一個元素“9”表示這個“帶”的長度為9。向量第二個元素“110”表示這個“帶”首個元素在轉移表的第110項。按這種規則構造的Banded-Row格式向量用于替代轉移表，能夠顯著降低存儲需求。

Banded-Row AC算法能夠壓縮表中首尾的無效值，但是，每個Banded-row格式的向量只有一個“帶”，無法壓縮“帶”中間的無效值。Sparse-Bands AC算法解決了這一問題。Sparse-Bands格式的向量與Banded-Row格式的向量相似，但前者在構造時還加入一個策略：當“帶”中間連續的無效值個數超過指定的閾值，這個“帶”將被分成前后兩個“帶”。這就壓縮了轉移表中間的無效值。

徐紅等提出的雙重壓縮AC算法，在Sparse-Bands AC的基礎上做了進一步的改進[5]。雙重壓縮AC算法將狀態機所有N個狀態的轉移表視為一張N×256的矩陣。將矩陣中的全為0的列刪除，記入其對應的字符為未用字符，然后再對各行進行Sparse-Bands格式壓縮。在匹配時，每次使用轉移函數，需判斷輸入字符是否為未用字符，若是，則使用轉移函數失敗。

基于稀疏向量壓縮改進的算法相對于AC算法，存儲效率都有著明顯的提高，但在匹配階段，每次用到轉移函數，都需要額外的計算[6]。

2.2 位圖AC算法

同樣基于降低存儲開銷這一目的，Tuck等提出了位圖AC(BitmappedAC)算法[7]。圖2給出了位圖AC中狀態的存儲結構。位圖AC的狀態節點引入了位圖用以判斷輸入字符是否存在有效的轉移函數值，引入了結構數組用以存儲有效的轉移字符及對應的狀態結點地址。在位圖中，每一個位的值由轉移表中每一項的值一一映射得到。若轉移表中第k項為一個有效值，則位圖的第k位為“1”；否則，位圖的第k位為“0”。在匹配階段使用轉移函數，先檢查輸入字符對應位的位圖值是否為“1”。若是“1”，則從結構數組中讀取下一個狀態；若是“0”，則接下來調用失效函數。

圖2 位圖AC狀態機中狀態的存儲結構

位圖的引入降低了算法的存儲需求，提高了cache性能[8]，同時保持了轉移表隨機訪問的特性，在空間性能與時間性能之間取得了平衡。

3 基于分類存儲的AC算法

無論是AC算法，還是眾多基于AC提高存儲效率的改進算法，都使用了單一的方式存儲狀態結點。本文介紹一種分類存儲狀態結點的AC算法。該算法根據狀態機不同特性，靈活選擇不同的方式存儲狀態結點。尤為可貴的是，新算法不但能基于經典的AC算法改進，還能應用于Banded-RowAC、位圖AC等多種改進算法上，實現在這些算法的基礎上進一步提高空間存儲效率。

3.1 存儲方式

在AC狀態機中，大量的狀態節點沒有轉移狀態或者只有一個轉移狀態。對于這類狀態結點，如果直接存儲有效的轉移字符及對應轉移狀態的地址，能夠進一步降低狀態機的空間需求。

基于這種樸素的想法，新算法根據狀態的轉移函數有效值個數是否大于1這一條件，將狀態分為兩類。第一類狀態是轉移函數的有效值至少有2個的狀態，這一類狀態依舊采取原有的轉移表或位圖等方式存儲轉移函數的信息。第二類狀態是轉移函數有效值最多只有一個狀態，采用直接存儲有效的轉移字符nextChar與對應轉移狀態nextNode的方式記錄轉移函數信息。同時，將nextChar為“0”作為轉移函數有效值個數為0的標志。圖3展示了使用分類存儲后AC算法狀態存儲結構的變化。為了能夠在匹配階段識別狀態結點的存儲方式，還引入占用一個字節大小的標識符flag。

圖3 使用分類存儲后AC算法狀態存儲結構的變化

使用圖3展示的存儲結構，每次使用轉移函數或失效函數更新為新的狀態，都必須讀取標識符檢查狀態的存儲類型，存在額外的時間開銷。為了降低這一部分時間開銷，新算法還采用了兩個措施。

措施一是將原先的兩種存儲方式根據輸出函數值是否是空值，進一步細分為四種，若輸出函數值是空值，則不再存儲這一個空值。圖4展示了這四種存儲結構。措施一的引入保證了在匹配階段更新為第三類或第四類狀態時，可以直接通過讀取標識符判斷輸出函數為空值，減少使用輸出函數的次數。

圖4 采用措施一后狀態存儲結構的變化

措施二是供給狀態只能為第一類或第三類狀態。只有滿足轉移函數有效值個數不超過一個且不是供給狀態的狀態，才能歸為第二類或第四類狀態。這就保證了在匹配階段，使用失效函數更新為新狀態時，新狀態只可能為第一類或第三類狀態，無需重新讀取標志符識別當前狀態轉移函數的存儲方式。表2展示了采用措施二后四類狀態的使用條件。

表2 四類狀態的使用條件

上述兩個措施降低了使用分類存儲在匹配階段額外的時間開銷。相比于原算法，新算法在每次使用轉移函數到新狀態后，多了檢查存儲類型這一操作，但對于大多數無輸出的狀態，不再需要調用輸出函數。

分類存儲同樣可以應用于Banded-RowAC、Sparse-BandsAC、位圖AC等多種改進的AC算法上。要將新算法應用于這些改進的AC算法，只需要調整新算法中第一類與第三類狀態的轉移函數存儲方式。如將分類存儲應用于位圖AC算法上，就將第一類與第三類狀態中的轉移表替換為相應的位圖和結構數組，其余的存儲結構均保持不變。

3.2 預處理與匹配

新算法的狀態機可以在原有算法狀態機的基礎上構建。遍歷原有算法狀態機所有的狀態結點，根據表2所示的使用條件，重新建立相應類型的狀態結點，即可得到新算法的狀態機。

在匹配階段，從狀態機的初始狀態出發，依次讀入被搜索文本的字符。每次使用轉移函數更新狀態后，先檢查標識符，決定是否需要調用輸出函數以及如何調用轉移函數。轉移函數的使用有兩種方式，一是使用相應原算法的轉移方式，如轉移表，Banded-Row向量，位圖等；二是直接讀取nextChar，并嘗試轉移到nextNode。每次使用失效函數更新狀態后，不需要檢查標識符，直接嘗試使用轉移函數，若成功則轉移到下一狀態，若失敗則再次使用失效函數更新到下一狀態。

4 實驗與分析

為了證明基于分類存儲的AC算法在空間開銷方面的優勢，在同一臺計算機上進行實驗。實驗的對象共有四個，分別是經典AC算法、基于分類存儲的AC算法、位圖AC算法、基于分類存儲的位圖AC算法。將實驗對象分為2組進行對比，第一組是經典AC算法與基于分類存儲的AC算法，第二組是位圖AC算法與基于分類存儲的位圖AC算法。實驗從狀態機的存儲開銷與匹配階段時間開銷兩方面評估算法的性能。實驗的所有算法均用C++實現，在windows10運行，配置為Intel(R)Core(TM)i7 4700HQ2.4GHzCPU，8GB內存。

實驗的第一部分是測試狀態機的存儲空間大小。使用四種算法預處理Snort2.9規則集中的3348條模式串，分別建立狀態機。圖5展示了四種算法建立的狀態機的存儲空間。狀態機的存儲空間為構造完狀態機后使用內存與未構造狀態機前使用內存之差。實驗結果顯示，在經典AC算法與位圖AC算法上使用分類存儲，狀態機的空間僅為原來的14.9%與36.7%。

圖5 狀態機存儲開銷的對比

實驗的第二部分是測試四種算法的匹配速度。被匹配的文本是來源于互聯網的10MB英文文本。直接使用實驗一中的4個狀態機對文本各進行5次匹配，取平均值為最終的測試數據。四種狀態機匹配用時如圖6所示。使用分類存儲后的AC算法與位圖AC算法，匹配階段用時平均增加8.3%和7.9%。

圖6 匹配階段時間開銷的對比

實驗結果表明，基于分類存儲的AC算法相對于經典AC算法，以匹配階段用時增加8.3%的代價，將狀態機的空間開銷減少為原來的14.9%。即使是在空間高效的位圖AC算法上使用分類存儲，依舊能以匹配階段用時增加7.9%的代價，將狀態機的空間開銷減少為原來的36.7%。

5 結 語

基于分類存儲的AC算法，與前人的位圖AC，Banded-RowAC等算法的目的相同，都旨在于提高狀態機的存儲效率。但相比這些算法，基于分類存儲的AC算法的優勢在于它的第一類狀態與第三類狀態能靈活選用轉移表，位圖或Banded-Row向量等方式存儲轉移函數的信息，實現在這些算法的基礎上進一步降低存儲開銷。但是，在當前實現的算法中，分類存儲的方式還比較簡單，選用存儲方式的條件也是固定的，還可以進一步引入其他的存儲方式，并系統性地調整選取不同存儲方式的條件，評估不同方式下的時間性能與空間性能。這將是下一步工作的方向。

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

[2] Navarro G,Raffinot M.Flexible pattern matching in strings:practical on-line search algorithms for texts and biological sequences[M].New York,NY,USA:Cambridge University Press,2002:221.

[3] 王培鳳,李莉.基于Aho-Corasick算法的多模式匹配算法研究[J].計算機應用研究,2011,28(4):1251-1253,1259.

[4] Norton M.Optimizing pattern matching for intrusion detection[R].Columbia,MD,USA:Sourcefire Inc,2004.

[5] 徐紅,秦志光.一種面向入侵檢測的改進AC算法[J].微電子學與計算機,2010,27(11):109-112.

[6] 董世博,李訓根,殷珍珍.一種改進的字符串多模式匹配算法[J].計算機工程與應用,2013,49(8):133-137.

[7] Tuck N,Sherwood T,Calder B,et al.Deterministic memory-efficient string matching algorithms for intrusion detection[C]//Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies.IEEE,2004:2628-2639.

[8] Wen Y,Chen Z,Ma G,et al.SECOMPAX:a bitmap index compression algorithm[C]//Computer Communication and Networks (ICCCN),2014 23rd International Conference on.IEEE,2014:1-7.

A SPACE-EFFICIENT AHO-CORASICK ALGORITHM BASED ON CLASSIFICATION STORAGE

Wang Hongcai Li Xungen

(SchoolofElectronicsandInformation,HangzhouDianziUniversity,Hangzhou310018,Zhejiang,China)

Aiming at the problem that the classical Aho-Corasick algorithm has large space overhead and low storage efficiency, an improved space-efficient Aho-Corasick algorithm is proposed. In the preprocessing stage, the new algorithm chooses different storage state nodes flexibly according to the different characteristics of the state transfer function and the output function, and achieves the compression of the Aho-Corasick algorithm state machine. Experiments show that compared with the classical Aho-Corasick algorithm and Bitmapped AC algorithm, the new algorithm can greatly reduce the storage space of the state machine at the cost of matching small time performance.

Aho-Corasick algorithm Pattern matching Space-efficient

2016-04-05。汪泓才，碩士生，主研領域：模式匹配。李訓根，副教授。

TP301

A

10.3969/j.issn.1000-386x.2017.05.048