suricata
util-mpm-ac-bs.c File Reference
#include "suricata-common.h"
#include "suricata.h"
#include "detect.h"
#include "detect-parse.h"
#include "detect-engine.h"
#include "util-mpm-ac-bs.h"
#include "conf.h"
#include "util-debug.h"
#include "util-unittest.h"
#include "util-unittest-helper.h"
#include "util-memcmp.h"
#include "util-memcpy.h"
Include dependency graph for util-mpm-ac-bs.c:

Go to the source code of this file.

Data Structures

struct  StateQueue_
 Helper structure used by AC during state table creation. More...
 

Macros

#define SC_AC_BS_FAIL   (-1)
 
#define STATE_QUEUE_CONTAINER_SIZE   65536
 

Typedefs

typedef struct StateQueue_ StateQueue
 Helper structure used by AC during state table creation. More...
 

Functions

void SCACBSInitCtx (MpmCtx *mpm_ctx)
 Initialize the AC context. More...
 
void SCACBSInitThreadCtx (MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx)
 Init the mpm thread context. More...
 
void SCACBSDestroyCtx (MpmCtx *mpm_ctx)
 Destroy the mpm context. More...
 
void SCACBSDestroyThreadCtx (MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx)
 Destroy the mpm thread context. More...
 
int SCACBSAddPatternCI (MpmCtx *mpm_ctx, uint8_t *pat, uint16_t patlen, uint16_t offset, uint16_t depth, uint32_t pid, SigIntId sid, uint8_t flags)
 Add a case insensitive pattern. Although we have different calls for adding case sensitive and insensitive patterns, we make a single call for either case. No special treatment for either case. More...
 
int SCACBSAddPatternCS (MpmCtx *mpm_ctx, uint8_t *pat, uint16_t patlen, uint16_t offset, uint16_t depth, uint32_t pid, SigIntId sid, uint8_t flags)
 Add a case sensitive pattern. Although we have different calls for adding case sensitive and insensitive patterns, we make a single call for either case. No special treatment for either case. More...
 
int SCACBSPreparePatterns (MpmCtx *mpm_ctx)
 Process the patterns added to the mpm, and create the internal tables. More...
 
uint32_t SCACBSSearch (const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 The aho corasick search function. More...
 
void SCACBSPrintInfo (MpmCtx *mpm_ctx)
 
void SCACBSPrintSearchStats (MpmThreadCtx *mpm_thread_ctx)
 
void SCACBSRegisterTests (void)
 
void MpmACBSRegister (void)
 Register the aho-corasick mpm. More...
 

Detailed Description

Author
Anoop Saldanha anoop.nosp@m.sald.nosp@m.anha@.nosp@m.gmai.nosp@m.l.com
    First iteration of aho-corasick MPM from -

    Efficient String Matching: An Aid to Bibliographic Search
    Alfred V. Aho and Margaret J. Corasick

    - Uses the delta table for calculating transitions, instead of having
      separate goto and failure transitions.
    - If we cross 2 ** 16 states, we use 4 bytes in the transition table
      to hold each state, otherwise we use 2 bytes.
    - This version of the MPM is heavy on memory, but it performs well.
      If you can fit the ruleset with this mpm on your box without hitting
      swap, this is the MPM to go for.
Todo:
  • Do a proper analyis of our existing MPMs and suggest a good one based on the pattern distribution and the expected traffic(say http).
    • Tried out loop unrolling without any perf increase. Need to dig deeper.
    • Irrespective of whether we cross 2 ** 16 states or not,shift to using uint32_t for state type, so that we can integrate it's status as a final state or not in the topmost byte. We are already doing it if state_count is > 2 ** 16.
    • Test case-senstive patterns if they have any ascii chars. If they don't treat them as nocase.
    • Carry out other optimizations we are working on. hashes, compression.

Definition in file util-mpm-ac-bs.c.

Macro Definition Documentation

#define SC_AC_BS_FAIL   (-1)

Definition at line 79 of file util-mpm-ac-bs.c.

Referenced by MpmACBSRegister().

#define STATE_QUEUE_CONTAINER_SIZE   65536

Definition at line 81 of file util-mpm-ac-bs.c.

Referenced by MpmACBSRegister().

Typedef Documentation

typedef struct StateQueue_ StateQueue

Helper structure used by AC during state table creation.

Function Documentation

void MpmACBSRegister ( void  )

Register the aho-corasick mpm.

Definition at line 95 of file util-mpm-ac-bs.c.

References MpmTableElmt_::AddPattern, MpmTableElmt_::AddPatternNocase, StateQueue_::bot, MpmPattern_::ci, SCACBSPatternList_::cs, MpmCtx_::ctx, MpmTableElmt_::DestroyCtx, MpmTableElmt_::DestroyThreadCtx, SCACBSCtx_::failure_table, SCACBSCtx_::goto_table, MpmPattern_::id, MpmTableElmt_::InitCtx, MpmTableElmt_::InitThreadCtx, MpmPattern_::len, MpmCtx_::memory_cnt, MpmCtx_::memory_size, MPM_AC_BS, mpm_table, MpmTableElmt_::name, SCACBSOutputTable_::no_of_entries, SCACBSCtx_::output_table, SCACBSCtx_::parray, MpmCtx_::pattern_cnt, SCACBSCtx_::pid_pat_list, SCACBSOutputTable_::pids, MpmTableElmt_::Prepare, MpmTableElmt_::PrintCtx, MpmTableElmt_::PrintThreadCtx, MpmTableElmt_::RegisterUnittests, SC_AC_BS_FAIL, SC_AC_BS_STATE_TYPE_U16, SC_AC_BS_STATE_TYPE_U32, SC_ERR_AHO_CORASICK, SC_ERR_MEM_ALLOC, SCACBSAddPatternCI(), SCACBSAddPatternCS(), SCACBSDestroyCtx(), SCACBSDestroyThreadCtx(), SCACBSInitCtx(), SCACBSInitThreadCtx(), SCACBSPreparePatterns(), SCACBSPrintInfo(), SCACBSPrintSearchStats(), SCACBSRegisterTests(), SCACBSSearch(), SCFree, SCLogCritical, SCLogError, SCMalloc, SCRealloc, MpmTableElmt_::Search, SCACBSCtx_::single_state_size, SCACBSCtx_::state_count, STATE_QUEUE_CONTAINER_SIZE, SCACBSCtx_::state_table_mod, SCACBSCtx_::state_table_mod_pointers, SCACBSCtx_::state_table_u16, SCACBSCtx_::state_table_u32, StateQueue_::store, and StateQueue_::top.

Referenced by MpmTableSetup().

Here is the call graph for this function:

Here is the caller graph for this function:

int SCACBSAddPatternCI ( MpmCtx mpm_ctx,
uint8_t *  pat,
uint16_t  patlen,
uint16_t  offset,
uint16_t  depth,
uint32_t  pid,
SigIntId  sid,
uint8_t  flags 
)

Add a case insensitive pattern. Although we have different calls for adding case sensitive and insensitive patterns, we make a single call for either case. No special treatment for either case.

Parameters
mpm_ctxPointer to the mpm context.
patThe pattern to add.
patnenThe pattern length.
offsetIgnored.
depthIgnored.
pidThe pattern id.
sidIgnored.
flagsFlags associated with this pattern.
Return values
0On success.
-1On failure.

Definition at line 1348 of file util-mpm-ac-bs.c.

References MPM_PATTERN_FLAG_NOCASE, and MpmAddPattern().

Referenced by MpmACBSRegister().

Here is the call graph for this function:

Here is the caller graph for this function:

int SCACBSAddPatternCS ( MpmCtx mpm_ctx,
uint8_t *  pat,
uint16_t  patlen,
uint16_t  offset,
uint16_t  depth,
uint32_t  pid,
SigIntId  sid,
uint8_t  flags 
)

Add a case sensitive pattern. Although we have different calls for adding case sensitive and insensitive patterns, we make a single call for either case. No special treatment for either case.

Parameters
mpm_ctxPointer to the mpm context.
patThe pattern to add.
patnenThe pattern length.
offsetIgnored.
depthIgnored.
pidThe pattern id.
sidIgnored.
flagsFlags associated with this pattern.
Return values
0On success.
-1On failure.

Definition at line 1373 of file util-mpm-ac-bs.c.

References MpmAddPattern().

Referenced by MpmACBSRegister().

Here is the call graph for this function:

Here is the caller graph for this function:

void SCACBSDestroyThreadCtx ( MpmCtx mpm_ctx,
MpmThreadCtx mpm_thread_ctx 
)

Destroy the mpm thread context.

Parameters
mpm_ctxPointer to the mpm context.
mpm_thread_ctxPointer to the mpm thread context.

Definition at line 1033 of file util-mpm-ac-bs.c.

References MpmThreadCtx_::ctx, MpmThreadCtx_::memory_cnt, MpmThreadCtx_::memory_size, SCACBSPrintSearchStats(), and SCFree.

Referenced by MpmACBSRegister(), and SCACBSPrintInfo().

Here is the call graph for this function:

Here is the caller graph for this function:

void SCACBSInitCtx ( MpmCtx mpm_ctx)

Initialize the AC context.

Parameters
mpm_ctxMpm context.

Definition at line 999 of file util-mpm-ac-bs.c.

References MpmCtx_::ctx, MpmCtx_::init_hash, MpmCtx_::memory_cnt, MpmCtx_::memory_size, MPM_INIT_HASH_SIZE, SCMalloc, and SCReturn.

Referenced by MpmACBSRegister().

Here is the caller graph for this function:

void SCACBSInitThreadCtx ( MpmCtx mpm_ctx,
MpmThreadCtx mpm_thread_ctx 
)

Init the mpm thread context.

Parameters
mpm_ctxPointer to the mpm context.
mpm_thread_ctxPointer to the mpm thread context.
matchsizeWe don't need this.

Definition at line 979 of file util-mpm-ac-bs.c.

References MpmThreadCtx_::ctx, MpmThreadCtx_::memory_cnt, MpmThreadCtx_::memory_size, and SCMalloc.

Referenced by MpmACBSRegister(), and SCACBSPrintInfo().

Here is the caller graph for this function:

void SCACBSPrintSearchStats ( MpmThreadCtx mpm_thread_ctx)

Definition at line 1380 of file util-mpm-ac-bs.c.

References MpmThreadCtx_::ctx, SCACBSThreadCtx_::total_calls, and SCACBSThreadCtx_::total_matches.

Referenced by MpmACBSRegister(), and SCACBSDestroyThreadCtx().

Here is the caller graph for this function:

void SCACBSRegisterTests ( void  )

Definition at line 2477 of file util-mpm-ac-bs.c.

References UtRegisterTest().

Referenced by MpmACBSRegister().

Here is the call graph for this function:

Here is the caller graph for this function:

uint32_t SCACBSSearch ( const MpmCtx mpm_ctx,
MpmThreadCtx mpm_thread_ctx,
PrefilterRuleStore pmq,
const uint8_t *  buf,
uint32_t  buflen 
)

The aho corasick search function.

Parameters
mpm_ctxPointer to the mpm context.
mpm_thread_ctxPointer to the mpm thread context.
pmqPointer to the Pattern Matcher Queue to hold search matches.
bufBuffer to be searched.
buflenBuffer length.
Return values
matchesMatch count.

Definition at line 1145 of file util-mpm-ac-bs.c.

References MpmCtx_::ctx, SCACBSOutputTable_::no_of_entries, SCACBSCtx_::output_table, SCACBSCtx_::pattern_id_bitarray_size, SCACBSCtx_::pid_pat_list, SCACBSOutputTable_::pids, SC_AC_BS_STATE_TYPE_U16, SC_AC_BS_STATE_TYPE_U32, SCMemcmp, SCACBSCtx_::state_count, SCACBSCtx_::state_table_mod_pointers, and u8_tolower.

Referenced by MpmACBSRegister(), and SCACBSPrintInfo().

Here is the caller graph for this function: