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

An Efficient Algorithm and Its Implementation Architecture for Network Intrusion Detection

摘要:

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

Abstract:

In order to realize the exact string matching in the network intrusion detection system, a string matching algorithm based on leaf-appended and binary search tree and its architecture is proposed in this paper. Firstly, the leaf-appended algorithm is used to process the given pattern set to eliminate the overlap between the patterns. Then the binary search tree algorithm is used to extract the leaf patterns and their matching vectors to construct the binary search tree. According to the comparison results of each node, the exact matching of strings is achieved through left traversal or right traversal. In order to further improve the memory efficiency of string matching algorithm, a cascaded binary search tree is presented. Finally, the overall architecture and the architecture of each functional module are given to realize exact string matching. Experimental results show that the proposed design is not only superior to the current advanced design techniques in terms of memory efficiency and throughput, but also has flexible scalability.