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

汪泓才 李訓根

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

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

汪泓才 李訓根

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

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

AC算法 模式匹配 空間高效

0 引 言

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

1 AC算法介紹

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

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

圖1 {every, job, enjoy}構(gòu)建的狀態(tài)機

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

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

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

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

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

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

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

表1 “state1”的轉(zhuǎn)移表

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

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

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

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

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

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

2.2 位圖AC算法

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

圖2 位圖AC狀態(tài)機中狀態(tài)的存儲結(jié)構(gòu)

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

3 基于分類存儲的AC算法

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

3.1 存儲方式

在AC狀態(tài)機中，大量的狀態(tài)節(jié)點沒有轉(zhuǎn)移狀態(tài)或者只有一個轉(zhuǎn)移狀態(tài)。對于這類狀態(tài)結(jié)點，如果直接存儲有效的轉(zhuǎn)移字符及對應(yīng)轉(zhuǎn)移狀態(tài)的地址，能夠進一步降低狀態(tài)機的空間需求。

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

圖3 使用分類存儲后AC算法狀態(tài)存儲結(jié)構(gòu)的變化

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

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

圖4 采用措施一后狀態(tài)存儲結(jié)構(gòu)的變化

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

表2 四類狀態(tài)的使用條件

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

分類存儲同樣可以應(yīng)用于Banded-RowAC、Sparse-BandsAC、位圖AC等多種改進的AC算法上。要將新算法應(yīng)用于這些改進的AC算法，只需要調(diào)整新算法中第一類與第三類狀態(tài)的轉(zhuǎn)移函數(shù)存儲方式。如將分類存儲應(yīng)用于位圖AC算法上，就將第一類與第三類狀態(tài)中的轉(zhuǎn)移表替換為相應(yīng)的位圖和結(jié)構(gòu)數(shù)組，其余的存儲結(jié)構(gòu)均保持不變。

3.2 預(yù)處理與匹配

新算法的狀態(tài)機可以在原有算法狀態(tài)機的基礎(chǔ)上構(gòu)建。遍歷原有算法狀態(tài)機所有的狀態(tài)結(jié)點，根據(jù)表2所示的使用條件，重新建立相應(yīng)類型的狀態(tài)結(jié)點，即可得到新算法的狀態(tài)機。

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

4 實驗與分析

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

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

圖5 狀態(tài)機存儲開銷的對比

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

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

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

5 結(jié) 語

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

[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].計算機應(yīng)用研究,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].計算機工程與應(yīng)用,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。汪泓才，碩士生，主研領(lǐng)域：模式匹配。李訓根，副教授。

TP301

A

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