School of Computing

A parallel 'String Matching Engine' for use in high speed network intrusion detection systems

Gerald Tripp

In Vlasti Broucek and Paul Turner, editors, 15th EICAR Annual Conference Proceedings, pages 182-196. EICAR, April 2006.

Abstract

This paper describes a finite state machine approach to string matching for an intrusion detection system. To obtain high performance, we typically need to be able to operate on input data that is several bytes wide. However, finite state machine designs become more complex when operating on large input data words, partly because of needing to match the starts and ends of a string that may occur part way through an input data word.

Here we use finite state machines that each operate on only a single byte wide data input. We then provide a separate finite state machine for each byte wide data path from a multi-byte wide input data word. By splitting the search strings into multiple interleaved substrings and by combining the outputs from the individual finite state machines in an appropriate way we can perform string matching in parallel across multiple finite state machines.

A hardware design for a parallel string matching engine has been generated, built for implementation in a Xilinx Field Programmable Gate Array and tested by simulation. The design is capable of operating at a search rate of 4.7 Gbps with a 32-bit input word size.

Download publication 411 kbytes (PDF)

Bibtex Record

@inproceedings{2553,
author = {Gerald Tripp},
title = {A parallel '{S}tring {M}atching {E}ngine' for use in high speed network intrusion detection systems},
month = {April},
year = {2006},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2006/2553},
    publication_type = {inproceedings},
    submission_id = {22292_1180963275},
    ISBN = {87-987271-8-4},
    booktitle = {15th EICAR Annual Conference Proceedings},
    editor = {Vlasti Broucek and Paul Turner},
    organization = {EICAR},
    refereed = {yes},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014