一种基于智能有限自动机的正则表达式匹配算法 被引量：14

1

作者 张大方 张洁坤 黄昆 《电子学报》 EI CAS CSCD 北大核心 2012年第8期1617-1623,共7页

本文提出了一种基于智能有限自动机(Smart Finite Automaton,SFA)的正则表达式匹配算法,在XFA的分支迁移边上增加额外的判断操作指令,消除XFA的回退迁移边,避免不必要的状态迁移操作.实验结果表明,SFA提高了正则表达式匹配的时空效率,与... 本文提出了一种基于智能有限自动机(Smart Finite Automaton,SFA)的正则表达式匹配算法,在XFA的分支迁移边上增加额外的判断操作指令,消除XFA的回退迁移边,避免不必要的状态迁移操作.实验结果表明,SFA提高了正则表达式匹配的时空效率,与XFA相比,在存储空间开销上减少了44.1%,在存储器访问次数上减少了69.1%. 展开更多

关键词 深度数据包检测 正则表达式匹配 确定型有限自动机 扩展有限自动机 智能有限自动机

在线阅读 下载PDF 职称材料

基于扩展确定有限自动机的功能需求获取方法

2

作者 马赞 王鹏 崔明山 《实验技术与管理》 CAS 北大核心 2020年第5期78-84,共7页

功能需求获取一直是系统需求分析的难点,目前尚无特别有效的方法。该文通过对确定有限自动机的扩展(extended deterministic finite automata,EDFA),将系统输入与确定有限状态机的输入激励相结合,将系统输出与系统输入和系统状态相结合... 功能需求获取一直是系统需求分析的难点,目前尚无特别有效的方法。该文通过对确定有限自动机的扩展(extended deterministic finite automata,EDFA),将系统输入与确定有限状态机的输入激励相结合,将系统输出与系统输入和系统状态相结合,通过确定有限状态机的状态集合,划分系统功能需求空间,提出了一种结构化的功能需求获取方法,有助于提升功能需求获取的完整性,降低功能需求获取的难度。通过对自动巡航系统跟车模式下的需求获取,验证了基于EDFA功能需求获取方法的有效性和实用性。 展开更多

关键词 需求获取 功能需求 扩展确定有限自动机(EDFA) 需求获取流程 结构化需求获取

在线阅读 下载PDF 职称材料

多用户界面应用程序代码自动生成机制研究

3

作者 邹静 陈英 姜波 《北京理工大学学报》 EI CAS CSCD 北大核心 2003年第5期589-592,600,共5页

设计和实现一种针对多用户界面应用系统的专用CASE平台,提出在这种CASE平台中具有新意且实用的代码自动生成方法.在论述作为代码自动生成机制的EFSM的定义基础上,通过实例介绍了在这种CASE平台中基于设计模型提取资源、建立EFSM模型,直... 设计和实现一种针对多用户界面应用系统的专用CASE平台,提出在这种CASE平台中具有新意且实用的代码自动生成方法.在论述作为代码自动生成机制的EFSM的定义基础上,通过实例介绍了在这种CASE平台中基于设计模型提取资源、建立EFSM模型,直到生成代码的全过程,进而验证了多用户界面应用系统平台上基于EFSM的代码自动生成机制的可行性. 展开更多

关键词 计算机辅助软件工程 扩展的有限状态自动机 代码自动生成

在线阅读 下载PDF 职称材料

高性能正则表达式匹配算法评估 被引量：4

4

作者 金军航 张大方 黄昆 《计算机工程》 CAS CSCD 北大核心 2010年第19期269-271,共3页

为对现有的高性能正则表达式匹配算法进行综合比较与分析,实现诸如DFA、D2FA、CD2FA、mDFA及XFA等最新算法,采用Snort规则集综合评估这些算法的存储空间和匹配时间。实验结果表明,在存储空间方面,与mDFA相比,XFA的存储空间减少84.9%89.... 为对现有的高性能正则表达式匹配算法进行综合比较与分析,实现诸如DFA、D2FA、CD2FA、mDFA及XFA等最新算法,采用Snort规则集综合评估这些算法的存储空间和匹配时间。实验结果表明,在存储空间方面,与mDFA相比,XFA的存储空间减少84.9%89.9%;在匹配效率方面,与mDFA相比,XFA的匹配时间增加了38.9%174.6%;XFA在存储空间和匹配效率上具有良好的可伸缩性,即当规则数增加到8倍时,mDFA的存储空间增长了64倍,而XFA的存储空间仅增加了16倍,匹配时间仅增加了61.3%。 展开更多

关键词 正则表达式匹配 确定有限自动机 扩展有限自动机 性能评估

在线阅读 下载PDF 职称材料

基于规则模板的正则表达式分组算法 被引量：8

5

作者 邵翔宇 刘勤让 谭力波 《电子学报》 EI CAS CSCD 北大核心 2016年第1期236-240,共5页

采用规则分组的方法解决确定型有限自动机（Deterministic Finite Automata,DFA）状态爆炸问题,随着分组数目的增加,匹配效率大大降低.本文提出正则表达式的输入驱动特性理论,并基于此提出了基于规则模板的分组算法——模板有限自动机.... 采用规则分组的方法解决确定型有限自动机（Deterministic Finite Automata,DFA）状态爆炸问题,随着分组数目的增加,匹配效率大大降低.本文提出正则表达式的输入驱动特性理论,并基于此提出了基于规则模板的分组算法——模板有限自动机.模板有限自动机算法基于规则模板对规则集进行分组,各分组分别构建匹配引擎.理论分析和实验表明,与典型的DFA改进算法相比,预处理时间和存储空间有2~3个数量级别的缩减,且匹配效率没有明显降低. 展开更多

关键词 正则表达式 确定型有限自动机 分组自动机 扩展有限自动机 多维有限自动机 规则模板

在线阅读 下载PDF 职称材料

大规模复杂规则匹配技术研究 被引量：3

6

作者 张树壮 罗浩 方滨兴 《高技术通讯》 EI CAS CSCD 北大核心 2010年第12期1217-1223,共7页

针对当前安全系统对复杂规则的需求和复杂规则匹配技术的状况,提出了一种新的规则表示方式——字符串表达式,并给出了对应的匹配方法——基于扩展的有限状态自动机(XFA)实现大规模复杂规则匹配的算法。字符串表达式可以描述多个精确字... 针对当前安全系统对复杂规则的需求和复杂规则匹配技术的状况,提出了一种新的规则表示方式——字符串表达式,并给出了对应的匹配方法——基于扩展的有限状态自动机(XFA)实现大规模复杂规则匹配的算法。字符串表达式可以描述多个精确字符串之间的逻辑关系与空间位置关系,从而满足安全系统对复杂特征的描述需求。匹配使用二维结构来完成,首先用经典串匹配算法进行字符串的存在性验证,然后将其结果作为输入,驱动以表达式中字符串为"字符"的XFA完成逻辑关系的验证。基于XFA的匹配方法的空间效率和时间效率都接近多模精确串匹配算法。实验结果表明,文中提出的方法既能满足安全系统对关联特征的描述需求,又能提供高效的匹配性能,较好地解决了大规模(万条)的复杂规则匹配问题。 展开更多

关键词 串匹配 正则表达式 字符串表达式 扩展字符串匹配 扩展有限自动机

在线阅读 下载PDF 职称材料

一种改进的XFA在深度包检测中的应用 被引量：1

7

作者 魏德志 洪联系 +1 位作者 林丽娜 吴旭 《计算机工程与应用》 CSCD 2012年第34期245-248,共4页

提出了一种应用于深度包检测的改进XFA。该算法在XFA的分支迁移边上添加判断指令,消除XFA存在冗余迁移边的问题;采用并行检测机制,将匹配线程升级为两个并行的线程,预统计线程和状态机匹配线程,加快匹配速度。实验验证该算法有更快的运... 提出了一种应用于深度包检测的改进XFA。该算法在XFA的分支迁移边上添加判断指令,消除XFA存在冗余迁移边的问题;采用并行检测机制,将匹配线程升级为两个并行的线程,预统计线程和状态机匹配线程,加快匹配速度。实验验证该算法有更快的运行速度和稳定性,适合多核计算环境。 展开更多

关键词 正则表达式 深度包检测 并行线程 扩展有限自动机 网络安全

在线阅读 下载PDF 职称材料

基于UML规格说明的增量式测试用例生成

8

作者 卢炎生 郭红涛 +1 位作者 谢晓东 毛澄映 《计算机工程与科学》 CSCD 2006年第4期53-55,共3页

测试用例的生成是软件测试的关键环节。本文把基于UML的规格说明和扩展的有限自动机结合起来,利用矩阵存储扩展自动机的状态和状态转换信息,用伪等价类生成树递增地生成测试用例,对类测试的测试用例自动生成作了有益的探讨。

关键词 测试生成 统一建模语言 扩展有限自动机 增量测试方法

在线阅读 下载PDF 职称材料

基于预定义类的紧凑型正则表达式匹配算法 被引量：7

9

作者 麦涛涛 潘晓中 +1 位作者 王亚奇 苏阳 《计算机应用》 CSCD 北大核心 2017年第2期397-401,416,共6页

针对目前硬件正则表达式匹配算法在存储空间以及吞吐量等方面面临的挑战,结合扩展有限自动机(XFA)正则表达式匹配算法,提出了一种预定义类的压缩自动机匹配算法(Pre-Class CFA)。通过预定义类,算法既可以实现正则表达式中类字符匹配,又... 针对目前硬件正则表达式匹配算法在存储空间以及吞吐量等方面面临的挑战,结合扩展有限自动机(XFA)正则表达式匹配算法,提出了一种预定义类的压缩自动机匹配算法(Pre-Class CFA)。通过预定义类,算法既可以实现正则表达式中类字符匹配,又能够通过优先级的设定匹配特殊字符集,并在XFA消除确定性有限状态机(DFA)状态爆炸问题的基础上进一步压缩了迁移边数目;同时算法根据现场可编程门阵列(FPGA)和迁移边的特征,设计了一种基于并联只读存储器(ROM)结构的迁移边存取方法,可以实现同一状态多条迁移边的并行读取和匹配。在中低性能FPGA平台ALTERA DE2-70上对算法进行测试,实验中系统吞吐量为1.3 Gb/s,可实现千兆网络下的入侵检测和垃圾过滤。 展开更多

关键词 正则表达式匹配 扩展有限自动机 现场可编程门阵列

在线阅读 下载PDF 职称材料

面向语用的仿真组件形式化建模及组合技术研究 被引量：3

10

作者 胡鹏 沈建京 吴善明 《计算机应用研究》 CSCD 北大核心 2015年第9期2697-2701,共5页

语法和语义层次的组合并不足以保证仿真组件组合的完整性、有效性和实用性,在语用组合问题分析的基础上,提出了基于扩展有限状态自动机的仿真组件模型形式化描述,包含了仿真组件行为语义和仿真运行语境约束信息,并在此基础上设计了基于... 语法和语义层次的组合并不足以保证仿真组件组合的完整性、有效性和实用性,在语用组合问题分析的基础上,提出了基于扩展有限状态自动机的仿真组件模型形式化描述,包含了仿真组件行为语义和仿真运行语境约束信息,并在此基础上设计了基于XML的仿真组件模型描述规范。最后,通过应用实例具体描述了面向语用组合的仿真组件模型组合过程。组合中考虑了模型发现、组合判定、仿真运行与仿真语境之间的关系,并且实现了面向语用的仿真系统自动化动态构建。 展开更多

关键词 语用 组合 仿真组件 形式化建模 扩展有限状态自动机

在线阅读 下载PDF 职称材料

语用层次仿真组件组合性质分析 被引量：2

11

作者 胡鹏 沈建京 陶林波 《计算机工程》 CAS CSCD 北大核心 2016年第2期293-299,共7页

针对语法和语义层次组合存在对仿真环境的匹配及组合结果实用性不强的问题,在语用组合与仿真语境研究的基础上,给出仿真语境空间形式化定义,提出一种基于语境空间匹配指数的静态语用组合性质分析方法。对扩展有限状态自动机进行分析,设... 针对语法和语义层次组合存在对仿真环境的匹配及组合结果实用性不强的问题,在语用组合与仿真语境研究的基础上,给出仿真语境空间形式化定义,提出一种基于语境空间匹配指数的静态语用组合性质分析方法。对扩展有限状态自动机进行分析,设计支持语境约束的仿真组件模型形式化描述,建立仿真组件模型与着色Petri网(CPN)之间的映射,并利用CPN Tools工具实现组合模型的动态语用可组合性质分析。应用结果表明,语用层次的仿真组件静态、动态组合性质分析,可为仿真组件发现、仿真建模优化、组合结果有效性判定等关键问题提供量化、直观的依据。 展开更多

关键词 语用 语境 仿真组件 组合性质分析 扩展有限状态自动机

在线阅读 下载PDF 职称材料

面向协议一致性测试的测试序列生成方法研究 被引量：1

12

作者 张新常 杨美红 +1 位作者 罗万明 耿光刚 《高技术通讯》 CAS CSCD 北大核心 2011年第10期1034-1041,共8页

考虑到协议一致性测试中基于扩展有限状态自动机（EFSM）模型的测试序列生成仍然是一个尚无理想方法解决的开放性问题，提出了一种面向协议一致性测试的基于EFSM模型的测试序列生成方法。此方法将EFSM模型转换成确定化的EFSM（DEFSM）... 考虑到协议一致性测试中基于扩展有限状态自动机（EFSM）模型的测试序列生成仍然是一个尚无理想方法解决的开放性问题，提出了一种面向协议一致性测试的基于EFSM模型的测试序列生成方法。此方法将EFSM模型转换成确定化的EFSM（DEFSM）模型，并在转换过程中对EFSM模型中的条件和操作冲突进行检测并加以消除，此外，通过测试序列生成附加模块的协助，可将变量及其条件判定从DEFSM模型中分离出来，使得处理后的DEFSM模型等同于有限状态自动机（FSM）模型，从而将EFSM的描述优势和基于FSM模型的测试序列生成优势进行有效的结合。理论和实验分析结果显示了此方法的有效性。 展开更多

关键词 协议一致性测试 扩展有限状态自动机(EFSM) 有限状态自动机(FSM) 测试序列生成 模型转换

在线阅读 下载PDF 职称材料

基于中国邮路算法及UIO序列的状态机测试序列生成

13

作者 赵明 张毅坤 张保卫 《计算机工程与应用》 CSCD 北大核心 2004年第17期58-60,共3页

状态测试的首要问题就是从大量的状态组合中挑选针对典型的错误能够最为有效和最为优化的测试序列。A.V.Aho等人提出了使用中国邮路算法及UIO序列进行生成测试序列的方法,但并没有考虑UIO序列的加入对状态迁移造成的影响,因此不能够对... 状态测试的首要问题就是从大量的状态组合中挑选针对典型的错误能够最为有效和最为优化的测试序列。A.V.Aho等人提出了使用中国邮路算法及UIO序列进行生成测试序列的方法,但并没有考虑UIO序列的加入对状态迁移造成的影响,因此不能够对测试序列进行全局优化。该文对上述算法进行改进,并使用遗传算法解决了中国邮路NP-Complete问题。 展开更多

关键词 状态测试 中国邮路算法 唯一输入输出序列 扩展有限状态自动机 遗传算法

在线阅读 下载PDF 职称材料

基于SPIN的模块化模型检测方法研究 被引量：9

14

作者 李兴锋 张新常 +1 位作者 杨美红 阎保平 《电子与信息学报》 EI CSCD 北大核心 2011年第4期902-907,共6页

该文针对模型检测过程中所存在的状态爆炸问题,提出了一种基于模型检测工具SPIN的模块化模型检测方法。所提出的方法能够将指定的抽象模型分解成若干的模块,并对这些验证复杂度相对低的模块执行模型检测,以替代对原模型的模型检测。所... 该文针对模型检测过程中所存在的状态爆炸问题,提出了一种基于模型检测工具SPIN的模块化模型检测方法。所提出的方法能够将指定的抽象模型分解成若干的模块,并对这些验证复杂度相对低的模块执行模型检测,以替代对原模型的模型检测。所提方法所用的分解过程保留了原模型所有的语义,同时不增加额外的语义,从而使得验证所有模块等同于验证原模型。理论和实验分析结果显示了所提方法的有效性。 展开更多

关键词 模型检测 扩展有限状态自动机 状态爆炸

在线阅读 下载PDF 职称材料