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

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

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

随着深度包检测规则数目的剧烈增长,为了适应网络处理的需求,必须对表示正则表达式的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%.     

一种基于深度报文检测的FSM状态表压缩技术

针对深度报文检测中正则表达式模式匹配的状态表爆炸问题,提出并实现了一种集合交割的预编码方法(SI-precode),在正则表达式转换成DFA前对所有输入符号进行预编码,通过压缩输入,减少FSM中输入符号的种类,从而压缩状态转移表的空间.证明了预编码生成的状态机的正确性及其与原状态机的同态性.采用L7-filter模式进行实验表明SI-precode不仅提高了正则表达式的编译速度,针对单模式状态机,其状态转移表空间比不进行预编码压缩了87%～97%,50个模式的多模式状态机可压缩59%.预编码在软硬件结合体系结构下进行协议识别时不会对性能造成影响;对纯软件结构性能降低2%～4%.     

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

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

一种面向网络安全检测的高性能正则表达式匹配算法

目前进行正则表达式匹配的典型工具DFA和NFA都存在匹配效率和内存需求之间不可调和的矛盾,无法胜任网络安全检测中大规模正则表达式的匹配.为了解决这个问题,文中从网络安全检测的行为特点出发,结合DFA、NFA模型各自的特性,提出了一种基于猜测-验证的匹配方法.首先使用DFA对正则表达式中的部分子特征进行搜索,完成特征存在性的猜测;当猜测到有可能匹配某个特征后,再使用NFA进行验证.文中方法既充分利用了DFA的高效性,减少了对相对较慢的验证过程的调用,又借助NFA避免了内存消耗过于巨大.结果表明,该方法可以在大大减少内存需求的情况下,实现正则表达式的高效匹配.     

一种用于深度包检测的正则表达式分组算法

当前深度包检测算法通常需要将正则表达式转换为NFA或者DFA．但是随着网络带宽的不断增加．NFA和DFA状态占用的存储空间越来越大,极大地考验着系统的存储能力。为了应对这个问题．提出一种基于正则表达式相性的分组算法来对表达式进行分组,实验证明该算法能减少NFA和DFA状态的数量,提高匹配的效率。     

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

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

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

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

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

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

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

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

基于正则表达式的应用层协议识别加速

在当今网络中,传统的采用端口进行协议识别已越来越无法满足需求.采用了正则表达式进行协议识别,并对其匹配正确性和速度进行了优化.通过将NFA匹配引擎转换为DFA匹配引擎,不仅减少了其状态数,还提高了匹配的速度;在匹配方式上提出了3种匹配方式,并加以测试比较,并与One-Pass扫描算法相结合.通过对DARPA数据集进行测试,验证加速后的匹配正确性比L7-filter高,匹配速度则可达到其6.5倍.     

Learning deterministic finite automata with a smart state labeling evolutionary algorithm

Learning a deterministic finite automaton (DFA) from a training set of labeled strings is a hard task that has been much studied within the machine learning community. It is equivalent to learning a regular language by example and has applications in language modeling. In this paper, we describe a novel evolutionary method for learning DFA that evolves only the transition matrix and uses a simple deterministic procedure to optimally assign state labels. We compare its performance with the evidence driven state merging (EDSM) algorithm, one of the most powerful known DFA learning algorithms. We present results on random DFA induction problems of varying target size and training set density. We also study the effects of noisy training data on the evolutionary approach and on EDSM. On noise-free data, we find that our evolutionary method outperforms EDSM on small sparse data sets. In the case of noisy training data, we find that our evolutionary method consistently outperforms EDSM, as well as other significant methods submitted to two recent competitions.     

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

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

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

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

Reducing graphics programming effort through structured support

This paper describes a method for structuring graphics support which simplifies the programming of interactive applications, while improving their portability by providing a device-independent interface. The primary objective is to ease the task of the application programmer in developing applications which use interaction and graphics. Common graphics functions which are used by several applications are generalized and defined in terms of transition tables. User actions become inputs, system wait points become states, and system responses are pointed to by table outputs. A suitable modification is applied to each of the generalized graphics functions to tailor it to be used by a particular application.     

On the look-ahead problem in lexical analysis

Modern programming languages use regular expressions to define valid tokens. Traditional lexical analyzers based on minimum deterministic finite automata for regular expressions cannot handle the look-ahead problem. The scanner writer needs to explicitly identify the look-ahead states and code the buffering and re-scanning operations by hand. We identify the class of finite look-ahead finite automata, which is general enough to include all finite automata of practical lexical analyzers. Finite look-ahead finite automata are then transformed into suffix finite automata. A new lexical analyzer makes use of the suffix finite automata to identify tokens. The new lexical analyzer solves the look-ahead problem in a table-driven approach and it can detect lexical errors at an earlier time than traditional lexical analyzers. The extra cost of the new lexical analyzers is the larger state transition table and three additional 1-dimensional tables. Incremental lexical analysis is also discussed.This work was supported in part by National Science Council, Taiwan, R.O.C. under grants NSC 83-0111-S-009-001-CL and NSC 84-2213-E-009-043