朱 俊

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

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

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

1 正則表達(dá)式

1.1 問題描述

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

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

1.2 狀態(tài)爆炸

狀態(tài)爆炸是指將多個正則表達(dá)式生成一個DFA 時的狀態(tài)總數(shù)比其獨(dú)自生成DFA 時的狀態(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 評價依據(jù)

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

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

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

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

2 有限自動機(jī)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

判斷正則表達(dá)式集合分組是否有效，既要考慮時間復(fù)雜度，又要考慮空間復(fù)雜度.本文通過自動學(xué)習(xí)的方式對規(guī)則分組進(jìn)行優(yōu)化，根據(jù)歷史記錄將正則表達(dá)式進(jìn)行分組，然后將這個歷史記錄分組緩存到一個存儲空間中，所以當(dāng)進(jìn)行匹配時，如果在該緩存中已經(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)從開源的入侵檢測系統(tǒng)Snort 中抽取若干條正則表達(dá)式作為測試對象，實(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 測試規(guī)則集的DFA 狀態(tài)總數(shù)的變化圖，由該圖可知，隨著迭代次數(shù)的變化，DFA 狀態(tài)的總數(shù)量的變化會降低，當(dāng)?shù)s三次以后，DFA 狀態(tài)的總數(shù)量基本上不再有明顯變化，從而可以得出，該算法能較快得到最優(yōu)情形.

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

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

5 小結(jié)

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