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

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

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

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

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

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

存储有效的多模式匹配算法和体系结构

多模式匹配是基于内容检测的网络安全系统的重要功能,同时,它在很多领域具有广泛的应用.实际应用中,高速且性能稳定的大规模模式匹配方法需求迫切,尤其是能够在线实时处理网络包的匹配体系结构.介绍了一种存储有效的高速大规模模式匹配算法及相关体系结构.研究从算法所基于的理论入手,提出了缓存状态机模型,并结合状态机中转换规则分类,提出了交叉转换规则动态生成的匹配算法ACC(Aho-Corasick-CDFA).该算法通过动态生成转换规则降低了生成状态机的规模,适用于大规模模式集.进一步提出了基于该算法的体系结构设计.采用网络安全系统中真实模式集进行的实验结果表明,该算法相比其他状态机类模式匹配算法,可以进一步减少80%~95%的状态机规模,存储空间降低40.7%,存储效率提高近2 倍,算法单硬件结构实现可以达到11Gbps 的匹配速度.     

基于Sunday算法的改良单模式匹配算法

Unicode编码的中文环境下应用Sunday算法时,如直接使用中文字符生成失效跳转表,将造成空间膨胀,而将中文字符拆分为两个字节进行处理,虽可以降低空间消耗,但匹配的执行速度又会受影响。针对Sunday算法应用于Unicode编码的字符拆分环境时所产生的时间性能降低问题,结合Unicode中文单元的内部关联性,优化了原Sunday算法的辅助跳转表与匹配规则,从而在解决Unicode下算法空间膨胀问题的同时,提升了Sunday算法在此环境下的时间性能,并利用模拟实验对改良算法的时间与空间性能进行了实验证明。     

基于Sunday算法的改良单模式匹配算法

Unicode编码的中文环境下应用Sunday算法时,如直接使用中文字符生成失效跳转表,将造成空间膨胀,而将中文字符拆分为两个字节进行处理,虽可以降低空间消耗,但匹配的执行速度又会受影响。针对Sunday算法应用于Unicode编码的字符拆分环境时所产生的时间性能降低问题,结合Unicode中文单元的内部关联性,优化了原Sunday算法的辅助跳转表与匹配规则,从而在解决Unicode下算法空间膨胀问题的同时,提升了Sunday算法在此环境下的时间性能,并利用模拟实验对改良算法的时间与空间性能进行了实验证明。     

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

模式匹配在计算机应用中扮演着很重要的角色。通过分析BM,BMH和BMHS算法及相关改进算法,提出BMHS算法的改进算法(DBMHS)。该算法(DBMHS)充分利用模式串两端字符,通过比较模式串两端字符的跳转距离来实现更大距离的跳转。实验证明,改进后的算法显著增加了匹配窗口的跳转距离,有效地提高了匹配效率。     

一种基于子串识别的多模式串匹配算法

多模式串匹配算法是网络内容过滤系统的核心技术。巨大的存储空间开销是制约多模式匹配串算法应用的瓶颈之一。提出一种基于子串识别的多模式匹配算法—HashBOM,该算法利用位哈希表存储模式串的子串信息以大幅度减少存储空间,利用递归哈希函数计算字符串的哈希值以实现快速匹配。理论分析表明,该算法的空间复杂度为O(rm~2),优于基于子串识别的匹配算法BOM的空间复杂度O(mr|∑|log_2mr);该算法搜索匹配过程的平均时间复杂度为O(nlog|∑|)mr/m,与BOM算法相同(其中m为最短模式串的长度,r为模式串的个数,n为待匹配文本的长度,|∑|为字母表的大小)。在随机数据集和真实数据集上的实验表明,该算法的存储空间远远低于BOM算法,而匹配速度与BOM算法相当,非常适合在线实时匹配的应用环境。     

中文多模式匹配算法性能的分析与研究

模式匹配算法一般不具有所有环境下的通用性,不同的算法在不同语义环境下的表现,往往差异较大。为实现中文环境下对模式串的快速多模式匹配,选择出在中文环境下的最优匹配算法,分析了几种经典的多模式匹配算法。通过对各个算法设计思路、时间性能与空间性能的研究,推导出基于“坏字符”的算法设计思路最适用于中文环境下大字符集、短字符串的特点,并通过实验对理论推测的中文环境最优算法-Wang算法的性能与其他几种经典算法的性能进行了比较,验证了理论推导的正确性。     

采用集合切分编码的大容量模式匹配算法*

针对现有模式匹配算法无法实现大容量模式集快速搜索的不足,提出了一种基于TCAM多字节状态机的模式匹配算法。利用TCAM的掩码特性,切分具有相同匹配字符串的状态集,提出了一种编号编码压缩机制。通过理论证明,集合切分编码利用状态机的已匹配信息,将编号存储改变为编号段存储,大幅压缩了具有相同转移字符串和目的状态的交叉转移路径,减少TCAM表项数目。经理论分析和实验仿真,该算法不仅具有高搜索速率,而且可以减少大量相似表项,降低TCAM存储资源消耗,从而支持大容量的模式集。     

一种节约内存的中文多模式匹配算法

AC及其改进算法基于有限状态自动机,随着中文模式串数目增加,完全Hash表和状态表矩阵存储方式会导致存储空间快速膨胀,状态转移函数计算量大,Cache命中率下降,算法的时空性能急剧下降。提出以邻接链表方式存储有限状态自动机,并将状态"0"的链表转化为线性表,以提高算法的时空效率。在此基础上,设计了一种适合中文的多模式匹配算法,该算法所需存储空间仅为完全Hash表方式的10%,约为状态表矩阵方式的20%。     

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

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

自动机算法在文本不精确匹配中的应用

论文从实用的角度,着重研究了有限自动机算法在文本的不精确匹配中的应用,提出了一种用于中文精确匹配的自动机的构建思想,两种用于中文同音字匹配的自动机的构建思想,以及利用自动机的原理去除无用字符对文本匹配的干扰的方法。编程实现了上述三种自动机算法并对其作了测试,给出了三种算法各自的性能测试数据。     

双向AC算法及其在入侵检测系统中应用

在经典的多模式字符串匹配算法-AC算法的基础上,提出了双向AC算法.该算法在预处理阶段构造正向和反向两个有限状态自动机,匹配时使用正向有限自动机从文本串中间位置向右扫描,同时依据反向有限状态自动机从中间位置向左扫描.将该算法应用于开放源码的入侵检测系统Snort中,实验结果表明较BM算法、WM算法和AC算法本算法有更好...     

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

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

面向实时事件流的复杂事件处理方法

复杂事件处理是一种动态环境下对事件流进行分析的技术。复杂事件处理技术通常基于有限状态自动机实现,匹配过程中会在事件流上产生大量且重叠的部分匹配,有限状态自动机需维护大量的重复匹配状态,导致基于该技术的方法都会出现冗余计算的问题。为了提高复杂事件处理的匹配效率,提出了使用复杂事件实例覆盖技术来实现复杂事件处理的方法。通过设计临时匹配链式分区存储结构以及基于此结构的匹配算法,来利用复杂事件实例覆盖减少冗余计算,从而实现匹配效率的提升。在模拟数据集和真实数据集上进行了实验测试与分析,与两种常用的复杂事件处理技术进行比较。实验表明,提出方法能够在保证匹配正确性的同时有效地减少匹配过程中的冗余计算,提高整体匹配效率。     

基于模板有限自动机的正则表达式匹配算法

采用规则分组的办法解决DFA状态爆炸问题,随着规则数目的增加,空间压缩效率大大降低。针对此问题,提出了模板有限自动机分组算法,基于规则模板对规则集进行分组,各分组分别构建匹配引擎。同时,根据实际规则数目和系统结构对规则子集的数目改变,达到更好的匹配效率。理论分析和实验表明,与传统分组算法相比,在存储空间压缩相当情况下,分组数目大大减少;与其他典型的DFA改进算法相比,预处理时间和存储空间有数量级别的缩减,且匹配速率没有明显降低。     

基于改进遗传算法的分形图像编码

为解决传统分形图像编码方案中块匹配时间过长的问题,提出一种结合图像块平均偏差的改进遗传算法,利用改进遗传算法的最优解搜索能力替代分形图像编码中复杂的块匹配过程,结合对比度因子的约束,限定遗传算法的搜索空间,缩短编码时间。实验结果表明,该方法与结合遗传算法的同类改进算法相比,能在缩短编码时间的同时,有效提高解压图像质量。