深度包检测中一种高效的正则表达式压缩算法

提出一种基于确定的有穷状态自动机(deterministic finite automaton,简称DFA)的正则表达式压缩算法.首先,定义了膨胀率DR(distending rate)来描述正则表达式的膨胀特性.然后基于DR提出一种分片的算法RECCADR(regular expressions cut and combine algorithm based on DR),有效地选择出导致DFA状态膨胀的片段并隔离,降低了单个正则表达式存储需求.同时,基于正则表达式的组合关系提出一种选择性分群算法REGADR(regular expressions group algorithm based on DR),在可以接受的存储需求总量下,通过选择性分群大幅度减少了状态机的个数,有效地降低了匹配算法的复杂性.

基于AC自动机匹配算法的入侵检测系统研究

基于特征的网络入侵检测系统性能与其所采用的匹配算法息息相关。本文对当前入侵检测系统中几种典型的匹配算法进行了分析,并指出了这些算法在入侵检测系统应用中存在的不足,同时,给出了完整的基于AC自动机匹配算法的入侵检测系统方案,理论分析和实验结果表明该系统能够实施快速高效的入侵检测。

快速的多模式匹配算法

在基于有限状态自动机的多模式匹配算法(DFSA算法)基础上,结合Tuned BM算法的优点,提出一个快速的多模式字符串匹配算法,实现了多模式匹配过程中不匹配字符的连续跳跃.在此基础上进一步改进,得到一个最差时间复杂度为线性的匹配算法.分析指出算法实际比较的字符数随着模式串长度的增加而下降,并随模式集的增大有所增多.实验表明,在模式串较短时,算法需要的匹配时间仅为AC算法的1/2到1/3,AQR算法的9/10左右;在模式串较长时,所需时间为AC算法的1/4至1/8,AQR算法的3/4左右.

基于混合策略的单模式匹配算法

结合后缀有限自动机和正向有限自动机的优点,提出了两个单模式匹配算法.算法中,无论是后缀自动机还是正向有限自动机,只要扫描到的模式前缀长度R>0或者超过模式长度的1/2时,使用正向有限自动机继续向右进行扫描;否则都滑动m-R个字符,使用后缀自动机反向扫描模式串的前缀.两个算法的最差、最好时间复杂度分别为O(n)和O(n/m).结果表明,在短模式的情况下,两个算法的平均时间复杂度均好于RF和LDM,在小字符集长模式或大字符集短模式的情况下它们的平均性能好于BM.

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

在基于有限状态自动机的多模式匹配算法(DFSA算法)基础上,结合Tuned BM算法的优点,提出一种快速的多模式字符串匹配算法,实现了多模式匹配过程中不匹配字符的连续跳跃.在一般情况下,算法不需要匹配目标串中的每个字符,而是在实际比较之前跳过尽可能多的字符,以减少字符比较的操作,实现快速匹配.在模式串较长和较短的情况下,算法都有很好的性能.分析指出算法实际比较的字符数随着模式串长度的增加而下降,并随模式集的增大有所增多.实验表明,在模式串较短时,算法需要的匹配时间仅为AC算法的50%到33.3%,AQR算法的90%左右;在模式串较长时,所需时间为AC算法的25%至12.5%,AQR算法的75%左右.

基于组合策略的单模式串精确匹配算法

以仅使用后缀有限自动机的RF算法作为参照对象,对采用组合策略的LDM、ILDM1、ILDM2等算法时间复杂度进行了比较研究。实验表明,LDM和ILDM1算法的时间复杂度要差于RF算法,即组合策略是失效的。实验还发现,ILDM2算法中把模式前缀长度R是否超过模式长度m的1/2作为正向有限自动机暂停匹配的条件,对于中小字母表的模式串的匹配也不是最佳策略。

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

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

一种应用于现代网络搜索引擎的快速串匹配算法

提出了一种基于确定有穷自动机的快速多模式串匹配算法,在匹配过程中能尽可能多地跳过待查文本串字符。算法的特性为现代网络搜索引擎的复合条件查询提供了有力的软件支撑。实验表明可有效地改善网络搜索引擎的性能。

一种带稀疏间隙约束的并行模式匹配算法

带通配符的模式匹配是一个经典的研究问题,带有可变间隙约束的模式匹配是近年来比较热门的研究方向.为适应某些查询精度要求较高的应用领域,提出一种在稀疏间隙约束条件下求解模式匹配完备解的算法SGPM-SAI(pattern matching with sparse gaps constraint based on suffix automaton index).SGPM-SAI通过对文本串预处理,建立一种称为W-SAM的图索引结构,然后对模式串分段查找End Pos集合,最后以集合归并求交的方法得到模式匹配的完备解.实验结果表明:在不考虑预处理时间的情况下,相比几种最典型的模式匹配算法(KMP,BM,AC,suffixarray),SGPM-SAI算法性能优势显著,至少高出3～5倍.通过与SAIL算法的最新优化版本(SAIL-Gen)进行比较,在稀疏间隙约束条件下,SGPM-SAI的性能要显著优于SAIL-Gen算法.此外,为有效利用现代处理器的大规模并行处理单元,提出了并行优化后的算法Parallel SGPM-SAI.实验结果表明:Parallel SGPM-SAI算法的加速效果显著,且具有良好的并行可扩展性,能够充分利用现代众核处理器的高并行计算优势.

入侵检测系统中一种模式匹配算法的研究与改进

对基于入侵检测系统来说．模式匹配算法是基于特征匹配的入侵检测系统中的核心算法，也是当前入侵检测设备中普遍应用的算法。它的效率直接影响到入侵检测系统的准确性和实时性，文章通过对模式匹配算法的改进，提出了一种改进的算法，在匹配文本中重复字符串较多时，该算法可以加快入侵检测系统的检测速度，提高现有入侵检测系统的检测能力。

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

深度包检测(Deep Packet Inspection,DPI)是一种先进的包过滤技术,广泛应用于防火墙中。基于正则表达式的模式匹配算法已成为实现DPI的重要方法之一,传统的正则表达式匹配算法的时间复杂度较高,不能实时进行网络安全的防护。为了提高正则表达式匹配算法的实时性,提出一种基于分布式存储的正则表达式匹配并行算法,该算法通过对数据进行步长计数,采用分布式存储,实现了并行处理。实验分析表明,与传统的串行算法相比,该算法匹配速度至少提高5倍,能够有效降低算法时间复杂度,提高匹配效率。

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

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

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

网络的发展和数据流量增长对入侵检测系统(IDS)提出了更高的要求:必须能够实时快速地从这些数据流中发现并阻止威胁。已知的一些著名算法,如Knuth-Morris-Pratt(KMP)算法和Boyer-Moore(BM)算法,在单模式的情况下,匹配效率很高,但是在多模式和长模式的情况下,并不能显著地提高匹配效率。一些改进算法也有同样的问题。针对IDS应用环境,提出一种新的模式匹配(NPM)算法,并给出了该算法的框架以及基于哈希表和红黑树(RB-Tree)的两种不同实现。NPM算法基于异或操作和哈希函数。实验表明,该算法能有效地提高扫描速度,特别是对于大模式库和长模式两种场合。在这样的场合下,BM算法的效率是比较低效的。

基于图划分的正则表达式分组算法

针对多条正则表达式转换为确定型有限自动机带来的状态空间膨胀问题,借鉴图划分的思想,提出一种改进的分组算法。与原分组算法相比,该算法在分组数相同时状态数平均减少30%,在某些情况下能获得更少的分组数。实验结果证明,该算法能有效降低匹配算法的复杂度。

IDS检测效率的研究

随着网络安全问题的日益严重,入侵检测系统IDS(Intrusion Detection System)在网络安全方面的重要性越来越明显.但是随着网络速度的不断加快,网络数据量的不断增多,对IDS的检测速度提出了挑战.本文在IDS使用的模式匹配算法MWM算法的基础上提出了一种改进技术,明显提高了IDS的检测数据包速度.

一种面向入侵检测系统的模式匹配算法的改进

分析引擎是入侵检测系统的核心部分,一个好的模式匹配算法直接决定了入侵检测系统分析引擎的效率。本文对几种经典的模式匹配算法如:BM算法,BMH算法以及BMHS算法等经典算法进行了研究和分析,比较了几种算法的优劣。最后在BMHS算法的基础上提出一种改进的算法,该算法可以有效提高入侵检测系统的检测速度。

网络数据检测模块设计

本文对入侵检测系统(IDS)中最重要的数据采集,数据分析功能进行研究。提出基于零拷贝的利用网络协议分析和模式匹配相结合的检测方法,其中的模式匹配模块改进了传统的 BM 匹配算法采用新的 AC_BM 的多模快速匹配算法,并将它们作为一个检测分析模块。