基于FPGA的可配置正則表達(dá)式匹配引擎的設(shè)計(jì).pdf

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

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

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

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