基于网络处理器的高效中英文多模式匹配算法

由于中英文字符在编码方面的差异，传统面向英文字符环境的多模式匹配算法无法直接应用于中英文字符混合环境。提出了一种适用于网络处理器和中英文混合环境的高效多模式匹配算法。该算法采用从左向右的正向匹配，以字节为最小匹配单位，以字符为最小移位单位，在Trie树结构基础上，利用块字符匹配降低逐字匹配的概率，结合Quick Search(QS)算法进行跳跃加速。实验表明，算法能够在中英文混合环境下避免字节错位和误匹配，匹配速度优于已有算法，且不存在空间膨胀问题，能够满足高速网络信息审计的要求。     

面向新型业务的多维快速包分类算法研究*

网络中新兴的新型业务例如P2P,VoIP,Worm等日益增多,在整个网络流量中占有越来越多的比重。对这些新型业务的监测和控制要求路由器等核心设备必须有能力对数据包进行快速和准确的分类。本文从这些新型业务包分类规则库的特点着手,提出在多维多模式匹配情况下的三种包分类决策树,通过实验说明这些决策树应用在新型业务的包分类上与传统的串行决策树性能各自的差异,进而得出适合新型业务包分类的最佳算法。     

基于Aho-Corasick算法的多模式匹配算法研究*

通过分析模式匹配算法在网络入侵检测中重要作用和所面临的问题,对Aho-Corasick基于自动机的算法和以Aho-Corasick算法为基础的相关算法进行了分析,并通过实验对多种多模式匹配算法进行综合对比,最后对多模式匹配方法的发展趋势进行了展望。     

网络入侵检测系统中基于多核平台的模式匹配技术研究

模式匹配是入侵检测的重要技术手段,利用多核平台加速模式匹配是近年学术研究的热点。本文重点阐述了利用网络处理器和GPU等平台研究加速入侵检测中模式匹配的原理和实现方法,比较分析了在多核环境下加速模式匹配的主要思路和技术特点,总结并提出了安全性、自适应性、可扩展性和系统性等开放性问题。     

基于网络处理器的多维包分类算法

提出一种基于网络处理器并行处理能力的多维快速IP数据包分类算法.首先对包过滤规则库进行有效的预处理,以使对规则的分组能够最大限度地发挥并行算法的优势;在合理分组之后对每一组规则实施相关的三值TRIE树最优编码,这种最优编码形式从根本上消除了在对规则库进行压缩编码时产生的规则扩展问题.算法的最终实现,仅需要对数据包进行一次索引表的哈希查询和一次规则匹配,因此有效提高了包分类运算的效率.     

多模式匹配算法在网络入侵自动检测中的应用

为了可以对计算机网络安全进行有效的保护,同时提高计算机网络入侵检测的功能及其效率,提出多模式匹配算法在网络入侵自动检测中的应用.首先快速检测引擎初始化,快速有效地区别规则集合;其次构造模式匹配链表,读取系统配置文件的规则;最后检测网络数据包,确保计算机网络安全.通过实验结果的对比,可以明显看出,相比于传统算法,多模式匹...     

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

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

基于IXP2400千兆防火墙包分类算法的设计与实现*

针对千兆网下包过滤防火墙,提出了HSBIPG(Hash Search Based on IP Group)包分类算法,并分析了算法的优缺点,基于该算法用IXP2400实现了线速千兆包过滤防火墙,通过实验证明了此算法是可行和高效的。     

Web入侵检测系统高效多模式匹配算法*

针对Web入侵检测系统中存在的攻击模式误匹配与效率问题,提出了一种高效的多模式匹配算法MPMA。MPMA通过构建比较树,并在比较树的每个节点中记录下次比较的字符位置以提高比较效率,并利用（模式,偏移）信息对来搜索可能符合的匹配模式。详细的实验以及与现有算法的比较表明,提出的MPMA不仅适合于Web入侵检测系统,同时在时间、空间和匹配率性能上具有更高的效率。     

Bitmap结构在高性能网络算法设计中的应用

基于Bitmap数据结构的数据压缩技术是一种针对线性存储结构的有效压缩方法,虽被广泛用于网络处理的多个领域(路由查找、网包分类等),却一直缺乏深入的分析。给出了Bitmap结构能提高算法空间性能的理论根据。总结了Bitmap结构在典型网络处理算法中的各种应用,给出了Bitmap结构的数学模型,并通过实例分析了Bitmap结构的优势和不足。Bitmap技术是一种能有效改善网络处理算法存储空间性能的通用技术,并给未来高性能网络处理算法设计提出以及现有算法的改进都提供了启发思路。     

基于模式串匹配的Ethernet协议识别算法研究

协议识别是网络安全与对抗领域中的一项关键技术。简要介绍了网络协议识别的重要性,分析了Ethernet类协议的特征,构建了协议识别的系统模型,依据Ethernet类协议的特征,提出了一种新的基于模式串匹配的协议识别算法NEWMATCH,并对该算法的性能进行了分析,并与传统模式串匹配算法（如：BF、KMP、BM等）进行了比较。该算法在Ethernet类协议识别方面具有一定的适用性。     

A parameterized multilevel pattern matching architecture on FPGAs for network intrusion detection and prevention

Pattern matching is one of the most performance-critical components for the content inspection based applications of network security, such as network intrusion detection and prevention. To keep up with the increasing speed network, this component needs to be accelerated by well designed custom coprocessor. This paper presents a parameterized multilevel pattern matching architecture (MPM) which is used on FPGAs. To achieve less chip area, the architecture is designed based on the idea of selected character decoding (SCD) and multilevel method which are analyzed in detail. This paper also proposes an MPM generator that can generate RTL-level codes of MPM by giving a pattern set and predefined parameters. With the generator, the efficient MPM architecture can be generated and embedded to a total hardware solution. The third contribution is a mathematical model and formula to estimate the chip area for each MPM before it is generated, which is useful for choosing the proper type of FPGAs. One example MPM architecture is implemented by giving 1785 patterns of Snort on Xilinx Virtex 2 Pro FPGA. The results show that this MPM can achieve 4.3 Gbps throughput with 5 stages of pipelines and 0.22 slices per character, about one half chip area of the most area-efficient architecture in literature. Other results are given to show that MPM is also efficient for general random pattern sets. The performance of MPM can be scalable near linearly, potential for more than 100 Gbps throughput. Supported by the National Natural Science Foundation of China (Grant No. 60803002), and the Excellent Young Scholars Research Fund of Beijing Institute of Technology     

基于WM算法的多模式匹配改进算法WMN

入侵检测系统中有部分时间用来进行模式匹配,因此提高模式匹配算法的处理速度具有重要的意义。从两个方面改进了目前公认效率较高的多模式匹配算法WM,设计出WMN算法,并对该算法进行了性能测试和分析。实验证明该文提出的WMN算法能够有效提高模式匹配的处理速度。     

改进的基于小枝模式的匹配算法——cTwigStack

给定一个小枝模式查询,如何快速地在XML数据集中找到所有感兴趣的信息,已成为当前研究的热点。针对TwigStack算法在处理含有父子节点的情况下会产生大量的中间结果等问题,通过栈来对非叶子节点缓存和对叶子节点延迟输出的思想,提出了一种改进的小枝模式匹配算法--cTwigStack。采用Treebank数据集进行测验,结果表明该算法不仅仅在处理祖孙/后继节点时能使输出结果的准确性达到最优,而且在处理父子节点时,相对目前提出的算法,也是非常高效的。     

一种改进的BM模式匹配算法

首先介绍了目前最常用的BM模式匹配算法,以及其改进算法Boyer Moore Horspool(BMH)算法,在此基础上提出了另一种改进的BM算法,该算法减少了匹配次数,有效的加快模式匹配的速度。     

基于线模式的指纹细节点匹配算法

提出了一种新的基于线模式的指纹图像细节点匹配算法,这种算法先分别找出最佳匹配点对,确定相对旋转角度,较快地确定两个指纹的相关性,之后再搜索漏的匹配点对,去掉错误的匹配点对。算法受指纹增强、后处理的影响较小,细节点相似程度受其邻域细节点影响较小。介绍了算法的具体实现方法,并用实际指纹数据进行了测试。初步测试的结果表明,此算法是指纹图像细节点匹配的一种有效算法。     

An optimized sequential pattern matching methodology for sequence classification

In this paper we present a novel methodology for sequence classification, based on sequential pattern mining and optimization algorithms. The proposed methodology automatically generates a sequence classification model, based on a two stage process. In the first stage, a sequential pattern mining algorithm is applied to a set of sequences and the sequential patterns are extracted. Then, the score of every pattern with respect to each sequence is calculated using a scoring function and the score of each class under consideration is estimated by summing the specific pattern scores. Each score is updated, multiplied by a weight and the output of the first stage is the classification confusion matrix of the sequences. In the second stage an optimization technique, aims to finding a set of weights which minimize an objective function, defined using the classification confusion matrix. The set of the extracted sequential patterns and the optimal weights of the classes comprise the sequence classification model. Extensive evaluation of the methodology was carried out in the protein classification domain, by varying the number of training and test sequences, the number of patterns and the number of classes. The methodology is compared with other similar sequence classification approaches. The proposed methodology exhibits several advantages, such as automated weight assignment to classes using optimization techniques and knowledge discovery in the domain of application.

网络入侵检测系统模式匹配算法研究

模式匹配算法是网络入侵检测中的关键所在,它直接影响到网络入侵检测系统的实时检测性能.引入4种模式匹配算法,分析其工作原理,通过实验对上述4种算法进行了性能测试.根据实验结果,得出了不同算法的应用范围,为今后入侵检测系统开发者选择模式匹配算法提供了有价值的参考.     

A geometric reasoning based algorithm for point pattern matching

Point pattern matching (PPM) is an important topic in computer vision and pattern recog-nition . It can be widely used in many areas such as image registration, object recognition, motion de-tection, target tracking, autonomous navigation, and pose estimation. This paper discusses the in-complete matching problem of two point sets under Euclidean transformation. According to geometric reasoning, some definitions for matching clique, support point pair, support index set, and support in-dex matrix, etc. are given. Based on the properties and theorems of them, a novel reasoning algo-rithm is presented, which searches for the optimal solution from top to bottom and could find out as many consistent corresponding point pairs as possible. Theoretical analysis and experimental results show that the new algorithm is very effective, and could be, under some conditions, applied to the PPM problem under other kind of transformations.