Fast Multipattern Search Algorithms for Intrusion Detection

Issue title: Computing Patterns in Strings

Article type: Research Article

Authors: Kuri, Josué | Navarro, Gonzalo | Mé, Ludovic

Affiliations: Dept. of Computer Science and Networks, ENST, 46, rue Barrault, 75634, France | Dept. of Computer Science, University of Chile, Blanco Encalada 2120, Santiago, Chile | Supélec. Campus de Rennes, France

Abstract: We present new search algorithms to detect the occurrences of any pattern from a given pattern set in a text, allowing in the occurrences a limited number of spurious text characters among those of the pattern. This is a common requirement in intrusion detection applications. Our algorithms exploit the ability to represent the search state of one or more patterns in the bits of a single machine word and update all the search states in a single operation. We show analytically and experimentally that the algorithms are able of fast searching for large sets of patterns allowing a wide number of spurious characters, yielding in our machine about a 75-fold improvement over the classical dynamic programming algorithm.

Keywords: Approximate string matching, bit-parallelism, security, audit trails

Journal: Fundamenta Informaticae, vol. 56, no. 1-2, pp. 23-49, 2003