Algorithms And Implementation Of String Match In Intrusion Detection System

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.