高性能正则表达式匹配算法评估

为对现有的高性能正则表达式匹配算法进行综合比较与分析,实现诸如DFA、D2FA、CD2FA、mDFA及XFA等最新算法,采用Snort规则集综合评估这些算法的存储空间和匹配时间。实验结果表明,在存储空间方面,与mDFA相比,XFA的存储空间减少84.9%~89.9%;在匹配效率方面,与mDFA相比,XFA的匹配时间增加了38.9%~174.6%;XFA在存储空间和匹配效率上具有良好的可伸缩性,即当规则数增加到8倍时,mDFA的存储空间增长了64倍,而XFA的存储空间仅增加了16倍,匹配时间仅增加了61.3%。     

面向高效深度包检测的启发式正则表达式分组算法*

经过对正则表达式合并DFA状态爆炸问题的分析,采用正则表达式两两合并DFA的状态增加数之和衡量多个正则表达式合并后真实的状态增加情况,将正则表达式最优分组问题归约为带权无向图的k-最大割问题。在此基础上,提出一种面向高效深度包检测的启发式正则表达式分组算法REG-EDPI。采用贪婪策略构造初始解,引入移除参数进行迭代优化。实验表明相比于其他算法,REG-EDPI算法能够在合理的运行时间内,获得更优的分组策略,具有更强的实际应用价值。     

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

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

面向存储的正则表达式匹配算法综述

正则表达式匹配是当前深度包检测领域中的关键性技术.介绍了面向存储的正则表达式匹配算法的基本思想和设计方法,给出了算法分类并比较了典型压缩算法间的差异,分析了正则表达式语法对算法设计的影响,最后论述了目前研究中面临的技术难点并对今后算法设计的发展趋势作了展望.     

基于DoLFA的高效正则表达式匹配算法

随着规则数量的急剧增长,表示正则表达式的DFA(Deterministic Finite Automata,确定型有限自动机)容易引起状态空间爆炸,难以满足高速网络的实时处理需求。提出一种高效的正则表达式匹配算法,该算法通过将正则表达式分割为精确串、字符集合以及重复字符3个子集,分别对其进行分区优化及检测,然后再利用结点信息对匹配信号进行连接,即构建一种特殊的状态机DoLFA(Divide-optimize-Link Finite Automata)。理论分析和仿真结果表明,该算法可以大大节省存储空间,并获得较高的吞吐量,且具有较强的扩展性。     

基于预定义类的紧凑型正则表达式匹配算法

针对目前硬件正则表达式匹配算法在存储空间以及吞吐量等方面面临的挑战,结合扩展有限自动机（XFA）正则表达式匹配算法,提出了一种预定义类的压缩自动机匹配算法（Pre-Class CFA）。通过预定义类,算法既可以实现正则表达式中类字符匹配,又能够通过优先级的设定匹配特殊字符集,并在XFA消除确定性有限状态机（DFA）状态爆炸问题的基础上进一步压缩了迁移边数目;同时算法根据现场可编程门阵列（FPGA）和迁移边的特征,设计了一种基于并联只读存储器（ROM）结构的迁移边存取方法,可以实现同一状态多条迁移边的并行读取和匹配。在中低性能FPGA平台ALTERA DE2-70上对算法进行测试,实验中系统吞吐量为1.3 Gb/s,可实现千兆网络下的入侵检测和垃圾过滤。     

基于Bloom filter的高效正则表达式匹配算法*

针对确定有限自动机(DFA)的正则表达式匹配技术存在状态膨胀和一次状态转移只能处理单个字符的问题,提出了一种基于布鲁姆过滤器的正则表达式匹配算法。该算法将正则表达式中的每个确定字符串组成DFA的一个状态,添加比特向量完成匹配过程,并且在一次状态转移中根据确定字符串的匹配结果达到处理多个字符的目的。实验分析表明该算法有效降低了DFA状态的膨胀,提高了匹配速率。     

基于DFA结构的高速并行正则表达式匹配算法

针对正则表达式匹配速度低的问题,提出一种基于DFA结构的并行匹配算法.正则表达式匹配过程中,DFA的一部分状态访问次数多而另一部分状态访问次数少.因此,建立数学模型,应用马尔科夫链求解各个状态的访问概率,从而将DFA的状态分成前端和后端两个部分.通过多个前端部分共用一个后端部分的方法实现多个数据流的并行处理,达到了提高匹配速度的目的.算法分析与实验表明在多消耗60％-80％的存储空间时,能够提高4.2-4.6倍的匹配速度.     

高性能正则表达式匹配算法综述

深度检测在维护网络安全、保证服务质量等方面扮演着重要的角色。正则表达式匹配算法作为高性能深度检测的核心技术,具有重要的研究价值和实践意义。随着网络流量不断增长、规则数目持续增多以及网络结构日趋灵活和动态,现有的正则表达式匹配算法面临着匹配速度、内存占用和更新能力等多方面的挑战。介绍了正则表达式匹配算法的研究背景,从空间压缩、匹配加速、新型自动机设计以及规则拆分和分组四个角度入手,分类总结了学术界具有影响力的研究成果。通过基于真实网络流量的评测,比较了几种经典匹配算法在不同规则集上的匹配速度、内存占用和预处理时间等性能指标,并给出了不同需求场景下高效正则表达式匹配算法的选择建议,归纳了高性能正则表达式匹配算法的下一步发展方向。     

有限自动机代数及其算法

本文提出有限自动机代数及其算法,它对于用有限自动机识别句子是有意义的。     

面向网络安全的正则表达式匹配技术

分析了基于有穷状态自动机的正则表达式匹配方法的时间复杂度、空间复杂度以及二者之间的制约关系,深入讨论了在网络安全应用中遇到的特有问题与挑战.围绕这两个问题,对当前出现的多种优化技术和策略进行了全面的综述和评价,最后对未来的研究方向进行了总结和展望.     

基于膨胀系数的正则表达式分组算法

确定性有限自动机(Det­erministic Finite Automata, DFA)匹配速度远快于非确定性有限状态自动机(Non-deterministic Finite state Autom­ata, NFA),但大量正则表达式转换为DFA时会引起状态爆炸而占用巨大的存储空间。首先定义膨胀系数(Expansion Coefficient, EC)来描述正则表达式的膨胀特性,然后在膨胀系数这一概念基础上,提出一种高效的分组算法--IGA(Improved Grouping Algorithm)算法对正则表达式进行有效分组,将容易引起状态爆炸的正则表达式相互隔离,从而节省存储空间。实验结果表明,与原有算法相比,在相同分组数目时IGA算法平均能够减少25%的状态数。     

面向深度包检测的DFA细粒度并行匹配方法

确定性有限自动机(DFA)是实现正则表达式匹配的一种有效手段,但DFA的状态跳转是串行的,导致匹配速度慢、难以满足高速骨干网环境深度包检测(DPI)的性能需求.提出了一种称为LBDFA(Loopback DFA)的细粒度并行化状态跳转方法,通过将在Loopback状态上的连续跳转并行化,提高了匹配速度.此外,利用Bloom filter消除该并行跳转中的临时偏离现象,进一步提高了并行潜力.在L7-filter以及Snort规则集上的测试结果表明,LBDFA能够满足10 Gbps以上的正则表达式匹配需求.     

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

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

基于正则表达式的DFA拆分算法研究

深度包检测采用简单的字符串匹配技术将报文内容与一组固定字符串进行匹配,基于正则表达式匹配算法能提供更强的表达能力和灵活性,而复杂的正则表达式结构可能引起DFA的状态数膨胀,导致存储代价巨大;DFA拆分算法将DFA转换表拆分为三个表：间接索引表,转换输出表,直接转换表,实验结果表明DFA所占空间大大减小,实现了DFA的压缩存储。     

Representations of Regular Ideals in Finite Automata

Regular ideals of a free monoid are shown to be characterized by weak (noninitial) representations in finite automata. The class of kernel ideals is also shown to be invariant under the action of several automata functors and to be equal to the class of zero ideals.     

基于有限自动机的多层次构件行为匹配模型

针对目前基于行为规约匹配的构件获取方面的不足,提出了一种基于有限自动机的多层次的构件行为匹配模型.该模型采用有限自动机对构件的行为进行建模,借鉴图论中图匹配的思想,提出了6种行为匹配关系:等价行为匹配、扩展行为匹配、相容行为匹配、包含行为匹配、弱包含行为匹配和弱相容行为匹配.分析了这些行为匹配关系之间的蕴涵关系,并给出...     

基于食肉植物算法的状态序列搜索

从有限自动机中生成简短、可读性强的正则表达式是计算机理论研究中的一个重大课题.在经典的正则表达式生成算法中,状态序列是影响正则表达式质量的关键因素.为了能够快速高效地找到较优的状态序列,本文以食肉植物算法的理论为核心,并结合其他启发式算法的思想进行设计与优化,提出了一种基于食肉植物算法的状态序列搜索方法.通过实验将此方法与已有的一些使用启发式规则的搜索算法进行了对比,实验结果表明,基于食肉植物算法的状态序列搜索方法优于其他启发式算法,生成的正则表达式长度比起其他启发式算法明显缩短,如跟DM算法相比,长度的缩短幅度可以随着自动机阶数的增加达到20%以上,跟随机序列算法相比,可以把长度缩短多个数量级.