suricata
util-mpm-ac.c File Reference
#include "suricata-common.h"
#include "suricata.h"
#include "detect.h"
#include "detect-parse.h"
#include "detect-engine.h"
#include "detect-engine-build.h"
#include "conf.h"
#include "util-debug.h"
#include "util-unittest.h"
#include "util-unittest-helper.h"
#include "util-memcmp.h"
#include "util-mpm-ac.h"
#include "util-memcpy.h"
#include "util-validate.h"
#include "detect-engine-alert.h"
Include dependency graph for util-mpm-ac.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_FAIL   (-1)
 
#define STATE_QUEUE_CONTAINER_SIZE   65536
 
#define AC_CASE_MASK   0x80000000
 
#define AC_PID_MASK   0x7FFFFFFF
 
#define AC_CASE_BIT   31
 

Typedefs

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

Functions

void SCACInitCtx (MpmCtx *mpm_ctx)
 Initialize the AC context. More...
 
void SCACDestroyCtx (MpmCtx *mpm_ctx)
 Destroy the mpm context. More...
 
int SCACAddPatternCI (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 SCACAddPatternCS (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 SCACPreparePatterns (MpmCtx *mpm_ctx)
 Process the patterns added to the mpm, and create the internal tables. More...
 
uint32_t SCACSearch (const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
 The aho corasick search function. More...
 
void SCACPrintInfo (MpmCtx *mpm_ctx)
 
void MpmACRegister (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 analysis 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-sensitive 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.c.

Macro Definition Documentation

◆ AC_CASE_BIT

#define AC_CASE_BIT   31

Definition at line 87 of file util-mpm-ac.c.

◆ AC_CASE_MASK

#define AC_CASE_MASK   0x80000000

Definition at line 85 of file util-mpm-ac.c.

◆ AC_PID_MASK

#define AC_PID_MASK   0x7FFFFFFF

Definition at line 86 of file util-mpm-ac.c.

◆ SC_AC_FAIL

#define SC_AC_FAIL   (-1)

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

◆ STATE_QUEUE_CONTAINER_SIZE

#define STATE_QUEUE_CONTAINER_SIZE   65536

Definition at line 83 of file util-mpm-ac.c.

Typedef Documentation

◆ StateQueue

typedef struct StateQueue_ StateQueue

Helper structure used by AC during state table creation.

Function Documentation

◆ MpmACRegister()

◆ SCACAddPatternCI()

int SCACAddPatternCI ( 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 1040 of file util-mpm-ac.c.

References flags, MPM_PATTERN_FLAG_NOCASE, MpmAddPattern(), and offset.

Referenced by MpmACRegister().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ SCACAddPatternCS()

int SCACAddPatternCS ( 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 1065 of file util-mpm-ac.c.

References flags, MpmAddPattern(), and offset.

Referenced by MpmACRegister().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ SCACDestroyCtx()

void SCACDestroyCtx ( MpmCtx mpm_ctx)

Destroy the mpm context.

Parameters
mpm_ctxPointer to the mpm context.

Definition at line 829 of file util-mpm-ac.c.

References ctx, MpmCtx_::ctx, MpmCtx_::init_hash, MpmCtx_::max_pat_id, MpmCtx_::memory_cnt, MpmCtx_::memory_size, MPM_INIT_HASH_SIZE, MpmFreePattern(), MpmCtx_::pattern_cnt, SC_AC_STATE_TYPE_U16, SC_AC_STATE_TYPE_U32, and SCFree.

Referenced by MpmACRegister().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ SCACInitCtx()

void SCACInitCtx ( MpmCtx mpm_ctx)

Initialize the AC context.

Parameters
mpm_ctxMpm context.

Definition at line 798 of file util-mpm-ac.c.

References MpmCtx_::ctx, MpmCtx_::init_hash, MpmCtx_::memory_cnt, MpmCtx_::memory_size, MPM_INIT_HASH_SIZE, and SCCalloc.

Referenced by MpmACRegister().

Here is the caller graph for this function:

◆ SCACPreparePatterns()

int SCACPreparePatterns ( MpmCtx mpm_ctx)

Process the patterns added to the mpm, and create the internal tables.

Parameters
mpm_ctxPointer to the mpm context.

Definition at line 705 of file util-mpm-ac.c.

References ctx, MpmCtx_::ctx, FatalError, MpmCtx_::init_hash, MpmCtx_::max_pat_id, MpmCtx_::memory_cnt, MpmCtx_::memory_size, MPM_INIT_HASH_SIZE, MPM_PATTERN_FLAG_ENDSWITH, MPM_PATTERN_FLAG_NOCASE, MpmPattern_::next, MpmCtx_::pattern_cnt, SCCalloc, SCFree, SCLogDebug, and SCMalloc.

Referenced by MpmACRegister().

Here is the caller graph for this function:

◆ SCACPrintInfo()

void SCACPrintInfo ( MpmCtx mpm_ctx)

Definition at line 1072 of file util-mpm-ac.c.

References ctx, MpmCtx_::ctx, MpmCtx_::maxlen, MpmCtx_::memory_cnt, MpmCtx_::memory_size, MpmCtx_::minlen, and MpmCtx_::pattern_cnt.

Referenced by MpmACRegister().

Here is the caller graph for this function:

◆ SCACSearch()

uint32_t SCACSearch ( 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: counts unique matches per pattern.

Definition at line 912 of file util-mpm-ac.c.

References AC_CASE_MASK, AC_PID_MASK, SCACPatternList_::cs, ctx, MpmCtx_::ctx, SCACPatternList_::depth, SCACPatternList_::endswith, offset, SCACPatternList_::offset, SCACPatternList_::patlen, SC_AC_STATE_TYPE_U16, SCMemcmp, and u8_tolower.

Referenced by MpmACRegister().

Here is the caller graph for this function: