基于确定有限状态自动机的改进多模式匹配算法研究

针对网络入侵检测系统的一般问题,在详细分析现存单模式与多模式匹配算法的基础上,将AC算法里的DFSA方法与单模式匹配算法BMH的思想相融合,以求取优化检测效率为目标,提出一种基于确定有限状态自动机的改进多模式匹配算法。该算法特别适合在大字符集文本串中查找小字符集模式串。将该改进多模式匹配算法应用到Snort入侵检测过程中,针对处理结果进行科学评价。通过实例的应用,验证了该改进算法的可行性和高效性。     

一种基于反向有限自动机的多模式匹配算法

在基于有限自动机的多模式匹配算法DFSA的基础上,结合改进的BM单模式匹配算法的优点,提出一种快速的多模式字符串匹配算法。在一般情况下,该算法不需要匹配目标文本串的每个字符,能充分利用匹配过程中本次匹配不成功的信息和已成功的信息,跳过尽可能多的字符。实验表明,模式串较短时,该算法需要的时间约为DFSA的1/2,模式串较长时,所需时间约为DFSA算法的1/3。     

改进的多模式匹配算法

在有限自动机的多模式匹配算法（DFSA算法）的基础上，结合Quick Search算法的优点，提出了一个快速的多模式字符串匹配算法，之后在算法中以连续跳跃的思想，给出了另一个更加有效的改进，在一般情况下，这两个算法不需要匹配目标文本串中的每个字符，并充分利用了匹配过程是本次匹配不成功的信息，跳过尽可能多的字符，在模式串较长和较短的情况下，算法都有很好的性能，实验表明，在模式串较短时，所提出的算法需要的匹配时间仅为DFSA算法的1／2到1／5，在模式串较长时，所需时间为DFSA算法的1／3至1／7。     

XML内容筛选中的快速串匹配算法

本文提出了一种对XML 文本进行快速串匹配的算法- XMatch。在对于XML 文本的含路径信息的模式串匹配中,由于XML 文本的结构化特点,使得传统的串匹配算法不能直接有效的使用;而现有的大部分XML 内容筛选方法都是基于SAX 分析的事件驱动过程,效率普遍较低。XMatch 在对XML 文本的结构-schema 进行分析的同时,结合模式串的路径信息,建立一个扫描自动机的有限状态自动机;此外,算法还支持带循环引用路径信息的模式串匹配。XMatch 容易扩展,可以支持普通的结构化文本的串匹配。实验结果显示,本算法的效率比使用SAX事件驱动的方法有明显的提高。     

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

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

网络信息审计系统中的多模式相似匹配算法

针对网络信息审计系统的需要,提出一种新颖的基于Episode距离的快速多模式相似串匹配算法.该算法把模式串集合转换为多个有限自动机,然后利用模式串集合建立一个状态驱动器.依次用待匹配串的字符驱动状态驱动器,由状态驱动器驱动各个有限自动机,实现了中英文混合的允许插入错误的相似多模式匹配.该算法不需要匹配每个字符,能充分利用匹配过程中本次匹配不成功的信息并结合改进的文本窗机制,跳过尽可能多的字符;能够控制每个模式串的允许错误上限;匹配速度与允许插入的错误字符教k无关.该算法在信息审计、数据库、信息检索等领域有     

基于自动机并操作的多目标AC-BM算法

AC-BM算法的优点在于能同时进行多个模式串的匹配搜索,且文本串的移位得到优化,但一次只能在一个文本串中进行搜索.为了实现一次可以同时在多个文本串中进行搜索,设计了多目标AC-BM算法.利用自动机并操作技术构造多目标多模式树自动机,借助BM算法的坏字符跳转技术来计算文本串集移位.在Snort系统中分别实现2-目标AC-BM算法和3-目标AC-BM算法.实验结果表明,新算法如果在多个文本串中找到模式串就停止(表示检测到攻击行为),其在时间性能上就明显优于AC-BM算法.     

基于改进BM算法的确定型有穷自动机的设计

通过对有穷自动机理论与BM算法进行分析,设计了一个基于改进BM算法的确定型有穷自动机的模型,该模型描述了向基于改进BM算法的确定型有穷自动机输入文本字符串,自动机输出TRUE,说明文本串中存在与模式串相匹配的字符;自动机输出FALSE,说明文本串中不存在与模式串相匹配的字符串,并给出了对比实验及分析.     

一种基于有限自动机的快速串匹配算法

串匹配是字符串的基本操作之一,因此为它设计一个高效算法具有一定意义.文中基于有限自动机理论,在对经典的K.M.P.算法进行分析的基础上,提出了一种快速的串匹配算法.该算法利用自动机的状态转换表实现串匹配,避免了扫描字符串时的失败链回溯,从而加快了算法的运行速度.理论分析与实验结果均表明,在正文串比较长,模式串中局部匹配失败时失败链反馈较多的情况下,该算法在速度上明显优于K.M.P.算法.但在空间复杂度上,该算法需要较多的存储空间.     

一种适合于超大规模特征集的匹配方法

串匹配技术是入侵检测系统中的关键技术,随着特征数量的增加,现有的自动机类匹配算法都会面对内存占用过大的问题.当特征超过一定数目后,自动机可能根本无法构造.文中提出了一种针对超大规模特征匹配(SLSPM)环境的匹配算法SLSPM.SLSPM算法借助一个块式匹配自动机和若干个普通自动机完成匹配工作,而且能够支持至少上万规模的特征集.与普通匹配自动机先读入状态再判断读入符号的方式不同,SLSPM首先使用散列函数判断当前文本块是否可以被过滤掉.如果文本块无法被过滤且为合法文本块时,再检查当前状态是否是一个能够识别当前文本块的状态.仅在当前状态吻合的情况下再读入下一个文本块进行后续匹配.理论证明显示SLSPM算法具有近似O(n)的复杂度.由于SLSPM算法未能保存全部的跳转信息,其匹配速度相对于高级AhoCorasick算法未有大幅提升.算法的优势在于,该算法在软件环境下能够维持与AC算法相同的匹配性能,而且能够将特征加载规模至少提升至上万以适应超大规模特征集匹配环境.     

一种基于有序二叉树的多模式匹配算法

传统的多模式匹配算法是用树型结构的有限自动机实现的 ,它具有很多缺点 .本文提出的多模式匹配算法是基于有序二叉树的多模式匹配算法 .实验证明 ,本文算法不但具有和传统算法相当的查找速度 ,而且构造速度快、内存耗费少 .因此 ,本文提出的算法特别适用于要求动态构造自动机的情况     

一种基于二叉树结构的入侵检测研究*

提出以二叉树结构取代原有入侵检测系统采用的链表结构,旨在改进入侵规则的存储和模式匹配,提高检测速度。对Snort规则结构作了简要分析,详细阐述了以规则聚类思想构建二叉树结构的过程;同时,采用C4.5算法为二叉树每个规则集节点动态选择最显著的特征,并进行并行测试,实现性能优化。为了尽可能减少冗余比较和无效匹配,引入数字型的IntMatch串匹配算法,有效地提高了模式匹配速度和规则的访问速度。     

面向中英文混合环境的多模式匹配算法

分析了中英文混合环境下多模式匹配的特点,以及已有多模式匹配算法应用于中英文混合环境时的不足,给出并证明了中英文混合环境下多模式匹配算法的性能定理,提出了一种适合于中英文混合环境的基于线索完全哈希Trie结构的多模式匹配算法.该算法扩展了标准Trie结构,以中英文字符内码为键值构造完全哈希Trie匹配机,并利用模式串之间的关系对Trie匹配机进行线索化.理论分析与实验结果表明,所提出的算法在匹配中无需复杂的哈希运算,不需要回溯匹配指针,在中英文混合环境下能够进行正确、高效的匹配,而且不存在空间膨胀问题,具有较低的空间与时间复杂度,有较大理论与应用价值.     

一种实现网络入侵检测的高效算法及其实现架构

为了实现网络入侵检测系统中的精确字符串匹配,本文提出了一种基于叶子-附加和二叉搜索树的字符串匹配算法及其实现架构;首先采用叶子-追加算法来对给定的模式集进行处理,以消除模式之间的重叠。然后采用二叉搜索树算法提取叶子模式及其匹配向量来构建二叉搜索树,并根据每个节点的比较结果,通过左遍历或右遍历来实现字符串的精确匹配;为了进一步提高字符串匹配算法的内存效率,提出了级联二叉搜索树;最后給出了实现精确字符串匹配的总体架构和各个功能模块的架构;实验结果表明,本文提出的设计不仅在内存效率和吞吐量方面优于目前先进的设计技术,而且具有灵活的可扩展性。     

适应类别增量的决策树训练算法

对于模式经常发生变化的客户资信评估、垃圾邮件检测和网络入侵检测等在线分类系统来说，自动感知客观存在的新类别，并让系统中的分类器对此作出自适应调整是其正确持续运行必须解决的问题。该文提出了一种适应新类别增加的决策树训练算法，该算法在新类别已检出的前提下，在原有决策树基础上利用新类别样本增量训练出新的决策树。实验结果表明：该文提出的算法可以较好地解决该问题，而与重新训练新决策树相比，它在分类器离线调整上较少的时间花费使其适用于在线分类系统。     

基于兴趣度的关联规则挖掘算法

对于模式经常发生变化的客户资信评估、垃圾邮件检测和网络入侵检测等在线分类系统来说，自动感知客观存在的新类别，并让系统中的分类器对此作出自适应凋整是其正确持续运行必须解决的问题。该文提出了一种适应新类别增加的决策树训练算法，该算法在新类别已检出的前提下，在原有决策树基础上利用新类别样本增量训练出新的决策树。实验结果表明：该文提出的算法可以较好地解决该问题，而与重新训练新决策树相比，它在分类器离线调整上较少的时间花费使其适用于在线分类系统。     

面向RFID数据处理的复杂事件模式匹配方法

RFID数据具有不确定性,复杂事件处理技术将RFID数据看作不同类型的事件,从事件流中检测符合特定匹配模式的复杂事件。概率事件流分为多项概率事件流和单项概率事件流;针对多项概率事件流,提出NFA-MMG模式匹配方法,亦即使用多个有向无环图结合自动机实现模式匹配。针对单项概率事件流,提出NFA-Tree模式匹配方法,亦即使用匹配树结合自动机实现模式匹配;并提出改进的NFA-Tree方法,即基于概率阈值进行过滤,提高结果过滤效率。实验结果验证了上述模式匹配方法的性能优势。     

基于AC自动机的多模式匹配算法FACA

Aho-Corasick自动机算法在模式匹配失配时,需要多次回溯才转移到有效的后继状态。为此,提出一种快速多模式匹配算法。该算法为每个状态建立失配时的后继指针,在模式匹配失配时,可以通过失配后继指针快速找到有效后继状态,从而避免Aho-Corasick自动机失配时的过多回溯,提高匹配效率。算法在自动机建立时采用动态规划的方法,为每个状态建立匹配长度和匹配量等信息,在模式匹配过程中,基于这些信息统计模式串在主串中的重复次数、最早出现模式串位置等信息。实验结果表明,该算法匹配精确、效率高,且支持在线操作。     

基于扩展模式树匹配的XConquer算法

针对XQuery全文扩展中合取语义ftcontains表达式的计算问题,提出基于扩展模式树匹配的XConquer算法。树形结构索引DataSkeleton为查询节点静态过滤初始数据节点流,最小最低公共祖先动态阻止无效节点入栈,避免无用栈操作。实验结果表明,XConquer算法的查询性能优于DeweyPathStack算法。     

一种入侵检测系统的模式匹配算法*

提出了一种基于后缀树自动机的模式匹配算法,匹配中应用后缀启发机制进行启发跳跃,忽略不必要的比较。实验表明,该方法与传统模式匹配方法相比能有效地加快模式匹配的速度,提高入侵检测效率。