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.     

基于多字符DFA的高速正则表达式匹配算法

基于确定性有限自动机(DFA)的传统正则表达式匹配方法存在单周期处理单字符的速度瓶颈。为提升处理速率,提出一种单周期处理多字符的匹配算法MC-DFA,该算法基于DFA实现,支持匹配位置的精确定位。MC-DFA将传统DFA中的单字符跳转合并为多字符跳转,实现了单周期处理多个输入字符。通过状态转移矩阵二阶压缩算法,MC-DFA分别对矩阵行内以及行间冗余进行消除,减少了内存使用。300条规则下,单周期处理8字符时,MC-DFA吞吐率能够达到7.88Gb/s,内存占用小于6MB,预处理时间为19.24s。实验结果表明,MC-DFA能够有效提升系统吞吐率,并且保证内存占用在可接受范围之内,性能优于现有正则表达式匹配算法。     

一种新的DFA状态最小化算法

提出了一种基于状态转换矩阵的适合计算机实现的DFA状态最小化算法,在计算等价状态过程中,通过记录扫描过程中发现的具有相同输入字符和相同转换状态的状态判定链表,算法可以用一遍扫描和与传统算法相近的存储空间实现DFA状态的最小化。与传统的DFA状态最小化算法相比,该算法具有较好的时间复杂度和相同的空间复杂度。     

DPI带宽管理技术的研究与应用

DPI检测技术是一种基于应用层的流量检测和控制技术,它能深入检查信息包流,准确地识别网络的业务类型,并通过特征库的匹配,有效识别P2P应用。DPI应用识别技术使网络运行变得透明,实现网络的智能化管理,保证网络资源的合理分配。     

DFA最小化算法研究

本文指出了现有DFA最小化算法的缺陷,并给出使用这些算法对DFA限制条件以及将不满足限制条件DFA等价转换成满足限制条件的DFA一般方法;在研究状态等价的充分条件基础上,提出了一种新的适用任何DFA的最小化算法及其算法的正确性证明。     

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

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

Optimized memory based accelerator for scalable pattern matching

One of the most promising techniques to detect and thwart a network attack in a network intrusion detection system is to compare each incoming packet with pre-defined attack patterns. This comparison can be performed by a pattern matching engine which has several key requirements including scalability to line rates of network traffic and easy updating of new attack patterns. Memory-based deterministic finite automata meet these requirements, however their storage requirement will grow exponentially with the number of patterns which makes it impractical for implementation. In this paper, we propose a customized memory-based pattern matching engine, whose storage requirement linearly increases with the number of patterns. The basic idea is to allocate one memory slot for each state instead of each edge of the deterministic finite automaton. To demonstrate this idea, we have developed two customized memory decoders. We evaluate them by comparing with a traditional approach in terms of programmability and resource requirements. We also examine their effectiveness for different optimized deterministic finite automata. Experimental results are presented to demonstrate the validity of our proposed approach.     

DFA模型及其语言的结构化代数规约

本文首先阐述了利用ＤＦＡ模型技术进行状态转换系统描述存在的主要问题,提出了利用代数规约技术解决这些问题的可行性,然后介绍了新一代具有松散语义的代数规约语言ＳＰＥＣＴＲＵＭ及其主要规约操作符的语法和语义,并根据ＤＦＡ模型及其语言的数学定义,给出了它们的结构化代数规约,为基于ＤＦＡ模型的状态转换系统的形式化设计和开发奠定了基础。     

一种深度包检测引擎的FPGA硬件实现

针对硬件防火墙的防护性能优势,提出一种基于FPGA实现的硬件防火墙,利用FPGA设计深度包检测引擎,实现基于应用层的内容防护。深度包检测引擎支持固定、浮动和统一资源定位符关键词匹配,可实现灵活的表项宽度变化和表项更新操作。实际测试表明,采用基于FPGA设计的深度包检测引擎,硬件防火墙的主要处理指标满足实用性要求。     

The design and development of an automated DFA system

This paper presents the design and development of an automated system to assist with Design for Assembly (DFA) analysis. The system is designed to accept information on alternative assemblies using DFA metaphors. Statistics are calculated for these assemblies so as to evaluate their assemblability. The alternative assemblies and improvements in any assembly design are evaluated using these statistics.

A binary tree data structure is used in the DFA system to represent the design data. This structure is implemented by a linked method with three links in each tree node. This allows any arbitrary tree to be represented efficiently, and it also allows for unpredictable tree growth and easy tree manipulation. The user interface of the DFA system is managed by the “User Interface Management System”, that achieves direct and fast control of the screen by directly accessing the video memory.     

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

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

基于模板有限自动机的正则表达式匹配算法

采用规则分组的办法解决DFA状态爆炸问题,随着规则数目的增加,空间压缩效率大大降低。针对此问题,提出了模板有限自动机分组算法,基于规则模板对规则集进行分组,各分组分别构建匹配引擎。同时,根据实际规则数目和系统结构对规则子集的数目改变,达到更好的匹配效率。理论分析和实验表明,与传统分组算法相比,在存储空间压缩相当情况下,分组数目大大减少;与其他典型的DFA改进算法相比,预处理时间和存储空间有数量级别的缩减,且匹配速率没有明显降低。     

A Speculative Parallel DFA Membership Test for Multicore,SIMD and Cloud Computing Environments

We present techniques to parallelize membership tests for Deterministic Finite Automata (DFAs). Our method searches arbitrary regular expressions by matching multiple bytes in parallel using speculation. We partition the input string into chunks, match chunks in parallel, and combine the matching results. Our parallel matching algorithm exploits structural DFA properties to minimize the speculative overhead. Unlike previous approaches, our speculation is failure-free, i.e., (1) sequential semantics are maintained, and (2) speed-downs are avoided altogether. On architectures with a SIMD gather-operation for indexed memory loads, our matching operation is fully vectorized. The proposed load-balancing scheme uses an off-line profiling step to determine the matching capacity of each participating processor. Based on matching capacities, DFA matches are load-balanced on inhomogeneous parallel architectures such as cloud computing environments. We evaluated our speculative DFA membership test for a representative set of benchmarks from the Perl-compatible Regular Expression (PCRE) library and the PROSITE protein database. Evaluation was conducted on a 4 CPU (40 cores) shared-memory node of the Intel Academic Program Manycore Testing Lab (Intel MTL), on the Intel AVX2 SDE simulator for 8-way fully vectorized SIMD execution, and on a 20-node (288 cores) cluster on the Amazon EC2 computing cloud. Obtained speedups are on the order of $\mathcal O \left( 1+\frac{|P|-1}{|Q|\cdot \gamma }\right) $ , where $|P|$ denotes the number of processors or SIMD units, $|Q|$ denotes the number of DFA states, and $0<\gamma \le 1$ represents a statically computed DFA property. For all observed cases, we found that $0.02<\gamma <0.47$ . Actual speedups range from 2.3 $\times $ to 38.8 $\times $ for up to 512 DFA states for PCRE, and between 1.3 $\times $ and 19.9 $\times $ for up to 1,288 DFA states for PROSITE on a 40-core MTL node. Speedups on the EC2 computing cloud range from 5.0 $\times $ to 65.8 $\times $ for PCRE, and from 5.0 $\times $ to 138.5 $\times $ for PROSITE. Speedups of our C-based DFA matcher over the Perl-based ScanProsite scan tool range from 559.3 $\times $ to 15079.7 $\times $ on a 40-core MTL node. We show the scalability of our approach for input-sizes of up to 10 GB.     

维吾尔语名词构形词缀有限状态自动机的构造

该文主要阐述维吾尔语词干提取中使用的名词构形词缀分析DFA的构造过程。维吾尔语属于黏着语,所以维吾尔语自然语言处理系统必须实现词干提取。词干提取的主要任务从单词提取词干和连接词干词尾的构形词缀。维吾尔语单词的构形词缀按照一定的规则连接到词干词尾,这使得维吾尔语构形词缀的连接规则可用有限状态自动机形式化描述。该文首先介绍维吾尔语名词的形态结构,然后根据规则构造从右向左的有限状态自动机,最后对这个自动机进行方向翻转和转换确定自动机操作。     

运用差分演化算法实现多维包匹配的研究

互联网的发展已经使网速的瓶颈由链路速度转移到核心网络设备的包处理速度上,而包处理的核心工作是包匹配。传统方法难以做到包匹配速度适应核心网络设备数据包线速转发。提出了一种新的包匹配算法,该算法对差分演化算法进行了改进,并结合了改进算法和传统的包匹配算法。在适应值处理上运用统计学方法,从而增加了分析问题的客观性。数值实验表明,新算法与传统算法相比,在速度、存储空间以及更新时间等性能上得到了有效改善,另外新算法的包匹配的时间性能与规则数目只有很弱的相关性,从而适合处理多维和大规模问题。新算法把演化算法运用于多域大规模规则库的网络数据包的转发,并且数据包还能做到线速转发。新算法具有普适性,适用于防火墙、差别服务路由器等网络设备。     

基于正则表达式的应用层协议识别加速

在当今网络中,传统的采用端口进行协议识别已越来越无法满足需求.采用了正则表达式进行协议识别,并对其匹配正确性和速度进行了优化.通过将NFA匹配引擎转换为DFA匹配引擎,不仅减少了其状态数,还提高了匹配的速度;在匹配方式上提出了3种匹配方式,并加以测试比较,并与One-Pass扫描算法相结合.通过对DARPA数据集进行测试,验证加速后的匹配正确性比L7-filter高,匹配速度则可达到其6.5倍.     

一种用于深度报文检测的DFA状态表压缩方法

基于正则表达式进行深度报文检测在IDS/IPS、应用层协议识别等网络应用中具有重要作用。然而,采用DFA实现正则表达式需要大量的存储空间,限制了它的实际应用。将DFA状态转换表拆分成3个表,使用run-length编码进行压缩,并对压缩方法进行了优化。采用l7-filter中几个常用应用程序的正则表达式进行测试,结果表明该方法压缩效果一般在90%以上。     

一种虚拟化深度包检测部署机制

网络功能虚拟化转变了网络架构和网络业务的部署。在网络功能虚拟化架构中,实现虚拟化深度包检测只需在传输路径上进行一次扫描,但高效部署深度包检测功能引擎成为难题。将深度包检测功能部署问题形式化为线性规划问题以满足约束条件,并提出一种基于代价最小的贪婪算法和优化的贪婪算法来解决深度包检测功能部署问题。该算法对部署代价和网络资源代价进行折衷,实现了最小化的部署代价。实验结果表明,所提算法能够实现深度包检测功能部署并取得近似最优解。     

基于DoLFA的高效正则表达式匹配算法

随着规则数量的急剧增长,表示正则表达式的DFA(Deterministic Finite Automata,确定型有限自动机)容易引起状态空间爆炸,难以满足高速网络的实时处理需求。提出一种高效的正则表达式匹配算法,该算法通过将正则表达式分割为精确串、字符集合以及重复字符3个子集,分别对其进行分区优化及检测,然后再利用结点信息对匹配信号进行连接,即构建一种特殊的状态机DoLFA(Divide-optimize-Link Finite Automata)。理论分析和仿真结果表明,该算法可以大大节省存储空间,并获得较高的吞吐量,且具有较强的扩展性。     

面向高效深度包检测的启发式正则表达式分组算法*

经过对正则表达式合并DFA状态爆炸问题的分析,采用正则表达式两两合并DFA的状态增加数之和衡量多个正则表达式合并后真实的状态增加情况,将正则表达式最优分组问题归约为带权无向图的k-最大割问题。在此基础上,提出一种面向高效深度包检测的启发式正则表达式分组算法REG-EDPI。采用贪婪策略构造初始解,引入移除参数进行迭代优化。实验表明相比于其他算法,REG-EDPI算法能够在合理的运行时间内,获得更优的分组策略,具有更强的实际应用价值。