入侵检测系统中字符串匹配算法与实现

摘要

作为网络内容安全检查的重要技术，字符串匹配算法被广泛的应用在入侵检测、入侵保护、网络防病毒和网络内容监控等网络安全系统中。字符串匹配是网络安全系统中对计算资源要求最高的部分，例如在当前的入侵检测系统中字符串匹配占用了百分之五十以上的计算资源。随着网络攻击的手段日益增多，网络安全设备中需要定义的模式字符串数量随之上升，这使得字符串匹配占用网络安全系统计算资源的比例还将增大。另外，从近二十年的发展来看，网络速率的提升速度大约为处理器的处理能力提升速度的3倍。基于处理器的软件字符串匹配技术不能满足网络速率发展的需求。基于专用集成电路的字符串匹配算法能够提供高速的字符串匹配，但是其模式字符串更新比较困难，不能适应安全系统检测规则的频繁更新。 本文使用兼顾了软件的灵活性和专用集成电路速率的FPGA来实现高速的字符串匹配。目前已有很多基于FPGA的字符串匹配研究，但是这些算法还有提高的余地，主要体现在如下几个方面：1）部分算法字节比较器不能充分使用FPGA的查找表；2）输入信号和比较器的扇出太大造成系统的时钟频率不可能太高；3）比较器的大量使用会降低系统的资源利用率；4）FPGA中的资源使用不合理，有的较多的使用了LUT和组合逻辑，而寄存器资源使用较少，另外一些则反之。 本文针对以上问题，对千兆网络环境和万兆网络环境对高性能的字符串匹配进行了研究。本文取得的成果包括以下几个方面： 1） 提出了适合千兆网络环境的双Hash字符串匹配算法。双Hash匹配法的主要思想是在于使用FPGA中的双端口存储器来实现Hash查找。双Hash匹配算法有两个优势：第一，每一个双端口存储器可以实现一种长度的字符串查找，这样大大提高了资源利用率，双Hash匹配算法资源利用率比相关基于Hash的匹配算法提高了百分之八十；第二，能够在线进行匹配模式串更新，解决了许多系统需要关机或者是更换芯片才能实现模式串更新的问题。 2） 提出了适合万兆网络环境的半字节字符串匹配算法。该算法通过对半字节比较器的比较结果和延时寄存器组的共享，极大地提高了资源的利用率。再通过4字节并行输入设计和模式字符串分组，提高了系统输入位宽和系统最高工作频率。综合性能比已知的算法提高了百分之三十四。 3） 分析目前入侵检测系统面临的挑战，对入侵检测系统不能满足高速网络处理性能的问题，提出了高速网络入侵检测系统架构，并实现了一套千兆网络入侵检测系统。通过测试分析，该系统能够满足千兆网络处理速度要求。