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

• 作者: 张伟 许海洋
• 来源期刊: 计算机应用研究
• 关键词: 正则表达式 字符替换 状态转换表压缩 确定性有限自动机 深度包检测
• 年，卷（期）: 2017,（5）
• 所属期刊栏目: 信息安全技术
• 页码范围: 1525-1530
• 页数: 6页
• 分类号: TP309.2
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2017.05.056

摘要

DFA(确定性有限自动机)对于实现深度包检测(deep packet inspection,DPI)技术具有重要作用.随着深度包检测规则的不断增多,DFA所需的存储空间急剧增大.为此,提出了一种基于字符替换的DFA压缩算法,利用状态转换表中每个状态通常只有少数几个不同跳转的特点,将状态转换表分解为剩余表和字符替换表,减少了存储空间.此外,通过使相似的状态可以共享相同的字符替换表以进一步压缩存储空间,给出了复杂度为O(n2)的压缩算法,n为DFA的状态数.实验结果表明,该算法在L7-filter和Snon规则集上具有较稳定的压缩率,压缩率都在5％以下.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许海洋	青岛农业大学理学与信息学院	22	46	4.0	6.0
2	张伟	中国劳动关系学院计算机应用教研室	17	11	2.0	2.0