基于規(guī)則模板的正則表達式分組算法

邵翔宇，劉勤讓，譚力波

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南鄭州450002)

?

基于規(guī)則模板的正則表達式分組算法

邵翔宇，劉勤讓，譚力波

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南鄭州450002)

摘要：采用規(guī)則分組的方法解決確定型有限自動機(Deterministic Finite Automata，DFA)狀態(tài)爆炸問題，隨著分組數(shù)目的增加，匹配效率大大降低.本文提出正則表達式的輸入驅(qū)動特性理論，并基于此提出了基于規(guī)則模板的分組算法——模板有限自動機.模板有限自動機算法基于規(guī)則模板對規(guī)則集進行分組，各分組分別構(gòu)建匹配引擎.理論分析和實驗表明，與典型的DFA改進算法相比，預處理時間和存儲空間有2～3個數(shù)量級別的縮減，且匹配效率沒有明顯降低.

關(guān)鍵詞：正則表達式;確定型有限自動機;分組自動機;擴展有限自動機;多維有限自動機;規(guī)則模板

1　引言

在網(wǎng)絡信息安全領(lǐng)域，入侵檢測系統(tǒng)(Intrusion Detection Systems，IDS)扮演著重要的角色，它采用深度包檢測(Deep Packet Inspection，DPI)方法進行病毒檢測、入侵識別等.隨著攻擊模式的多樣化，最早的基于精確字符串匹配方式已經(jīng)無法滿足要求，正則表達式以其強大的、靈活的表達能力而得到廣泛應用.但隨著網(wǎng)絡帶寬逐年增加、規(guī)則數(shù)目的快速增長以及正則表達式表達功能的強大，DPI應用中的正則表達式匹配(Regular Expression Matching，REM)面臨嚴峻挑戰(zhàn)，其中最為急迫的是如何滿足高速網(wǎng)絡數(shù)據(jù)包處理的要求.有限自動機分為非確定性有限自動機(Non-deterministic Finite Automata，NFA)和確定性有限自動機(Deterministic Finite Automata，DFA)兩種，其中DFA與NFA相比在任意時刻只有一個活躍狀態(tài)、處理一個字符只需要一次遷移，具有線速的匹配性能，適用于高速數(shù)據(jù)鏈路中的REM.

將多條正則表達式編譯成一個DFA時，由于各條規(guī)則之間的相互重疊和影響，會導致狀態(tài)爆炸問題.YU等人［1］分析了這種爆炸問題，提出對正則表達式規(guī)則進行分組的mDFA(Multiple DFAs)算法.mDFA是基于規(guī)則之間的膨脹情況而進行的分組，各分組采用DFA進行匹配，這種分組無法進行徹底的存儲壓縮，且會造成分割成的組數(shù)目過多，降低分組算法匹配效率.

本文提出了正則表達式匹配引擎的輸入驅(qū)動特性理論，針對當前單一算法無法針對整個規(guī)則集進行有效的存儲壓縮問題，提出了基于規(guī)則模板的正則表達式分組算法—模板自動機(Templates based Finite Automata，TFA).TFA算法將規(guī)則模板作為正則表達式分組的依據(jù)，各分組采用的特定改進算法進行匹配.

2　正則表達式輸入驅(qū)動特性

2.1狀態(tài)爆炸問題

正則表達式規(guī)則集在編譯成一個DFA時，產(chǎn)生狀態(tài)爆炸的規(guī)則主要有兩類:計數(shù)器型爆炸和克林閉包型爆炸，這兩種爆炸類型嚴重制約著DFA在IDS中的應用.

在IDS中DFA的構(gòu)造［2］中，狀態(tài)爆炸通常在NFA子集構(gòu)造時產(chǎn)生，按照構(gòu)造角度來分，解決DFA狀態(tài)爆炸問題方案有以下4個方向:分組算法［1，3，4］，不確定度調(diào)節(jié)算法［5，6］，狀態(tài)轉(zhuǎn)移表(State Transition Table，STT)壓縮算法［7～9］，自動機結(jié)構(gòu)改進算法［10～12］.以上四類算法可以很大程度壓縮存儲空間，但無法針對整個規(guī)則集進行有效的存儲壓縮.在自動機結(jié)構(gòu)改進算法中，針對這兩類爆炸類型各自有比較有效的壓縮算法:針對計數(shù)器型爆炸改進的擴展有限自動機(eXtended Finite Automata，XFA)算法［10］，針對克林閉包型爆炸改進的多維立方體自動機(Multi-dimensional Finite Automata，MFA)算法［11］.

XFA算法通過增加計數(shù)器型標記避免計數(shù)器部分狀態(tài)的重復描述，達到對計數(shù)器部分狀態(tài)的對數(shù)級別縮減.XFA存在一定的規(guī)則受限性，對其他規(guī)則類型的爆炸類型的壓縮效果不明顯.

MFA算法解決克林閉包型規(guī)則聯(lián)合編譯造成的爆炸問題.MFA通過在多維空間構(gòu)造聯(lián)合DFA，利用聯(lián)合狀態(tài)轉(zhuǎn)移圖的對稱性達到壓縮存儲空間的目的.MFA算法構(gòu)建的多維模型針對克林閉包型爆炸進行冗余狀態(tài)壓縮，但存在一定的規(guī)則受限性，無法解決計數(shù)器等類型的爆炸問題.

2.2正則表達式輸入驅(qū)動特性

規(guī)則和文本是正則表達式匹配引擎的兩個輸入，采用有限自動機實現(xiàn)的正則表達式匹配引擎的存儲空間和帶寬受輸入的影響，如圖1所示.NFA接收一個字符時帶寬主要決定于激活狀態(tài)集合內(nèi)的狀態(tài)數(shù)目，而激活的狀態(tài)數(shù)目與字符所達到的狀態(tài)位置有關(guān)，其匹配時間最差為O(n2)，DFA在任何文本輸入下處理一個字符的時間都為常數(shù)O(1)，因此NFA的匹配時間受輸入文本影響.NFA狀態(tài)數(shù)目與規(guī)則長度n呈線性關(guān)系，DFA不同類型的規(guī)則編譯產(chǎn)生的狀態(tài)數(shù)是不同的，因此DFA狀態(tài)數(shù)目受輸入規(guī)則影響.

基于以上所述NFA和DFA的特性，本文給出正則表達式匹配引擎輸入驅(qū)動特性的定義.正則表達式匹配引擎的帶寬(匹配時間)受文本驅(qū)動，造成處理一個字符的時間變化，則稱該正則表達式匹配引擎為文本驅(qū)動(text directed)引擎.正則表達式匹配引擎的空間復雜度(狀態(tài)數(shù)目和存儲空間)受規(guī)則類型影響，而產(chǎn)生不同的狀態(tài)數(shù)目，則稱該正則表達式匹配引擎為規(guī)則驅(qū)動(signature directed)引擎.

表1列出了當前幾類代表性算法的輸入驅(qū)動特性.自動機結(jié)構(gòu)改進算法中XFA執(zhí)行的操作符受輸入文本影響，造成不同輸入文本的匹配時間有所不同; MFA所處狀態(tài)的受輸入文本影響，造成匹配時間有所不同，但是兩者最差匹配時間復雜度為常數(shù)級別，可以認為屬于弱文本驅(qū)動.

單一的算法是無法針對所有規(guī)則同時消除其規(guī)則驅(qū)動和文本驅(qū)動特性，無法同時達到存儲空間和匹配時間的下界.基于匹配引擎的驅(qū)動特性，有兩種提高自動機匹配效率的改進思路:(1)輸入文本控制:通常輸入文本是需要待匹配的數(shù)據(jù)流，不受匹配引擎的控制，但是可以在文本進入匹配引擎之前進行文本預篩選，從而減小輸入文本對匹配時間的影響;(2)輸入規(guī)則控制:通常輸入規(guī)則用于匹配病毒或惡意代碼，輸入規(guī)則的減少會嚴重影響引擎匹配的準確性，可以運行多個匹配引擎，保證規(guī)則的完整性.

3　基于規(guī)則模板的分組算法

分組算法是對輸入規(guī)則控制的一種算法.通常為了盡可能最大程度隔離規(guī)則，需要較多的分組和較多的DFA引擎來完成對全部規(guī)則的覆蓋，這也不可避免降低匹配引擎的匹配速度.本文對分組算法中DFA引擎進行改進，采用當前算法中DFA改進算法進行匹配引擎構(gòu)造，改變分組算法的分組依據(jù)、降低分組數(shù)目，在保持分組算法規(guī)則高覆蓋率的同時，提高分組算法匹配效率.由于XFA、MFA在各自適用的規(guī)則內(nèi)能消除規(guī)則驅(qū)動特性，且不存在嚴重的文本驅(qū)動特性，將XFA 和MFA兩種匹配算法同時應用在分組算法的匹配引擎中，達到更好的存儲壓縮效果.

表1　當前算法的輸入驅(qū)動特性

3.1基于規(guī)則模板的分組算法

針對DFA中最嚴重兩種類型的爆炸問題，本文通過設(shè)定模板(template)，按照XFA、MFA的適用規(guī)則特點進行規(guī)則分組，然后將各分組規(guī)則按照XFA、MFA、DFA構(gòu)造自動機，形成模板自動機TFA匹配引擎.圖2給出了TFA算法的模型，其中包含:規(guī)則分組、匹配引擎構(gòu)建、匹配過程.

規(guī)則分組

TFA規(guī)則分組就是根據(jù)規(guī)則模板對規(guī)則集進行文本處理，從規(guī)則集中查找出符合規(guī)則模板的各條規(guī)則，形成三個規(guī)則子集的過程.規(guī)則模板是一組正則表達式規(guī)則，用于查找包含特定類型的規(guī)則.由于引擎中XFA和MFA算法的特點，用于規(guī)則分組模板的設(shè)定將直接影響TFA算法的效率，TFA的規(guī)則模板設(shè)定為計數(shù)器型模板和克林閉包型模板.

通過計數(shù)器模板篩選出的都是包含計數(shù)器的正則表達式規(guī)則，可以通過XFA實現(xiàn)聯(lián)合編譯;通過克林閉包模板篩選出的包含克林閉包型規(guī)則，可以采用MFA算法進行聯(lián)合編譯;其他不膨脹規(guī)則可以簡單采用DFA來實現(xiàn).

引擎構(gòu)造

將三組預處理規(guī)則分別按照XFA、MFA和聯(lián)合DFA構(gòu)造自動機，形成三個正則表達式匹配引擎.其中XFA的構(gòu)造方法，按照文獻［10］中的方案.而MFA的構(gòu)造方法是:以克林閉包規(guī)則的一個DFA(single-DFA)為一個維度，以每個規(guī)則的“.*”對應的狀態(tài)為交點，構(gòu)造一個在多維空間的跳轉(zhuǎn)結(jié)構(gòu).DFA構(gòu)造方法參照基本流程構(gòu)建聯(lián)合DFA.

匹配過程

待匹配數(shù)據(jù)送入系統(tǒng)之后，匹配判決會將相同的數(shù)據(jù)送入三個匹配引擎中，三個匹配引擎的進行相對獨立的匹配過程.由于各個引擎匹配結(jié)果產(chǎn)生的時間會有所不同，需要匹配判決模塊根據(jù)系統(tǒng)的實際要求進行判決.

3.2性能分析

衡量正則表達式算法性能主要有三個方面:預處理時間、存儲空間和匹配時間.TFA預處理時間即規(guī)則分組，是用正則表達式處理引擎規(guī)則文本的處理過程，處理時間較短.因此，本文從TFA存儲(狀態(tài))空間和TFA匹配時間來分析TFA算法復雜度.

存儲空間(狀態(tài))復雜度

自動機的儲存主要用于記錄狀態(tài)及其跳轉(zhuǎn)信息，存儲占用與狀態(tài)數(shù)目直接相關(guān)，存儲壓縮最有效的方式是減少狀態(tài)數(shù)目.

在包含l條計數(shù)器的規(guī)則中，XFA針對計數(shù)部分進行的改進，其他部分與DFA相同.XFA需要輔助的計數(shù)器空間，計數(shù)器重復次數(shù)為x，則占用log2x，因此存儲空間復雜度SXFA-S1

在包含m條克林閉包的規(guī)則中，MFA需要存儲m 個DFA、m條坐標軸信息和2個動態(tài)狀態(tài)，因此MFA存儲空間SMFA-S2

S3中n條DFA之間不會產(chǎn)生爆炸，因此SDFA-S3與QDFA-S3一致，因此TFA存儲空間復雜度STFA為SXFA-S1、SMFA-S2、SDFA-S3之和

因為計數(shù)器型改寫后的DFA不產(chǎn)生爆炸，采用計數(shù)器對限定部分描述會造成空間節(jié)省，TFA算法存儲空間與規(guī)則數(shù)呈線性關(guān)系.

匹配時間復雜度

XFA的匹配時間取決于當前狀態(tài)的標志位操作，XFA中賦值、復位和計數(shù)的處理時間為常數(shù)，因此XFA匹配時間復雜度為常數(shù)級別O(1).MFA的匹配時間長短取決于當前狀態(tài)所處位置，交點與非交點處理時間不一致，但交點最差處理時間為常數(shù)，因此MFA匹配時間復雜度為O(1).DFA匹配時間復雜度為常數(shù)O(1).而TFA的匹配時間三者的匹配時間之和，因此其最差匹配時間復雜度應為常數(shù)級別O(1)+ O(1)+ O(1).

表2列出了TFA算法的時空復雜度，并將DFA和NFA作為對比.由表可見，TFA算法與NFA的存儲空間復雜度類似，屬于非規(guī)則驅(qū)動引擎;同時與DFA匹配時間復雜度一致，與輸入有較弱的相關(guān)性，因此，TFA算法在消除規(guī)則驅(qū)動特性同時并未引起嚴重的文本驅(qū)動特性，可以達到較好存儲壓縮效果.

4　實驗結(jié)果

仿真實驗主要分為兩部分:實驗一主要是與mDFA算法對比，驗證TFA分組算法的分組有效性;實驗二是與經(jīng)典改進算法對比，驗證TFA算法的效率.本文提出的規(guī)則模板分組算法是一種樸素的分組算法，參照實際IDS中各類規(guī)則比例，從實際IDS中選取40條規(guī)則作為測試規(guī)則集，包含20條精確型規(guī)則、10條克林閉包型規(guī)則和10條計數(shù)器型規(guī)則.

本文采用Becchi提供的軟件RegEx Processor［13］，分別實現(xiàn)了NFA、DFA、mDFA、Hybrid-FA、D2FA以及本文的TFA算法.利用RegEx Processor自帶的tracegen工具生成1GB的測試數(shù)據(jù)，用于匹配時間的測試.

實驗一TFA與mDFA算法對比

對比TFA與mDFA兩種分組算法.通過更改閾值設(shè)定不同的mDFA算法分組數(shù)目.如表3所示，mDFA算法的預處理時間和狀態(tài)數(shù)目隨著分組數(shù)目的增加而減少;但隨著分組數(shù)目的增加，匹配時間與分組數(shù)目基本呈線性關(guān)系.如圖3所示的算法匹配時間和狀態(tài)數(shù)目二維圖上，TFA相比于mDFA更加靠近坐標軸原點，說明TFA可以在不降低匹配效率的情況下縮減狀態(tài)數(shù)目，可以避免mDFA分組數(shù)目過多造成的效率下降問題，TFA分組算法比mDFA更有優(yōu)勢.

實驗二TFA與經(jīng)典算法對比

對比的算法包含mDFA(m = 6)、Hybrid-FA、D2FA以及NFA和DFA.如表4所示，在預處理時間方面，TFA與mDFA時間相當，比Hybrid-FA、D2FA算法有幾個數(shù)量級的縮減，實時更新能力最強;存儲空間方面，TFA比Hybrid-FA、D2FA算法降低了2～3個數(shù)量級;匹配時間較基于DFA的算法DFA、Hybrid-FA無明顯增加.如圖4所示的算法匹配時間和狀態(tài)數(shù)目二維圖上，相比于其他DFA改進算法TFA達到了存儲空間和匹配速率更好的折中，算法匹配效率更好.

表3　TFA與mDFA對比

表4　TFA與經(jīng)典算法對比

5　結(jié)束語

本文通過對算法的驅(qū)動特性進行分析，提出了基于規(guī)則模板的分組算法TFA，TFA算法基于規(guī)則模板進行分組，各分組的實現(xiàn)采用DFA及改進算法.理論分析和實驗結(jié)果表明，TFA能在不降低匹配效率的情況下，達到mDFA的空間壓縮效果，同時避免了分組數(shù)目過多造成的效率下降問題.與經(jīng)典的改進算法相比，TFA預處理時間和存儲空間比Hybrid-FA、D2FA算法降低了2～3個數(shù)量級;匹配時間與基于DFA的算法DFA、Hybrid-FA數(shù)量級相當.

本文提出的分組方法是一種基于DFA的樸素正則表達式匹配算法，而對于既是計數(shù)型也是閉包型的規(guī)則，基于DFA的分組方案無法進行有效的狀態(tài)數(shù)目壓縮.因此，對TFA內(nèi)部算法引擎的優(yōu)化，對所有規(guī)則類型進行更加有效的存儲壓縮，是下一步的工作方向.

參考文獻

［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］徐乾，鄂躍鵬，葛敬國.深度包檢測中一種高效的正則表達式壓縮算法［J］.軟件學報，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］.通信學報，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)絡安全的高性能特征匹配技術(shù)研究［J］.軟件學報，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］宮陽陽，劉勤讓，邵翔宇，等.基于多維有限自動機的DFA改進算法［J］.電子學報，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è)于電子科技大學，現(xiàn)為國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心在讀研究生，主要研究方向為寬帶信息網(wǎng)絡及芯片設(shè)計.

E-mail: sxyslf@163.com

劉勤讓男，1975年11月出生，河南睢縣人.現(xiàn)為國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心研究員，碩士生導師.主要研究方向為寬帶信息網(wǎng)絡及芯片設(shè)計.

E-mail: qinrangliu@ sina.com

譚力波男，1981年11月出生，內(nèi)蒙古赤峰人.2004年畢業(yè)于武漢理工大學，現(xiàn)為國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心工程師，主要研究方向為芯片設(shè)計技術(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

作者簡介

基金項目:國家973重點基礎(chǔ)研究發(fā)展計劃(No.2013CB329104)

收稿日期:2014-07-31;修回日期: 2015-01-31;責任編輯:李勇鋒

DOI:電子學報URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.036

中圖分類號：TP393

文獻標識碼：A

文章編號：0372-2112(2016)01-0236-05