Mike Frantzen assumed the extended riemann hypothesis and showed:
There are a plethora of multi-pattern regex algorithms that even with a
ton of patterns will only walk the packet data once (not many times as
most people would think). Shift-Or, Aho-Corasick and DFAs are the ones
To be pedantic, Shift-Or and Aho-Corasick are merely multistring
algorithms ("DFA"'s are of course not algorithms, but rather a
class of computational constructs equivalent to regular expressions
in terms of languages recognized and the basis of most regex matching
algorithms). Regex algorithms almost universally combine a Shift-Or
or Shift-And-esque search with a partitioned Glushkov or Thompson
automaton, balancing the higher running time of direct NFA simulation
against the exponential space costs of worst-case NFA->DFA conversion.
BPThompson / BPGlushkov are based directly on a Shift-And transition,
for what it's worth. BNDM has a fairly trivial extension to regular
expressions, but the prefix-matching space is best extended by the
MultiStringRE algorithm (not derived from Aho-Corasick iirc, as
evidenced by the absence of a supply function).
...back under my rock...
--
nick black "np: the class of dashed hopes and idle dreams."
--------------------------------------------------------------------------
Test Your IDS
Is your IDS deployed correctly?
Find out quickly and easily by testing it with real-world attacks from
CORE IMPACT.
Go to http://www.securityfocus.com/sponsor/CoreSecurity_focus-ids_040708
to learn more.
--------------------------------------------------------------------------
