基于膨脹系數(shù)的正則表達式分組算法

王美陽，唐學(xué)文，楊正益

(1.重慶大學(xué)計算機學(xué)院，重慶 400030;2.重慶大學(xué)信息與網(wǎng)絡(luò)管理中心，重慶 400030;3.重慶大學(xué)軟件學(xué)院，重慶 401331)

0 引言

隨著網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展以及網(wǎng)絡(luò)應(yīng)用的復(fù)雜多樣，深度包檢測(Deep Packet Inspection，DPI)在防火墻、入侵檢測系統(tǒng)、網(wǎng)絡(luò)審計等網(wǎng)絡(luò)安全領(lǐng)域的應(yīng)用越來越廣泛。正則表達式(Regular Expression，RE)[1-2]能夠靈活高效地描述字符串，逐漸取代精確字符串匹配，成為深度包檢測的重要手段之一，在開源入侵檢測系統(tǒng)Snort、Bro以及眾多網(wǎng)絡(luò)安全產(chǎn)品中都得到廣泛應(yīng)用。

正則表達式匹配引擎的工作原理是將正則表達式轉(zhuǎn)化為有限狀態(tài)機(Finite State Machine，F(xiàn)SM)，然后利用有限狀態(tài)機對檢測內(nèi)容進行掃描。正則表達式匹配有2種實現(xiàn)方式，一種是確定性有限狀態(tài)自動機(Deterministic Finite Automata，DFA)，另一種是非確定性有限狀態(tài)自動機(Non-deterministic Finite state Automata，NFA)。NFA的特點是存儲空間高效，狀態(tài)轉(zhuǎn)移路徑可以有多條，匹配的時間效率低下;DFA的特點是狀態(tài)轉(zhuǎn)移路徑最多只有一條，匹配的時間效率高，但當規(guī)則數(shù)量增多時，DFA的狀態(tài)數(shù)量呈指數(shù)增長，存儲空間需求劇增，導(dǎo)致DFA難以實際使用。

針對正則表達式匹配時存在的狀態(tài)空間爆炸問題，近些年來研究者提出了多種基于DFA的存儲高效的正則表達式匹配算法，來降低DFA的存儲空間需求。有些研究者提出的 D2FA[3]、CD2FA[4]、δFA[5]和XFA[6]等方法都是通過消除冗余的DFA狀態(tài)轉(zhuǎn)移，能夠取得良好的壓縮效果，但無法減少DFA的狀態(tài)數(shù)。Yu等人[7]首次提出DFA分組算法(下文稱之為Yu分組算法)，但搜索策略存在可改進之處。Becchi等人[8]提出一種兼顧 DFA和NFA兩者優(yōu)點的混合自動機引擎。李鯤鵬等人[9]提出基于布魯姆過濾器的正則表達式匹配算法，有效節(jié)約存儲空間，提高匹配速度，但帶來一定的誤匹配率。徐乾等人[10]提出一種選擇性分群算法來減少DFA狀態(tài)數(shù)，但算法中的調(diào)整因子難以合理設(shè)置。王磊[11]、吳鴻偉[12]等人設(shè)計了基于多GPU的正則表達式匹配引擎，提高了匹配性能，但增加了硬件成本。還有研究者設(shè)計并改進基于FPGA[13-16]架構(gòu)的正則表達式匹配技術(shù)，但FPGA時鐘頻率低于通用處理器，可伸縮性不佳。

本文在Yu算法的基礎(chǔ)上，提出一種改進型正則表達式分組算法——IGA(Improved Grouping Algorithm)算法，采用更加合理的啟發(fā)搜索策略，進一步減少DFA的狀態(tài)數(shù)目，從而降低DFA所占存儲空間。

1 Yu算法

Yu等人首先提出了正則表達式之間的相互作用這一概念，利用這一概念構(gòu)造正則表達式集合的關(guān)系圖，再對正則表達式進行分組。

定義1[7]對于正則表達式R1和R2，若#DFA，則R1與R2之間相互作用，其中#DFA(X)表示正則表達式X轉(zhuǎn)換為DFA后的狀態(tài)數(shù)，R1|R2表示正則表達式R1與R2合并之后的DFA狀態(tài)數(shù)。

Yu算法的大致流程如下:

1)計算正則表達式集合中兩兩之間的相互作用關(guān)系，構(gòu)造正則表達式集合的作用關(guān)系圖G。

2)選擇一條與其它正則表達式作用最小的正則表達式，加入到分組NG中。

3)選擇一條與分組NG連接數(shù)最少的正則表達式R。

4)將R與NG合并轉(zhuǎn)化為DFA，如果此DFA大小超過閾值，就跳轉(zhuǎn)到步驟5)，否則將R加入到NG中。

5)對G中所有的正則表達式是否檢查完畢?若是則跳轉(zhuǎn)到步驟3)，否則NG分組完畢。

6)G中是否還有未分組的正則表達式?若是則跳轉(zhuǎn)到步驟2)，否則算法完畢。

2 改進型分組算法

本文在膨脹系數(shù)(Expansion Coefficient，EC)這一概念的基礎(chǔ)上，提出改進型分組算法——IGA算法來改進Yu算法，更有效地降低DFA所占用的存儲空間。

2.1 膨脹系數(shù)

在Yu算法中的定義1僅僅根據(jù)2條正則表達式合并之后與合并之前的狀態(tài)數(shù)比較結(jié)果而得到相互作用關(guān)系，并沒有描述2條正則表達式合并之后與合并之前的狀態(tài)膨脹的劇烈程度，即沒有充分利用正則表達式之間的關(guān)系所蘊含的信息。為充分利用正則表達式之間的相互作用關(guān)系信息來構(gòu)造正則表達式集合的作用關(guān)系圖，給出膨脹系數(shù)這一定義。

定義2 對于正則表達式R1、R2，膨脹系數(shù)計算公式如下:

當膨脹系數(shù)EC＞1時，表示R1、R2相互作用。如果EC的值越大，說明2條正則表達式合并之后與合并之前相比，狀態(tài)數(shù)膨脹越厲害，因此需要盡量將R1與R2隔離，盡量不要將它們分配到同一個DFA分組里，從而減少總狀態(tài)數(shù)目。當膨脹系數(shù)EC＜1時表示R1、R2不相互作用，可以將R1、R2放在同一個分組。當膨脹系數(shù)EC=1時表示R1、R2合并之后的狀態(tài)數(shù)恰好等于合并之前的狀態(tài)數(shù)，不過這種情況出現(xiàn)的可能性很小。

2.2 IGA 算法

在膨脹系數(shù)這一概念的基礎(chǔ)上，本文設(shè)計改進型分組算法——IGA算法，偽代碼如下:

算法輸入:規(guī)模為n的正則表達式集合R

算法輸出:集合 R的分組結(jié)果 R={g1，g2，g3，…，gk}

IGA算法中的SIZE_LIMIT為各個分組DFA狀態(tài)數(shù)的閾值。第1行代碼的作用是構(gòu)建以膨脹系數(shù)為權(quán)值的關(guān)系圖。第3～5行代碼主要初始化新分組并選擇最初的2條正則表達式。第7～21行代碼的主要功能是選擇使新分組膨脹系數(shù)最小的正則表達式，判斷分組的狀態(tài)數(shù)是否超過設(shè)置的閾值，并更新新分組與集合中其他正則表達式之間的膨脹系數(shù)。

為更直觀地描述算法，假設(shè)有包含5條正則表達式的集合，計算正則表達式之間的膨脹系數(shù)，構(gòu)造相互作用關(guān)系圖，如圖1所示。

圖1 獲得分組的雙親節(jié)點

選擇膨脹系數(shù)最小的2個頂點(即表達式b和e)作為group 0的雙親，從圖G中刪除b、e兩個頂點，這樣就得到圖2。

圖2 獲得分組的孩子節(jié)點

選擇與group 0頂點相關(guān)聯(lián)的頂點并且膨脹系數(shù)最小的頂點c，從圖G中刪除頂點c，增加到group 0中，不斷重復(fù)此過程，直到group 0再添加任意一個膨脹系數(shù)最小的頂點會超過SIZE_LIMIT。如果group 0的狀態(tài)數(shù)超過SIZE_LIMIT，則建立一個新的group 1，再向group 1中添加頂點。如此重復(fù)圖1與圖2所示的過程，直到所有頂點都分組完畢。

3 實驗結(jié)果與分析

實驗采用的硬件配置為Intel Dual-Core 2.5 GHz CPU，4 GB內(nèi)存，操作系統(tǒng)為CentOS 6.2。正則表達式轉(zhuǎn)換為DFA使用的是開源軟件——由Becchi開發(fā)的Regex 1.4.1，并用 C++語言實現(xiàn)了 Yu算法與IGA算法。為了避免規(guī)則集上的不同實驗效果的影響，在不同的公開規(guī)則集上比較IGA算法的分組結(jié)果與Yu算法的分組結(jié)果。規(guī)則集分別源自開源軟件L7-filter、Snort和Bro的規(guī)則各100條。表1、表2和表3分別給出了上述3個規(guī)則集的實驗結(jié)果。

表1 L7_filter分組狀況對比

表2 Snort分組狀況對比

表3 Bro分組狀況對比

從表1、表2和表3的對比結(jié)果可以發(fā)現(xiàn)，在相同分組數(shù)的情況下，IGA算法比Yu算法的總狀態(tài)數(shù)平均能夠減少25%。DFA總狀態(tài)數(shù)減少，能夠減少存儲DFA的內(nèi)存空間，降低匹配算法的空間復(fù)雜度。

4 結(jié)束語

與Yu算法相比，IGA算法主要有以下改進:

1)IGA算法使用膨脹系數(shù)來計算表示正則表達式之間的關(guān)系，而Yu算法之間簡單地依據(jù)正則表達式合并前后狀態(tài)數(shù)是否增大來表示正則表達式之間的關(guān)系。

2)IGA算法將正則表達式加入新分組的選擇標準是膨脹系數(shù)最小，而Yu算法的選擇標準是邊連接數(shù)最少。

3)IGA算法每次更新新分組與其他正則表達式之間的膨脹系數(shù)，而Yu算法不會更新正則表達式之間的連接數(shù)。

實驗表明，與Yu算法相比，IGA算法在分組數(shù)目相同的情況下，總的DFA狀態(tài)數(shù)平均減少25%以上，降低了匹配算法的空間復(fù)雜度。下一步工作是研究高速網(wǎng)絡(luò)環(huán)境下如何利用網(wǎng)絡(luò)流的局部性來實現(xiàn)DFA分組調(diào)度算法，從而提高正則表達式匹配引擎的吞吐量。

[1] 姚遠，劉鵬，單征，等.面向存儲的正則表達式匹配算法綜述[J].計算機應(yīng)用，2009，29(12):3171-3173.

[2] 鄧凱元，姜磊.正則表達式匹配引擎性能分析[J].計算機與現(xiàn)代化，2011(7):105-107.

[3] Kumar S，Dharmapurikar S，Yu Fang，et al.Algorithms toaccelerate multiple regular expressions matching for deep packet inspection[C]//Proceedings of the 2006 ACM Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.2006:339-350.

[4] Kumar S，Turner J，Williams J.Advanced algorithms for fast and scalable deep packet inspection[C]//Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems.2006:81-92.

[5] Ficara D，Giordano S，Procissi G，et al.An improved DFA for fast regular expression matching[J].Computer Communication Review，2008，38(5):29-40.

[6] Smith R，Estan C，Jha S.XFA:Faster signature matching with extended automata[C]//Proceedings of the 2008 IEEE Symposium on Security and Privacy.2008:187-201.

[7] Yu Fang，Chen Zhifeng，Diao Yanlei，et al.Fast andmemory-efficient regularexpression matchingfordeep packet inspection[C]//Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems.2006:93-102.

[8] Becchi M，Crowley P.A hybrid finite automaton for practical deep packet inspection[C]//Proceedings of the 2007 ACM Conference on Emerging Network Experiment and Technology.2007.

[9] 李鯤鵬，蘭巨龍，李印海.基于Bloom filter的高效正則表達式匹配算法[J].計算機應(yīng)用研究，2012，29(3):950-954.

[10] 徐乾，鄂躍鵬，葛敬國，等.深度包檢測中一種高效的正則表達式壓縮算法[J].軟件學(xué)報，2009，20(8):2214-2226.

[11] 王磊，陳曙暉，蘇金樹，等.深度報文檢測中基于GPU的正則表達式匹配引擎[J].計算機應(yīng)用研究，2010，27(11):4324-4327.

[12] 吳鴻偉，郭東輝，莊進發(fā)，等.基于多GPU的正則表達式匹配技術(shù)[J].華中科技大學(xué)學(xué)報(自然科學(xué)版)，2013，41(1):51-55.

[13] Mitra A，Najjar W，Bhuyan L.Compiling PCRE to FPGA for accelerating SNORT IDS[C]//Proceedings of the 2007 ACM/IEEE Symposium on Architecture for Networking and Communications Systems.2007:127-136.

[14] Lee J，Hwang S H，Park N.A high performance NIDS using FPGA-based regular expression matching[C]//Proceedings of the 2007 ACM Symposium on Applied Computing.2007:1187-1191.

[15] Dan Lo C，Tai Yi-Gang，Psarris K.Hardware implementation for network intrusion detection rules with regular expression support[C]//Proceedings of the 2008 ACM Symposium on Applied Computing.2008:1535-1539.

[16] 唐球，姜磊，譚建龍，等.FPGA實現(xiàn)的正則表達式匹配性能分析[J].小型微型計算機系統(tǒng)，2012，33(11):2405-2409.