Fast Multipattern Search Algorithms for Intrusion Detection

Josué Kuri and Gonzalo Navarro

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 large sets of patterns allowing a wide number of spurious characters, yielding about a 75-fold improvement over the classical algorithm.