快速高效的模式匹配算法的剖析与改进  

Anatomy and improvement of fast and memory-efficient pattern matching algorithm

作　　者：王杰[1] 刘亚宾[1] 石成辉[1] 

机构地区：[1]郑州大学电气工程学院,河南郑州450001

出　　处：《计算机工程与设计》2009年第11期2649-2651,2655,共4页Computer Engineering and Design

基　　金：河南省杰出人才创新基金项目(074200510013);河南省教育厅自然科学基金项目(2007520048)

摘　　要：考虑到处理性能和内存开销两大因素，模式匹配成为网络入侵检测系统（NIDS）中最为关键的一环，而现有内存消耗较少的算法性能一般较差。因此，提出一种专为入侵检测领域设计的Modified-Piranha（MP）算法，它基于排斥思想，并采用位图法、优化高速缓存和状态重排思想对Pranha算法中的哈希表进行了改进，进一步减少了匹配步骤和内存访问次数，极大地提升了模式匹配的效率。实验结果表明，相对目前先进的模式匹配算法，MP算法能显著提升Snort的性能，能减少10.8%-36.7%的处理时间，节省5.6%-38.9%的内存使用。Taking Processing and memory resources into account, pattern matching has become the most critical part of signature-based NIDSes, but the existed pattern-matching algorithms which consumed less memory gives poor performance generally. Modified-Piranha （MP）, an improved algorithm for pattern matching tailored for intrusion detection, is developed. It is based on the observation that if the rarest substring of a pattern does not appear, then the whole pattern will definitely not match. To better the hash table ofpranha algorithm, the method ofbitmaps and the thought of optimized cache and rearranging states is used. By using the proposed method, the matching step and the memory access are evidently reduced, and the pattern matching efficiency is promoted enormously. The experimental results indicate that MP algorithm can enhance the performance of Snort by 10.8% to 36.7% in terms of processing time and by 5.6% to 38.9% in terms of memory usage compared to existing state-of-the-art algorithms.

关 键 词：MP算法 网络入侵检测系统 模式匹配 特征检测 位图 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]