一种针对DFA状态爆炸的正则表达式匹配方法
来源：计算机工程杂志2019年第4期北京时间：
作者：王翔,卢毓海,马伟,刘燕兵
单位：1.中国科学院大学 网络空间安全学院,北京 100049; 2.中国科学院信息工程研究所,北京 100093; 3.信息内容安全技术国家工程实验室,北京 100093
摘要：针对基于确定有限状态自动机的匹配引擎在大规模、复杂规则下会出现状态爆炸的问题,提出正则表达式子串抽取算法。通过将子串抽取算法应用于DFA状态爆炸场景,设计基于子串抽取的正则匹配引擎。实验结果表明,该算法在单个规则上运行时间可达10 ms量级,抽取率高达99%,同时匹配引擎具有较好的稳定性和可拓展性,且匹配速度优于相关开源匹配引擎。
关键词：正则表达式,确定有限自动机,状态爆炸,子串抽取,匹配引擎
基金资助：国家重点研发计划(2016YFB0800303);中国科学院信息工程研究所基础前沿项目(Y7Z0351101)。
