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

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

基于硬件的快速正则表达式匹配方法

网络应用中基于正则表达式特殊模式识别技术是比较新颖的一门学科。基于NFA的方法速率较慢，而基于DFA的执行算法会耗费大量的存储空间。文中提出一种分组模式处理方法，将序列庞大的正则表达式编译为少量的DFA，然后利用多核处理器来并行地处理分组模式，在不明显增加内存耗费的情形之下增加了正则表达式的匹配速率。     

基于正则表达式的通用应用层协议解析技术

面对当前网络的复杂性和异构性,设计了一种基于正则表达式的通用应用层协议解析方案。为满足应用层协议解析的实时性,采用基于DFA的正则表达式匹配引擎,并利用DFA分组算法,避免了DFA状态数的指数级增长。实验表明此方案具有较高的实时性和正确率。     

基于状态约束的大规模正则表达式匹配算法

通过观察不确定有限自动机NFA到确定性有限自动机DFA的转化过程,分析内存增长的原因,提出了一种基于状态间约束关系的正则表达式匹配算法Group2-DFA。Group2-DFA通过两级分组,利用状态间的约束关系,将原始NFA转化为NFA和DFA的混合结构。实验表明,在保持一定处理速率的前提下,Group2-DFA能够有效地减少内存占用。在300条规则下,Group2-DFA吞吐率能够达到1Gbps,并且减少约75%的状态数。     

改进的空间协议识别算法

提出了一种适合空间协议识别的改进BM算法。首先给出了一种基于比特距离的空间数据预处理算法,增大字符集数量,并通过引入小数跳进机制,提高BM算法协议分组头匹配效率;然后应用正则表达式进行协议识别,利用层次关系法提高多层空间协议识别效率;最后对提出的算法进行了复杂度分析和实验验证。结果表明:对于识别模式串长度为m的单层协议,算法时间复杂度可降低到BM算法的(1+m/4)/m,对多层协议识别效率可提高2.5倍;同时,与BM算法相比,提出的算法可有效解决模式串长度不足与存在大量不确定数据的问题,在数据量较大情况下具有更高的识别效率,且所形成的分组可有效抑制正则表达式DFA匹配引擎状态膨胀。     

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

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

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

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

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

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

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

基于FPGA的正则表达式匹配引擎设计

为了提高硬件正则表达式匹配引擎的吞吐率和状态信息存储效率,设计了一种可以多字节并行处理的正则表达式匹配结构,引入了"失效状态"的概念,并且结合Bloom Filter的思想,对状态机进行了过滤和分类匹配。最后在FPGA上进行了验证和测试,结果表明,该匹配引擎有效节约了状态信息存储所需的空间,提高了正则表达式的匹配速率。     

一种压缩DFA的高效FPGA实现

目前,面向网络流实时处理的正则表达式匹配技术面临两方面的挑战:一方面,复杂或大规模规则集会导致DFA存储空间爆炸的问题;另一方面,传统计算机的串行DFA匹配技术很难满足对高速主干网的线速深度包检测。本文提出了一个基于改进游程编码的DFA压缩算法,并在FPGA上高效实现了该压缩DFA的匹配引擎。测试结果表明规则集的单个DFA的吞吐率均大于800Mbps,在FPGA块内存最大利用率情况下的理论最大吞吐率达到49.5Gbps。     

一种无匹配时间损耗的DFA压缩算法的研究与实现

高性能深度包检测系统使用确定型有穷自动机DFA（Deterministic Finite Automata）来执行数据包的检测过程.然而,DFA所带来的存储消耗问题使其难以适用于片内资源稀缺的FPGA.目前已存在多种算法着眼于解决DFA的空间爆炸问题,但是其在带来较好压缩率的同时,也在一定程度上影响到了系统的检测速度.本文提出了一种无匹配时间损耗的DFA压缩算法,并在此基础上,基于FPGA硬件平台,设计实现了单个DFA匹配引擎.实验测试结果表明,本文所设计的算法,在未影响整个系统匹配性能的前提下,可以实现10%~30%左右的压缩率.     

基于混沌理论与改进回声状态网络的网络流量多步预测

网络流量预测是网络管理及网络拥塞控制的重要问题,针对该问题提出一种基于混沌理论与改进回声状态网络的网络流量预测方法。首先利用0-1混沌测试法与最大Lyapunov指数法对不同时间尺度下的网络流量样本数据进行分析,确定网络流量在不同时间尺度下都具有混沌特性。将相空间重构技术引入网络流量预测,通过C-C方法确定延迟时间,G-P算法确定嵌入维数。对网络流量时间序列进行相空间重构之后,利用一种改进的回声状态网络进行网络流量的多步预测。提出一种改进的和声搜索优化算法对回声状态网络的相关参数进行优化以提高预测精度。利用网络流量的公共数据集以及实际数据进行了仿真,结果表明,提出的预测方法具有更高的预测精度以及更小的预测误差。