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

摘要

正则表达式匹配在网络安全领域具有重要地位。传统的正则表达式匹配引擎通常采用NFA和DFA,由于具有匹配性能高的特点,DFA成为深度报文检测( DPI)的首选。但是DFA的生成首先需要由正则表达式转换成NFA,再由NFA转换成DFA,这个过程称为正则表达式的编译,且是一个计算非常密集的行为。针对构建DFA过程中耗时过多的问题,在Michela Becchi实现的编译过程的基础上,提出了一种基于多核平台的多线程并行化执行的方案,来降低构建DFA消耗的时间。同时针对所使用正则表达式中不能识别尾锚的不足,增加尾锚处理流程,提高正则表达式匹配的准确性。实验结果表明,经并行优化,构建DFA过程的加速比达到2.3及以上,且添加的尾锚处理流程经验证是正确的。%Regular expression matching plays an important role in network security domain. Traditionally,NFA and DFA could be used in regular expression matching. As DFA has the characteristic of high throughput,it becomes the preferred option of Deep Packet Inspection ( DPI) . However,DFA construction needs a compilation,which first converts regular expressions into NFA,and NFA is then used to con-struct DFA. The compilation process is a computation-intensive behavior. In this paper,the most time-consuming process of the construc-tion of DFA is researched. Based on the previous works of Michela Becchi,propose a multi-thread parallel strategy to reduce time-cost in the compilation process on the multi-core platform. In addition,the function of tail anchor is added and the accuracy is proved,so that the regular expression matching engine can deal with tail anchor. The experimental results show that the compiling process can be accelerated by 2. 3 times with parallel optimization.