[Snort-devel] Snort Pattern Search Algorithms

Marc Norton marc.norton at ...402...
Fri Apr 16 08:09:09 EDT 2004


Rule order is no longer important for content rules.  WE use two passes
in the detection engine, one does a high speed pass looking for all
possible rule contents at the same time, when any rule content is found
we completely process the rule it's associated with.  We use a bit mask
to make sure we don't process the same rule a bunch of times per packet
though.  Check out the White/tech Papers at snort.org on the detection
engine, they have more info.
 
-----Original Message-----
From: snort-devel-admin at lists.sourceforge.net
[mailto:snort-devel-admin at lists.sourceforge.net] On Behalf Of Peter
Richard
Sent: Friday, April 16, 2004 2:13 AM
To: Marc Norton; Alejandro Flores
Cc: snort-devel at lists.sourceforge.net
Subject: RE: RE: [Snort-devel] Snort Pattern Search Algorithms
 
Hi Marc
 
I was just going through one of the archieves of Snort User 
http://msgs.securepoint.com/cgi-bin/get/snort-0404/60/1.html
from Alejandro Flores  where it says pattern order has a significance
while matching in snort. Please let me know if u r sure about it. 
 
Alejandro,
can u also comment on this.
 
Thanks
Peter

Marc Norton <marc.norton at ...402...> wrote:
Pattern order does not matter in Snort if you just specify content:ABC,
content:DEF .   either ABCDEF or DEFABC will match.
 
The wu-manber paper is A Fast Algorithm for Multi-Pattern Searching,
by Sung Wu and Udi Manber 1994
 
-----Original Message-----
From: Peter Richard [mailto:list_tom at ...398...] 
Sent: Wednesday, April 14, 2004 1:59 AM
To: Marc Norton
Subject: Re: RE: [Snort-devel] Snort Pattern Search Algorithms
 
Hi Mark,
can u also help me in 1 more thing...
Assume a Snort Signature has to match ABC and DEF
Will it be detected if the packet is having sequence as DEFABC.
just wanted to know if ordering of patterns matter?

Also Mark please let me know if you can lend me some documents for
Wu-Manber Apporach used in snort.
Thanks
Peter.
 
 

--__--__--

Message: 5
Date: Wed, 7 Apr 2004 18:24:44 +0200
From: Frank Meerkoetter 
To: snort-devel at lists.sourceforge.net
Subject: Re: [Snort-devel] Snort Pattern Search Algorithms
Reply-To: frank at ...2444...

On Tue, Apr 06, 2004 at 10:35:25AM -0400, Marc Norton wrote:
Hello,

> Snort uses a variant of the Wu-Manber algorithm, and a straight
forward
> implementation of the Aho-Corasick state machine. These perform the
> high speed multi-pattern matching in Snort. You need to find the links
> 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, since
> much of snort is not documented outside of the source code. Good luck.


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 character
hashtable wu-manber search.

The function mwmSearchExBW which implements the two character shifttable
version is only used when explicitly asked for (by calling
mwmLargeShifts aka. mpseLargeShifts). Which is only done for searching
URI-Content.

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


--__--__--

Message: 6
From: "Marc Norton" 
To: snort-devel at lists.sourceforge.net
Subject: RE: [Snort-devel] Snort Pattern Search Algorithms
Date: Wed, 7 Apr 2004 14:02:29 -0400



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

--- 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:
> Hello,
> 
> > Snort uses a variant of the Wu-Manber algorithm, and a straight
forward
> > implementation of the Aho-Corasick state machine. These perform the
> > high speed multi-pattern matching in Snort. You need to find the
links
> > 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,
since
> > much of snort is not documented outside of the source code. Good
luck.
> 
> 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
character
> hashtable wu-manber search.
> 
> The function mwmSearchExBW which implements the two character
shifttable
> version is only used when explicitly asked for (by calling
> mwmLargeShifts aka. mpseLargeShifts). Which is only done for searching
> URI-Content.
> 
> 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
would
> 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.
> 

  _____  

Do you Yahoo!?
Yahoo! Tax Center - File online by <http://taxes.yahoo.com/filing.html>
April 15th
  _____  

Do you Yahoo!?
Yahoo! Tax Center - File online by <http://taxes.yahoo.com/filing.html>
April 15th
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.snort.org/pipermail/snort-devel/attachments/20040416/3ef07a2d/attachment.html>


More information about the Snort-devel mailing list