模式匹配在網(wǎng)絡(luò)安全中的研究

徐東亮,張宏莉，張 磊，姚崇崇

（1.哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001；2.河南大學(xué)數(shù)據(jù)與知識(shí)工程研究所 開封 475004）

1 引言

近年來(lái)，隨著計(jì)算機(jī)、智能手機(jī)和互聯(lián)網(wǎng)的迅速發(fā)展，新的應(yīng)用軟件和服務(wù)不斷出現(xiàn)，計(jì)算機(jī)、智能手機(jī)和互聯(lián)網(wǎng)已經(jīng)深入人類生活、工作、科技和文化的各個(gè)領(lǐng)域。然而，在人們充分享受計(jì)算機(jī)網(wǎng)絡(luò)帶來(lái)的便捷的同時(shí)，也不得不面臨一個(gè)無(wú)法回避的問題，即網(wǎng)絡(luò)信息安全問題。

數(shù)據(jù)流管理是管理安全分析技術(shù)之一，是處理相對(duì)固定不變的大量查詢和源源不斷的流動(dòng)數(shù)據(jù)的技術(shù)。數(shù)據(jù)流處理器實(shí)際上也可以看成一種數(shù)據(jù)管理系統(tǒng)，該系統(tǒng)的組織結(jié)構(gòu)如圖1所示。在數(shù)據(jù)流管理中，相對(duì)靜止的是檢索條件和操縱程序，相對(duì)易變的是數(shù)據(jù)，數(shù)據(jù)流管理的對(duì)象就是檢索條件和操縱程序。

目前，網(wǎng)絡(luò)安全方面的數(shù)據(jù)流管理系統(tǒng)主要有防火墻系統(tǒng)、病毒防護(hù)系統(tǒng)、惡意軟件檢測(cè)系統(tǒng)、入侵檢測(cè)系統(tǒng)等。在這些網(wǎng)絡(luò)安全系統(tǒng)中，數(shù)據(jù)通常以大量、快速、持續(xù)的數(shù)據(jù)流的形式到達(dá)。在網(wǎng)絡(luò)安全領(lǐng)域，如何對(duì)這些數(shù)據(jù)進(jìn)行快速有效的處理一直是一個(gè)具有挑戰(zhàn)性的問題。從圖1可以看出，數(shù)據(jù)流管理系統(tǒng)都需要一個(gè)核心模塊——數(shù)據(jù)流查詢（數(shù)據(jù)分組檢測(cè)或分組過濾）。早先的數(shù)據(jù)分組檢測(cè)主要是檢測(cè)數(shù)據(jù)分組頭的五元組，這種方法簡(jiǎn)單、高效，對(duì)應(yīng)用層協(xié)議相對(duì)透明，但是這種方法無(wú)法檢測(cè)數(shù)據(jù)分組的內(nèi)容。為了解決這一問題，研究者們將注意力轉(zhuǎn)移到基于內(nèi)容的過濾方法——深度分組檢測(cè)技術(shù)。與只掃描數(shù)據(jù)分組頭五元組的傳統(tǒng)方法不同，深度分組檢測(cè)技術(shù)對(duì)數(shù)據(jù)分組的負(fù)載（payload）進(jìn)行掃描分析，在掃描過程中將數(shù)據(jù)分組的內(nèi)容與一組給定的規(guī)則進(jìn)行比較，檢測(cè)其中的非法內(nèi)容，以決定該數(shù)據(jù)是否應(yīng)被進(jìn)一步處理。該過程所依賴的最重要的技術(shù)就是模式匹配技術(shù)[1]。

圖1 數(shù)據(jù)流管理系統(tǒng)的組織結(jié)構(gòu)

從20世紀(jì)70年代到21世紀(jì)的今天，模式匹配算法經(jīng)歷了從單模式匹配到多模式匹配、從精確匹配到近似匹配、從串行匹配到并行匹配、從軟件算法到硬件實(shí)現(xiàn)的多個(gè)階段。下面以2000年為分界線，對(duì)近半個(gè)世紀(jì)的模式匹配算法的發(fā)展進(jìn)行簡(jiǎn)單介紹。

2 問題描述

模式匹配[1]，即字符串（特征、模式、字符串、規(guī)則這幾個(gè)詞在本文中意義相同）匹配，一個(gè)字符串是一個(gè)定義在有限字母表Σ上的字符序列。根據(jù)模式串和文本串是否預(yù)先給出，本文將模式匹配問題分為兩大類：一是不對(duì)文本進(jìn)行預(yù)處理的在線模式匹配（online string matching）；二是文本預(yù)先給出，可以對(duì)文本建立索引的離線模式匹配。由于網(wǎng)絡(luò)內(nèi)容安全中涉及的大都是在線匹配問題，因此本文只關(guān)注第一類問題，即不對(duì)文本建立索引數(shù)據(jù)結(jié)構(gòu)。

根據(jù)算法的功能可以分為單模式匹配算法、多模式匹配算法、近似匹配算法、基于硬件的并行模式匹配算法。

單模式匹配算法是指掃描一遍文本只匹配一個(gè)模式串的算法，經(jīng)典的單模式匹配算法有Knuth-Morris-Pratt（KMP）算法[2]和 Boyer-Moore（BM）算法[3]等。

多模式匹配算法是指只掃描一遍文本就可以查找出字符串集合P={p1,p2,…,pr}中所有字符串出現(xiàn)的位置。大多數(shù)單模式字符串匹配算法經(jīng)過一定的改進(jìn)都可以很容易地?cái)U(kuò)展成多模式字符串匹配算法。例如，Aho-Corasick（AC）算法[4]是由 KMP算法擴(kuò)展而來(lái)的，backward dawg matching（BDM）算法[5]和 Wu-Manber（WM）算法[6]是由 BM算法擴(kuò)展而來(lái)的。

近似模式匹配就是允許在文本T中查找到的匹配與模式串p之間有k個(gè)不同。近似模式匹配問題中最經(jīng)典的算法都是基于動(dòng)態(tài)規(guī)劃的匹配算法，除此之外還有基于自動(dòng)機(jī)的方法、基于位并行的方法等[7]。

基于硬件實(shí)現(xiàn)的算法是指將傳統(tǒng)的模式匹配算法移植到具有更加高效計(jì)算能力的專用硬件后的算法，或者根據(jù)硬件本身的特性設(shè)計(jì)實(shí)現(xiàn)一種專門在該硬件上使用的模式匹配算法。多核處理器、眾核處理器及專用處理芯片等硬件技術(shù)的發(fā)展使得并行的深層次細(xì)粒度的內(nèi)容檢測(cè)和分析被越來(lái)越多地用于處理模式匹配問題。

3 傳統(tǒng)模式匹配算法

本文將2000年之前提出的模式匹配算法稱為傳統(tǒng)模式匹配算法，2000年之后出現(xiàn)的算法稱為新模式匹配算法。傳統(tǒng)模式匹配算法大多都是純軟件算法，主要是精確模式匹配算法和近似模式匹配算法，采用的方法可以概括為前綴匹配、后綴匹配、子串匹配等幾大類，其代表算法 有 KMP 算法、Shift-And[8]算法、Shift-Or[9]算法、BM 算法、Horspool[10]算法、backward nondeterministic DAWG matching（BNDM）算法[11]、backward oracle matching（BOM）算法[12]等，所用到的技術(shù)包括滑動(dòng)窗口、位并行、自動(dòng)機(jī)和后綴樹等。

3.1 精確模式匹配算法

精確模式匹配算法主要分為單模式匹配算法和多模式匹配算法。在網(wǎng)絡(luò)內(nèi)容安全分析中，單模式匹配算法使用較少，現(xiàn)在只有理論研究?jī)r(jià)值，而多模式匹配算法被廣泛使用。

3.1.1 單模式匹配算法

字符串匹配問題最壞計(jì)算復(fù)雜度的下界是O(n)，第一個(gè)達(dá)到這個(gè)下界的算法是1970年由Morris和Pratt提出的[13]，之后Knuth等人在1977年將其改進(jìn)成著名的單模式匹配算法——KMP算法，它是第一個(gè)在線性時(shí)間解決模式匹配問題的算法，也是單模式匹配算法中前綴匹配滑動(dòng)窗口技術(shù)的代表算法之一。

（1）前綴匹配

KMP算法的匹配過程如圖2所示。在T＝“abcabcabcaddabba”中查找p=“abcabd”，模式串p的長(zhǎng)度為搜索窗口。在匹配時(shí)，窗口從左到右逐個(gè)字符比較。當(dāng)字符發(fā)生不等時(shí)可以跳躍。當(dāng)?shù)谝淮嗡阉鞯絋[5]和p[5]不匹配時(shí)，模式串p并不是向后移動(dòng)1位，而是根據(jù)p中p[5]=‘d’的字符串函數(shù)值（next[5]=2）檢測(cè)T[5]和p[2]是否相等。如果相等，T和p的下標(biāo)同時(shí)增加，最終在T中匹配到p。

圖2 KMP算法的匹配過程示意

（2）后綴匹配

后綴匹配方法移動(dòng)窗口時(shí)是從左到右的，而進(jìn)行比較時(shí)窗口內(nèi)則從右向左逐個(gè)比較字符，找出窗口內(nèi)文本子串和模式串的最長(zhǎng)公共后綴。如果到達(dá)窗口的起始位置，說(shuō)明已經(jīng)發(fā)現(xiàn)了一個(gè)匹配。在單模式匹配算法中，BM算法是后綴匹配方法的代表算法之一。

BM算法包含兩個(gè)跳轉(zhuǎn)方法：壞字符跳轉(zhuǎn)和好后綴跳轉(zhuǎn)。這兩種跳轉(zhuǎn)方法的目的是讓模式串每次向右移動(dòng)盡可能大的距離。如圖3所示，好后綴跳轉(zhuǎn)有兩種情況：在情況1中，如果子串和好后綴在模式串中被匹配到，則最右邊的子串將被移動(dòng)到好后綴的位置，繼續(xù)匹配；在情況2中，如果模式串中沒有與好后綴相同的子串，則在模式串p和好后綴中找到一個(gè)最長(zhǎng)前綴，并與之對(duì)齊。

圖3 壞字符跳轉(zhuǎn)示意

BM算法每次向右移動(dòng)模式串的距離是根據(jù)好后綴跳轉(zhuǎn)和壞字符跳轉(zhuǎn)得到的最大距離。BM算法具有亞線性的平均時(shí)間復(fù)雜度，而搜索階段的最壞時(shí)間復(fù)雜度為O(m×n)。BM算法的很多變體都可以保證線性的最壞時(shí)間復(fù)雜度。

（3）子串匹配

基于子串匹配的算法在字符等概率出現(xiàn)且互相獨(dú)立的情況下，具有最優(yōu)的平均時(shí)間復(fù)雜度。搜索窗口在基于子串匹配算法中的移動(dòng)很優(yōu)美，如圖4所示。假設(shè)模式串的子串u已經(jīng)在匹配窗口中從后向前倒序地被識(shí)別出來(lái)，且下一個(gè)字符“b”無(wú)法被繼續(xù)識(shí)別，這意味著p的子串中不包含bu，文本中不可能存在覆蓋bu的字符串。所以，這時(shí)匹配窗口可以被安全地移動(dòng)到u之后。如何識(shí)別模式串的所有子串是基于子串匹配算法的最大難點(diǎn)。

圖4 子串搜索示意

在單模式匹配算法中，BDM算法[5]是基于子串搜索的代表算法之一。該算法使用了后綴自動(dòng)機(jī)這種數(shù)據(jù)結(jié)構(gòu)，雖然功能強(qiáng)大，但結(jié)構(gòu)復(fù)雜。當(dāng)模式串的長(zhǎng)度不超過機(jī)器字長(zhǎng)時(shí)，后綴自動(dòng)機(jī)可以用位并行方法進(jìn)行有效模擬。

位并行算法BNDM[11]比BDM算法更快、更易于實(shí)現(xiàn)，且可用于擴(kuò)展字符串匹配，它與BDM算法具有相同的最壞時(shí)間復(fù)雜度O(m×n)，也都具有最優(yōu)的平均時(shí)間復(fù)雜度O(nlog|Σ|m/m)；當(dāng)模式串 的長(zhǎng)度較長(zhǎng) 時(shí)，BOM 算 法[12]能夠獲得與BDM算法相同的效果，且具有相同的最壞時(shí)間復(fù)雜度，但是BOM算法對(duì)基于子串的方法進(jìn)行了修改，采用了更簡(jiǎn)單的自動(dòng)機(jī)——factor oracle。

3.1.2多模式匹配算法

單模式匹配中用到的3類主要搜索方法——前綴搜索、后綴搜索和子串搜索，也是多模式匹配所用到的3類主要方法。

（1）前綴匹配

前綴匹配是指在固定長(zhǎng)度的窗口內(nèi)逐一字符自左向右地掃描文本，對(duì)于已讀入的字符，既是文本的后綴也是模式集中某個(gè)模式串的最長(zhǎng)前綴，如圖5所示。

圖5 多模式前綴匹配示意

最經(jīng)典的前綴匹配算法是著名的AC算法。該算法使用了一種被稱為Aho-Corasick（AC）自動(dòng)機(jī)的特殊自動(dòng)機(jī)。該自動(dòng)機(jī)由模式集P生成，它是對(duì)trie樹添加了失敗轉(zhuǎn)移函數(shù)擴(kuò)展而成的。

自動(dòng)機(jī)在模式匹配的應(yīng)用中性能穩(wěn)定，由于具有不依賴于模式集合和文本本身的特點(diǎn)，所以一直受到應(yīng)用者的歡迎。但自動(dòng)機(jī)有一個(gè)缺點(diǎn)，即它需要很大的內(nèi)存空間，尤其在正則表達(dá)式的匹配中，正則表達(dá)式的通配符等引起的狀態(tài)爆炸導(dǎo)致內(nèi)存爆炸，這使得自動(dòng)機(jī)在應(yīng)用中受到很大限制。

（2）后綴匹配

后綴匹配是指在固定窗口內(nèi)從右向左逐一字符匹配模式串的后綴。與單模式串的后綴匹配算法相似，根據(jù)匹配到后綴的下一次出現(xiàn)位置來(lái)移動(dòng)模式串。這種方法可以跳過一些不必要查找的字符，如圖6所示。

圖6 多模式后綴匹配示意

WM算法是多模式后綴匹配方法的代表算法之一。散列和跳躍不可能匹配的字符是WM算法最重要的思想。Commentz-Walter算法[14]是第一個(gè)從單模式擴(kuò)展到多模式的后綴匹配算法，雖然在時(shí)間、空間、實(shí)用價(jià)值方面它都無(wú)法與經(jīng)典的AC算法和WM算法等相比，但它是第一個(gè)實(shí)現(xiàn)亞線性平均時(shí)間復(fù)雜度的多模式匹配算法，在多模式匹配算法史上具有里程碑式的意義。

（3）子串匹配

子串匹配是指搜索沿著文本從后向前進(jìn)行，在模式串長(zhǎng)度為lmin的前綴中搜索子串，以此決定當(dāng)前文本位置的移動(dòng)。這種方法也可以跳過不必要的字符，如圖7所示。

圖7 多模式子串匹配示意

一般基于子串的方法只要解決兩個(gè)技術(shù)問題，都可以直接擴(kuò)展到一組模式串的情形：如何安全地移動(dòng)模式串，以避免遺漏可能的成功匹配；如何識(shí)別一組字符串的子串。SBOM算法[15]和SBDM算法[16]是多模式匹配方法中基于子串搜索的代表算法，它們分別是對(duì)BOM算法和BDM算法的擴(kuò)展。

SBDM算法在長(zhǎng)度為lmin的文本窗口內(nèi)使用以模式集建立的后綴自動(dòng)機(jī)來(lái)移動(dòng)窗口，移動(dòng)時(shí)需要從后向前識(shí)別出模式串的所有子串。該算法在所有模式串長(zhǎng)度為lmin的前綴窗口上建立反轉(zhuǎn)自動(dòng)機(jī)，從后向前識(shí)別文本在lmin的窗口中的最長(zhǎng)后綴，該后綴同時(shí)也是模式集P中模式串長(zhǎng)度為lmin的前綴子串。

SBOM算法使用factor oracle結(jié)構(gòu)為模式串集合P建立自動(dòng)機(jī)，該自動(dòng)機(jī)識(shí)別的是模式集合P中所有模式串的所有子串的超集。搜索時(shí)，在所有模式串的前綴lmin的窗口上建立反轉(zhuǎn)自動(dòng)機(jī)factor oracle（時(shí)間復(fù)雜度為O(r×lmin)），在長(zhǎng)度為lmin的文本窗口內(nèi)從后向前匹配文本字符來(lái)移動(dòng)窗口。如果無(wú)法繼續(xù)識(shí)別文本字符，那么當(dāng)前窗口可以安全地移動(dòng)到該字符之后；如果完全識(shí)別了窗口內(nèi)的字符，到達(dá)了窗口的起始位置，那么需要將P的一個(gè)子集與文本進(jìn)行比較驗(yàn)證。SBOM算法與SBDM算法的最壞時(shí)間復(fù)雜度相同，均為O(n×|P|)，平均時(shí)間復(fù)雜度也都是亞線性的。

3.2 近似模式匹配算法

近似串匹配又稱“模糊匹配”或“允許誤差的串匹配”，就是查找一個(gè)模式串p在文本T中出現(xiàn)的所有位置，并且允許有限的k個(gè)差異存在于模式串p和它在文本中的出現(xiàn)之間。近似模式匹配目前主要有如下4種方法。

（1）用來(lái)計(jì)算編輯距離的動(dòng)態(tài)規(guī)劃算法，其中1980年Sellers設(shè)計(jì)了一個(gè)非常經(jīng)典的算法[17]，它的時(shí)間復(fù)雜度為O(m)。如此看來(lái)，該算法的效率不是很高，但對(duì)它稍加改動(dòng)就可以適用于更復(fù)雜的模型。

（2）使用位并行等各種方法模擬實(shí)現(xiàn)自動(dòng)機(jī)進(jìn)行匹配。這種自動(dòng)機(jī)最初以其確定化的形式在參考文獻(xiàn)[18]中被提出，后來(lái)在參考文獻(xiàn)[19]中給出了更明確的闡述。當(dāng)模式串較短時(shí)，這類算法效率不錯(cuò)。

（3）用位并行方法模擬其他方法，該方法是所有方法中最有效的。近似搜索中大量使用位并行方法，很多很好的結(jié)果都是使用位并行方法得到的。

（4）過濾方法，該方法先執(zhí)行一個(gè)高效的過濾算法，這樣文本中那些不存在成功匹配的很多區(qū)域就可以被直接跳過，不需要匹配，然后剩下的少量文本區(qū)域是否存在成功匹配，再利用一個(gè)普通的模式匹配算法驗(yàn)證即可。

4 新模式匹配算法

2000年以前提出的經(jīng)典模式匹配算法共40種左右，但在2000年至今的這15年里就提出了50種左右，但這50種算法大多數(shù)都是對(duì)以前經(jīng)典算法的改進(jìn)或者移植，且主要是面向并行或者基于硬件加速的模式匹配方法。本節(jié)介紹最近這15年提出的新模式匹配算法。

4.1 精確模式匹配算法

4.1.1 單模式匹配算法

BM算法激發(fā)了后續(xù)單模式匹配算法的研究，近十幾年出現(xiàn)的很多單模式匹配算法都是BM算法的變體。

fast-search[20]算法是一個(gè)簡(jiǎn)單有效的BM算法的變體，模式匹配階段在模式串的第m-1個(gè)字符處開始，根據(jù)horspool算法的壞字符規(guī)則計(jì)算移動(dòng)增量。在匹配結(jié)束階段，采用好后綴規(guī)則進(jìn)行跳轉(zhuǎn)。隨后，又產(chǎn)生了fast-search算法的兩種變體：backward-fast-search[21]和forward-fast-search[22]，分別采用backward good suffix和forward good suffix規(guī)則。其中，規(guī)則表的構(gòu)建需要O(m×max(m,σ))時(shí)間，σ表示字母表的大小。

算法GRASPm[23]是使用horspool壞字符的轉(zhuǎn)移方法，通過散列函數(shù)在模式上計(jì)算2-grams的過濾方法。由此產(chǎn)生的算法最壞時(shí)間復(fù)雜度為O(m×n)，平均時(shí)間復(fù)雜度為亞線性，需要O(σ+m)的空間計(jì)算散列表和壞字符轉(zhuǎn)移表。

4.1.2 多模式匹配算法

近15年的多模匹配算法大部分是基于自動(dòng)機(jī)原理的改進(jìn)算法。

算 法 extended-BOM[24]和 simplified extended BOM[25]都是BOM算法的變體，采用自動(dòng)機(jī)的方法進(jìn)行實(shí)現(xiàn)，這兩個(gè)算法的區(qū)別在于計(jì)算模式串最右的兩個(gè)字符轉(zhuǎn)移是否在一步完成。forward-BOM[23]算法進(jìn)一步改進(jìn)了extended-BOM算法，通過當(dāng)前窗口后的字符計(jì)算轉(zhuǎn)移混合了extended-BOM算法和quick-search算法。

Kumar等人[26]研究發(fā)現(xiàn)，自動(dòng)機(jī)中很多失敗轉(zhuǎn)移指針指向相同的狀態(tài)，這造成了大量狀態(tài)轉(zhuǎn)移邊的冗余。為了解決這個(gè)問題，Kumar等人介紹了一種新的自動(dòng)機(jī)——delayed input DFA（D2FA）。D2FA將DFA（確定有限自動(dòng)機(jī)）中所有指向相同狀態(tài)的轉(zhuǎn)移用一個(gè)默認(rèn)轉(zhuǎn)移代替，這樣就大量減少了不同狀態(tài)間轉(zhuǎn)移的數(shù)量。算法XFA[27]使用有限暫存器擴(kuò)展了有限狀態(tài)自動(dòng)機(jī) （finite state automata，F(xiàn)SA），并用指令來(lái)操作這個(gè)暫存器。這種方法的時(shí)間復(fù)雜度接近DFA，空間復(fù)雜度接近NFA（非確定有限自動(dòng)機(jī)）。

4.2 近似模式匹配算法

最近15年內(nèi)的近似模式匹配方法發(fā)展依然緩慢，提出的算法不多。

Alba A等人[28]提出了針對(duì)近似模式匹配的新穎方法，該方法不依賴于編輯距離的計(jì)算，而是采用相似度指數(shù)來(lái)實(shí)現(xiàn)。在生物學(xué)領(lǐng)域，允許用戶在短時(shí)間內(nèi)找出相關(guān)的匹配。Kim Y等人[29]提出了針對(duì)近似串匹配的Top-K算法。采用q-grams跳躍字符的方式同樣不需要計(jì)算字符串的編輯距離，通過真實(shí)的實(shí)驗(yàn)數(shù)據(jù)展示了算法的有效性和伸縮性。

Li C等人[30]研究了對(duì)于一個(gè)給定的模式串，如何快速找到它的一個(gè)相似模式串集合。在此基礎(chǔ)上，他們提出了ScanCount算法、MergeSkip算法和DivideSkip算法這3個(gè)近似模式匹配算法。Prasad等人[31]提出了兩個(gè)多模式近似匹配算法：MASM1和MASM2。這兩個(gè)算法可以處理長(zhǎng)度超過一個(gè)機(jī)器字的模式串。Xu等人[32]在Prasad等人工作的基礎(chǔ)上提出了一個(gè)改進(jìn)的位并行算法——impMASM，該算法可以方便地移植到GPU（graphic processing unit，圖形處理器）上且可以處理不等長(zhǎng)模式串。

4.3 并行模式匹配算法

近15年來(lái)，對(duì)純軟件并行算法的研究也不是很多。

馬明[33]采用MPI并行編程技術(shù)，使用MPI消息傳遞函數(shù)，在不同處理單元上進(jìn)行并行處理，對(duì)經(jīng)典的KMP算法和BM算法進(jìn)行了并行實(shí)現(xiàn)，并給出了算法實(shí)現(xiàn)的核心代碼。

獨(dú)立并行壓縮自動(dòng)機(jī) （independent parallel compact finite automata，PC-FA）[34]算法也是一個(gè)基于壓縮自動(dòng)機(jī)的并行模式匹配算法。該方法是將經(jīng)典的單模式最長(zhǎng)前綴匹配算法擴(kuò)展到多模式匹配的算法。它同時(shí)使用了k個(gè)PC-FA處理輸入流中的k個(gè)字符，該參考文獻(xiàn)還從理論上證明了DFA與PC-FA是等價(jià)的。

4.4 基于硬件的模式匹配算法

進(jìn)入21世紀(jì)，隨著高性能硬件多核處理器、眾核處理器、FPGA （field-programmable gate array，現(xiàn)場(chǎng)可編程門陣列）、TCAM（ternary content addressable memory，三態(tài)內(nèi)容尋址存儲(chǔ)器）和GPU等的興起，模式匹配的研究另辟蹊徑。多核、眾核架構(gòu)提供了一個(gè)低成本實(shí)現(xiàn)高速模式匹配的方法。Villa 等人[35,36]在 IBM cell broadband engine（CBE）上實(shí)現(xiàn)了高速模式匹配系統(tǒng)，他們的工作表明將模式匹配算法經(jīng)過優(yōu)化，在多核架構(gòu)上實(shí)現(xiàn)的性能可能超過專業(yè)的加速器。但是在IBM CBE上編程、優(yōu)化非常復(fù)雜，因此譚光明等人[37]就開始在普通的多核架構(gòu)下尋找解決模式搜索的方法。他們?cè)谄胀ǖ亩嗪思軜?gòu)下設(shè)計(jì)實(shí)現(xiàn)了一個(gè)基于分解策略的高效多模式匹配算法，將模式集分解成多個(gè)子集，對(duì)每一個(gè)子集根據(jù)其模式特點(diǎn)選擇合適的匹配算法，并將它們分配到每一個(gè)核上進(jìn)行處理。

FPGA具有高速計(jì)算能力和可重配能力，被廣泛應(yīng)用于網(wǎng)絡(luò)安全過濾系統(tǒng)[38～40]。基于FPGA的模式匹配技術(shù)[41,42]是利用片上資源把模式集編譯成狀態(tài)機(jī)，將該狀態(tài)機(jī)存儲(chǔ)于片內(nèi)存儲(chǔ)器內(nèi)，然后再對(duì)輸入數(shù)據(jù)進(jìn)行過濾。純FPGA技術(shù)由于本身存儲(chǔ)器較小，很難滿足大規(guī)模模式集的匹配，所以應(yīng)用中的FPGA都與可重寫ROM結(jié)合，采用比較的方法實(shí)現(xiàn)模式匹配算法。

TCAM主要用于快速查找訪問控制列表（ACL）、路由表等，它是從CAM的基礎(chǔ)上發(fā)展而來(lái)的。一般的CAM存儲(chǔ)器中每個(gè)比特位的狀態(tài)只有兩個(gè)，即 “0”或 “1”，而TCAM中每個(gè)比特位有 3種狀態(tài)，除“0”和“1”之外，還有“don’t care”狀態(tài)，所以稱為“三態(tài)”，它是通過掩碼實(shí)現(xiàn)的。正是TCAM的第三種狀態(tài)使其既能進(jìn)行精確匹配查找[43～45]，又能進(jìn)行模糊匹配查找[46]，而CAM沒有第三種狀態(tài)，所以只能進(jìn)行精確查找[47]。

將GPU用于圖形處理以外的其他領(lǐng)域被稱為基于GPU的通用計(jì)算 （general-purpose computing on graphics processing units，GPGPU）。CPU+GPU的異構(gòu)模式是GPGPU的通用模式，其中，GPU負(fù)責(zé)并行處理密集型的海量數(shù)據(jù)，CPU負(fù)責(zé)不適合并行計(jì)算的事務(wù)管理和復(fù)雜邏輯處理。該異構(gòu)模式利用GPU的高帶寬和高性能的并行計(jì)算能力彌補(bǔ)了CPU的計(jì)算能力不足的劣勢(shì)。

GPU是單指令多數(shù)據(jù)流 （simple instruction multiple data，SIMD）體系結(jié)構(gòu)，大量的計(jì)算部件使它很適合處理模式匹配算法中對(duì)比字符這種計(jì)算密集型操作。PixeSnort[48]是第一種在入侵檢測(cè)系統(tǒng)中將GPU用于模式匹配計(jì)算的方法。這種方法使用修改的KMP算法將數(shù)據(jù)分組內(nèi)容匹配部分的工作從CPU移交給GPU處理，利用GPU強(qiáng)大的并行計(jì)算能力來(lái)提高流量處理能力。MIDeA[49]架構(gòu)利用了多個(gè)NICs、多個(gè)CPUs和多個(gè)GPUs的并行性，將它們結(jié)合起來(lái)運(yùn)用到實(shí)際網(wǎng)絡(luò)中，將相應(yīng)的操作映射到相應(yīng)的設(shè)備中，構(gòu)建了一個(gè)并行網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)。該系統(tǒng)沒有順序執(zhí)行部件，無(wú)需同步、等待或者內(nèi)容共享。大多數(shù)基于GPU實(shí)現(xiàn)的模式匹配方法都將GPU作為協(xié)處理器，幫助CPU分擔(dān)主要的計(jì)算工作。而參考文獻(xiàn)[50]實(shí)現(xiàn)了GPU-to-GPU，即輸入和輸出都在GPU的內(nèi)存中進(jìn)行，相對(duì)于GPU只作為CPU的協(xié)處理器，這種方法的匹配速度提高了3～4倍。

4.5 未來(lái)趨勢(shì)

近兩年來(lái)，對(duì)網(wǎng)絡(luò)安全中模式匹配的研究主要集中在以下兩個(gè)方面。

（1）利用專用硬件芯片，并行加速傳統(tǒng)模式匹配算法或改進(jìn)算法。例如，參考文獻(xiàn)[51]基于GPU的并行體系結(jié)構(gòu)實(shí)現(xiàn)了一個(gè)近似模式匹配算法；參考文獻(xiàn)[52]利用二叉搜索樹在FPGA上實(shí)現(xiàn)了一個(gè)內(nèi)在高效的模式匹配算法。

（2）針對(duì)特定需求，改進(jìn)現(xiàn)有算法或設(shè)計(jì)新算法。例如，參考文獻(xiàn)[53]針對(duì)海量模式集造成的高沖突率導(dǎo)致算法效率下降的問題，提出了一種隨機(jī)指紋模型，并將該模型用于WM算法，從而極大地降低了WM算法模式塊散列的沖突率，提高了算法的效率；參考文獻(xiàn)[54]對(duì)表達(dá)式的包含關(guān)系做了分類，提出了表達(dá)式冗余消除算法，然后在BitCount算法的基礎(chǔ)上提出了一種時(shí)間復(fù)雜度為O(1)的掩碼驗(yàn)證算法MaskVeri。除此之外，本文第4節(jié)中列出的近兩年的參考文獻(xiàn)也都是基于這兩個(gè)方面做出的研究。

利用專用硬件芯片和針對(duì)特定環(huán)境需求，依然是未來(lái)網(wǎng)絡(luò)安全中模式匹配最主要的兩個(gè)研究方向。專用芯片有GPU、CAM、FPGA、眾核等；特定需求包括降低海量模式規(guī)則沖突率、高效內(nèi)存利用率等。

5 結(jié)束語(yǔ)

從網(wǎng)絡(luò)中快速通過的數(shù)據(jù)流中查找用戶感興趣的信息（海量模式集），是一項(xiàng)非常富有挑戰(zhàn)性的工作。隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡(luò)流量日益增大，病毒、垃圾郵件等攻擊手段越來(lái)越多樣，安全系統(tǒng)中的模式集趨向海量發(fā)展。與之相反的是，安全系統(tǒng)中的核心模塊——模式匹配算法的發(fā)展過于緩慢，傳統(tǒng)的模式匹配算法性能已經(jīng)趨于理論上限。模式匹配技術(shù)在實(shí)際應(yīng)用中還面臨以下兩個(gè)問題。

· 到目前為止，還沒有一種算法可以適用于任何網(wǎng)絡(luò)環(huán)境。

· 目前，網(wǎng)絡(luò)內(nèi)容過濾方面的主要矛盾為純軟件的模式匹配算法的吞吐量已經(jīng)達(dá)到或接近理論上限與網(wǎng)絡(luò)流量指數(shù)級(jí)增長(zhǎng)之間的矛盾。

本文針對(duì)目前模式匹配在網(wǎng)絡(luò)安全系統(tǒng)中面臨的挑戰(zhàn)，以2000年為分界線對(duì)傳統(tǒng)模式匹配方法和新模式匹配方法進(jìn)行了介紹。2000年以前的傳統(tǒng)模式匹配算法大都以純軟件算法為主，且部分算法性能已經(jīng)接近或達(dá)到了理論上限。但是，即使性能達(dá)到理論上限的算法也并不是適用于所有環(huán)境的，這也是至今依然有很多研究者從事模式匹配問題研究的原因。2000年以后，由于專用芯片等硬件的快速發(fā)展，眾多的研究者開始改進(jìn)大量的傳統(tǒng)模式匹配算法，利用專用芯片的高計(jì)算性能來(lái)提高匹配效率。

不難看出，經(jīng)過近半個(gè)世紀(jì)的發(fā)展，模式匹配技術(shù)已經(jīng)從純軟件方法逐漸發(fā)展到借助于專用硬件來(lái)提升效率。因此，本文針對(duì)海量模式集和特定應(yīng)用環(huán)境，著重介紹了利用專用芯片加速模式匹配算法，提升網(wǎng)絡(luò)安全系統(tǒng)性能，這也是目前網(wǎng)絡(luò)安全中模式匹配的重要方向。

1 Navarro G,Raffinot M.Flexible Pattern Matching in Strings:Practical On-Line Search Algorithms for Texts and Biological Sequences.Cambridge:Cambridge University Press,2002

2 Knuth D E,Morris J H,Pratt V R，et al.Fast pattern matching in strings.SIAM Journal on Computing,1977,6(2):323～350

3 Boyer R S,Moore J S.A fast string searching algorithm.Communications of the ACM,1977,20(10):762～772

4 Aho A V,Corasick M J.Efficient string matching:an aid to bibliographic search.Communications of the ACM,1975,18(6):333～340

5 Crochemore M,Czumaj A,Gasieniec L,et al.Speeding up two string-matching algorithms.Algorithmica,1994,12(4～5):247～267

6 Wu S,Manber U.A Fast Algorithm for Multi-Pattern Searching.Technical Report TR-94-17,University of Arizona,1994

7 Ukkonen E.Finding approximate patterns in strings.Journal of Algorithms,1985,6(1～3):132～137

8 Wu S,Manber U.Fast textsearching:allowing errors.Communications of the ACM,1992,35(10):83～91

9 Baeza-Yates R A,Gonnet G H.A new approach to text searching.Communications of the ACM,1992,35(10):74～82

10 Horspool R N.Practical fast searching in strings.Software:Practice and Experience,1980,10(6):501～506

11 Navarro G,Raffinot M.Fast and flexible string matching by combining bit-parallelism and suffix automata.ACM Journal of Experimental Algorithmics,2000,5(4):1～36

12 Allauzen C,Crochemore M,Raffinot M.Efficient experimental string matching by weak factor recognition.Proceedings of 17th Annual Symposium on Combinatorial Pattern Matching,Barcelona,Spain,2006:51～72

13 Morris J J,Pratt V R.A Linear Pattern-Matching Algorithm.Technical Report 40,University of California,1970

14 Commentz-Walter B.A String Matching Algorithm Fast on the Average.Berlin:Springer Berlin Heidelberg,1979

15 Allauzen C,Raffinot M.Factor Oracle of a Set of Words.Institute Gaspart-Monge,University de Marne-la-Vallee,TR-99-11,1999

16 Blumer A,Blumer J,Haussler D,et al.Complete inverted files for efficient text retrieval and analysis.Journal of the ACM,1987,34(3):578～595

17 Sellers P H.On the theory and computation of evolutionary distances.SIAM Journal on Applied Mathematics,1974,26(4):787～793

18 Ukkonen E.Finding approximate patterns in strings.Journal of Algorithms,1985,6(1):132～137

19 Wu S,ManberU.Fasttextsearching:allowing errors.Communications of the ACM,1992,35(10):83～91

20 Cantone D,Faro S.Fast-search:a new efficient variant of the boyer-moore string matching algorithm.Proceedings of the 2nd International Workshop on Experimental and Efficient Algorithms,Ascona,Switzerland,2003:247～267

21 Cantone D,Faro S.Forward-fast-search:another fast variant of the boyer-moore string matching algorithm.Proceedings of the Prague Stringology Conference,Prague,Czech Republic,2003:10～24

22 Cantone D,Faro S.Searching for a substring with constant extra-space complexity.Proceedings of the 3rd International Conference on Fun with Algorithms,Isola d’Elba,Italy,2004:118～131

23 Deusdado S,Carvalho P.GRASPm:an efficient algorithm for exact pattern-matching in genomic sequences.International Journal of Bioinformatics Research and Applications,2009,5(4):385～401

24 Fan H,Yao N,Ma H.Fastvariantsofthe backwardoracle-marching algorithm.Proceedings of the 4th International Conference on Internet Computing for Science and Engineering,Harbin,China,2009:56～59

25 Faro S,Lecroq T.Efficient variants of the backward-oraclematching algorithm.Proceedingsofthe Prague Stringology Conference,Prague,Czech Republic,2008:146～160

26 Kumar S,Dharmapurikar S,Yu F,et al.Algorithms to accelerate multiple regular expressions matching for deep packet inspection.Proceedings ofSIGCOMM,Pisa,Italy,2006:339～350

27 Smith R,Estan C,Jha S.XFA:Faster signature matching with extended automata.Proceedings of IEEE Symposium on Security and Privacy,Oakland,CA,USA,2008:187～201

28 Abla A,Rodriguez-KesslerM,Arce-Santana E R,etal.Approximate string matching using phase correlation.Proceedings of the 34th Annual International Conference of the IEEE Engineering in Medicine and Biology Society,San Diego,CA,USA,2012:6309～6312

29 Kim Y，Shim K.Efficient top-kalgorithms for approximate substring matching.Proceedings of ACM SIGMOD,New York,USA,2013:385～396

30 Li C,Lu J H,Lu Y M.Efficient merging and filtering algorithms for approximate string searches.Proceedings of IEEE 24th International Conference on Data Engineering,Cancun,Mexico,2008:257～266

31 Prasad R,Sharma A K,Singh A,et al.Efficient bit-parallel multi-patterns approximate string matching algorithms.Scientific Research and Essays,2011,6(4):876～881

32 Xu K,Cui W,Hu Y,et al.Bit-parallel multiple approximate string matching based on GPU.Procedia Computer Science,2013,17(5):523～529

33 馬明.串匹配算法的并行實(shí)現(xiàn)策略 （碩士學(xué)位論文）.湖北大學(xué),2010

Ma M.The parallel implementation of string matching algorithm(master dissertation).Hubei University,2010

34 Tang Y,Jiang J,Wang X,et al.Independent parallel compact finite automatons for accelerating multi-string matching.Proceedings of IEEE Global Telecommunications Conference,Miami,FL,USA,2010:1～5

35 Villa O,Sca rpazza D P,Petrini F.Accelerating real-time string searching with multicore processors.Computer,2008,41(4):42～50

36 Scarpazza D P,Villa O,Petrini F.Peak-performance DFA-based string matching on the cell processor.Proceedings of 21th International Parallel and Distributed Processing Symposium,Long Beach,USA,2007:1～8

37 Tan G M,Liu P,Bu D B,et al.Revisiting multiple pattern matching algorithmsformulti-core architecture.Journalof Computer Science and Technology,2011,26(5):866～874

38 Song H,Lockwood J W.Efficient packet classification for network intrusion detection using FPGA.Proceedings of the 13th International Symposium on Field-Programmable Gate Arrays,Monterey,CA,USA,2005:238～245

39 SchuehlerD V,Lockwood JW.A ModularSystem for FPGA-Based TCP Flow Processing in High-Speed Networks.Berlin:Springer Berlin Heidelberg,2004:301～310

40 Katashita T,Maeda A,Toda K,et al.Highly efficient string matching circuit for IDS with FPGA.Proceedings of the 14th AnnualIEEE Symposium on Field-Programmable Custom Computing Machines,Napa,CA,USA,2006:285～286

41 Dandass Y S,Burgess S C,Lawrence M,et al.Accelerating string setmatching in FPGA hardware forbioinformatics research.BMC Bioinformatics,2008,9(1)

42 Van CourtT,HerbordtM C.Families ofFPGA-based accelerators for approximate string matching.Microprocessors and Microsystems,2007,31(2):135～145

43 Meiners C R,Patel J,Norige E,et al.Fast regular expression matching using small TCAMs for network intrusion detection and prevention systems.Proceedings of the 19th USENIX Conference on Security,Washington,USA,2010

44 Hua N,Song H,Lakshman T V.Variable-stride multi-pattern matching for scalable deep packet inspection.Proceedings of IEEE INFOCOM,Rio de Janeiro,Brazil,2009:415～423

45 Bremler-Barr A,Hay D,Koral Y.CompactDFA:generic state machine compression for scalable pattern matching.Proceedings of IEEE INFOCOM,San Diego,CA,USA,2010:1～9

46 張小山,趙國(guó)鴻,王勇軍等.基于TCAM的深度報(bào)文過濾技術(shù)研究.2005全國(guó)網(wǎng)絡(luò)與信息安全技術(shù)研討會(huì)論文集,2005:143～148

Zhang X S,Zhao G H,Wang Y J,et al.Research on deep packet filtering technology based on TCAM.2005 National Conference on Network and Information Security Technology,2005:143～148

47 Gan C G.FPGA based CAM architecture string matching for network intrusion detection (Ph D dissertation).Universiti Teknologi Malaysia,Faculty of Electrical Engineering,2012

48 Nigel J,Carla B.Offloading IDS computation to the GPU.Proceedings ofthe 22nd Computer Security Applications Conference,Miami Beach,FL,USA,2006:371～380

49 Vasiliadis G, Polychronakis M, Ioannidis S. MIDeA:amulti-parallel intrusion detection architecture.Proceedings of the 18th ACM Conference on Computer and Communications Security,Chicago,USA,2011

50 Zha X,Sahni S.GPU-to-GPU and host-to-host multipattern string matching on a GPU.IEEE Transactions on Computers,2013,62(6):1156～1169

51 Man D,Nakano K,Ito Y.The approximate string matching on the hierarchical memory machine,with performance evaluation.Proceedings of the 7th International Symposium on Embedded Multicore Socs,Tokyo,Japan,2013:79～84

52 Le H,Prasanna V K.A memory-efficient and modular approach for large-scale string pattern matching.IEEE Transactions on Computers,2013,62(5):844～857

53 張宏莉,徐東亮,梁敏等.海量模式高效匹配方法研究.電子學(xué)報(bào),2014,42(6):1220～1224

Zhang H L,Xu D L,Liang M,et al.Massive strings efficient matching method research.Acta Electronica Sinica,2014,42(6):1220～1224

54 楊天龍,張宏莉.一種關(guān)鍵字表達(dá)式的匹配優(yōu)化方法.電信科學(xué),2013,29(1):39～45

Yang T L,Zhang H L.Optimization of expression matching for string matching.Telecommunications Science,2013,29(1):39～45