深度報文檢測基礎之AC演算法

05-09

說到DPI-深度包檢測引擎，離不開多模式匹配的AC演算法（aho-corasick）。與經典的單模式匹配演算法KMP演算法不同，AC演算法提供了一個匹配效率與模式串多少無關，只與被檢測字元串長度相關的匹配辦法。這對報文檢測來說有一個極大的好處，即：不需要回退搜索，一次掃描就可以查找出目標串中所有的模式串。

AC演算法涉及到三個重要的概念：字典樹；失敗態；狀態映射。

字典樹：即前綴樹，有相同前綴的模式串公用相同的前綴。構造方法如下：

1 在沒有模式串加入到AC樹上時，樹只有一個根節點root。給根節點賦予狀態0；

2 在加入第一個模式串時，根節點上沒有子節點，新建一個子節點，賦予狀態1。狀態之間的關係滿足link(0,1) = p1[0]。即根節點到第一個子節點的邊是模式串p1的第一個字元。繼續增加節點，賦予新的狀態。直到模式串p1的最後一個字元添加到樹中，記錄最後節點的狀態s，標記為終結點。

3 添加第二個模式串，從根節點開始，如果有link(0,1) = p2[0]，則往下走，判斷是否有關係 link(1,2) = p2[0]，如果link(0,1) != p2[0]，則新建節點，狀態為s+1。依次將剩下的字元添加到樹中。

4 重複3，將剩下的模式串添加到樹中。

失敗態：也叫失敗態映射，就是說在匹配過程中遇到不匹配的字元後應該跳轉的哪個狀態繼續進行匹配。為了減少重複性的匹配工作，要想辦法利用模式串的共同前綴部分，即在已匹配完成的字元串後綴中找一個最大的後綴，這個後綴正好是其他模式串的一個前綴。為了達到這個目的，我們定義失敗態：

1 根節點和它所有的子節點，即層為1的節點的失敗態都是0；

2 除1以外，若節點s的父節點father(s)的失敗態failure (father(s))節點存在子節點child(i)，滿足link(father(s),child(i)) = link(father(s), s)，則s的失敗態節點就是child(i)。

狀態映射：在完成字典樹（AC樹）和失敗態計算後，整個樹上，從任意一個節點出發，輸入任意一個字元，都可以跳轉到另外一個節點。最終形成一個二元映射關係：|S|*|C|->|S|。我們將這個完整的二元映射表稱之為DFA(Deterministic Finite Automata)，中文叫做確定性有窮自動狀態機。與之相對應的叫做NFA(Nondeterminisic Finite Automata)，叫做非確定性有限自動狀態機。

在AC樹建立好，完整的狀態映射表計算好之後，就可以針對被匹配報文進行匹配了。匹配過程如下：

for (pBuff = pStart; pBuff < pEnd; pBuff++){ State = S[State][*pBuff]; if (State is Terminal) { record the signature; }}

匹配過程代碼非常簡單。