用优化的正则表达式引擎进行快速网络流分类

摘要 依赖于正则表达式匹配的深度包检测技术因准确率高成为网络流分类广泛使用的技术.为了能在线性时间内对网络流进行快速分类，需采用时间高效的确定性有限自动机（DFA）匹配引擎，但DFA存在空间爆炸问题，无法满足实际需求.为了解决这个问题，本文从DFA中每个状态在不同的输入字符转换下到达的目的状态特性出发，提出了一种基于默认目的状态和位图技术的DFA压缩算法（对应的自动机模型称为DBDFA），该算法能够将有着相同目的状态的多条转移边压缩为只需一个默认目的状态或只需一个时空高效的位图.实验表明，DBDFA能达到平均99%的压缩效率，优于目前大多数的DFA压缩技术，且压缩后的总体匹配效率是原有DFA的3~5倍，这是目前大部分的压缩技术所不能达到的