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

来源：计算机技术与发展杂志2015年第09期北京时间：

作者：李朋飞;陈曙晖;徐成成

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

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