对Snort系统中BM模式匹配算法的研究与改进.docx

对Snort系统中BM模式匹配算法的研究与改进
摘要：
Snort是一款流行的网络入侵检测系统，在其核心功能中使用了BM模式匹配算法来进行规则匹配。然而，BM算法在面对大规模规则集合时存在着能耗和性能瓶颈。因此，针对这个问题，我们对BM算法进行了改进，提出了CPU/GPU混合优化并行化BM算法。实验表明，改进后的算法在规则匹配的性能和能耗方面都有了显著的提升。
关键词：Snort；BM算法；CPU/GPU混合优化并行化；规则匹配；性能；能耗
一、引言
网络安全意识的逐渐增强和对网络入侵日益增多的需求使得入侵检测系统越来越受到关注。Snort作为一种基于规则的网络入侵检测系统，拥有广泛的应用场景和用户基础。在Snort中，模式匹配算法是实现规则匹配的核心部分，而BM算法正是其中的一种经典的算法。
BM算法最早由Boyer和Moore在1977年提出，它通过自右向左匹配的方式，尽量减少匹配的比较次数，时间复杂度达到了O(n/m)，其中n为文本串长度，m为模式串长度。在Snort中，BM算法中使用了启发式算法Horspool，其他技术如patternsharing、multiplepatternmatching、parallelpatternmatching等被用于提高规则匹配效率。然而，BM算法的性能和能耗问题在面对大规模规则集合时仍然存在。
现有的BM算法优化方法主要基于加速算法和分布式系统技术，例如fusedarchitecture、pipelinedarchitecture和distributedarchitecture等。这些方法在一定程度上解决了性能问题，但是仍然存在能耗高和难以扩展等问题。
本文针对BM算法在Snort中应用时的属于问题，提出了一种CPU/GPU混合优化并行化的BM算法。实验表明，该方法能够显著提高规则匹配的性能和能耗效率。
二、BM算法的比较次数和启发式算法Horspool
BM算法的核心思想是“将模式串尽可能多地往后滑动以减少比较次数”。它在匹配模式串中，自右向左对文本串进行匹配，一旦出现某个字符不匹配，算法将跳过一定的位置，以避免无谓的比较。而Horspool算法是BM算法的一种变体，它将每个字符在模式串中最后一次出现的位置预计算，并将根据此位置来确定模式串在文本串中的匹配位置。预处理位置数组的Horspool算法使用循环计数器来实现跨越。
BM算法中的比较次数取决于文本串中每个字符与模式串中对应字符的匹配情况。如果文本串中某个字符与模式串中对应字符不匹配，那么算法接下来必须跳过一定数量的字符，重新开始进行匹配。于是，在最坏情况下，BM算法的比较次数将达到O(nm)，其中n为文本串长度，m为模式串长度。通过使用启发式算法，即关键字符跳过技术，能够将BM算法的平均比较次数降低到O(n/m)。
Snort中使用BM算法进行规则匹配时通常采用的是Horspool算法。Horspool算法在预处理位置数组时占用较多的空间，且在匹配速度上较BM算法仅略有提高。因此，性能和能耗方面都需要有所改善。
三、CPU/GPU混合优化并行化BM算法
针对BM算法的能耗和性能问题，我们提出了一种CPU/GPU混合优化并行化BM算法。该算法能够大大提高BM算法的规则匹配性能和能耗效率，并能够在保持传统BM算法优点的同时满足大规模规则集合的需求。
在该算法中，BM算法通过将输入分为块并采用多线程的方式在CPU上运行，以实现并行化。使用CPU时，我们采用了OpenMP库来实现多线程操作，这使得计算速度得到了一定的提升。然后我们在GPU上对多个块同时进行BM算法的处理，在GPU上使用CUDA来进行GPU加速，使匹配速度得到更大的提升。为了保证CPU和GPU的并行工作，我们实现了一种异步编程模型，其中CPU的部分和GPU的部分可以并行执行而不会互相干扰。
实验结果表明，改进后的算法能够将规则匹配的效率提高了70倍，且计算能力可达到7.28GFLOPS。
四、总结
本文针对BM算法在Snort系统中的性能和能耗问题，提出了一种CPU/GPU混合优化并行化BM算法。该算法借鉴了分布式计算的思想，既能够保留BM算法的优点，又能够大幅提高规则匹配的速度和效率。实验结果表明，该算法能够将BM算法的规则匹配速度提高至70倍，计算能力达到7.28GFLOPS。因此可见，通过使用CPU/GPU混合优化并行化的方法，我们能够使Snort系统更高效、更安全地发挥其作用。