邵翔宇,劉勤讓,譚力波
(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,河南鄭州450002)
?
基于規(guī)則模板的正則表達(dá)式分組算法
邵翔宇,劉勤讓,譚力波
(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,河南鄭州450002)
摘要:采用規(guī)則分組的方法解決確定型有限自動(dòng)機(jī)(Deterministic Finite Automata,DFA)狀態(tài)爆炸問題,隨著分組數(shù)目的增加,匹配效率大大降低.本文提出正則表達(dá)式的輸入驅(qū)動(dòng)特性理論,并基于此提出了基于規(guī)則模板的分組算法——模板有限自動(dòng)機(jī).模板有限自動(dòng)機(jī)算法基于規(guī)則模板對規(guī)則集進(jìn)行分組,各分組分別構(gòu)建匹配引擎.理論分析和實(shí)驗(yàn)表明,與典型的DFA改進(jìn)算法相比,預(yù)處理時(shí)間和存儲空間有2~3個(gè)數(shù)量級別的縮減,且匹配效率沒有明顯降低.
關(guān)鍵詞:正則表達(dá)式;確定型有限自動(dòng)機(jī);分組自動(dòng)機(jī);擴(kuò)展有限自動(dòng)機(jī);多維有限自動(dòng)機(jī);規(guī)則模板
在網(wǎng)絡(luò)信息安全領(lǐng)域,入侵檢測系統(tǒng)(Intrusion Detection Systems,IDS)扮演著重要的角色,它采用深度包檢測(Deep Packet Inspection,DPI)方法進(jìn)行病毒檢測、入侵識別等.隨著攻擊模式的多樣化,最早的基于精確字符串匹配方式已經(jīng)無法滿足要求,正則表達(dá)式以其強(qiáng)大的、靈活的表達(dá)能力而得到廣泛應(yīng)用.但隨著網(wǎng)絡(luò)帶寬逐年增加、規(guī)則數(shù)目的快速增長以及正則表達(dá)式表達(dá)功能的強(qiáng)大,DPI應(yīng)用中的正則表達(dá)式匹配(Regular Expression Matching,REM)面臨嚴(yán)峻挑戰(zhàn),其中最為急迫的是如何滿足高速網(wǎng)絡(luò)數(shù)據(jù)包處理的要求.有限自動(dòng)機(jī)分為非確定性有限自動(dòng)機(jī)(Non-deterministic Finite Automata,NFA)和確定性有限自動(dòng)機(jī)(Deterministic Finite Automata,DFA)兩種,其中DFA與NFA相比在任意時(shí)刻只有一個(gè)活躍狀態(tài)、處理一個(gè)字符只需要一次遷移,具有線速的匹配性能,適用于高速數(shù)據(jù)鏈路中的REM.
將多條正則表達(dá)式編譯成一個(gè)DFA時(shí),由于各條規(guī)則之間的相互重疊和影響,會導(dǎo)致狀態(tài)爆炸問題.YU等人[1]分析了這種爆炸問題,提出對正則表達(dá)式規(guī)則進(jìn)行分組的mDFA(Multiple DFAs)算法.mDFA是基于規(guī)則之間的膨脹情況而進(jìn)行的分組,各分組采用DFA進(jìn)行匹配,這種分組無法進(jìn)行徹底的存儲壓縮,且會造成分割成的組數(shù)目過多,降低分組算法匹配效率.
本文提出了正則表達(dá)式匹配引擎的輸入驅(qū)動(dòng)特性理論,針對當(dāng)前單一算法無法針對整個(gè)規(guī)則集進(jìn)行有效的存儲壓縮問題,提出了基于規(guī)則模板的正則表達(dá)式分組算法—模板自動(dòng)機(jī)(Templates based Finite Automata,TFA).TFA算法將規(guī)則模板作為正則表達(dá)式分組的依據(jù),各分組采用的特定改進(jìn)算法進(jìn)行匹配.
2.1狀態(tài)爆炸問題
正則表達(dá)式規(guī)則集在編譯成一個(gè)DFA時(shí),產(chǎn)生狀態(tài)爆炸的規(guī)則主要有兩類:計(jì)數(shù)器型爆炸和克林閉包型爆炸,這兩種爆炸類型嚴(yán)重制約著DFA在IDS中的應(yīng)用.
在IDS中DFA的構(gòu)造[2]中,狀態(tài)爆炸通常在NFA子集構(gòu)造時(shí)產(chǎn)生,按照構(gòu)造角度來分,解決DFA狀態(tài)爆炸問題方案有以下4個(gè)方向:分組算法[1,3,4],不確定度調(diào)節(jié)算法[5,6],狀態(tài)轉(zhuǎn)移表(State Transition Table,STT)壓縮算法[7~9],自動(dòng)機(jī)結(jié)構(gòu)改進(jìn)算法[10~12].以上四類算法可以很大程度壓縮存儲空間,但無法針對整個(gè)規(guī)則集進(jìn)行有效的存儲壓縮.在自動(dòng)機(jī)結(jié)構(gòu)改進(jìn)算法中,針對這兩類爆炸類型各自有比較有效的壓縮算法:針對計(jì)數(shù)器型爆炸改進(jìn)的擴(kuò)展有限自動(dòng)機(jī)(eXtended Finite Automata,XFA)算法[10],針對克林閉包型爆炸改進(jìn)的多維立方體自動(dòng)機(jī)(Multi-dimensional Finite Automata,MFA)算法[11].
XFA算法通過增加計(jì)數(shù)器型標(biāo)記避免計(jì)數(shù)器部分狀態(tài)的重復(fù)描述,達(dá)到對計(jì)數(shù)器部分狀態(tài)的對數(shù)級別縮減.XFA存在一定的規(guī)則受限性,對其他規(guī)則類型的爆炸類型的壓縮效果不明顯.
MFA算法解決克林閉包型規(guī)則聯(lián)合編譯造成的爆炸問題.MFA通過在多維空間構(gòu)造聯(lián)合DFA,利用聯(lián)合狀態(tài)轉(zhuǎn)移圖的對稱性達(dá)到壓縮存儲空間的目的.MFA算法構(gòu)建的多維模型針對克林閉包型爆炸進(jìn)行冗余狀態(tài)壓縮,但存在一定的規(guī)則受限性,無法解決計(jì)數(shù)器等類型的爆炸問題.
2.2正則表達(dá)式輸入驅(qū)動(dòng)特性
規(guī)則和文本是正則表達(dá)式匹配引擎的兩個(gè)輸入,采用有限自動(dòng)機(jī)實(shí)現(xiàn)的正則表達(dá)式匹配引擎的存儲空間和帶寬受輸入的影響,如圖1所示.NFA接收一個(gè)字符時(shí)帶寬主要決定于激活狀態(tài)集合內(nèi)的狀態(tài)數(shù)目,而激活的狀態(tài)數(shù)目與字符所達(dá)到的狀態(tài)位置有關(guān),其匹配時(shí)間最差為O(n2),DFA在任何文本輸入下處理一個(gè)字符的時(shí)間都為常數(shù)O(1),因此NFA的匹配時(shí)間受輸入文本影響.NFA狀態(tài)數(shù)目與規(guī)則長度n呈線性關(guān)系,DFA不同類型的規(guī)則編譯產(chǎn)生的狀態(tài)數(shù)是不同的,因此DFA狀態(tài)數(shù)目受輸入規(guī)則影響.
基于以上所述NFA和DFA的特性,本文給出正則表達(dá)式匹配引擎輸入驅(qū)動(dòng)特性的定義.正則表達(dá)式匹配引擎的帶寬(匹配時(shí)間)受文本驅(qū)動(dòng),造成處理一個(gè)字符的時(shí)間變化,則稱該正則表達(dá)式匹配引擎為文本驅(qū)動(dòng)(text directed)引擎.正則表達(dá)式匹配引擎的空間復(fù)雜度(狀態(tài)數(shù)目和存儲空間)受規(guī)則類型影響,而產(chǎn)生不同的狀態(tài)數(shù)目,則稱該正則表達(dá)式匹配引擎為規(guī)則驅(qū)動(dòng)(signature directed)引擎.
表1列出了當(dāng)前幾類代表性算法的輸入驅(qū)動(dòng)特性.自動(dòng)機(jī)結(jié)構(gòu)改進(jìn)算法中XFA執(zhí)行的操作符受輸入文本影響,造成不同輸入文本的匹配時(shí)間有所不同; MFA所處狀態(tài)的受輸入文本影響,造成匹配時(shí)間有所不同,但是兩者最差匹配時(shí)間復(fù)雜度為常數(shù)級別,可以認(rèn)為屬于弱文本驅(qū)動(dòng).
單一的算法是無法針對所有規(guī)則同時(shí)消除其規(guī)則驅(qū)動(dòng)和文本驅(qū)動(dòng)特性,無法同時(shí)達(dá)到存儲空間和匹配時(shí)間的下界.基于匹配引擎的驅(qū)動(dòng)特性,有兩種提高自動(dòng)機(jī)匹配效率的改進(jìn)思路:(1)輸入文本控制:通常輸入文本是需要待匹配的數(shù)據(jù)流,不受匹配引擎的控制,但是可以在文本進(jìn)入匹配引擎之前進(jìn)行文本預(yù)篩選,從而減小輸入文本對匹配時(shí)間的影響;(2)輸入規(guī)則控制:通常輸入規(guī)則用于匹配病毒或惡意代碼,輸入規(guī)則的減少會嚴(yán)重影響引擎匹配的準(zhǔn)確性,可以運(yùn)行多個(gè)匹配引擎,保證規(guī)則的完整性.
分組算法是對輸入規(guī)則控制的一種算法.通常為了盡可能最大程度隔離規(guī)則,需要較多的分組和較多的DFA引擎來完成對全部規(guī)則的覆蓋,這也不可避免降低匹配引擎的匹配速度.本文對分組算法中DFA引擎進(jìn)行改進(jìn),采用當(dāng)前算法中DFA改進(jìn)算法進(jìn)行匹配引擎構(gòu)造,改變分組算法的分組依據(jù)、降低分組數(shù)目,在保持分組算法規(guī)則高覆蓋率的同時(shí),提高分組算法匹配效率.由于XFA、MFA在各自適用的規(guī)則內(nèi)能消除規(guī)則驅(qū)動(dòng)特性,且不存在嚴(yán)重的文本驅(qū)動(dòng)特性,將XFA 和MFA兩種匹配算法同時(shí)應(yīng)用在分組算法的匹配引擎中,達(dá)到更好的存儲壓縮效果.
表1 當(dāng)前算法的輸入驅(qū)動(dòng)特性
3.1基于規(guī)則模板的分組算法
針對DFA中最嚴(yán)重兩種類型的爆炸問題,本文通過設(shè)定模板(template),按照XFA、MFA的適用規(guī)則特點(diǎn)進(jìn)行規(guī)則分組,然后將各分組規(guī)則按照XFA、MFA、DFA構(gòu)造自動(dòng)機(jī),形成模板自動(dòng)機(jī)TFA匹配引擎.圖2給出了TFA算法的模型,其中包含:規(guī)則分組、匹配引擎構(gòu)建、匹配過程.
規(guī)則分組
TFA規(guī)則分組就是根據(jù)規(guī)則模板對規(guī)則集進(jìn)行文本處理,從規(guī)則集中查找出符合規(guī)則模板的各條規(guī)則,形成三個(gè)規(guī)則子集的過程.規(guī)則模板是一組正則表達(dá)式規(guī)則,用于查找包含特定類型的規(guī)則.由于引擎中XFA和MFA算法的特點(diǎn),用于規(guī)則分組模板的設(shè)定將直接影響TFA算法的效率,TFA的規(guī)則模板設(shè)定為計(jì)數(shù)器型模板和克林閉包型模板.
通過計(jì)數(shù)器模板篩選出的都是包含計(jì)數(shù)器的正則表達(dá)式規(guī)則,可以通過XFA實(shí)現(xiàn)聯(lián)合編譯;通過克林閉包模板篩選出的包含克林閉包型規(guī)則,可以采用MFA算法進(jìn)行聯(lián)合編譯;其他不膨脹規(guī)則可以簡單采用DFA來實(shí)現(xiàn).
引擎構(gòu)造
將三組預(yù)處理規(guī)則分別按照XFA、MFA和聯(lián)合DFA構(gòu)造自動(dòng)機(jī),形成三個(gè)正則表達(dá)式匹配引擎.其中XFA的構(gòu)造方法,按照文獻(xiàn)[10]中的方案.而MFA的構(gòu)造方法是:以克林閉包規(guī)則的一個(gè)DFA(single-DFA)為一個(gè)維度,以每個(gè)規(guī)則的“.*”對應(yīng)的狀態(tài)為交點(diǎn),構(gòu)造一個(gè)在多維空間的跳轉(zhuǎn)結(jié)構(gòu).DFA構(gòu)造方法參照基本流程構(gòu)建聯(lián)合DFA.
匹配過程
待匹配數(shù)據(jù)送入系統(tǒng)之后,匹配判決會將相同的數(shù)據(jù)送入三個(gè)匹配引擎中,三個(gè)匹配引擎的進(jìn)行相對獨(dú)立的匹配過程.由于各個(gè)引擎匹配結(jié)果產(chǎn)生的時(shí)間會有所不同,需要匹配判決模塊根據(jù)系統(tǒng)的實(shí)際要求進(jìn)行判決.
3.2性能分析
衡量正則表達(dá)式算法性能主要有三個(gè)方面:預(yù)處理時(shí)間、存儲空間和匹配時(shí)間.TFA預(yù)處理時(shí)間即規(guī)則分組,是用正則表達(dá)式處理引擎規(guī)則文本的處理過程,處理時(shí)間較短.因此,本文從TFA存儲(狀態(tài))空間和TFA匹配時(shí)間來分析TFA算法復(fù)雜度.
存儲空間(狀態(tài))復(fù)雜度
自動(dòng)機(jī)的儲存主要用于記錄狀態(tài)及其跳轉(zhuǎn)信息,存儲占用與狀態(tài)數(shù)目直接相關(guān),存儲壓縮最有效的方式是減少狀態(tài)數(shù)目.
在包含l條計(jì)數(shù)器的規(guī)則中,XFA針對計(jì)數(shù)部分進(jìn)行的改進(jìn),其他部分與DFA相同.XFA需要輔助的計(jì)數(shù)器空間,計(jì)數(shù)器重復(fù)次數(shù)為x,則占用log2x,因此存儲空間復(fù)雜度SXFA-S1
在包含m條克林閉包的規(guī)則中,MFA需要存儲m 個(gè)DFA、m條坐標(biāo)軸信息和2個(gè)動(dòng)態(tài)狀態(tài),因此MFA存儲空間SMFA-S2
S3中n條DFA之間不會產(chǎn)生爆炸,因此SDFA-S3與QDFA-S3一致,因此TFA存儲空間復(fù)雜度STFA為SXFA-S1、SMFA-S2、SDFA-S3之和
因?yàn)橛?jì)數(shù)器型改寫后的DFA不產(chǎn)生爆炸,采用計(jì)數(shù)器對限定部分描述會造成空間節(jié)省,TFA算法存儲空間與規(guī)則數(shù)呈線性關(guān)系.
匹配時(shí)間復(fù)雜度
XFA的匹配時(shí)間取決于當(dāng)前狀態(tài)的標(biāo)志位操作,XFA中賦值、復(fù)位和計(jì)數(shù)的處理時(shí)間為常數(shù),因此XFA匹配時(shí)間復(fù)雜度為常數(shù)級別O(1).MFA的匹配時(shí)間長短取決于當(dāng)前狀態(tài)所處位置,交點(diǎn)與非交點(diǎn)處理時(shí)間不一致,但交點(diǎn)最差處理時(shí)間為常數(shù),因此MFA匹配時(shí)間復(fù)雜度為O(1).DFA匹配時(shí)間復(fù)雜度為常數(shù)O(1).而TFA的匹配時(shí)間三者的匹配時(shí)間之和,因此其最差匹配時(shí)間復(fù)雜度應(yīng)為常數(shù)級別O(1)+ O(1)+ O(1).
表2列出了TFA算法的時(shí)空復(fù)雜度,并將DFA和NFA作為對比.由表可見,TFA算法與NFA的存儲空間復(fù)雜度類似,屬于非規(guī)則驅(qū)動(dòng)引擎;同時(shí)與DFA匹配時(shí)間復(fù)雜度一致,與輸入有較弱的相關(guān)性,因此,TFA算法在消除規(guī)則驅(qū)動(dòng)特性同時(shí)并未引起嚴(yán)重的文本驅(qū)動(dòng)特性,可以達(dá)到較好存儲壓縮效果.
仿真實(shí)驗(yàn)主要分為兩部分:實(shí)驗(yàn)一主要是與mDFA算法對比,驗(yàn)證TFA分組算法的分組有效性;實(shí)驗(yàn)二是與經(jīng)典改進(jìn)算法對比,驗(yàn)證TFA算法的效率.本文提出的規(guī)則模板分組算法是一種樸素的分組算法,參照實(shí)際IDS中各類規(guī)則比例,從實(shí)際IDS中選取40條規(guī)則作為測試規(guī)則集,包含20條精確型規(guī)則、10條克林閉包型規(guī)則和10條計(jì)數(shù)器型規(guī)則.
本文采用Becchi提供的軟件RegEx Processor[13],分別實(shí)現(xiàn)了NFA、DFA、mDFA、Hybrid-FA、D2FA以及本文的TFA算法.利用RegEx Processor自帶的tracegen工具生成1GB的測試數(shù)據(jù),用于匹配時(shí)間的測試.
實(shí)驗(yàn)一TFA與mDFA算法對比
對比TFA與mDFA兩種分組算法.通過更改閾值設(shè)定不同的mDFA算法分組數(shù)目.如表3所示,mDFA算法的預(yù)處理時(shí)間和狀態(tài)數(shù)目隨著分組數(shù)目的增加而減少;但隨著分組數(shù)目的增加,匹配時(shí)間與分組數(shù)目基本呈線性關(guān)系.如圖3所示的算法匹配時(shí)間和狀態(tài)數(shù)目二維圖上,TFA相比于mDFA更加靠近坐標(biāo)軸原點(diǎn),說明TFA可以在不降低匹配效率的情況下縮減狀態(tài)數(shù)目,可以避免mDFA分組數(shù)目過多造成的效率下降問題,TFA分組算法比mDFA更有優(yōu)勢.
實(shí)驗(yàn)二TFA與經(jīng)典算法對比
對比的算法包含mDFA(m = 6)、Hybrid-FA、D2FA以及NFA和DFA.如表4所示,在預(yù)處理時(shí)間方面,TFA與mDFA時(shí)間相當(dāng),比Hybrid-FA、D2FA算法有幾個(gè)數(shù)量級的縮減,實(shí)時(shí)更新能力最強(qiáng);存儲空間方面,TFA比Hybrid-FA、D2FA算法降低了2~3個(gè)數(shù)量級;匹配時(shí)間較基于DFA的算法DFA、Hybrid-FA無明顯增加.如圖4所示的算法匹配時(shí)間和狀態(tài)數(shù)目二維圖上,相比于其他DFA改進(jìn)算法TFA達(dá)到了存儲空間和匹配速率更好的折中,算法匹配效率更好.
表3 TFA與mDFA對比
表4 TFA與經(jīng)典算法對比
本文通過對算法的驅(qū)動(dòng)特性進(jìn)行分析,提出了基于規(guī)則模板的分組算法TFA,TFA算法基于規(guī)則模板進(jìn)行分組,各分組的實(shí)現(xiàn)采用DFA及改進(jìn)算法.理論分析和實(shí)驗(yàn)結(jié)果表明,TFA能在不降低匹配效率的情況下,達(dá)到mDFA的空間壓縮效果,同時(shí)避免了分組數(shù)目過多造成的效率下降問題.與經(jīng)典的改進(jìn)算法相比,TFA預(yù)處理時(shí)間和存儲空間比Hybrid-FA、D2FA算法降低了2~3個(gè)數(shù)量級;匹配時(shí)間與基于DFA的算法DFA、Hybrid-FA數(shù)量級相當(dāng).
本文提出的分組方法是一種基于DFA的樸素正則表達(dá)式匹配算法,而對于既是計(jì)數(shù)型也是閉包型的規(guī)則,基于DFA的分組方案無法進(jìn)行有效的狀態(tài)數(shù)目壓縮.因此,對TFA內(nèi)部算法引擎的優(yōu)化,對所有規(guī)則類型進(jìn)行更加有效的存儲壓縮,是下一步的工作方向.
參考文獻(xiàn)
[1]Yu F,Chen Z,Diao Y,et al.Fast and memory-efficient regular expression matching for deep packet inspection[A].Proc of the IEEE/ACM Symp on Architectures for Networking and Communications Systems[C].IEEE,2006.93 -102.
[2]Hopcroft J E.Introduction to Automata Theory,Languages,and Computation[M].Pearson Addison Wesley,2007.
[3]徐乾,鄂躍鵬,葛敬國.深度包檢測中一種高效的正則表達(dá)式壓縮算法[J].軟件學(xué)報(bào),2009,20(8): 2214 -2226.Xu Q,E Y,Ge J.Efficient regular expression compression algorithm for deep packet inspection[J].Journal of Software,2009,20(8): 2214 -2226.(in Chinese)
[4]喬登科,王卿,柳廳文,等.基于狀態(tài)分組的高效i - DFA構(gòu)造技術(shù)[J].通信學(xué)報(bào),2013,34(8): 102 -109.Qiao D,Wang Q,Liu T,et al.Efficient i-DFA construction algorithm based on state grouping[J].Journal on Communications,2013,34(8): 102 -109.(in Chinese)
[5]Becchi M,Crowley P.A hybrid finite automaton for practical deep packet inspection[A].Proceedings of the 2007 ACM CoNEXT Conference[C].ACM,2007.1.
[6]張樹壯,羅浩,方濱興.面向網(wǎng)絡(luò)安全的高性能特征匹配技術(shù)研究[J].軟件學(xué)報(bào),2011,22(8): 1838 -1854.Zhang S,Luo H,F(xiàn)ang B.Regular expressions matching for network security[J].Journal of Software,2011,22(8): 1838 -1854.(in Chinese)
[7]Kumar S,Dharmapurikar S,Yu F,et al.Algorithms to accelerate multiple regular expressions matching for deep packet inspection[J].ACM SIGCOMM Computer Communication Review,2006,36(4): 339 -350.
[8]Ficara D,Giordano S,Procissi G,et al.An improved DFA for fast regular expression matching[J].ACM SIGCOMM Computer Communication Review,2008,38(5): 29 -40.
[9]Liu T,Yang Y,Liu Y,et al.An efficient regular expressions compression algorithm from a new perspective[A].Proceedings of IEEE INFOCOM 2001[C].IEEE,2011.2129 -2137.
[10]Smith R,Estan C,Jha S,et al.Deflating the big bang: fast and scalable deep packet inspection with extended finite automata[J].ACM SIGCOMM Computer Communication Review,2008,38(4): 207 -218.
[11]宮陽陽,劉勤讓,邵翔宇,等.基于多維有限自動(dòng)機(jī)的DFA改進(jìn)算法[J].電子學(xué)報(bào),2014,42(9): 1818 -1822.Gong Y,Liu Q,Shao X,et al.A regular expression matching algorithm based on multi-dimensional cube[J].Acta Electronica Sinica,2014,42(9): 1818 - 1822.(in Chinese)
[12]Liu C,Pan Y,Chen A,et al.A DFA with extended character-set for fast deep packet inspection[J].IEEE Transactions on Computers,2014,63(8): 1527 -1937.
[13]Regular Expression Processor[EB/OL].http: / /regex.wustl.edu/index.php/Main-Page,2014.
邵翔宇男,1992年1月出生,河南清豐人.2012年畢業(yè)于電子科技大學(xué),現(xiàn)為國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心在讀研究生,主要研究方向?yàn)閷拵畔⒕W(wǎng)絡(luò)及芯片設(shè)計(jì).
E-mail: sxyslf@163.com
劉勤讓男,1975年11月出生,河南睢縣人.現(xiàn)為國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心研究員,碩士生導(dǎo)師.主要研究方向?yàn)閷拵畔⒕W(wǎng)絡(luò)及芯片設(shè)計(jì).
E-mail: qinrangliu@ sina.com
譚力波男,1981年11月出生,內(nèi)蒙古赤峰人.2004年畢業(yè)于武漢理工大學(xué),現(xiàn)為國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心工程師,主要研究方向?yàn)樾酒O(shè)計(jì)技術(shù).
A Regular Expression Grouping Algorithm Based on Signature Templates
SHAO Xiang-yu,LIU Qin-rang,TAN Li-bo
(National Digital Switching System Engineering&Technological R&D Center,Zhengzhou,Henan 450002,China)
Abstract:As the group number grows,the classical signature grouping algorithm solves the DFA state explosion problem with a big decrease on matching efficiency.This paper presents a regular expression(Regex)input drive theory.According to such theory,a grouping algorithm based on signature templates,templates based finite automata(TFA),is proposed.TFA divides Regex set based on signature templates and constructs matching engines in each set.Experiment results show that the preprocessing time and storage are reduced by 2~3 orders of magnitude compared with classical DFA improved algorithms,and TFA brings no obvious decrease on matching efficiency.
Key words:regular expression; deterministic finite automata; multiple DFAs; extended finite automata; multi-dimensional finite automata; signature templates
作者簡介
基金項(xiàng)目:國家973重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(No.2013CB329104)
收稿日期:2014-07-31;修回日期: 2015-01-31;責(zé)任編輯:李勇鋒
DOI:電子學(xué)報(bào)URL:http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.036
中圖分類號:TP393
文獻(xiàn)標(biāo)識碼:A
文章編號:0372-2112(2016)01-0236-05