一种基于深度报文检测的FSM状态表压缩技术

针对深度报文检测中正则表达式模式匹配的状态表爆炸问题,提出并实现了一种集合交割的预编码方法(SI-precode),在正则表达式转换成DFA前对所有输入符号进行预编码,通过压缩输入,减少FSM中输入符号的种类,从而压缩状态转移表的空间.证明了预编码生成的状态机的正确性及其与原状态机的同态性.采用L7-filter模式进行实验表明SI-precode不仅提高了正则表达式的编译速度,针对单模式状态机,其状态转移表空间比不进行预编码压缩了87%～97%,50个模式的多模式状态机可压缩59%.预编码在软硬件结合体系结构下进行协议识别时不会对性能造成影响;对纯软件结构性能降低2%～4%.     

Temporal determinization of mutating finite automata: Reconstructing or restructuring

A mutating finite automaton (MFA) is a nondeterministic finite automaton (NFA) that changes its morphology over discrete time by a sequence of mutations. This results in a sequence of NFAs, the initial NFA, and one mutated NFA for each mutation. Some application domains, including model-based diagnosis of discrete-event systems in artificial intelligence and model-based testing in software engineering, require temporal determinization of MFAs. Determinizing an MFA temporally means generating a deterministic finite automaton (DFA) that is equivalent to the mutated NFA as soon as a mutation occurs. Since, in computation time, the classical Subset Construction determinization algorithm may be less than optimal when applied to MFAs, a conservative algorithm is proposed, called Subset Restructuring, which, instead of constructing the new DFA from scratch based on the mutated NFA, generates the new DFA by updating the previous DFA based on the mutation occurred. Subset Restructuring is sound and complete, thereby yielding the same DFA generated by Subset Construction. Results from massive experimentation indicate the viability of Subset Restructuring, especially so when large MFAs change by small mutations.     

A memory-based NFA regular expression match engine for signature-based intrusion detection

Signature-based intrusion detection is required to inspect network traffic at wire-speed. Matching packet payloads against patterns specified with regular expression is a computation intensive task. Hence, the design of hardware accelerator to speed up regular expression matching has been an active research area. A systematic approach to detect regular expression is based on finite automaton. The space-time trade-off between deterministic finite automaton (DFA) and non-deterministic finite automaton (NFA) is well-known. DFA can offer constant throughput but it may suffer from the state explosion problem. Hence, implementation of DFA for large pattern sets on embedded device with limited on-chip memory may not be viable. NFA requires linear space but the throughput can be very low. Implementations of NFA with hardwired circuits can overcome the speed deficiency by exploiting the massive parallelism offered by dedicated hardware circuitries, but this approach does not support efficient dynamic updates. In this paper, we shall present a memory-based architecture for the implementation of NFA to speed up regular expression matching for signature-based intrusion detection. The proposed method supports dynamic updates and offers constant throughput so that it can be used to supplement the existing DFA-based methods in handling large pattern sets.     

Minimized Thompson NFA

The problem of converting a regular expression to nondeterministic finite automaton (NFA) is a fundamental problem that has been well studied. However, the two basic construction algorithms: (1) Thompson, (2) McNaughton–Yamada and Glushkov, both have disadvantages. In this article: first, a ‘smart’ parsing algorithm is developed which constructs a parse tree with at most (3l???1) nodes form a regular expression with l literals; second, we propose an algorithm that works on the resulting NFA from Thompson's construction, eliminating as many auxiliary states as possible while maintaining Thompson's properties. It is shown that the resulting NFA is minimized. This means that no auxiliary states can be eliminated without violating the defining properties of Thompson NFA. The time and space requirements for the above algorithms are linear with respect to the length of the regular expression.     

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

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

Compact and fast algorithms for safe regular expression search

This article describes an improvement of the brute force determinization algorithm in the case of homogeneous nondeterministic finite automata (NFAs), as well as its application to pattern matching. Brute force determinization with limited memory may provide a partially determinized automaton, but its bounded complexity makes it a safe procedure contrary to the classical subset construction. Actually, our algorithm is inspired by both recent results of Champarnaud concerning the subset automaton of a homogeneous NFA and the algorithm recently designed by Navarro and Raffinot to implement the brute force determinization of the Glushkov NFA of a regular pattern. Our algorithm significantly improves Navarro–Raffinot's one since it has an average exponentially smaller memory requirement for a given level of determinization, which, considering a bounded memory, implies a quadratically smaller parsing time. This algorithm has been implemented in CCP software (http://www.univ-rouen.fr/LIFAR/aia/ccp.html). Tests have been carried out in the field of text processing and biology. Experimental results are reported.     

Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition

This paper investigates the transition function and the reachability conditions of finite automata by using a semitensor product of matrices, which is a new powerful matrix analysis tool. The states and input symbols are first expressed in vector forms, then the transition function is described in an algebraic form. Using this algebraic representation, a sufficient and necessary condition of the reachability of any two states is proposed, based on which an algorithm is developed for discovering all the paths from one state to another. Furthermore, a mechanism is established to recognize the language acceptable by a finite automaton. Finally, illustrative examples show that the results/algorithms presented in this paper are suitable for both deterministic finite automata (DFA) and nondeterministic finite automata (NFA).     

Sofic Tree-Shifts

We introduce the notion of sofic tree-shifts which corresponds to symbolic dynamical systems of infinite ranked trees accepted by finite tree automata. We show that, contrary to shifts of infinite sequences, there is no unique reduced deterministic irreducible tree automaton accepting an irreducible sofic tree-shift, but that there is a unique synchronized one, called the Fischer automaton of the tree-shift. We define the notion of almost of finite type tree-shift which are sofic tree-shifts accepted by a tree automaton which is both deterministic and co-deterministic with a finite delay. It is a meaningful intermediate dynamical class in between irreducible finite type tree-shifts and irreducible sofic tree-shifts. We characterize the Fischer automaton of an almost of finite type tree-shift and we design an algorithm to check whether a sofic tree-shift is almost of finite type. We prove that the Fischer automaton is a topological conjugacy invariant of the underlying irreducible sofic tree-shift.     

一种改进的区域自动机构造方法

用时间自动机验证一个有穷状态实时系统的正确性，可归结为判定两个时间正则语言的包含问题，亦可归结为判定两个时间正则语言的交是否为空的问题。在判定一个时间正则语言是否为空时，先要将时间自动机转化为无时间的区域自动机。Alur和Dill给出的构造区域自动机的算法，存在许多不可达或虽可达但无用的状态。通过对时钟约束进行分析，在求时钟区域和时间后继的过程中，不断地将一些不可达或无用状态筛掉，使构造出的区域自动机更为优化，改进了Alur等人给出的算法。     

Amounts of nondeterminism in finite automata

Summary The amount of nondeterminism in a nondeterministic finite automaton (NFA) is measured by counting the minimal number of guessing points a string w has to pass through on its way to an accepting state. NFA's with more nondeterminism can achieve greater savings in the number of states over their deterministic counterparts than NFA's with less nondeterminism. On the other hand, for some nontrivial infinite regular languages a deterministic finite automaton (DFA) can already be quite succinct in the sense that NFA's need as many states (and even context-free grammars need as many nonterminals) as the minimal DFA has states.This research was supported in part by the National Science Foundation under Grant No. MCS 76-10076     

基于行为自动机的构件可替换性分析与验证

在交互协议层面讨论构件的可替换性,采用非确定性有限状态自动机(nondeterministic finite automata,简称NFA)来建模构件的交互行为,在保证交互兼容性的前提下,提出了按构件环境的透明度和构件交互的变化度两维划分的可替换性模型,给出了4类可替换性的形式化定义及其之间的关系,并基于NFA理论给出了相关的验证算法。另外,该模型以构件的替换行为而不是其全部行为作为构件替换的参照,从而使替换时有更多的候选构件可供使用,提高了构件复用的几率。     

The cartesian composition of automata

There are several known ways to define a product automaton on the cartesian product of the state sets of two given automata. This paper introduces a new product called the cartesian composition and discusses how various properties of the product automaton depend on the corresponding properties of the factors. A main result is that any finite connected automaton has a unique representation as a cartesian composition of prime automata.     

A characterization of s-languages

We show that a language L is an s-language if and only if the set of the quotients of L (i.e., the set of the states of its minimal deterministic automaton seen as languages) is a subset of a free monoid generated by a finite set of prefix codes. We demonstrate through examples how to use this result for deciding whether a given language is an s-language.     

A state space approach to the finite automata

This paper proposes a state space approach for analyzing the finite automata. A Ψ-representation transforms a set of words into a formal power series for establishing the state equation of a finite automaton. We investigate the structure of the automaton via its corresponding state equation. It is shown that the solution of the state equation always exists and is unique. Furthermore, we prove that the solution field is a separable algebraic extension of the coefficient field. Finally, the concept of the substitution property of a partition is shown to be equivalent to that of invariant subspaces of the associated state space.     

When does abstraction help?

Abstraction is a leading technique for coping with large state spaces. Abstraction over-approximates the transitions of the original system or the automaton that models it and may introduce nondeterminism. In applications where determinism is essential, we say that an abstraction function is helpful if, after determining and minimizing the abstract automaton, we end up with fewer states than the original automaton. We show that abstraction functions are not always helpful; in fact, they may introduce an exponential blow-up. We study the problem of deciding whether a given abstraction function is helpful for a given deterministic automaton and show that it is PSPACE-complete.     

A Special Case of a Unary Regular Language Containment

Given an n-state unary finite automaton accepting a language T, and an ultimately periodic set S given as a union of arithmetic progressions that can be represented using n^O(1) bits, and whose periods are mutually coprime, deciding whether T ⫅ S is in n^{O(log n)} time. Dropping the mutual coprimality condition, this containment problem becomes NP-hard.     

基于层次自动机模型的复杂事件层次实现研究

复杂事件处理技术从数据流中提取满足特定模式的事件序列,具有实时、海量、智能的特点,近年来引起了学术界和商业界的广泛关注。但是,之前的工作侧重于对单层复杂事件检测的研究。事实上,由于业务系统对信息有不同层次的需求,需要对事件进行分层处理,单层复杂事件检测并不能充分支持事件分层的需求。针对这种情况,在事件层次概念以及传统NFA模型的基础上,定义了分层复杂事件检测模型层次自动机NHA,基于NHA模型设计了更为直观高效的EH-Tree结构,并给出了分层复杂事件检测HCED算法和代价模型。最后以吞吐量和内存占用为指标,进行了大量的实验,对比并分析了HCED算法与传统基于NFA模型的SASE算法的时间性能和空间性能。实验结果表明,HCED算法能有效且高效地实现分层复杂事件检测,填补了CEP不支持分层复杂事件检测的空白,为下一步研究提供了基础。