杭州電子科技大學電子信息學院 王奇敏 李訓根 趙 海斌

1.引言

基于模式匹配的入侵檢測系統(tǒng)是將入侵的行為和手段表達為一種模式和特征，然后檢測網(wǎng)絡上的數(shù)據(jù)是否與既定的模式相匹配。正則表達式匹配是模式匹配的一種，因其豐富和靈活的表達能力在模式匹配中得到廣泛應用。最初的正則表達式匹配引擎大多是基于軟件的，但是通用處理器的發(fā)展遠遠跟不上網(wǎng)絡數(shù)據(jù)流量的增長?；谲浖恼齽t表達匹配引擎的吞吐率越來越跟不上日益增長的網(wǎng)絡數(shù)據(jù)流量，所以基于硬件的正則表達匹配引擎逐漸成為國內(nèi)外學者研究的熱點。

自1982年Floyd和Ullman[1]首次在硬件上實現(xiàn)一個分層的NFA模型起，正則表達式的硬件匹配技術(shù)已得到了長足地發(fā)展。Sidhu和Prasanna[2]設(shè)計了針對正則表達式中“或”、“循環(huán)”、“連接”3個基本操作的專用電路，并基于基本操作提出了一個NFA專用匹配電路結(jié)構(gòu)。Christopher L.Hayes等人提出了一種能夠減少存儲空間且能夠有很高匹配速率的正則表達式匹配結(jié)構(gòu)。國內(nèi)的學者也研究出了不少高性能的正則 表達式匹配引擎。清華大學的張 偉[5]等人提出了一種硬件四級流水線的多正則表達式匹配結(jié)構(gòu)；張樹壯[6]等人提出了一種基于猜測—驗證的正則表達式匹配結(jié)構(gòu)。

目前，正則表達式匹配的硬件實現(xiàn)方法主要有兩種：基于純硬件專用匹配電路和基于存儲器查詢。前者的特點是占用資源比較少，不需要大容量存儲器，匹配速度快，但缺點同樣明顯，即重構(gòu)性差，只能針對特定的正則表達式，有局限性。基于存儲器查詢的方法可以解決前者的不可重構(gòu)性和局限性的問題，但是它需要大容量存儲器的支持。并且，存儲器訪問頻率的限制和大量狀態(tài)信息的存儲已成為基于存儲器查詢的正則表達式匹配引擎性能提高的瓶頸。本文在前人研究的基礎(chǔ)上，利用硬件的可并行特點，設(shè)計了一種可以多字符同時處理的正則表達匹配結(jié)構(gòu)。并且結(jié)合Bloom filter的思想，對狀態(tài)機進行了過濾和分類匹配，引入了“失效狀態(tài)”的概念，在一定程度上解決了以上的兩個瓶頸問題。

2.設(shè)計原理

2.1 多字符的并行處理

假設(shè)，待檢測的字符串為“FiniteAutomata”，模式串為“.*Auto”。那么模式串“.*Auto”的DFA如圖1所示。

一般情況下，必須把字符串進行逐個匹配，設(shè)一次狀態(tài)轉(zhuǎn)移需要消耗的時鐘周期為M，那么共需消耗M*N（N為字符串長度，這里N=14）個時鐘周期?，F(xiàn)在把字符串平均分成兩段，L1=FiniteA和L2=utomata，如表1所示。

然后進行如下處理，第一步，讓L1和L2從0狀態(tài)開始進行并行匹配，并且記錄L2達到過的狀態(tài)；第二步，以L1的末狀態(tài)為首狀態(tài)，繼續(xù)對L2進行匹配，并且每到達一個狀態(tài)與第一步中L2在該字符到達的狀態(tài)比較。如果兩個狀態(tài)相同，那么就可以跳過后面的字符，直接開始下一個字符串的匹配。

這種方法是正確的。①當模式串只包含在L1或L2中時，第一步就可以把模式串匹配出來。②當模式串被拆散在L1和L2中的情況下，因為第二步繼續(xù)匹配的起始狀態(tài)為L1的末狀態(tài)，所以同樣能匹配出來。③假設(shè)，第二步中找到的相同狀態(tài)為Si，因為對于同一DFA，在同一狀態(tài)下，輸入同一個字符，能到達的下一個狀態(tài)是確定的[7]，所以在Si以后的狀態(tài)在第一步的L2中都已到達過，可以直接跳過。

從表1可以看到，用此方法來處理字符串“FiniteAutomata”時，消耗的時鐘周期為11*M，比直接逐個處理的方法節(jié)省了22%的時間。當用正則表達式狀態(tài)機來匹配網(wǎng)絡數(shù)據(jù)流時，匹配的概率是很低的，所有的正則表達式開始于一個單一的初始狀態(tài)，大量狀態(tài)轉(zhuǎn)換會回到初始狀態(tài)或與初始狀態(tài)相鄰的狀，且許多狀態(tài)接受同樣的字符會轉(zhuǎn)移到相同的目的狀態(tài)[7]。因此，當進行第二步處理時，有很高的概率可以較早得到達相同狀態(tài)。最好情況下，把待處理的字符串分成兩段，速度就可以提高一倍；分成四段，速度就可以提高三倍。

2.2 “失效狀態(tài)”的概念

當正則表達式編譯成DFA狀態(tài)機時，會引起狀態(tài)爆炸，狀態(tài)信息的存儲面臨著巨大地挑戰(zhàn)。本文對狀態(tài)信息的存儲進行了優(yōu)化，引入了“失效狀態(tài)”的概念，有效地節(jié)省了狀態(tài)信息存儲占用的空間。先舉一個簡單的例子，如表2所示為“AB.*CD”的狀態(tài)轉(zhuǎn)移表。狀態(tài)2就是由“.*”引入的狀態(tài)，也是當多條表達式編譯時引起狀態(tài)爆炸的地方。如果我們對每個狀態(tài)的每條轉(zhuǎn)移都進行存儲，狀態(tài)2就需要有256條有效轉(zhuǎn)移，如表2所示。

現(xiàn)在我們引入“失效狀態(tài)”的概念，即把每個狀態(tài)有效轉(zhuǎn)移條數(shù)最多的那個下一狀態(tài)定為此狀態(tài)的“失效狀態(tài)”。這樣只需存儲“失效狀態(tài)”，不存儲大量的轉(zhuǎn)移信息。對于表2所示的例子，狀態(tài)2的“失效狀態(tài)”就是狀態(tài)2，簡化后的狀態(tài)轉(zhuǎn)移表就如表3所示，空格的地方就不需要再存儲，明顯地減少了狀態(tài)信息存儲所需的空間。

單獨編譯一條正則表達式時不存在狀態(tài)爆炸的問題，但當多條正則表達式一起編譯成一個DFA時，有些元字符就會引起狀態(tài)爆炸：“.*”會導致DFA狀態(tài)數(shù)的線性增加，“.{}”和“[]{}”會導致DFA狀態(tài)數(shù)的指數(shù)級增加，而每個狀態(tài)又會包含大量的轉(zhuǎn)移信息。snort規(guī)則庫中14%的規(guī)則包含“.*”，1%的規(guī)則包含“.{}”和“[]{}”[7]，“失效狀態(tài)”的引入可以很大程度地節(jié)省狀態(tài)信息的存儲空間。

2.3 Bloom Filter和分類匹配

Snort規(guī)則庫中的正則表達式的DFA需要占用龐大的存儲資源，F(xiàn)PGA內(nèi)部的存儲資源有限，而過多地訪問外部存儲器成為硬件匹配結(jié)構(gòu)提高吞吐率的瓶頸之一。正則表達式匹配應用于網(wǎng)絡入侵檢測系統(tǒng)時，具有以下特點：①在大量的網(wǎng)絡數(shù)據(jù)流中，存在入侵行為的概率是很低的；②當正則表達式規(guī)則庫編譯成一個DFA進行匹配時，所有的正則表達式開始于一個單一的初始狀態(tài)，大量狀態(tài)轉(zhuǎn)換徘徊在初始狀態(tài)或與初始狀態(tài)相鄰的狀態(tài)，以及一些特殊的狀態(tài)，這些狀態(tài)只是DFA少量的一部分，需要的存儲空間也比較小，而大量的遠離初始狀態(tài)的狀態(tài)被訪問到的概率很小，且需要大量的存儲資源。

表1 L1和L2到達的狀態(tài)表

表2 未優(yōu)化的AB.*CD狀態(tài)轉(zhuǎn)移表

表3 優(yōu)化后的AB.*CD狀態(tài)轉(zhuǎn)移表

表4 測試結(jié)果

Bloom Filter是一種基于多個哈希函數(shù)映射，復雜度很小的隨機數(shù)據(jù)結(jié)構(gòu)[10]。用Bloom filter結(jié)構(gòu)可以大大減少系統(tǒng)訪問外部存儲器的次數(shù)，并且高效利用片上資源。但是Bloom filter的使用必須要控制假陽性誤判率和匹配概率，誤判率的公式為：

其中k為哈希函數(shù)的個數(shù)，m為存儲空間的位數(shù)，n為存入的元素個數(shù)。

基于以上考慮，本文設(shè)計了一種內(nèi)部匹配與Bloom Filter并行的匹配結(jié)構(gòu)，如圖2所示。

圖1 *Atuo的DFA

圖2 內(nèi)部匹配與Bloomfilter的并行結(jié)構(gòu)圖

圖3 存儲的信息結(jié)構(gòu)

圖4 系統(tǒng)總體結(jié)構(gòu)圖

我們對snort規(guī)則庫中的正則表達式的DFA進行了統(tǒng)計和分 類，把適量淺層次和被訪問概率比較大的狀態(tài)信息存在片上ram，大量深層次的被訪問到概率小的狀態(tài)信息存在外部RAM。狀態(tài)轉(zhuǎn)移表內(nèi)存儲的信息如圖3（a）所示，Bloom Filter內(nèi)存儲的信息如圖3（b）所示。Bloom Filter與內(nèi)配匹配模塊并行運行，當內(nèi)部匹配模塊和Bloom Filter都不匹配時就可以直接跳轉(zhuǎn)到失效狀態(tài)，當內(nèi)部匹配模塊匹配時就可以直接查詢到下一狀態(tài)，當內(nèi)部匹配模塊不匹配，但Bloom Filter出現(xiàn)匹配是就需查詢外部RAM。這樣可以大大減少系統(tǒng)訪問外部RAM的次數(shù)，同時充分利用了片上資源。

3.總體結(jié)構(gòu)設(shè)計

系統(tǒng)的總體方案設(shè)計如圖4所示。在數(shù)據(jù)輸入模塊用以太網(wǎng)接口接受數(shù)據(jù)，用兩個RAM組對輸入數(shù)據(jù)緩存，進行乒乓操作，實現(xiàn)內(nèi)部數(shù)據(jù)的無縫連接。內(nèi)部狀態(tài)轉(zhuǎn)移表和Bloom Filter信息的存儲都用運了hash映射，使信息存儲更加緊湊，采用的hash函數(shù)為H3哈希函數(shù)組。理論上在多字符并行處理時需要多個狀態(tài)轉(zhuǎn)移表與之對應，但是基于實際考慮，本文設(shè)計的匹配結(jié)構(gòu)需要訪問片外狀態(tài)轉(zhuǎn)移表的頻率很低，所以本文在FPGA內(nèi)部設(shè)計了一個多路的虛擬狀態(tài)轉(zhuǎn)移表，而只使用一個片外RAM，在不怎么影響系統(tǒng)性能的前提下，節(jié)省系統(tǒng)所需的資源。

4.性能測試

在現(xiàn)有實驗條件下，我們在FPGA上對系統(tǒng)的綜合性能進行了模擬驗證和測試，并且與現(xiàn)有的方法進行了對比。使用的FPGA是Altera Cyclone II EP2C35F484C8，片外RAM是Micron的SDRAM，系統(tǒng)時鐘為50MHZ。測試結(jié)果如表4所示。

p_seed表示輸入字符對狀態(tài)機中深層結(jié)點的訪問概率；L表示并行處理的字符數(shù)，即輸入字符串的分段數(shù)。Hybrid-FA是參考文獻[6]中作者提出的一種比較先進的正則表達式匹配方法。從圖中可以明顯看出，在系統(tǒng)頻率為50MHZ時，一般情況下（p_seed=3%），本文設(shè)計的匹配引擎的吞吐率明顯高于文獻[6]提出的匹配方法；在比較極端的情況下（p_seed=50%），本文設(shè)計的匹配引擎也能較好地保持匹配速度。當系統(tǒng)頻率達到250MHZ，L=4時，該匹配引擎的最高吞吐率就能到達1.63Gb/s。另外，經(jīng)測試與對比，本文設(shè)計的正則表達引擎的存儲效率也有一定的提高。

5.結(jié)束語

本文針對當前正則表達式匹配的硬件實現(xiàn)所遇到的兩個瓶頸問題，設(shè)計了一種時空高效的正則表達式匹配結(jié)構(gòu)。該匹配系統(tǒng)的匹配速度快，可重構(gòu)，配置靈活。只要更新存儲器里的狀態(tài)信息就可以匹配新的正則表達式。在正常情況下，只要提高L的值，增加內(nèi)部匹配模塊的信息量就能提高系統(tǒng)的吞吐率。本系統(tǒng)的局限性在于當受到惡意攻擊的時候，系統(tǒng)性能將會有所下降，這也是需要進一步考慮的地方。另外，本文雖然提出了一種提高狀態(tài)信息存儲效率的方法，但只做了理論分析和簡單的定性測試，未給出定量的測試結(jié)果，這也是本文進一步要開展的工作。

[1]Floyd R W,Ullman J D.The Compilation of Regular Expressions into Integrated Circuits[J].Journal of theACM,1982,29(3):603-622.

[2]Sidhu,R,Prasanna,V.K.Fast Regular Expression Matching using FPGAs:the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines,2001[C].USA:Rohnert Park,California,2001:227-238.

[3]Joao B,Ioannis S,Cardoso J M,etal.Regular expression matching for reconfigurable packet inspection:Proceedings of IEEE International Conference on Field-Programmable Technology(FPT),2006[C].Thailand:Bangkok,2006:119-126.

[4]Tsern-Huei Lee.Hardware Architecture for High-Performance Regular Expression Matching[J].IEEE TRANSACTIONS ON COMPUTERS,2009,58(7):984-993.

[5]張偉.支持多正則表達式匹配的硬件結(jié)構(gòu)[J].清華大學學報(自然科學版)2009,49(10):1704-1707.

[6]張樹壯.一種面向網(wǎng)絡安全檢測的高性能正則表達式匹配算法[J].計算機學報,2010,33(10):1976-1986.

[7]YAO YUAN.Survey on storage-oriented regular expressions matching algorithms[J].Journal of Computer Applications,2009,29(12):3171-3173.

[8]Harmapurikai D,Lockwood S.Fast and scalable Pattern Matching for Network instrusion Detection Systems[J].IEEE,2006,24(10):1781-1792.

[9]Michela Becchi.A Hybrid Finite Automaton for Practical Deep Packet Inspection:CONEXT 2007[C].New York,NY,U.S.A.2007.10-13.

[10]程瀾綿,周峰.基于Bloom Filter和概率分發(fā)隊列的P2P網(wǎng)絡快速查找算法[J].計算機科學,2012,39(5):57-61.