一种构造正则表达式更小ε-NFA的方法

基于有限自动机的正则表达式匹配技术在网络信息领域得到了广泛应用,提出了一种构造正则表达式的更小NFA的方法——基于闭包的分片构造法GREC.GREC方法基于正则表达式中同态运算的封闭性以及闭包运算的层次特性和递归性进行构造.首先对正则表达式进行分片处理,然后构造每个分片的NFA,最后利用栈对各分片NFA进行重组获得最终的NFA.GREC方法在正则表达式层次结构复杂或包含有大量闭包运算的情况下,能够快速地构造出空间效率比传统的Thompson构造法高得多的NFA.     

面向网络流的自适应正则表达式分组匹配算法

针对当前的多正则表达式匹配算法占用较大的系统资源,且吞吐量较低的问题,在分析典型的正则表达式匹配算法的基础上,提出了一种自适应的多正则表达式分组匹配算法.该算法通过对正则表达式进行高效分组,将相互之间存在交叠且容易引起状态数指数增长的表达式相互隔离;将每个分组构造为一个确定性有限自动机(DFA),按匹配概率大小建立伸展树进行调度.仿真结果表明,该算法不仅大大节省了存储空间,而且吞吐量提高了大约3倍.     

基于网络处理器的高速字符串匹配

为了解决网络深度检测系统中字符串匹配的速度瓶颈问题,提出了一种新的确定性有限状态自动机(DFA)实现结构,以及状态转移表静态Cache策略.该方法基于软硬件协同设计思想,从系统优化的角度综合网络处理器(NP)和字符串匹配算法特点.所提出的基于NP优化的AC算法(NP-AC)与标准Aho-Corasick(AC)算法相比,降低了访问外存次数和总的存储需求,提高了处理单元的利用率和吞吐量.测试表明,在单片Intel IXP2800网络处理器上NP-AC算法可以达到6.4 Gb/s的处理能力.     

一种基于Bloom Filter的正则表达式集合快速搜索算法

正则表达式搜索算法的性能与从非确定性有限状态自动机(NFA)的初始状态到终止状态的最短路径Lmin成正比,与正则表达式所表达的语言的前缀集合Pref(RE)成反比,而一般情况下Pref(RE)较大,确定Pref(RE)中的元素在目标文本中的出现位置比较困难.文中提出了一种基于Bloom Filter的正则表达式集合搜索算法,此算法利用Bloom Filter集合查询时间与集合大小无关的特点,可以快速准备定位Pref(RE)的出现位置,使得搜索速度不受Pref(RE)的影响,如果采用多个Bloom Filter并行,还可以间接增大Lmin.分析与测试结果表明,该算法较大地加快了正则表达式的搜索速度,对于正则表达式集合,算法性能改善尤其明显,在Lmin较长、Pref(RE)较大时,搜索速度可以提高数倍至数十倍,适合大规模的多正则表达式的快速搜索.     

基于规则分组的DFA正则表达式匹配算法

模式匹配因误报率低和漏报率低被入侵检测所采用.在使用正则表达式构造DFA时,因状态爆炸导致匹配算法需要较多的存储空间和运行时间,算法效率低下,采用规则分组后,可以在一定程度上抑制状态爆炸问题.根据缓存中的历史记录对正则表达式进行分组,既能利用规则分组减少状态总数,抑制状态爆炸,又能减少因每次重新构建DFA所带来的开销,提高了匹配效率,有利于提高入侵检测的实时性、准确性和高效性.     

P2P网络中基于非确定有限自动机的XML数据流过滤

将自动机方法对XML数据的过滤延伸到P2P网络中,依据在本地XML系统YFilter中构造非确定有限自动机(NFA)的思想,采用Chord环建立起分布式的NFA对于peer节点中的XML数据的查询过滤系统,并基于递归法执行查询过滤,在不同的peer节点上得到满足查询条件的数据集合。通过实验验证了当查询的数量和网络大小发生变化时分布式NFA的方法的执行性能。结果表明:本文方法可在不同的过滤场景中处理百万数量级的XPath查询,具有良好的网络流量和过滤延迟。     

基于参数设定的正则表达式匹配算法

为了解决现有正则表达式匹配算法在时间复杂度与空间复杂之间的平衡问题,提出一种通过参数动态设定的确定有限自动机(dynamic parameters DFA,DPDFA)的正则表达式匹配算法.首先对现有典型正则表达式匹配算法进行性能分析,指出它们在内存占用、规则匹配时间、可扩展性方面存在的不足.然后给出DPDFA算法的设计思想:先设定组合后状态数上限,分离组合表达式之间的互斥性,从而降低内存占用;再设定状态数增长率参数,将表达式进行切片,隔离状态数膨胀片段,降低它们之间的歧义匹配,从而节约匹配时间.试验结果表明,DPDFA算法在时间复杂度方面优于D2FA约23%,在空间复杂度方面优于m DFA约43%,在拓展性方面优于XFA近260%,整体匹配效率方面也优于其他算法.     

关于确定有穷自动机最小化算法的注记

《程序设计语言编译原理》给出了确定有穷自动机(以下简称为DFA)最小化的算法.步骤1 构造DFA M 状态集S的分划Ⅱ.该分划是由若干个不相交的状态子集所组成,并且任何不同的两子集的状态都是可区别的,而同一子集中的任何两个状态都是等价的.其构造算法如下:BEGIN     

一种非确定型有穷自动机的极小化方法

自动机状态极小化是寻求状态数较少的自动机,使其与原自动机接受相同的语言．确定型有穷状态自动机（DFA）极小化问题在平方时间内可解,通过状态集上引入等价关系导出的商自动机即为接受相同正则语言的极小化自动机．而非确定型有穷状态自动机（NFA）极小化问题尚未找到有效算法．尽管NFA可以转化为DFA且接受的语言不变,但可能会出现状态数指数级增加．从语言B可以构造一个接受自己的子语言自动机,同态压缩映射子语言自动机为最终系统,从而为接受语言B的极小化自动机．     

基于多GPU的正则表达式匹配技术

针对传统正则匹配性能低下的问题,设计了基于多GPU的正则表达式匹配引擎,并采用折半分组优化算法解决了有限状态自动机在大规模正则集合情况下由于空间爆炸无法使用的问题,并做了相关的优化,提升了数据匹配速度.实验结果表明:基于多GPU的正则表达式匹配性能较CPU提升了61倍,其数据吞吐率远优于其他加速方式.     

高速网络环境下的新型木马快速检测方法研究

为了适应高速网络环境下的木马检测,通过分析传统的IDS,针对其在高速网络环境下对木马检测能力的不足,提出了单引擎大特征集的木马检测方法;通过分析木马的网络数据特征,对有限自动机转换过程进行优化,缩短了编译的时间,避免了重复匹配的问题,大幅度提高了基于正则表达式的木马检测方法的效率.     

基于NFA的XML数据流查询算法设计与实现

随着XML数据流应用的深入,如何在XML数据流上执行海量的XPath查询便成为迫切需要解决的问题。本文根据XPath语法规则,即任意一个XPath路径表达式都可转化成一个正则表达式,基于自动机理论,实现了基于NFA的XPath表达式的查询处理。     

非确定型有穷自动机的极小化

利用自动机状态集上的等价关系对自动机的状态集进行极小化, 从而得到与原自动机功能等价的极小化自动机. 通过两台确定型有穷自动机（DFA）的连接, 构造一台非确定型有穷自动机（NFA）. 利用这两台确定型有穷自动机状态集上的等价关系, 可以构造这台非确定型有穷自动机状态集上的等价关系, 从而对这台非确定型有穷自动机进行极小化. 结果表明这台非确定型有穷自动机的极小化自动机的状态复杂 度, 不大于对那两台确定型有穷自动机的极小化自动机进行连接得到的非确定型有穷自动机的状态复杂度; 并且自动机在等价关系基础上进行极小化时不改变识别语言.     

基于TCP状态有限自动机的入侵检测研究

入侵检测是一种重要的信息安全防御技术.基于TCP状态有限自动机的入侵检测是一种异常检测方法,它能发现违背TCP状态有限自动机的行为.描述了TCP协议中正常的连接状态转换关系,构造了TCP状态有限自动杌,给出了基于TCP状态有限自动机的入侵检测实现.     

基于TCP状态有限自动机的入侵检测研究

入侵检测是一种重要的信息安全防御技术.基于TCP状态有限自动机的入侵检测是一种异常检测方法,它能发现违背TCP状态有限自动机的行为.描述了TCP协议中正常的连接状态转换关系,构造了TCP状态有限自动杌,给出了基于TCP状态有限自动机的入侵检测实现.     

一种基于NFA查询重写的XML过滤技术

研究了可扩展的标志性语言(XM L)存取控制策略。通过基于不确定的自动机(NFA)的XM L查询重写技术,实现了支持精细粒度的XM L文档存取控制策略。通过构造XM L文档存取控制策略的NFA以及基于NFA的查询语句重写技术,有效地实现了独立于视图的、高效的XM L精细粒度的存取控制。     

基于前序关系的非确定型有穷自动机极小化算法

为了减少非确定型有穷自动机(non-deterministic finite automata,NFA)的状态数,引入前序关系,并以图论为工具,将NFA的转移图看作一个带有标记的有向图,给出了NFA极小化的一个新方法。与现行的利用归并等价状态来极小化NFA的算法相比,该方法可以使得NFA在接受语言的能力等价的前提下,状态数得到进一步的减少。     

有限自动机的最小化理论

系统表述确定性有限自动机最小化理论,给出了有关概念与命题的严谨的数学形式和严格的数学证明.引入了状态的严格k阶区分,研究了其性质.进而给出DFA最小化算法的一个容易实现的构造性描述及其复杂性分析.     

一种正则表达式集合快速搜索算法

正则表达式由于其强描述能力和灵活性,在信息检索,程序设计,数据挖掘,深度分组检测,生物信息处理等领域得到了广泛而深入的应用,然而正则表达式,尤其是正则表达式集合,由于搜索速度慢往往成为系统的性能瓶颈。现有的正则表达式搜索算法性能较好的是多模式过滤类型的算法,此类算法严重依赖于两个因素,从NFA的初始状态到终止状态的最短路径Lmin和正则表达式所表达的语言的前缀集合Pref（RE）的大小,Lmin越长,搜索速度越快,Pref（RE）越大,搜索速度越慢。针对上述问题提出了一种基于Bloom filter的正则表达式集合搜索算法,此方法利用Bloom filter的集合查询时间集合大小无关的特点,使得正则表达式搜索速度不受Pref（RE）大小的影响,如果采用多个Bloom filter并行,还可以间接增大Lmin的长度。分析与测试结果表明,本算法较大的加快了正则表达式的搜索速度,对于正则表达式集合,算法性能改善尤其明显,可以实现大规模正则表达式集合的快速搜索。     

有限自动机在模式匹配中的应用与研究

有限自动机匹配算法是多模式匹配中的重要算法.反向有限自动机在一定的条件下能压缩自动机的规模,从而提高模式匹配的速度.将反向有限自动机算法与BM算法相结合,利用当前获取信息进一步增大匹配过程中的跳跃距离,可进一步提高模式匹配的速度.