基于规则分组的DFA正则表达式匹配算法

作者：朱俊

来源：湖南工程学院学报(自然科学版), 2021, 31(2): 49-53.

DOI：10.3969/j.issn.1671-119X.2021.02.008

• 入侵检测系统
• 模式匹配
• 正则表达式
• 确定性有限自动机

模式匹配因误报率低和漏报率低被入侵检测所采用.在使用正则表达式构造DFA时,因状态爆炸导致匹配算法需要较多的存储空间和运行时间,算法效率低下,采用规则分组后,可以在一定程度上抑制状态爆炸问题.根据缓存中的历史记录对正则表达式进行分组,既能利用规则分组减少状态总数,抑制状态爆炸,又能减少因每次重新构建DFA所带来的开销,提高了匹配效率,有利于提高入侵检测的实时性、准确性和高效性.

• 单位
  电子信息工程学院; 安徽水利水电职业技术学院; 合肥工业大学