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

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 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 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_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 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_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 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 SCACBSDestroyCtx ( MpmCtx * mpm_ctx )

Destroy the mpm context.

Parameters

mpm_ctx Pointer to the mpm context.

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

References SCACBSPatternList_::cs, MpmCtx_::ctx, MpmCtx_::init_hash, MpmCtx_::max_pat_id, MpmCtx_::memory_cnt, MpmCtx_::memory_size, MPM_INIT_HASH_SIZE, MpmFreePattern(), SCACBSCtx_::output_table, SCACBSCtx_::parray, MpmCtx_::pattern_cnt, SCACBSCtx_::pid_pat_list, SCACBSOutputTable_::pids, SC_AC_BS_STATE_TYPE_U16, SC_AC_BS_STATE_TYPE_U32, SCFree, SCACBSPatternList_::sids, SCACBSCtx_::state_count, SCACBSCtx_::state_table_mod, SCACBSCtx_::state_table_mod_pointers, SCACBSCtx_::state_table_u16, and SCACBSCtx_::state_table_u32.

Referenced by MpmACBSRegister(), and SCACBSPrintInfo().

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_ctx	Pointer to the mpm context.
mpm_thread_ctx	Pointer 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_ctx Mpm 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_ctx	Pointer to the mpm context.
mpm_thread_ctx	Pointer to the mpm thread context.
matchsize	We 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:

int SCACBSPreparePatterns ( 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 888 of file util-mpm-ac-bs.c.

References SCACBSPatternList_::cs, MpmCtx_::ctx, 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_NOCASE, MpmFreePattern(), MpmPattern_::next, MpmPattern_::original_pat, SCACBSCtx_::parray, SCACBSPatternList_::patlen, MpmCtx_::pattern_cnt, SCACBSCtx_::pattern_id_bitarray_size, SCACBSCtx_::pid_pat_list, SC_ERR_MEM_ALLOC, SCFree, SCLogDebug, SCLogError, SCMalloc, SCACBSPatternList_::sids, MpmPattern_::sids, SCACBSPatternList_::sids_size, MpmPattern_::sids_size, and SCACBSCtx_::single_state_size.

Referenced by MpmACBSRegister(), and SCACBSPrintInfo().

Here is the call graph for this function:

Here is the caller graph for this function:

void SCACBSPrintInfo ( MpmCtx * mpm_ctx )

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

References MpmCtx_::ctx, DE_QUIET, DetectEngineCtxFree(), DetectEngineCtxInit(), DetectEngineThreadCtxDeinit(), DetectEngineThreadCtxInit(), DetectEngineCtx_::flags, MpmCtx_::maxlen, MpmCtx_::memory_cnt, MpmCtx_::memory_size, MpmCtx_::minlen, MPM_AC_BS, DetectEngineCtx_::mpm_matcher, MpmAddPatternCI(), MpmAddPatternCS(), MpmInitCtx(), Signature_::next, PacketAlertCheck(), MpmCtx_::pattern_cnt, PmqFree(), PmqSetup(), SCACBSDestroyCtx(), SCACBSDestroyThreadCtx(), SCACBSInitThreadCtx(), SCACBSPreparePatterns(), SCACBSSearch(), DetectEngineCtx_::sig_list, SigCleanSignatures(), SigGroupBuild(), SigGroupCleanup(), SigInit(), SigMatchSignatures(), SCACBSCtx_::state_count, UTHBuildPacket(), and UTHFreePackets().

Referenced by MpmACBSRegister().

Here is the call graph for this function:

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_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.

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:

Data Structures

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

Typedef Documentation

Function Documentation