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

提出一种基于确定的有穷状态自动机(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),在可以接受的存储需求总量下,通过选择性分群大幅度减少了状态机的个数,有效地降低了匹配算法的复杂性.     

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

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

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

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

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

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

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

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

一组提高存储效率的深度包检测算法

随着深度包检测规则数目的剧烈增长,为了适应网络处理的需求,必须对表示正则表达式的DFA(deterministic finite automata,确定的有限自动机)进行高效的存储.一方面,对DFA的状态点数目进行压缩,提出了一种复合的FSM(有限自动机)的构造方法,通过对正则表达转化成DFA的状态点数目复杂度的分析,将不同复杂度的正则表达式采用不同的方式构建DFA,使得所有平方级和指数级复杂度的状态点数目降低到了线性级.另一方面,对DFA的状态转移数目进行压缩,给出了一种高效的压缩算法,即WD2FA(weighted delayed input DFA,带权延迟DFA)算法,对于任意复杂度的正则表达式都可以将状态转移数目压缩为原来的5%左右,相对于D2FA(delayed input DFA,延迟的DFA)有更好的压缩能力,并且使得D2FA是WD2FA在权值为0情况下的特例.实验结果表明,有限自动机的状态点数目能够控制在线性级,并且在状态点压缩的基础上将状态转移数目压缩为原来的7%.     

一种正则表达式的高效分组算法

正则表达式（Regular Expression,RE）因其强大的表达能力和简单性正取代精确字符串（explicitstring）成为描述模式（pattern）的首选。在网络应用中,基于DFA（确定有限自动机）的正则表达式匹配技术通常用于网络流量实时处理、病毒检测等系统中。随着正则表达式的数量不断增加,DFA的存储空间急剧膨胀导致Cache的命中率大大降低,最终影响匹配的性能。提出了一种高效的正则表达式分组算法,通过合理地将正则表达式分组来大大降低DFA所需的存储空间。还尝试提出了评价正则表达式分组算法的一些指标。     

正则表达式在Web数据验证中的优化机制研究

正则表达式是数据验证技术中功能最为强大的输入控制技术。传统的基于NFA的正则表达式引擎的匹配速度低。通过正则表达式与自动机等价的原理,研究了通过最小化的确定的有限自动机（DFA）来等价实现.NET中正则表达式的数据验证的机制,以期提高正则表达式的匹配速度。     

基于并行字符索引的多步长正则表达式匹配算法

深度包检测（deep packet inspection ,DPI）是网络入侵检测与防御系统（network intrusion dete‐ction and prevention system ,NIDPS）的核心．基于三态内容可寻址存储器（ternary content addressable memory ,TCAM ）的正则表达式匹配算法提高了数据包的处理速度,成为DPI技术的一个重要研究方向．TCAM 具有查找速度快、存储空间小等特性,且能耗与存储空间成正比．由于DFA的存储空间开销比较大,且存储空间大小随着DFA步长数的增加而指数倍增,基于TCAM的DFA面临高能耗的问题,特别是多步长DFA ．提出一种基于并行字符索引的多步长正则表达式匹配算法（multi‐stride parallel character‐indexed DFA ,PCIDFA ）,对确定型有限自动机（deterministic finite automaton ,DFA ）构造并行字符索引,通过比特位图取交集,减少匹配时激活的TCAM 块数,显著降低TCAM 能耗．实验结果表明：与多步长DFA相比,多步长PCIDFA在TCAM 能耗上减少了99．8％以上,在 TCAM 存储空间开销上减少了48．5％～65．3％,在吞吐量上提高了1．9～2．6倍．     

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

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