运用时间分类树的确定单时钟时间自动机学习

时间自动机的模型学习算法旨在通过提供输入和观察输出构建软硬件系统的形式化模型.确定性单时钟时间自动机的学习是其中的一个重要研究方向,但是该算法具有一定的局限性,在状态较多时学习速度较慢,很难应用到复杂的系统中.由此,提出了一种改进的学习算法,使用逻辑时间分类树代替逻辑时间观察表作为学习算法的内部数据结构,有效地减少了成员查询次数,降低了算法的空间复杂度,并能够高效率地构建假设自动机.最后进行了相关实验,实验结果表明,提出的改进算法减少了60%左右的成员查询和5%左右的等价查询.同时在该实验中,改进算法的学习速度最高可提高45倍以上.

基于自动机原理的自动售货机软件的实现

利用自动机原理对现有的自动售货机的工作模式进行了分析,指出了自动售货机在购买多种商品时的不方便之处和销售管理上的落后现象,提出了用软件方法对自动售货机工作模式进行优化和扩展,并增强其管理功能,以使自动化销售过程更快捷、准确和有效.

关于有限自动机定义的一个注记

给出了有限自动机的一般定义M=(Q,Σ,R,q0,F),其中R哿(Q×(Σ∪{ε}))×Q,特别地,如果R:Q×Σ→Q,则M是确定性有限自动机,该定义统一描述了确定性有限自动机、非确定性有限自动机、带空转移的非确定性有限自动机与部分自动机的概念。在该定义下,证明了确定性有限自动机与非确定性有限自动机的等价性以及正则语言类关于连接、闭包运算的封闭性,因此该定义在理论上是完备的。

基于自动机原理的钢筋标识串的自动识别

钢筋量的统计是工程预算中的一个重要组成部分。传统的钢筋量统计方法存在效率低、易出错等缺点。而利用计算机自动识别完成钢筋量的统计可以很好解决上述缺点。本文基于形式语言与自动机理论,主要对钢筋标识串的自动识别进行了研究。首先对钢筋标识串给出了递归的定义,并构造出了相应的文法;其次,设计出了一台确定性有限自动机,对钢筋标识串所包含的信息进行自动识别。提高了识别的正确性、有效性,为钢筋量的自动统计提供了有力的基础。

面向维吾尔文的敏感信息过滤方法研究

在这个信息量爆炸性增长的时代,网络不良信息充斥在日常生活当中。为了构建洁净的网络环境,实现对网络维吾尔文中敏感信息的检测与过滤,通过分析维吾尔文的特点,将维吾尔文进行词干提取和编码化处理,再结合DFA和决策树提出了针对维吾尔文敏感信息过滤的相应方法。维吾尔文经过词干提取、编码化处理解决了维吾尔文书写顺序和形式多样、存储易出现乱码等问题。再结合决策树的特点,将转码后的维吾尔文信息存储于决策树节点上,将决策树的子节点按照特定编码进行顺序排列。这样维吾尔文文本信息进行敏感信息过滤时可以缩小检测范围,提高算法效率。

基于正则表达式的深度包检测算法

在深入分析了DFA状态数对算法性能影响的基础上,提出了一种新的基于正则表达式的深度包检测算法,该算法保证在任意有限的系统资源下算法的时间复杂度空间复杂度最小。在Linux下实现了该算法,并对基于L7-filter模式集合的网络数据包进行了大量检测实验。结果表明,与已有的正则表达式算法比较,该算法的时间复杂度和空降复杂度最小。

RFID数据流上多目标复杂事件检测

已有的RFID复杂事件处理技术主要关注于单个RFID对象的复杂事件检测和优化技术.实际上,很多RFID应用中往往需要同时检测多个同类型关联目标的复杂事件序列.研究了多个关联的RFID对象的复杂事件处理问题.通过扩展的事件语言和算子的语义以支持同类型多个RFID目标复杂事件查询的定义.通过模式的变换规则,将RFID应用中存在的各种非线性多目标复杂事件模式转换成线性模式,以便各种多目标模式在一个统一的框架下检测.提出了基于自动机NFAb2的多目标复杂事件检测模型和多目标复杂事件检测算法.通过在多目标检测算法中使用关键节点下压和同位置约束置后优化策略,大大减少了单个类型上无用实例的数目和不同类型间模式匹配的搜索空间.与SASE算法的实验比较表明算法的正确性和高效性.

基于事件驱动模型的集装箱物流信息系统

提出了基于约束规则集的事件驱动模型的概念,以之为基础并结合确定性有穷自动机的理论,建立了整个集装箱物流的工作流程,通过满足约束规则的事件来驱动物流和资金流的状态改变,并给出了系统的一个具体实现方案。

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

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

状态不可观测的信息物理融合系统运行时验证

确保信息物理融合系统(Cyber-Physical System,CPS)运行时行为正确性是至关重要的,尤其在航空航天、汽车、核电和医疗等安全攸关领域.本文针对具有随机行为且状态不可观测的CPS,提出一种基于隐马尔科夫模型的运行时安全性验证方法.首先构造状态不可观测的CPS运行时安全性验证框架,该框架通过隐马尔科夫模型表示系统,使用确定性有限自动机规约系统安全属性的否定,两者的乘积自动机作为运行时监控器,从而将CPS运行时安全性验证问题约简到监控器上的概率推断问题.然后,提出一种增量迭代安全性验证算法以及反例生成算法.实验结果表明本文算法和粒子滤波算法相比预测错误率下降了近20%,并且当系统违背安全属性时,本文的方法能给出反例.

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

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

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

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

对模式匹配算法的存储优化研究

基于确定性有限自动机(DFA)的多模式匹配算法被广泛用于数据包深度检测系统中。它功能虽然强大,但是对内存的需求也比较大,因此很多算法提出了对它的优化方法,以减少对内存的需求量。本文通过用动态默认转移来替代DFA的failto转移,将DFA中大部分的failto转移删掉,从而达到优化DFA的目的。而且本算法易于用硬件实现,因此在对速度有要求的场合,可以通过专门的硬件来计算默认转移,这样默认转移的计算并不会对检测产生延迟,从而加快匹配速度。

采用OBDD实现快速子匹配提取

为提高模式匹配算法中子匹配提取过程的时间效率,采用有序二元决策图(ordered binary decision diagram,OBDD)与布尔函数相结合的方法,完成了与PCRE(perl compatible regular expressions)和谷歌的RE2库的对比实验研究。结果表明:基于OBDD的子匹配算法的性能比PCRE和RE2提高了约一到两个数量级。

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

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

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

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

基于信息量的工控网络异常检测技术

为解决传统工业网络异常检测系统具有误报率高、状态构建不够灵活等问题,提出一种基于信息量的双层确定性有限自动机模型(IDDFA)。引入信息量和时间参数的概念,通过状态之间的信息衰减智能提取实际SCADA网络当中主要状态,在内存操作的粒度上构建一个次级DFA,具备内存操作上的语义分析功能。实验结果表明,该方法在已有的基础上,有效改进了工业控制系统网络当中的异常流量检测。

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

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

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

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

基于载荷特征与统计特征的Shodan流量识别

针对Shodan扫描流量对工业控制系统产生的不安全问题,结合载荷特征与统计特征,构建一种将确定性有限自动机(DFA)与支持向量机(SVM)相结合的流量识别DFA-SVM模型。通过分析应用层的流量特征,以提取协议功能码序列作为载荷特征,并结合传统的流量统计特征对流量进行识别。采用VPS部署6个分布式蜜罐系统对处理后的32522个样本进行Shodan流量识别。实验结果表明,相比仅使用单一特征的模型,该模型可有效识别出27个Shodan扫描器IP,识别精度达到99.38%。