一种面向深度包检测的DFA压缩算法  

Algorithm to compress DFA for deep packet inspection

作　　者：张伟[1] 许海洋[2] 

机构地区：[1]中国劳动关系学院计算机应用教研室,北京100048 [2]青岛农业大学理学与信息学院,山东青岛266109

出　　处：《计算机应用研究》2017年第5期1525-1530,共6页Application Research of Computers

基　　金：国家自然科学基金青年科学基金资助项目(61403223);中国劳动关系学院中央高校基本科研业务费专项基金项目(17ZY005)

摘　　要：DFA(确定性有限自动机)对于实现深度包检测(deep packet inspection,DPI)技术具有重要作用。随着深度包检测规则的不断增多,DFA所需的存储空间急剧增大。为此,提出了一种基于字符替换的DFA压缩算法,利用状态转换表中每个状态通常只有少数几个不同跳转的特点,将状态转换表分解为剩余表和字符替换表,减少了存储空间。此外,通过使相似的状态可以共享相同的字符替换表以进一步压缩存储空间,给出了复杂度为O(n2)的压缩算法,n为DFA的状态数。实验结果表明,该算法在L7-filter和Snort规则集上具有较稳定的压缩率,压缩率都在5%以下。DFA( deterministic finite automata) is very important to achieve deep packet inspection( deep packet inspection,DPI) technology. With the growing number of deep packet inspection rules,the storage space of DFA expands rapidly. Therefore,this paper presented an effective compression algorithm based character replacement. Using the characteristics that the state transition table in each state is often only a few different jumps,it decomposed the state transition table into the remaining table and the character replacement table to make storage space reduce. In addition,many similar states could share the same character replacement table to further compress the storage space. Finally,it presented an O( n2) compression algorithm which n denoted the number of DFA states. The test results show that the proposed algorithm is more stable compression ratio on the L7-filter and Snort rule set,and the compression ratio is below 5%.

关 键 词：正则表达式 字符替换 状态转换表压缩 确定性有限自动机 深度包检测 

分 类 号：TP309.2[自动化与计算机技术—计算机系统结构]