基于DFA進(jìn)行規(guī)則組合的算法研究

◆許 黎

（西南油氣田分公司 四川 610000）

深度包檢測(cè)就是將IDS和IPS整合起來，不僅僅檢測(cè)網(wǎng)絡(luò)層和傳輸層數(shù)據(jù)包頭部，而且在應(yīng)用層深入到正在進(jìn)入服務(wù)器的數(shù)據(jù)包的有效載荷所封裝的內(nèi)容部分，搜尋合法或非法的內(nèi)容以決定是否允許數(shù)據(jù)包通過，或者查找常見的攻擊，并丟棄與之相關(guān)的會(huì)話。它要求將數(shù)據(jù)包的內(nèi)容與指定的規(guī)則集進(jìn)行匹配來識(shí)別出具體的應(yīng)用，如病毒，攻擊等等。

規(guī)則的使用之所以如此廣泛，是因?yàn)樗鼈冊(cè)诿枋瞿Ｊ綍r(shí)表現(xiàn)出強(qiáng)大的表達(dá)能力。例如，在Linux應(yīng)用層協(xié)議分類器（7層過濾器）[1]中，所有的協(xié)議標(biāo)識(shí)符都被表示為規(guī)則。同樣地，Snort[2]入侵檢測(cè)系統(tǒng)從2003年4月在規(guī)則集中從沒有規(guī)則發(fā)展到現(xiàn)在使用超過4867條規(guī)則。另一個(gè)入侵檢測(cè)系統(tǒng)Bro[3]，也把規(guī)則作為模式語言使用。

一方面，由于深度包檢測(cè)中對(duì)內(nèi)容進(jìn)行掃描時(shí)廣泛的應(yīng)用規(guī)則對(duì)內(nèi)容進(jìn)行匹配，因此我們必須使對(duì)包內(nèi)容進(jìn)行的規(guī)則匹配與線速的包頭處理保持同步。但是現(xiàn)在很多已經(jīng)存在的內(nèi)容掃描并不能滿足這個(gè)要求。而且，90%以上的CPU時(shí)間花在規(guī)則的匹配上，只給其他的入侵檢測(cè)或監(jiān)測(cè)功能留出了很少一部分的時(shí)間。另外一方面，盡管近來已經(jīng)提出了在入侵檢測(cè)系統(tǒng)中很多快速字符串匹配的方案，但是他們僅僅關(guān)注的是明確的字符串模式，而不能簡(jiǎn)單擴(kuò)展為快速的規(guī)則匹配。

規(guī)則匹配時(shí)的低效很大程度上歸結(jié)于以下三個(gè)很復(fù)雜的應(yīng)用于網(wǎng)絡(luò)中的規(guī)則的特征，目前還沒有極其優(yōu)化的解決方案。第一，很多模式使用多樣化的通配符（例如.，*）。在模式匹配中，規(guī)則被轉(zhuǎn)換為狀態(tài)機(jī)，大量的通配符能夠引起相應(yīng)的DFA的狀態(tài)數(shù)目呈指數(shù)型的增長。第二，大多數(shù)通配符使用時(shí)受到了長度的限制（?代表一個(gè)或更少，+代表長于）。這些長度限制將會(huì)增加規(guī)則匹配時(shí)對(duì)內(nèi)存資源的需求。第三，組合成類的字符是非常普遍的：例如，匹配ftp協(xié)議的規(guī)則“^220[x09-x0d -～]*ftp”中包括了一個(gè)類（方括弧中表示的）。這類字符可能會(huì)與其他類或者通配符交叉。這種交叉又將導(dǎo)致一個(gè)高度復(fù)雜的狀態(tài)機(jī)。

為了避免規(guī)則匹配時(shí)的低效，針對(duì)高速處理的要求，本文首先分析導(dǎo)致DFA的狀態(tài)數(shù)目呈指數(shù)型增長的規(guī)則的結(jié)構(gòu)特征，并提出把多個(gè)DFA組合到一個(gè)組中用來提高匹配速度的解決方案。即在不引起增加內(nèi)存耗費(fèi)的前提下有選擇的把多個(gè)模式組合成幾組自動(dòng)機(jī)，并通過實(shí)驗(yàn)對(duì)我們的組合算法進(jìn)行測(cè)試。

1 背景和相關(guān)工作

在對(duì)內(nèi)容進(jìn)行匹配時(shí)，Snort系統(tǒng)采用BM模式匹配算法對(duì)該數(shù)據(jù)包的內(nèi)容進(jìn)行匹配。如果在數(shù)據(jù)包中存在與模式字符串精確匹配的數(shù)據(jù)內(nèi)容，則該匹配成功。此外，還有其他許多模式匹配算法，如AC，AC_BM，KMP算法等，這些算法都是針對(duì)一條或多條明確的字符串進(jìn)行精確的匹配，而我們實(shí)際應(yīng)用的規(guī)則中很大一部分都包括多樣化的通配符，這種情況是傳統(tǒng)的針對(duì)明確字符串形式的模式匹配算法所不能解決的。因此，我們有必要對(duì)傳統(tǒng)的字符串匹配算法進(jìn)行改進(jìn)，使之能夠適應(yīng)對(duì)規(guī)則的匹配。在傳統(tǒng)的模式匹配算法中，一種比較經(jīng)典的方法是利用多個(gè)模式串構(gòu)建一個(gè)有限自動(dòng)機(jī)，自動(dòng)機(jī)是結(jié)構(gòu)化的，這樣每個(gè)前綴都可以用唯一的狀態(tài)來標(biāo)志。那么我們沿用這種思想，仍然用有限自動(dòng)機(jī)來匹配規(guī)則。

2 多模式DFA的大小和組合算法

有限自動(dòng)機(jī)有兩個(gè)主要的分類：確定有限自動(dòng)機(jī)（DFA）和不確定有限自動(dòng)機(jī)（NFA）。一個(gè)DFA包括一組有限的輸入信號(hào)，表示為∑，一組有限的狀態(tài)，一個(gè)狀態(tài)轉(zhuǎn)換函數(shù)δ[4]。

為了處理m條規(guī)則，可以有兩種選擇。一種是把這m條規(guī)則編輯到一個(gè)自動(dòng)機(jī)中，另外一種是在m個(gè)自動(dòng)機(jī)中分別處理它們。在基于DFA的系統(tǒng)中，把m條規(guī)則編輯到一個(gè)合成的DFA中比運(yùn)行m個(gè)單獨(dú)的DFA更能夠保證性能上的改善。特別的 ，一個(gè)合成的DFA的處理耗費(fèi)從原來每個(gè)字符的O（m） （每個(gè)單獨(dú)的自動(dòng)機(jī)為O（1））減少到O（1）。然而，合成的自動(dòng)機(jī)中的狀態(tài)的數(shù)量理論上最壞的情況可以達(dá)到O（2mn）（n為規(guī)則長度）。由于DFA對(duì)每一個(gè)輸入字符有一個(gè)確定的（O（1））的計(jì)算花銷，我們關(guān)注的是存儲(chǔ)花銷.內(nèi)存空間的使用有兩種來源：狀態(tài)和狀態(tài)轉(zhuǎn)換.狀態(tài)轉(zhuǎn)換的數(shù)目與狀態(tài)的數(shù)目呈線性關(guān)系，因?yàn)槊總€(gè)狀態(tài)最多能與下一個(gè)狀態(tài)有28條（針對(duì)所有的ASCII字符）連接。因此，我們認(rèn)為狀態(tài)的數(shù)目是決定內(nèi)存空間使用情況的首要因素，并且我們所有的研究都是基于最小化的DFA進(jìn)行的。

當(dāng)我們把多條規(guī)則編輯到一個(gè)合成的DFA中時(shí)，會(huì)產(chǎn)生多條規(guī)則間的交互。在有些情況下，合成的DFA的狀態(tài)數(shù)目等于或少于多個(gè)單獨(dú)的DFA的狀態(tài)數(shù)目數(shù)量之和。因此，它能夠在不引起額外的內(nèi)存耗費(fèi)[3，5]的前提下提高處理的速度。然而在另外一些情況下，合成DFA的狀態(tài)數(shù)目能夠呈現(xiàn)出指數(shù)型的增長趨勢(shì)。因?yàn)榫W(wǎng)絡(luò)應(yīng)用中的模式之間是相互交迭的，所以導(dǎo)致DFA中的狀態(tài)數(shù)目呈指數(shù)型增長。針對(duì)這些情況，我們提出組合算法，它有選擇性地把規(guī)則進(jìn)行組合，并且能夠避免規(guī)則間不利的交互。

2.1 規(guī)則間的交互

當(dāng)模式前綴被共享時(shí)，一些狀態(tài)能夠被合并，組合這些模式能夠節(jié)省存儲(chǔ)和計(jì)算耗費(fèi)。如果模式不共享前綴的話，把m個(gè)模式集中在一起會(huì)產(chǎn)生2m個(gè)狀態(tài)。合成的DFA會(huì)產(chǎn)生很多在單獨(dú)的DFA中不存在的狀態(tài)，我們需要?jiǎng)?chuàng)建新的狀態(tài)來記錄這種情況。

2.2 網(wǎng)絡(luò)應(yīng)用中的規(guī)則交互

如果有70個(gè)模式被單獨(dú)的編輯到70個(gè)DFA中，每個(gè)DFA含有成百上千的狀態(tài)，那么70個(gè)DFA總共的狀態(tài)數(shù)目是9795個(gè)。當(dāng)我們把多個(gè)模式組合到一個(gè)合成的DFA中的時(shí)候，處理耗費(fèi)就會(huì)降低，如圖1中的下降的實(shí)線所示。然而，DFA中總共的狀態(tài)數(shù)目（合成的DFA中的狀態(tài)數(shù)目和未組合的DFA中的狀態(tài)數(shù)目之和）增加到超過136，786個(gè)，這還僅僅是只有40個(gè)模式的情況，如圖1中上升的實(shí)線所示。然而，并不是所有的模式都能夠引DFA的狀態(tài)數(shù)目的顯著增長。只有一些模式（如圖1中的模式12等）會(huì)導(dǎo)致DFA的狀態(tài)數(shù)目的顯著增長：這些模式都包括很大數(shù)量的通配符，有時(shí)還包含類字符。

圖1 多個(gè)模式合成的DFA的大小和處理的復(fù)雜度

2.3 規(guī)則組合算法

在前面我們提到，當(dāng)模式被編輯到一起的時(shí)候會(huì)相互影響，會(huì)導(dǎo)致合成DFA的狀態(tài)數(shù)目很多。因此我們提出一個(gè)算法，它有選擇的把m個(gè)模式組合成k個(gè)組這樣使得每個(gè)組的模式互相之間不會(huì)產(chǎn)生不利的影響。這樣，這些算法在不引起額外的內(nèi)存耗費(fèi)的同時(shí)把計(jì)算的復(fù)雜性從O（m）減少到O（k）。

我們首先給交互一個(gè)正式的定義：如果兩個(gè)模式合成的DFA包括的狀態(tài)數(shù)目比兩個(gè)單獨(dú)的DFA的狀態(tài)數(shù)目之和多，則兩個(gè)模式互相交互。

我們使用兩兩之間的交互信息來對(duì)m條規(guī)則進(jìn)行組合。我們的想法是如果在任何從R1，R2，R3中選出的規(guī)則對(duì)中沒有交互，那么很有可能合成R1，R2，R3構(gòu)成的DFA的狀態(tài)數(shù)目不會(huì)超過單獨(dú)的DFA的數(shù)目之和。相反的情況只發(fā)生在規(guī)則共享前綴的時(shí)候。然而在實(shí)際的網(wǎng)絡(luò)應(yīng)用中共享前綴是并不普遍的，因?yàn)槊織l規(guī)則主要是針對(duì)一個(gè)特定的協(xié)議或攻擊寫的。

我們針對(duì)多核處理器結(jié)構(gòu)設(shè)計(jì)了組合算法。

在這種結(jié)構(gòu)中，有多個(gè)能夠并行運(yùn)行的處理單元。處理單元的數(shù)目是有限的，它比規(guī)則的數(shù)目少得多。因此，每個(gè)處理單元針對(duì)每種規(guī)則運(yùn)行一個(gè)DFA是不可行的。我們的目標(biāo)是設(shè)計(jì)把規(guī)則組合成幾組的算法，這樣一個(gè)處理單元能夠運(yùn)行一個(gè)或幾個(gè)合成的DFA。下面我們將給出算法的偽代碼。

在這個(gè)算法中，我們首先計(jì)算得出規(guī)則的兩兩交互信息。有了這些兩兩的交互信息，我們構(gòu)建一個(gè)圖表，每個(gè)模式都作為頂點(diǎn)，如果模式Ri和Rj之間互相交互，則在它們之間劃一條邊。用這個(gè)圖，我們從一個(gè)和其他模式具有最少交互的模式開始，然后嘗試向同一組中增添不與它產(chǎn)生交互的模式。我們一直增添模式，直到合成的DFA的大小超過了內(nèi)存的限制。然后我們從剩下的未組合的模式中再創(chuàng)建一個(gè)新組。

3 性能評(píng)價(jià)

我們對(duì)于網(wǎng)絡(luò)上運(yùn)行基于DFA掃描器的吞吐量進(jìn)行度量。結(jié)果如圖3所示。當(dāng)規(guī)則被組合為10個(gè)組時(shí)，對(duì)合成的DFA掃描比對(duì)未組合的DFA的情況相比仍然獲得了310%－410%的性能改善。當(dāng)我們把組的數(shù)目降到3時(shí)，它獲得了362%－536%的性能改善。

如果網(wǎng)絡(luò)流量中主要是包括很長的入侵包，平均的包有效載荷長度會(huì)很大（即圖2中的dump A）。如果網(wǎng)絡(luò)流量中大多數(shù)的包都是正常流量，平均的包有效載荷會(huì)小很多，并且占很大比率的ICMP和ARP包都非常短并且能夠匹配7層過濾器中的任何協(xié)議，這種情況下，系統(tǒng)的吞吐量比前一種情況大（即圖2中的dump B）。

圖2 基于DFA掃描的吞吐量

4 結(jié)束語

我們分析了網(wǎng)絡(luò)應(yīng)用中快速規(guī)則掃描的實(shí)現(xiàn)。在實(shí)現(xiàn)的過程中我們通常采用基于NFA的方法，因?yàn)镈FA的實(shí)現(xiàn)會(huì)造成狀態(tài)數(shù)目呈指數(shù)型增長因而增加內(nèi)存的耗費(fèi)。為了解決這個(gè)問題，我們提出了一個(gè)方案：選擇性地把模式組合起來能3到5倍地加速匹配處理的過程。實(shí)驗(yàn)結(jié)果說明，我們達(dá)到的吞吐量比未對(duì)規(guī)則進(jìn)行組合的DFA多了3.1到4.1倍，它動(dòng)態(tài)地增加規(guī)則的匹配速度，而不需要明顯的增加對(duì)內(nèi)存空間的使用。但是對(duì)規(guī)則的組合算法我們?nèi)匀恍枰鲞M(jìn)一步的探討，使之不斷完善和改進(jìn)，以更適合實(shí)際應(yīng)用的需要。是否有更為高效的規(guī)則組合算法，還有待于我們進(jìn)一步地探討和研究。