#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:

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 anoopsaldanha@gmail.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()

void MpmACRegister ( void )

Register the aho-corasick mpm.

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

References MpmTableElmt_::AddPattern, MpmTableElmt_::AddPatternNocase, MpmTableElmt_::DestroyCtx, MpmTableElmt_::InitCtx, MPM_AC, mpm_table, MpmTableElmt_::name, MpmTableElmt_::Prepare, MpmTableElmt_::PrintCtx, MpmTableElmt_::RegisterUnittests, SCACAddPatternCI(), SCACAddPatternCS(), SCACDestroyCtx(), SCACInitCtx(), SCACPreparePatterns(), SCACPrintInfo(), SCACSearch(), and MpmTableElmt_::Search.

Referenced by MpmTableSetup().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ 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_ctx	Pointer to the mpm context.
pat	The pattern to add.
patnen	The pattern length.
offset	Ignored.
depth	Ignored.
pid	The pattern id.
sid	Ignored.
flags	Flags associated with this pattern.

Return values

0	On success.
-1	On failure.

Definition at line 1068 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_ctx	Pointer to the mpm context.
pat	The pattern to add.
patnen	The pattern length.
offset	Ignored.
depth	Ignored.
pid	The pattern id.
sid	Ignored.
flags	Flags associated with this pattern.

Return values

0	On success.
-1	On failure.

Definition at line 1093 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_ctx Pointer to the mpm context.

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

References SCACPatternList_::cs, MpmCtx_::ctx, MpmCtx_::init_hash, MpmCtx_::max_pat_id, MpmCtx_::memory_cnt, MpmCtx_::memory_size, MPM_INIT_HASH_SIZE, MpmFreePattern(), SCACCtx_::output_table, SCACCtx_::parray, MpmCtx_::pattern_cnt, SCACCtx_::pid_pat_list, SCACOutputTable_::pids, SC_AC_STATE_TYPE_U16, SC_AC_STATE_TYPE_U32, SCFree, SCACPatternList_::sids, SCACCtx_::state_count, SCACCtx_::state_table_u16, and SCACCtx_::state_table_u32.

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_ctx Mpm context.

Definition at line 824 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_ctx Pointer to the mpm context.

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

References SCACPatternList_::cs, MpmCtx_::ctx, SCACPatternList_::depth, MpmPattern_::depth, SCACPatternList_::endswith, FatalError, MpmPattern_::flags, MpmPattern_::id, MpmCtx_::init_hash, MpmPattern_::len, MpmCtx_::max_pat_id, MpmCtx_::memory_cnt, MpmCtx_::memory_size, MPM_INIT_HASH_SIZE, MPM_PATTERN_FLAG_ENDSWITH, MPM_PATTERN_FLAG_NOCASE, MpmPattern_::next, SCACPatternList_::offset, MpmPattern_::offset, MpmPattern_::original_pat, SCACCtx_::parray, SCACPatternList_::patlen, MpmCtx_::pattern_cnt, SCACCtx_::pid_pat_list, SCCalloc, SCFree, SCLogDebug, SCMalloc, SCACPatternList_::sids, MpmPattern_::sids, SCACPatternList_::sids_size, MpmPattern_::sids_size, and SCACCtx_::single_state_size.

Referenced by MpmACRegister().

Here is the caller graph for this function:

◆ SCACPrintInfo()

void SCACPrintInfo ( MpmCtx * mpm_ctx )

Definition at line 1100 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:

◆ 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_ctx	Pointer to the mpm context.
mpm_thread_ctx	Pointer to the mpm thread context.
pmq	Pointer to the Pattern Matcher Queue to hold search matches.
buf	Buffer to be searched.
buflen	Buffer length.

Return values

matches Match count: counts unique matches per pattern.

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

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

Referenced by MpmACRegister().

Here is the caller graph for this function:

Data Structures

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

◆ AC_CASE_BIT

◆ AC_CASE_MASK

◆ AC_PID_MASK

◆ SC_AC_FAIL

◆ STATE_QUEUE_CONTAINER_SIZE

Typedef Documentation

◆ StateQueue

Function Documentation

◆ MpmACRegister()

◆ SCACAddPatternCI()

◆ SCACAddPatternCS()

◆ SCACDestroyCtx()

◆ SCACInitCtx()

◆ SCACPreparePatterns()

◆ SCACPrintInfo()

◆ SCACSearch()