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

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

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

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

基于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,可实现千兆网络下的入侵检测和垃圾过滤。     

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

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

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

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

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

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

一种针对DFA状态爆炸的正则表达式匹配方法

针对基于确定有限状态自动机的匹配引擎在大规模、复杂规则下会出现状态爆炸的问题,提出正则表达式子串抽取算法。通过将子串抽取算法应用于DFA状态爆炸场景,设计基于子串抽取的正则匹配引擎。实验结果表明,该算法在单个规则上运行时间可达10 ms量级,抽取率高达99%,同时匹配引擎具有较好的稳定性和可拓展性,且匹配速度优于相关开源匹配引擎。     

一种基于Bloom filter的加强队列公平性改进算法*

随着Internet基于非TCP的应用不断涌现,基于异质流网络拥塞控制公平性研究越来越重要。针对流与流之间传输的公平性问题,基于BLUE算法,结合Bloom filter,提出了一种改进的AQM算法EFBLUE。通过仿真实验对新算法从分组丢失率、吞吐量、延时等方面的性能进行了测试并与RED算法进行了性能对比。NS2仿真实验结果表明,该算法只需使用极少量的状态位和很小的缓存空间就能较好地鉴别出非响应流,并限制其速率,保护TCP流免受非响应流影响,实现了流量传输的公平性。最后对EFBLUE的性能优化问题作了进一步的分析。     

基于FPGA改进电路的高性能正则表达式匹配算法

针对正则表达式匹配过程中吞吐率低及逻辑资源占用数多的问题,提出一种完全基于现场可编程门阵列(FPGA)逻辑电路的改进确定有限自动机(DFA)匹配算法。首先,该算法统计了DFA中每个状态的大多数转移边都会集中指向相同状态特征的结果,随后根据正则表达式的转移矩阵为DFA的每个状态设置一条默认的转移边,最后进行逻辑电路简化处理,并采用L7-filter规则集进行实测。实验结果表明,改进后的DFA方案与非确定有限自动机(NFA)方案相比,有10%~60%的规则获得了更高的吞吐率,62%~87%的规则占用了更少的逻辑资源。     

面向网络流的正则表达式匹配改进算法

提出了基于猜测-分组-检验的面向网络流正则表达式匹配算法。首先对出现概率高的部分特征子块进行搜索并把特征子块进行分组后DFA转换,然后对输出进行猜测匹配。若匹配成功,则使用NFA进行完整验证。实验表明,该方法能够在减少内存使用和资源占用率的同时,具有极高的匹配效率。     

Fast and compact regular expression matching

We study 4 problems in string matching, namely, regular expression matching, approximate regular expression matching, string edit distance, and subsequence indexing, on a standard word RAM model of computation that allows logarithmic-sized words to be manipulated in constant time. We show how to improve the space and/or remove a dependency on the alphabet size for each problem using either an improved tabulation technique of an existing algorithm or by combining known algorithms in a new way.     

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

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

Spark环境下基于多维布隆过滤器的星型连接算法

为了适应联机分析处理(OLAP)系统中实时数据高性能分析需求不断提高的需求,提出一种能够适合Spark环境并结合多维Bloom Filter(MDBF)的星型连接算法SMDBFSJ。首先,根据多个维表构建MDBF,利用其占用空间小的特点,广播到所有节点;然后,在本地节点完成事实表过滤操作,事实表不需要在节点间移动数据;最后,过滤后的事实表与维表采用重划分方式进行连接,进而得到最终结果。SMDBFSJ算法避免了事实表数据移动,通过MDBF减小了需要广播的数据量,充分结合了广播连接和重划分连接的优势。实验结果表明了该算法的有效性,在单机和集群环境下,该算法相比重划分连接均获得了3倍左右的性能提升。     

基于 BIoom fiIter 的 RFID 中间件数据过滤算法研究

有效地减少 RFID 系统中冗余阅读器或天线采集到的大量重复数据,可以降低系统能耗和提高处理效率。经研究,提出采用改进的布隆过滤器（Bloom filter）对 RFID 采集数据进行去重过滤,并运用到中间件系统中。改进的 Bloom filter 主要将两个标准的 Bloom filter 组成二维并行 Bloom filter,对 RFID 采集数据所包含的两个属性值 tagID 和 readerID 进行并行过滤。经实验可见,标准 Bloom filter 与哈希过滤（hash filter）相比具有明显的优势,对其改进后,采用二维并行 Bloom filter 在误判率、吞吐率和存储空间上具有更高的系统性能。     

针对动态集的矩阵型Bloom filter表示与查找

提出一种针对动态集合的矩阵型Bloom filter表示与查找法（matrix Bloom filter,MBF）,它使用一个s×m位矩阵对数据集合进行哈希表示与查找,较同类算法SBF和DBF,能继承Bloom filter算法常数查找开销的基本精髓。     

基于正则表达式的深度包检测算法

在深入分析了DFA状态数对算法性能影响的基础上,提出了一种新的基于正则表达式的深度包检测算法,该算法保证在任意有限的系统资源下算法的时间复杂度空间复杂度最小。在Linux下实现了该算法,并对基于L7-filter模式集合的网络数据包进行了大量检测实验。结果表明,与已有的正则表达式算法比较,该算法的时间复杂度和空降复杂度最小。