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

Design and Implement of Regular Expression Pattern Matching Algorithm Based on Distributed Storage

作　　者：李璋[1] 杜慧敏[1] 张丽果[1,2] 

机构地区：[1]西安邮电大学电子工程学院微电子学系,西安710061 [2]西安电子科技大学微电子学院,西安710071

出　　处：《计算机科学》2013年第3期74-76,99,共4页Computer Science

基　　金：国家自然科学基金项目(60976020);陕西省教育厅科研计划项目(11JK1063;2010JK833)资助

摘　　要：深度包检测(Deep Packet Inspection,DPI)是一种先进的包过滤技术,广泛应用于防火墙中。基于正则表达式的模式匹配算法已成为实现DPI的重要方法之一,传统的正则表达式匹配算法的时间复杂度较高,不能实时进行网络安全的防护。为了提高正则表达式匹配算法的实时性,提出一种基于分布式存储的正则表达式匹配并行算法,该算法通过对数据进行步长计数,采用分布式存储,实现了并行处理。实验分析表明,与传统的串行算法相比,该算法匹配速度至少提高5倍,能够有效降低算法时间复杂度,提高匹配效率。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 DPI. Because the traditional regular expression matching algorithm has higher time complexity, it can not be used in real-time network se- curity 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 se- rial 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.

关 键 词：正则表达式 模式匹配算法 确定型有限状态机 深度包检测 分布式存储 

分 类 号：TP338.6[自动化与计算机技术—计算机系统结构]