#include "suricata-common.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 "util-debug.h"
Go to the source code of this file.
Data Structures | |
| struct | SpmTestData_ |
Macros | |
| #define | SPM_NO_MATCH UINT32_MAX |
Typedefs | |
| typedef struct SpmTestData_ | SpmTestData |
Functions | |
| uint8_t | SinglePatternMatchDefaultMatcher (void) |
| Returns the single pattern matcher algorithm to be used, based on the spm-algo setting in yaml. More... | |
| void | SpmTableSetup (void) |
| SpmGlobalThreadCtx * | SpmInitGlobalThreadCtx (uint8_t matcher) |
| void | SpmDestroyGlobalThreadCtx (SpmGlobalThreadCtx *global_thread_ctx) |
| SpmThreadCtx * | SpmMakeThreadCtx (const SpmGlobalThreadCtx *global_thread_ctx) |
| void | SpmDestroyThreadCtx (SpmThreadCtx *thread_ctx) |
| SpmCtx * | SpmInitCtx (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 * | 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) |
Variables | |
| SpmTableElmt | spm_table [SPM_TABLE_SIZE] |
Detailed Description
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
◆ SPM_NO_MATCH
| #define SPM_NO_MATCH UINT32_MAX |
Definition at line 2452 of file util-spm.c.
Typedef Documentation
◆ SpmTestData
| typedef struct SpmTestData_ SpmTestData |
Function Documentation
◆ BoyerMooreNocaseSearch()
| 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
-
text Text to search in textlen length of the text needle pattern to search for needlelen length of the pattern
Definition at line 252 of file util-spm.c.
References BoyerMooreCtxDeInit(), BoyerMooreNocase(), and BoyerMooreNocaseCtxInit().
◆ BoyerMooreSearch()
| 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
-
text Text to search in textlen length of the text needle pattern to search for needlelen length of the pattern
Definition at line 232 of file util-spm.c.
References BoyerMoore(), BoyerMooreCtxDeInit(), and BoyerMooreCtxInit().
◆ Bs2bmSearch()
| 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
-
text Text to search in textlen length of the text needle pattern to search for needlelen length of the pattern
Definition at line 214 of file util-spm.c.
References ALPHABET_SIZE, Bs2Bm(), and Bs2BmBadchars().
◆ SinglePatternMatchDefaultMatcher()
| uint8_t SinglePatternMatchDefaultMatcher | ( | void | ) |
Returns the single pattern matcher algorithm to be used, based on the spm-algo setting in yaml.
Definition at line 68 of file util-spm.c.
References ConfGet(), FatalError, SCLogError, SCLogInfo, SPM_BM, SPM_HS, spm_table, and SPM_TABLE_SIZE.
◆ SpmDestroyCtx()
| void SpmDestroyCtx | ( | SpmCtx * | ctx | ) |
Definition at line 183 of file util-spm.c.
References BUG_ON, ctx, SpmTableElmt_::DestroyCtx, and spm_table.
Referenced by DetectContentConvertToNocase(), and DetectContentFree().
◆ SpmDestroyGlobalThreadCtx()
| void SpmDestroyGlobalThreadCtx | ( | SpmGlobalThreadCtx * | global_thread_ctx | ) |
Definition at line 144 of file util-spm.c.
References SpmTableElmt_::DestroyGlobalThreadCtx, SpmGlobalThreadCtx_::matcher, and spm_table.
Referenced by DetectEngineCtxFree().
◆ SpmDestroyThreadCtx()
| void SpmDestroyThreadCtx | ( | SpmThreadCtx * | thread_ctx | ) |
Definition at line 163 of file util-spm.c.
References BUG_ON, SpmTableElmt_::DestroyThreadCtx, SpmThreadCtx_::matcher, and spm_table.
◆ SpmInitCtx()
| SpmCtx* SpmInitCtx | ( | const uint8_t * | needle, |
| uint16_t | needle_len, | ||
| int | nocase, | ||
| SpmGlobalThreadCtx * | global_thread_ctx | ||
| ) |
Definition at line 173 of file util-spm.c.
References BUG_ON, SpmTableElmt_::InitCtx, SpmGlobalThreadCtx_::matcher, and spm_table.
Referenced by DetectContentConvertToNocase(), and DetectContentParse().
◆ SpmInitGlobalThreadCtx()
| SpmGlobalThreadCtx* SpmInitGlobalThreadCtx | ( | uint8_t | matcher | ) |
Definition at line 138 of file util-spm.c.
References BUG_ON, SpmTableElmt_::InitGlobalThreadCtx, and spm_table.
◆ SpmMakeThreadCtx()
| SpmThreadCtx* SpmMakeThreadCtx | ( | const SpmGlobalThreadCtx * | global_thread_ctx | ) |
Definition at line 153 of file util-spm.c.
References BUG_ON, SpmTableElmt_::MakeThreadCtx, SpmGlobalThreadCtx_::matcher, and spm_table.
◆ SpmScan()
| uint8_t* SpmScan | ( | const SpmCtx * | ctx, |
| SpmThreadCtx * | thread_ctx, | ||
| const uint8_t * | haystack, | ||
| uint32_t | haystack_len | ||
| ) |
Definition at line 193 of file util-spm.c.
References ctx, SpmTableElmt_::Scan, and spm_table.
◆ SpmTableSetup()
| void SpmTableSetup | ( | void | ) |
Definition at line 122 of file util-spm.c.
References spm_table, SpmBMRegister(), and SpmHSRegister().
Referenced by ListAppLayerProtocols(), ListKeywords(), LLVMFuzzerTestOneInput(), PostConfLoadedSetup(), and RunUnittests().
◆ UtilSpmSearchRegistertests()
| void UtilSpmSearchRegistertests | ( | void | ) |
Definition at line 2657 of file util-spm.c.
References UtRegisterTest().
Variable Documentation
◆ spm_table
| SpmTableElmt spm_table[SPM_TABLE_SIZE] |
Definition at line 62 of file util-spm.c.
Referenced by SinglePatternMatchDefaultMatcher(), SpmBMRegister(), SpmDestroyCtx(), SpmDestroyGlobalThreadCtx(), SpmDestroyThreadCtx(), SpmInitCtx(), SpmInitGlobalThreadCtx(), SpmMakeThreadCtx(), SpmScan(), and SpmTableSetup().
