一种正则表达式编译器优化技术

摘要：

正则表达式匹配在网络安全领域具有重要地位。传统的正则表达式匹配引擎通常采用NFA和DFA,由于具有匹配性能高的特点,DFA成为深度报文检测( DPI)的首选。但是DFA的生成首先需要由正则表达式转换成NFA,再由NFA转换成DFA,这个过程称为正则表达式的编译,且是一个计算非常密集的行为。针对构建DFA过程中耗时过多的问题,在Michela Becchi实现的编译过程的基础上,提出了一种基于多核平台的多线程并行化执行的方案,来降低构建DFA消耗的时间。同时针对所使用正则表达式中不能识别尾锚的不足,增加尾锚处理流程,提高正则表达式匹配的准确性。实验结果表明,经并行优化,构建DFA过程的加速比达到2.3及以上,且添加的尾锚处理流程经验证是正确的。

关键词：正则表达式、子集法、确定型有限自动机、并行、优化

分类号：TP393.08(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61379148

在线出版日期：2015-10-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：123-128