摘要
字符串匹配是一个在很多信息处理技术中都必须面对的问题，在入侵检测技术中由为突出，而其相关的研究也已经开展了多年，一些经典的算法已经在很多入侵检测系统中得以广泛应用。但现有的一些算法都或多或少地存在某些局限或不足。为此，相关的研究仍在继续。在总结前人经验成果的基础上，本文提出了自己的新的想法，并将新的想法通过算法加以实现，最后通过实验验证了算法的正确性和提高之处。
由于目前没有任何一种字符串匹配算法能够适应各种情况，达到最好、最坏及平均时间复杂度都达到最优，只是理论上存在上述的可能。因此本文提出的算法只是对前人算法的一种改进，让新的算法更适合于多字符串并行查找，以及适应动态地增加模式字符串的情况。具体说来，本文得到如下的成果：
其一：提出一个分割定理，证明了通过非“准匹配”字符可以将大文本分割为若干个用于匹配的小文本。
其二：提出一个采样定理，证明了针对某一模式串，当采样距离小于模式串长度时，我们可以通过抽样检测的方式，发现文本中模式串出现的位置。
其三：实现了一个依据采样定理思想来设计的算法，并通过算法进一步证明了采样定理的正确性。
其四：将这一算法，应用到入侵检测的入侵识别引擎当中，用于规则匹配。并提高了检测引擎的效率。
It is a key issue that many technologies of information have to deal with,especially used in intrusion detection. It has been developed for a lot of years.Now, some classical algorithms have been used widely in many intrusion detectionsystems. But there have been some blemishes in these algorithms. For this reasonresearching in this field is still valuable. This article gets a few newconclusions based on the results of former researchers, and we have made analgorithm according to these new conclusions of this article come true. And,we prove the conclusions to be correct. In the end, we use a great deal of datasto test the new algorithm.
Until now any of strings matching algorithms is not perfect, but people havegot some limits of this kind of algorithm in theroy. So the new algorithm is notperfect but improved on the base of former people. We make the new algorithmmore fit to multi pattern parallel matching. When the new pattern strings hasto add for matching in the same text, this algroithm will give a good show ofits effect.
In fact, this article do four work as blow:
1) We bring a theorem named splitted theorem forward. This theorem show thata text can be splitted into sub_text which is smaller than the text, bynever_appeared_in_patterns characters.
2) We bring a theorem named sampling theorem forward. This theorem show thata text can be matched by samples which could be sampled from the text. To usethis theorem we must prove the length between any two samples is not longer thanthat of the pattern which will be matched.
3) We make the sampling theorem into truth. According to the theorem, wemake an algorithm named sample_algorithm that can be used to strings matching.
4) We use the sample_algorithm into the engine of intrusion detection, andimprove the detection efficiency.
引文
[1] Knuth D E, Morris H, Pratt V R. Fast pattern matching in strings [J]. SIAM J Comp, 1977, 6: 323-350.
[2] Boyer R S, Moore J S. A fast string searching algorithm [J]. Communications of the ACM, 1977, 20: 762-772.
[3] WU Sun, Manber U. A Fast Algorithm for Multi-Pattern Searching [R]. Technical Report TR 94-17, University of Arizona at Tucson, May 1994.
[4] Sunday D M. A very fast substring search algorithm [J]. Communications of the ACM, 1990, 33(8): 132-142
[5] WU Sun, M anber U. A grep—A fast approximate pattern-matching tool[A]. Proc of the USENIX Technical Conference[C]. San Fransisco, CA, 1992. 153-162.
[6] Tuck N, Sherwood T, Calder B, et al. Deterministic memory efficient string matching algorithm s for intrusion detection [A]. Proceedings of IEEE Infocom [C]. Hong Kong, March 2004.
[7] 李洪宇，刘胜辉 基于Snort系统特殊字符串匹配算法的研究[D]哈尔滨：哈尔滨理工大学2005
[8] 刘燕兵，郭莉 串匹配算法优化技术研究[D]北京：中科院计算所2006
[9] 李伟男，鄂跃鹏等 多模式匹配算法及硬件实现[J]北京：软件学报2006
[10] 王成，刘金刚一种改进的字符串匹配算法[J]上海：计算机工程2006
[11] 张胤，贾超 模式匹配型入侵检测系统改进[D] 河北：燕山大学2006
[12] 孙晓山，王强等一种改进的Wu-Manber多模式匹配算法及应用 [J]北京：中文信息学报 2006
[13] 赵丽，孙敏 一种基于高效模式匹配算法的入侵检测系统[D] 山西：山西大学 2005
[14] 张鑫，谭建龙等 一种改进的Wu-Manber多关键词匹配算法[J] 四川：计算机应用 2003