snort-devel April 2008 archive
Main Archive Page > Month Archives  > snort-devel archives
snort-devel: Re: [Snort-devel] snort single pattern matching alg

Re: [Snort-devel] snort single pattern matching algorithm

From: Steven Sturges <steve.sturges_at_nospam>
Date: Tue Apr 29 2008 - 13:41:00 GMT
To: Beliz Senyuz <beliz.senyuz@gmail.com>


Hi Beliz--

Boyer-Moore is the better performing algorithm for a single pattern. AC is better for multiple patterns.

make_precomp() is called when the pattern is parsed, which is prior to any patterns being checked, so the skip and shift tables are computer BEFORE the call to CheckANDPatternMatch() (or CheckUriPatternMatch()). The data for the skip & shift tables are included in the PatternMatchData structure that is referenced in those functions.

Cheers.
-steve

Beliz Senyuz wrote:
> Hi,
>
> I am working on pattern matching algorithms. I want to find the occurrence
> of a single pattern in a given text.
>
> I found the Boyer-Moore Algorithm implementation in (src/mstring.c) Is this
> code valid? Or even for single pattern search do I have to use Aho-Corasick?
>
> Here is my question about Boyer-Moore implementation:
> - search function mSearch which is in (src/mstring.c) is called from
> (detection_plugins/sp_pattern_match.c)
> - mSearch takes as parameter Boyer-Moore skip and shift tables
> - skip and shift tables are computed by make_precomp function in
> (detection_plugins/sp_pattern_match.c)
> - make_precomp is called AFTER mSearch
>
> How does it work? How the parameters can be computed after the function
> call?
>
> Thanks,
>
> Beliz
>
>
>
> ------------------------------------------------------------------------
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
> Don't miss this year's exciting event. There's still time to save $100.
> Use priority code J8TL2D2.
> http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Snort-devel mailing list
> Snort-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/snort-devel



This SF.net email is sponsored by the 2008 JavaOne(SM) Conference Don't miss this year's exciting event. There's still time to save $100. Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone

Snort-devel mailing list
Snort-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/snort-devel