[Snort-devel] snort single pattern matching algorithm

Steven Sturges steve.sturges at ...402...
Tue Apr 29 09:41:00 EDT 2008


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 at lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/snort-devel




More information about the Snort-devel mailing list