一组提高存储效率的深度包检测算法

• 作者: 于强 霍红卫
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 深度包检测 正则表达式 多模式匹配 复合的FSM D2FA(delayed input DFA) WD2FA(weighted delayed input DFA)
• 年，卷（期）: 2011,（1）
• 页码范围: 149-163
• 分类号: TP393
• 字数: 10550字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2011.03724

摘要

随着深度包检测规则数目的剧烈增长.为了适应网络处理的需求,必须对表示正则表达式的DFA(deterministic finite automata,确定的有限自动机)进行高效的存储一方面,对DFA的状态点数目进行压缩,提出了一种复合的FSM(有限自动机)的构造方法,通过对正则表达转化成DFA的状态点数目复杂度的分析,将不同复杂度的正则表达式采用不同的方式构建DFA,使得所有平方级和指数级复杂度的状态点数目降低到了线性级.另一方面,对DFA队的状态转移数目进行压缩,给出了一种高效的压缩算法,即WD2FA(weighted delayed input DFA,带权延迟DFA)算法,对于任意复杂度的正则表达式都可以将状态转移数目压缩为原来的5%左右,相对于D2FA(delayed input DFA,延迟的DFA)有更好的压缩能力,并且使得D2FA是WD2FA在权值为O情况下的特例.实验结果表明,有限自动机的状态点数目能够控制在线性级,并且在状态点压缩的基础上将状态转移数目压缩为原来的7%.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	霍红卫	西安电子科技大学计算机学院	29	436	11.0	20.0
2	于强	西安电子科技大学计算机学院	8	44	3.0	6.0