文献类型：期刊文献

中文题名：一种面向深度包检测的DFA压缩算法

英文题名：Algorithm to compress DFA for deep packet inspection

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

机构：[1]中国劳动关系学院计算机应用教研室;[2]青岛农业大学理学与信息学院

年份：2017

卷号：34

期号：5

起止页码：1525

中文期刊名：计算机应用研究

外文期刊名：Application Research of Computers

收录：CSTPCD、、BDHX2014、CSCD_E2017_2018、BDHX、CSCD

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

语种：中文

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

外文关键词：regular expression;;character replacement;;state transition table compression;;deterministic finite automata;;deep packet inspection

中文摘要：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%.