一种基于确定型有穷自动机的动物识别系统的设计方法

提出了一种新的动物识别系统的设计方法.通过对有穷自动机理论与动物识别系统进行分析,建立了一个基于动物特征的确定型有穷自动机的模型.该模型描述了当输入一个动物特征值后,自动机的状态将发生转移,当输入的动物特征值充足时,即可识别出动物的种类.最后,根据这种模型设计出了动物识别系统,并上机进行了实现.     

精确学习模型下确定的有穷自动机的学习

利用多态自动机和有穷自动机的关系，根据多态自动机的学习算法，给出了EXACT学习模型下，确定的有穷自动机的学习算法，并对算法复杂度做了分析，说明确定的有穷自动机在EXACT模型下可以在多项式时间内进行学习。这样就可以用软件来模拟确定的有穷自动机的学习。     

动态异构冗余结构的拟态防御自动机模型

动态异构冗余结构是拟态防御技术的常用工程模型.然而,目前尚缺乏对该结构实施形式化分析的手段,因为该结构缺乏形式化建模方法.针对此问题,使用有穷状态自动机及其并行组合自动机为一些拟态攻防行为建立计算模型.首先,使用单个有穷状态自动机为单个执行体建模;其次,使用有穷状态自动机的并行组合为执行体组合建模;再次,修改状态迁移规则,得到可描述攻防行为的拟态防御自动机模型;最后,根据该自动机模型的状态条件,分析动态异构冗余结构上拟态攻防行为的安全性.此外,也可使用交替自动机为拟态攻防建模,并把安全性自动分析规约为交替自动机模型检测问题.     

基于DNA有穷自动机的素性测试法

有穷自动机,一种计算能力极其有限的计算模型,具有解决素性测试的能力通过构造法得到了证明。既而提出了一种基于有穷自动机的测试一个整数是否为素数的DNA算法,并且详细描述了该有穷自动机的构造方法,将有穷自动机的状态用DNA单链分子来编码,而输入则用DNA双链分子编码,用带环的双链DNA分子来编码状态转移规则,通过限制性内切酶的切割实现状态的转移。该算法的创新之处在于它是基于有穷自动机这种计算能力极其有限的计算模型的,并且该算法不仅能判断一个整数是否是素数,还能用于素因子分解。该算法的优点是实验实现容易,所需的时间是输入的多项式函数而不是指数函数。     

以DNA为载体的线性时序逻辑模型检测

线性时序逻辑模型检测被广泛应用于处理器设计与验证、网络协议验证、安全协议验证等领域.然而到目前为止,该技术只能在电子计算的平台上实现.为了以脱氧核糖核酸(Deoxyribo Nucleic Acid,DNA)为载体对线性时序逻辑(Linear Temporal Logic,LTL)实施模型检测,给出了使用粘贴自动机实现Until算子模型检测的方法.首先,使用粘贴自动机对Until公式的有穷状态自动机(Finite State Automata,FSA)模型进行编码;然后,将系统模型转换为粘贴自动机的输入字符串;最后,用粘贴自动机验证系统是否满足公式.仿真实验结果证实,新方法可实现对LTL逻辑时序算子的检测.     

基于启发式SCCs的广义Büchi 自动机判空检测算法

 基于自动机理论模型检测的一个关键算法是判断有穷状态系统是否满足属性的判空检测.对标准Büchi自动机作判空检测,容易引起状态爆炸.本文以TGBA为研究对象,提出基于启发式SCCs的广义Büchi自动机判空检测算法.该算法在on-the-fly算法的基础上结合启发式深度优先搜索和SCCs检测算法,能较快地判断TGBA的非空性.通过正确性证明、复杂性分析和实验验证了该算法的正确可行性.在TGBA非空的情况下,该算法的时空性能比已有算法更优.     

有限状态自动机在复杂界面操作中的应用

为提高程序开发效率和软件稳定性,减轻应用程序在复杂界面操作上的代码量,设计实现了基于有限状态自动机的界面控制器.界面控制器在自动机的基础上引入动作集,通过将界面上的复杂操作抽象为简单的状态和状态转换函数,可实现对界面的复杂操作与逻辑控制,具有建模方便、小巧轻便和简单易用的优点.     

基于PFADS的网络数据获取平台的研究与实现

随着IPv6网络的发展,基于IPv6的网络管理系统亟待开发。针对IPv6与IPv4长期共存的情况,论文提出一个基于并行有穷状态自动机的、双协议栈PFADS的网络信息获取平台。该平台采用有穷状态自动机进行协议还原,同时采用双直达式缓冲区和并行自动机方法,能满足在大规模网络下的信息获取,保证数据获取的实时性与准确性。     

基于UIO序列的类重要性度量

程序理解是测试和维护大规模面向对象程序的关键,选择程序的关键类优先开展分析是理解程序结构的一个有效的方法.为支持自动识别软件系统中的关键类,本文提出了一种基于UIO序列的类重要性度量方法.首先将软件系统抽象为一个以类为转换的有限自动机模型,随后求解该自动机的UIO序列,将该序列集合转化为状态转换树.通过递归计算状态转换树的节点复杂度求得类重要度.并在考虑异常传播的基础上改进了算法.最后通过实验验证了算法的有效性.     

VHDL中的有限状态机教学方法研究

本文以三段式编程框架介绍了VHDL中有限状态机的教学方法,即系统图、状态转换图和编程架构三部分.系统图用以确定系统模块和输入输出的位置,并合理分类强制和常规状态控制信号;状态图用以确定实现系统功能而设计的状态转换过程;基于系统图和状态图,编程架构使用三进程方式.教学过程中以位元检测器的设计为例,通过练习提高了学生对有限状态机的理解和设计能力.     

基于状态约束的大规模正则表达式匹配算法

通过观察不确定有限自动机NFA到确定性有限自动机DFA的转化过程,分析内存增长的原因,提出了一种基于状态间约束关系的正则表达式匹配算法Group2-DFA。Group2-DFA通过两级分组,利用状态间的约束关系,将原始NFA转化为NFA和DFA的混合结构。实验表明,在保持一定处理速率的前提下,Group2-DFA能够有效地减少内存占用。在300条规则下,Group2-DFA吞吐率能够达到1Gbps,并且减少约75%的状态数。     

一种基于FPGA压缩DFA的高速正则表达式匹配算法

正则表达式匹配技术在网络应用中面临两方面的制约,一方面,复杂或大规模规则导致DFA存储空间急剧膨胀,现有的内存容量难以支撑;另一方面,传统计算机架构的DFA处理能力有限,很难满足高速网络流的线速处理需求。因此,提出一种基于FPGA使用改进游程编码压缩DFA的高速正则表达式匹配算法。实现了基于改进游程编码的DFA引擎架构、分组存储与多路并行比较器技术。该算法不仅具有游程编码的压缩效果,而且压缩后的DFA实现一次状态转移只需2个时钟周期。     

基于多维有限自动机的DFA改进算法

多个正则表达式规则编译成一个DFA(deter minister finite automata)时,会产生状态爆炸、存储急剧增加的现象。针对最严重的状态爆炸问题,从信息论的角度给出了解释,并提出多维数学模型,将冗余状态分为0维状态和1维状态,通过前者按照维度压缩,后者动态构建的方法将空间复杂度降到理论下界,并在此基础上提出多维有限自动机(MFA, multi-dimensional finite automata)。实验表明,MFA构造时间比XFA略少,比DFA、STT冗余压缩算法和Hybrid-FA降低了2~3个数量级;存储空间比XFA略高,比DFA、STT冗余压缩算法、mDFA、Hybrid-FA降低了1~2个数量级;匹配时间比DFA、Hybrid-FA略多,但是比XFA略少,比STT冗余压缩算法和mDFA降低了1~2个数量级。     

基于状态分组的高效i-DFA构造技术

正则表达式匹配在很多网络安全领域起着非常重要的作用。确定性有限自动机(DFA,deterministic finiteautomaton)具有线速稳定的匹配性能,因而更适合在高速网络环境下执行正则表达式匹配。但DFA可能由于状态膨胀而占用巨大的内存空间。作为状态膨胀问题的一种经典解决方案,i-DFA在大幅降低内存开销的同时,还能保证最差匹配性能。然而,已有方法构造i-DFA时在时间和空间上都是非常低效的。基于状态分组的思想,提出了一种高效的i-DFA构造方法。进一步地,对状态分组进行了形式化描述,并证明了获得最优状态分组是NP困难的,并基于局部搜索的思想提出了一种近优的状态分组算法。实验结果表明,相比经典的i-DFA构造方法,所做的工作在时间和空间上都有极大的改进:i-DFA的状态规模可能只是已有方法的2/3,而构造i-DFA所用时间仅是已有方法的1/16。     

一种压缩DFA的高效FPGA实现

目前,面向网络流实时处理的正则表达式匹配技术面临两方面的挑战:一方面,复杂或大规模规则集会导致DFA存储空间爆炸的问题;另一方面,传统计算机的串行DFA匹配技术很难满足对高速主干网的线速深度包检测。本文提出了一个基于改进游程编码的DFA压缩算法,并在FPGA上高效实现了该压缩DFA的匹配引擎。测试结果表明规则集的单个DFA的吞吐率均大于800Mbps,在FPGA块内存最大利用率情况下的理论最大吞吐率达到49.5Gbps。     

BSPM： A NEW MECHANISM FOR ＂OVERLAP-MATCHING EXPRESSIONS＂ IN DPI

Nowadays, using Deterministic Finite Automata (DFA) or Non-deterministic Finite Automata (NFA) to parse regular expressions is the most popular way for Deep Packet Inspection (DPI), and the research about DPI focuses on the improvement of DFA to reduce memory. However, most of the existing literature ignores a special kind of “overlap-matching expression”, which causes states explosion and takes quite a large part in the DPI rules. To solve this problem, in this paper a new mechanism is proposed based on bitmap. We start with a simple regular expression to describe “overlap-matching expressions” and state the problem. Then, after calculating the terrible number of exploded states for this kind of expressions, the procedure of Bitmap-based Soft Parallel Mechanism (BSPM) is described. Based on BSPM, we discuss all the different types of “overlap-matching expressions” and give optimization suggestions of them separately. Finally, experiment results prove that BSPM can give an excellent performance on solving the problem stated above, and the optimization suggestions are also effective for the memory reduction on all types of “overlap-matching expressions”.     

基于多维立方体的正则表达式匹配算法

针对特定条件下含有“.*”的正则表达式规则相互作用产生的状态爆炸问题,本文提出一种基于多维立方体的确定性有限自动机（Deterministic Finite Automaton,DFA）结构,将冗余状态按维度划分并压缩,并设计相应的多维立方体确定性有限自动机（Multi-Dimension-Cube-DFA,M-D-Cube-DFA）算法,通过构造动态交点的方法实现等价的状态转移.理论分析和仿真实验表明,与DFA算法相比,在维持时间复杂度不变的基础上对状态数目和存储空间进行了对数级别压缩.     

基于TCAM的低能耗正则表达式匹配算法

提出一种基于字符索引的正则表达式匹配算法,对确定型有限自动机（DFA, deterministic finite automaton）的字母表和状态进行分离存储,构建字符索引,减少匹配时激活的TCAM块数,显著降低TCAM能耗。实验结果表明：与DFA相比,基于字符索引的DFA（CIDFA, character-indexed DFA）在能耗上平均减少了92.7%,在存储空间开销上平均减少了32.0%,在吞吐量上平均提高了57.9%。     

基于正则表达式的通用应用层协议解析技术

面对当前网络的复杂性和异构性,设计了一种基于正则表达式的通用应用层协议解析方案。为满足应用层协议解析的实时性,采用基于DFA的正则表达式匹配引擎,并利用DFA分组算法,避免了DFA状态数的指数级增长。实验表明此方案具有较高的实时性和正确率。