基于FPGA的正則表達式匹配引擎設計

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

1.引言

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

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

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

2.設計原理

2.1 多字符的并行處理

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

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

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

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

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

2.2 “失效狀態”的概念

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

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

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

2.3 Bloom Filter和分類匹配

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

表1 L1和L2到達的狀態表

表2 未優化的AB.*CD狀態轉移表

表3 優化后的AB.*CD狀態轉移表

表4 測試結果

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

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

基于以上考慮，本文設計了一種內部匹配與Bloom Filter并行的匹配結構，如圖2所示。

圖1 *Atuo的DFA

圖2 內部匹配與Bloomfilter的并行結構圖

圖3 存儲的信息結構

圖4 系統總體結構圖

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

3.總體結構設計

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

4.性能測試

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

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

5.結束語

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

[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]張偉.支持多正則表達式匹配的硬件結構[J].清華大學學報(自然科學版)2009,49(10):1704-1707.

[6]張樹壯.一種面向網絡安全檢測的高性能正則表達式匹配算法[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和概率分發隊列的P2P網絡快速查找算法[J].計算機科學,2012,39(5):57-61.