一种面向入侵检测的快速多模式匹配算法

随着网络速度和入侵检测规则的持续增长,模式匹配正在成为网络入侵检测系统的性能瓶颈。提出了一种新的Wu-Manber类型的模式匹配算法,通过将模式分组,对不同子模式组采用不同匹配方法,显著提高了模式匹配的效率。对比实验表明,当模式组中含有长度小于3的模式时,新算法性能比原算法平均提高了29%~44%。     

一种改进的Wu-Manber多关键字匹配算法

针对Wu-Manber算法在处理公共子后缀模式情况下的不足,该文提出了一种基于非空公共子后缀模式的处理算法。该算法把有非空公共子后缀的模式汇集在一起,进一步减小了next链表的平均长度。在匹配过程中减少了字符比较的次数,从而提高算法的运行效率。该文对搜狗实验室给出的相关文档进行全文检索实验,并和原Wu-Manber算法、孙晓山等提出的改进算法进行比较。实验结果表明,该文提出的改进算法有效地减少了匹配过程中字符比较的次数,从而提高匹配的速度和效率。     

中西文混合字符串的模式匹配算法

在文献１等有关文章中介绍了模式匹配的Ｂｒｕｔｅ－Ｆｏｒｃｅ算法，这种算法对于西文字符串无疑是正确有效的，但对于中西文混合字符串则将出现异常现象，为此，特提出一种解决这一问题的模式匹配算法。     

基于CUDA 的Wu-Manber 多模式匹配算法

多模式匹配是计算机科学中最基本的问题,其应用在许多领域,在一些情形下也是比较耗时的。GPU拥有比CPU更强的并行计算能力,随着CUDA架构的推出,GPU用于通用计算领域的并行编程工作变得更加轻松。实现了基于CUDA架构的Wu-Manber多模式匹配算法,实验结果表明,相比传统串行算法而言,本文的实现获得了10倍以上的加速。     

一种改进的针对中文编码的Wu-Manber多模式匹配算法

Wu-Manber算法是多模式匹配领域性能优越的算法之一.针对Wu-Manber算法不能很好的用于中文环境,以及滑动距离受限和冗余匹配的问题,提出一种改进的针对中文编码的WM_CH多模式匹配算法.WM_CH针对中文编码修改了哈希函数,优化了建立哈希表的过程;修改并优化了算法匹配过程,在执行精确匹配时消除了冗余匹配,增大了单次精确匹配后的滑动距离.实际测试表明,该算法性能优异,保持与原算法匹配精确度一致,针对中文编码能快速过滤非中文字符.在特征串集规模大于50 000时,匹配速度比原算法提升40%以上,同时滑动窗口的跳转次数显著下降.     

基于BF算法改进的字符串模式匹配算法

基于人在字符串匹配过程中常用的思维,提出一种从模式串中提取特殊字符和具有特殊结构的字符组成字符串,用数组或链表来表示这种字符串的结构,使得提取出来的字符能与目标串中相应位置的字符比较的算法。用以减少比较次数,提高匹配效率。     

入侵检测中一种新的多模式匹配算法

基于模式匹配的检测方法是目前入侵检测系统的一种重要方法,因此作为模式匹配方法核心的字符串匹配算法直接影响入侵检测系统的性能和效率。在AC算法和WuManber算法的研究基础上,提出了一种新的多模式匹配算法——ACWM。该算法能够增加字符跳转距离,比较稳定地减少匹配过程中字符比较的次数,提高匹配的速度和效率。     

基于网络处理器的高效中英文多模式匹配算法

由于中英文字符在编码方面的差异，传统面向英文字符环境的多模式匹配算法无法直接应用于中英文字符混合环境。提出了一种适用于网络处理器和中英文混合环境的高效多模式匹配算法。该算法采用从左向右的正向匹配，以字节为最小匹配单位，以字符为最小移位单位，在Trie树结构基础上，利用块字符匹配降低逐字匹配的概率，结合Quick Search(QS)算法进行跳跃加速。实验表明，算法能够在中英文混合环境下避免字节错位和误匹配，匹配速度优于已有算法，且不存在空间膨胀问题，能够满足高速网络信息审计的要求。     

一种快速的字符串匹配算法

字符串匹配技术在许多领域里广泛应用，本文在分析了BF、BM算法以及一些重要的改进算法的基础上，提出了一种新的改进算法——BMH2C，该算法利用两个字符计算右移量并保存在二维数组里，使右移量增大，比较次数减少，有效地提高了匹配速度．最后本文还给出了几种匹配算法的测试结果。     

入侵检测系统中模式匹配算法的优化研究

模式匹配是入侵检测系统中常用的技术,而字符串匹配算法是其核心内容.本文分析了三个常用的匹配算法,并在此基础上对其中的BM(Boyer-Moore)算法和WM(Wu-Manber)算法进行了改进和优化,从而提高了模式匹配的速度和效益.     

一种面向PDF文本内容审查的高效多模式匹配算法

针对Wu-Manber多模式匹配算法所存在的匹配效率低、跳转距离较小的问题,结合PDF文本内容的编码规则,提出了一种适用于中文PDF文本内容审查的Wu-Manber改进算法。该算法使用布隆过滤器提取模式串关键信息,同时结合双重哈希和PDF文本编码规则,减少了无谓的匹配次数,加大了跳转幅度,从而提升了PDF文本的匹配性能。实验结果表明,这种改进算法在PDF文本审查中的匹配速率有较大提升,尤其当最短模式串较长且模式串规模较大时速度可以提升一倍以上。     

An aggressive algorithm for multiple string matching

A new algorithm based on the Wu-Manber algorithm for multiple string matching is presented in this paper. The algorithm eliminates the functional overlap of the table HASH and SHIFT, and computes the shift distances in an aggressive manner. After each test, the algorithm examines the character next to the scan window to maximize the shift distance. This idea is consistent with that of the quick-search (QS) algorithm. Experimental results on four alphabets show that the new algorithm is more efficient than Wu-Manber and other recent algorithms, particularly on short pattern sets and large alphabet.     

入侵检测中一种节约内存的多模式匹配算法

模式匹配既是网络入侵检测系统（NIDS）的关键,也是NIDS中消耗资源最多的部分。随着网络速度和入侵检测规则的持续增长,模式匹配正在成为NIDS的性能瓶颈。提出了一种基于非确定有限自动机结构的Aho-Corasick算法,通过压缩状态表,把状态和状态变迁存储在一个单一向量中,显著降低了内存需求,获得了良好的cache性能。测试表明,与其他Aho-Corasick 算法相比,MEAC的内存消耗平均减少了92.3%~98.4%,同时保持了Aho-Corasick算法的良好性能。     

一种适用于大规模特征集的快速匹配算法

提出了一种适用于大规模特征集的快速匹配算法——SRS算法,该算法性能优异,在特征集达到100 000条时,匹配速度比经典算法快10倍以上。该算法适用于内容过滤、防病毒、反垃圾邮件、短信过滤、网络入侵检测和防御等众多领域。     

基于Aho-Corasick算法的多模式匹配算法研究*

通过分析模式匹配算法在网络入侵检测中重要作用和所面临的问题,对Aho-Corasick基于自动机的算法和以Aho-Corasick算法为基础的相关算法进行了分析,并通过实验对多种多模式匹配算法进行综合对比,最后对多模式匹配方法的发展趋势进行了展望。     

一种改进的BM字符串匹配算法

经典字符串匹配算法的本质都是从左向右或者从右向左顺序进行字符匹配的,在主串中存在大量子串与模式串前缀或者后缀相同时效率较低,并且模式串最大右移长度为模式串长度。改进算法采用二分匹配字符串的方法,有效地避免了由主串中大量子串与模式串前缀相同或者后缀相同引起的无意义比较次数。模式串的移动距离根据改进的坏字符规则进行计算,增大了模式串的移动距离。实验结果表明,改进的字符串匹配算法可以有效地减少字符串的匹配次数和移动次数,达到了提高算法效率的目的。     

一种BM模式匹配算法的改进

模式匹配算法是入侵检测系统中使用较多的一种重要算法。在分析了BM算法以及相关算法的基础上,提出了一种新的改进算法——BMI算法。该算法借鉴了BM算法的思想,并利用了下一字符和末字符的单一性和组合性,有效地提高了最大位移出现的概率。实验测试结果表明该算法能够有效提高匹配过程的效率。     

一种基于双重状态编码的多模式匹配算法

基于自动机的多模式匹配算法是网络内容过滤与业务监管的核心技术之一,但随着模式集合的扩大,对存储资源消耗过大。为降低当前匹配算法的空间复杂度,同时保持较低的时间复杂度,提出了一种基于关键字预处理和状态编码的优化方法。关键字预处理用于过滤冗杂内容,大大降低了处理复杂度;而采用状态编码消除了NFA中的大量failure转移,可有效降低其开销。理论分析和实验仿真表明,相对于传统的基于TCAM的匹配算法,该算法在大大减少内存需求的情况下,实现了模式的高效匹配。