基于簇聚類和游程編碼的正則表達式壓縮算法

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

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

1 概述

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

2 背景介紹

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

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

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

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

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

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

3 ClusterFA 算法

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

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

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

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

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

算法1

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

算法2

4 基于ClusterFA 算法的改進

4.1 ClusterFA 算法分析

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

表1 編譯時間與分組數關系 h

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

圖1 各規則集重復行占總行數比例

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

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

圖2 連續重復轉移狀態的各長度片斷所占比例

4.2 Cluster 算法改進方法

為了保證較好的壓縮效果，采用一種RLE 的變體［14］進行編碼。對于連續重復的轉移狀態number，假設其重復次數為w(w≥2)，由于DFA 轉移狀態數值不為負數，可以用(-256 -w)來表示連續重復的w 個轉移狀態;對于單個轉移狀態(w=1)，直接用該轉移狀態表示。例如對序列{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 轉移狀態

圖4 原始DFA 的分解

圖5 分解壓縮

4.2.1 建表過程

建表過程分成4 個步驟:

(1)遍歷整個CommonTable 表，將有首尾相同部分com_pre，且首尾相同部分長度L≥6 的行劃為一分組，記錄各行的行號id，剩下的不符合條件的行，不用分組，不記錄其行號id。假設符合條件的分組數量為X，如果X≥2，執行步驟(2);否則，執行步驟(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 作為區分id 與start_pos 的界限標志。對CommonTable 表建立REL_Index，結果如下: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 中建立表項。接著執行步驟(3)。

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

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

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

算法3

4.2.2 查找過程

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

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

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

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

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

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

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

算法4

5 實驗結果分析

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

表3 規則集的具體情況

En_ClusterFA 壓縮率公式:

ClusterFA 壓縮率公式:

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

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

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

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

圖6 各規則集的壓縮率趨勢

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

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

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

圖8 ClusterFA 和En_ClusterFA 吞吐率比較

6 結束語

本文針對ClusterFA 算法的數據冗余問題進行研究，結合游程編碼的優點，提出了改進算法En_ClusterFA。將重復行相同首尾部分分離，然后對整個類中心向量表游程編碼。實驗結果表明，En_ClusterFA 能夠有效地減少ClusterFA 算法的數據冗余，減少存儲空間消耗。今后的研究重點是利用現場可編程門陣列［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.