基于FPGA的多模式匹配算法研究与实现

针对模式匹配软件算法速度慢、正确率低等问题,提出一种基于FPGA的硬件多模式匹配算法,通过设计窗口折叠的布鲁姆过滤器,有效减小资源消耗。与多级确认机制结合可降低虚警率,并采用不同于传统方式的并行结构提高查询速度,实现高效率无虚警的精确模式匹配。实验结果表明,采用该算法的高速入侵检测系统吞吐率可达到10 Gb/s。     

基于硬件的定长移位高速浮动关键词匹配算法

针对浮动关键词匹配问题,提出了一种基于TCAM的定长移位匹配算法.该算法通过对移动步长的灵活控制有效降低了存储器的访问频率,提高了系统速率.通过分析空间复杂度,该算法与其它移位加速算法相比,在一定的范围之内对TCAM容量的需求也具有明显的优势.算法性能分析和仿真表明,该算法不仅可以实现任意长度模式的线速搜索,还可以使系统所能支持的模式集规模达到几万条.     

采用集合切分编码的大容量模式匹配算法*

针对现有模式匹配算法无法实现大容量模式集快速搜索的不足,提出了一种基于TCAM多字节状态机的模式匹配算法。利用TCAM的掩码特性,切分具有相同匹配字符串的状态集,提出了一种编号编码压缩机制。通过理论证明,集合切分编码利用状态机的已匹配信息,将编号存储改变为编号段存储,大幅压缩了具有相同转移字符串和目的状态的交叉转移路径,减少TCAM表项数目。经理论分析和实验仿真,该算法不仅具有高搜索速率,而且可以减少大量相似表项,降低TCAM存储资源消耗,从而支持大容量的模式集。     

基于三态内容寻址存储器的多模式匹配算法

传统模式匹配算法在高速环境下无法实现数据包的实时处理。为此,提出一种基于三态内容寻址存储器(TCAM)的快速多模式匹配算法,通过模式移位将长模式截取为若干个子串,第1级TCAM存储子串,第2级TCAM存储子串的序列编号。搜索模式时,第1级TCAM向后端输出命中表项的编号,第2级TCAM实现序列编号的匹配,从而获得长模式的匹配信息,并通过编号空间划分方法压缩表项数目以提高资源利用率。实验结果表明,该算法可以实现网络数据的高速匹配处理,与基于hash标识的移位存储算法相比,具有空间消耗少的优势。     

基于双字符序检测的BM模式匹配改进算法

BM算法是一类效率较高的单模式匹配算法,通常改进的BM算法往往从提高字符首次不匹配概率和匹配窗口的最大移动距离入手,但为实现此目的所带来的高访存开销使算法实际效率受到影响。DCSBM算法以适当减小关键步长为代价,在利用双字符序检测提高首次匹配失败概率的同时,对匹配窗口移动关键步长字符距离所需的查表次数和访存次数进行优化。经测试,DCSBM算法显著提高了匹配窗口的平均移动距离。在文本或模式串相对较长情况下,该算法实际测试效率优于BM、BMHS、BMN等算法。     

基于HASH-TCAM算法的高速模式匹配研究*

针对基于硬件的模式匹配算法处理长模式串时吞吐率不高的问题,提出了基于将哈希压缩与TCAM查表相结合的算法——HASH-TCAM算法。通过哈希算法将待匹配的关键字预处理,减少其长度,解决了40 Gbps线速下的长模式串匹配问题,并通过40 Gbps测试仪验证了该算法的可行性。分析表明,该算法在查询的固定关键字长度为72 Byte,模式集数目为5000,哈希压缩后地址的编码宽度为46 bit时,模式识别模块以牺牲冲突的代价实现了51.2 Gbps的吞吐率,可以满足40 Gbps链路中DPI算法的逐包线速的需求     

Wu_Manber多模式匹配算法的研究与改进

模式匹配算法的性能对入侵检测系统影响很大。该文介绍模式匹配算法的原理,研究多模式匹配算法Wu_Manber及改进方法,提出QMWM方法。该方法利用前缀信息,实现了移动距离的最优,且不增加空间复杂度。实验表明,QMWM在提高效率的同时能够避免空间的额外占用。     

基于并行字符索引的多步长正则表达式匹配算法

深度包检测（deep packet inspection ,DPI）是网络入侵检测与防御系统（network intrusion dete‐ction and prevention system ,NIDPS）的核心．基于三态内容可寻址存储器（ternary content addressable memory ,TCAM ）的正则表达式匹配算法提高了数据包的处理速度,成为DPI技术的一个重要研究方向．TCAM 具有查找速度快、存储空间小等特性,且能耗与存储空间成正比．由于DFA的存储空间开销比较大,且存储空间大小随着DFA步长数的增加而指数倍增,基于TCAM的DFA面临高能耗的问题,特别是多步长DFA ．提出一种基于并行字符索引的多步长正则表达式匹配算法（multi‐stride parallel character‐indexed DFA ,PCIDFA ）,对确定型有限自动机（deterministic finite automaton ,DFA ）构造并行字符索引,通过比特位图取交集,减少匹配时激活的TCAM 块数,显著降低TCAM 能耗．实验结果表明：与多步长DFA相比,多步长PCIDFA在TCAM 能耗上减少了99．8％以上,在 TCAM 存储空间开销上减少了48．5％～65．3％,在吞吐量上提高了1．9～2．6倍．     

基于硬件的乱序报文重组算法

在硬件实现TCP时,TCP协议对接收报文的乱序管理使硬件实现复杂度大为增加。针对该问题,提出一种利于硬件执行的算法,将数据直接基于序列号进行放置,同时进行序列号映射比较。实验结果表明,该算法具有易于实现、执行效率高的优点,使10G接口的TCP数据传输率达到4.64 Gb/s。     

基于网络处理器的多模式串匹配研究

深度数据包检查是网络入侵检测系统的性能瓶颈。该文分析入侵规则集中模式串的分布特点,对多模式匹配算法FNP进行改进,研究在多核多线程体系结构的网络处理器上高效实现模式串匹配的方法。在Intel IXP2800网络处理器上的仿真实验结果表明,改进算法在规模为10 K的模式串集合上能达到6 Gb/s的吞吐量,具有几乎线性的加速比。     

基于TCAM的高效浮动关键词匹配算法

针对传统浮动关键词匹配算法功耗高和速率低的问题,提出一种基于三态内容寻址寄存器(TCAM)的高效匹配算法。该算法应用关键词分类数据结构,将关键词存储在不同的TCAM模块中,并只将疑似关键词送入TCAM中查找匹配,从而减少每次访问TCAM查找的表项数目,提高一个查询周期内待匹配报文的移动速度。仿真结果表明,与传统算法相比,该算法功耗较低、匹配速度较快。     

Power efficient packet classification using cascaded bloom filter and off-the-shelf ternary CAM for WDM networks

In wavelength division multiplexing (WDM) networks, tens or hundreds of wavelengths can be transmitted over a single fiber. As transmission line speed goes to 10 Gb/s and beyond, ternary CAM (TCAM) is usually employed for wire speed packet classification. To the best of authors’ knowledge, this is the first paper that addresses the impact of WDM transmission on the power consumption of packet classification. We show that as the number of wavelengths increases in the WDM networks, the power consumption of TCAMs can become the limiting factor for WDM network expansion. For example, the power consumption of IPv4 and IPv6 packet classification with merely 32 channels at 40 Gb/s can be as high as 700 and 1400 W, respectively, while technology wise it is feasible to transmit over 500 channels over a single fiber. Existing power efficient TCAM designs require special modification to TCAM cell structures, which makes the adoption of the technology difficult. This paper proposes a novel approach which cascades bloom filter with off-the-shelf TCAM to greatly reduce the power consumption of packet classification. In particular, the proposed solution takes advantage of the fact that bloom filters may give false positive alarms but never give false negative alarms. By eliminating majority of non-matching packets before passing the packets to the TCAM, the TCAM is only activated to exam packets with a high potential of matching in the filter set. The proposed scheme greatly reduces the activation frequency of the TCAM, thus achieving great power savings.     

A fast pattern matching algorithm with multi-byte search unit for high-speed network security

A signature-based intrusion detection system identifies intrusions by comparing the data traffic with known signature patterns. In this process, matching of packet strings against signature patterns is the most time-consuming step and dominates the overall system performance. Many signature-based network intrusion detection systems (NIDS), e.g., the Snort, employ one or multiple pattern matching algorithms to detect multiple attack types. So far, many pattern matching algorithms have been proposed. Most of them use single-byte standard unit for search, while a few algorithms such as the Modified Wu-Manber (MWM) algorithm use typically two-byte unit, which guarantees better performance than others even as the number of different signatures increases. Among those algorithms, the MWM algorithm has been known as the fastest pattern matching algorithm when the patterns in a rule set rarely appear in packets. However, the matching time of the MWM algorithm increases as the length of the shortest pattern in a signature group decreases.In this paper, by extending the length of the shortest pattern, we minimize the pattern matching time of the algorithm which uses multi-byte unit. We propose a new pattern matching algorithm called the L⁺¹-MWM algorithm for multi-pattern matching. The proposed algorithm minimizes the performance degradation that is originated from the dependency on the length of the shortest pattern. We show that the L⁺¹-MWM algorithm improves the performance of the MWM algorithm by as much as 20% in average under various lengths of shortest patterns and normal traffic conditions. Moreover, when the length of the shortest pattern in a rule set is less than 5, the L⁺¹-MWM algorithm shows 38.87% enhancement in average. We also conduct experiments on a real campus network and show that 12.48% enhancement is obtained in average. In addition, it is shown that the L⁺¹-MWM algorithm provides a better performance than the MWM algorithm by as much as 25% in average under various numbers of signatures and normal traffic conditions, and 20.12% enhancement in average with real on-line traffic.     

Hash算法在网络处理器中的实现

提出一种应用于网络处理器的Hash算法,通过建立新型查找表的结构和构造两级Hash函数,能够有效地解决Hash冲突的问题。描述Hash表的软件建立流程和硬件查找过程,在Hash查找的基础上,给出硬件表项的学习过程和老化方法,简化表项的更新操作。针对不同的应用,建立不同类型的Hash表,合理地利用内外部存储资源,兼顾了存储资源和处理速度的平衡。实验结果表明,该算法对各种查找表中不同的表项数目和关键词长度均具有较好的兼容性,成功查找的平均长度为2,减少了存储器的访存次数,其单个微引擎的查找速度高达25Mb/s,能够满足网络处理器接口处理带宽20Gb/s的要求。     

一种新型精确深度包检测引擎研究与设计

传统的深度包检测算法通常存在频率带宽瓶颈、不能精确匹配、不切实际的存储要求等其中之一或数个缺点.本文基于哈希与Bloom Filter提出一种新型精确匹配结构:Bloom Filter分类器,首先基于哈希对特征串分组,再用多组Bloom Filter对输入串分类,在每长度定位到唯一可能的匹配串并对比验证.对Snort、ClamAV集合进行了存储实验评估,以约1.22(字节/字符)的低存储代价实现对万条字符串集的精确匹配.该结构具有精确匹配、多字节匹配扩展简单、不存在带宽瓶颈等优点.     

gAC:基于GPU的高性能AC算法

字符串匹配是计算科学中研究最广泛的问题之一,已成为信息检索和生物计算等领域的核心操作。然而受限于CPU的计算能力和存储器访问带宽,传统的串行字符串匹配算法难以进一步提升性能。GPU在计算能力和存储器访问带宽上有很大提升,已经在很多应用上取得了卓越成效。gAC作为一种基于GPU的并行AC算法,针对GPU的SIMT(Single-Instruction Multiple-Thread)以及合并存储器访问的技术特点,采取了减少条件分支、合并访问全局存储器等优化方法,使得在C1060GPU上的字符串扫描速度达到51Gb/s,比基于CPU的串行算法提升了28倍。