面向存储的正则表达式匹配算法综述 被引量：13

1

作者 姚远 刘鹏 +1 位作者 单征 田双鹏 《计算机应用》 CSCD 北大核心 2009年第12期3171-3173,3177,共4页

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

关键词 确定的有限自动机 面向存储 正则表达式 深度包检测 压缩算法

下载PDF 职称材料

基于云模型的网络系统状态评估与预测模型研究 被引量：11

2

作者 李飞 张仕斌 《四川大学学报（工程科学版）》 EI CAS CSCD 北大核心 2010年第6期99-104,共6页

目前,国内外众多网络系统可生存性研究都主要集中在理论上的研究,且均使用经典的数学理论来研究复杂多变环境下的网络系统状态,也没有形成完整的理论体系,而实际上网络系统状态具有不确定性、随机性等特性。以可信网络的可生存性为研究... 目前,国内外众多网络系统可生存性研究都主要集中在理论上的研究,且均使用经典的数学理论来研究复杂多变环境下的网络系统状态,也没有形成完整的理论体系,而实际上网络系统状态具有不确定性、随机性等特性。以可信网络的可生存性为研究背景,首先分析了网络可生存性等关键问题。考虑到网络系统状态具有不确定性、随机性等特征,引入云模型和有限状态机理论对网络系统状态来进行描述和检测,提出了基于云模型的网络系统状态评估与预测模型,并从理论上进行了具体的分析和求证。最后通过仿真实验与分析,进一步说明了本研究的模型的可行性与合理性,为当前错综复杂的网络系统的可生存性研究提供了一种有价值的新思路。 展开更多

关键词 云模型 网络系统 有限状态机 状态评估 预测模型

下载PDF 职称材料

Xgadget:基于动静结合的二进制Gadget搜索

3

作者 吕建强 付才 +3 位作者 何帅 江帅 李明 韩兰胜 《计算机工程与应用》 CSCD 北大核心 2024年第9期299-308,共10页

代码复用技术一直以来都是软件安全研究领域的热点,ROP(return-oriented programming)、JOP(jump-oriented programming)和DOP(data-oriented programming)技术是典型代表。Gadget搜索是代码复用的基础,针对现有静态搜索算法存在支持的G... 代码复用技术一直以来都是软件安全研究领域的热点,ROP(return-oriented programming)、JOP(jump-oriented programming)和DOP(data-oriented programming)技术是典型代表。Gadget搜索是代码复用的基础,针对现有静态搜索算法存在支持的Gadget类型不多,不能同时搜索动态链接库等问题,提出了基于动静结合的二进制Gadget搜索方法,基于此开发了搜索工具Xgadget。利用动态映像级插桩,对所有函数进行反汇编;设计了Token级和指令级有穷自动机,实现了基于自动机的静态搜索算法;在五款应用程序中对其进行了测试与评估。实验结果表明,算法支持ROP、JOP、DOP等多种Gadget类型的搜索,能够同时对目标程序动态链接库进行搜索,搜索数量是ROPgadget的12.5倍,单位指令搜索时间较之降低32.1%。算法为不同需求的代码复用提供更为广泛的支持,且输出结果是二进制Gadget,后续复用更直接,有利于代码复用自动化利用。 展开更多

关键词 代码复用 Gadget搜索 动静结合 dfa算法 二进制 DOP方法 动态链接库

下载PDF 职称材料

一种针对DFA状态爆炸的正则表达式匹配方法 被引量：4

4

作者 王翔 卢毓海 +1 位作者 马伟 刘燕兵 《计算机工程》 CAS CSCD 北大核心 2019年第4期148-156,共9页

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

关键词 正则表达式 确定有限自动机 状态爆炸 子串抽取 匹配引擎

下载PDF 职称材料

一种高效匹配PCRE的扩展自动机 被引量：2

5

作者 刘鹏 姚远 +1 位作者 邰铭 张铮 《计算机工程》 CAS CSCD 北大核心 2010年第12期39-42,共4页

分析现有方法处理状态爆炸的局限性,将条件函数和位图结构引入自动机,提出一种位图移位有限自动机(Bs-FA),并给出由正则表达式到Bs-FA的一般方法。对计数字符组与前缀交迭的情况,仅需引入较小位图空间,就能使整个自动机内存空间明显减... 分析现有方法处理状态爆炸的局限性,将条件函数和位图结构引入自动机,提出一种位图移位有限自动机(Bs-FA),并给出由正则表达式到Bs-FA的一般方法。对计数字符组与前缀交迭的情况,仅需引入较小位图空间,就能使整个自动机内存空间明显减少。在实际规则集上评估,并与现有方法进行比较,说明该自动机的应用价值。 展开更多

关键词 确定的有限自动机 深度包检测 正则表达式

下载PDF 职称材料

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

6

作者 卓艳男 刘强 +1 位作者 姜磊 戴琼 《计算机应用》 CSCD 北大核心 2016年第4期927-930,共4页

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

关键词 正则表达式 现场可编程门阵列 模式匹配 确定性有穷状态自动机

下载PDF 职称材料

识别幺半群强半格的最少状态DFA 被引量：1

7

作者 黎宏伟 《江苏师范大学学报（自然科学版）》 CAS 2017年第4期36-38,共3页

为了研究识别幺半群强半格的最少状态DFA,对幺半群强半格的R类进行了深入探讨,证明了当每个幺半群中只有一个R类时,幺半群强半格中的R类的个数就是幺半群的个数,且半群中的R类是正规语言中的一种右不变等价类.借助这两个结论,证明了识... 为了研究识别幺半群强半格的最少状态DFA,对幺半群强半格的R类进行了深入探讨,证明了当每个幺半群中只有一个R类时,幺半群强半格中的R类的个数就是幺半群的个数,且半群中的R类是正规语言中的一种右不变等价类.借助这两个结论,证明了识别幺半群强半格的最少状态DFA的终结状态的个数等于幺半群的个数,并建立了识别幺半群强半格的最少状态DFA. 展开更多

关键词 强半格 幺半群 确定型有穷自动机

下载PDF 职称材料

基于确定有限自动机实现MES的流程控制应用研究 被引量：1

8

作者 吴卫平 王丽芳 蒋泽军 《航空计算技术》 2007年第4期53-55,59,共4页

简述确定有限自动机的基本概念,提出了应用确定有限自动机在MES中实现流程控制的思想。通过XML来构造确定有限自动机,并给出实现方法和实例。

关键词 确定有限自动机 XML 流程控制

下载PDF 职称材料

确定自动机上的XML数据过滤算法改进

9

作者 印桂生 沈洁 谢晓芹 《哈尔滨工程大学学报》 EI CAS CSCD 北大核心 2011年第3期328-333,共6页

XML数据过滤过程中存在的缓存失效会导致过滤效率的降低,因此研究基于确定有限自动机的XML数据过滤过程中如何减少缓存失效对于改进过滤的性能具有重要意义.对已有的Lazy DFA执行算法进行改进,引入了频繁访问区的概念,对缓存中的状态增... XML数据过滤过程中存在的缓存失效会导致过滤效率的降低,因此研究基于确定有限自动机的XML数据过滤过程中如何减少缓存失效对于改进过滤的性能具有重要意义.对已有的Lazy DFA执行算法进行改进,引入了频繁访问区的概念,对缓存中的状态增加一个状态转换计数器,然后通过设定该计数器的访问阈值对缓存中的数据进行筛选,超过该阈值的状态被确定为频繁访问区中的状态.并通过实验证明该访问机制可以减少自动机中状态转移过程在缓存大量状态中的搜索时间,从而有效地提高过滤和查询的时间性能. 展开更多

关键词 dfa XML 状态转移 频繁访问节点

下载PDF 职称材料

构建最小入侵检测特征集的贪心算法

10

作者 陈传鹏 潘送军 《企业技术开发》 2012年第12期26-27,共2页

文章通过贪心算法构建入侵检测特征串的最小特征集,并生成基于该最小特征集的确定有限状态自动机(DFA)。实验结果表明:该方法减少入侵检测特征的存储空间40%,提高了基于DFA模式匹配的入侵检测速度,有效提升了入侵检测软硬件系统的性能。

关键词 入侵检测 贪心算法 有限状态自动机

下载PDF 职称材料

基于图划分的正则表达式分组算法 被引量：3

11

作者 魏强 李云照 褚衍杰 《计算机工程》 CAS CSCD 2012年第18期137-139,共3页

针对多条正则表达式转换为确定型有限自动机带来的状态空间膨胀问题,借鉴图划分的思想,提出一种改进的分组算法。与原分组算法相比,该算法在分组数相同时状态数平均减少30%,在某些情况下能获得更少的分组数。实验结果证明,该算法能有效... 针对多条正则表达式转换为确定型有限自动机带来的状态空间膨胀问题,借鉴图划分的思想,提出一种改进的分组算法。与原分组算法相比,该算法在分组数相同时状态数平均减少30%,在某些情况下能获得更少的分组数。实验结果证明,该算法能有效降低匹配算法的复杂度。 展开更多

关键词 深度包检测 模式匹配 正则表达式 确定型有限自动机 分组算法 图划分

下载PDF 职称材料

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

12

作者 吴绍根 李洛 《微型电脑应用》 2006年第5期10-12,2,共3页

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

关键词 入侵检测系统 确定型有限自动机 非确定型有限自动机 等价性

下载PDF 职称材料

基于稀疏矩阵存储的状态表压缩算法 被引量：5

13

作者 姚远 刘鹏 +1 位作者 王辉 笱程成 《计算机应用》 CSCD 北大核心 2010年第8期2157-2160,2217,共5页

正则表达式匹配对于网络安全应用至关重要。将稀疏矩阵和索引表引入确定的有限自动机的状态转换表,提出了一种稀疏矩阵索引的状态压缩表算法,并给出了稀疏矩阵和索引表的构造方法。而后同字母压缩表算法结合,给出了该算法的优化策略。... 正则表达式匹配对于网络安全应用至关重要。将稀疏矩阵和索引表引入确定的有限自动机的状态转换表,提出了一种稀疏矩阵索引的状态压缩表算法,并给出了稀疏矩阵和索引表的构造方法。而后同字母压缩表算法结合,给出了该算法的优化策略。最后在实际规则集上进行评估,实验结果证明了算法的压缩效果,并进一步得出了算法的适用范围。 展开更多

关键词 确定的有限自动机 深度包检测 正则表达式 稀疏矩阵 压缩算法

下载PDF 职称材料