| 一种针对DFA状态爆炸的正则表达式匹配方法 |
| |
| 引用本文： | 王翔,卢毓海,马伟,刘燕兵. 一种针对DFA状态爆炸的正则表达式匹配方法[J]. 计算机工程, 2019, 45(4): 148-156 |
| |
| 作者姓名： | 王翔 卢毓海 马伟 刘燕兵 |
| |
| 作者单位： | 中国科学院大学网络空间安全学院,北京100049;中国科学院信息工程研究所,北京100093;信息内容安全技术国家工程实验室,北京100093;中国科学院信息工程研究所,北京100093;信息内容安全技术国家工程实验室,北京100093 |
| |
| 基金项目： | 国家重点研发计划;前沿项目 |
| |
| 摘 要： | 针对基于确定有限状态自动机的匹配引擎在大规模、复杂规则下会出现状态爆炸的问题,提出正则表达式子串抽取算法。通过将子串抽取算法应用于DFA状态爆炸场景,设计基于子串抽取的正则匹配引擎。实验结果表明,该算法在单个规则上运行时间可达10 ms量级,抽取率高达99%,同时匹配引擎具有较好的稳定性和可拓展性,且匹配速度优于相关开源匹配引擎。
|
| 关 键 词： | 正则表达式 确定有限自动机 状态爆炸 子串抽取 匹配引擎 |
A Regular Expression Matching Method for DFA State Explosion |
| |
| WANG Xiang,LU Yuhai,MA Wei,LIU Yanbing. A Regular Expression Matching Method for DFA State Explosion[J]. Computer Engineering, 2019, 45(4): 148-156 |
| |
| Authors: | WANG Xiang LU Yuhai MA Wei LIU Yanbing |
| |
| Affiliation: | (School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,China;Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China;National Engineering Laboratory for Information Security Technologies,Beijing 100093,China) |
| |
| Abstract: | WANG Xiang;LU Yuhai;MA Wei;LIU Yanbing(School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,China;Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China;National Engineering Laboratory for Information Security Technologies,Beijing 100093,China) |
| |
| Keywords: | regular expression Deterministic Finite Automaton(DFA) state explosion substring extraction matching engine |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
