自動(dòng)機(jī)概況

使用Linux開發(fā)環(huán)境的程序員一定使用過sed、grep、lex等Linux系統(tǒng)工具，sed、grep是Linux中重要的數(shù)據(jù)流搜索與處理工具，Lex是linux下廣泛使用的詞法分析器生成器，用于復(fù)雜語言的解析、編譯器前端的開發(fā)等。盡管這些Linux系統(tǒng)工具功能各異，但這些工具內(nèi)部都實(shí)現(xiàn)了一個(gè)自動(dòng)機(jī)，用于對(duì)輸入預(yù)料進(jìn)行基于正則表達(dá)式的文本搜索。自動(dòng)機(jī)則是正則表達(dá)式的等價(jià)實(shí)現(xiàn)。

從計(jì)算理論上講，正則表達(dá)式與自動(dòng)機(jī)具有理論上的嚴(yán)格等價(jià)性，正則表達(dá)式和自動(dòng)機(jī)具有等價(jià)的對(duì)匹配模式的定義能力。正則表達(dá)式是匹配模式的形式化表達(dá)，自動(dòng)機(jī)則是對(duì)匹配模式的計(jì)算機(jī)實(shí)現(xiàn)的一種表達(dá)。

安全檢測(cè)與防護(hù)領(lǐng)域的入侵檢測(cè)系統(tǒng)(Intrusion Detection Systems,IDS)、入侵防護(hù)系統(tǒng)(Intrusion Prevention System, IPS)、web應(yīng)用防火墻(Web Application Firewall,WAF)等都大量應(yīng)用了自動(dòng)機(jī)技術(shù)進(jìn)行網(wǎng)絡(luò)數(shù)據(jù)流的正則表達(dá)式匹配，以實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)報(bào)文的檢測(cè)與分析。

IPS/IDS與WAF系統(tǒng)

自動(dòng)機(jī)技術(shù)也廣泛應(yīng)用于DPI系統(tǒng)(Deep Packet Inspection,DPI)中，以實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)報(bào)文的解析與識(shí)別。

應(yīng)用于應(yīng)用識(shí)別的DPI系統(tǒng)

2、正則表達(dá)式與自動(dòng)機(jī)

2.1 初識(shí)正則表達(dá)式與自動(dòng)機(jī)

在形式化語言與自動(dòng)機(jī)理論中，正則表達(dá)式與有窮自動(dòng)機(jī)有著理論上的嚴(yán)格等價(jià)性。

正則表達(dá)式與自動(dòng)機(jī)的等價(jià)性

自動(dòng)機(jī)分為確定型有窮自動(dòng)機(jī)(Deterministic Finite Automata，DFA)和非確定型有窮自動(dòng)機(jī)(Non-Deterministic Finite Automata，NFA)。確定型有窮自動(dòng)機(jī)中，對(duì)于給定的確定狀態(tài)與確定輸入，其狀態(tài)轉(zhuǎn)移關(guān)系是確定唯一的，且每一時(shí)刻只存在一個(gè)激活狀態(tài)。相反，在非確定型有窮自動(dòng)機(jī)中，對(duì)于給定的確定狀態(tài)與確定輸入，其可能存在多個(gè)狀態(tài)轉(zhuǎn)移關(guān)系，且某一時(shí)刻可能存在多個(gè)的激活狀態(tài)。非確定型有窮自動(dòng)機(jī)又主要分為存在epsilon轉(zhuǎn)移的epsilon-NFA與沒有epsilon轉(zhuǎn)移的NFA，其經(jīng)典代表分別為Thompson NFA與Gluskov NFA。

Thompson NFA

上圖所示為識(shí)別正則表達(dá)式(AB|CD)*AFF*的Thompson NFA，可見thompson NFA由基本的子正則表達(dá)式NFA單元通過epsilon邊連接而成，epsilon邊連接的兩個(gè)狀態(tài)可以由空字符進(jìn)行轉(zhuǎn)移，即存在無條件的狀態(tài)轉(zhuǎn)移關(guān)系，由字母標(biāo)識(shí)的邊連接的兩個(gè)狀態(tài)表明這兩個(gè)狀態(tài)之間需要輸入對(duì)應(yīng)的字符才能進(jìn)行激活狀態(tài)的轉(zhuǎn)移。

Gluskov NFA

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

對(duì)Thompson NFA或Gluskov NFA使用子集構(gòu)造算法，可以將NFA轉(zhuǎn)化為DFA。DFA相較于NFA最大的優(yōu)勢(shì)是性能，而劣勢(shì)在于空間開銷，這是因?yàn)镈FA狀態(tài)轉(zhuǎn)移的確定性是通過對(duì)NFA不同狀態(tài)進(jìn)行組合得到的，因此功能等價(jià)的DFA和NFA從理論上來說，DFA狀態(tài)數(shù)的上限是NFA狀態(tài)數(shù)的指數(shù)關(guān)系。

DFA狀態(tài)圖

上圖所示為使用子集構(gòu)造算法將識(shí)別正則表達(dá)式(AB|CD)*AFF*的thompson NFA轉(zhuǎn)化為DFA后的狀態(tài)圖。圖中每個(gè)藍(lán)色框的序號(hào)集中的序號(hào)對(duì)應(yīng)于thompson NFA中狀態(tài)的序號(hào)，體現(xiàn)了DFA中的每個(gè)狀態(tài)對(duì)應(yīng)于NFA狀態(tài)集的一個(gè)子集。

2.2 主流的開源自動(dòng)機(jī)相關(guān)庫

目前廣泛使用的主流開源自動(dòng)機(jī)相關(guān)庫主要是Pcre、RE2、Hyperscan：

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

3、自動(dòng)機(jī)的性能優(yōu)化實(shí)踐

正則表達(dá)式的匹配速率是制約IDS/IPS、WAF、DPI等業(yè)務(wù)的重要性能瓶頸。提升正則表達(dá)式自動(dòng)機(jī)的匹配性能是提升以上業(yè)務(wù)能力的關(guān)鍵所在，下面介紹自動(dòng)機(jī)性能優(yōu)化的幾種主流方法。

3.1 基于預(yù)過濾的性能優(yōu)化

基于預(yù)過濾的正則表達(dá)式優(yōu)化策略

上圖所示為基于字符串匹配器預(yù)過濾的正則表達(dá)式匹配優(yōu)化策略。該方案會(huì)在正則表達(dá)式的編譯過程中提取正則表達(dá)式中的字符串信息，并根據(jù)提取的字符串構(gòu)建一個(gè)多字符串預(yù)匹配器。如針對(duì)規(guī)則0，提取了字符串SEARCH，針對(duì)規(guī)則N提取了字符串SUBSCRIBE。在對(duì)輸入預(yù)料進(jìn)行匹配的過程中，會(huì)先使用多字符串匹配器進(jìn)行字符串的匹配，若匹配過程中匹配到了字符串SERACH但是沒有匹配到字符串SUBCRIBE，則會(huì)進(jìn)一步使用根據(jù)正則表達(dá)式規(guī)則0構(gòu)建的自動(dòng)機(jī)進(jìn)行第二階段的正則表達(dá)式匹配?？梢娀陬A(yù)過濾的正則表達(dá)式匹配方案為一個(gè)兩階段的匹配過程。

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

（1）對(duì)正則表達(dá)式中的字符串存在重復(fù)匹配，即預(yù)過濾的字符串匹配組件匹配一次字符串，自動(dòng)機(jī)又重復(fù)匹配一次字符串；

（2）基于預(yù)過濾的匹配方案中的第二階段，使用自動(dòng)機(jī)對(duì)字符串進(jìn)行匹配難以有效地使用CPU的SIMD指令集進(jìn)行字符串匹配的并行加速；

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

針對(duì)基于字符串匹配器預(yù)過濾的正則表達(dá)式匹配方案的不足，一種更新穎有效的基于正則表達(dá)式分解的正則表達(dá)式匹配方案便應(yīng)運(yùn)而生了。

3.2 基于正則表達(dá)式分解的性能優(yōu)化

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

基于規(guī)則拆分的正則表達(dá)式匹配策略

上圖所示為使用拆解后的正則表達(dá)式.*start[^x]comA+匹配輸入字符串AstarZcomA的一個(gè)示例。首先，正則表達(dá)式被拆解為五個(gè)部分，分別對(duì)應(yīng)于自動(dòng)機(jī)部分FA2、FA1、FA0與字符串部分STR2、STR1。拆解后構(gòu)造的各個(gè)子自動(dòng)機(jī)與子字符串匹配器的匹配順序?yàn)镾TR1->STR2->FA1->FA0->FA2。拆解后構(gòu)造的各個(gè)子自動(dòng)機(jī)與子字符串遵循一下的優(yōu)先級(jí)原則：

• 字符串匹配優(yōu)先于自動(dòng)機(jī)匹配。
• 兩個(gè)字符串中間的自動(dòng)機(jī)匹配優(yōu)先于其它位置的自動(dòng)機(jī)匹配。
• 匹配語料尾部的自動(dòng)機(jī)優(yōu)先于匹配語料頭部的自動(dòng)機(jī)。

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

對(duì)于輸入語料，AstarZcomA，首先會(huì)使用字符串匹配器匹配字符串STR1，此時(shí)字符串匹配成功，繼續(xù)調(diào)用字符串匹配器匹配字符串STR2，此時(shí)字符串STR2匹配失敗，則不再使用后續(xù)的FA1、FA0、FA2進(jìn)行匹配。若輸入的字符串為AstartZcomA，則會(huì)依次成功匹配STR1、STR2、FA1、FA0、FA2，最后輸出匹配成功信息。

4、正則規(guī)則匹配的應(yīng)用思考

在互聯(lián)網(wǎng)領(lǐng)域的各種開發(fā)與應(yīng)用中，網(wǎng)絡(luò)進(jìn)攻檢測(cè)、應(yīng)用流量識(shí)別等大量的場(chǎng)景需要使用正則引擎進(jìn)行正則表達(dá)式的匹配。正則表達(dá)式的匹配效率不僅取決于使用的正則引擎的性能好壞，也與書寫的正則表達(dá)式形式息息相關(guān)。揭秘正則引擎的實(shí)現(xiàn)原理能讓我們更深入了解正則表達(dá)式的形式與正則引擎效率的相關(guān)性，更好地指導(dǎo)我們進(jìn)行正則引擎的性能調(diào)優(yōu)。以下原則的正則表達(dá)式書寫指導(dǎo)意見能幫助我們?cè)陂_發(fā)與應(yīng)用過程中更高效地進(jìn)行正則表達(dá)式的匹配：

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