自動機概況

使用Linux開發環境的程序員一定使用過sed、grep、lex等Linux系統工具，sed、grep是Linux中重要的數據流搜索與處理工具，Lex是linux下廣泛使用的詞法分析器生成器，用于復雜語言的解析、編譯器前端的開發等。盡管這些Linux系統工具功能各異，但這些工具內部都實現了一個自動機，用于對輸入預料進行基于正則表達式的文本搜索。自動機則是正則表達式的等價實現。

從計算理論上講，正則表達式與自動機具有理論上的嚴格等價性，正則表達式和自動機具有等價的對匹配模式的定義能力。正則表達式是匹配模式的形式化表達，自動機則是對匹配模式的計算機實現的一種表達。

安全檢測與防護領域的入侵檢測系統(Intrusion Detection Systems,IDS)、入侵防護系統(Intrusion Prevention System, IPS)、web應用防火墻(Web Application Firewall,WAF)等都大量應用了自動機技術進行網絡數據流的正則表達式匹配，以實現對網絡報文的檢測與分析。

IPS/IDS與WAF系統

自動機技術也廣泛應用于DPI系統(Deep Packet Inspection,DPI)中，以實現對網絡報文的解析與識別。

應用于應用識別的DPI系統

2、正則表達式與自動機

2.1 初識正則表達式與自動機

在形式化語言與自動機理論中，正則表達式與有窮自動機有著理論上的嚴格等價性。

正則表達式與自動機的等價性

自動機分為確定型有窮自動機(Deterministic Finite Automata，DFA)和非確定型有窮自動機(Non-Deterministic Finite Automata，NFA)。確定型有窮自動機中，對于給定的確定狀態與確定輸入，其狀態轉移關系是確定唯一的，且每一時刻只存在一個激活狀態。相反，在非確定型有窮自動機中，對于給定的確定狀態與確定輸入，其可能存在多個狀態轉移關系，且某一時刻可能存在多個的激活狀態。非確定型有窮自動機又主要分為存在epsilon轉移的epsilon-NFA與沒有epsilon轉移的NFA，其經典代表分別為Thompson NFA與Gluskov NFA。

Thompson NFA

上圖所示為識別正則表達式(AB|CD)*AFF*的Thompson NFA，可見thompson NFA由基本的子正則表達式NFA單元通過epsilon邊連接而成，epsilon邊連接的兩個狀態可以由空字符進行轉移，即存在無條件的狀態轉移關系，由字母標識的邊連接的兩個狀態表明這兩個狀態之間需要輸入對應的字符才能進行激活狀態的轉移。

Gluskov NFA

上圖所示為識別正則表達式(AB|CD)*AFF*的Gluskov NFA。顯而易見，Gluskov NFA比Thompson NFA要簡潔很多，且Glukov NFA中NFA的狀態數與正則表達式中出現的字符和字符集總數一致。相比于Thompson NFA，Gluskov NFA狀態數更少，結構更緊湊。同時在Gluskov NFA中，狀態之間的跳轉條件被移到了節點內變成了節點的激活條件，因此Gluskov NFA的運行時處理也會變得更加簡單。在運行時讀入一個字符c時，便可知道字符c可以激活的狀態集reach(c)，那么只需在Gluskov NFA當前的激活狀態集s的基礎上計算其后繼狀態集succ(s)，并取reach(c)與succ(s)的交集，所得的交集即為Gluskov NFA的下一刻激活狀態集。對于Thompson NFA，節點的激活條件并不唯一，且需要處理epsilon邊連接的狀態轉移關系，其下一刻的激活狀態集的計算會更復雜。

對Thompson NFA或Gluskov NFA使用子集構造算法，可以將NFA轉化為DFA。DFA相較于NFA最大的優勢是性能，而劣勢在于空間開銷，這是因為DFA狀態轉移的確定性是通過對NFA不同狀態進行組合得到的，因此功能等價的DFA和NFA從理論上來說，DFA狀態數的上限是NFA狀態數的指數關系。

DFA狀態圖

上圖所示為使用子集構造算法將識別正則表達式(AB|CD)*AFF*的thompson NFA轉化為DFA后的狀態圖。圖中每個藍色框的序號集中的序號對應于thompson NFA中狀態的序號，體現了DFA中的每個狀態對應于NFA狀態集的一個子集。

2.2 主流的開源自動機相關庫

目前廣泛使用的主流開源自動機相關庫主要是Pcre、RE2、Hyperscan：

• Pcre支持的正則表達式語法是最全最復雜的，但PCRE只支持塊模式編譯和匹配，并且只支持單條正則表達式的編譯和匹配，性能在這三款軟件中是最差的。對于需要進行大規模正則規則并行匹配的場景，pcre就顯得力不從心了。
• Google的開源正則匹配引擎RE2是基于虛擬機方法c++實現的一款快速、安全、線程友好的正則匹配自動機，支持的正則表達式語法比pcre少但比hyperscan多。RE2支持少量正則規則集的并行匹配，不支持只能用回溯算法實現的正則表達式語法。
• Hyperscan是Intel開源的一款基于正則表達式NFA/DFA圖分析與拆解的高性能正則表達式混合自動機。在這三款軟件中，hyperscan支持的正則語法最少，但其性能是最強的，且支持大規模正則規則集的并行匹配。

3、自動機的性能優化實踐

正則表達式的匹配速率是制約IDS/IPS、WAF、DPI等業務的重要性能瓶頸。提升正則表達式自動機的匹配性能是提升以上業務能力的關鍵所在，下面介紹自動機性能優化的幾種主流方法。

3.1 基于預過濾的性能優化

基于預過濾的正則表達式優化策略

上圖所示為基于字符串匹配器預過濾的正則表達式匹配優化策略。該方案會在正則表達式的編譯過程中提取正則表達式中的字符串信息，并根據提取的字符串構建一個多字符串預匹配器。如針對規則0，提取了字符串SEARCH，針對規則N提取了字符串SUBSCRIBE。在對輸入預料進行匹配的過程中，會先使用多字符串匹配器進行字符串的匹配，若匹配過程中匹配到了字符串SERACH但是沒有匹配到字符串SUBCRIBE，則會進一步使用根據正則表達式規則0構建的自動機進行第二階段的正則表達式匹配。可見基于預過濾的正則表達式匹配方案為一個兩階段的匹配過程。

基于字符串匹配器的預過濾正則表達式匹配方案雖然能提早過濾掉無法匹配的語料。但仍然存在以下的諸多不足：

（1）對正則表達式中的字符串存在重復匹配，即預過濾的字符串匹配組件匹配一次字符串，自動機又重復匹配一次字符串；

（2）基于預過濾的匹配方案中的第二階段，使用自動機對字符串進行匹配難以有效地使用CPU的SIMD指令集進行字符串匹配的并行加速；

（3）不合理的關鍵字符串選擇容易拖累整體正則表達式的匹配性能。

針對基于字符串匹配器預過濾的正則表達式匹配方案的不足，一種更新穎有效的基于正則表達式分解的正則表達式匹配方案便應運而生了。

3.2 基于正則表達式分解的性能優化

基于正則表達式分解的正則表達式匹配方案首先會將正則表達式拆解成幾個子字符串和子正則表達式。拆解的子字符串會被構建為一個字符串匹配器（字符串匹配器可以有效地使用CPU的SIMD指令集進行并行加速，相比于使用自動機匹進行字符串配具有數量級上的性能優勢），而拆解的子正則表達式則會被構建為一個子自動機，如NFA或DFA。在對輸入語料進行正則表達式匹配時，該方案會按照一定順序調用各個匹配器，并盡量優先調用字符串匹配器進行字符串的匹配，只有當前一個匹配器匹配成功后才會調用下一個匹配器進行匹配，并且只有當所有的匹配器都按照既定的順序匹配成功后，整條拆解的正則表達式才真正匹配成功。

基于規則拆分的正則表達式匹配策略

上圖所示為使用拆解后的正則表達式.*start[^x]comA+匹配輸入字符串AstarZcomA的一個示例。首先，正則表達式被拆解為五個部分，分別對應于自動機部分FA2、FA1、FA0與字符串部分STR2、STR1。拆解后構造的各個子自動機與子字符串匹配器的匹配順序為STR1->STR2->FA1->FA0->FA2。拆解后構造的各個子自動機與子字符串遵循一下的優先級原則：

• 字符串匹配優先于自動機匹配。
• 兩個字符串中間的自動機匹配優先于其它位置的自動機匹配。
• 匹配語料尾部的自動機優先于匹配語料頭部的自動機。

第一條優先級原則很好理解，在于字符串匹配速率相對于自動機匹配速率有著數量級上的性能優勢。兩個字符串之間的自動機所需匹配的語料的行首和行尾是錨定的，因此它的優先級相對于其它自動機優先級較高，即優先級原則2。由于匹配語料尾部的自動機其匹配的行首是錨定的無需回溯操作，所以其優先級較高，即優先級原則3。可見，拆解后的各子自動機與子字符串匹配器的匹配順序原則上遵循：性能開銷越小的匹配過程，其匹配順序越靠前。

對于輸入語料，AstarZcomA，首先會使用字符串匹配器匹配字符串STR1，此時字符串匹配成功，繼續調用字符串匹配器匹配字符串STR2，此時字符串STR2匹配失敗，則不再使用后續的FA1、FA0、FA2進行匹配。若輸入的字符串為AstartZcomA，則會依次成功匹配STR1、STR2、FA1、FA0、FA2，最后輸出匹配成功信息。

4、正則規則匹配的應用思考

在互聯網領域的各種開發與應用中，網絡進攻檢測、應用流量識別等大量的場景需要使用正則引擎進行正則表達式的匹配。正則表達式的匹配效率不僅取決于使用的正則引擎的性能好壞，也與書寫的正則表達式形式息息相關。揭秘正則引擎的實現原理能讓我們更深入了解正則表達式的形式與正則引擎效率的相關性，更好地指導我們進行正則引擎的性能調優。以下原則的正則表達式書寫指導意見能幫助我們在開發與應用過程中更高效地進行正則表達式的匹配：

1. 盡量避免使用需要用回溯方法實現的正則表達式語法，如反向引用語法。回溯的引入會使最壞情況下正則匹配的時間復雜度呈指數的增長。
2. 盡量在正則表達式中避免(.*)、{min,max}這樣的語法，(.*)引入的不確定性以及{min,max}帶來的有界重復是正則表達式引擎的重要性能瓶頸。
3. 盡量將正則表達式寫得更確定，如盡量在正則表達式中寫更多確定的字符或字符串。