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

Tripp, Gerald (2005) A Finite-State-Machine based string matching system for Intrusion Detection on High-Speed Networks. In: 14th Annual EICAR Conference, 30 April - 2 May 2005, Valletta, Malta. (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided)

The full text of this publication is not available from this repository. (Contact us about this Publication)


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.

Item Type: Conference or workshop item (Paper)
Uncontrolled keywords: Security, intrusion detection, finite state machine, string matching, high speed networks
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Faculties > Science Technology and Medical Studies > School of Computing > Systems Architecture Group
Depositing User: Mark Wheadon
Date Deposited: 24 Nov 2008 18:03
Last Modified: 06 Dec 2008 13:05
Resource URI: https://kar.kent.ac.uk/id/eprint/14327 (The current URI for this page, for reference purposes)
  • Depositors only (login required):