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 "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 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 SCACInitThreadCtx (MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx)
 Init the mpm thread context. More...
 
void SCACDestroyCtx (MpmCtx *mpm_ctx)
 Destroy the mpm context. More...
 
void SCACDestroyThreadCtx (MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx)
 Destroy the mpm thread 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 SCACPrintSearchStats (MpmThreadCtx *mpm_thread_ctx)
 
void SCACRegisterTests (void)
 
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 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.c.

Macro Definition Documentation

#define AC_CASE_BIT   31

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

#define AC_CASE_MASK   0x80000000

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

Referenced by SCACSearch().

#define AC_PID_MASK   0x7FFFFFFF

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

Referenced by SCACSearch().

#define SC_AC_FAIL   (-1)

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

#define STATE_QUEUE_CONTAINER_SIZE   65536

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

Typedef Documentation

typedef struct StateQueue_ StateQueue

Helper structure used by AC during state table creation.

Function Documentation

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 1167 of file util-mpm-ac.c.

References MPM_PATTERN_FLAG_NOCASE, and MpmAddPattern().

Referenced by MpmACRegister().

Here is the call graph for this function:

Here is the caller graph for this function:

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 1192 of file util-mpm-ac.c.

References MpmAddPattern().

Referenced by MpmACRegister().

Here is the call graph for this function:

Here is the caller graph for this function:

void SCACDestroyCtx ( MpmCtx mpm_ctx)
void SCACDestroyThreadCtx ( 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 926 of file util-mpm-ac.c.

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

Referenced by MpmACRegister().

Here is the call graph for this function:

Here is the caller graph for this function:

void SCACInitCtx ( MpmCtx mpm_ctx)

Initialize the AC context.

Parameters
mpm_ctxMpm context.

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

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

Referenced by MpmACRegister().

Here is the caller graph for this function:

void SCACInitThreadCtx ( 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 872 of file util-mpm-ac.c.

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

Referenced by MpmACRegister().

Here is the caller graph for this function:

void SCACPrintInfo ( MpmCtx mpm_ctx)

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

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

Referenced by MpmACRegister().

Here is the caller graph for this function:

void SCACPrintSearchStats ( MpmThreadCtx mpm_thread_ctx)

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

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

Referenced by MpmACRegister(), and SCACDestroyThreadCtx().

Here is the caller graph for this function:

void SCACRegisterTests ( void  )

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

References UtRegisterTest().

Referenced by MpmACRegister().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

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

References AC_CASE_MASK, AC_PID_MASK, SCACPatternList_::cs, MpmCtx_::ctx, SCACPatternList_::depth, SCACOutputTable_::no_of_entries, SCACPatternList_::offset, offset, SCACCtx_::output_table, SCACPatternList_::patlen, SCACCtx_::pattern_id_bitarray_size, SCACCtx_::pid_pat_list, SCACOutputTable_::pids, SC_AC_STATE_TYPE_U16, SC_AC_STATE_TYPE_U32, SCMemcmp, SCACPatternList_::sids, SCACPatternList_::sids_size, SCACCtx_::state_count, SCACCtx_::state_table_u16, SCACCtx_::state_table_u32, and u8_tolower.

Referenced by MpmACRegister().

Here is the caller graph for this function: