楊嘉佳，姜臘林，姜 磊，戴 瓊，譚建龍

(1.長沙理工大學計算機與通信工程學院，長沙 410114;2.中國科學院計算技術研究所，北京 100190;3.中國科學院信息工程研究所，北京 100093)

1 概述

網(wǎng)絡入侵檢測(Network Intrusion Detection，NID)系統(tǒng)在網(wǎng)絡安全領域扮演著越來越重要的作用。當前的NID，比如Bro［1］、Snort［2］和L7-filter 主要利用特征來描述和檢測網(wǎng)絡入侵行為。傳統(tǒng)的特征都是基于精確串模式來描述，但是隨著智能攻擊，傳統(tǒng)的基于精確串的特征描述難以準確地描述這些新型攻擊的復雜特征，導致基于精確串的入侵檢測準確率降低。由于正則表達式具有豐富和靈活的表達能力，當前的NID 已采用正則表達式替代精確串來描述攻擊特征。據(jù)統(tǒng)計，截至2013 年，Snort 已經(jīng)有超過1 500條正則表達式規(guī)則。針對ClusterFA 算法存在的問題，本文對類中心向量表CommonTable 行之間的冗余建立索引表，同時利用游程編碼(Ren-length Encoding，RLE)［3］對連續(xù)重復轉(zhuǎn)移狀態(tài)進行編碼。

2 背景介紹

傳統(tǒng)的正則表達式匹配算法都是用確定型有限自動機(Deterministic Finite Automaton，DFA)和非確定型有限自動機(Nondeterministic Finite Automaton，NFA)來實現(xiàn)。NFA 的時間復雜度是O(n2)，空間復雜度是O(n)，而DFA 最壞情況下的時間復雜度為O(1)，空間復雜度為O(2n)，容易遭遇空間爆炸性問題。NFA 的時間復雜度是其理論模型決定的，在不改變處理器體系結(jié)構(gòu)的情況下很難對其進行改進，因此，當前的研究大多集中于對DFA 的內(nèi)存空間進行縮減。

自1960 年以來，大量與DFA 相關的算法和理論已經(jīng)被提出［4-6］，包括D2FA、δFA［7］、CRD、混合結(jié)構(gòu)自動機、基于歷史記錄的自動機［8］以及XFA 等，這些方法都是以時間換空間，通過增加計算量來減少內(nèi)在空間的使用。

文獻［9］發(fā)現(xiàn)較為復雜的正則表達式會造成DFA狀態(tài)數(shù)呈指數(shù)級增長。為了避免這種情況，提出改寫規(guī)則的思想，顯著地減少了DFA 狀態(tài)數(shù)目。此外，還提出將正則表達式進行分組的思想，將具有較大相關度的正則表達式分到不同的組里，盡可能減少表達式之間的交互作用，從而減少DFA 所需存儲空間。

文獻［10］提出D2FA 表示方法，認為如果2 個狀態(tài)對于相同的輸入字符具有相同的跳轉(zhuǎn)目標，那么這2 個狀態(tài)是等價的。對于等價的狀態(tài)，用一條默認轉(zhuǎn)移邊把2 個等價的狀態(tài)連接起來，通過引入默認轉(zhuǎn)移來減少狀態(tài)轉(zhuǎn)移的數(shù)目，從而降低自動機的存儲空間，實驗結(jié)果表明D2FA 比DFA 減少存儲空間90%以上，但是引入默認轉(zhuǎn)移邊導致一個字符可能需要多次訪存，會降低DFA 的匹配性能。為了解決這個問題，文獻［11］對D2FA 進行了改進，提出了CD2FA。CD2FA 不僅具有類似于D2FA 的壓縮效果，而且由于它使用了哈希函數(shù)，可以直接計算出對應于每個字符的跳轉(zhuǎn)目標，與原始DFA 一樣，每處理一個字符時只需訪問1 個狀態(tài)，使得CD2FA 吞吐量與原始的DFA 相當。

文獻［12］提出另一種消除狀態(tài)間由等價項而形成的冗余方法，稱為δFA。通過觀察發(fā)現(xiàn)，在DFA中相鄰的狀態(tài)之間，通常會有大量的等價項，所以提出為DFA 增加一個臨時轉(zhuǎn)換表，而不必像D2FA 那樣使用缺省轉(zhuǎn)換。δFA 并不能完全避免冗余，而且它還必須增加額外的操作來更新臨時轉(zhuǎn)換表項，所以大量的更新操作可能會降低DFA 的匹配效率。

文獻［13］通過觀察DFA 的狀態(tài)轉(zhuǎn)移表，注意到每一個狀態(tài)都有大量相似的轉(zhuǎn)移狀態(tài)，只有少量(＜1%)不同的轉(zhuǎn)移狀態(tài)。通過分析D2FA，發(fā)現(xiàn)該算法是從相鄰的狀態(tài)來減少冗余，是一種局部的算法。因此從全局的視角出發(fā)，提出了一種新穎的可以大幅度縮減DFA 空間的算法，稱為ClusterFA 算法，并首次采用簇聚類技術來解決DFA 的壓縮問題。實驗證明，相對原始DFA 而言，能減少95%的空間消耗。但是該算法的壓縮效率與分組個數(shù)K 值密切相關，而確定K 值需要較大的時間復雜度。此外，觀察實驗結(jié)果發(fā)現(xiàn)，算法類中心向量表CommonTable 行與行之間存在冗余，以及每行的轉(zhuǎn)移狀態(tài)有較高的重復率，因此，該方法的壓縮率還可以進一步提高。

3 ClusterFA 算法

ClusterFA 算法是在研究D2FA，δFA 時提出來的，是一種基于冗余消除達到內(nèi)存空間縮減目的的DFA 壓縮算法。

視DFA 狀態(tài)轉(zhuǎn)移表為一個N ×C 大小的矩陣，命名為DFAMatrix。其中，N 表示狀態(tài)的數(shù)目;C 是字母個數(shù)，其值一般等于ASCII 字母表字符個數(shù)256。DFAMatrix［s，c］定義了當輸入字符c 時，狀態(tài)從s 轉(zhuǎn)移到下一狀態(tài)。

ClusterFA 算法通過clusterStates()函數(shù)把類似的狀態(tài)分成K 個分組，命名為Groups，同時建立索引表IndexTable 記錄DFA 狀態(tài)屬于哪一分組。然后從Groups 中的每一分組提取一個參考狀態(tài)，建立用于記錄K 個參考狀態(tài)的CommonTable 表和存儲特殊狀態(tài)的稀疏矩陣SparseMatrix 過程，如算法1［13］所示。

假設當前狀態(tài)是s，輸入字符是c。在ClusterFA算法中執(zhí)行一次查找時，首先通過查找IndexTable，找到狀態(tài)所在分組的分組號(id)，再進入Common-Table 表中找到分組id 對應的中間狀態(tài)tcommon。

然后查找(s，c)是否在稀疏矩陣SparseMatrix中，如果存在，把tcommon當作下一個狀態(tài)Snext，否則，把tcommon+SparseMatrix［s］［c］作為下一個狀態(tài)Snext，查找過程偽代碼描述如算法2［13］所示。

算法1

從N-狀態(tài)DFA 建立ClusterFA，其中，Groups［i］表示聚類的第i 個分組

算法2

4 基于ClusterFA 算法的改進

4.1 ClusterFA 算法分析

對于一個新的DFA，ClusterFA 算法很難決定將其分為多少分組較為合適。也就是說，無法提前確定分組個數(shù)K 的理想值。更重要的是，K 值直接與壓縮效率有關。文獻［13］提出2 種方法來尋找理想K 值，第1 種方法是利用分層聚類方法從N 中找到合適的K 值;第2 種方法是采用人工方法利用不同的K 值來測試聚類算法，并找到理想K 值。第1 種方法的時間復雜度是O(N3)，其中，N 為狀態(tài)的數(shù)量，這種方法對于大規(guī)模DFA 來說并不適用。一般地，采用第2 種方法來尋找合適的K 值，但是在實際應用中用人工的方法從N 中找到理想K 值，工作量又太大，例如，對分組數(shù)K 與編譯時間的關系進行實驗(實驗環(huán)境:處理器酷睿雙核T5750 2.00 GHz，內(nèi)存1 GB，Win7 操作系統(tǒng))，結(jié)果如表1 所示，隨著分組數(shù)K 的增加，編譯時間也不斷增長。

表1 編譯時間與分組數(shù)關系 h

由于很難找到理想K 值，通過聚類算法得到的CommonTable 表會出現(xiàn)很多有相同首尾的重復行，如圖1 所示，可以看出重復行占總行數(shù)9%～22%，而且CommonTable 表中重復行首尾相同部分占整行比例范圍為86.1%～96.1%，統(tǒng)計結(jié)果如表2 所示。因此，通過提取CommonTable 表中重復行的相同首尾部分建立索引表，減少CommonTable 表消耗的內(nèi)存空間。

圖1 各規(guī)則集重復行占總行數(shù)比例

表2 各規(guī)則集重復行首尾相同部分占整行比例 %

此外，通過ClusterFA 中的聚類算法進行聚類后，CommonTable 表每行中會出現(xiàn)很多連續(xù)重復轉(zhuǎn)移狀態(tài)。假設連續(xù)重復的轉(zhuǎn)移狀態(tài)為一個片斷，根據(jù)統(tǒng)計，轉(zhuǎn)移狀態(tài)重復數(shù)為1 的片斷、轉(zhuǎn)移狀態(tài)重復數(shù)為2 的片斷與轉(zhuǎn)移狀態(tài)重復數(shù)為3 的片斷占整行的比例如圖2 所示。從圖中可以看出，長度大于2的片斷占據(jù)了相當比例，因此，設計一種策略對CommonTable 表進行壓縮以進一步節(jié)省內(nèi)存空間。

圖2 連續(xù)重復轉(zhuǎn)移狀態(tài)的各長度片斷所占比例

4.2 Cluster 算法改進方法

為了保證較好的壓縮效果，采用一種RLE 的變體［14］進行編碼。對于連續(xù)重復的轉(zhuǎn)移狀態(tài)number，假設其重復次數(shù)為w(w≥2)，由于DFA 轉(zhuǎn)移狀態(tài)數(shù)值不為負數(shù)，可以用(-256 -w)來表示連續(xù)重復的w 個轉(zhuǎn)移狀態(tài);對于單個轉(zhuǎn)移狀態(tài)(w=1)，直接用該轉(zhuǎn)移狀態(tài)表示。例如對序列{1，1，1，2，4，3，4}編碼得，-259，1，2，4，3，4。

首先，利用ClusterFA 算法［13］將圖3 等價的原始DFA 表分解為CommonTable 表與SparseMatrix 表，分解過程示例如圖4 所示;然后，在ClusterFA 算法基礎上進行擴展，將CmmonTable 表分解成RLE_M 表與Rest_Table 表，并進行RLE 壓縮后，得到RLE_Index表和RLE_Compress 表，過程示例如圖5 所示。

圖3 DFA 轉(zhuǎn)移狀態(tài)

圖4 原始DFA 的分解

圖5 分解壓縮

4.2.1 建表過程

建表過程分成4 個步驟:

(1)遍歷整個CommonTable 表，將有首尾相同部分com_pre，且首尾相同部分長度L≥6 的行劃為一分組，記錄各行的行號id，剩下的不符合條件的行，不用分組，不記錄其行號id。假設符合條件的分組數(shù)量為X，如果X≥2，執(zhí)行步驟(2);否則，執(zhí)行步驟(4)。

(2)記錄每個分組的某一行中與com_pre 不同的部分non_com 的偏移位置，記為(start_pos，last_pos)。其中，start_pos 表示non_com 頭與行首的偏移量，last_pos 表示non_com 尾與行首的偏移量。對com_pre 進行RLE 壓縮得pre，將(各行id，-2，start_pos，last_pos，pre，-1)放入索引表。-1 作為索引表RLE_Index 中分組與分組之間分隔標志，-2 作為區(qū)分id 與start_pos 的界限標志。對CommonTable 表建立REL_Index，結(jié)果如下:1 3，-2，5 6，-260 1 -258 3-1，由于RLE_Index 需要記錄有首尾相同部分的行id，non_com 的偏移位置start_pos，last_pos，以及用-2，-1 作為界限標志，所以需要額外的空間開銷，為了保證壓縮效果，在步驟(1)中只對有首尾相同部分且L≥6 的行在索引表REL_Index 中建立表項。接著執(zhí)行步驟(3)。

(3)假設CommonTable 提取首尾相同部分后，余下部分為Rest_Table 表，對Rest_Table 的每一行進行RLE 編碼壓縮，最終的壓縮結(jié)果為一維數(shù)組RLE_Compress，Rest_Table 的每一行壓縮后占一維數(shù)組的一個片斷，用-1 表示一行的結(jié)束。

(4)執(zhí)行這一步，表明CommonTable 表沒有首尾相同部分的行，此時，只需對整個CommonTable 表進行RLE 編碼，得到RLE_Compress 表。

建表過程偽碼如算法3 所示，第1 行has_common_Part()函數(shù)判斷CommonTable 表中是否有首尾相同部分且首尾相同部分長度L ＞4 的行。如果有，則利用divide()函數(shù)將CommonTable 表分成X個分組Groups，第4 行proces_com_part ()函數(shù)將分組的首尾相同部分提取出來，第5 行RLE()函數(shù)對com_pre 進行游程編碼，第6 行put()用于將(id，-2，start_pos，last_pos，pre，-1)片斷放入RLE_Index中，第8 行表示從CommonTable 中去掉所有com_pre后，剩余部分為Rest_Table。

算法3

4.2.2 查找過程

假設當前狀態(tài)是s，輸入字符是c，為了查找到下一跳狀態(tài)，需要執(zhí)行以下步驟:

(1)通過查找IndexTable［12］，找到狀態(tài)所在分組的id，假設為y。

(2)通過搜索RLE_Index 表中‘各行id'字段，判斷y 是否在RLE_Index 表中;如果y 在RLE_Index表中，則得到其對應的pre，start_pos，last_post，執(zhí)行步驟(3);若不在，則執(zhí)行步驟(4)。

(3)將pre 的前start_pos 位、RLE_Compress 中的第y 個片斷和pre 的后(256 -last_post-1)位連接起來并解碼得到向量pre_RLE_Compress，通過pre_RLE _ Compress ［c］→中 間 狀 態(tài) tcommon，執(zhí)行步驟(5)。

(4)將RLE_Compress 中第y 個片斷解碼得到向量RLE_Compress'，通過RLE_Compress'［c］→中間狀態(tài)tcommon，執(zhí)行步驟(5)。

(5)查找(s，c)是否在稀疏矩陣SparseMatrix中，如果不存在，把tcommon當作下一個狀態(tài)Snext，否則把tcommon+SparseMatrix［s］［c］作為下一個狀態(tài)Snext。

查找過程偽碼描述如算法4 所示。其中，decoded(the y fragment of RLE_Compress)表示對RLE_Compress 中的第y 個片斷進行解碼，BloomFilter.test(s，c)表示用Bloom 過濾器來判斷(s，c)是否在SparseMatrix 稀疏矩陣中。

算法4

5 實驗結(jié)果分析

實驗環(huán)境:處理器酷睿雙核T5750 2.00 GHz，內(nèi)存1 GB，Win7 操作系統(tǒng)。利用開源工具regex-tool生成原始DFA 狀態(tài)轉(zhuǎn)移表并利用Bro，Snort 和L7-filter 規(guī)則集進行測試。由于空間爆炸問題，很難將L7-filter 規(guī)則集直接生成DFA，因此把L7-filter 分成7 分組，然后利用開源工具regex-tool 生成。同時，也把snort 規(guī)則分成3 分組。規(guī)則集的具體情況如表3所示［12］。

表3 規(guī)則集的具體情況

En_ClusterFA 壓縮率公式:

ClusterFA 壓縮率公式:

經(jīng)過對經(jīng)典的DFA 算法δFA，D2FA，以及ClusterFA 算法、En_ClusterFA 進行測試，δFA，D2FA采用文獻［12］中原有數(shù)據(jù)，而對ClusterFA 算法、En_ClusterFA 分別利用式(1)、式(2)測試20 次，然后取平均值，得到的壓縮率如表4 所示。

以規(guī)則集為橫坐標，壓縮率為縱坐標，將表4 繪制成趨勢圖，如圖6 所示，同時將表4 中ClusterFA算法與En_ClusterFA 測試結(jié)果進行繪圖，如圖7所示。

從圖6 可以看出，En_ClusterFA 的壓縮率是最好的，而且壓縮率曲線相比其他算法更穩(wěn)定。而從圖7 也可以看出，En _ ClusterFA 的壓縮率較ClusterFA 算法有較好改善，平均壓縮率從ClusterFA算法的95%提升到了99%。

表4 δFA，D2FA，ClusterFA，En_ClusterFA 算法壓縮率

圖6 各規(guī)則集的壓縮率趨勢

圖7 ClusterFA 算法與En_ClusterFA 壓縮率對比

但是，En_ClusterFA 算法過程中使用了RLE 編碼，這并不適合于用軟件來實現(xiàn)，因為編解碼會消耗太多時間，從而導致該算法吞吐率較ClusterFA算法下降，如表5、圖8 所示為軟件實現(xiàn)該算法的吞吐率情況，后續(xù)工作將進一步從減少編解碼所消耗的時間入手，利用FPGA 硬件的并行性特點，對RLE 編解碼過程進行優(yōu)化，提高En_ClusterFA 的吞吐率。

表5 吞吐率比較 (MB·s -1)

圖8 ClusterFA 和En_ClusterFA 吞吐率比較

6 結(jié)束語

本文針對ClusterFA 算法的數(shù)據(jù)冗余問題進行研究，結(jié)合游程編碼的優(yōu)點，提出了改進算法En_ClusterFA。將重復行相同首尾部分分離，然后對整個類中心向量表游程編碼。實驗結(jié)果表明，En_ClusterFA 能夠有效地減少ClusterFA 算法的數(shù)據(jù)冗余，減少存儲空間消耗。今后的研究重點是利用現(xiàn)場可編程門陣列［14-16］加速En_ClusterFA 算法的編碼與解碼，減少編碼與解碼所消耗的時間，提高吞吐率。

［1］Paxson V.A System for Detecting Network Intruders in Real-time［J］.Computer Networks，1999，31 (23):2435-2463.

［2］Roesch M.Snort-lightweight Intrusion Detection for Networks［C］//Proc.of the 13th USENIX Conference on System Administration.Seattle，USA:［s.n.］，1999:229-238.

［3］蒙繼華，孫寶生，李 婷.采用行程編碼進行位圖壓縮的研究［J］.新疆大學學報，2003，20(4):121-123.

［4］Yates R B，Gonnet H.Fast Text Searching for Regular Expressions or Automation Searing on Tries［J］.Journal of the ACM，1996，43(6):915-936.

［5］Myers G.A Four Russians Algorithm for Regular Expression Pattern Matching［J］.Journal of the ACM，1992，39(2):432-448.

［6］Thompson K.Programming Techniques:Regular Expression Searching Algorithm［J］.Communications of the ACM，1968，11(6):419-422.

［7］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.

［8］Kumar S，Chandrasekaran B，Turner J，et al.Curing Regular Expressions Matching Algorithms from Insomnia，Amnesia，and Acalculia［C］//Proc.of the 3rd ACM/IEEE Symposium on Architecture for Networking and Communications Systems.Washington D.C.，USA:［s.n.］，2007:144-164.

［9］Yu Fang，Chen Zhifeng，Diao Yanlei，et al.Fast and Memory-efficient Regular Expression Matching for Deep Packet Inspection［C］//Proc.of ACM/IEEE Symposium on Architecture for Networking and Communications Systems.New York，USA:［s.n.］，2006:93-102.

［10］Kumar S，Crowley P，Yu Fang，et al.Algorithms to Accelerate Multiple Regular Expressions Matching for Deep Packet Inspection［C］//Proc.of Annual Conference of ACM Special Interest Group on Data Communication.Pisa，Italy:［s.n.］，2006:339-350.

［11］Kumar S，Turner J，Williams J.Advanced Algorithms for Fast and Scalable Deep Packet Inspection［C］//Proc.of ACM/IEEE Symposium on Architecture for Networking and Communications Systems.［S.l.］:IEEE Press，2006:81-92.

［12］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.

［13］Jiang Lei，Tan Jianlong，Liu Yuanbin.ClusterFA:A Memory-efficient DFA Structure for Network Intrusion Detection［C］//Proc.of the 7th ACM Symposium on Information，Computer and Communications Security.Seoul，South Korea:［s.n.］，2012:65-66.

［14］Lee J，Hwang S H，Park N，et al.A High Performance NIDS Using FPGA-based Regular Expression Matching［C］//Proc.of ACM Symposium on Applied Computing.New York，USA:［s.n.］，2007:1187-1191.

［15］Faezipour M，Nourani M.Constraint Repetition Inspection for Regular Expression on FPGA［C］//Proc.of the 16th IEEE Symposium on High Performance Interconnects.［S.l.］:IEEE Press，2008:111-118.

［16］Yang Y，Prasanna V K.Automatic Construction of Largescale Regular Expression Matching Engines on FPGA［C］//Proc.of the International Conference on Reconfigurable Computing and FPGAs.［S.l.］:IEEE Press，2008:73-78.