基于規(guī)則分組的DFA正則表達(dá)式匹配算法

朱 俊

（1.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，合肥 230009；2.安徽水利水電職業(yè)技術(shù)學(xué)院電子信息工程學(xué)院，合肥 231603）

入侵檢測(cè)系統(tǒng)（Intrusion Detection Systems，IDS）不僅能夠識(shí)別出網(wǎng)絡(luò)中的入侵行為，還能檢測(cè)出網(wǎng)絡(luò)中的漏洞信息，從而采取相應(yīng)對(duì)策進(jìn)行處理和防范，阻止入侵行為帶來的危害.入侵檢測(cè)方法主要分為異常檢測(cè)和誤用檢測(cè)兩大類.異常檢測(cè)主要采用統(tǒng)計(jì)分析的方法，常用的有：神經(jīng)網(wǎng)絡(luò)、人工免疫、統(tǒng)計(jì)模型、數(shù)據(jù)挖掘等［1］.誤用檢測(cè)主要采用模式匹配的方法，模式匹配技術(shù)的過程通常是提前將特征信息提取出來，存放到模式庫中，再把收集到的數(shù)據(jù)與模式庫中的特征信息進(jìn)行比對(duì)，從而發(fā)現(xiàn)入侵行為.當(dāng)今，模式匹配技術(shù)是入侵檢測(cè)系統(tǒng)主要采用的方式.隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)帶寬的使用量增長(zhǎng)迅速，單位時(shí)間傳輸?shù)臄?shù)據(jù)呈幾何倍數(shù)增加，規(guī)則數(shù)量隨之增加，所帶來的最大問題是如何快速地進(jìn)行檢測(cè).構(gòu)建有限自動(dòng)機(jī)對(duì)于模式匹配來說非常有效.構(gòu)建有限自動(dòng)機(jī)后，對(duì)每個(gè)文本字符只需要進(jìn)行一次遍歷，因而在時(shí)間復(fù)雜度上有很大的優(yōu)勢(shì)，構(gòu)建有限自動(dòng)機(jī)所花費(fèi)的時(shí)間復(fù)雜度通常為O（n）［1-2］.但是，在輸入字符集元素很龐大的情況下，建立有限自動(dòng)機(jī)所花費(fèi)的時(shí)間就會(huì)大大地增加.

為了充分發(fā)揮確定性有限自動(dòng)機(jī)（deterministic finite automata，DFA）速度快的優(yōu)勢(shì)，對(duì)其存儲(chǔ)空間的算法進(jìn)行優(yōu)化具有重要意義.如果有多條正則表達(dá)式構(gòu)造成一個(gè)DFA，則各個(gè)規(guī)則會(huì)有相同或相似情況，狀態(tài)集合很大，導(dǎo)致出現(xiàn)狀態(tài)爆炸問題［2-4］.Yu Fang 等［5］提出了對(duì)規(guī)則進(jìn)行分組的算法，來解決狀態(tài)爆炸問題，這種分組算法可以在一定程度上抑制狀態(tài)爆炸問題，但在存儲(chǔ)空間上并未有大的提升，并且當(dāng)分組數(shù)量大時(shí)，算法空間復(fù)雜度較大.

1 正則表達(dá)式

1.1 問題描述

傳統(tǒng)的入侵檢測(cè)主要使用樸素模式匹配算法或一些經(jīng)典匹配算法，如AC 算法、BM 算法、KMP算法等［1］，但是這些算法的缺點(diǎn)是描述精確字符串的能力非常有限.隨著計(jì)算機(jī)技術(shù)的發(fā)展，入侵行為變得多樣，特征更加復(fù)雜，增加了代碼復(fù)雜度.簡(jiǎn)單的字符串匹配不再滿足入侵檢測(cè)需求.

正則表達(dá)式起源于科學(xué)家用一種數(shù)學(xué)方法來描述神經(jīng)網(wǎng)絡(luò)的研究，后來正則表達(dá)式被用于計(jì)算機(jī)領(lǐng)域，先后在Unix 的編輯器qed 和ed 以及grep 中得到應(yīng)用，著名的Perl 語言也使用正則表達(dá)式.近年來，在WINDOWS 環(huán)境下，正則表達(dá)式也得到了廣泛的應(yīng)用.主流的開發(fā)語言delphi、PHP、C#、Java、C++、VB、Javascript、Ruby 以及Python 等都可以支持正則表達(dá)式.

正則表達(dá)式非常靈活、邏輯性強(qiáng)、功能強(qiáng)大，通過簡(jiǎn)單的方式就可以對(duì)字符串進(jìn)行操作.正則表達(dá)式應(yīng)用的對(duì)象通常是文本，所以適用范圍很廣，一些普通的文本編輯器都可以使用，如EditPlus 等.正因?yàn)檎齽t表達(dá)式的優(yōu)勢(shì)，比精確字符串匹配更適合進(jìn)行深度報(bào)文檢測(cè)，更符合入侵檢測(cè)場(chǎng)景應(yīng)用.像開源的入侵檢測(cè)系統(tǒng)Snort 基本上都使用正則表達(dá)式來對(duì)規(guī)則進(jìn)行描述.一些網(wǎng)絡(luò)安全設(shè)備也使用正則表達(dá)式來檢測(cè)，判斷是否有入侵行為［2-4］.

1.2 狀態(tài)爆炸

狀態(tài)爆炸是指將多個(gè)正則表達(dá)式生成一個(gè)DFA 時(shí)的狀態(tài)總數(shù)比其獨(dú)自生成DFA 時(shí)的狀態(tài)總數(shù)量更大.例如正則表達(dá)式E1 和E2，E1 生成的DFA 的狀態(tài)數(shù)量為Count（E1），E2 生成的DFA 的狀態(tài)數(shù)量為Count（E2），將E1 和E2 合并后的表達(dá)式為E12，生成的DFA 的狀態(tài)數(shù)量為Count（E12），如果存在Count（E1）+Count（E2）

圖1 正則表達(dá)式E1的DFA

圖2 正則表達(dá)式E2的DFA

1.3 評(píng)價(jià)依據(jù)

判斷正則表達(dá)式集合分組是否有效，主要看生成DFA 的狀態(tài)總數(shù)及分組的數(shù)量.

（1）DFA 狀態(tài)總數(shù)越多，所需要的存儲(chǔ)空間也越大.所以，減少DFA 狀態(tài)總數(shù)，可以減小所需要的存儲(chǔ)空間，在空間復(fù)雜度上得到一定的優(yōu)化.

（2）分組的總數(shù)量會(huì)影響到DFA 的匹配速度，當(dāng)對(duì)某個(gè)字符的狀態(tài)轉(zhuǎn)移表進(jìn)行訪問時(shí)，分組數(shù)越多，訪問的次數(shù)相應(yīng)會(huì)越多，匹配的效率就會(huì)低，分組數(shù)越少，訪問的次數(shù)相應(yīng)減少，匹配的效率就會(huì)提高.

在一般情況下，分組數(shù)量越多，DFA 狀態(tài)總數(shù)量就會(huì)越小，分組數(shù)量越少，DFA 狀態(tài)總數(shù)量就會(huì)越大，只有當(dāng)DFA 狀態(tài)總數(shù)和分組的總數(shù)量這兩個(gè)因素在一個(gè)合適的結(jié)合點(diǎn)時(shí)，達(dá)到存儲(chǔ)空間和匹配速度上總體最優(yōu)化.

2 有限自動(dòng)機(jī)

通常一個(gè)有限自動(dòng)機(jī)包括五個(gè)元素，例如有限自動(dòng)機(jī)M（Q，q0，A，ε，δ），其中：Q 表示狀態(tài)的有限集合，q0∈Q代表初始狀態(tài)，A 是一個(gè)接受狀態(tài)集合且A?Q，ε是有限的輸入字符表，包含256 個(gè)字符，δ 是M 的轉(zhuǎn)移函數(shù)，為Q×ε到Q 的函數(shù)［1］.

有限自動(dòng)機(jī)從初始狀態(tài)q0開始，如果有限自動(dòng)機(jī)在狀態(tài)q時(shí)讀入了輸入字符a，則它從狀態(tài)q變?yōu)闋顟B(tài)δ（q，a）.每當(dāng)其當(dāng)前狀態(tài)q屬于A時(shí)，就說明自動(dòng)機(jī)M接受了迄今為止所輸入的字符串.沒有被接收的輸入稱為拒絕的輸入.

有限自動(dòng)機(jī)M可以推導(dǎo)出一個(gè)函數(shù)，稱為終態(tài)函數(shù)Φ，M接受字符串w，當(dāng)且僅當(dāng)Φ(w)∈A.函數(shù)Φ由下列遞歸關(guān)系定義：

對(duì)于任意一個(gè)模式P，都可以構(gòu)造一個(gè)字符串匹配自動(dòng)機(jī)，在預(yù)處理階段，先根據(jù)模式P構(gòu)造出DFA，然后利用構(gòu)造出的DFA 來遍歷字符串，首先定義一個(gè)輔助函數(shù)σ，稱為相應(yīng)P的后綴函數(shù).函數(shù)σ是一個(gè)從ε*到{0，1，…，m}上定義的映射，是x的后綴P的最長(zhǎng)前綴的長(zhǎng)度：

因?yàn)榭兆址甈0=ε是每一個(gè)字符串的后綴，所以后綴函數(shù)是有完備定義的.例如，對(duì)模式P=ab，有σ（ε）=0，σ（ccaca）=1，σ（ccab）=2.對(duì)一個(gè)長(zhǎng)度為m的模式P來說，σ（x）=m，當(dāng)且僅當(dāng)P?x.根據(jù)后綴函數(shù)的定義有：如果x?y，則σ(x)≤σ(y)［1］.

已知模式P［1，…，m］，其對(duì)應(yīng)的字符串匹配自動(dòng)機(jī)定義如下：

狀態(tài)集Q為{0，1，…，m}，初始狀態(tài)q0為0，狀態(tài)m是唯一的接受狀態(tài).

對(duì)任意狀態(tài)q和字符a，變遷函數(shù)δ由如下等式定義.

自動(dòng)機(jī)的操作中保持如下條件不變：

這意味著對(duì)文本字符串T的前面i個(gè)字符進(jìn)行掃描后，自動(dòng)機(jī)的狀態(tài)為Φ（Ti）=q，其中q=σ（Ti）是最長(zhǎng)后綴Ti的長(zhǎng)度，Ti是模式P的一個(gè)前綴.如果下面掃描到的字符為T［i+1］=a，則自動(dòng)機(jī)的狀態(tài)應(yīng)轉(zhuǎn)換為σ（Ti+1）=σ（Tia）.也就是說，為了計(jì)算P的前綴Tia的最長(zhǎng)后綴的長(zhǎng)度，可以先計(jì)算出P的前綴Pqa的最長(zhǎng)后綴.在每一種狀態(tài)上，自動(dòng)機(jī)僅需要知道迄今已讀入的字符串的后綴P的最長(zhǎng)前綴的長(zhǎng)度.

對(duì)于長(zhǎng)度為m的模式的任意字符串匹配自動(dòng)機(jī)來說，狀態(tài)集Q為{0，1，…，m}，初始狀態(tài)為唯一的接收態(tài)是狀態(tài)m［1］.

從FAM 算法可以看出，如果一個(gè)長(zhǎng)度為n的文本字符串，計(jì)算其所需要的匹配時(shí)間，如果不包括計(jì)算轉(zhuǎn)換函數(shù)δ所需要的預(yù)處理時(shí)間，那么它的時(shí)間復(fù)雜度為O（n）.

下列過程根據(jù)一個(gè)給定模式P［1，…，n］來計(jì)算轉(zhuǎn)換函數(shù)φ［1］.

DFA 適用在不要求回溯的線性狀態(tài)，它的一個(gè)顯著特點(diǎn)是在匹配很長(zhǎng)的字符串時(shí)依然能夠確保成功.

3 基于規(guī)則分組的匹配算法

基于規(guī)則優(yōu)先級(jí)的匹配算法的出發(fā)點(diǎn)是減少DFA 中出現(xiàn)的爆炸問題，同時(shí)在時(shí)間復(fù)雜度上和空間復(fù)雜度兩個(gè)維度上占用較少的消耗.

圖1 和圖2 描述了當(dāng)用一個(gè)正則表達(dá)式構(gòu)造DFA 時(shí)，會(huì)導(dǎo)致狀態(tài)爆炸的情況.在另外一些情況下，雖然一條規(guī)則不會(huì)引起狀態(tài)爆炸，但當(dāng)多個(gè)正則表達(dá)式構(gòu)造同一個(gè)DFA 時(shí)，由于其相互作用影響，也會(huì)造成狀態(tài)爆炸.極端情況下，如果每個(gè)正則表達(dá)式中出現(xiàn)x次同一字符串，則復(fù)雜度為O（(x+1)y）.文獻(xiàn)［2-3，5-6］中提出了對(duì)正則表達(dá)式進(jìn)行分組，從而減少狀態(tài)爆炸情況的思想.其主要思想是通過找到正則表達(dá)式中的等價(jià)因子，然后構(gòu)造出關(guān)系圖，每個(gè)正則表達(dá)式作為關(guān)系圖中的頂點(diǎn)，如果任兩個(gè)正則表達(dá)式存在造價(jià)因子，則將該兩頂點(diǎn)連接起來.在進(jìn)行分組前，找出一個(gè)與其他表達(dá)式相關(guān)度最少的一個(gè)正則表達(dá)式，然后將該正則表達(dá)式加入分組里，接下來重復(fù)上述步驟，將其他的正則表達(dá)式依次加入分組里，當(dāng)這個(gè)分組的DFA 的存儲(chǔ)空間達(dá)到一定的閾值時(shí)，將新建一個(gè)分組，接下來繼續(xù)重復(fù)上述步驟，直至所有的正則表達(dá)式都被加入相應(yīng)的分組中，這種算法的優(yōu)點(diǎn)是減少了正則表達(dá)式之間的相互影響，存儲(chǔ)空間使用較小，并且狀態(tài)爆炸問題可以得到抑制［6，8-9］.

為了抑制狀態(tài)爆炸問題出現(xiàn)，分組是一個(gè)非常有效的辦法，但是消除狀態(tài)爆炸，就需要進(jìn)行大量分組，這樣會(huì)增加分組數(shù)量，需要很多DFA 才能覆蓋所有規(guī)則，這樣會(huì)降低匹配引擎的效率.

判斷正則表達(dá)式集合分組是否有效，既要考慮時(shí)間復(fù)雜度，又要考慮空間復(fù)雜度.本文通過自動(dòng)學(xué)習(xí)的方式對(duì)規(guī)則分組進(jìn)行優(yōu)化，根據(jù)歷史記錄將正則表達(dá)式進(jìn)行分組，然后將這個(gè)歷史記錄分組緩存到一個(gè)存儲(chǔ)空間中，所以當(dāng)進(jìn)行匹配時(shí)，如果在該緩存中已經(jīng)有了相應(yīng)的記錄，就不需要重新構(gòu)建DFA，就可以根據(jù)歷史記錄來決定相應(yīng)操作，從而避免重復(fù)增加狀態(tài)來模擬排列組合現(xiàn)象，減少開銷，在實(shí)際應(yīng)用中，如果規(guī)則集已知的情況下，根據(jù)歷史記錄進(jìn)行規(guī)則分組具有一定的意義.

4 仿真實(shí)驗(yàn)

為驗(yàn)證算法的有效性，本實(shí)驗(yàn)從開源的入侵檢測(cè)系統(tǒng)Snort 中抽取若干條正則表達(dá)式作為測(cè)試對(duì)象，實(shí)驗(yàn)環(huán)境是在虛擬機(jī)中實(shí)現(xiàn)，操作系統(tǒng)為Intel i7處理器，內(nèi)存4 GB，操作系統(tǒng)為ubuntu 18.04LTS，表1 為算法的性能數(shù)據(jù)，圖3 是采用Snort 測(cè)試規(guī)則集的DFA 狀態(tài)總數(shù)的變化圖，由該圖可知，隨著迭代次數(shù)的變化，DFA 狀態(tài)的總數(shù)量的變化會(huì)降低，當(dāng)?shù)s三次以后，DFA 狀態(tài)的總數(shù)量基本上不再有明顯變化，從而可以得出，該算法能較快得到最優(yōu)情形.

表1 根據(jù)歷史記錄進(jìn)行分組的算法性能指標(biāo)

圖3 DFA規(guī)則分組數(shù)與狀態(tài)總數(shù)對(duì)應(yīng)顯示圖

5 小結(jié)

模式匹配作為IDS 的一種主要應(yīng)用，其效率高低直接影響IDS 的性能優(yōu)劣.在由正則表達(dá)式構(gòu)造DFA 時(shí)，因?yàn)闀?huì)產(chǎn)生狀態(tài)爆炸情況，導(dǎo)致在存儲(chǔ)空間和匹配速度上性能不佳.采用分組算法可以在一定程度上抑制狀態(tài)爆炸問題，通過自動(dòng)學(xué)習(xí)的方式，根據(jù)歷史記錄將正則表達(dá)式進(jìn)行分組，當(dāng)緩存中存在相應(yīng)記錄時(shí)，不需要重復(fù)構(gòu)建DFA，從而提高性能.實(shí)驗(yàn)證明，該算法在規(guī)則集一定的情況下，能夠減少狀態(tài)總數(shù)，在空間復(fù)雜度上有一定的優(yōu)化，能夠在一定程度上抑制狀態(tài)爆炸的發(fā)生.