Re: IDS\IPS that can handle one Gig

[Nick Black <dank () reflexsecurity net>]

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.
--------------------------------------------------------------------------