<DIV>Hi Marc</DIV>
<DIV> </DIV>
<DIV>I was just going through one of the archieves of Snort User </DIV>
<DIV><A href="http://msgs.securepoint.com/cgi-bin/get/snort-0404/60/1.html">http://msgs.securepoint.com/cgi-bin/get/snort-0404/60/1.html</A></DIV>
<DIV>from <STRONG><EM>Alejandro Flores  </EM></STRONG>where it says pattern order has a significance while matching in snort. Please let me know if u r sure about it. </DIV>
<DIV> </DIV>
<DIV><STRONG><EM>Alejandro</EM></STRONG>,</DIV>
<DIV>can u also comment on this.</DIV>
<DIV> </DIV>
<DIV>Thanks</DIV>
<DIV>Peter<BR><BR><B><I>Marc Norton <marc.norton@...402...></I></B> wrote:</DIV>
<BLOCKQUOTE class=replbq style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #1010ff 2px solid">
<META content=Word.Document name=ProgId>
<META content="Microsoft Word 10" name=Generator>
<META content="Microsoft Word 10" name=Originator><LINK href="cid:filelist.xml@...2482..." rel=File-List><LINK href="cid:editdata.mso@...2482..." rel=Edit-Time-Data>
<STYLE>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</STYLE>

<STYLE>
<!--
 /* Font Definitions */
 @font-face
        {font-family:Tahoma;
        panose-1:2 11 6 4 3 5 4 4 2 4;
        mso-font-charset:0;
        mso-generic-font-family:swiss;
        mso-font-pitch:variable;
        mso-font-signature:553679495 -2147483648 8 0 66047 0;}
 /* Style Definitions */
 p.MsoNormal, li.MsoNormal, div.MsoNormal
        {mso-style-parent:"";
        margin:0in;
        margin-bottom:.0001pt;
        mso-pagination:widow-orphan;
        font-size:12.0pt;
        font-family:"Times New Roman";
        mso-fareast-font-family:"Times New Roman";}
a:link, span.MsoHyperlink
        {color:blue;
        text-decoration:underline;
        text-underline:single;}
a:visited, span.MsoHyperlinkFollowed
        {color:blue;
        text-decoration:underline;
        text-underline:single;}
p
        {mso-margin-top-alt:auto;
        margin-right:0in;
        mso-margin-bottom-alt:auto;
        margin-left:0in;
        mso-pagination:widow-orphan;
        font-size:12.0pt;
        font-family:"Times New Roman";
        mso-fareast-font-family:"Times New Roman";}
span.EmailStyle18
        {mso-style-type:personal-reply;
        mso-style-noshow:yes;
        mso-ansi-font-size:10.0pt;
        mso-bidi-font-size:10.0pt;
        font-family:Arial;
        mso-ascii-font-family:Arial;
        mso-hansi-font-family:Arial;
        mso-bidi-font-family:Arial;
        color:navy;}
span.SpellE
        {mso-style-name:"";
        mso-spl-e:yes;}
span.GramE
        {mso-style-name:"";
        mso-gram-e:yes;}
@page Section1
        {size:8.5in 11.0in;
        margin:1.0in 1.25in 1.0in 1.25in;
        mso-header-margin:.5in;
        mso-footer-margin:.5in;
        mso-paper-source:0;}
div.Section1
        {page:Section1;}
-->
</STYLE>

<DIV class=Section1>
<P class=MsoNormal><FONT face=Arial color=navy size=2><SPAN style="FONT-SIZE: 10pt; COLOR: navy; FONT-FAMILY: Arial">Pattern order does not matter in Snort if you just specify <SPAN class=SpellE>content<SPAN class=GramE>:ABC</SPAN></SPAN>, <SPAN class=SpellE>content:DEF</SPAN> .<SPAN style="mso-spacerun: yes">   </SPAN><SPAN class=GramE>either</SPAN> ABCDEF or DEFABC will match.<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" /><o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial color=navy size=2><SPAN style="FONT-SIZE: 10pt; COLOR: navy; FONT-FAMILY: Arial"><o:p> </o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial color=navy size=2><SPAN style="FONT-SIZE: 10pt; COLOR: navy; FONT-FAMILY: Arial">The <SPAN class=SpellE>wu-manber</SPAN> paper is “A Fast Algorithm for Multi-Pattern Searching”, by Sung Wu and Udi Manber 1994<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial color=navy size=2><SPAN style="FONT-SIZE: 10pt; COLOR: navy; FONT-FAMILY: Arial"><o:p> </o:p></SPAN></FONT></P>
<DIV style="BORDER-RIGHT: medium none; PADDING-RIGHT: 0in; BORDER-TOP: medium none; PADDING-LEFT: 4pt; PADDING-BOTTOM: 0in; BORDER-LEFT: blue 1.5pt solid; PADDING-TOP: 0in; BORDER-BOTTOM: medium none">
<P class=MsoNormal><FONT face=Tahoma size=2><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: Tahoma">-----Original Message-----<BR><B><SPAN style="FONT-WEIGHT: bold">From:</SPAN></B> Peter Richard [mailto:list_tom@...398...] <BR><B><SPAN style="FONT-WEIGHT: bold">Sent:</SPAN></B> Wednesday, April 14, 2004 1:59 AM<BR><B><SPAN style="FONT-WEIGHT: bold">To:</SPAN></B> Marc Norton<BR><B><SPAN style="FONT-WEIGHT: bold">Subject:</SPAN></B> Re: RE: [Snort-devel] Snort Pattern Search Algorithms</SPAN></FONT></P>
<P class=MsoNormal><FONT face="Times New Roman" size=3><SPAN style="FONT-SIZE: 12pt"><o:p> </o:p></SPAN></FONT></P>
<DIV>
<BLOCKQUOTE style="BORDER-RIGHT: medium none; PADDING-RIGHT: 0in; BORDER-TOP: medium none; MARGIN-TOP: 5pt; PADDING-LEFT: 4pt; MARGIN-BOTTOM: 5pt; PADDING-BOTTOM: 0in; MARGIN-LEFT: 3.75pt; BORDER-LEFT: #1010ff 1.5pt solid; PADDING-TOP: 0in; BORDER-BOTTOM: medium none">
<P><FONT face="Times New Roman" size=3><SPAN style="FONT-SIZE: 12pt">Hi Mark,<o:p></o:p></SPAN></FONT></P>
<P><FONT face="Times New Roman" size=3><SPAN style="FONT-SIZE: 12pt">can u also help me in 1 more thing...<BR>Assume a Snort Signature has to match ABC and DEF<o:p></o:p></SPAN></FONT></P>
<P><FONT face="Times New Roman" size=3><SPAN style="FONT-SIZE: 12pt">Will it be detected if the packet is having sequence as DEFABC.<BR>just wanted to know if ordering of patterns matter?<BR><BR>Also Mark please let me know if you can lend me some documents for Wu-Manber Apporach used in snort.<o:p></o:p></SPAN></FONT></P>
<P><FONT face="Times New Roman" size=3><SPAN style="FONT-SIZE: 12pt">Thanks<BR>Peter.<o:p></o:p></SPAN></FONT></P>
<P><FONT face="Times New Roman" size=3><SPAN style="FONT-SIZE: 12pt"> <o:p></o:p></SPAN></FONT></P>
<P><FONT face="Times New Roman" size=3><SPAN style="FONT-SIZE: 12pt"> <o:p></o:p></SPAN></FONT></P>
<P><FONT face="Times New Roman" size=3><SPAN style="FONT-SIZE: 12pt"><BR>--__--__--<BR><BR>Message: 5<BR>Date: Wed, 7 Apr 2004 18:24:44 +0200<BR>From: Frank Meerkoetter <BR><FRANK@...2483...>To: snort-devel@lists.sourceforge.net<BR>Subject: Re: [Snort-devel] Snort Pattern Search Algorithms<BR>Reply-To: frank@...2444...<BR><BR>On Tue, Apr 06, 2004 at 10:35:25AM -0400, Marc Norton wrote:<BR>Hello,<BR><BR>> Snort uses a variant of the Wu-Manber algorithm, and a straight forward<BR>> implementation of the Aho-Corasick state machine. These perform the<BR>> high speed multi-pattern matching in Snort. You need to find the links<BR>> on the snort.org web site to the papers that describe the detection<BR>> engine as a whole in order to understand how the whole thing is tied<BR>> together. You'll also need to read a fair amount of source code, since<BR>> much of snort is not documented outside of the source code. Good luck. <BR><BR>while we're at it. I've got the
 following question concerning the<BR>implementation of the wu-manber multi-pattern matcher.<BR><BR>As far as i could see "normal" traffic is searched using the function<BR>mwmSearchExBC which implements a one character shifttable/two character<BR>hashtable wu-manber search.<BR><BR>The function mwmSearchExBW which implements the two character shifttable<BR>version is only used when explicitly asked for (by calling<BR>mwmLargeShifts aka. mpseLargeShifts). Which is only done for searching<BR>URI-Content.<BR><BR>What's the reason behind this? Why isn't mwmSearchExBW suitable for<BR>all traffic?<BR>Shouldn't it perform better than mwwSearchExBC? Why not? <BR>I thought a shifttable which is accessed by a block of characters would <BR>perform better than a shifttable accessed by a single character.<BR><BR>TIA Frank Meerkoetter<BR>-- <BR>mixed emotions:<BR>Watching a bus-load of lawyers plunge off a cliff.<BR>With five empty seats.<BR><BR><BR>--__--__--<BR><BR>Message: 6<BR>From: "Marc
 Norton" <BR><MARC.NORTON@...2484...>To: snort-devel@lists.sourceforge.net<BR>Subject: RE: [Snort-devel] Snort Pattern Search Algorithms<BR>Date: Wed, 7 Apr 2004 14:02:29 -0400<BR><BR><BR><BR>Deciding what algorithms perform best in all pattern matching situations<BR>is pretty dicey business - meaning , you can always find exceptions.<BR>The Bad Word shifts aren't always faster than Bad Character shifts,<BR>especially with small patterns of 1-3 bytes, and attack patterns. The<BR>Wu-Manber algorithm has great average case performance and poor worst<BR>case performance. In contrast the Aho-Corasick algorithm has the same<BR>average and worst case performance and is very insensitive to the<BR>content being inspected. However, it lacks any shifting features. In<BR>practice however, mostly due to the rule sets used in Snort we don't see<BR>a much difference in performance in real world networks. In some cases<BR>where we have only a few rules applied to a service and they are
 all<BR>3,4, or more characters in size the wu-manber algorithm benefits form<BR>larger pattern sizes, but overall many rules have small patterns, and<BR>the smallest pattern in a rule group determines the overall performance<BR>of the wu-manber algorithm. This issues has no effect on the<BR>aho-corasick algorithm though. In snort 2.1 we moved away from using<BR>the wu-manber as the default, and suggest using the aho-corasick as the<BR>default. When all issues are considered, it seems to be a more robust<BR>choice.<BR><BR>--- Shameless self-promotion and more answers to your questions ---<BR><BR>I will be addressing performance issues in the very near term, in more<BR>detail in a paper on pattern matching in Snort. You can look for this<BR>paper at Snort.org, Idsresearch.com, and Sourcefire.com in the next<BR>couple of weeks.<BR><BR><BR>> -----Original Message-----<BR>> From: snort-devel-admin@lists.sourceforge.net [mailto:snort-devel-<BR>> admin@lists.sourceforge.net] On
 Behalf Of Frank Meerkoetter<BR>> Sent: Wednesday, April 07, 2004 12:25 PM<BR>> To: snort-devel@lists.sourceforge.net<BR>> Subject: Re: [Snort-devel] Snort Pattern Search Algorithms<BR>> <BR>> On Tue, Apr 06, 2004 at 10:35:25AM -0400, Marc Norton wrote:<BR>> Hello,<BR>> <BR>> > Snort uses a variant of the Wu-Manber algorithm, and a straight<BR>forward<BR>> > implementation of the Aho-Corasick state machine. These perform the<BR>> > high speed multi-pattern matching in Snort. You need to find the<BR>links<BR>> > on the snort.org web site to the papers that describe the detection<BR>> > engine as a whole in order to understand how the whole thing is tied<BR>> > together. You'll also need to read a fair amount of source code,<BR>since<BR>> > much of snort is not documented outside of the source code. Good<BR>luck.<BR>> <BR>> while we're at it. I've got the following question concerning the<BR>> implementation of the
 wu-manber multi-pattern matcher.<BR>> <BR>> As far as i could see "normal" traffic is searched using the function<BR>> mwmSearchExBC which implements a one character shifttable/two<BR>character<BR>> hashtable wu-manber search.<BR>> <BR>> The function mwmSearchExBW which implements the two character<BR>shifttable<BR>> version is only used when explicitly asked for (by calling<BR>> mwmLargeShifts aka. mpseLargeShifts). Which is only done for searching<BR>> URI-Content.<BR>> <BR>> What's the reason behind this? Why isn't mwmSearchExBW suitable for<BR>> all traffic?<BR>> Shouldn't it perform better than mwwSearchExBC? Why not?<BR>> I thought a shifttable which is accessed by a block of characters<BR>would<BR>> perform better than a shifttable accessed by a single character.<BR>> <BR>> TIA Frank Meerkoetter<BR>> --<BR>> mixed emotions:<BR>> Watching a bus-load of lawyers plunge off a cliff.<BR>> With five empty seats.<BR>>
 <o:p></o:p></SPAN></FONT></P></BLOCKQUOTE></DIV>
<DIV class=MsoNormal style="TEXT-ALIGN: center" align=center><FONT face="Times New Roman" size=3><SPAN style="FONT-SIZE: 12pt">
<HR align=center width="100%" SIZE=1>
</SPAN></FONT></DIV>
<P class=MsoNormal><FONT face=Arial size=2><SPAN style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">Do you Yahoo!?<BR>Yahoo! Tax Center - <A href="http://taxes.yahoo.com/filing.html">File online by April 15th</A></SPAN></FONT><o:p></o:p></P></DIV></DIV></BLOCKQUOTE><p>
                <hr size=1><font face=arial size=-1>Do you Yahoo!?<br>
Yahoo! Tax Center - <a href="http://taxes.yahoo.com/filing.html">File online by April 15th</a>