基于簇聚类和游程编码的正则表达式压缩算法

杨嘉佳，姜腊林，姜 磊，戴 琼，谭建龙

(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.