一种用于深度包检测的正则表达式分组算法

当前深度包检测算法通常需要将正则表达式转换为NFA或者DFA．但是随着网络带宽的不断增加．NFA和DFA状态占用的存储空间越来越大,极大地考验着系统的存储能力。为了应对这个问题．提出一种基于正则表达式相性的分组算法来对表达式进行分组,实验证明该算法能减少NFA和DFA状态的数量,提高匹配的效率。     

基于改进正则表达式规则分组的内网行为审计方案

针对网络安全审计中对应用层协议审计能力不足的问题,提出一种基于改进正则表达式（RE）规则分组的内网行为审计方案。首先,通过正则表达式对需审计的协议进行描述,并设置相关参数,使内网中出现频率高和审计中相对重要的协议状态在正则表达式描述集中取得高优先级;然后,在正则表达式交互值小的前提下,尽可能地将高优先级协议状态表达式构建到相同自动机分组中以生成审计引擎;最后,根据审计需求,改变相关参数,实现对内网行为的安全审计。实验结果显示,所提出的自动机构建算法在转化时的状态数缩减为经典非确定有限状态自动机（NFA）转化算法Thompson的10%~20%,检测时的吞吐量约为传统自动机分组引擎的8到12倍;所提审计方案能够满足对应用层协议进行安全审计的需求,具有较高的准确性和效率。     

A sequential regression based algorithm for estimating sinusoids in white noise

This paper presents a new algorithm for recursive implementation of Pisarenko's harmonic retrieval method of estimating the parameters of sinusoidal signals in additive noise. The spectral estimation performance of this algorithm is compared with that of least squares type (LST) and Thompson's algorithms. A new measure of performance called the resolution factor is proposed and used in comparing the three algorithms.     

基于LazyDFA的XPath在XML数据流上查询优化算法

针对XML数据流上XPath查询处理及查询优化问题,给出了一种基于lazyDFA技术的解决方案,并提出了优化算法。共享NFA状态表,通过将NFA中的状态分成共享和独享两个状态集来降低lazyDFA的内存使用量;建立状态转移表优化算法通过在lazyDFA状态结构中增加一个状态转移表,来提高lazyDFA的查询速度。实验结果表明,提出的方法能够在执行效率和空间代价方面优于传统算法。     

New Techniques for Regular Expression Searching

We present two new techniques for regular expression searching and use them to derive faster practical algorithms. Based on the specific properties of Glushkov’s nondeterministic finite automaton construction algorithm, we show how to encode a deterministic finite automaton (DFA) using O(m2^m) bits, where m is the number of characters, excluding operator symbols, in the regular expression. This compares favorably against the worst case of O(m2^m|Σ|) bits needed by a classical DFA representation (where Σ is the alphabet) and O(m2^2m) bits needed by the Wu and Manber approach implemented in Agrep. We also present a new way to search for regular expressions, which is able to skip text characters. The idea is to determine the minimum length ℓ of a string matching the regular expression, manipulate the original automaton so that it recognizes all the reverse prefixes of length up to ℓ of the strings originally accepted, and use it to skip text characters as done for exact string matching in previous work. We combine these techniques into two algorithms, one able and one unable to skip text characters. The algorithms are simple to implement, and our experiments show that they permit fast searching for regular expressions, normally faster than any existing algorithm.     

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.     

Optimising unicode regular expression evaluation with previews

The jsre regular expression library was designed to provide fast matching of complex expressions over large input streams using user‐selectable character encodings. An established design approach was used: a simulated non‐deterministic automaton (NFA) implemented as a virtual machine, avoiding exponential cost functions in either space or time. A deterministic automaton (DFA) was chosen as a general dispatching mechanism for Unicode character classes, and this also provided the opportunity to use compact DFAs in various optimization strategies. The result was the development of a regular expression Preview which provides a summary of all the matches possible from a given point in a regular expression in a form that can be implemented as a compact DFA and can be used to further improve the performance of the standard NFA simulation algorithm. This paper formally defines a preview and describes and evaluates several optimizations using this construct. They provide significant speed improvements accrued from fast scanning of anchor positions, avoiding retesting of repeated strings in unanchored searches and efficient searching of multiple alternate expressions which in the case of keyword searching has a time complexity which is logarithmic in the number of words to be searched. Copyright © 2016 John Wiley & Sons, Ltd.     

Glushkov Construction For Series: The Non Commutative Case

We present an extension to multiplicities of a classical algorithm for computing a boolean automaton from a regular expression. The Glushkov construction computes an automaton with n +1 states from a regular expression with n occurences of letters. We give an extension of the Glushkov algorithm for the multiplicity case in a non commutative semiring. Next, we give four equivalent extended step by step algorithms.     

Mergible states in large NFA

Quite often, trivial problems stated for deterministic finite automata (DFA) are surprisingly difficult for the non-deterministic case (NFA). In any non-minimal DFA for a given regular language, we can find two equivalent states which can be “merged” without changing the accepted language. This is not the case for NFA, where we can have non-minimal automata with no “mergible” states. In this paper, we prove a very basic result for NFA, that for a given regular language, any NFA of size greater than a computable constant must contain mergible states. Even more, we parameterized this constant in order to guarantee groups of an arbitrary number of mergible states.     

正则表达式分组的1/(1-1/k)-近似算法

对正则表达式集合进行分组是解决DFA状态膨胀问题的一种重要方法.已有的分组算法大都是启发式的或蛮力的,分组效果很差.分析了DFA状态膨胀的原因,总结了某些正则表达式间的冲突状况.证明了当冲突非负和冲突独立时,正则表达式集合的最优k分组问题可归结为最大k割问题,从而说明该问题是NP-Hard的.基于局部搜索的思想,提出了一种分组算法GRELS来解决分组问题,并证明对最大k割问题,该算法的近似比是1/(1-1/k)与已有的分组算法相比,当分组数目相同时,GRELS算法分组结果的状态总数最少,并且集合发生变化时所需的更新时间最短.     

Memory-efficient algorithms for the verification of temporal properties

This article addresses the problem of designing memory-efficient algorithms for the verification of temporal properties of finite-state programs. Both the programs and their desired temporal properties are modeled as automata on infinite words (Büchi automata). Verification is then reduced to checking the emptiness of the automaton resulting from the product of the program and the property. This problem is usually solved by computing the strongly connected components of the graph representing the product automaton. Here, we present algorithms that solve the emptiness problem without explicitly constructing the strongly connected components of the product graph. By allowing the algorithms to err with some probability, we can implement them with a randomly accessed memory of size O(n) bits, where n is the number of states of the graph, instead of O(n log n) bits that the presently known algorithms require.     

A study of one class of NLP problems arising in parametric semi-infinite programming

The paper deals with a nonlinear programming (NLP) problem that depends on a finite number of integers (parameters). This problem has a special form, and arises as an auxiliary problem in study of solutions' properties of parametric semi-infinite programming (SIP) problems with finitely representable compact index sets. Therefore, it is important to provide a deep study of this NLP problem and its properties w.r.t. the values of the parameters. We are especially interested in the case when optimal solutions of the NLP problem satisfy certain properties due to some specific requirements arising in parametric SIP. We establish the values of the parameters for which optimal solutions of the corresponding NLP problem fulfil the needed properties, and suggest an algorithm that determines the right values of the parameters. An example is proposed to illustrate the application of the algorithm.     

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.     

Stability and persistent disturbance attenuation properties for a class of networked control systems: switched system approach

In this paper, both the asymptotic stability and l ^∞ persistent disturbance attenuation issues are investigated for a class of networked control systems (NCSs) under bounded uncertain access delay and packet dropout effects. The basic idea is to formulate such NCSs as discrete-time switched systems with arbitrary switching. Then the NCSs' stability and performance problems can be reduced to the corresponding problems of such switched systems. The asymptotic stability problem is considered first, and a necessary and sufficient condition is derived for the NCSs' asymptotic stability based on robust stability techniques. Secondly, the NCSs' l ^∞ persistent disturbance attenuation properties are studied and an algorithm is introduced to calculate the l ^∞ induced gain of the NCSs. The decidability issue of the algorithm is also discussed. A network controlled integrator system is used throughout the paper for illustration.     

Deciding unique decodability of bigram counts via finite automata

We revisit the problem of deciding by means of a finite automaton whether a string is uniquely decodable from its bigram counts. An efficient algorithm for constructing a polynomial-size Nondeterministic Finite Automaton (NFA) that decides unique decodability is given. This NFA may be simulated efficiently in time and space. Conversely, we show that the minimum deterministic finite automaton for deciding unique decodability has exponentially many states in alphabet size, and compute the correct order of magnitude of the exponent.     

一种基于彩色编码技术的基序发现算法

从DNA序列中发现基序是生物计算中的一个重要问题,序列条数K=20包含基序用例的序列条数k=16的(l,d)-(K-k)问题(记作(l,d)-(20-16)问题)是目前生物学家十分关注的基序发现问题.针对该问题提出了一种基于彩色编码技术的SDA(sample-driven algorithm)搜索算法--彩色编码基序搜索算法(color coding motif finding algorithm,简称CCMF算法).它利用彩色编码技术将该问题转化为(l,d)-(16-16)问题,再采用分治算法和分支定界法来求解.在解决将(l,d)-(20-16)问题转化为(l,d)-(16-16)问题时,CCMF算法利用彩色编码技术将4 845个组合降低到403个着色,这将极大地提高算法的整体运行效率.使用模拟数据和生物数据进行测试的结果表明,CCMF算法能够快速发现所有(l,d)-(20-16)问题的基序模型和基序用例,具有优于其他算法的综合性能评价,能够用于真实的基序发现问题.同时,通过修改着色方案,CCMF算法可以用于求解一般的(l,d)-(K-k)问题,其中,k＜K.     

Practical methods for constructing suffix trees

Sequence datasets are ubiquitous in modern life-science applications, and querying sequences is a common and critical operation in many of these applications. The suffix tree is a versatile data structure that can be used to evaluate a wide variety of queries on sequence datasets, including evaluating exact and approximate string matches, and finding repeat patterns. However, methods for constructing suffix trees are often very time-consuming, especially for suffix trees that are large and do not fit in the available main memory. Even when the suffix tree fits in memory, it turns out that the processor cache behavior of theoretically optimal suffix tree construction methods is poor, resulting in poor performance. Currently, there are a large number of algorithms for constructing suffix trees, but the practical tradeoffs in using these algorithms for different scenarios are not well characterized. In this paper, we explore suffix tree construction algorithms over a wide spectrum of data sources and sizes. First, we show that on modern processors, a cache-efficient algorithm with O(n²) worst-case complexity outperforms popular linear time algorithms like Ukkonen and McCreight, even for in-memory construction. For larger datasets, the disk I/O requirement quickly becomes the bottleneck in each algorithm's performance. To address this problem, we describe two approaches. First, we present a buffer management strategy for the O(n²) algorithm. The resulting new algorithm, which we call “Top Down Disk-based” (TDD), scales to sizes much larger than have been previously described in literature. This approach far outperforms the best known disk-based construction methods. Second, we present a new disk-based suffix tree construction algorithm that is based on a sort-merge paradigm, and show that for constructing very large suffix trees with very little resources, this algorithm is more efficient than TDD.     

On the Influence of Lookahead in Competitive Paging Algorithms

We introduce a new model of lookahead for on-line paging algorithms and study several algorithms using this model. A paging algorithm is n-line with strong lookahead l if it sees the present request and a sequence of future requests that contains l pairwise distinct pages. We show that strong lookahead has practical as well as theoretical importance and improves the competitive factors of on-line paging algorithms. This is the first model of lookahead having such properties. In addition to lower bounds we present a number of deterministic and randomized on-line paging algorithms with strong lookahead which are optimal or nearly optimal. Received April 8, 1994; revised May 15, 1995.     

Improving the bit-parallel NFA of Baeza-Yates and Navarro for approximate string matching

We propose a new variant of the bit-parallel NFA of Baeza-Yates and Navarro (BPD) for approximate string matching [R. Baeza-Yates, G. Navarro, Faster approximate string matching, Algorithmica 23 (1999) 127-158]. BPD is one of the most practical approximate string matching algorithms under moderate pattern lengths and error levels [G. Myers, A fast bit-vector algorithm for approximate string matching based on dynamic programming, J. ACM 46 (3) 1989 395-415; G. Navarro, M. Raffinot, Flexible Pattern Matching in Strings—Practical On-line Search Algorithms for Texts and Biological Sequences, Cambridge University Press, Cambridge, UK, 2002]. Given a length-m pattern and an error threshold k, the original BPD requires (m−k)(k+2) bits of space to represent an NFA with (m−k)(k+1) states. In this paper we remove redundancy from the original NFA representation. Our variant requires (m−k)(k+1) bits of space, which is optimal in the sense that exactly one bit per state is used. The space efficiency is achieved by using an alternative, but equally or even more efficient, simulation algorithm for the bit-parallel NFA. We also present experimental results to compare our modified NFA against the original BPD and its main competitors. Our new variant is more efficient than the original BPD, and it hence takes over/extends the role of the original BPD as one of the most practical approximate string matching algorithms under moderate values of k and m.