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

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

用于网络入侵检测的模式匹配新方法

针对新一代网络入侵检测系统(NIDS)的创建需要先进的模式匹配引擎,提出一种模式匹配的新方案,利用基于硬件的可编程状态机技术(B-FSM)来实现确定性处理过程。该技术可以在一个输入流中同时获取大量模式,并高效地映射成转换规则。通过对网络入侵检测系统中普遍采用的规则集(Snort)进行实验,实验结果表明该方法具有存储高效、执行速度快、动态可更新等特点,可以满足NIDS的需要。     

面向涉密检查系统的基于KMP思想的多模式匹配算法

模式匹配算法是涉密检查系统搜索引擎中的主要算法。在分析比较常用模式匹配算法基础上,提出了一种基于KMP算法跳跃思想的多模式匹配算法。该算法可兼容多模式匹配情况和单模式匹配情况,引入多维数组存储模式集并对模式集进行简单排序处理以简化后续操作,引入棋盘表记录各模式串的最大跳跃距离及模式串间跳跃距离。实验结果表明,该算法易于实现,并能有效提高匹配速度,对海量数据检索,有较好的时间和空间性能。     

一种并行中英文混合多模式匹配算法

针对中英文混合文本的匹配准确性及大规模数据文本的匹配效率等问题,基于经典的线索化完全哈希特里树算法,提出一种并行化的中英文混合多模式文本匹配算法。采用拆分文本降低多模式匹配算法的串行度,进而在拆分出的小文本上并行地执行文本匹配。通过并行化预处理过程,设计新的存储结构。实验结果表明,该算法在保证结果正确的前提下,执行效率高于经典的串行匹配算法,当数据规模达到226个字符时,可以获得8倍以上的加速比。     

一种基于子串识别的多模式串匹配算法

多模式串匹配算法是网络内容过滤系统的核心技术。巨大的存储空间开销是制约多模式匹配串算法应用的瓶颈之一。提出一种基于子串识别的多模式匹配算法—HashBOM,该算法利用位哈希表存储模式串的子串信息以大幅度减少存储空间,利用递归哈希函数计算字符串的哈希值以实现快速匹配。理论分析表明,该算法的空间复杂度为O(rm~2),优于基于子串识别的匹配算法BOM的空间复杂度O(mr|∑|log_2mr);该算法搜索匹配过程的平均时间复杂度为O(nlog|∑|)mr/m,与BOM算法相同(其中m为最短模式串的长度,r为模式串的个数,n为待匹配文本的长度,|∑|为字母表的大小)。在随机数据集和真实数据集上的实验表明,该算法的存储空间远远低于BOM算法,而匹配速度与BOM算法相当,非常适合在线实时匹配的应用环境。     

入侵检测系统中模式匹配算法的研究

入侵检测是网络安全的最后一道防线,模式匹配算法是基于特征匹配的入侵检测系统中的核心算法,模式匹配的效率决定这类入侵检测系统的性能.本文对入侵检测系统中的模式匹配算法进行了综述,包括经典的单模式匹配算法--KMP算法、BM算法、RK算法和多模式匹配AC算法.对各种算法的性能进行了分析.最后提出了改进模式匹配算法效率的研究方向.     

一种基于编码关联的快速多模式匹配算法

多模式匹配算法经常使用有限自动状态机来实现多个模式串的并行匹配。针对基于自动状态机的多模式匹配算法在应用于中文编码时存在的存储空间膨胀问题,使用中文字符的拆分编码构造自动状态机,以优化算法自动状态机的存储空间,并利用中文编码的编码关联性,设计了一种基于编码关联跳转的失效跳转表,使用启发式跳跃规则提升匹配算法的时间性能。最后通过实验证明,中文编码环境下,相比于其它使用自动状态机的多模式匹配算法,改良算法拥有更小的空间消耗与更快的运行速度。     

多模式匹配算法的优化研究

模式匹配技术有着广泛的应用且模式匹配算法已经被研究了很多年,同时对稀疏存储及其结构的操作也有大量的文献资料。本文首先描述了Aho-Corasick多模式匹配算法,该算法是基于自动机及状态向量的,然后提出了使用banded-row稀疏存储对Aho-Corasick算法中的状态转换表进行存储优化的观点,给出了优化算法。最后给出了和原Aho-Corasick算法相比较的测试结果,该结果表明在大模式集的情况下,使用banded-row稀疏存储的Aho-Corasick算法减少了存储需求,进一步地提高了性能。     

改进的模式匹配算法在入侵检测中的应用

随着网络技术的高速发展,网络安全问题日益突出,入侵检测技术成为当今关注的焦点。模式匹配算法的性能对入侵检测系统影．响很大。在分析现有模式区配算法的基础上,提出了改进的AC_BM算法,该算法在文本与模式某次匹配失败后,跳过尽可能多的字符,实现更快的匹配过程。实验证明,改进后的算法大大提高了检测的性能。     

一种基于数据挖掘的Deep Web模式匹配方法

模式匹配是Deep Web异构信息集成中的关键问题.介绍了一种整体性匹配方法,即同时发现大量模式,并一次性进行匹配.主要通过分析和比较两种已经存在的大规模模式匹配原型系统:MGS和DCM,结合它们核心算法的优点,提出一种新的基于数据挖掘技术的算法(Correlated-clustering).该算法先利用积极相关发现组匹配,再通过概念相似度的计算聚类同义属性,最后进行匹配选择.实验结果表明,本算法全面、效率高,充分体现了整体性方法的思想.     

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     

A platform-based SoC design and implementation of scalable automaton matching for deep packet inspection

String matching plays a central role in packet inspection applications such as intrusion detection, anti-virus, anti-spam and Web filtering. Since they are computation and memory intensive, software matching algorithms are insufficient to meet the high-speed performance. Thus, offloading packet inspection to a dedicated hardware seems inevitable. This paper presents a scalable automaton matching (SAM) coprocessor that uses Aho-Corasick (AC) algorithm with two parallel acceleration techniques, root-indexing and pre-hashing. The root-indexing can match multiple bytes in one single matching, and the pre-hashing can be used to avoid bitmap AC matching which is a cycle-consuming operation. In the platform-based SoC implementation of the Xilinx ML310 FPGA, the proposed hardware architecture can achieve almost 10.7 Gbps and support over 10,000 patterns for virus, which is the largest pattern set from among the existing works. On the average, the performance of SAM is 7.65 times faster than the original bitmap AC. Furthermore, SAM is feasible for either internal or external memory architecture. The internal memory architecture provides high performance, while the external memory architecture provides high scalability in term of the number of patterns.     

基于存储改进的分区并行关联规则挖掘算法

针对现有算法存储结构简单、生成大量冗余的候选集、时间和空间复杂度高,挖掘效率不理想的情况,为了进一步提高关联规则算法挖掘频繁集的速度,优化算法的执行性能,提出基于内存结构改进的关联规则挖掘算法。该算法基于Spark分布式框架,分区并行挖掘出频繁集,提出在挖掘过程中利用布隆过滤器进行项目存储,并对事务集和候选集进行精简化操作,进而达到优化挖掘频繁集的速度、节省计算资源的目的。算法在占用较少内存的条件下,相比于YAFIM和MR-Apriori算法,在挖掘频繁集效率上有明显的提升,不但能较好地提升挖掘速度,降低内存的压力,而且具有很好的可扩展性,使得算法可以应用到更大规模的数据集和集群,从而达到优化算法性能的目的。     

一种基于可排序视图的RDF模式匹配算法

随着语义网络中数据量的激增,在RDF数据集中高效查询数据已成为一个亟待解决的问题。传统的基于物化视图的RDF模式匹配方法虽然能降低表的自连接操作次数,加快查询模式重写过程,但在视图集中检索模式匹配的视图等价于子图同构这一NP-hard问题。为了减小查询模式重写代价,提高RDF模式匹配过程效率,引入可排序视图概念,设计包含映射发现算法contain及其扩展算法contain+,简化等长度模式间包含映射发现过程,同时保证模式间的匹配代价与输入数据的规模线性相关。此外,提出基于倒排表/MapReduce检索候选可排序视图的方法,实现RDF模式重写算法rewrite,用以处理不同规模数据集上的模式匹配问题。理论分析及实验证明,基于可排序视图的RDF模式匹配算法能有效地兼顾算法效率及算法可扩展性。     

A new paradigm for real-time parallel storage and recognition of patterns based on a hierarchical organization of associative memories utilizing Walsh function encoding

A new hierarchical Walsh memory which can store and quickly recognize any number of patterns is proposed. A Walsh function based associative memory was found to be capable of storing and recognizing patterns in parallel via purely a software algorithmic technique (namely, without resorting to parallel hardware) while the memory itself only takes a single pattern space of computer memory, due to the Walsh encoding of each pattern. This type of distributed associative memory lends itself to high speed pattern recognition and has been reported earlier in a single memory version. In this paper, the single memory concept has first been extended to a parallel memory module and then to a tree-shaped hierarchy of these parallel modules that are capable of storing and recognizing any number of patterns for practical large scale data applications exemplified by image and speech recognition. The memory hierarchy was built by successively applying k-means clustering to the training data set. In the proposed architecture, the clustered data subsets are stored respectively into a parallel memory module where the module allocation is optimized using the genetic algorithm to realize a minimal implementation of the memory structure. The system can recognize all the training patterns with 100% accuracy and further, can also generalize on similar data. In order to demonstrate its efficacy with large scale real world data, we stored and recognized over 500 faces while at same time, achieving much reduced recognition time and storage space than template matching.     

基于动态默认转移的深度包检测算法

由于基于确定性有限自动机（DFA）的多模式匹配算法对内存的需求比较大,因此需要对DFA进行优化,以减少其对内存的需求量。算法通过用动态默认转移来替代DFA的failto转移,将DFA中大量的failto转移删掉,从而达到优化DFA的目的。实验结果证明,该算法能有效地优化DFA对内存的需求。     

A caving degree based flake arrangement approach for the container loading problem

A caving degree based flake arrangement (CDFA) approach for the NP-hard container loading problem is presented in this paper. Based on the caving degree approach, CDFA binds items in the same size into a larger flake whose binding number is 1 in one of its three dimensions, and then it tries to pack the flake into a corner nearest to the eight vertices of the container. Then, caving degree is redefined to evaluate different placements of flakes, such that an action is selected whose packing flake is as compact and close as possible with other flakes already in (the six surfaces of the container can be regarded as six special flakes). CDFA is extensively tested over two sets of famous benchmarks: 15 LN instances and 1500 BR instances. Experimental results show the high performance of this new approach. Especially for the LN set, CDFA improved current highest volume utilization by 1.3% and 0.5% for two difficult instances LN2 and LN6 respectively; at the same time it got optimal layouts for the other 13 instances, equalling current best records. This breaks current best record created and held by Bortfeldt and Gehring since 1998. Besides, CDFA achieved the second highest average volume utilization among several top efficient algorithms for the BR set.     

一种实现网络入侵检测的高效算法及其实现架构

为了实现网络入侵检测系统中的精确字符串匹配,本文提出了一种基于叶子-附加和二叉搜索树的字符串匹配算法及其实现架构;首先采用叶子-追加算法来对给定的模式集进行处理,以消除模式之间的重叠。然后采用二叉搜索树算法提取叶子模式及其匹配向量来构建二叉搜索树,并根据每个节点的比较结果,通过左遍历或右遍历来实现字符串的精确匹配;为了进一步提高字符串匹配算法的内存效率,提出了级联二叉搜索树;最后給出了实现精确字符串匹配的总体架构和各个功能模块的架构;实验结果表明,本文提出的设计不仅在内存效率和吞吐量方面优于目前先进的设计技术,而且具有灵活的可扩展性。     

基于压缩式改进迷宫算法的同构子电路提取

提出了一种用于集成电路逆向工程的高性能子电路识别算法。在搜索匹配过程中,采用改进的迷宫算法对电路中有效节点进行遍历,解决了实际电路中出现的缓冲器问题;采用压缩式存储方法,大大降低了算法的空间复杂度,可支持超大规模的集成电路。该算法将最终的结果以通用的EDIF文件格式输出,实现与Cadence等主流EDA工具无缝衔接。该算法已应用于实际工程项目中,可显著提高分析整理集成电路的工作效率。     

多模式匹配算法的优化研究

模式匹配技术有着广泛的应用且模式匹配算法已经被研究了很多年，同时对稀疏存储及其结构的操作也有大量的文献资料。本文首先描述了Aho—Corasiek多模式匹配算法，该算法是基于自动机及状态向量的，然后提出了使用banded—row稀疏存储对Aho—Corasick算法中的状态转换表进行存储优化的观点，给出了优化算法。最后给出了和原Aho—Corasick算法相比较的测试结果，该结果表明在大模式集的情况下，使用banded—row稀疏存储的Aho—Corasick算法减少了存储需求，进一步地提高了性能。