一类NFA 到DFA 的直接转化方法

NFA的确定化具有重要的理论和实际意义.迄今为止,普遍采用子集构造法将一个NFA(非确定性自动机)转化为DFA(确定性自动机),但这种方法需要引入空输入ε及状态子集I的ε-闭包,其计算过程相对繁琐.而且在确定化过程中对于NFA状态集存在ε-closure重复计算和由于对非ε转换的判断而引起的重复计算等问题.本文描述了一种将一类NFA直接转化为DFA的方法.在本方法中,不需要引入空输入ε,可根据原始的NFA状态图或状态转移表直接得出等价的DFA状态图或状态转移表,而且所有状态都是单一的状态而非集合状态,便于软硬件实现与测试.     

入侵检测系统中模式匹配自动机的构造研究

本文提出了一种新的用于构造入侵检测模式匹配自动机的方法。该方法从构造判定单个模式的NFA自动机入手,通过集成单个的NFA而得到全集的NFA,并将全集NFA转换为与之等价的DFA并化简,从而可得到全集的确定型模式匹配有限自动机。由于该方法可以完全自动完成,从而可以方便地为入侵检测系统构造模式匹配自动机。     

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

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

一种适于XPath查询的自动机最小化算法

近年来,XM L数据流的查询处理引起了国内外学者的广泛兴趣。如何在XM L流中有效地查询大量XPath表达式是当今研究的一个热点问题。先将多个XPath式通过共享前缀处理,构造一个非确定的有穷自动机（NFA）模型,再将其转化为确定的有穷自动机（DFA）,以实现状态转移的确定性,然后对DFA进行最小化,提出了一种普遍适用的改进的最小化算法,在执行效率和空间代价方面它都优于一般性算法。     

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

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

XSIEQ-一种立即计算的XML流查询系统

XSIEQ是一种立即计算谓词并即时输出的XML流查询系统．它利用前缀共享的方法由多个XPath式构造一个NFA，并对NFA状态进行分类和添加索引．使得在运行时能快速确定谓词计算和数据缓存等的时机，XSIEQ还提供在运行时惰性地构造DFA进行查询．陈述了XSIEQ的查询机制以及多重匹配问题的解决方案，最后给出了XSIEQ的两种自动机和YFilter的查询性能对比及分析．     

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

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

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

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

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

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

基于动态默认转移的深度包检测算法

由于基于确定性有限自动机（DFA）的多模式匹配算法对内存的需求比较大,因此需要对DFA进行优化,以减少其对内存的需求量。算法通过用动态默认转移来替代DFA的failto转移,将DFA中大量的failto转移删掉,从而达到优化DFA的目的。实验结果证明,该算法能有效地优化DFA对内存的需求。     

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

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

一种快速且节约存储器的多模式匹配算法

同时对数百个模式进行比较的多模式匹配算法是入侵侦测/预防系统的一项关键技术.但是在Gbps级的高速网络中,多模式匹配过度仍是一个瓶颈.提出一个基于确定性有限自动机(DFA)的算法,能在一个周期内处理多个字符.该算法持DFA的头部抽取出来,构造一个子DFA,称为Head DFA(HDFA),将其余部分构成另一个子DFA-General DFA(GDFA).针对这两个子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%.     

一种面向深度包检测的DFA压缩算法

DFA (确定性有限自动机)对于实现深度包检测（deep packet inspection, DPI）技术具有重要作用。随着深度包检测规则的不断增多,DFA所需的存储空间急剧增大。为此,本文提出了一种基于字符替换的DFA压缩算法,利用状态转换表中每个状态通常只有少数几个不同跳转的特点,我们将状态转换表分解为剩余表和字符替换表,减少了存储空间。此外,通过使相似的状态可以共享相同的字符替换表以进一步压缩存储空间。最后,本文给出了复杂度为O(n2)的压缩算法,n为DFA的状态数。实验结果表明,该算法在L7-filter和Snort规则集上具有较稳定的压缩率,压缩率都在5%以下。     

一种新的基于有限自动机的XML过滤方法

设计实现了一种新的基于有限自动机的XML过滤方法，这种方法和以往基于有限自动机方法（不确定的有限自动机和确定的有限自动机）的不同在于它首先使用XML Schcma把带“*,//”的路径表达式简化，然后把生成的DFAs合并成一个大的DFA，这个DFA充当过滤引擎。     

一种将NFA到最小化DFA的方法

词法分析是编译程序重要阶段，有效的词法分析可提高编译程序的效率。本文提出用子集方法完成NFA到DFA并使用树型分割法实现DFA到最小化DFA的化简。     

Streett自动机确定化工具

自动机的确定化是将非确定性自动机转换为接收相同语言的确定性自动机,是自动机理论的基本问题之一.ω自动机的确定化是诸多逻辑,如SnS, CTL*,μ演算等,判定过程的基础,同时也是解决无限博弈求解问题的关键,因此对ω自动机确定化的研究具有重要意义.主要关注一类ω自动机——Streett自动机的确定化.非确定性Streett自动机可以转换为等价的确定性Rabin或Parity自动机,在前期工作中已经分别得到了状态复杂度最优以及渐进最优算法,为了验证提出的算法的实际效果,也为了形象地展示确定化过程,开发一款支持Streett自动机确定化的工具是必要的.首先介绍4种不同的Streett确定化结构:μ-Safra tree和H-Safra tree (最优)将Streett确定化为Rabin自动机, compact Streett Safra tree和LIR-H-Safra tree (渐进最优)将Streett确定化为Parity自动机;然后,根据Streett确定化算法,基于开源工具GOAL (graphical tool for omega-automata and logics),实现...     

基于多字符DFA的高速正则表达式匹配算法

基于确定性有限自动机(DFA)的传统正则表达式匹配方法存在单周期处理单字符的速度瓶颈。为提升处理速率,提出一种单周期处理多字符的匹配算法MC-DFA,该算法基于DFA实现,支持匹配位置的精确定位。MC-DFA将传统DFA中的单字符跳转合并为多字符跳转,实现了单周期处理多个输入字符。通过状态转移矩阵二阶压缩算法,MC-DFA分别对矩阵行内以及行间冗余进行消除,减少了内存使用。300条规则下,单周期处理8字符时,MC-DFA吞吐率能够达到7.88Gb/s,内存占用小于6MB,预处理时间为19.24s。实验结果表明,MC-DFA能够有效提升系统吞吐率,并且保证内存占用在可接受范围之内,性能优于现有正则表达式匹配算法。     

基于行为自动机的构件可替换性分析与验证

在交互协议层面讨论构件的可替换性,采用非确定性有限状态自动机(nondeterministic finite automata,简称NFA)来建模构件的交互行为,在保证交互兼容性的前提下,提出了按构件环境的透明度和构件交互的变化度两维划分的可替换性模型,给出了4类可替换性的形式化定义及其之间的关系,并基于NFA理论给出了相关的验证算法。另外,该模型以构件的替换行为而不是其全部行为作为构件替换的参照,从而使替换时有更多的候选构件可供使用,提高了构件复用的几率。     

带谓词的XPath查询的即时处理

介绍了一种立即计算谓词并即时输出的XML流数据查询系统XSIEQ。XSIEQ采用修改了的下推自动机技术,对多个XPath式按前缀共享的方式构造NFA,并对NFA状态进行类型标记和添加索引;从而在运行时能快速确定谓词计算和数据缓存等动作的时机,实现了即时处理;最后给出了XSIEQ和YFilter的查询性能对比及分析。