ac自動機

說到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;    }}

匹配過程程式碼非常簡單。