[Snort-devel] Snort Pattern Search Algorithms
marc.norton at ...402...
Wed Apr 7 11:03:06 EDT 2004
Deciding what algorithms perform best in all pattern matching situations
is pretty dicey business - meaning , you can always find exceptions.
The Bad Word shifts aren't always faster than Bad Character shifts,
especially with small patterns of 1-3 bytes, and attack patterns. The
Wu-Manber algorithm has great average case performance and poor worst
case performance. In contrast the Aho-Corasick algorithm has the same
average and worst case performance and is very insensitive to the
content being inspected. However, it lacks any shifting features. In
practice however, mostly due to the rule sets used in Snort we don't see
a much difference in performance in real world networks. In some cases
where we have only a few rules applied to a service and they are all
3,4, or more characters in size the wu-manber algorithm benefits form
larger pattern sizes, but overall many rules have small patterns, and
the smallest pattern in a rule group determines the overall performance
of the wu-manber algorithm. This issues has no effect on the
aho-corasick algorithm though. In snort 2.1 we moved away from using
the wu-manber as the default, and suggest using the aho-corasick as the
default. When all issues are considered, it seems to be a more robust
--- Shameless self-promotion and more answers to your questions ---
I will be addressing performance issues in the very near term, in more
detail in a paper on pattern matching in Snort. You can look for this
paper at Snort.org, Idsresearch.com, and Sourcefire.com in the next
couple of weeks.
> -----Original Message-----
> From: snort-devel-admin at lists.sourceforge.net [mailto:snort-devel-
> admin at lists.sourceforge.net] On Behalf Of Frank Meerkoetter
> Sent: Wednesday, April 07, 2004 12:25 PM
> To: snort-devel at lists.sourceforge.net
> Subject: Re: [Snort-devel] Snort Pattern Search Algorithms
> On Tue, Apr 06, 2004 at 10:35:25AM -0400, Marc Norton wrote:
> > Snort uses a variant of the Wu-Manber algorithm, and a straight
> > implementation of the Aho-Corasick state machine. These perform the
> > high speed multi-pattern matching in Snort. You need to find the
> > on the snort.org web site to the papers that describe the detection
> > engine as a whole in order to understand how the whole thing is tied
> > together. You'll also need to read a fair amount of source code,
> > much of snort is not documented outside of the source code. Good
> while we're at it. I've got the following question concerning the
> implementation of the wu-manber multi-pattern matcher.
> As far as i could see "normal" traffic is searched using the function
> mwmSearchExBC which implements a one character shifttable/two
> hashtable wu-manber search.
> The function mwmSearchExBW which implements the two character
> version is only used when explicitly asked for (by calling
> mwmLargeShifts aka. mpseLargeShifts). Which is only done for searching
> What's the reason behind this? Why isn't mwmSearchExBW suitable for
> all traffic?
> Shouldn't it perform better than mwwSearchExBC? Why not?
> I thought a shifttable which is accessed by a block of characters
> perform better than a shifttable accessed by a single character.
> TIA Frank Meerkoetter
> mixed emotions:
> Watching a bus-load of lawyers plunge off a cliff.
> With five empty seats.
> This SF.Net email is sponsored by: IBM Linux Tutorials
> Free Linux tutorial presented by Daniel Robbins, President and CEO of
> GenToo technologies. Learn everything from fundamentals to system
> Snort-devel mailing list
> Snort-devel at lists.sourceforge.net
More information about the Snort-devel