基于分布式存储的正则表达式匹配算法设计与实现

摘要

Deep packet inspection is an advanced packet filter technology, widely used in the network firewall. Pattern matching algorithm based on regular expression has become one of the important methods in achieving DPL Because the traditional regular expression matching algorithm has higher time complexity, it can not be used in real-time network security protection. In order to improve the real-time of regular expression matching algorithm, this paper proposed the parallel regular expression matches algorithm based on distributed storage. This algorithm counts step data,uses of the distributed storage,and realizes parallel processing. Experimental analysis shows that compared with the traditional serial algorithm, the proposed algorithm increases at least five times in matching speed,and can effectively reduce the time complexity of the algorithm, improve the matching efficiency.%深度包检测(Deep Packet Inspection,DPI)是一种先进的包过滤技术,广泛应用于防火墙中.基于正则表达式的模式匹配算法已成为实现DPI的重要方法之一,传统的正则表达式匹配算法的时间复杂度较高,不能实时进行网络安全的防护.为了提高正则表达式匹配算法的实时性,提出一种基于分布式存储的正则表达式匹配并行算法,该算法通过对数据进行步长计数,采用分布式存储,实现了并行处理.实验分析表明,与传统的串行算法相比,该算法匹配速度至少提高5倍,能够有效降低算法时间复杂度,提高匹配效率.