Fast multipattern search algorithms for intrusion detection
Josué Kuri, Gonzalo Navarro · 2002
Presents 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 to update all the search states in a single operation. We show analytically and experimentally that the algorithms are able of rapidly searching large sets of patterns, allowing a large number of spurious characters, yielding about a 75-fold improvement over the classical algorithm.