張巍等

摘 要： 網(wǎng)絡(luò)數(shù)據(jù)包內(nèi)容檢測技術(shù)已在網(wǎng)絡(luò)安全、網(wǎng)絡(luò)監(jiān)視、HTTP負(fù)載均衡等方面得到廣泛的應(yīng)用，因此，對快速數(shù)據(jù)包內(nèi)容的檢測就變得異常重要。在數(shù)據(jù)包內(nèi)容檢測過程中，數(shù)據(jù)包的凈載數(shù)據(jù)要通過一系列已經(jīng)定義好的正則表達(dá)式模式進(jìn)行數(shù)據(jù)匹配。在此，闡述目前數(shù)據(jù)包檢測存在的問題，如傳統(tǒng)數(shù)據(jù)包檢測應(yīng)用程序要求很大的內(nèi)存空間去存儲(chǔ)相應(yīng)的正則表達(dá)式模式，提出一種大大降低對內(nèi)存空間使用的改進(jìn)算法。通過將該改進(jìn)算法應(yīng)用到以DFA為基礎(chǔ)的包檢測應(yīng)用程序中，說明經(jīng)過真實(shí)網(wǎng)絡(luò)數(shù)據(jù)來檢測算法的改進(jìn)成果。結(jié)果表明了改進(jìn)算法的有效性。

關(guān)鍵詞： 正則表達(dá)式； 深度包檢測； DFA 模式； 內(nèi)存使用

中圖分類號(hào)： TN915.08?34； TP3 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）05?0087?06

Improvement of regular expression matching algorithm for deep packet inspection

ZHANG Wei1， CHEN Jiao2， ZHAO Mei?kai2

（1. China Southern Power Grid Science Academy， Guangzhou 510080， China； 2. Space Star Technology Co.， Ltd.， Beijing 100086， China）

Abstract： Content inspection technology for network data packet has been widely used in network security， network monitoring， HTTP load balancing， etc. In content scanning of data packet， the payload data of the packet needs to be matched by a set of the specified regular expressions. The problem existing in the current data packet inspection is elaborated in this paper. That is， the traditional application program of data packet inspection needs a large memory space to store the corresponding regular expression pattern. A improved algorithm that effectively reduces memory space usage is proposed. The application of the improved algorithm in DFA?based packet inspection program indicates the improvement achievements， which were obtained by detection of the true network data.

Keywords： regular expression； deep packet inspection； DFA pattern； memory usage

0 引 言

網(wǎng)絡(luò)數(shù)據(jù)包的內(nèi)容檢測對于網(wǎng)絡(luò)安全和網(wǎng)絡(luò)監(jiān)視軟件來說是一個(gè)至關(guān)重要的技術(shù)。在這些軟件中，它們已經(jīng)定義好了一系列的關(guān)于應(yīng)用程序分級、病毒、網(wǎng)絡(luò)協(xié)議等的模式集合，用來檢測匹配網(wǎng)絡(luò)的實(shí)時(shí)數(shù)據(jù)。

就目前來說，正則表達(dá)式[1]模式已經(jīng)漸漸成為數(shù)據(jù)包檢測程序的首選，正在慢慢替代明確的字符串匹配[2]模式。正則表達(dá)式模式具備了對相應(yīng)模式超強(qiáng)的表達(dá)力和描述的靈活性。例如，L7?filter[3]（在Linux中對數(shù)據(jù)流進(jìn)行分類的應(yīng)用程序），使用模式匹配算法把進(jìn)入設(shè)備的數(shù)據(jù)包應(yīng)用層內(nèi)容與事先定義好的協(xié)議規(guī)則進(jìn)行比對，如果匹配成功就說明這個(gè)數(shù)據(jù)包屬于某種協(xié)議。Snort[4]入侵檢測系統(tǒng)也已經(jīng)從以前不使用正則表達(dá)式規(guī)則集到現(xiàn)在大量使用正則表達(dá)式規(guī)則集了，還有一些其他的入侵檢測系統(tǒng)，如Bro[5]，同樣也使用正則表達(dá)式作為它的模式描述語言。

隨著正則表達(dá)式在數(shù)據(jù)包內(nèi)容檢測方面得到廣泛的采用，它的匹配數(shù)據(jù)包凈載數(shù)據(jù)的速度應(yīng)該與包頭處理的線性速度保持一致，顯得非常重要。但目前現(xiàn)存的大多數(shù)相應(yīng)軟件的凈載數(shù)據(jù)檢測速度都不能滿足線性要求。例如，當(dāng)L7?filter的70個(gè)協(xié)議過濾器同時(shí)生效時(shí)，系統(tǒng)的吞吐量小于10 Mb/s，僅僅相當(dāng)于局域網(wǎng)的傳輸速度。并且，需耗用超過90%的CPU使用時(shí)間去匹配正則表達(dá)式，只留給程序執(zhí)行入侵檢測和監(jiān)視很少的使用時(shí)間。另一方面，最近一些快速匹配字符串的算法有了一定發(fā)展，但它們只是關(guān)注明確的字符串匹配，這些算法并不能簡單地?cái)U(kuò)展到正則表達(dá)式中。

在網(wǎng)絡(luò)數(shù)據(jù)包檢測過程中，正則表達(dá)式模式匹配效率很低的原因如下：

（1） 在許多指定的匹配網(wǎng)絡(luò)數(shù)據(jù)的模式中使用了很多不同的通配符（例如，“.” ，“*”）。由于大量使用通配符，導(dǎo)致當(dāng)正則表達(dá)式被轉(zhuǎn)化成模式匹配狀態(tài)機(jī)時(shí)，其產(chǎn)生的Deterministic Finite Automaton（DFA）[6]的復(fù)雜度呈幾何倍數(shù)增長。

（2） 大多數(shù)通配符的使用都有不同長度的限制，導(dǎo)致更多資源被使用。

（3） 不同的字符組被公共的使用，如有字符集包涵所有可打印的字符和空格符，影響了字符集或通配符的使用，這種相互影響將導(dǎo)致高復(fù)雜度狀態(tài)機(jī)的產(chǎn)生。

本文將著重分析如何避免正則表達(dá)式模式匹配在數(shù)據(jù)包內(nèi)容檢測上的問題，并優(yōu)化其算法。此外還提出一個(gè)基于DFA的優(yōu)化內(nèi)存使用的高速匹配解決方案?；谝陨系姆治?，提出針對某些特定正則表達(dá)式的兩條重寫規(guī)則。最后實(shí)驗(yàn)證明，通過重寫的正則表達(dá)式所構(gòu)建的DFA將大大提高數(shù)據(jù)包內(nèi)容檢測軟件的匹配速度[7]。

1 問題闡述

1.1 正則表達(dá)式

正則表達(dá)式是指一個(gè)用來描述或者匹配一系列符合某個(gè)句法規(guī)則的字符串的單個(gè)字符串。表1列出了在數(shù)據(jù)包內(nèi)容檢測中所用的正則表達(dá)式元字符的特殊含義。

將兩個(gè)匹配條件進(jìn)行邏輯“或”（Or）運(yùn)算＼&例如正則表達(dá)式（him|her） 匹配"it belongs to him"和"it belongs to her"，但是不能匹配"it belongs to them."。＼&.＼&匹配任何單個(gè)字符＼&正則表達(dá)式r.t匹配這些字符串：rat、rut、r t，但是不匹配root。＼&？＼&匹配0或1個(gè)正好在它之前的那個(gè)字符＼&＼&*＼&匹配0或多個(gè)正好在它之前的那個(gè)字符。＼&正則表達(dá)式.*意味著能夠匹配任意數(shù)量的任何字符。＼&{}＼&匹配指定數(shù)目的字符，這些字符是在它之前的表達(dá)式定義的。＼&正則表達(dá)式A[0?9]{3} 能夠匹配字符"A"后面跟著正好3個(gè)數(shù)字字符的串，＼&[]＼&匹配括號(hào)中的

任何一個(gè)字符。＼&正則表達(dá)式r[aou]t匹配rat、rot和

rut，但是不匹配ret。＼&[^]＼&匹配除了指定區(qū)間之外的字符＼&正則表達(dá)式[^269A?Z] 將匹配除了2、6、9和所有大寫字母之外的任何字符。＼&]

1.2 正則表達(dá)式實(shí)現(xiàn)

有窮自動(dòng)機(jī)是一種比較完美的實(shí)現(xiàn)正則表達(dá)式的形式。它分為兩種：一種是確定的有窮自動(dòng)機(jī)DFA（Deterministic Finite Automaton）；另一種是不確定的有窮自動(dòng)機(jī)NFA（Nondeterministic Finite Automaton）。下面詳細(xì)說明這兩種自動(dòng)機(jī)是如何實(shí)現(xiàn)正則表達(dá)式的：

一個(gè)DFA包括：一個(gè)有限的輸入字符表，用Σ表示；一個(gè)有限的狀態(tài)集合；一個(gè)轉(zhuǎn)移函數(shù)[δ。]在網(wǎng)絡(luò)應(yīng)用程序中，[Σ]包括所有擴(kuò)展ASCII碼的28個(gè)字符表，在狀態(tài)集中，有惟一的一個(gè)開始狀態(tài)[q0]和一個(gè)接收狀態(tài)集合。轉(zhuǎn)移函數(shù)是使自動(dòng)機(jī)從某一狀態(tài)，因輸入一個(gè)字符而返回另一狀態(tài)。DFA的一個(gè)重要的特征是無論何時(shí)自動(dòng)機(jī)只存在一個(gè)活動(dòng)狀態(tài)。另一個(gè)自動(dòng)機(jī)NFA與DFA的執(zhí)行機(jī)制很相似，其區(qū)別在于它的轉(zhuǎn)移函數(shù)δ可以從一個(gè)狀態(tài)和一個(gè)輸入字符返回一個(gè)新的狀態(tài)的集合，因此，NFA允許同時(shí)存在多個(gè)活動(dòng)狀態(tài)。

當(dāng)一個(gè)長度為[n]正則表達(dá)式被轉(zhuǎn)換成DFA時(shí)，最壞情況下，狀態(tài)的復(fù)雜度[8]為[O（n），]另外，一個(gè)長度同樣為[n]的正則表達(dá)式NFA轉(zhuǎn)換成DFA時(shí)，它的狀態(tài)復(fù)雜度為[O（Σn）。]并且對于DFA來說，每一個(gè)輸入的字符執(zhí)行的復(fù)雜度為[O（1），]但是對于NFA，當(dāng)所有[n]個(gè)狀態(tài)同時(shí)為活動(dòng)狀態(tài)時(shí)，每一個(gè)輸入字符的執(zhí)行復(fù)雜度為[O（n2）。]

2 解決問題

在本文中，將尋找一種快速的內(nèi)存使用高效的數(shù)據(jù)包內(nèi)容檢測正則表達(dá)式匹配方案，下面給出此種方案適用問題的范圍。

本文采用以DFA來實(shí)現(xiàn)正則表達(dá)式匹配的方案，因?yàn)镹FA方案對于順序化處理器或者有限的并行化處理器來說效率是非常低的。這里的目標(biāo)是使每個(gè)輸入自動(dòng)機(jī)的字符都要以[O（1）]的代價(jià)來執(zhí)行，但是就目前而言，由于DFA過大的內(nèi)存占用導(dǎo)致不可能完成此目標(biāo)。因此，本文將重點(diǎn)研究減小DFA的內(nèi)存占用，以此來使每個(gè)輸入的字符都已[O（1）]的代價(jià)來執(zhí)行。

本文還將關(guān)注在通用的處理器架構(gòu)下，限制正則表達(dá)式匹配速度的原因。并且還要關(guān)注在多核處理器上的移植性，因?yàn)槎嗪瞬⑿刑幚硪呀?jīng)成為處理器的發(fā)展趨勢。

在DFA的內(nèi)存資源占用方面有兩個(gè)因素值得關(guān)注，它們是狀態(tài)量和轉(zhuǎn)移量。轉(zhuǎn)移量是隨狀態(tài)量線性增加的，因?yàn)閷τ诿恳粋€(gè)狀態(tài)這里都存在最多28個(gè)下一個(gè)轉(zhuǎn)移到的狀態(tài)。因此本文認(rèn)為DFA的狀態(tài)量是直接決定DFA內(nèi)存使用量的主要因素。

3 單獨(dú)模式匹配優(yōu)化

3.1 提出概念

盡管正則表達(dá)式和自動(dòng)機(jī)理論能夠直接應(yīng)用于數(shù)據(jù)包檢測，但是應(yīng)該注意到它們應(yīng)用的不同之處。目前大多數(shù)的研究都主要關(guān)注在檢測某個(gè)定長的字符串是否匹配已定義好的正則表達(dá)式。更明確地說，如果某個(gè)定長的字符串通過了正則表達(dá)式DFA的匹配過程，就認(rèn)為它是符合該正則表達(dá)式語言的。但是相比之下，在數(shù)據(jù)包檢測當(dāng)中，一個(gè)正則表達(dá)式可以匹配整個(gè)輸入的字符串，也可以匹配輸入字符串的某個(gè)子串，則都符合DFA的匹配過程。這個(gè)字串沒有已知的開始和結(jié)束的位置，因此DFA為了匹配所有可能的子串，將導(dǎo)致復(fù)雜度大幅度提高。

為了能更好地理解本文提出的優(yōu)化方案，下面給出實(shí)現(xiàn)子串匹配的幾個(gè)不同的的標(biāo)準(zhǔn)和DFA對于子串匹配的幾種執(zhí)行模式。

3.1.1 實(shí)現(xiàn)匹配的標(biāo)準(zhǔn)

已知一個(gè)正則表達(dá)式模式和一個(gè)輸入字符串，一個(gè)完整的匹配結(jié)果應(yīng)包括所有可能與正則表達(dá)式匹配的子串。例如，已知一個(gè)模式為ca*和一個(gè)輸入為caaa，匹配結(jié)果應(yīng)包括ca，caa，caaa。則稱這種匹配標(biāo)準(zhǔn)為完全性匹配[9]，它的正式定義如下：

完全性匹配：已知一個(gè)處理函數(shù)[M，]以一個(gè)模式[P]和一個(gè)輸入字符串[S]作為參數(shù)，生成了一個(gè)屬于[S]的子串集，表示為{[M（P，S）={]S是[S]的子串|S能被[P]的DFA所接受}。

實(shí)際上，在大多數(shù)應(yīng)用程序中并不要求包含所有的匹配結(jié)果，可能只需要一個(gè)這樣的結(jié)果。因此本文給出了一個(gè)新的標(biāo)準(zhǔn)，即非重復(fù)性匹配，它將放寬完全式匹配的要求。

非重復(fù)性匹配：已知一個(gè)處理函數(shù)[M，]以一個(gè)模式[P]和一個(gè)輸入字符串[S]作為參數(shù)，生成了任意一個(gè)屬于[S]的子串，簡單的說，[M（P，S）={S]的子串[Si|]任意[Si，][Sj]能被[P]的DFA所接受，[Si∩Sj=?}。]

如果一個(gè)模式出現(xiàn)在輸入字符串的多個(gè)位置，這個(gè)匹配過程將給出所有非重復(fù)性的匹配子串。例如，已知一個(gè)模式ca*和一個(gè)輸入caaa，三個(gè)匹配都有一個(gè)重復(fù)的前綴ca，因此，非重復(fù)匹配將得到三個(gè)匹配中的一個(gè)。

對于大多數(shù)數(shù)據(jù)包檢測程序而言，一個(gè)非重復(fù)性匹配已經(jīng)足夠，因?yàn)檫@些程序僅僅為了探測是否存在網(wǎng)絡(luò)入侵襲擊，或者是否在應(yīng)用層出現(xiàn)某個(gè)匹配。事實(shí)上，比如說檢測工具grep和flex，系統(tǒng)Snort和Bro都用的是非重復(fù)性匹配的特殊情況，如左最長匹配，或者左最短匹配。本文采取的是左最短匹配，非重復(fù)性匹配能很好地構(gòu)建一個(gè)內(nèi)存使用更高效的DFA。

3.1.2 DFA執(zhí)行子串匹配的方式

下而將關(guān)描述的是一類不以“^”開頭的模式。這類模式中，它并不知道要匹配的子串是否或者在輸入字符串什么位置將出現(xiàn)，對于這類模式，DFA可以采取不同的兩種方式去執(zhí)行：

（1） 重復(fù)查找。一個(gè)DFA可以通過一個(gè)模式經(jīng)過標(biāo)準(zhǔn)的構(gòu)建技術(shù)所生成。為了去尋找應(yīng)匹配的子串，DFA將反復(fù)查找整個(gè)的輸入字符串：即從字符串的開始部分查找，直到遇到以下兩種情況結(jié)束：它已經(jīng)輸出了所有可能的子串匹配（在完全式匹配情況下）或找到一個(gè)可能的匹配（在非重復(fù)性匹配）；它遇到輸出的結(jié)尾。這種DFA重復(fù)掃描的方式通常在語言匹配[10]處理中使用。但是對于數(shù)據(jù)包內(nèi)容檢測來說效率是相當(dāng)?shù)偷摹?/p>

（2） 一次查找。在這種方式中，模式都是以“.*”開頭的，這表示它可能在輸出字符串的任何位置被匹配，DFA將被這種擴(kuò)展的模式所創(chuàng)建，因?yàn)镈FA只需要一遍對輸入字符串的查找，他就能獲得所有在不同位置匹配的子串。使用這種一次查找的方式，它能取得的每個(gè)字符的計(jì)算復(fù)雜度都為O（1），因此其非常適合網(wǎng)絡(luò)應(yīng)用程序。為了能成功獲得對字符串的很高的檢測率，本文就采取的是這種查找方式。

3.2 單獨(dú)正則表達(dá)式生成DFA解析

下面重點(diǎn)研究一些數(shù)據(jù)包內(nèi)容檢測應(yīng)用程序（比如：Linux L7?filter，Snort和Bro）的幾種模式所生成DFA的復(fù)雜度。它們使用的匹配標(biāo)準(zhǔn)和匹配方式是完全性匹配和一次查找。表2為研究結(jié)果。

確定的字符串模式生成DFA的復(fù)雜度與該字符串的字符數(shù)呈線性關(guān)系。

如果一個(gè)匹配模式以“^”開頭，那么它所構(gòu)造DFA與兩個(gè)因素有關(guān)：一個(gè)是模式的整體長度[k，]一個(gè)是通配符所限制的通配字符串個(gè)數(shù)[j。]本文通過對現(xiàn)有包檢測程序的匹配規(guī)則的研究發(fā)現(xiàn)，通常模式長度[k]是有限的，但通配符匹配長度[j]通常可以達(dá)到幾百個(gè)甚至上千個(gè)。因此，情況4導(dǎo)致DFA的復(fù)雜度為[j]的平方數(shù)量級。

如果模式是以“.*”開始的，所生成的DFA的復(fù)雜度與通配符匹配數(shù)量呈指數(shù)級增長。

下面將重點(diǎn)分析后兩種情況狀態(tài)數(shù)量的激增原因。

3.2.1 平方級狀態(tài)數(shù)量的DFA結(jié)構(gòu)

通常的觀念認(rèn)為如果匹配模式以“^”開頭，那么它生成的DFA將是一個(gè)狀態(tài)數(shù)量比較少的簡單的DFA，從表2中可看出，第4種情況盡管是以“^”開頭的模式，但它存在這一個(gè)可以循環(huán)多次任意匹配的字符前綴集，這仍然使它產(chǎn)生了一個(gè)復(fù)雜的DFA。下面考慮這樣一個(gè)例子，模式^B+[^＼n]{3}D，其中[^＼n]是一個(gè)匹配除了（＼n）以外的任意字符。它所產(chǎn)生的相應(yīng)的DFA有平方數(shù)量級個(gè)狀態(tài)，圖1描述了一個(gè)它的狀態(tài)轉(zhuǎn)化圖。

產(chǎn)生平方級的復(fù)雜度是因?yàn)槟Ｊ街凶址鸅的可重復(fù)匹配與三次[^＼n]的匹配集相互重疊，因此產(chǎn)生了模式的內(nèi)在的匹配模糊[11]。第二個(gè)B字符既可以認(rèn)為是匹配B+的一部分，又可以是認(rèn)為是匹配[^＼n]{3}的一部分。因此，如果一個(gè)輸入字符串包括多個(gè)B字符，DFA需要去記住B字符的具體個(gè)數(shù)和準(zhǔn)確的輸入位置，這樣才能準(zhǔn)確的匹配接下來的輸入字符。如果一個(gè)可重復(fù)匹配的字符集的匹配限制次數(shù)是j，那么DFA需要O（j2）數(shù)量級個(gè)狀態(tài)去記住輸入字符B的第一個(gè)和最后一個(gè)。

在實(shí)際應(yīng)用程序模式集中的相似結(jié)構(gòu)：

實(shí)際上在Snort中有大量的模式規(guī)則集屬于這類情況。例如，匹配NNTP規(guī)則的正則表達(dá)式“^SEARCH＼s+[^＼n]{1 024}”，與圖1所示的例子很相似，＼s+與[^＼n]處于重疊的狀態(tài)。輸入的空格符既可以匹配＼s+部分又可以匹配[^＼n]{1 024}部分，這導(dǎo)致了模糊的產(chǎn)生。簡單地說，如果一個(gè)輸入字符串在輸入“SEARCH”后輸入了1 024個(gè)空格符，又輸入了1 024個(gè)字符A，那么將可能產(chǎn)生1 024個(gè)匹配的子串。如，一個(gè)空格符去匹配＼s+，剩下的空格符去匹配[^＼n]{1 024}部分，或者兩個(gè)空格符去匹配＼s+，剩下的空格符去匹配[^＼n]{1 024}部分等。需要10242狀態(tài)去記錄所有可能空格符的序列，這樣生成的DFA才能滿足所有不同長度的字符匹配需求。注意所有子串都要以SEARCH開頭，然后以不同長度重復(fù)匹配。

僅僅通過構(gòu)建NFA是無法解決平方級個(gè)狀態(tài)問題的，也就是說，相應(yīng)的NFA需要1 042個(gè)狀態(tài)，在這些狀態(tài)當(dāng)中，一部分去匹配SEARCH，一部分去匹配＼s+，還需要1 024個(gè)狀態(tài)去記錄[^＼n]{1 024}的匹配個(gè)數(shù)，但是一個(gè)黑客可以很容易地構(gòu)建一個(gè)以“SEARCH”為開頭，緊接著1 024個(gè)空格符的輸入。這將導(dǎo)致＼s+狀態(tài)和所有1 023個(gè)非接受狀態(tài)（因?yàn)榭崭穹诮Y(jié)束匹配之前可以重復(fù)1 023次）同時(shí)處于活動(dòng)狀態(tài)，在匹配接下來的一個(gè)字符時(shí)，NFA需要去相繼檢測這1 024個(gè)狀態(tài)，然后計(jì)算新的活動(dòng)狀態(tài)組，這將導(dǎo)致很低的執(zhí)行效率。這個(gè)問題也不能通過固定字符串預(yù)先匹配機(jī)制來解決（Snort使用這種機(jī)制）。這是因?yàn)轭A(yù)先過濾只能識(shí)別固定字符串“SEARCH”是否存在于輸入字符串中。之后，DFA或者NFA匹配機(jī)制仍然需要指出輸入是否匹配這個(gè)模式并且指出這個(gè)子串是什么。另外一個(gè)選擇是在識(shí)別“SEARCH”前綴后，要記錄隨后要處理的字符。這個(gè)方法同樣也不能解決問題，因?yàn)槊總€(gè)包含該前綴的數(shù)據(jù)包都要觸發(fā)這個(gè)計(jì)數(shù)過程。另外，一些黑客能很容易地構(gòu)建具有同樣這種前綴數(shù)據(jù)包，去觸發(fā)大量的這個(gè)處理過程，導(dǎo)致網(wǎng)絡(luò)癱瘓。

3.2.2 指數(shù)級狀態(tài)數(shù)量的DFA

許多數(shù)據(jù)包檢測模式都包含一個(gè)匹配任意個(gè)字符的開端，圖2顯示了這樣一個(gè)模式所構(gòu)建的DFA的狀態(tài)轉(zhuǎn)移全過程，例子模式為“.*A.{2}CD”。

模式中的兩個(gè)通配符一共需要（22+1）個(gè)狀態(tài)來記錄所有可能的匹配形式。因?yàn)樵诓粩囗樞蜃x取輸入的字符串時(shí)，必須考慮之前讀取字符串的所有可能影響最終匹配結(jié)果的不同前置輸入。如，一個(gè)前置輸入AAB與一個(gè)ABA的前置輸入是不同的，因?yàn)楫?dāng)隨后輸入的是字符串BCD時(shí)，它與前一個(gè)所構(gòu)成的字符串（AABBCD）是一個(gè)合法的匹配結(jié)果，但與后一個(gè)前置串構(gòu)成的字符串（ABABCD）就是一個(gè)非法的匹配結(jié)果。通常情況下，如果一個(gè)模式以“.*”開端，其中還包含可以匹配j個(gè)任意字符的通配符，那么它將需要O（2j）個(gè)狀態(tài)去滿足DFA的匹配要求。比如相似情況的模式還可能有“.*A[A-Z]{j}D”。

在實(shí)際應(yīng)用程序模式集中的相似結(jié)構(gòu)：

在入侵檢測系統(tǒng)Snort中，有53.8%的匹配模式包含可重復(fù)匹配指定次數(shù)的字符集。其中80%是以“^”開頭的模式，它們將不會(huì)導(dǎo)致指數(shù)級狀態(tài)的增長，但需要注意的是，仍有20%的模式?jīng)]有以“^”開端，它將導(dǎo)致狀態(tài)激增的問題。如，用于檢測TMAP協(xié)議數(shù)據(jù)包是否溢出的測試規(guī)則，它使用的正則表達(dá)式是“.*AUTH＼s[^＼n]{100}”。這個(gè)規(guī)則是用于探測任意一個(gè)包含AUTH，然后是一個(gè)空格符，最后是100個(gè)非換行符的字符串的輸入。如果直接用它生成一個(gè)DFA，將需要超過10 000個(gè)狀態(tài)去記錄所有可能的匹配結(jié)果，它是匹配AUTH＼s的第一個(gè)AUTH＼s。因?yàn)榭赡艹霈F(xiàn)這樣的情況：第二個(gè)AUTH＼s即能匹配[^＼n]{100}，也可能作為一個(gè)新的正則表達(dá)式模式的開始。很顯然，指數(shù)級狀態(tài)的增長問題也不能通過構(gòu)建NFA的方式所解決[12]。圖3顯示了“.*AUTH＼s[^＼n]{100}”以NFA構(gòu)建的狀態(tài)轉(zhuǎn)移實(shí)例。

因?yàn)榈谝粋€(gè)狀態(tài)可能伴隨著輸入產(chǎn)生無數(shù)個(gè)自循環(huán)，如“AUTH＼sAUTH＼sAUTH＼s…”將導(dǎo)致大量的狀態(tài)同時(shí)處于活動(dòng)狀態(tài)，大大降低了系統(tǒng)的執(zhí)行速度。與表2中的情況4相似，這個(gè)問題也不能通過固定字符串預(yù)先匹配機(jī)制來解決。

3.3 優(yōu)化重寫正則表達(dá)式

本文已經(jīng)詳細(xì)分析了傳統(tǒng)的模式在數(shù)據(jù)包檢測過程中所構(gòu)建的DFA的規(guī)模很大的具體原因。在這一部分，將探究一種優(yōu)化正則表達(dá)式模式的方案，從而大大降低DFA的規(guī)模。這個(gè)方案的關(guān)鍵就是將傳統(tǒng)模式中的完全性匹配標(biāo)準(zhǔn)改用非重復(fù)性匹配來實(shí)現(xiàn)。尤其是將重點(diǎn)實(shí)現(xiàn)兩類正則表達(dá)式模式的優(yōu)化重寫。一種是表2提到的情況4：平方級狀態(tài)復(fù)雜度，另一種是表2提到的情況5：指數(shù)級狀態(tài)復(fù)雜度。這兩種情況可以進(jìn)行優(yōu)化重寫的一個(gè)共同特點(diǎn)是，它們的后綴可以匹配一個(gè)字符集的指定次數(shù)，這與它們的前綴匹配相重疊。這樣的情況廣泛存在于現(xiàn)實(shí)的一些數(shù)據(jù)包檢測程序中如Snort，Bro。對于這樣的模式，3.2部分所提到的NFA和預(yù)先過濾方式都不能提高它們的匹配效率，下面所提出的優(yōu)化重寫規(guī)則能成功的將平方級和指數(shù)級復(fù)雜度降為線性復(fù)雜度。

3.3.1 優(yōu)化規(guī)則一

本文在第3.2節(jié)所提到的匹配模式“^SEARCH ＼s+[^＼n]{1 024}”將產(chǎn)生一個(gè)與重復(fù)匹配次數(shù)（這里為1 024次）成平方級規(guī)模的DFA。

通常情況下，這類模式是用于檢測數(shù)據(jù)包緩沖區(qū)是否溢出[13]，因此本文用非重復(fù)性匹配標(biāo)準(zhǔn)去檢測是否溢出，是非常高效的而又不失準(zhǔn)確性的一種替代方法?；谶@個(gè)觀點(diǎn)，可以等價(jià)地將“^SEARCH＼s+[^＼n]{1 024}”優(yōu)化重寫成“^SEARCH＼s[^＼n]{1 024}”。這個(gè)新的模式表明，在匹配完第一個(gè)空格符后，不管以后的輸入字符串是什么，則開始匹配計(jì)數(shù)[^＼n]{1 024}。用以前的模式匹配，很容易就確定每一個(gè)可能匹配的子串s是很困難的一件事情，不過對于新模式所產(chǎn)生的匹配子串s′而言，不是與s保持一致，就是s的一個(gè)前綴。換句話說，新的模式是采用左最短非重復(fù)性匹配的標(biāo)準(zhǔn)執(zhí)行的。這樣，新模式所產(chǎn)生的狀態(tài)數(shù)量與重復(fù)次數(shù)j成線性關(guān)系，因?yàn)橐呀?jīng)消除了對＼s的匹配不確定性。最后，本文確定可以將諸如“^A+[A-Z]{j}” 形式的正則匹配模式優(yōu)化改寫為“^A[A-Z]{j}”形式。在實(shí)際程序Snort中，本文重新改寫了17個(gè)相似的模式。

3.3.2 優(yōu)化規(guī)則二

在3.2節(jié)中討論了像“.*AUTH＼s[^＼n]{100}”這種模式產(chǎn)生指數(shù)級數(shù)量狀態(tài)，是因?yàn)樗仨氂涗洀牡谝粋€(gè)AUTH＼s開始隨后所有的AUTH＼s。如果同樣使用非重復(fù)性匹配標(biāo)準(zhǔn)，在匹配完第一個(gè)AUTH＼s后不用去記錄第二個(gè)AUTH＼s。首先，如果在接下來的100輸入的字符中存在＼n，匹配結(jié)束，第二個(gè)AUTH＼s一定包含在這100字符當(dāng)中。其次，如果在接下來的100個(gè)字符中不包括＼n，那么第一個(gè)AUTH＼s和接下來的字符可以完成一次匹配過程。因此可以將模式改寫成只去獲取一次前綴的匹配模式。這樣改寫可以消除大量的去處理記錄隨后AUTH＼s的狀態(tài)，從而簡化了DFA，如圖4所示。

4 改進(jìn)效果驗(yàn)證

首先從常用的網(wǎng)絡(luò)數(shù)據(jù)檢測程序中挑選3個(gè)有代表性的復(fù)雜的模式集。第1個(gè)是從Linux L?7filter中選取了用于檢測不同網(wǎng)絡(luò)協(xié)議的70個(gè)正則表達(dá)式模式。第2個(gè)是從Snort中挑選了1 555個(gè)用于入侵檢測的正則表達(dá)式模式[14]，最后一個(gè)是Bro入侵檢測系統(tǒng)的所有2 781個(gè)正則表達(dá)式模式。并且從實(shí)際網(wǎng)絡(luò)中獲取了數(shù)以百萬級數(shù)據(jù)包進(jìn)行測試。

從這三個(gè)模式集中發(fā)現(xiàn)一些可以用3.3節(jié)提到的優(yōu)化重寫規(guī)則進(jìn)行改寫的模式，在Snort中有71個(gè)規(guī)則需要被重寫，在Bro中有49個(gè)模式需要被重寫。這120模式中，其中有17個(gè)適用于優(yōu)化規(guī)則一，它們將從平方級的狀態(tài)數(shù)量下降為線性數(shù)量。另外103種適用于優(yōu)化規(guī)則二，它們將大大降低DFA的內(nèi)存使用，從而滿足大部分的個(gè)人電腦系統(tǒng)。表3具體顯示了優(yōu)化效果。

5 結(jié) 語

本文以實(shí)際存在的包檢測程序中的正則表達(dá)式模式為基礎(chǔ)，通過優(yōu)化重寫規(guī)則的運(yùn)用，大大提高了應(yīng)用程序的執(zhí)行效率。但是本文并沒有證明優(yōu)化規(guī)則適用于所有可能導(dǎo)致DFA規(guī)模激增的模式，優(yōu)化規(guī)則可能還并不通用，但這些優(yōu)化重寫規(guī)則經(jīng)過試驗(yàn)確實(shí)可以提高Snort和Bro的執(zhí)行效率，如果要有新的模式導(dǎo)致DFA規(guī)模的激增，還要根據(jù)具體模式的結(jié)構(gòu)加以分析，具體問題還需具體分析，從而進(jìn)行改進(jìn)。

參考文獻(xiàn)

[1] FIREDL J E F.精通正則表達(dá)式[M].北京：電子工業(yè)出版社，2009.

[2] THOMAS H， CORMEN C E， LEISERSON R L， et al. Introduction to algorithms [M]. 2nd ed. Beijing： Machinery Industry Press， 2006： 557?568.

[3] LEVANDOSKI J， SOMMER E， STRAIT M. Application layer packet classifier for Linux [EB/OL]. [2014?10?14]. http：//l7?filter.sourceforge.net.

[4] Snort Team. Snort network intrusion detection system [EB/OL]. [2014?10?14]. http：//www.snort.org.

[5] The Bro Project. The bro network security monitor [EB/OL]. [2014?10?14]. https：//www.bro.org/documentation/index.html.

[6] ALFRED V， AHO M S， SETHI Lam Ravi， et al. Compilers： principles， techniques and tools [M]. 2nd ed. Beijing： Machi?nery Industry Press， 2009： 93?96.

[7] 劉更樓，丁常福，婁建國.基于狀態(tài)檢測的防火墻系統(tǒng)研究[J].航空計(jì)算技術(shù)，2009，43（1）：122?125.

[8] WU S， MANBER U. A fast algorithm for multi?pattern sear?ching， TR?94?17 [R]. Arizona： University of Arizona， 2005.

[9] ASOKAN N. Fairness in electronic commerce [D]. Waterloo： Waterloo University， 2006.

[10] LARSSON N J. Structures of string matching and data compression [EB/OL]. [2011?12?16]. http：// www.docin.com...926.html.

[11] BAKER Z K， PRASANNA V K. Automatic synthesis of efficient intrusion detection systems on FPGAs [C]// 14th International Conference on Field Prog Logic and Applications. [S.l.]： [s.n.]， 2004： 311?321.

[12] HOPCROFT J E， ULLMAN J D. Introduction automata theory， languages， and computation [M]. [S.l.]： Addison Wesley， 1984.

[13] 李文嘉，謝高崗，張大方.一種基于數(shù)據(jù)包分析的網(wǎng)絡(luò)入侵檢測探針[J].同濟(jì)大學(xué)學(xué)報(bào)，2002，27（10）：185?191.

[14] 吳薄峰.Snort入侵檢測實(shí)用解決方案[M].北京：機(jī)械工業(yè)出版社，2005.