suricata
util-spm.c File Reference
#include "suricata-common.h"
#include "suricata.h"
#include "util-unittest.h"
#include "conf.h"
#include "util-spm.h"
#include "util-spm-bs.h"
#include "util-spm-bs2bm.h"
#include "util-spm-bm.h"
#include "util-spm-hs.h"
#include "util-clock.h"
Include dependency graph for util-spm.c:

Go to the source code of this file.

Data Structures

struct  SpmTestData_
 

Macros

#define STATS_TIMES   1000000
 
#define SPM_NO_MATCH   UINT32_MAX
 

Typedefs

typedef struct SpmTestData_ SpmTestData
 

Functions

uint16_t SinglePatternMatchDefaultMatcher (void)
 Returns the single pattern matcher algorithm to be used, based on the spm-algo setting in yaml. More...
 
void SpmTableSetup (void)
 
SpmGlobalThreadCtxSpmInitGlobalThreadCtx (uint16_t matcher)
 
void SpmDestroyGlobalThreadCtx (SpmGlobalThreadCtx *global_thread_ctx)
 
SpmThreadCtxSpmMakeThreadCtx (const SpmGlobalThreadCtx *global_thread_ctx)
 
void SpmDestroyThreadCtx (SpmThreadCtx *thread_ctx)
 
SpmCtxSpmInitCtx (const uint8_t *needle, uint16_t needle_len, int nocase, SpmGlobalThreadCtx *global_thread_ctx)
 
void SpmDestroyCtx (SpmCtx *ctx)
 
uint8_t * SpmScan (const SpmCtx *ctx, SpmThreadCtx *thread_ctx, const uint8_t *haystack, uint32_t haystack_len)
 
uint8_t * Bs2bmSearch (const uint8_t *text, uint32_t textlen, const uint8_t *needle, uint16_t needlelen)
 Search a pattern in the text using the Bs2Bm algorithm (build a bad characters array) More...
 
uint8_t * Bs2bmNocaseSearch (const uint8_t *text, uint32_t textlen, const uint8_t *needle, uint16_t needlelen)
 Search a pattern in the text using the Bs2Bm nocase algorithm (build a bad characters array) More...
 
uint8_t * BoyerMooreSearch (const uint8_t *text, uint32_t textlen, const uint8_t *needle, uint16_t needlelen)
 Search a pattern in the text using Boyer Moore algorithm (build a bad character shifts array and good prefixes shift array) More...
 
uint8_t * BoyerMooreNocaseSearch (const uint8_t *text, uint32_t textlen, uint8_t *needle, uint16_t needlelen)
 Search a pattern in the text using Boyer Moore nocase algorithm (build a bad character shifts array and good prefixes shift array) More...
 
void UtilSpmSearchRegistertests (void)
 

Detailed Description

Author
Pablo Rincon Crespo pablo.nosp@m..rin.nosp@m.con.c.nosp@m.resp.nosp@m.o@gma.nosp@m.il.c.nosp@m.om

PR (17/01/2010): Single pattern search algorithms: Currently there are 3 algorithms to choose: BasicSearch, Bs2Bm and BoyerMoore (Boyer Moores algorithm). The first one doesn't need a context. But for Bs2Bm and BoyerMoore, you'll need to build some arrays.

!! If you are going to use the same pattern multiple times, please, try to store the context some where. For Bs2Bm, the context is an array of "badchars". For BoyerMoore you need to store two arrays of shifts. Have a look at the wrappers and unittests for examples of this. If you cant store the context, use the wrappers: Bs2bmSearch, BoyerMooreSearch, and the ones caseless, or BasicSearch That is the most basic.

Use the stats and util-clock.h to determine which one fit better for you Boyer Moore should be used for patterns greater than 1 of length In the range of 2 - 6, if the text length is greater than 1000 you could use boyer moore, otherwise, basic search. If the pattern is greater than 6 and the textlen is greater than 500, use boyer moore. This is an aproximation, but use the stats and util-clock to determine which one fit better for your case.

Definition in file util-spm.c.

Macro Definition Documentation

#define SPM_NO_MATCH   UINT32_MAX

Definition at line 2461 of file util-spm.c.

#define STATS_TIMES   1000000

Comment out this if you want stats #define ENABLE_SEARCH_STATS 1

Definition at line 281 of file util-spm.c.

Typedef Documentation

typedef struct SpmTestData_ SpmTestData

Function Documentation

uint8_t* BoyerMooreNocaseSearch ( const uint8_t *  text,
uint32_t  textlen,
uint8_t *  needle,
uint16_t  needlelen 
)

Search a pattern in the text using Boyer Moore nocase algorithm (build a bad character shifts array and good prefixes shift array)

Parameters
textText to search in
textlenlength of the text
needlepattern to search for
needlelenlength of the pattern

Definition at line 262 of file util-spm.c.

References BoyerMooreCtxDeInit(), BoyerMooreNocase(), and BoyerMooreNocaseCtxInit().

Here is the call graph for this function:

uint8_t* BoyerMooreSearch ( const uint8_t *  text,
uint32_t  textlen,
const uint8_t *  needle,
uint16_t  needlelen 
)

Search a pattern in the text using Boyer Moore algorithm (build a bad character shifts array and good prefixes shift array)

Parameters
textText to search in
textlenlength of the text
needlepattern to search for
needlelenlength of the pattern

Definition at line 242 of file util-spm.c.

References BoyerMoore(), BoyerMooreCtxDeInit(), and BoyerMooreCtxInit().

Here is the call graph for this function:

uint8_t* Bs2bmNocaseSearch ( const uint8_t *  text,
uint32_t  textlen,
const uint8_t *  needle,
uint16_t  needlelen 
)

Search a pattern in the text using the Bs2Bm nocase algorithm (build a bad characters array)

Parameters
textText to search in
textlenlength of the text
needlepattern to search for
needlelenlength of the pattern

Definition at line 224 of file util-spm.c.

References ALPHABET_SIZE, Bs2BmBadchars(), and Bs2BmNocase().

Here is the call graph for this function:

uint8_t* Bs2bmSearch ( const uint8_t *  text,
uint32_t  textlen,
const uint8_t *  needle,
uint16_t  needlelen 
)

Search a pattern in the text using the Bs2Bm algorithm (build a bad characters array)

Wrappers for building context and searching (Bs2Bm and boyermoore) Use them if you cant store the context

Parameters
textText to search in
textlenlength of the text
needlepattern to search for
needlelenlength of the pattern

Definition at line 207 of file util-spm.c.

References ALPHABET_SIZE, Bs2Bm(), and Bs2BmBadchars().

Here is the call graph for this function:

uint16_t SinglePatternMatchDefaultMatcher ( void  )

Returns the single pattern matcher algorithm to be used, based on the spm-algo setting in yaml.

Definition at line 66 of file util-spm.c.

References ConfGet(), SC_ERR_INVALID_YAML_CONF_ENTRY, SCLogError, SCLogInfo, SPM_BM, SPM_HS, spm_table, and SPM_TABLE_SIZE.

Referenced by AppLayerProtoDetectSetup(), and DetectEngineInspectBufferGeneric().

Here is the call graph for this function:

Here is the caller graph for this function:

void SpmDestroyCtx ( SpmCtx ctx)
void SpmDestroyGlobalThreadCtx ( SpmGlobalThreadCtx global_thread_ctx)

Definition at line 137 of file util-spm.c.

References SpmTableElmt_::DestroyGlobalThreadCtx, SpmGlobalThreadCtx_::matcher, and spm_table.

Referenced by AppLayerProtoDetectDeSetup(), and DetectEngineCtxFree().

Here is the caller graph for this function:

void SpmDestroyThreadCtx ( SpmThreadCtx thread_ctx)

Definition at line 156 of file util-spm.c.

References BUG_ON, SpmTableElmt_::DestroyThreadCtx, SpmThreadCtx_::matcher, and spm_table.

Referenced by AppLayerProtoDetectDestroyCtxThread(), and DetectEngineThreadCtxInit().

Here is the caller graph for this function:

SpmCtx* SpmInitCtx ( const uint8_t *  needle,
uint16_t  needle_len,
int  nocase,
SpmGlobalThreadCtx global_thread_ctx 
)
SpmGlobalThreadCtx* SpmInitGlobalThreadCtx ( uint16_t  matcher)

Definition at line 131 of file util-spm.c.

References BUG_ON, SpmTableElmt_::InitGlobalThreadCtx, and spm_table.

Referenced by AppLayerProtoDetectSetup(), and DetectEngineInspectBufferGeneric().

Here is the caller graph for this function:

SpmThreadCtx* SpmMakeThreadCtx ( const SpmGlobalThreadCtx global_thread_ctx)

Definition at line 146 of file util-spm.c.

References BUG_ON, SpmTableElmt_::MakeThreadCtx, SpmGlobalThreadCtx_::matcher, and spm_table.

Referenced by AppLayerProtoDetectGetCtxThread(), and DetectEngineResetMaxSigId().

Here is the caller graph for this function:

uint8_t* SpmScan ( const SpmCtx ctx,
SpmThreadCtx thread_ctx,
const uint8_t *  haystack,
uint32_t  haystack_len 
)

Definition at line 186 of file util-spm.c.

References SpmCtx_::matcher, SpmTableElmt_::Scan, and spm_table.

Referenced by DetectEngineContentInspection().

Here is the caller graph for this function:

void SpmTableSetup ( void  )

Definition at line 115 of file util-spm.c.

References spm_table, SpmBMRegister(), and SpmHSRegister().

Referenced by ListAppLayerProtocols(), ListKeywords(), PostRunDeinit(), RegisterAllModules(), and RunUnittests().

Here is the call graph for this function:

Here is the caller graph for this function:

void UtilSpmSearchRegistertests ( void  )

Definition at line 2669 of file util-spm.c.

References UtRegisterTest().

Here is the call graph for this function: