Re: IDS\IPS that can handle one Gig

From: Nick Black (dank_at_reflexsecurity.net)
Date: 06/06/05

  • Next message: Nick Black: "Re: IDS\IPS that can handle one Gig" 
    Date: Mon, 6 Jun 2005 16:29:22 -0400
To: Mike Frantzen <frantzen@nfr.com>

    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.
--------------------------------------------------------------------------
  • Next message: Nick Black: "Re: IDS\IPS that can handle one Gig"