基于FPGA的可配置正則表達式匹配引擎的設計.pdf

1、正則表達式具有較強的靈活性、邏輯性及功能性，是一種字符串匹配模式，可以迅速地用較簡單的方式來表述復雜的字符串。正則表達式多用于入侵檢測系統(tǒng)及文本處理等。一般地，都是采用軟件方式來實現(xiàn)正則表達式的匹配。然而，隨著網(wǎng)絡帶寬的大幅度提高、網(wǎng)絡數(shù)據(jù)流量的劇增以及云計算技術等的快速發(fā)展，軟件實現(xiàn)的方式成了正則表達式高速匹配的瓶頸。而硬件由于其并行化工作的特點，可以用于快速處理模式的匹配，因此成為研究人員設計、構造匹配引擎的新載體。
　　FP

2、GA由于其特殊結(jié)構及具有可重復配置等特性，現(xiàn)多用于高速多數(shù)據(jù)處理的場合。本文介紹了采用FPGA來實現(xiàn)正則表達式匹配的方法。論文首先對正則表達式構造自動機的幾種經(jīng)典算法進行了簡述。在分析對比各自優(yōu)缺點之后提出了一種新的NFA構造算法，該算法的空間復雜度理論上為O（n），時間復雜度為O（n2）。且構造生成的NFA的規(guī)模數(shù)相對很小，其中狀態(tài)數(shù)比正則表達式中含有的普通字符數(shù)n要少，轉(zhuǎn)換數(shù)約等于n。有且只有一個終止狀態(tài)。其次對在FPGA中實現(xiàn)匹配

3、的過程進行了研究，提出了構建匹配子模塊的設計，生成匹配子模塊庫。該設計可以大大節(jié)約后續(xù)設計過程中的時間成本，加快入侵檢測系統(tǒng)中的特征模式的更新速度。對于一些特殊結(jié)構的正則表達式，論文給出了設計中的一些優(yōu)化方案以節(jié)約實現(xiàn)中的硬件資源。最后利用論文中構建的子模塊庫，分別采用新算法S-NFA和經(jīng)典的Thompson算法對正則表達式進行處理，生成對應的NFA。論文的第四章給出了將NFA進行邏輯化處理的方法，以適用于硬件化的處理。搭建Testbe

4、nch測試平臺，對各實例進行測試并給出了仿真結(jié)果，從得到的NFA規(guī)模以及實際匹配延時兩個方面對新的算法進行了評價。
　　綜上所述，本文在對正則表達式匹配技術的研究基礎之上，提出了一種新的NFA構造算法及NFA的邏輯化處理方法，構建了匹配子模塊庫，通過仿真實驗對該子模塊庫進行了驗證，并比較了S-NFA算法和Thompson算法的性能。結(jié)果表明S-NFA算法在構造過程、生成的NFA的規(guī)模以及應用后的實際延時等方面要優(yōu)于傳統(tǒng)的Thomp