[Snort-devel] Exceeding the Speed of Snort

Martin Roesch roesch at ...48...
Sat Feb 10 22:51:14 EST 2001

Thanks for submitting this code, this is something I want to implement
in Snort ASAP.  Nice work Jason!


"C. Jason Coit" wrote:
> Silicon Defense is pleased to announce the proof of concept release of the
> Aho-Corasick Boyer-Moore (AC_BM) pattern matching algorithm for Snort.  Our
> implementation is integrated into Snort 1.6.3.  It is intended as a
> motivation to explore advanced pattern matching techniques in NIDS,
> particularly Snort.
> Background:
> Snort currently uses a standard Boyer-Moore searching
> algorithm to perform pattern matching.  It repeated applies this
> algorithm to examine packet content against a long list of patterns held
> by various OTN's that often contain common substrings - one example
> being the myriad of WEB-GET rules.  The standard search proceeds
> linearly down the OTN list and attempts to match a pattern contained in
> a rule against the entire packet.  If no match is found for the content
> of a particular rule, Snort will try to match the packet against the
> next OTN in the list.  Thus the packet requires several content searches
> of the entire packet before a match is found.  Our Aho-Corasick,
> Boyer-Moore Style (AC_BM) algorithm takes advantage of the similarities
> to examine the packet against multiple patterns at the same time and
> reduce the time it takes for a match to be found.  Since a majority of the
> rules (786 out of the 854 rules in 10102kany.rules) contain at least one
> "content:"  option, we thought any improvement on content searching would
> dramatically improve the overall
> efficiency of Snort.
> The AC_BM algorithm is an application of Boyer-Moore strategies of exact
> pattern matching to a set of patterns held in an Aho-Corasick like
> keyword tree.  It is essentially an implementation of a "Boyer-Moore
> Approach to Exact Set Matching" described by Dan Gusfield in "Algorithms
> on Strings, Trees, and Sequences."  In the text, Gusfield outlines an
> algorithm which uses suffix trees, and examines the text from left to
> right. Our implementation mirrors the Gusfield algorithm - it examines
> packet data from right to left and uses a common prefix approach instead
> of a common suffix approach.  The AC_BM implementation allows the
> various content rules to be placed in a tree that can be searched using
> elements of Boyer-Moore.
> Results:
> We tested our implementation on Capture the Flag (CTF) data from Defcon 8
> available at www.shmoo.org.  For 786 content rules the AC_BM implementation
> took 7.8 seconds while standard Boyer-Moore approach took 25.92 seconds.
> We exchange performance speed for memory.  AC_BM takes approximately 3 times
> the memory to run, for the example above standard Snort requires 3684 KB and
> ours requires 12312 KB.
> Information/Download:
> For more information, please visit the website at
> http://www.silicondefense.com/acbm/main.html
> where you will find our paper describing the algorithm, results, and
> behavioral changes to snort as well as our source code for the AC_BM
> integrated into Snort 1.6.3.
> or, download these directly from
> paper: http://www.silicondefense.com/acbm/speed_of_snort_01_10_2001.pdf
> readme: http://www.silicondefense.com/acbm/README.ACBMSEARCH
> code: http://www.silicondefense.com/acbm/snort-acbm-1.0.tar.gz
> Future Work:
> This is a proof of concept implementation.  Thus while it demonstrates the
> benefits of advanced pattern matching in Snort, it still needs some work to
> be integrated into future versions of Snort.  It is a quick and dirty
> approach that relies on the wonderful world of #ifdef's.  The memory required
> for the AC_BM can most likely be reduced by implementing a true suffix tree
> approach rather than a hybrid Aho-Corasick tree with a node for every
> character.  Snort's RTN/OTN list can also be redesigned to better condense
> similar options to eliminate unnecessary option checks and facilitate "exact
> set pattern matching."
> Silicon Defense does not currently plan to continue this research.  We are
> releasing the code for developers to do with as they wish.
> Feel free to email me with questions or comments.
> Regards,
> -Jason Coit
> +--------------------------------+
> |  Jason Coit, Silicon Defense   |
> | http://www.silicondefense.com/ |
> +--------------------------------+
> _______________________________________________
> Snort-devel mailing list
> Snort-devel at lists.sourceforge.net
> http://lists.sourceforge.net/lists/listinfo/snort-devel

Martin Roesch
roesch at ...48...

More information about the Snort-devel mailing list