基于距離比較的AC自動機(jī)并行匹配算法

姜海洋 李雪菲 楊 曄

①(中國科學(xué)院計(jì)算技術(shù)研究所 北京 100190)

②(中國科學(xué)院大學(xué) 北京 100049)

③(江蘇省未來網(wǎng)絡(luò)創(chuàng)新研究院 南京 211111)

1 引言

深度包監(jiān)測(Deep Packet Inspection, DPI)引擎通常采用多模式匹配算法(Multi-Pattern Matching,MPM)，在數(shù)據(jù)包中查找多個(gè)模式串的方式來判定數(shù)據(jù)包的合法性。DPI引擎是網(wǎng)絡(luò)安全設(shè)備的核心模塊和系統(tǒng)的性能瓶頸[1]。隨著網(wǎng)絡(luò)流量的增長，DPI面臨嚴(yán)峻的性能挑戰(zhàn)，對網(wǎng)絡(luò)流量進(jìn)行分割，利用多線程的方式進(jìn)行并行處理，成為提高匹配性能的重要手段。

根據(jù)負(fù)載劃分的粒度不同，數(shù)據(jù)包并行處理方法可分為基于流(flow)、基于數(shù)據(jù)包和基于數(shù)據(jù)包分片3種。由于互聯(lián)網(wǎng)流量分布具有不均衡性和局部性，基于數(shù)據(jù)包或者流的負(fù)載均衡方法難以保證并行任務(wù)間的均衡[2-4]?；跀?shù)據(jù)包分片的方法雖然可以保證任務(wù)均衡，卻存在分割點(diǎn)漏判問題：當(dāng)模式串橫跨多個(gè)數(shù)據(jù)包分片時(shí)，這種并行方法將無法檢測到這些模式串?，F(xiàn)有方法通過冗余檢測來解決這個(gè)漏判問題：在每個(gè)分片后面，都存在一個(gè)冗余檢測區(qū)域，該區(qū)域會被前后兩個(gè)MPM線程檢測，從而保證檢測到所有的模式串。顯然，冗余檢測加重了引擎的處理負(fù)擔(dān)，引入了線程間的同步開銷[5]。

針對上述問題，本文提出了一種高效的數(shù)據(jù)包分割和并行匹配算法-距離比較并行匹配算法(Distance Comparison Parallel Matching,DCPM)：進(jìn)入冗余檢測區(qū)域后，DCPM線程在處理每個(gè)字符時(shí)，根據(jù)該字符距離分割點(diǎn)的長度是否大于自動機(jī)當(dāng)前狀態(tài)的深度，來判斷是否可以結(jié)束冗余檢測。DCPM算法消除了數(shù)據(jù)包分割造成的線程同步開銷，大幅度降低了冗余檢測開銷。

本文首先簡單介紹多模式字符串匹配算法AC(Aho-Corasick)算法，以及目前已有的基于數(shù)據(jù)包分片的并行匹配算法；第2節(jié)詳細(xì)描述了DCPM算法的工作過程，并結(jié)合實(shí)例對算法進(jìn)行了進(jìn)一步的說明；第3節(jié)對算法進(jìn)行理論分析，證明DCPM算法的正確性；最后在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集兩種場景下，對DCPM算法和已有算法的性能差異進(jìn)行評估，實(shí)驗(yàn)結(jié)果表明采用DCPM算法后，多模式匹配性能有顯著提升：當(dāng)處理真實(shí)數(shù)據(jù)集時(shí)，性能獲得1.3～3.5倍提升。

2 相關(guān)工作

2.1 Aho-Corasick算法

Aho-Corasick(AC)算法是廣泛使用的多模式匹配算法，算法通過構(gòu)建表示一組模式串的自動機(jī)來進(jìn)行匹配查詢：自動機(jī)根據(jù)輸入的字符串逐字節(jié)進(jìn)行狀態(tài)跳轉(zhuǎn)，直到完成整個(gè)輸入的檢測。算法的時(shí)間復(fù)雜度只與輸入數(shù)據(jù)的長度有關(guān)[6]。

圖1 模式串集合{he, she, his, hers}對應(yīng)的DFA

圖1是模式串集合{he, she, his, hers}對應(yīng)的確定有限自動機(jī)(Deterministic Finite Automaton，DFA)。該自動機(jī)有10個(gè)節(jié)點(diǎn)，對應(yīng)了10個(gè)可跳轉(zhuǎn)狀態(tài)，節(jié)點(diǎn)間的邊以及邊上的字符，表示狀態(tài)間的跳轉(zhuǎn)關(guān)系和條件。例如當(dāng)前狀態(tài)為s5，如果下一個(gè)輸入的字符是“s”，則跳轉(zhuǎn)到s6。圖1的自動機(jī)有4個(gè)可接受狀態(tài)(accepting state)s2,s4,s6和s9，分別對應(yīng)集合中的4個(gè)模式串，當(dāng)狀態(tài)機(jī)跳轉(zhuǎn)到這4個(gè)狀態(tài)時(shí)，表示在待匹配串中檢測到對應(yīng)的模式串。

假設(shè)輸入串為{s-h-e}，從s0開始依次跳轉(zhuǎn)至狀態(tài)s7,s8和s9，而s9為一個(gè)可接受狀態(tài)，說明在輸入串中檢測到了模式串(he和she)。

將鏈接根節(jié)點(diǎn)到狀態(tài)節(jié)點(diǎn)s的一系列輸入字符表示為與s相關(guān)的一個(gè)后綴標(biāo)記L(s)，定義節(jié)點(diǎn)s在AC狀態(tài)機(jī)中的深度為標(biāo)記L(s)的長度，如L(s1),L(s7)長度為1，表示s1和s7的深度為1。

已有工作已經(jīng)證明，AC自動機(jī)具有下面的幾個(gè)性質(zhì)[6,7]：

(1)AC自動機(jī)中，各個(gè)狀態(tài)si對應(yīng)的標(biāo)記L(si)是唯一的。

(2)用{b0,b1,...,bi,...,bn}表示輸入字符序列，用{s0,s1,...,si,...,sn}表示對應(yīng)的AC狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換序列(s0為根節(jié)點(diǎn))。對任意i∈{1,2,...,n}，L(si)都是{b0,b1,...,bi,...,bn}的一個(gè)后綴，并且是AC狀態(tài)機(jī)所有狀態(tài)的后綴標(biāo)記中，后綴匹配長度最長的一個(gè)。即AC自動機(jī)實(shí)現(xiàn)的是字符串最長后綴匹配。

(3)AC自動機(jī)在任一個(gè)時(shí)刻都處于有限個(gè)狀態(tài)中的一個(gè)，并且下一個(gè)狀態(tài)只由當(dāng)前的輸入和當(dāng)前的狀態(tài)所決定。因此，如果兩個(gè)獨(dú)立運(yùn)轉(zhuǎn)的、構(gòu)造相同的狀態(tài)機(jī)的當(dāng)前狀態(tài)和輸入序列也都相同，之后它們的狀態(tài)跳轉(zhuǎn)序列將完全相同。

2.2 基于數(shù)據(jù)包分片的負(fù)載均衡并行匹配算法

基于數(shù)據(jù)包分片的負(fù)載均衡方法如圖2所示，首先把數(shù)據(jù)包的有效負(fù)載根據(jù)匹配引擎的線程數(shù)目進(jìn)行分割，再將分割后的各個(gè)分片分發(fā)給不同的線程。每個(gè)負(fù)載引擎檢查的是同一數(shù)據(jù)包的不同部分，但總體上看整個(gè)數(shù)據(jù)包的有效負(fù)載都完整得到檢查。這種方法有以下優(yōu)點(diǎn)：(1)模式匹配算法的時(shí)間復(fù)雜度與輸入數(shù)據(jù)的長度有關(guān)，減少了每個(gè)引擎處理的數(shù)據(jù)量能有效減少處理時(shí)間，獲得更好的加速比；(2)數(shù)據(jù)包分片的并行粒度小且均衡，從而可以獲得很好的并行加速效果。

圖2 基于數(shù)據(jù)包分片的負(fù)載均衡并行匹配方法

基于數(shù)據(jù)包分片的并行方法的主要缺點(diǎn)是在分割點(diǎn)處，有可能發(fā)生模式串的漏判。檢測過程中，只有當(dāng)模式串被完整地包含在一個(gè)數(shù)據(jù)包分片中時(shí)，該模式串才能被檢測到。如果一個(gè)模式串跨越多個(gè)分片那么每個(gè)處理線程都只能檢測到它的一部分，因此將不會被發(fā)現(xiàn)，從而產(chǎn)生漏判。如圖2所示，檢測引擎在數(shù)據(jù)包中查找模式串“her”，由于該模式串恰好處在分片1和分片2的分割點(diǎn)位置，數(shù)據(jù)包的分割導(dǎo)致該匹配模式串也被分割成兩段且被包含于不同的數(shù)據(jù)包分片中，因此無論哪一個(gè)檢測引擎都不能發(fā)現(xiàn)該模式串的存在。對于這個(gè)問題，在已有的數(shù)據(jù)包分片并行方法中，都把匹配過程劃分為兩個(gè)階段：正常匹配階段和驗(yàn)證階段，每個(gè)線程檢測完所分配的數(shù)據(jù)包分片任務(wù)后，繼續(xù)向后處理，以驗(yàn)證和消除分割點(diǎn)處的漏判。在驗(yàn)證階段所做的檢測工作，顯然和其他線程是重疊的，帶來了冗余的檢測開銷。因此，算法設(shè)計(jì)的關(guān)鍵在于如何確定何時(shí)可以停止冗余檢測，以最小的開銷來解決漏判的問題。

2.2.1 數(shù)據(jù)包分割并行匹配

文獻(xiàn)[5]提出一種數(shù)據(jù)包分割并行匹配算法(Divided Data Parallel signature matching, DDP)。DDP中，驗(yàn)證階段處理的冗余數(shù)據(jù)包長度是固定的，為最長的模式串長度Smax-1。如圖3所示，當(dāng)線程1處理完分片1后，會繼續(xù)向后處理，直至處理完Smax-1個(gè)字符結(jié)束。由于最長模式串是Smax個(gè)字符，多處理Smax-1個(gè)字符就可以保證不會因?yàn)閿?shù)據(jù)包分片而存在任何匹配模式串的遺漏。

DDP算法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，線程間不需要同步，只需要單純增加冗余檢測就能避免漏判。缺點(diǎn)是重疊區(qū)域大，在實(shí)際環(huán)境中，由于Smax數(shù)值比較大，導(dǎo)致算法時(shí)間復(fù)雜度非常高，如在開源NIDS軟件Snort中，最長的待檢測字符串長度超過500 Byte，在開源的病毒檢測工具ClamAV中，最長的字符串長度超過160 Byte[8-10]。

圖3 DDP算法示意圖

2.2.2 猜測式并行模式匹配算法

為了解決DDP中存在的問題，文獻(xiàn)[11]提出猜測式的并行模式匹配算法(Speculative Parallel Pattern Matching, SPPM)。

如圖4所示，在SPPM線程正常匹配階段的處理過程中，會記錄每個(gè)字節(jié)跳轉(zhuǎn)時(shí)的AC自動機(jī)狀態(tài)；進(jìn)入驗(yàn)證階段后，SPPM會比較當(dāng)前字節(jié)跳轉(zhuǎn)時(shí)的自動機(jī)狀態(tài)和歷史記錄中其他線程處理該字節(jié)時(shí)的自動機(jī)狀態(tài)，如果狀態(tài)相同，就可以退出驗(yàn)證匹配階段。

SPPM的原理是如果兩個(gè)相同的狀態(tài)機(jī)的當(dāng)前狀態(tài)和輸入序列相同，之后它們的狀態(tài)跳轉(zhuǎn)序列將完全相同。和DDP相比，SPPM算法減小了冗余匹配長度，大幅度降低了時(shí)間復(fù)雜度。但該算法需要一塊額外空間用來記錄歷史檢測狀態(tài)序列，空間消耗較大；此外算法中相鄰并行分片的檢測結(jié)果存在依賴關(guān)系，因此各個(gè)并行單位的同步要求很高，如果有一個(gè)分片檢測得太慢，檢測其他分片的檢測引擎也要暫停等待，最終性能反而會下降。

2.2.3 枚舉式并行模式匹配算法

文獻(xiàn)[12]提出一種基于枚舉的數(shù)據(jù)并行算法ParaRegex，如圖5(分片1、分片2)所示，在分割點(diǎn)處，算法將枚舉自動機(jī)所有狀態(tài)作為初始狀態(tài)，分別進(jìn)行狀態(tài)的轉(zhuǎn)移。這種基于枚舉的方法會產(chǎn)生大量的冗余計(jì)算開銷，因此已有研究主要通過減少和聚合枚舉數(shù)目來提升算法性能。

圖4 SPPM算法示意圖

圖5 枚舉式并行匹配算法示意圖

例如在ParaRegex[12]中，利用隨著字符串向后匹配時(shí)，激活狀態(tài)會越來越少，即狀態(tài)會逐漸匯聚的現(xiàn)象，設(shè)計(jì)“中間狀態(tài)單元”的數(shù)據(jù)結(jié)構(gòu)，以比特形式記錄各字符的匹配信息，將相同狀態(tài)的計(jì)算序列合并，從而減少計(jì)算復(fù)雜度(如圖5，在處理分片3的第2個(gè)字符‘f’時(shí)，兩個(gè)狀態(tài)3發(fā)生了匯聚)。類似的，文獻(xiàn)[13]則通過計(jì)算兩次狀態(tài)轉(zhuǎn)移中各狀態(tài)出現(xiàn)概率，預(yù)測枚舉的初始狀態(tài)子集來減少計(jì)算量。

雖然已有方法大幅度減少了枚舉的狀態(tài)數(shù)[12,13]，但是枚舉式并行匹配方法需要利用前一個(gè)匹配引擎得出的前一個(gè)分片匹配完的最后結(jié)果進(jìn)行狀態(tài)合并從而確定正確的可能性序列，造成同步開銷。此外，在狀態(tài)數(shù)目多的情形下，即使收斂狀態(tài)，減少激活狀態(tài)個(gè)數(shù)，還是不能很好地減少枚舉帶來的性能開銷，因此，枚舉式并行匹配方法的性能受自動機(jī)的狀態(tài)數(shù)影響較大。

2.2.4 基于硬件的并行算法

此外，還有一些基于硬件的工作，利用指令集并行來實(shí)現(xiàn)DPI的數(shù)據(jù)并行。文獻(xiàn)[14]認(rèn)為字符串匹配算法性能受限于CPU的停頓和cache未命中訪存開銷，通過最大限地減少CPU停頓并最大化指令級并行性來實(shí)現(xiàn)高速的匹配，與此同時(shí)優(yōu)化了訪存次數(shù)進(jìn)一步提升性能；文獻(xiàn)[15]利用Intel CPU的SIMD并行化指令一次并行匹配多個(gè)模式串大幅提升匹配效率。這些基于硬件的工作，與基于軟件的數(shù)據(jù)包分割算法是正交的，可以同時(shí)使用進(jìn)一步提高性能。

3 DCPM算法設(shè)計(jì)

為了解決DDP, SPPM, ParaRegex的問題，我們提出了距離比較并行匹配(Distance Comparison Parallel Matching, DCPM)算法。和DDP以及SPPM類似，DCPM也是基于AC字符串匹配算法，以數(shù)據(jù)包分片為粒度并行處理網(wǎng)絡(luò)流量，檢測階段也劃分為正常匹配階段和驗(yàn)證匹配階段。不同的是，驗(yàn)證階段中，DCPM線程在處理每個(gè)字符時(shí)，通過比較當(dāng)前字符與分割點(diǎn)間的距離和當(dāng)前狀態(tài)的深度，決定是否退出驗(yàn)證檢測。和DDP, SPPM相比，DCPM的線程間沒有同步開銷，不需要實(shí)時(shí)保存匹配狀態(tài)，具有更好的時(shí)間和空間復(fù)雜度。

算法的具體匹配處理流程如下：

假設(shè)有n個(gè)DCPM線程：DCPM1,DCPM2,...,DCPMi,...,DCPMn。假設(shè)待檢測的字符串input，被相應(yīng)地分為n個(gè)分片：input1,input2,...,inputi,...,inputn，第i個(gè)分片由 DCPMi線程處理。

(1)正常匹配階段。每個(gè)DCPMi線程都初始化一個(gè)記錄AC自動機(jī)狀態(tài)的變量statei=0，并按照AC算法逐字節(jié)檢測第i個(gè)分片，根據(jù)輸入的字符進(jìn)行狀態(tài)跳轉(zhuǎn)并更新statei變量，同時(shí)判斷檢測過程中是否發(fā)生了字符串匹配。

(2)驗(yàn)證匹配階段。除最后一個(gè)線程外，前面的n-1個(gè)線程DCPMi都初始化一個(gè)記錄越過分割點(diǎn)(即inputi和inputi+1之間的分割位置)距離的變量stepi=0。DCPMi線程在檢測完第i個(gè)分片之后，繼續(xù)檢測其后的數(shù)據(jù)包分片內(nèi)容，每處理一個(gè)字節(jié)，stepi都會加1。在每個(gè)狀態(tài)statei，比較狀態(tài)statei的深度和當(dāng)前的stepi：若深度大于stepi，則繼續(xù)進(jìn)行驗(yàn)證階段的匹配；反之若深度小于或等于stepi，則可認(rèn)為不會再有漏判，跳出驗(yàn)證階段。

單個(gè)DCPM線程的模式匹配算法的偽碼如表1所示。下面仍然以圖1所示的DFA作為例子，對本算法的執(zhí)行過程做進(jìn)一步的說明。

假設(shè)有3個(gè)DCPM線程，輸入的字節(jié)序列為e-sh-s-h-i-s-s-i-h-s-h-s-r-e，表2為3個(gè)線程在正常匹配階段的狀態(tài)跳轉(zhuǎn)結(jié)果：都從初始狀態(tài)s0開始檢測，在檢測完分片后3個(gè)線程分別跳轉(zhuǎn)至狀態(tài)s8，s1，s0。從表2的狀態(tài)跳轉(zhuǎn)過程可知，在正常階段的檢測中，在所有的3個(gè)分片中均未發(fā)現(xiàn)有匹配。

表1 單個(gè)DCPM線程內(nèi)的模式匹配算法

表2 DCPM匹配算法正常階段檢測結(jié)果

表3 DCPM算法驗(yàn)證階段檢測結(jié)果

表3為進(jìn)入驗(yàn)證階段后的狀態(tài)跳轉(zhuǎn)情況。由于第3個(gè)線程已檢測到了輸入字符串的最末位置，因此不需要再繼續(xù)進(jìn)入到驗(yàn)證階段；線程1和線程2則分別向后處理，進(jìn)入到驗(yàn)證階段。以第1個(gè)線程為例：

(1)檢測完分片1之后，狀態(tài)為s8，進(jìn)入驗(yàn)證階段后，根據(jù)讀入的第1個(gè)字節(jié)‘i’，狀態(tài)跳轉(zhuǎn)至s5，同時(shí)檢測步數(shù)加1；s5的狀態(tài)深度為2，此時(shí)的檢測步數(shù)為1，根據(jù)DCPM算法，驗(yàn)證階段的匹配未結(jié)束，繼續(xù)上述過程。

(2)根據(jù)讀入的第2個(gè)字節(jié)‘s’，狀態(tài)跳轉(zhuǎn)至s6，這是一個(gè)可接受狀態(tài)因此可確定發(fā)生了匹配。此時(shí)的檢測步數(shù)為2，而狀態(tài)深度為3，匹配仍未結(jié)束。

(3)繼續(xù)讀入分片2的第3個(gè)字節(jié)‘s’，狀態(tài)跳轉(zhuǎn)至s7，此時(shí)狀態(tài)深度為1，小于等于冗余檢測步數(shù)3，冗余檢測結(jié)束。

因此，在第2階段線程1共檢測了3個(gè)字節(jié)的輸入，發(fā)現(xiàn)一個(gè)橫跨分片1和分片2的匹配字符串his。線程2按照同樣的方法對分片3進(jìn)行檢測，共檢測一個(gè)字節(jié)的輸入，未發(fā)現(xiàn)匹配。

綜合兩個(gè)階段的檢測結(jié)果，整個(gè)輸入中發(fā)現(xiàn)有一個(gè)匹配，發(fā)生在第1個(gè)和第2個(gè)分片的分割處：第5～7 Bytes的his。這個(gè)檢測結(jié)果也和順序檢測一致。

4 算法理論分析

4.1 算法正確性證明

如圖6所示，在算法執(zhí)行過程中，當(dāng)處于驗(yàn)證匹配階段的DCPMi線程在處理數(shù)據(jù)包長度為P1+P2時(shí)，假定此時(shí)滿足了驗(yàn)證階段的退出條件depthi(State_P1P2)< stepi，(State_P1P2)為當(dāng)前的自動機(jī)狀態(tài))。

圖6中，首先證明在P1+P2的位置退出時(shí)，不會在分割點(diǎn)造成漏判：即線程DCPMi+1在處理到相同位置時(shí)，自動機(jī)的狀態(tài)State_P2和DCPMi的State_P1P2是同一個(gè)狀態(tài)；類似于SPPM算法，當(dāng)滿足這個(gè)條件時(shí)，由于DCPMi和DCPMi+1的后續(xù)狀態(tài)跳轉(zhuǎn)將完全一致，則DCPMi線程可以退出驗(yàn)證階段，不會造成分割點(diǎn)的漏判問題。

圖6 DCPM算法理論分析示意圖

算法正確性的證明過程如下：

(1)DCPMi+1線程在處理完P(guān)2區(qū)域后，狀態(tài)為State_P2。由2.1節(jié)介紹的AC自動機(jī)性質(zhì)(2)可知，在自動機(jī)的所有狀態(tài)中，State_P2的后綴標(biāo)記L(State_P2)是該冗余區(qū)域P2的最長后綴匹配。

(2)DCPMi線程在處理完P(guān)1和P2區(qū)域后，狀態(tài)為State_P1P2。同樣，由2.1節(jié)介紹的AC自動機(jī)性質(zhì)(2)可知，State_P1P2的后綴標(biāo)記L(State_P1P2)是區(qū)域P1+P2的最長后綴匹配。由于線程在State_P1P2時(shí)退出驗(yàn)證匹配，根據(jù)DCPM算法，L(State_P1P2)的長度小于等于P2長度，所以State_P1P2的后綴標(biāo)記L(State_P1P2)也是P2的最長后綴匹配。

(3)State_P1P2和State_P2的后綴標(biāo)記都是P2的最長后綴匹配，所以L(State_P1P2)和L(State_P2)兩個(gè)后綴標(biāo)記相等，根據(jù)2.1節(jié)介紹的AC自動機(jī)性質(zhì)(1)，State_P1P2和State_P2事實(shí)上是同一狀態(tài)。

4.2 最短冗余檢測長度證明

仍然以圖6的兩個(gè)線程為例，證明DCPM算法的冗余檢測長度與前文介紹的SPPM算法相等，都檢測了最短的冗余長度：即在DCPMi線程的驗(yàn)證匹配停止條件滿足之前，不存在一個(gè)字符位置，使得DCPMi線程和DCPMi+1線程跳轉(zhuǎn)到相同的狀態(tài)。

利用反證法進(jìn)行證明：

(1)假如有比DCPM算法距離分割點(diǎn)更近的停止位置，使得兩個(gè)DCPM線程跳轉(zhuǎn)到相同狀態(tài)s，s的深度為d，該位置到分割點(diǎn)的距離為x(該位置不滿足DCPM算法停止條件)；

(2)DCPMi+1線程處理x個(gè)字節(jié)時(shí)，從狀態(tài)0跳轉(zhuǎn)到狀態(tài)s，x必然大于等于s的深度d；

(3)由DCPM算法定義可知，由于線程DCPMi在驗(yàn)證階段處理該位置時(shí)，并沒有滿足退出條件，因此該位置到分割點(diǎn)的距離x小于s的深度d；

(4)由于(2)和(3)矛盾，因此不存在比DCPM算法找到的停止位置，距離分割點(diǎn)更近的冗余檢測停止位置。

從上述證明過程可以看出，DCPM的冗余長度實(shí)際上和SPPM一樣。但是DCPM算法的優(yōu)勢是不需要線程間的同步開銷。

5 實(shí)驗(yàn)評估

為評估DCPM算法的性能，本文以AC算法為基礎(chǔ)，實(shí)現(xiàn)了已有研究中提到的DDP和SPPM，以及本文提出的DCPM并行匹配引擎，并與構(gòu)建了與ParaRegex相似的實(shí)驗(yàn)環(huán)境。

文獻(xiàn)[11]的實(shí)驗(yàn)結(jié)果表明，SPPM并行模式匹配引擎的負(fù)載情況，和模式串在待檢測串中的比重(Ratio)有關(guān)：模式串在待匹配串中的比重越大，冗余區(qū)域就越大，并行引擎的負(fù)載加重。而DDP算法的時(shí)間復(fù)雜度顯然和模式串的最大長度有關(guān)：模式串最大長度越長，冗余檢測區(qū)域越大。因此，首先通過人工產(chǎn)生的模式串和待匹配串，考察并驗(yàn)證在不同的Ratio和模式串長度情況下，DCPM和DDP以及SPPM算法的性能對比情況。為了測試算法的實(shí)際效果，測量了3種算法在真實(shí)的良性和惡意流量情況下采用開源入侵檢測系統(tǒng)Snort[10]規(guī)則集進(jìn)行匹配的加速比情況，并構(gòu)建了類似文獻(xiàn)[12]的數(shù)據(jù)集，在不同的狀態(tài)數(shù)條件下，和枚舉式并行模式匹配算法進(jìn)行加速比對比。

5.1 實(shí)驗(yàn)環(huán)境與測試數(shù)據(jù)

本文的實(shí)驗(yàn)環(huán)境使用處理器型號為Intel E5-2660 @ 2.00 GHz，包含8個(gè)core，cache大小為35840 kB，操作系統(tǒng)為64位的CentOS Linux release 7.2.1511。

5.1.1 人工產(chǎn)生模式串和待匹配串

采用的字符范圍為a～z, A～Z以及數(shù)字0～9，所隨機(jī)產(chǎn)生的模式串集和待匹配串集的具體情況分別如表4、表5 所示，表5 中長度范圍1 5 0 0 ～3000 Byte，字符串?dāng)?shù)50000。

5.1.2 真實(shí)流量場景

(1) 場景1。選取Snort規(guī)則庫中2858條規(guī)則作為模式串集，選取USTC-TFC2016[16]良性流量(使用了Gmail郵件數(shù)據(jù)包和Weibo數(shù)據(jù)包，詳細(xì)屬性見表6)和CTU-13[17]惡意流量(使用Bot僵尸網(wǎng)絡(luò)流量，詳細(xì)屬性見表7)的數(shù)據(jù)包作為待檢測集。本實(shí)驗(yàn)檢測數(shù)據(jù)具體情況分別如表6、表7所示。

該場景的主要目標(biāo)是驗(yàn)證DCPM, DDP和SPPM相比在真實(shí)流量環(huán)境中的性能優(yōu)勢，分別比對了3種算法在惡意流量和良性流量中的加速比。具體的測試結(jié)果將在5.2.3節(jié)詳細(xì)介紹。

表4 人工產(chǎn)生模式串集合

表5 人工產(chǎn)生待匹配字符串集合

表6 實(shí)驗(yàn)所用的snort模式串集合1

表7 實(shí)驗(yàn)所用真實(shí)流量數(shù)據(jù)集1

(2) 場景2。分別選取Snort規(guī)則庫中52條、828條規(guī)則作為模式串集(生成的DFA狀態(tài)數(shù)與文獻(xiàn)[12]采用的數(shù)據(jù)集相近)，選取Darpa[18]中Monday這一天的流量作為待檢測集(與文獻(xiàn)[12]采用同一數(shù)據(jù)集)。數(shù)據(jù)集的具體情況分別如表8、表9所示。

在該場景中，為了驗(yàn)證算法的穩(wěn)定性，本文構(gòu)建了類似文獻(xiàn)[12]的數(shù)據(jù)集，在不同的狀態(tài)數(shù)條件下，和枚舉式并行模式匹配算法進(jìn)行加速比對比。

5.2 實(shí)驗(yàn)結(jié)果

5.2.1 實(shí)驗(yàn)1：算法正確性實(shí)驗(yàn)

對DCPM算法的正確性進(jìn)行驗(yàn)證：用表4的pattern1集構(gòu)造的AC自動機(jī)檢測mstring1_0,mstring1_50, mstring1_100輸入字符串集，用pattern2集構(gòu)造的AC自動機(jī)檢測mstring2_0,mstring2_50, mstring2_100輸入字符串集，記錄AC自動機(jī)的匹配次數(shù)，并和對應(yīng)情況下，啟動不同線程數(shù)(1, 2, 4, 8個(gè)線程)的DCPM算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果如表10所示，DCPM算法的匹配個(gè)數(shù)和AC算法完全一致。

5.2.2 實(shí)驗(yàn)2：對比DDP, SPPM和DCPM的加速比

本實(shí)驗(yàn)使用人工產(chǎn)生的模式串和規(guī)則集，測量DDP, SPPM和DCPM 3種算法在不同的模式串集和待檢測的輸入字符串集下的加速比。

圖7表示在不同長度的pattern集和不同特征模式比例的待匹配字符串集下3種算法加速比情況。

為了更好地分析3種算法的性能，本文將數(shù)據(jù)包并行匹配算法的開銷劃分為3部分：正常匹配開銷，重疊匹配開銷，并行開銷。正常匹配開銷為串行匹配時(shí)的N分之一，這是基于數(shù)據(jù)包分片的并行匹配算法加速的基礎(chǔ)。但任何一種數(shù)據(jù)包分片并行算法都無法達(dá)到與串行相比為N的加速比，算法在完成所有輸入數(shù)據(jù)的檢測之后還需要增加冗余數(shù)據(jù)的檢測以確保算法的準(zhǔn)確，這一部分就是重疊匹配開銷。此外，并行處理還會造成如同步時(shí)延、數(shù)據(jù)共享時(shí)延等的其他時(shí)延，這是數(shù)據(jù)包并行匹配算法的并行開銷。

圖7可以明顯看到DDP算法和DCPM算法的加速比隨著線程數(shù)的增加呈上升趨勢，但由于存在重疊匹配開銷，加速比無法達(dá)到隨線程數(shù)線性增長。SPPM算法的加速比表現(xiàn)則始終較差，這是因?yàn)樵撍惴ㄋ刑幚砥鞴蚕硗粋€(gè)歷史緩存表，各個(gè)分片的檢測結(jié)果相互依賴因而對同步的要求很高，并行帶來的加速不能彌補(bǔ)并行開銷。

表8 實(shí)驗(yàn)所用的snort模式串集合2

表9 實(shí)驗(yàn)所用真實(shí)流量數(shù)據(jù)集2

表10 正確性測試實(shí)驗(yàn)結(jié)果

圖7 不同pattern集和檢測集下各算法加速比隨線程數(shù)變化情況

對于含有不同pattern比例的待匹配字符串集，比較使用相同pattern的圖7(a)-圖7(c)的測量結(jié)果，可以看到，當(dāng)待檢測集中包含的pattern比例更少時(shí)，DCPM算法的加速效果更加顯著。這是由于DCPM算法中各個(gè)匹配引擎共享的信息少，引擎間的獨(dú)立程度高，只要實(shí)現(xiàn)方法恰當(dāng)算法的并行開銷就能保持在一個(gè)較小的值內(nèi)，而重疊開銷與輸入數(shù)據(jù)與模式串集的匹配程度有關(guān)-在最優(yōu)情形下，分片的起始狀態(tài)恰好為狀態(tài)s0，重疊區(qū)域長度為0；而DDP算法由于其重疊匹配長度固定為最長模式串減1，所以基本不受模式串比例的影響。同樣地，比較圖7(d)-圖7(f)也可以看到相同的現(xiàn)象。

對于不同長度的pattern，比較使用相同待檢測集的圖7(a)與圖7(d)可以發(fā)現(xiàn)，與模式串pattern 1構(gòu)成待檢測集的結(jié)果相比，DCPM算法較DDP算法的加速比在模式串pattern 2構(gòu)成待檢測集的結(jié)果中提升更明顯。這是由于DDP算法的重疊匹配區(qū)域與最長的模式串長度Smax有關(guān)，當(dāng)Smax變長時(shí)重疊匹配區(qū)域也同樣變長，而DCPM算法的重疊匹配區(qū)域長度只與匹配串所占比例有關(guān)。在匹配串所占比例相同時(shí)，模式串最大長度越大，DDP算法的重疊匹配區(qū)域與DCPM算法的重疊匹配區(qū)域相差越大，冗余越多，從而在模式串更長的時(shí)候，DCPM算法的加速比優(yōu)勢會更大。比較圖7(b)和圖7(e)，圖7(c)和圖7(f)也能得到類似的結(jié)果。

5.2.3 實(shí)驗(yàn)3：真實(shí)流量測試結(jié)果

(1)對比DDP, SPPM和DCPM的加速比。本實(shí)驗(yàn)采用真實(shí)流量場景1中的數(shù)據(jù)集進(jìn)行測試。3種并行算法的加速比實(shí)驗(yàn)測量結(jié)果如圖8所示。

從圖8可以看出，SPPM由于同步開銷較大仍表現(xiàn)較差。而本文提出的DCPM算法隨著線程的增多，性能的優(yōu)勢更加明顯。在8個(gè)線程時(shí)，其加速比是DDP算法的3.5倍(Gmail)，1.4倍(Weibo)和1.3倍(Bot)。

從圖8(b)和圖8(c)可以看出，在數(shù)據(jù)包長度同為1500～1600 Byte的Weibo, Bot中，DCPM算法在良性流量Weibo中的加速比優(yōu)于在惡意流量Bot中的加速比。這是由于惡意流量在模式串集中的匹配(告警等)比例高于良性流量，與實(shí)驗(yàn)1中的結(jié)果分析一致。

圖8 真實(shí)規(guī)則集和檢測集下各算法加速比情況

從圖8(a)和圖8(b)可以看出，在處理良性流量時(shí)，當(dāng)待檢測字符串的長度較長時(shí)，DCPM算法的加速比隨著線程數(shù)增多的提升效果更明顯。但在圖8(a)中，DDP算法的加速比幾乎沒有增長。這是因?yàn)樽铋L模式串長度較長時(shí)，DDP算法的驗(yàn)證區(qū)域長度遠(yuǎn)遠(yuǎn)大于字符串本身的長度，所以并行并沒有減少同步處理的字符數(shù)目，也由此可以看出DDP算法在真實(shí)場景中的適應(yīng)力有限。

相比DDP和SPPM算法，DCPM算法在不同數(shù)據(jù)包有效負(fù)載長度、不同匹配比例的真實(shí)場景中均有不錯(cuò)的表現(xiàn)，因此DCPM算法具有很好的實(shí)際應(yīng)用能力。

另外，觀察圖8(a)的DCPM算法加速比，可以發(fā)現(xiàn)其性能隨核數(shù)提升不明顯，與其他兩種真實(shí)流量存在差距。這表明當(dāng)數(shù)據(jù)包較短時(shí)，分片算法加速比的提升效果不夠理想。其原因可能是對于并行匹配算法而言，分片后同步處理的字符數(shù)目減少不明顯，而冗余匹配和線程的切換帶來的其他時(shí)間影響更大。后續(xù)的工作將從分片條件、分片優(yōu)化線程同步開支、與向量化指令結(jié)合等多個(gè)方面進(jìn)一步解決這個(gè)問題。

(2)對比DCPM和ParaRegex的加速比。本實(shí)驗(yàn)用真實(shí)流量場景2中的數(shù)據(jù)集進(jìn)行測試。兩種算法的加速比實(shí)驗(yàn)測量結(jié)果如圖9所示。

圖9 不同狀態(tài)數(shù)規(guī)則集下各算法加速比隨線程數(shù)變化情況

從圖9可以看出，在DFA狀態(tài)數(shù)變多時(shí)，Para-Regex的加速比有顯著的下降，這是由于狀態(tài)數(shù)少時(shí)活躍狀態(tài)更容易匯聚到一起。而本文提出的DCPM算法并不受規(guī)則集狀態(tài)數(shù)的影響，相比ParaRegex，算法的穩(wěn)定性更好。

6 結(jié)束語

隨著網(wǎng)絡(luò)流量的增長，多模式匹配的性能問題日益嚴(yán)峻。本文首先介紹了目前在多模式匹配中應(yīng)用最廣泛的AC 算法，之后針對多模式匹配的性能問題介紹了現(xiàn)有的數(shù)據(jù)包分片并行檢測算法思想及其實(shí)現(xiàn)，包括DDP算法、SPPM算法和ParaRegex算法。為了消除漏判，這些數(shù)據(jù)包并行匹配算法在分片處增加了不同方式的冗余檢測，但都造成了嚴(yán)重的負(fù)載冗余和線程同步開銷。

為解決此問題，本文提出距離比較并行匹配(DCPM)算法，該算法基于AC算法，沒有同步開銷，冗余檢測開銷也大大減小。本文對DCPM算法的正確性和最優(yōu)性做出了證明，并對算法性能進(jìn)行了理論分析。通過人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)，證明DCPM算法不僅在性能上更優(yōu)，其受特征模式所占比例、特征模式長度、自動機(jī)狀態(tài)數(shù)等因素影響更?。辉?核處理器平臺上，相比其他算法，處理真實(shí)數(shù)據(jù)集的加速比提升了1.3～3.5倍。