Skip to main content

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: Turner, Paul and Broucek, Vlasti, eds. EICAR 2005 Conference Best Paper Proceedings. EICAR, pp. 26-40. ISBN 87-987271-7-6. (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) (KAR id:14327)

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.

Abstract

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: Book section
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: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Mark Wheadon
Date Deposited: 24 Nov 2008 18:03 UTC
Last Modified: 12 Jul 2022 10:39 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/14327 (The current URI for this page, for reference purposes)

University of Kent Author Information

Tripp, Gerald.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.