【作者】 黄建；

【导师】 杨宗凯；

【作者基本信息】 华中科技大学 ， 通信与信息系统， 2008， 博士

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

【Abstract】 As the key technology of network content security check, string matching algorithms are wildly used in the intrusion detection, intrusion protection, network virus protection, network content monitoring and other network security systems. String matching algorithm is the most computational part of the network security system, take network intrusion detection system as an example, string matching takes up over 50% computational resource. With the increasing of network attack method, more and more pattern strings is defined in the network security system that causes computational resource used by string matching increasing. In addition, network bandwidth grows three times faster than computing power in the passed twenty years. Software based string matching algorithms can’t keep up with the network bandwidth increasing. ASIC based string matching algorithms can provide high throughputs, but its pattern strings is difficult to update that causes ASIC based string matching can’t satisfy the detection rules frequent updating in the network security systems.This thesis advocates the use FPGA to provide high speed and flexibility string matching. In recent years, many string matching researches based on FPGA, these researches all face the following 3 problems: 1) utilization ratio of FPGA resource is difficult to improve; 2) FPGA uses half custom technology, its highest working frequency is limited; 3) String matching algorithms design should be not too complex, that is convenient for implementing on FPGA.To solve the above problems, we studied the high performance string matching algorithms in the gigabits network and 10 gigabits network environment. The contributions of this thesis include:1) Proposed a double Hash matching algorithm that suits for gigabits networks environment. The main idea of double Hash matching algorithm is the use of double port block rams to implement hash lookup. This algorithm has 2 advantages: first, because every double port block ram can implement multi pattern strings that have the same length, its resource utilization ratio is high. Double Hash algorithm improves the resource utilization ratio 38% than the related hash based algorithms; Second, Hash table in the double ports block ram can be updated online, but many security systems should shutdown or change chips when updating pattern strings.2) Proposed a half byte string matching algorithm that suits for the 10 gigabits network environment. This algorithm shares the result of half byte comparator and delay register array, improved resource utilization ratio extremely. With the use of 4 bytes input in parallel and pattern strings grouping, we improved system input bit-width and system working frequency. Half byte string matching algorithm improves the performance 34% higher than the known algorithms.3) Analyzed challenges of current intrusion detection system. Proposed high speed network intrusion detection architecture to solve the processing speed limitation of current intrusion detection system. We implemented a set of gigabits network intrusion detection system. The test result implies our system can satisfy the requirement of processing speed in gigabits network environment.更多还原