深度包检测中一种正则表达式匹配算法的改进

网络数据包内容检测技术已在网络安全、网络监视、HTTP负载均衡等方面得到广泛的应用,因此,对快速数据包内容的检测就变得异常重要。在数据包内容检测过程中,数据包的净载数据要通过一系列已经定义好的正则表达式模式进行数据匹配。在此,阐述目前数据包检测存在的问题,如传统数据包检测应用程序要求很大的内存空间去存储相应的正则表达式模式,提出一种大大降低对内存空间使用的改进算法。通过将该改进算法应用到以DFA为基础的包检测应用程序中,说明经过真实网络数据来检测算法的改进成果。结果表明了改进算法的有效性。     

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

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

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

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

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

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

基于两级存储的正则表达式匹配技术

为解决正则表达式匹配中内存需求与检测性能的矛盾,首次提出两级存储的匹配方案。将马尔可夫链理论应用于自动机,通过求解稳态向量,得到各状态被随机访问的概率。将高概率的状态表项配置在FPGA嵌入存储器中,低概率的状态表项配置在SRAM中。使用L7-filter规则集进行实验,吞吐量达到33Gbit/s,匹配性能比将状态表完全存储在SRAM中提高了50倍。     

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

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

基于二元组的简单正则表达式的快速检索算法

在大型数据集群网络中,业务逻辑节点和数据库节点分布在不同的地理位置,导致在该网络中创建或检索用户数据将经历较大的网络延迟.如何快速找到用户数据的地理位置节点（服务器识别号）将是减少网络延迟的关键.介绍一种动态索引算法,基于简单正则表达,建立用户数据和服务器组之间的映射关系,并引入动态多叉树,实现动态更改映射关系.引入一元组数据节点和二元组数据节点的概念,应用于多叉树,通过分析一元组多叉树和二元组多叉树的时间效率和空间效率,证明二元组多叉树随着树深的增长,检索时间复杂度保持更好的线性特性.通过一些性能测试的实验数据的比较,得出二元组方案的综合性能更优的结论.最后,简要地介绍该算法的应用领域.     

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

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

基于硬件的虚拟化简化了采用多核处理器的设计

将队列与流量管理卸载给硬件,降低了设计的复杂程度,改进了应用效率,获得了最高性能。今天的SoC(系统单芯片)处理器都集成了一系列的核心、加速器和其它处理单元。这些异质的多核架构提供了更多的计算能力,但其复杂性也为各种应用中嵌入系统的开发人员带来了新的挑战,这些应用包括控制层处理器、视频服务器、无线基     

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

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

一种压缩DFA的高效FPGA实现

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

一种基于智能有限自动机的正则表达式匹配算法

本文提出了一种基于智能有限自动机(Smart Finite Automaton,SFA)的正则表达式匹配算法,在XFA的分支迁移边上增加额外的判断操作指令,消除XFA的回退迁移边,避免不必要的状态迁移操作.实验结果表明,SFA提高了正则表达式匹配的时空效率,与XFA相比,在存储空间开销上减少了44.1％,在存储器访问次数上减少了69.1％.     

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

采用规则分组的方法解决确定型有限自动机(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个数量级。     

基于正则表达式的协议行为审计技术研究

协议行为审计技术通过在线深度解析应用层协议来分析用户行为并进行审计,为人工分析监测网络安全事件提供依据,达到增强网络安全的目的。重点探讨了利用正则表达式进行协议行为解析的技术,并提出一个灵活、可扩展的协议行为审计技术框架。基于该技术框架实现了一个支持HTTP协议、SMB协议和TNS协议的协议行为审计系统,通过详细的实例介绍阐明了利用正则表达式进行协议行为解析技术在该系统中的运用过程。最后,该系统的测试结果验证了基于正则表达式的协议行为审计技术的有效性。     

基于ABNF的高速硬件解码方法的研究

本文提出了一种硬件实现网络协议解码的方法.这种方法采用基于流水线的高速并行字符串匹配结构和基于ABNF(Augmented Backus Naur Form)范式定义的高速域值合法性检查.文中还对用这种方法实现的SIP(Session Initiation Protocol)协议解码器的性能进行了分析,并与软件实现进行了对比.通过比较可以得出,采用本方法所实现的协议解码系统只需要较少的硬件资源就可以得到比传统的软件实现几十倍的性能提高,并显著提高整个系统的吞吐量.