基于DFA進行規則組合的算法研究

◆許 黎

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

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

規則的使用之所以如此廣泛，是因為它們在描述模式時表現出強大的表達能力。例如，在Linux應用層協議分類器（7層過濾器）[1]中，所有的協議標識符都被表示為規則。同樣地，Snort[2]入侵檢測系統從2003年4月在規則集中從沒有規則發展到現在使用超過4867條規則。另一個入侵檢測系統Bro[3]，也把規則作為模式語言使用。

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

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

為了避免規則匹配時的低效，針對高速處理的要求，本文首先分析導致DFA的狀態數目呈指數型增長的規則的結構特征，并提出把多個DFA組合到一個組中用來提高匹配速度的解決方案。即在不引起增加內存耗費的前提下有選擇的把多個模式組合成幾組自動機，并通過實驗對我們的組合算法進行測試。

1 背景和相關工作

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

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

有限自動機有兩個主要的分類：確定有限自動機（DFA）和不確定有限自動機（NFA）。一個DFA包括一組有限的輸入信號，表示為∑，一組有限的狀態，一個狀態轉換函數δ[4]。

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

當我們把多條規則編輯到一個合成的DFA中時，會產生多條規則間的交互。在有些情況下，合成的DFA的狀態數目等于或少于多個單獨的DFA的狀態數目數量之和。因此，它能夠在不引起額外的內存耗費[3，5]的前提下提高處理的速度。然而在另外一些情況下，合成DFA的狀態數目能夠呈現出指數型的增長趨勢。因為網絡應用中的模式之間是相互交迭的，所以導致DFA中的狀態數目呈指數型增長。針對這些情況，我們提出組合算法，它有選擇性地把規則進行組合，并且能夠避免規則間不利的交互。

2.1 規則間的交互

當模式前綴被共享時，一些狀態能夠被合并，組合這些模式能夠節省存儲和計算耗費。如果模式不共享前綴的話，把m個模式集中在一起會產生2m個狀態。合成的DFA會產生很多在單獨的DFA中不存在的狀態，我們需要創建新的狀態來記錄這種情況。

2.2 網絡應用中的規則交互

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

圖1 多個模式合成的DFA的大小和處理的復雜度

2.3 規則組合算法

在前面我們提到，當模式被編輯到一起的時候會相互影響，會導致合成DFA的狀態數目很多。因此我們提出一個算法，它有選擇的把m個模式組合成k個組這樣使得每個組的模式互相之間不會產生不利的影響。這樣，這些算法在不引起額外的內存耗費的同時把計算的復雜性從O（m）減少到O（k）。

我們首先給交互一個正式的定義：如果兩個模式合成的DFA包括的狀態數目比兩個單獨的DFA的狀態數目之和多，則兩個模式互相交互。

我們使用兩兩之間的交互信息來對m條規則進行組合。我們的想法是如果在任何從R1，R2，R3中選出的規則對中沒有交互，那么很有可能合成R1，R2，R3構成的DFA的狀態數目不會超過單獨的DFA的數目之和。相反的情況只發生在規則共享前綴的時候。然而在實際的網絡應用中共享前綴是并不普遍的，因為每條規則主要是針對一個特定的協議或攻擊寫的。

我們針對多核處理器結構設計了組合算法。

在這種結構中，有多個能夠并行運行的處理單元。處理單元的數目是有限的，它比規則的數目少得多。因此，每個處理單元針對每種規則運行一個DFA是不可行的。我們的目標是設計把規則組合成幾組的算法，這樣一個處理單元能夠運行一個或幾個合成的DFA。下面我們將給出算法的偽代碼。

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

3 性能評價

我們對于網絡上運行基于DFA掃描器的吞吐量進行度量。結果如圖3所示。當規則被組合為10個組時，對合成的DFA掃描比對未組合的DFA的情況相比仍然獲得了310%－410%的性能改善。當我們把組的數目降到3時，它獲得了362%－536%的性能改善。

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

圖2 基于DFA掃描的吞吐量

4 結束語

我們分析了網絡應用中快速規則掃描的實現。在實現的過程中我們通常采用基于NFA的方法，因為DFA的實現會造成狀態數目呈指數型增長因而增加內存的耗費。為了解決這個問題，我們提出了一個方案：選擇性地把模式組合起來能3到5倍地加速匹配處理的過程。實驗結果說明，我們達到的吞吐量比未對規則進行組合的DFA多了3.1到4.1倍，它動態地增加規則的匹配速度，而不需要明顯的增加對內存空間的使用。但是對規則的組合算法我們仍然需要做進一步的探討，使之不斷完善和改進，以更適合實際應用的需要。是否有更為高效的規則組合算法，還有待于我們進一步地探討和研究。