A Finite-State-Machine based string matching system for Intrusion Detection on High-Speed Networks

This paper describes a finite state machine approach for string matching within high-speed network intrusion detection systems. This method uses a standard table based finite state machine implementation, but this is preceded by a preliminary stage that compresses multi-byte network input data into a series of tokens. Each string is matched using a separate finite state machine, each of which has an individually customised token stream. The finite state machines thus created need only a small amount of hardware resources and the overall system is designed to consume network input data at a rate of one word per clock cycle, independent of the search strings and the input data being searched. This technique has been tested using a high-level simulation in Java, with an architecture consisting of two Ternary Content Addressable Memory (TCAM) components followed by a tree structure of lookup tables that generate a separate token stream for each finite state machine. The results of the simulation show that the technique is effective for an input word size of up to 64-bits. It is possible to build the lookup tables and the finite state machine tables with relatively small blocks of memory, such as those provided within a Field Programmable Gate Array the TCAM can be implemented as external components. Most of the complexity in this system is within the software that compiles the string matching rules into the contents for the various lookup tables; the hardware resources required are mainly the various interconnected lookup tables that need initialising each time we change the rule set.