基于有限状态自动机的复合事件监测模型

通过对复合事件的自动机检测模型的研究，给出了构造事件表达式的自动机模型的完整过程。其中的关键步骤：从复合事件到NFA，从NFA到DFA都进行了详细的说明。在NFA向DFA转换过程中给出了子集构造算法、状态最小化算法。     

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

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

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

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

基于多维有限自动机的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个数量级。     

新颖的正则NFA引擎构造方法

提出了一种新颖的正则NFA引擎构造方法——PFA构造法。PFA构造法包括3个主要算法：预处理算法、解析树编码算法和基于编码树的NFA构造算法。采用PFA构造法能够构造出只含有一个开始状态和一个终止状态的规模更小的NFA,称其为NFAp。NFAp的规模与正则表达式组的长度线性相关,较Thompson自动机、后跟自动机、位置自动机以及部分派生自动机的规模都要小,是Thompson NFA的1/3,比已经接近最优的后跟自动机构造法所获得的NFA还要小。     

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

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

基于规则模板的正则表达式分组算法

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

基于确定有穷自动机描述的仿人智能控制记忆

模仿熟练操作者通过记忆多步连续调控系统的方式,将记忆用上下文无关文法表示.根据控制经验和滚动预测优化建立特征状态转换表和构造不确定有穷自动机,给出了转换确定有穷自动机的算法.在任意特征状态下,通过一系列的DFA状态转换函数的复合运算,得到使系统稳定下来的控制模态序列.     

输入可控的二元判定可编程控制器

二元判定自动机是借助于判定方法而不是用布尔逻辑来耱解开关函数的有限状态时序机，二元判定时序机（简称BDMs）在高速可编程控制器中的应用十分重要。因为BDMs的有效工作速度远远超过了普通微机处理器的有效工作速度。本文首次论了BDM求解时序函数的能力，以前研究者所定义的BDM表明，从自动机的理论上讲它的求解能力不如确定性有限状态自动机（简称DFA）的能力强，然而，用输入控制对BDM扩展之后表明其求解能力与DFA等效，这样BDM就可以用于完成有限状态时序函数的计算，本文旨在根据所期望的情况时空复杂性分析用BDM有限状态自动机取代较普通的自动机模型，同时阐述了由此分析所得出的硬件设计方法，并讨论编程方法。     

上下文无关文法与无限状态自动机

目前，在研究上下文无关语言时常用的形式系统是上下文无关文法和下推自动机，在研究正则语言时常用的形式系统是正则文法和有限状态自动机。正则文法中的符号和有限状态自动机的符号之间的对应关系比较明显，因此，两种系统之间的转换比较容易，并且在这两种系统中观察语言时，可以得到一致的解释。     

一种压缩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”.     

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

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

Optimizing Timed Cosimulation by Hybrid Synchronization

In this paper, we present an approach to improving the performance of timed cosimulation. Our approach applies optimistic simulation concept to timed cosimulation for the reduction of synchronization overhead. It consists of (1) a predictive method for the synchronization between optimistic and synchronous simulators and (2) a method for the reduction of the state saving overhead inherent in optimistic simulation. To reduce the synchronization overhead, the predictive synchronization method predicts the time point when the next event is transferred between hardware and software. They the optimistic simulator runs optimistically until the predicted time point. Because of prediction and optimistic simulation, it is possible for the optimistic simulator to roll back and re-execute. To support rollbacks during optimistic simulation, states of the simulator are stored at checkpoints. In optimistic simulation, state saving can cause significant overhead in run-time and memory usage. For the reduction of state saving overhead, we perform state saving on a task basis, which enables saving only the state of currently running task without saving the whole state of the simulator at each checkpoint. Especially, single checkpoint property for hardware tasks enables minimizing the number of state savings in hardware simulation. We demonstrate the efficiency of the presented approach through cosimulation of two embedded system design examples.     

面向数据传输稳定性的无人机群频谱接入方法

针对频繁变化的无线通信环境中无人机群频谱资源使用问题,在保障无人机数据传输稳定的前提下,以降低无人机间用频冲突率、提升信道利用率和系统吞吐量为目标,设计了基于多用户非耦合排队频谱接入方法。该方法中无人机之间不需要信息交互和中心控制节点,仅需根据自身数据传输需求、互扰功率和历史信道使用状态信息来构建学习效益函数,生成频谱使用策略。仿真结果表明,所提方法在确保无人机数据传输稳定和兼顾无人机用频公平性的前提下,能有效降低无人机间用频冲突,提升无人机群吞吐量。