suricata
util-mpm-ac.c
Go to the documentation of this file.
1 /* Copyright (C) 2007-2014 Open Information Security Foundation
2  *
3  * You can copy, redistribute or modify this Program under the terms of
4  * the GNU General Public License version 2 as published by the Free
5  * Software Foundation.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * version 2 along with this program; if not, write to the Free Software
14  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
15  * 02110-1301, USA.
16  */
17 
18 /**
19  * \file
20  *
21  * \author Anoop Saldanha <anoopsaldanha@gmail.com>
22  *
23  * First iteration of aho-corasick MPM from -
24  *
25  * Efficient String Matching: An Aid to Bibliographic Search
26  * Alfred V. Aho and Margaret J. Corasick
27  *
28  * - Uses the delta table for calculating transitions, instead of having
29  * separate goto and failure transitions.
30  * - If we cross 2 ** 16 states, we use 4 bytes in the transition table
31  * to hold each state, otherwise we use 2 bytes.
32  * - This version of the MPM is heavy on memory, but it performs well.
33  * If you can fit the ruleset with this mpm on your box without hitting
34  * swap, this is the MPM to go for.
35  *
36  * \todo - Do a proper analyis of our existing MPMs and suggest a good one based
37  * on the pattern distribution and the expected traffic(say http).
38  * - Tried out loop unrolling without any perf increase. Need to dig deeper.
39  * - Irrespective of whether we cross 2 ** 16 states or not,shift to using
40  * uint32_t for state type, so that we can integrate it's status as a
41  * final state or not in the topmost byte. We are already doing it if
42  * state_count is > 2 ** 16.
43  * - Test case-senstive patterns if they have any ascii chars. If they
44  * don't treat them as nocase.
45  * - Carry out other optimizations we are working on. hashes, compression.
46  */
47 
48 #include "suricata-common.h"
49 #include "suricata.h"
50 
51 #include "detect.h"
52 #include "detect-parse.h"
53 #include "detect-engine.h"
54 
55 #include "conf.h"
56 #include "util-debug.h"
57 #include "util-unittest.h"
58 #include "util-unittest-helper.h"
59 #include "util-memcmp.h"
60 #include "util-mpm-ac.h"
61 #include "util-memcpy.h"
62 #include "util-validate.h"
63 
64 void SCACInitCtx(MpmCtx *);
66 void SCACDestroyCtx(MpmCtx *);
68 int SCACAddPatternCI(MpmCtx *, uint8_t *, uint16_t, uint16_t, uint16_t,
69  uint32_t, SigIntId, uint8_t);
70 int SCACAddPatternCS(MpmCtx *, uint8_t *, uint16_t, uint16_t, uint16_t,
71  uint32_t, SigIntId, uint8_t);
72 int SCACPreparePatterns(MpmCtx *mpm_ctx);
73 uint32_t SCACSearch(const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx,
74  PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen);
75 void SCACPrintInfo(MpmCtx *mpm_ctx);
76 void SCACPrintSearchStats(MpmThreadCtx *mpm_thread_ctx);
77 void SCACRegisterTests(void);
78 
79 /* a placeholder to denote a failure transition in the goto table */
80 #define SC_AC_FAIL (-1)
81 
82 #define STATE_QUEUE_CONTAINER_SIZE 65536
83 
84 #define AC_CASE_MASK 0x80000000
85 #define AC_PID_MASK 0x7FFFFFFF
86 #define AC_CASE_BIT 31
87 
88 static int construct_both_16_and_32_state_tables = 0;
89 
90 /**
91  * \brief Helper structure used by AC during state table creation
92  */
93 typedef struct StateQueue_ {
95  int top;
96  int bot;
98 
99 /**
100  * \internal
101  * \brief Initialize the AC context with user specified conf parameters. We
102  * aren't retrieving anything for AC conf now, but we will certainly
103  * need it, when we customize AC.
104  */
105 static void SCACGetConfig(void)
106 {
107  //ConfNode *ac_conf;
108  //const char *hash_val = NULL;
109 
110  //ConfNode *pm = ConfGetNode("pattern-matcher");
111 
112  return;
113 }
114 
115 /**
116  * \internal
117  * \brief Check if size_t multiplication would overflow and perform operation
118  * if safe. In case of an overflow we exit().
119  *
120  * \param a First size_t value to multiplicate.
121  * \param b Second size_t value to multiplicate.
122  *
123  * \retval The product of a and b, guaranteed to not overflow.
124  */
125 static inline size_t SCACCheckSafeSizetMult(size_t a, size_t b)
126 {
127  /* check for safety of multiplication operation */
128  if (b > 0 && a > SIZE_MAX / b) {
129  SCLogError(SC_ERR_MEM_ALLOC, "%"PRIuMAX" * %"PRIuMAX" > %"
130  PRIuMAX" would overflow size_t calculating buffer size",
131  (uintmax_t) a, (uintmax_t) b, (uintmax_t) SIZE_MAX);
132  exit(EXIT_FAILURE);
133  }
134  return a * b;
135 }
136 
137 /**
138  * \internal
139  * \brief Initialize a new state in the goto and output tables.
140  *
141  * \param mpm_ctx Pointer to the mpm context.
142  *
143  * \retval The state id, of the newly created state.
144  */
145 static inline int SCACReallocState(SCACCtx *ctx, uint32_t cnt)
146 {
147  void *ptmp = NULL;
148  size_t size = 0;
149 
150  /* reallocate space in the goto table to include a new state */
151  size = SCACCheckSafeSizetMult((size_t) cnt, (size_t) ctx->single_state_size);
152  if (size > 0)
153  ptmp = SCRealloc(ctx->goto_table, size);
154  if (ptmp == NULL) {
155  SCFree(ctx->goto_table);
156  ctx->goto_table = NULL;
157  FatalError(SC_ERR_FATAL, "Error allocating memory");
158  }
159  ctx->goto_table = ptmp;
160 
161  /* reallocate space in the output table for the new state */
162  size_t oldsize = SCACCheckSafeSizetMult((size_t) ctx->state_count,
163  sizeof(SCACOutputTable));
164  size = SCACCheckSafeSizetMult((size_t) cnt, sizeof(SCACOutputTable));
165  SCLogDebug("oldsize %"PRIuMAX" size %"PRIuMAX" cnt %d ctx->state_count %u",
166  (uintmax_t) oldsize, (uintmax_t) size, cnt, ctx->state_count);
167 
168  ptmp = NULL;
169  if (size > 0)
170  ptmp = SCRealloc(ctx->output_table, size);
171  if (ptmp == NULL) {
172  SCFree(ctx->output_table);
173  ctx->output_table = NULL;
174  FatalError(SC_ERR_FATAL, "Error allocating memory");
175  }
176  ctx->output_table = ptmp;
177 
178  memset(((uint8_t *)ctx->output_table + oldsize), 0, (size - oldsize));
179 
180  /* \todo using it temporarily now during dev, since I have restricted
181  * state var in SCACCtx->state_table to uint16_t. */
182  //if (ctx->state_count > 65536) {
183  // printf("state count exceeded\n");
184  // exit(EXIT_FAILURE);
185  //}
186 
187  return 0;//ctx->state_count++;
188 }
189 
190 /** \internal
191  * \brief Shrink state after setup is done
192  *
193  * Shrinks only the output table, goto table is freed after calling this
194  */
195 static void SCACShrinkState(SCACCtx *ctx)
196 {
197  /* reallocate space in the output table for the new state */
198 #ifdef DEBUG
199  int oldsize = ctx->allocated_state_count * sizeof(SCACOutputTable);
200 #endif
201  int newsize = ctx->state_count * sizeof(SCACOutputTable);
202 
203  SCLogDebug("oldsize %d newsize %d ctx->allocated_state_count %u "
204  "ctx->state_count %u: shrink by %d bytes", oldsize,
205  newsize, ctx->allocated_state_count, ctx->state_count,
206  oldsize - newsize);
207 
208  void *ptmp = SCRealloc(ctx->output_table, newsize);
209  if (ptmp == NULL) {
210  SCFree(ctx->output_table);
211  ctx->output_table = NULL;
212  FatalError(SC_ERR_FATAL, "Error allocating memory");
213  }
214  ctx->output_table = ptmp;
215 }
216 
217 static inline int SCACInitNewState(MpmCtx *mpm_ctx)
218 {
219  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;;
220 
221  /* Exponentially increase the allocated space when needed. */
222  if (ctx->allocated_state_count < ctx->state_count + 1) {
223  if (ctx->allocated_state_count == 0)
224  ctx->allocated_state_count = 256;
225  else
226  ctx->allocated_state_count *= 2;
227 
228  SCACReallocState(ctx, ctx->allocated_state_count);
229 
230  }
231 #if 0
232  if (ctx->allocated_state_count > 260) {
233  SCACOutputTable *output_state = &ctx->output_table[260];
234  SCLogInfo("output_state %p %p %u", output_state, output_state->pids, output_state->no_of_entries);
235  }
236 #endif
237  int ascii_code = 0;
238  /* set all transitions for the newly assigned state as FAIL transitions */
239  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
240  ctx->goto_table[ctx->state_count][ascii_code] = SC_AC_FAIL;
241  }
242 
243  return ctx->state_count++;
244 }
245 
246 /**
247  * \internal
248  * \brief Adds a pid to the output table for a state.
249  *
250  * \param state The state to whose output table we should add the pid.
251  * \param pid The pattern id to add.
252  * \param mpm_ctx Pointer to the mpm context.
253  */
254 static void SCACSetOutputState(int32_t state, uint32_t pid, MpmCtx *mpm_ctx)
255 {
256  void *ptmp;
257  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
258  SCACOutputTable *output_state = &ctx->output_table[state];
259  uint32_t i = 0;
260 
261  for (i = 0; i < output_state->no_of_entries; i++) {
262  if (output_state->pids[i] == pid)
263  return;
264  }
265 
266  output_state->no_of_entries++;
267  ptmp = SCRealloc(output_state->pids,
268  output_state->no_of_entries * sizeof(uint32_t));
269  if (ptmp == NULL) {
270  SCFree(output_state->pids);
271  output_state->pids = NULL;
272  FatalError(SC_ERR_FATAL, "Error allocating memory");
273  }
274  output_state->pids = ptmp;
275 
276  output_state->pids[output_state->no_of_entries - 1] = pid;
277 
278  return;
279 }
280 
281 /**
282  * \brief Helper function used by SCACCreateGotoTable. Adds a pattern to the
283  * goto table.
284  *
285  * \param pattern Pointer to the pattern.
286  * \param pattern_len Pattern length.
287  * \param pid The pattern id, that corresponds to this pattern. We
288  * need it to updated the output table for this pattern.
289  * \param mpm_ctx Pointer to the mpm context.
290  */
291 static inline void SCACEnter(uint8_t *pattern, uint16_t pattern_len, uint32_t pid,
292  MpmCtx *mpm_ctx)
293 {
294  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
295  int32_t state = 0;
296  int32_t newstate = 0;
297  int i = 0;
298  int p = 0;
299 
300  /* walk down the trie till we have a match for the pattern prefix */
301  state = 0;
302  for (i = 0; i < pattern_len; i++) {
303  if (ctx->goto_table[state][pattern[i]] != SC_AC_FAIL) {
304  state = ctx->goto_table[state][pattern[i]];
305  } else {
306  break;
307  }
308  }
309 
310  /* add the non-matching pattern suffix to the trie, from the last state
311  * we left off */
312  for (p = i; p < pattern_len; p++) {
313  newstate = SCACInitNewState(mpm_ctx);
314  ctx->goto_table[state][pattern[p]] = newstate;
315  state = newstate;
316  }
317 
318  /* add this pattern id, to the output table of the last state, where the
319  * pattern ends in the trie */
320  SCACSetOutputState(state, pid, mpm_ctx);
321 
322  return;
323 }
324 
325 /**
326  * \internal
327  * \brief Create the goto table.
328  *
329  * \param mpm_ctx Pointer to the mpm context.
330  */
331 static inline void SCACCreateGotoTable(MpmCtx *mpm_ctx)
332 {
333  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
334  uint32_t i = 0;
335 
336  /* add each pattern to create the goto table */
337  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
338  SCACEnter(ctx->parray[i]->ci, ctx->parray[i]->len,
339  ctx->parray[i]->id, mpm_ctx);
340  }
341 
342  int ascii_code = 0;
343  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
344  if (ctx->goto_table[0][ascii_code] == SC_AC_FAIL) {
345  ctx->goto_table[0][ascii_code] = 0;
346  }
347  }
348 
349  return;
350 }
351 
352 static inline void SCACDetermineLevel1Gap(MpmCtx *mpm_ctx)
353 {
354  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
355  uint32_t u = 0;
356 
357  int map[256];
358  memset(map, 0, sizeof(map));
359 
360  for (u = 0; u < mpm_ctx->pattern_cnt; u++)
361  map[ctx->parray[u]->ci[0]] = 1;
362 
363  for (u = 0; u < 256; u++) {
364  if (map[u] == 0)
365  continue;
366  int32_t newstate = SCACInitNewState(mpm_ctx);
367  ctx->goto_table[0][u] = newstate;
368  }
369 
370  return;
371 }
372 
373 static inline int SCACStateQueueIsEmpty(StateQueue *q)
374 {
375  if (q->top == q->bot)
376  return 1;
377  else
378  return 0;
379 }
380 
381 static inline void SCACEnqueue(StateQueue *q, int32_t state)
382 {
383  int i = 0;
384 
385  /*if we already have this */
386  for (i = q->bot; i < q->top; i++) {
387  if (q->store[i] == state)
388  return;
389  }
390 
391  q->store[q->top++] = state;
392 
394  q->top = 0;
395 
396  if (q->top == q->bot) {
397  SCLogCritical(SC_ERR_AHO_CORASICK, "Just ran out of space in the queue. "
398  "Fatal Error. Exiting. Please file a bug report on this");
399  exit(EXIT_FAILURE);
400  }
401 
402  return;
403 }
404 
405 static inline int32_t SCACDequeue(StateQueue *q)
406 {
408  q->bot = 0;
409 
410  if (q->bot == q->top) {
411  SCLogCritical(SC_ERR_AHO_CORASICK, "StateQueue behaving weirdly. "
412  "Fatal Error. Exiting. Please file a bug report on this");
413  exit(EXIT_FAILURE);
414  }
415 
416  return q->store[q->bot++];
417 }
418 
419 /*
420 #define SCACStateQueueIsEmpty(q) (((q)->top == (q)->bot) ? 1 : 0)
421 
422 #define SCACEnqueue(q, state) do { \
423  int i = 0; \
424  \
425  for (i = (q)->bot; i < (q)->top; i++) { \
426  if ((q)->store[i] == state) \
427  return; \
428  } \
429  \
430  (q)->store[(q)->top++] = state; \
431  \
432  if ((q)->top == STATE_QUEUE_CONTAINER_SIZE) \
433  (q)->top = 0; \
434  \
435  if ((q)->top == (q)->bot) { \
436  SCLogCritical(SC_ERR_AHO_CORASICK, "Just ran out of space in the queue. " \
437  "Fatal Error. Exiting. Please file a bug report on this"); \
438  exit(EXIT_FAILURE); \
439  } \
440  } while (0)
441 
442 #define SCACDequeue(q) ( (((q)->bot == STATE_QUEUE_CONTAINER_SIZE)? ((q)->bot = 0): 0), \
443  (((q)->bot == (q)->top) ? \
444  (printf("StateQueue behaving " \
445  "weirdly. Fatal Error. Exiting. Please " \
446  "file a bug report on this"), \
447  exit(EXIT_FAILURE)) : 0), \
448  (q)->store[(q)->bot++]) \
449 */
450 
451 /**
452  * \internal
453  * \brief Club the output data from 2 states and store it in the 1st state.
454  * dst_state_data = {dst_state_data} UNION {src_state_data}
455  *
456  * \param dst_state First state(also the destination) for the union operation.
457  * \param src_state Second state for the union operation.
458  * \param mpm_ctx Pointer to the mpm context.
459  */
460 static inline void SCACClubOutputStates(int32_t dst_state, int32_t src_state,
461  MpmCtx *mpm_ctx)
462 {
463  void *ptmp;
464  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
465  uint32_t i = 0;
466  uint32_t j = 0;
467 
468  SCACOutputTable *output_dst_state = &ctx->output_table[dst_state];
469  SCACOutputTable *output_src_state = &ctx->output_table[src_state];
470 
471  for (i = 0; i < output_src_state->no_of_entries; i++) {
472  for (j = 0; j < output_dst_state->no_of_entries; j++) {
473  if (output_src_state->pids[i] == output_dst_state->pids[j]) {
474  break;
475  }
476  }
477  if (j == output_dst_state->no_of_entries) {
478  output_dst_state->no_of_entries++;
479 
480  ptmp = SCRealloc(output_dst_state->pids,
481  (output_dst_state->no_of_entries * sizeof(uint32_t)));
482  if (ptmp == NULL) {
483  SCFree(output_dst_state->pids);
484  output_dst_state->pids = NULL;
485  FatalError(SC_ERR_FATAL, "Error allocating memory");
486  }
487  output_dst_state->pids = ptmp;
488 
489  output_dst_state->pids[output_dst_state->no_of_entries - 1] =
490  output_src_state->pids[i];
491  }
492  }
493 
494  return;
495 }
496 
497 /**
498  * \internal
499  * \brief Create the failure table.
500  *
501  * \param mpm_ctx Pointer to the mpm context.
502  */
503 static inline void SCACCreateFailureTable(MpmCtx *mpm_ctx)
504 {
505  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
506  int ascii_code = 0;
507  int32_t state = 0;
508  int32_t r_state = 0;
509 
510  StateQueue q;
511  memset(&q, 0, sizeof(StateQueue));
512 
513  /* allot space for the failure table. A failure entry in the table for
514  * every state(SCACCtx->state_count) */
515  ctx->failure_table = SCMalloc(ctx->state_count * sizeof(int32_t));
516  if (ctx->failure_table == NULL) {
517  FatalError(SC_ERR_FATAL, "Error allocating memory");
518  }
519  memset(ctx->failure_table, 0, ctx->state_count * sizeof(int32_t));
520 
521  /* add the failure transitions for the 0th state, and add every non-fail
522  * transition from the 0th state to the queue for further processing
523  * of failure states */
524  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
525  int32_t temp_state = ctx->goto_table[0][ascii_code];
526  if (temp_state != 0) {
527  SCACEnqueue(&q, temp_state);
528  ctx->failure_table[temp_state] = 0;
529  }
530  }
531 
532  while (!SCACStateQueueIsEmpty(&q)) {
533  /* pick up every state from the queue and add failure transitions */
534  r_state = SCACDequeue(&q);
535  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
536  int32_t temp_state = ctx->goto_table[r_state][ascii_code];
537  if (temp_state == SC_AC_FAIL)
538  continue;
539  SCACEnqueue(&q, temp_state);
540  state = ctx->failure_table[r_state];
541 
542  while(ctx->goto_table[state][ascii_code] == SC_AC_FAIL)
543  state = ctx->failure_table[state];
544  ctx->failure_table[temp_state] = ctx->goto_table[state][ascii_code];
545  SCACClubOutputStates(temp_state, ctx->failure_table[temp_state],
546  mpm_ctx);
547  }
548  }
549 
550  return;
551 }
552 
553 /**
554  * \internal
555  * \brief Create the delta table.
556  *
557  * \param mpm_ctx Pointer to the mpm context.
558  */
559 static inline void SCACCreateDeltaTable(MpmCtx *mpm_ctx)
560 {
561  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
562  int ascii_code = 0;
563  int32_t r_state = 0;
564 
565  if ((ctx->state_count < 32767) || construct_both_16_and_32_state_tables) {
566  ctx->state_table_u16 = SCMalloc(ctx->state_count *
567  sizeof(SC_AC_STATE_TYPE_U16) * 256);
568  if (ctx->state_table_u16 == NULL) {
569  FatalError(SC_ERR_FATAL, "Error allocating memory");
570  }
571  memset(ctx->state_table_u16, 0,
572  ctx->state_count * sizeof(SC_AC_STATE_TYPE_U16) * 256);
573 
574  mpm_ctx->memory_cnt++;
575  mpm_ctx->memory_size += (ctx->state_count *
576  sizeof(SC_AC_STATE_TYPE_U16) * 256);
577 
578  StateQueue q;
579  memset(&q, 0, sizeof(StateQueue));
580 
581  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
582  DEBUG_VALIDATE_BUG_ON(ctx->goto_table[0][ascii_code] > UINT16_MAX);
583  SC_AC_STATE_TYPE_U16 temp_state = (uint16_t)ctx->goto_table[0][ascii_code];
584  ctx->state_table_u16[0][ascii_code] = temp_state;
585  if (temp_state != 0)
586  SCACEnqueue(&q, temp_state);
587  }
588 
589  while (!SCACStateQueueIsEmpty(&q)) {
590  r_state = SCACDequeue(&q);
591 
592  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
593  int32_t temp_state = ctx->goto_table[r_state][ascii_code];
594  if (temp_state != SC_AC_FAIL) {
595  SCACEnqueue(&q, temp_state);
596  DEBUG_VALIDATE_BUG_ON(temp_state > UINT16_MAX);
597  ctx->state_table_u16[r_state][ascii_code] = (uint16_t)temp_state;
598  } else {
599  ctx->state_table_u16[r_state][ascii_code] =
600  ctx->state_table_u16[ctx->failure_table[r_state]][ascii_code];
601  }
602  }
603  }
604  }
605 
606  if (!(ctx->state_count < 32767) || construct_both_16_and_32_state_tables) {
607  /* create space for the state table. We could have used the existing goto
608  * table, but since we have it set to hold 32 bit state values, we will create
609  * a new state table here of type SC_AC_STATE_TYPE(current set to uint16_t) */
610  ctx->state_table_u32 = SCMalloc(ctx->state_count *
611  sizeof(SC_AC_STATE_TYPE_U32) * 256);
612  if (ctx->state_table_u32 == NULL) {
613  FatalError(SC_ERR_FATAL, "Error allocating memory");
614  }
615  memset(ctx->state_table_u32, 0,
616  ctx->state_count * sizeof(SC_AC_STATE_TYPE_U32) * 256);
617 
618  mpm_ctx->memory_cnt++;
619  mpm_ctx->memory_size += (ctx->state_count *
620  sizeof(SC_AC_STATE_TYPE_U32) * 256);
621 
622  StateQueue q;
623  memset(&q, 0, sizeof(StateQueue));
624 
625  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
626  SC_AC_STATE_TYPE_U32 temp_state = ctx->goto_table[0][ascii_code];
627  ctx->state_table_u32[0][ascii_code] = temp_state;
628  if (temp_state != 0)
629  SCACEnqueue(&q, temp_state);
630  }
631 
632  while (!SCACStateQueueIsEmpty(&q)) {
633  r_state = SCACDequeue(&q);
634 
635  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
636  int32_t temp_state = ctx->goto_table[r_state][ascii_code];
637  if (temp_state != SC_AC_FAIL) {
638  SCACEnqueue(&q, temp_state);
639  ctx->state_table_u32[r_state][ascii_code] = temp_state;
640  } else {
641  ctx->state_table_u32[r_state][ascii_code] =
642  ctx->state_table_u32[ctx->failure_table[r_state]][ascii_code];
643  }
644  }
645  }
646  }
647 
648  return;
649 }
650 
651 static inline void SCACClubOutputStatePresenceWithDeltaTable(MpmCtx *mpm_ctx)
652 {
653  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
654  int ascii_code = 0;
655  uint32_t state = 0;
656  uint32_t temp_state = 0;
657 
658  if ((ctx->state_count < 32767) || construct_both_16_and_32_state_tables) {
659  for (state = 0; state < ctx->state_count; state++) {
660  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
661  temp_state = ctx->state_table_u16[state & 0x7FFF][ascii_code];
662  if (ctx->output_table[temp_state & 0x7FFF].no_of_entries != 0)
663  ctx->state_table_u16[state & 0x7FFF][ascii_code] |= (1 << 15);
664  }
665  }
666  }
667 
668  if (!(ctx->state_count < 32767) || construct_both_16_and_32_state_tables) {
669  for (state = 0; state < ctx->state_count; state++) {
670  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
671  temp_state = ctx->state_table_u32[state & 0x00FFFFFF][ascii_code];
672  if (ctx->output_table[temp_state & 0x00FFFFFF].no_of_entries != 0)
673  ctx->state_table_u32[state & 0x00FFFFFF][ascii_code] |= (1 << 24);
674  }
675  }
676  }
677 
678  return;
679 }
680 
681 static inline void SCACInsertCaseSensitiveEntriesForPatterns(MpmCtx *mpm_ctx)
682 {
683  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
684  uint32_t state = 0;
685  uint32_t k = 0;
686 
687  for (state = 0; state < ctx->state_count; state++) {
688  if (ctx->output_table[state].no_of_entries == 0)
689  continue;
690 
691  for (k = 0; k < ctx->output_table[state].no_of_entries; k++) {
692  if (ctx->pid_pat_list[ctx->output_table[state].pids[k]].cs != NULL) {
693  ctx->output_table[state].pids[k] &= AC_PID_MASK;
694  ctx->output_table[state].pids[k] |= ((uint32_t)1 << AC_CASE_BIT);
695  }
696  }
697  }
698 
699  return;
700 }
701 
702 #if 0
703 static void SCACPrintDeltaTable(MpmCtx *mpm_ctx)
704 {
705  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
706  int i = 0, j = 0;
707 
708  printf("##############Delta Table##############\n");
709  for (i = 0; i < ctx->state_count; i++) {
710  printf("%d: \n", i);
711  for (j = 0; j < 256; j++) {
712  if (SCACGetDelta(i, j, mpm_ctx) != 0) {
713  printf(" %c -> %d\n", j, SCACGetDelta(i, j, mpm_ctx));
714  }
715  }
716  }
717 
718  return;
719 }
720 #endif
721 
722 /**
723  * \brief Process the patterns and prepare the state table.
724  *
725  * \param mpm_ctx Pointer to the mpm context.
726  */
727 static void SCACPrepareStateTable(MpmCtx *mpm_ctx)
728 {
729  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
730 
731  /* create the 0th state in the goto table and output_table */
732  SCACInitNewState(mpm_ctx);
733 
734  SCACDetermineLevel1Gap(mpm_ctx);
735 
736  /* create the goto table */
737  SCACCreateGotoTable(mpm_ctx);
738  /* create the failure table */
739  SCACCreateFailureTable(mpm_ctx);
740  /* create the final state(delta) table */
741  SCACCreateDeltaTable(mpm_ctx);
742  /* club the output state presence with delta transition entries */
743  SCACClubOutputStatePresenceWithDeltaTable(mpm_ctx);
744 
745  /* club nocase entries */
746  SCACInsertCaseSensitiveEntriesForPatterns(mpm_ctx);
747 
748  /* shrink the memory */
749  SCACShrinkState(ctx);
750 
751 #if 0
752  SCACPrintDeltaTable(mpm_ctx);
753 #endif
754 
755  /* we don't need these anymore */
756  SCFree(ctx->goto_table);
757  ctx->goto_table = NULL;
758  SCFree(ctx->failure_table);
759  ctx->failure_table = NULL;
760 
761  return;
762 }
763 
764 /**
765  * \brief Process the patterns added to the mpm, and create the internal tables.
766  *
767  * \param mpm_ctx Pointer to the mpm context.
768  */
770 {
771  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
772 
773  if (mpm_ctx->pattern_cnt == 0 || mpm_ctx->init_hash == NULL) {
774  SCLogDebug("no patterns supplied to this mpm_ctx");
775  return 0;
776  }
777 
778  /* alloc the pattern array */
779  ctx->parray = (MpmPattern **)SCMalloc(mpm_ctx->pattern_cnt *
780  sizeof(MpmPattern *));
781  if (ctx->parray == NULL)
782  goto error;
783  memset(ctx->parray, 0, mpm_ctx->pattern_cnt * sizeof(MpmPattern *));
784  mpm_ctx->memory_cnt++;
785  mpm_ctx->memory_size += (mpm_ctx->pattern_cnt * sizeof(MpmPattern *));
786 
787  /* populate it with the patterns in the hash */
788  uint32_t i = 0, p = 0;
789  for (i = 0; i < MPM_INIT_HASH_SIZE; i++) {
790  MpmPattern *node = mpm_ctx->init_hash[i], *nnode = NULL;
791  while(node != NULL) {
792  nnode = node->next;
793  node->next = NULL;
794  ctx->parray[p++] = node;
795  node = nnode;
796  }
797  }
798 
799  /* we no longer need the hash, so free it's memory */
800  SCFree(mpm_ctx->init_hash);
801  mpm_ctx->init_hash = NULL;
802 
803  /* the memory consumed by a single state in our goto table */
804  ctx->single_state_size = sizeof(int32_t) * 256;
805 
806  /* handle no case patterns */
807  ctx->pid_pat_list = SCMalloc((mpm_ctx->max_pat_id + 1)* sizeof(SCACPatternList));
808  if (ctx->pid_pat_list == NULL) {
809  FatalError(SC_ERR_FATAL, "Error allocating memory");
810  }
811  memset(ctx->pid_pat_list, 0, (mpm_ctx->max_pat_id + 1) * sizeof(SCACPatternList));
812 
813  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
814  if (!(ctx->parray[i]->flags & MPM_PATTERN_FLAG_NOCASE)) {
815  ctx->pid_pat_list[ctx->parray[i]->id].cs = SCMalloc(ctx->parray[i]->len);
816  if (ctx->pid_pat_list[ctx->parray[i]->id].cs == NULL) {
817  FatalError(SC_ERR_FATAL, "Error allocating memory");
818  }
819  memcpy(ctx->pid_pat_list[ctx->parray[i]->id].cs,
820  ctx->parray[i]->original_pat, ctx->parray[i]->len);
821  ctx->pid_pat_list[ctx->parray[i]->id].patlen = ctx->parray[i]->len;
822  }
823  ctx->pid_pat_list[ctx->parray[i]->id].offset = ctx->parray[i]->offset;
824  ctx->pid_pat_list[ctx->parray[i]->id].depth = ctx->parray[i]->depth;
825 
826  /* ACPatternList now owns this memory */
827  //SCLogInfo("ctx->parray[i]->sids_size %u", ctx->parray[i]->sids_size);
828  ctx->pid_pat_list[ctx->parray[i]->id].sids_size = ctx->parray[i]->sids_size;
829  ctx->pid_pat_list[ctx->parray[i]->id].sids = ctx->parray[i]->sids;
830 
831  ctx->parray[i]->sids_size = 0;
832  ctx->parray[i]->sids = NULL;
833  }
834 
835  /* prepare the state table required by AC */
836  SCACPrepareStateTable(mpm_ctx);
837 
838  /* free all the stored patterns. Should save us a good 100-200 mbs */
839  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
840  if (ctx->parray[i] != NULL) {
841  MpmFreePattern(mpm_ctx, ctx->parray[i]);
842  }
843  }
844  SCFree(ctx->parray);
845  ctx->parray = NULL;
846  mpm_ctx->memory_cnt--;
847  mpm_ctx->memory_size -= (mpm_ctx->pattern_cnt * sizeof(MpmPattern *));
848 
849  ctx->pattern_id_bitarray_size = (mpm_ctx->max_pat_id / 8) + 1;
850  SCLogDebug("ctx->pattern_id_bitarray_size %u", ctx->pattern_id_bitarray_size);
851 
852  return 0;
853 
854 error:
855  return -1;
856 }
857 
858 /**
859  * \brief Init the mpm thread context.
860  *
861  * \param mpm_ctx Pointer to the mpm context.
862  * \param mpm_thread_ctx Pointer to the mpm thread context.
863  * \param matchsize We don't need this.
864  */
865 void SCACInitThreadCtx(MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx)
866 {
867  memset(mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
868 
869  mpm_thread_ctx->ctx = SCMalloc(sizeof(SCACThreadCtx));
870  if (mpm_thread_ctx->ctx == NULL) {
871  exit(EXIT_FAILURE);
872  }
873  memset(mpm_thread_ctx->ctx, 0, sizeof(SCACThreadCtx));
874  mpm_thread_ctx->memory_cnt++;
875  mpm_thread_ctx->memory_size += sizeof(SCACThreadCtx);
876 
877  return;
878 }
879 
880 /**
881  * \brief Initialize the AC context.
882  *
883  * \param mpm_ctx Mpm context.
884  */
885 void SCACInitCtx(MpmCtx *mpm_ctx)
886 {
887  if (mpm_ctx->ctx != NULL)
888  return;
889 
890  mpm_ctx->ctx = SCMalloc(sizeof(SCACCtx));
891  if (mpm_ctx->ctx == NULL) {
892  exit(EXIT_FAILURE);
893  }
894  memset(mpm_ctx->ctx, 0, sizeof(SCACCtx));
895 
896  mpm_ctx->memory_cnt++;
897  mpm_ctx->memory_size += sizeof(SCACCtx);
898 
899  /* initialize the hash we use to speed up pattern insertions */
900  mpm_ctx->init_hash = SCMalloc(sizeof(MpmPattern *) * MPM_INIT_HASH_SIZE);
901  if (mpm_ctx->init_hash == NULL) {
902  exit(EXIT_FAILURE);
903  }
904  memset(mpm_ctx->init_hash, 0, sizeof(MpmPattern *) * MPM_INIT_HASH_SIZE);
905 
906  /* get conf values for AC from our yaml file. We have no conf values for
907  * now. We will certainly need this, as we develop the algo */
908  SCACGetConfig();
909 
910  SCReturn;
911 }
912 
913 /**
914  * \brief Destroy the mpm thread context.
915  *
916  * \param mpm_ctx Pointer to the mpm context.
917  * \param mpm_thread_ctx Pointer to the mpm thread context.
918  */
919 void SCACDestroyThreadCtx(MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx)
920 {
921  SCACPrintSearchStats(mpm_thread_ctx);
922 
923  if (mpm_thread_ctx->ctx != NULL) {
924  SCFree(mpm_thread_ctx->ctx);
925  mpm_thread_ctx->ctx = NULL;
926  mpm_thread_ctx->memory_cnt--;
927  mpm_thread_ctx->memory_size -= sizeof(SCACThreadCtx);
928  }
929 
930  return;
931 }
932 
933 /**
934  * \brief Destroy the mpm context.
935  *
936  * \param mpm_ctx Pointer to the mpm context.
937  */
938 void SCACDestroyCtx(MpmCtx *mpm_ctx)
939 {
940  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
941  if (ctx == NULL)
942  return;
943 
944  if (mpm_ctx->init_hash != NULL) {
945  SCFree(mpm_ctx->init_hash);
946  mpm_ctx->init_hash = NULL;
947  mpm_ctx->memory_cnt--;
948  mpm_ctx->memory_size -= (MPM_INIT_HASH_SIZE * sizeof(MpmPattern *));
949  }
950 
951  if (ctx->parray != NULL) {
952  uint32_t i;
953  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
954  if (ctx->parray[i] != NULL) {
955  MpmFreePattern(mpm_ctx, ctx->parray[i]);
956  }
957  }
958 
959  SCFree(ctx->parray);
960  ctx->parray = NULL;
961  mpm_ctx->memory_cnt--;
962  mpm_ctx->memory_size -= (mpm_ctx->pattern_cnt * sizeof(MpmPattern *));
963  }
964 
965  if (ctx->state_table_u16 != NULL) {
966  SCFree(ctx->state_table_u16);
967  ctx->state_table_u16 = NULL;
968 
969  mpm_ctx->memory_cnt++;
970  mpm_ctx->memory_size -= (ctx->state_count *
971  sizeof(SC_AC_STATE_TYPE_U16) * 256);
972  }
973  if (ctx->state_table_u32 != NULL) {
974  SCFree(ctx->state_table_u32);
975  ctx->state_table_u32 = NULL;
976 
977  mpm_ctx->memory_cnt++;
978  mpm_ctx->memory_size -= (ctx->state_count *
979  sizeof(SC_AC_STATE_TYPE_U32) * 256);
980  }
981 
982  if (ctx->output_table != NULL) {
983  uint32_t state_count;
984  for (state_count = 0; state_count < ctx->state_count; state_count++) {
985  if (ctx->output_table[state_count].pids != NULL) {
986  SCFree(ctx->output_table[state_count].pids);
987  }
988  }
989  SCFree(ctx->output_table);
990  }
991 
992  if (ctx->pid_pat_list != NULL) {
993  uint32_t i;
994  for (i = 0; i < (mpm_ctx->max_pat_id + 1); i++) {
995  if (ctx->pid_pat_list[i].cs != NULL)
996  SCFree(ctx->pid_pat_list[i].cs);
997  if (ctx->pid_pat_list[i].sids != NULL)
998  SCFree(ctx->pid_pat_list[i].sids);
999  }
1000  SCFree(ctx->pid_pat_list);
1001  }
1002 
1003  SCFree(mpm_ctx->ctx);
1004  mpm_ctx->memory_cnt--;
1005  mpm_ctx->memory_size -= sizeof(SCACCtx);
1006 
1007  return;
1008 }
1009 
1010 /**
1011  * \brief The aho corasick search function.
1012  *
1013  * \param mpm_ctx Pointer to the mpm context.
1014  * \param mpm_thread_ctx Pointer to the mpm thread context.
1015  * \param pmq Pointer to the Pattern Matcher Queue to hold
1016  * search matches.
1017  * \param buf Buffer to be searched.
1018  * \param buflen Buffer length.
1019  *
1020  * \retval matches Match count.
1021  */
1022 uint32_t SCACSearch(const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx,
1023  PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
1024 {
1025  const SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
1026  uint32_t i = 0;
1027  int matches = 0;
1028 
1029  /* \todo tried loop unrolling with register var, with no perf increase. Need
1030  * to dig deeper */
1031  /* \todo Change it for stateful MPM. Supply the state using mpm_thread_ctx */
1032  const SCACPatternList *pid_pat_list = ctx->pid_pat_list;
1033 
1034  uint8_t bitarray[ctx->pattern_id_bitarray_size];
1035  memset(bitarray, 0, ctx->pattern_id_bitarray_size);
1036 
1037  if (ctx->state_count < 32767) {
1038  register SC_AC_STATE_TYPE_U16 state = 0;
1039  SC_AC_STATE_TYPE_U16 (*state_table_u16)[256] = ctx->state_table_u16;
1040  for (i = 0; i < buflen; i++) {
1041  state = state_table_u16[state & 0x7FFF][u8_tolower(buf[i])];
1042  if (state & 0x8000) {
1043  uint32_t no_of_entries = ctx->output_table[state & 0x7FFF].no_of_entries;
1044  uint32_t *pids = ctx->output_table[state & 0x7FFF].pids;
1045  uint32_t k;
1046  for (k = 0; k < no_of_entries; k++) {
1047  if (pids[k] & AC_CASE_MASK) {
1048  uint32_t lower_pid = pids[k] & AC_PID_MASK;
1049  const SCACPatternList *pat = &pid_pat_list[lower_pid];
1050  const int offset = i - pat->patlen + 1;
1051 
1052  if (offset < (int)pat->offset || (pat->depth && i > pat->depth))
1053  continue;
1054 
1055  if (SCMemcmp(pat->cs, buf + offset, pat->patlen) != 0)
1056  {
1057  /* inside loop */
1058  continue;
1059  }
1060  if (bitarray[(lower_pid) / 8] & (1 << ((lower_pid) % 8))) {
1061  ;
1062  } else {
1063  bitarray[(lower_pid) / 8] |= (1 << ((lower_pid) % 8));
1064  PrefilterAddSids(pmq, pat->sids, pat->sids_size);
1065  }
1066  matches++;
1067  } else {
1068  const SCACPatternList *pat = &pid_pat_list[pids[k]];
1069  const int offset = i - pat->patlen + 1;
1070 
1071  if (offset < (int)pat->offset || (pat->depth && i > pat->depth))
1072  continue;
1073 
1074  if (bitarray[pids[k] / 8] & (1 << (pids[k] % 8))) {
1075  ;
1076  } else {
1077  bitarray[pids[k] / 8] |= (1 << (pids[k] % 8));
1078  PrefilterAddSids(pmq, pat->sids, pat->sids_size);
1079  }
1080  matches++;
1081  }
1082  //loop1:
1083  //;
1084  }
1085  }
1086  } /* for (i = 0; i < buflen; i++) */
1087 
1088  } else {
1089  register SC_AC_STATE_TYPE_U32 state = 0;
1090  SC_AC_STATE_TYPE_U32 (*state_table_u32)[256] = ctx->state_table_u32;
1091  for (i = 0; i < buflen; i++) {
1092  state = state_table_u32[state & 0x00FFFFFF][u8_tolower(buf[i])];
1093  if (state & 0xFF000000) {
1094  uint32_t no_of_entries = ctx->output_table[state & 0x00FFFFFF].no_of_entries;
1095  uint32_t *pids = ctx->output_table[state & 0x00FFFFFF].pids;
1096  uint32_t k;
1097  for (k = 0; k < no_of_entries; k++) {
1098  if (pids[k] & AC_CASE_MASK) {
1099  uint32_t lower_pid = pids[k] & 0x0000FFFF;
1100  const SCACPatternList *pat = &pid_pat_list[lower_pid];
1101  const int offset = i - pat->patlen + 1;
1102 
1103  if (offset < (int)pat->offset || (pat->depth && i > pat->depth))
1104  continue;
1105 
1106  if (SCMemcmp(pat->cs, buf + offset,
1107  pat->patlen) != 0) {
1108  /* inside loop */
1109  continue;
1110  }
1111  if (bitarray[(lower_pid) / 8] & (1 << ((lower_pid) % 8))) {
1112  ;
1113  } else {
1114  bitarray[(lower_pid) / 8] |= (1 << ((lower_pid) % 8));
1115  PrefilterAddSids(pmq, pat->sids, pat->sids_size);
1116  }
1117  matches++;
1118  } else {
1119  const SCACPatternList *pat = &pid_pat_list[pids[k]];
1120  const int offset = i - pat->patlen + 1;
1121 
1122  if (offset < (int)pat->offset || (pat->depth && i > pat->depth))
1123  continue;
1124 
1125  if (bitarray[pids[k] / 8] & (1 << (pids[k] % 8))) {
1126  ;
1127  } else {
1128  bitarray[pids[k] / 8] |= (1 << (pids[k] % 8));
1129  PrefilterAddSids(pmq, pat->sids, pat->sids_size);
1130  }
1131  matches++;
1132  }
1133  //loop1:
1134  //;
1135  }
1136  }
1137  } /* for (i = 0; i < buflen; i++) */
1138  }
1139 
1140  return matches;
1141 }
1142 
1143 /**
1144  * \brief Add a case insensitive pattern. Although we have different calls for
1145  * adding case sensitive and insensitive patterns, we make a single call
1146  * for either case. No special treatment for either case.
1147  *
1148  * \param mpm_ctx Pointer to the mpm context.
1149  * \param pat The pattern to add.
1150  * \param patnen The pattern length.
1151  * \param offset Ignored.
1152  * \param depth Ignored.
1153  * \param pid The pattern id.
1154  * \param sid Ignored.
1155  * \param flags Flags associated with this pattern.
1156  *
1157  * \retval 0 On success.
1158  * \retval -1 On failure.
1159  */
1160 int SCACAddPatternCI(MpmCtx *mpm_ctx, uint8_t *pat, uint16_t patlen,
1161  uint16_t offset, uint16_t depth, uint32_t pid,
1162  SigIntId sid, uint8_t flags)
1163 {
1165  return MpmAddPattern(mpm_ctx, pat, patlen, offset, depth, pid, sid, flags);
1166 }
1167 
1168 /**
1169  * \brief Add a case sensitive pattern. Although we have different calls for
1170  * adding case sensitive and insensitive patterns, we make a single call
1171  * for either case. No special treatment for either case.
1172  *
1173  * \param mpm_ctx Pointer to the mpm context.
1174  * \param pat The pattern to add.
1175  * \param patnen The pattern length.
1176  * \param offset Ignored.
1177  * \param depth Ignored.
1178  * \param pid The pattern id.
1179  * \param sid Ignored.
1180  * \param flags Flags associated with this pattern.
1181  *
1182  * \retval 0 On success.
1183  * \retval -1 On failure.
1184  */
1185 int SCACAddPatternCS(MpmCtx *mpm_ctx, uint8_t *pat, uint16_t patlen,
1186  uint16_t offset, uint16_t depth, uint32_t pid,
1187  SigIntId sid, uint8_t flags)
1188 {
1189  return MpmAddPattern(mpm_ctx, pat, patlen, offset, depth, pid, sid, flags);
1190 }
1191 
1192 void SCACPrintSearchStats(MpmThreadCtx *mpm_thread_ctx)
1193 {
1194 
1195 #ifdef SC_AC_COUNTERS
1196  SCACThreadCtx *ctx = (SCACThreadCtx *)mpm_thread_ctx->ctx;
1197  printf("AC Thread Search stats (ctx %p)\n", ctx);
1198  printf("Total calls: %" PRIu32 "\n", ctx->total_calls);
1199  printf("Total matches: %" PRIu64 "\n", ctx->total_matches);
1200 #endif /* SC_AC_COUNTERS */
1201 
1202  return;
1203 }
1204 
1205 void SCACPrintInfo(MpmCtx *mpm_ctx)
1206 {
1207  SCACCtx *ctx = (SCACCtx *)mpm_ctx->ctx;
1208 
1209  printf("MPM AC Information:\n");
1210  printf("Memory allocs: %" PRIu32 "\n", mpm_ctx->memory_cnt);
1211  printf("Memory alloced: %" PRIu32 "\n", mpm_ctx->memory_size);
1212  printf(" Sizeof:\n");
1213  printf(" MpmCtx %" PRIuMAX "\n", (uintmax_t)sizeof(MpmCtx));
1214  printf(" SCACCtx: %" PRIuMAX "\n", (uintmax_t)sizeof(SCACCtx));
1215  printf(" MpmPattern %" PRIuMAX "\n", (uintmax_t)sizeof(MpmPattern));
1216  printf(" MpmPattern %" PRIuMAX "\n", (uintmax_t)sizeof(MpmPattern));
1217  printf("Unique Patterns: %" PRIu32 "\n", mpm_ctx->pattern_cnt);
1218  printf("Smallest: %" PRIu32 "\n", mpm_ctx->minlen);
1219  printf("Largest: %" PRIu32 "\n", mpm_ctx->maxlen);
1220  printf("Total states in the state table: %" PRIu32 "\n", ctx->state_count);
1221  printf("\n");
1222 
1223  return;
1224 }
1225 
1226 
1227 /************************** Mpm Registration ***************************/
1228 
1229 /**
1230  * \brief Register the aho-corasick mpm.
1231  */
1232 void MpmACRegister(void)
1233 {
1234  mpm_table[MPM_AC].name = "ac";
1246 
1247  return;
1248 }
1249 
1250 /*************************************Unittests********************************/
1251 
1252 #ifdef UNITTESTS
1253 
1254 static int SCACTest01(void)
1255 {
1256  int result = 0;
1257  MpmCtx mpm_ctx;
1258  MpmThreadCtx mpm_thread_ctx;
1259  PrefilterRuleStore pmq;
1260 
1261  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1262  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1263  MpmInitCtx(&mpm_ctx, MPM_AC);
1264  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1265 
1266  /* 1 match */
1267  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1268  PmqSetup(&pmq);
1269 
1270  SCACPreparePatterns(&mpm_ctx);
1271 
1272  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1273 
1274  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1275  (uint8_t *)buf, strlen(buf));
1276 
1277  if (cnt == 1)
1278  result = 1;
1279  else
1280  printf("1 != %" PRIu32 " ",cnt);
1281 
1282  SCACDestroyCtx(&mpm_ctx);
1283  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1284  PmqFree(&pmq);
1285  return result;
1286 }
1287 
1288 static int SCACTest02(void)
1289 {
1290  int result = 0;
1291  MpmCtx mpm_ctx;
1292  MpmThreadCtx mpm_thread_ctx;
1293  PrefilterRuleStore pmq;
1294 
1295  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1296  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1297  MpmInitCtx(&mpm_ctx, MPM_AC);
1298  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1299 
1300  /* 1 match */
1301  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abce", 4, 0, 0, 0, 0, 0);
1302  PmqSetup(&pmq);
1303 
1304  SCACPreparePatterns(&mpm_ctx);
1305 
1306  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1307  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1308  (uint8_t *)buf, strlen(buf));
1309 
1310  if (cnt == 0)
1311  result = 1;
1312  else
1313  printf("0 != %" PRIu32 " ",cnt);
1314 
1315  SCACDestroyCtx(&mpm_ctx);
1316  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1317  PmqFree(&pmq);
1318  return result;
1319 }
1320 
1321 static int SCACTest03(void)
1322 {
1323  int result = 0;
1324  MpmCtx mpm_ctx;
1325  MpmThreadCtx mpm_thread_ctx;
1326  PrefilterRuleStore pmq;
1327 
1328  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1329  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1330  MpmInitCtx(&mpm_ctx, MPM_AC);
1331  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1332 
1333  /* 1 match */
1334  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1335  /* 1 match */
1336  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"bcde", 4, 0, 0, 1, 0, 0);
1337  /* 1 match */
1338  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"fghj", 4, 0, 0, 2, 0, 0);
1339  PmqSetup(&pmq);
1340 
1341  SCACPreparePatterns(&mpm_ctx);
1342 
1343  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1344  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1345  (uint8_t *)buf, strlen(buf));
1346 
1347  if (cnt == 3)
1348  result = 1;
1349  else
1350  printf("3 != %" PRIu32 " ",cnt);
1351 
1352  SCACDestroyCtx(&mpm_ctx);
1353  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1354  PmqFree(&pmq);
1355  return result;
1356 }
1357 
1358 static int SCACTest04(void)
1359 {
1360  int result = 0;
1361  MpmCtx mpm_ctx;
1362  MpmThreadCtx mpm_thread_ctx;
1363  PrefilterRuleStore pmq;
1364 
1365  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1366  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1367  MpmInitCtx(&mpm_ctx, MPM_AC);
1368  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1369 
1370  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1371  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"bcdegh", 6, 0, 0, 1, 0, 0);
1372  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"fghjxyz", 7, 0, 0, 2, 0, 0);
1373  PmqSetup(&pmq);
1374 
1375  SCACPreparePatterns(&mpm_ctx);
1376 
1377  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1378  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1379  (uint8_t *)buf, strlen(buf));
1380 
1381  if (cnt == 1)
1382  result = 1;
1383  else
1384  printf("1 != %" PRIu32 " ",cnt);
1385 
1386  SCACDestroyCtx(&mpm_ctx);
1387  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1388  PmqFree(&pmq);
1389  return result;
1390 }
1391 
1392 static int SCACTest05(void)
1393 {
1394  int result = 0;
1395  MpmCtx mpm_ctx;
1396  MpmThreadCtx mpm_thread_ctx;
1397  PrefilterRuleStore pmq;
1398 
1399  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1400  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1401  MpmInitCtx(&mpm_ctx, MPM_AC);
1402  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1403 
1404  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"ABCD", 4, 0, 0, 0, 0, 0);
1405  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"bCdEfG", 6, 0, 0, 1, 0, 0);
1406  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"fghJikl", 7, 0, 0, 2, 0, 0);
1407  PmqSetup(&pmq);
1408 
1409  SCACPreparePatterns(&mpm_ctx);
1410 
1411  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1412  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1413  (uint8_t *)buf, strlen(buf));
1414 
1415  if (cnt == 3)
1416  result = 1;
1417  else
1418  printf("3 != %" PRIu32 " ",cnt);
1419 
1420  SCACDestroyCtx(&mpm_ctx);
1421  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1422  PmqFree(&pmq);
1423  return result;
1424 }
1425 
1426 static int SCACTest06(void)
1427 {
1428  int result = 0;
1429  MpmCtx mpm_ctx;
1430  MpmThreadCtx mpm_thread_ctx;
1431  PrefilterRuleStore pmq;
1432 
1433  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1434  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1435  MpmInitCtx(&mpm_ctx, MPM_AC);
1436  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1437 
1438  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1439  PmqSetup(&pmq);
1440 
1441  SCACPreparePatterns(&mpm_ctx);
1442 
1443  const char *buf = "abcd";
1444  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1445  (uint8_t *)buf, strlen(buf));
1446 
1447  if (cnt == 1)
1448  result = 1;
1449  else
1450  printf("1 != %" PRIu32 " ",cnt);
1451 
1452  SCACDestroyCtx(&mpm_ctx);
1453  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1454  PmqFree(&pmq);
1455  return result;
1456 }
1457 
1458 static int SCACTest07(void)
1459 {
1460  int result = 0;
1461  MpmCtx mpm_ctx;
1462  MpmThreadCtx mpm_thread_ctx;
1463  PrefilterRuleStore pmq;
1464 
1465  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1466  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1467  MpmInitCtx(&mpm_ctx, MPM_AC);
1468  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1469 
1470  /* should match 30 times */
1471  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"A", 1, 0, 0, 0, 0, 0);
1472  /* should match 29 times */
1473  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 1, 0, 0);
1474  /* should match 28 times */
1475  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAA", 3, 0, 0, 2, 0, 0);
1476  /* 26 */
1477  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAAAA", 5, 0, 0, 3, 0, 0);
1478  /* 21 */
1479  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAAAAAAAAA", 10, 0, 0, 4, 0, 0);
1480  /* 1 */
1481  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
1482  30, 0, 0, 5, 0, 0);
1483  PmqSetup(&pmq);
1484  /* total matches: 135 */
1485 
1486  SCACPreparePatterns(&mpm_ctx);
1487 
1488  const char *buf = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
1489  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1490  (uint8_t *)buf, strlen(buf));
1491 
1492  if (cnt == 135)
1493  result = 1;
1494  else
1495  printf("135 != %" PRIu32 " ",cnt);
1496 
1497  SCACDestroyCtx(&mpm_ctx);
1498  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1499  PmqFree(&pmq);
1500  return result;
1501 }
1502 
1503 static int SCACTest08(void)
1504 {
1505  int result = 0;
1506  MpmCtx mpm_ctx;
1507  MpmThreadCtx mpm_thread_ctx;
1508  PrefilterRuleStore pmq;
1509 
1510  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1511  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1512  MpmInitCtx(&mpm_ctx, MPM_AC);
1513  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1514 
1515  /* 1 match */
1516  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1517  PmqSetup(&pmq);
1518 
1519  SCACPreparePatterns(&mpm_ctx);
1520 
1521  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1522  (uint8_t *)"a", 1);
1523 
1524  if (cnt == 0)
1525  result = 1;
1526  else
1527  printf("0 != %" PRIu32 " ",cnt);
1528 
1529  SCACDestroyCtx(&mpm_ctx);
1530  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1531  PmqFree(&pmq);
1532  return result;
1533 }
1534 
1535 static int SCACTest09(void)
1536 {
1537  int result = 0;
1538  MpmCtx mpm_ctx;
1539  MpmThreadCtx mpm_thread_ctx;
1540  PrefilterRuleStore pmq;
1541 
1542  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1543  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1544  MpmInitCtx(&mpm_ctx, MPM_AC);
1545  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1546 
1547  /* 1 match */
1548  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"ab", 2, 0, 0, 0, 0, 0);
1549  PmqSetup(&pmq);
1550 
1551  SCACPreparePatterns(&mpm_ctx);
1552 
1553  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1554  (uint8_t *)"ab", 2);
1555 
1556  if (cnt == 1)
1557  result = 1;
1558  else
1559  printf("1 != %" PRIu32 " ",cnt);
1560 
1561  SCACDestroyCtx(&mpm_ctx);
1562  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1563  PmqFree(&pmq);
1564  return result;
1565 }
1566 
1567 static int SCACTest10(void)
1568 {
1569  int result = 0;
1570  MpmCtx mpm_ctx;
1571  MpmThreadCtx mpm_thread_ctx;
1572  PrefilterRuleStore pmq;
1573 
1574  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1575  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1576  MpmInitCtx(&mpm_ctx, MPM_AC);
1577  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1578 
1579  /* 1 match */
1580  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcdefgh", 8, 0, 0, 0, 0, 0);
1581  PmqSetup(&pmq);
1582 
1583  SCACPreparePatterns(&mpm_ctx);
1584 
1585  const char *buf = "01234567890123456789012345678901234567890123456789"
1586  "01234567890123456789012345678901234567890123456789"
1587  "abcdefgh"
1588  "01234567890123456789012345678901234567890123456789"
1589  "01234567890123456789012345678901234567890123456789";
1590  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1591  (uint8_t *)buf, strlen(buf));
1592 
1593  if (cnt == 1)
1594  result = 1;
1595  else
1596  printf("1 != %" PRIu32 " ",cnt);
1597 
1598  SCACDestroyCtx(&mpm_ctx);
1599  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1600  PmqFree(&pmq);
1601  return result;
1602 }
1603 
1604 static int SCACTest11(void)
1605 {
1606  int result = 0;
1607  MpmCtx mpm_ctx;
1608  MpmThreadCtx mpm_thread_ctx;
1609  PrefilterRuleStore pmq;
1610 
1611  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1612  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1613  MpmInitCtx(&mpm_ctx, MPM_AC);
1614  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1615 
1616  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"he", 2, 0, 0, 1, 0, 0) == -1)
1617  goto end;
1618  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"she", 3, 0, 0, 2, 0, 0) == -1)
1619  goto end;
1620  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"his", 3, 0, 0, 3, 0, 0) == -1)
1621  goto end;
1622  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"hers", 4, 0, 0, 4, 0, 0) == -1)
1623  goto end;
1624  PmqSetup(&pmq);
1625 
1626  if (SCACPreparePatterns(&mpm_ctx) == -1)
1627  goto end;
1628 
1629  result = 1;
1630 
1631  const char *buf = "he";
1632  result &= (SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1633  strlen(buf)) == 1);
1634  buf = "she";
1635  result &= (SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1636  strlen(buf)) == 2);
1637  buf = "his";
1638  result &= (SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1639  strlen(buf)) == 1);
1640  buf = "hers";
1641  result &= (SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1642  strlen(buf)) == 2);
1643 
1644  end:
1645  SCACDestroyCtx(&mpm_ctx);
1646  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1647  PmqFree(&pmq);
1648  return result;
1649 }
1650 
1651 static int SCACTest12(void)
1652 {
1653  int result = 0;
1654  MpmCtx mpm_ctx;
1655  MpmThreadCtx mpm_thread_ctx;
1656  PrefilterRuleStore pmq;
1657 
1658  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1659  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1660  MpmInitCtx(&mpm_ctx, MPM_AC);
1661  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1662 
1663  /* 1 match */
1664  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"wxyz", 4, 0, 0, 0, 0, 0);
1665  /* 1 match */
1666  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"vwxyz", 5, 0, 0, 1, 0, 0);
1667  PmqSetup(&pmq);
1668 
1669  SCACPreparePatterns(&mpm_ctx);
1670 
1671  const char *buf = "abcdefghijklmnopqrstuvwxyz";
1672  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1673  (uint8_t *)buf, strlen(buf));
1674 
1675  if (cnt == 2)
1676  result = 1;
1677  else
1678  printf("2 != %" PRIu32 " ",cnt);
1679 
1680  SCACDestroyCtx(&mpm_ctx);
1681  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1682  PmqFree(&pmq);
1683  return result;
1684 }
1685 
1686 static int SCACTest13(void)
1687 {
1688  int result = 0;
1689  MpmCtx mpm_ctx;
1690  MpmThreadCtx mpm_thread_ctx;
1691  PrefilterRuleStore pmq;
1692 
1693  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1694  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1695  MpmInitCtx(&mpm_ctx, MPM_AC);
1696  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1697 
1698  /* 1 match */
1699  const char pat[] = "abcdefghijklmnopqrstuvwxyzABCD";
1700  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1701  PmqSetup(&pmq);
1702 
1703  SCACPreparePatterns(&mpm_ctx);
1704 
1705  const char *buf = "abcdefghijklmnopqrstuvwxyzABCD";
1706  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1707  (uint8_t *)buf, strlen(buf));
1708 
1709  if (cnt == 1)
1710  result = 1;
1711  else
1712  printf("1 != %" PRIu32 " ",cnt);
1713 
1714  SCACDestroyCtx(&mpm_ctx);
1715  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1716  PmqFree(&pmq);
1717  return result;
1718 }
1719 
1720 static int SCACTest14(void)
1721 {
1722  int result = 0;
1723  MpmCtx mpm_ctx;
1724  MpmThreadCtx mpm_thread_ctx;
1725  PrefilterRuleStore pmq;
1726 
1727  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1728  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1729  MpmInitCtx(&mpm_ctx, MPM_AC);
1730  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1731 
1732  /* 1 match */
1733  const char pat[] = "abcdefghijklmnopqrstuvwxyzABCDE";
1734  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1735  PmqSetup(&pmq);
1736 
1737  SCACPreparePatterns(&mpm_ctx);
1738 
1739  const char *buf = "abcdefghijklmnopqrstuvwxyzABCDE";
1740  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1741  (uint8_t *)buf, strlen(buf));
1742 
1743  if (cnt == 1)
1744  result = 1;
1745  else
1746  printf("1 != %" PRIu32 " ",cnt);
1747 
1748  SCACDestroyCtx(&mpm_ctx);
1749  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1750  PmqFree(&pmq);
1751  return result;
1752 }
1753 
1754 static int SCACTest15(void)
1755 {
1756  int result = 0;
1757  MpmCtx mpm_ctx;
1758  MpmThreadCtx mpm_thread_ctx;
1759  PrefilterRuleStore pmq;
1760 
1761  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1762  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1763  MpmInitCtx(&mpm_ctx, MPM_AC);
1764  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1765 
1766  /* 1 match */
1767  const char pat[] = "abcdefghijklmnopqrstuvwxyzABCDEF";
1768  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1769  PmqSetup(&pmq);
1770 
1771  SCACPreparePatterns(&mpm_ctx);
1772 
1773  const char *buf = "abcdefghijklmnopqrstuvwxyzABCDEF";
1774  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1775  (uint8_t *)buf, strlen(buf));
1776 
1777  if (cnt == 1)
1778  result = 1;
1779  else
1780  printf("1 != %" PRIu32 " ",cnt);
1781 
1782  SCACDestroyCtx(&mpm_ctx);
1783  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1784  PmqFree(&pmq);
1785  return result;
1786 }
1787 
1788 static int SCACTest16(void)
1789 {
1790  int result = 0;
1791  MpmCtx mpm_ctx;
1792  MpmThreadCtx mpm_thread_ctx;
1793  PrefilterRuleStore pmq;
1794 
1795  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1796  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1797  MpmInitCtx(&mpm_ctx, MPM_AC);
1798  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1799 
1800  /* 1 match */
1801  const char pat[] = "abcdefghijklmnopqrstuvwxyzABC";
1802  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1803  PmqSetup(&pmq);
1804 
1805  SCACPreparePatterns(&mpm_ctx);
1806 
1807  const char *buf = "abcdefghijklmnopqrstuvwxyzABC";
1808  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1809  (uint8_t *)buf, strlen(buf));
1810 
1811  if (cnt == 1)
1812  result = 1;
1813  else
1814  printf("1 != %" PRIu32 " ",cnt);
1815 
1816  SCACDestroyCtx(&mpm_ctx);
1817  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1818  PmqFree(&pmq);
1819  return result;
1820 }
1821 
1822 static int SCACTest17(void)
1823 {
1824  int result = 0;
1825  MpmCtx mpm_ctx;
1826  MpmThreadCtx mpm_thread_ctx;
1827  PrefilterRuleStore pmq;
1828 
1829  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1830  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1831  MpmInitCtx(&mpm_ctx, MPM_AC);
1832  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1833 
1834  /* 1 match */
1835  const char pat[] = "abcdefghijklmnopqrstuvwxyzAB";
1836  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1837  PmqSetup(&pmq);
1838 
1839  SCACPreparePatterns(&mpm_ctx);
1840 
1841  const char *buf = "abcdefghijklmnopqrstuvwxyzAB";
1842  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1843  (uint8_t *)buf, strlen(buf));
1844 
1845  if (cnt == 1)
1846  result = 1;
1847  else
1848  printf("1 != %" PRIu32 " ",cnt);
1849 
1850  SCACDestroyCtx(&mpm_ctx);
1851  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1852  PmqFree(&pmq);
1853  return result;
1854 }
1855 
1856 static int SCACTest18(void)
1857 {
1858  int result = 0;
1859  MpmCtx mpm_ctx;
1860  MpmThreadCtx mpm_thread_ctx;
1861  PrefilterRuleStore pmq;
1862 
1863  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1864  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1865  MpmInitCtx(&mpm_ctx, MPM_AC);
1866  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1867 
1868  /* 1 match */
1869  const char pat[] = "abcde"
1870  "fghij"
1871  "klmno"
1872  "pqrst"
1873  "uvwxy"
1874  "z";
1875  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1876  PmqSetup(&pmq);
1877 
1878  SCACPreparePatterns(&mpm_ctx);
1879 
1880  const char *buf = "abcde""fghij""klmno""pqrst""uvwxy""z";
1881  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1882  (uint8_t *)buf, strlen(buf));
1883 
1884  if (cnt == 1)
1885  result = 1;
1886  else
1887  printf("1 != %" PRIu32 " ",cnt);
1888 
1889  SCACDestroyCtx(&mpm_ctx);
1890  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1891  PmqFree(&pmq);
1892  return result;
1893 }
1894 
1895 static int SCACTest19(void)
1896 {
1897  int result = 0;
1898  MpmCtx mpm_ctx;
1899  MpmThreadCtx mpm_thread_ctx;
1900  PrefilterRuleStore pmq;
1901 
1902  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1903  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1904  MpmInitCtx(&mpm_ctx, MPM_AC);
1905  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1906 
1907  /* 1 */
1908  const char pat[] = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
1909  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1910  PmqSetup(&pmq);
1911 
1912  SCACPreparePatterns(&mpm_ctx);
1913 
1914  const char *buf = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
1915  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1916  (uint8_t *)buf, strlen(buf));
1917 
1918  if (cnt == 1)
1919  result = 1;
1920  else
1921  printf("1 != %" PRIu32 " ",cnt);
1922 
1923  SCACDestroyCtx(&mpm_ctx);
1924  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1925  PmqFree(&pmq);
1926  return result;
1927 }
1928 
1929 static int SCACTest20(void)
1930 {
1931  int result = 0;
1932  MpmCtx mpm_ctx;
1933  MpmThreadCtx mpm_thread_ctx;
1934  PrefilterRuleStore pmq;
1935 
1936  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1937  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1938  MpmInitCtx(&mpm_ctx, MPM_AC);
1939  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1940 
1941  /* 1 */
1942  const char pat[] = "AAAAA"
1943  "AAAAA"
1944  "AAAAA"
1945  "AAAAA"
1946  "AAAAA"
1947  "AAAAA"
1948  "AA";
1949  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1950  PmqSetup(&pmq);
1951 
1952  SCACPreparePatterns(&mpm_ctx);
1953 
1954  const char *buf = "AAAAA""AAAAA""AAAAA""AAAAA""AAAAA""AAAAA""AA";
1955  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1956  (uint8_t *)buf, strlen(buf));
1957 
1958  if (cnt == 1)
1959  result = 1;
1960  else
1961  printf("1 != %" PRIu32 " ",cnt);
1962 
1963  SCACDestroyCtx(&mpm_ctx);
1964  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1965  PmqFree(&pmq);
1966  return result;
1967 }
1968 
1969 static int SCACTest21(void)
1970 {
1971  int result = 0;
1972  MpmCtx mpm_ctx;
1973  MpmThreadCtx mpm_thread_ctx;
1974  PrefilterRuleStore pmq;
1975 
1976  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1977  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1978  MpmInitCtx(&mpm_ctx, MPM_AC);
1979  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1980 
1981  /* 1 */
1982  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 0, 0, 0);
1983  PmqSetup(&pmq);
1984 
1985  SCACPreparePatterns(&mpm_ctx);
1986 
1987  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1988  (uint8_t *)"AA", 2);
1989 
1990  if (cnt == 1)
1991  result = 1;
1992  else
1993  printf("1 != %" PRIu32 " ",cnt);
1994 
1995  SCACDestroyCtx(&mpm_ctx);
1996  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1997  PmqFree(&pmq);
1998  return result;
1999 }
2000 
2001 static int SCACTest22(void)
2002 {
2003  int result = 0;
2004  MpmCtx mpm_ctx;
2005  MpmThreadCtx mpm_thread_ctx;
2006  PrefilterRuleStore pmq;
2007 
2008  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2009  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2010  MpmInitCtx(&mpm_ctx, MPM_AC);
2011  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2012 
2013  /* 1 match */
2014  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
2015  /* 1 match */
2016  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcde", 5, 0, 0, 1, 0, 0);
2017  PmqSetup(&pmq);
2018 
2019  SCACPreparePatterns(&mpm_ctx);
2020 
2021  const char *buf = "abcdefghijklmnopqrstuvwxyz";
2022  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2023  (uint8_t *)buf, strlen(buf));
2024 
2025  if (cnt == 2)
2026  result = 1;
2027  else
2028  printf("2 != %" PRIu32 " ",cnt);
2029 
2030  SCACDestroyCtx(&mpm_ctx);
2031  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2032  PmqFree(&pmq);
2033  return result;
2034 }
2035 
2036 static int SCACTest23(void)
2037 {
2038  int result = 0;
2039  MpmCtx mpm_ctx;
2040  MpmThreadCtx mpm_thread_ctx;
2041  PrefilterRuleStore pmq;
2042 
2043  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2044  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2045  MpmInitCtx(&mpm_ctx, MPM_AC);
2046  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2047 
2048  /* 1 */
2049  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 0, 0, 0);
2050  PmqSetup(&pmq);
2051 
2052  SCACPreparePatterns(&mpm_ctx);
2053 
2054  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2055  (uint8_t *)"aa", 2);
2056 
2057  if (cnt == 0)
2058  result = 1;
2059  else
2060  printf("1 != %" PRIu32 " ",cnt);
2061 
2062  SCACDestroyCtx(&mpm_ctx);
2063  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2064  PmqFree(&pmq);
2065  return result;
2066 }
2067 
2068 static int SCACTest24(void)
2069 {
2070  int result = 0;
2071  MpmCtx mpm_ctx;
2072  MpmThreadCtx mpm_thread_ctx;
2073  PrefilterRuleStore pmq;
2074 
2075  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2076  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2077  MpmInitCtx(&mpm_ctx, MPM_AC);
2078  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2079 
2080  /* 1 */
2081  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 0, 0, 0);
2082  PmqSetup(&pmq);
2083 
2084  SCACPreparePatterns(&mpm_ctx);
2085 
2086  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2087  (uint8_t *)"aa", 2);
2088 
2089  if (cnt == 1)
2090  result = 1;
2091  else
2092  printf("1 != %" PRIu32 " ",cnt);
2093 
2094  SCACDestroyCtx(&mpm_ctx);
2095  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2096  PmqFree(&pmq);
2097  return result;
2098 }
2099 
2100 static int SCACTest25(void)
2101 {
2102  int result = 0;
2103  MpmCtx mpm_ctx;
2104  MpmThreadCtx mpm_thread_ctx;
2105  PrefilterRuleStore pmq;
2106 
2107  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2108  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2109  MpmInitCtx(&mpm_ctx, MPM_AC);
2110  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2111 
2112  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"ABCD", 4, 0, 0, 0, 0, 0);
2113  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"bCdEfG", 6, 0, 0, 1, 0, 0);
2114  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"fghiJkl", 7, 0, 0, 2, 0, 0);
2115  PmqSetup(&pmq);
2116 
2117  SCACPreparePatterns(&mpm_ctx);
2118 
2119  const char *buf = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2120  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2121  (uint8_t *)buf, strlen(buf));
2122 
2123  if (cnt == 3)
2124  result = 1;
2125  else
2126  printf("3 != %" PRIu32 " ",cnt);
2127 
2128  SCACDestroyCtx(&mpm_ctx);
2129  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2130  PmqFree(&pmq);
2131  return result;
2132 }
2133 
2134 static int SCACTest26(void)
2135 {
2136  int result = 0;
2137  MpmCtx mpm_ctx;
2138  MpmThreadCtx mpm_thread_ctx;
2139  PrefilterRuleStore pmq;
2140 
2141  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2142  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2143  MpmInitCtx(&mpm_ctx, MPM_AC);
2144  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2145 
2146  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"Works", 5, 0, 0, 0, 0, 0);
2147  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"Works", 5, 0, 0, 1, 0, 0);
2148  PmqSetup(&pmq);
2149 
2150  SCACPreparePatterns(&mpm_ctx);
2151 
2152  const char *buf = "works";
2153  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2154  (uint8_t *)buf, strlen(buf));
2155 
2156  if (cnt == 1)
2157  result = 1;
2158  else
2159  printf("3 != %" PRIu32 " ",cnt);
2160 
2161  SCACDestroyCtx(&mpm_ctx);
2162  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2163  PmqFree(&pmq);
2164  return result;
2165 }
2166 
2167 static int SCACTest27(void)
2168 {
2169  int result = 0;
2170  MpmCtx mpm_ctx;
2171  MpmThreadCtx mpm_thread_ctx;
2172  PrefilterRuleStore pmq;
2173 
2174  memset(&mpm_ctx, 0, sizeof(MpmCtx));
2175  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2176  MpmInitCtx(&mpm_ctx, MPM_AC);
2177  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2178 
2179  /* 0 match */
2180  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"ONE", 3, 0, 0, 0, 0, 0);
2181  PmqSetup(&pmq);
2182 
2183  SCACPreparePatterns(&mpm_ctx);
2184 
2185  const char *buf = "tone";
2186  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2187  (uint8_t *)buf, strlen(buf));
2188 
2189  if (cnt == 0)
2190  result = 1;
2191  else
2192  printf("0 != %" PRIu32 " ",cnt);
2193 
2194  SCACDestroyCtx(&mpm_ctx);
2195  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2196  PmqFree(&pmq);
2197  return result;
2198 }
2199 
2200 static int SCACTest28(void)
2201 {
2202  int result = 0;
2203  MpmCtx mpm_ctx;
2204  MpmThreadCtx mpm_thread_ctx;
2205  PrefilterRuleStore pmq;
2206 
2207  memset(&mpm_ctx, 0, sizeof(MpmCtx));
2208  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2209  MpmInitCtx(&mpm_ctx, MPM_AC);
2210  SCACInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2211 
2212  /* 0 match */
2213  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"one", 3, 0, 0, 0, 0, 0);
2214  PmqSetup(&pmq);
2215 
2216  SCACPreparePatterns(&mpm_ctx);
2217 
2218  const char *buf = "tONE";
2219  uint32_t cnt = SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2220  (uint8_t *)buf, strlen(buf));
2221 
2222  if (cnt == 0)
2223  result = 1;
2224  else
2225  printf("0 != %" PRIu32 " ",cnt);
2226 
2227  SCACDestroyCtx(&mpm_ctx);
2228  SCACDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2229  PmqFree(&pmq);
2230  return result;
2231 }
2232 
2233 static int SCACTest29(void)
2234 {
2235  uint8_t buf[] = "onetwothreefourfivesixseveneightnine";
2236  uint16_t buflen = sizeof(buf) - 1;
2237  Packet *p = NULL;
2238  ThreadVars th_v;
2239  DetectEngineThreadCtx *det_ctx = NULL;
2240  int result = 0;
2241 
2242  memset(&th_v, 0, sizeof(th_v));
2243  p = UTHBuildPacket(buf, buflen, IPPROTO_TCP);
2244 
2246  if (de_ctx == NULL)
2247  goto end;
2248 
2249  de_ctx->flags |= DE_QUIET;
2250 
2251  de_ctx->sig_list = SigInit(de_ctx, "alert tcp any any -> any any "
2252  "(content:\"onetwothreefourfivesixseveneightnine\"; sid:1;)");
2253  if (de_ctx->sig_list == NULL)
2254  goto end;
2255  de_ctx->sig_list->next = SigInit(de_ctx, "alert tcp any any -> any any "
2256  "(content:\"onetwothreefourfivesixseveneightnine\"; fast_pattern:3,3; sid:2;)");
2257  if (de_ctx->sig_list->next == NULL)
2258  goto end;
2259 
2261  DetectEngineThreadCtxInit(&th_v, (void *)de_ctx, (void *)&det_ctx);
2262 
2263  SigMatchSignatures(&th_v, de_ctx, det_ctx, p);
2264  if (PacketAlertCheck(p, 1) != 1) {
2265  printf("if (PacketAlertCheck(p, 1) != 1) failure\n");
2266  goto end;
2267  }
2268  if (PacketAlertCheck(p, 2) != 1) {
2269  printf("if (PacketAlertCheck(p, 1) != 2) failure\n");
2270  goto end;
2271  }
2272 
2273  result = 1;
2274 end:
2275  if (de_ctx != NULL) {
2278 
2279  DetectEngineThreadCtxDeinit(&th_v, (void *)det_ctx);
2281  }
2282 
2283  UTHFreePackets(&p, 1);
2284  return result;
2285 }
2286 
2287 #endif /* UNITTESTS */
2288 
2290 {
2291 
2292 #ifdef UNITTESTS
2293  UtRegisterTest("SCACTest01", SCACTest01);
2294  UtRegisterTest("SCACTest02", SCACTest02);
2295  UtRegisterTest("SCACTest03", SCACTest03);
2296  UtRegisterTest("SCACTest04", SCACTest04);
2297  UtRegisterTest("SCACTest05", SCACTest05);
2298  UtRegisterTest("SCACTest06", SCACTest06);
2299  UtRegisterTest("SCACTest07", SCACTest07);
2300  UtRegisterTest("SCACTest08", SCACTest08);
2301  UtRegisterTest("SCACTest09", SCACTest09);
2302  UtRegisterTest("SCACTest10", SCACTest10);
2303  UtRegisterTest("SCACTest11", SCACTest11);
2304  UtRegisterTest("SCACTest12", SCACTest12);
2305  UtRegisterTest("SCACTest13", SCACTest13);
2306  UtRegisterTest("SCACTest14", SCACTest14);
2307  UtRegisterTest("SCACTest15", SCACTest15);
2308  UtRegisterTest("SCACTest16", SCACTest16);
2309  UtRegisterTest("SCACTest17", SCACTest17);
2310  UtRegisterTest("SCACTest18", SCACTest18);
2311  UtRegisterTest("SCACTest19", SCACTest19);
2312  UtRegisterTest("SCACTest20", SCACTest20);
2313  UtRegisterTest("SCACTest21", SCACTest21);
2314  UtRegisterTest("SCACTest22", SCACTest22);
2315  UtRegisterTest("SCACTest23", SCACTest23);
2316  UtRegisterTest("SCACTest24", SCACTest24);
2317  UtRegisterTest("SCACTest25", SCACTest25);
2318  UtRegisterTest("SCACTest26", SCACTest26);
2319  UtRegisterTest("SCACTest27", SCACTest27);
2320  UtRegisterTest("SCACTest28", SCACTest28);
2321  UtRegisterTest("SCACTest29", SCACTest29);
2322 #endif
2323 
2324  return;
2325 }
MpmTableElmt_::PrintThreadCtx
void(* PrintThreadCtx)(struct MpmThreadCtx_ *)
Definition: util-mpm.h:167
detect-engine.h
SCACOutputTable_::no_of_entries
uint32_t no_of_entries
Definition: util-mpm-ac.h:47
SCACInitCtx
void SCACInitCtx(MpmCtx *)
Initialize the AC context.
Definition: util-mpm-ac.c:885
offset
uint64_t offset
Definition: util-streaming-buffer.h:0
MpmTableElmt_::InitThreadCtx
void(* InitThreadCtx)(struct MpmCtx_ *, struct MpmThreadCtx_ *)
Definition: util-mpm.h:147
SCACThreadCtx_
Definition: util-mpm-ac.h:78
StateQueue
struct StateQueue_ StateQueue
Helper structure used by AC during state table creation.
MpmThreadCtx_
Definition: util-mpm.h:46
MpmFreePattern
void MpmFreePattern(MpmCtx *mpm_ctx, MpmPattern *p)
Definition: util-mpm.c:349
SCACCtx_::parray
MpmPattern ** parray
Definition: util-mpm-ac.h:52
UtRegisterTest
void UtRegisterTest(const char *name, int(*TestFn)(void))
Register unit test.
Definition: util-unittest.c:103
MpmTableElmt_::name
const char * name
Definition: util-mpm.h:145
SC_ERR_AHO_CORASICK
@ SC_ERR_AHO_CORASICK
Definition: util-error.h:206
SCACCtx_::allocated_state_count
uint32_t allocated_state_count
Definition: util-mpm-ac.h:74
PrefilterRuleStore_
structure for storing potential rule matches
Definition: util-prefilter.h:32
SCLogDebug
#define SCLogDebug(...)
Definition: util-debug.h:298
PacketAlertCheck
int PacketAlertCheck(Packet *p, uint32_t sid)
Check if a certain sid alerted, this is used in the test functions.
Definition: detect-engine-alert.c:137
MpmThreadCtx_::memory_cnt
uint32_t memory_cnt
Definition: util-mpm.h:49
SCACPatternList_::patlen
uint16_t patlen
Definition: util-mpm-ac.h:33
SCACCtx_::pid_pat_list
SCACPatternList * pid_pat_list
Definition: util-mpm-ac.h:69
u8_tolower
#define u8_tolower(c)
Definition: suricata.h:178
SigInit
Signature * SigInit(DetectEngineCtx *, const char *)
Parses a signature and adds it to the Detection Engine Context.
Definition: detect-parse.c:2115
SCACPrintInfo
void SCACPrintInfo(MpmCtx *mpm_ctx)
Definition: util-mpm-ac.c:1205
StateQueue_
Helper structure used by AC during state table creation.
Definition: util-mpm-ac-bs.c:87
AC_CASE_BIT
#define AC_CASE_BIT
Definition: util-mpm-ac.c:86
DetectEngineCtx_
main detection engine ctx
Definition: detect.h:811
util-memcpy.h
MpmCtx_::memory_size
uint32_t memory_size
Definition: util-mpm.h:103
SCACCtx_::failure_table
int32_t * failure_table
Definition: util-mpm-ac.h:67
SC_AC_STATE_TYPE_U32
#define SC_AC_STATE_TYPE_U32
Definition: util-mpm-ac.h:29
DetectEngineCtxFree
void DetectEngineCtxFree(DetectEngineCtx *)
Free a DetectEngineCtx::
Definition: detect-engine.c:2433
MpmTableElmt_::AddPatternNocase
int(* AddPatternNocase)(struct MpmCtx_ *, uint8_t *, uint16_t, uint16_t, uint16_t, uint32_t, SigIntId, uint8_t)
Definition: util-mpm.h:163
DE_QUIET
#define DE_QUIET
Definition: detect.h:295
MpmCtx_::maxlen
uint16_t maxlen
Definition: util-mpm.h:100
MpmTableElmt_::AddPattern
int(* AddPattern)(struct MpmCtx_ *, uint8_t *, uint16_t, uint16_t, uint16_t, uint32_t, SigIntId, uint8_t)
Definition: util-mpm.h:162
UTHBuildPacket
Packet * UTHBuildPacket(uint8_t *payload, uint16_t payload_len, uint8_t ipproto)
UTHBuildPacket is a wrapper that build packets with default ip and port fields.
Definition: util-unittest-helper.c:337
SigMatchSignatures
void SigMatchSignatures(ThreadVars *tv, DetectEngineCtx *de_ctx, DetectEngineThreadCtx *det_ctx, Packet *p)
wrapper for old tests
Definition: detect.c:1790
SigCleanSignatures
void SigCleanSignatures(DetectEngineCtx *de_ctx)
Definition: detect-engine-build.c:42
MpmPattern_::original_pat
uint8_t * original_pat
Definition: util-mpm.h:67
SCACCtx_::state_count
uint32_t state_count
Definition: util-mpm-ac.h:55
STATE_QUEUE_CONTAINER_SIZE
#define STATE_QUEUE_CONTAINER_SIZE
Definition: util-mpm-ac.c:82
MpmTableElmt_::InitCtx
void(* InitCtx)(struct MpmCtx_ *)
Definition: util-mpm.h:146
SC_AC_STATE_TYPE_U16
#define SC_AC_STATE_TYPE_U16
Definition: util-mpm-ac.h:28
util-unittest.h
util-unittest-helper.h
MpmPattern_::flags
uint8_t flags
Definition: util-mpm.h:58
util-memcmp.h
SCACThreadCtx_::total_matches
uint64_t total_matches
Definition: util-mpm-ac.h:82
MpmInitCtx
void MpmInitCtx(MpmCtx *mpm_ctx, uint8_t matcher)
Definition: util-mpm.c:200
Signature_::next
struct Signature_ * next
Definition: detect.h:622
MpmTableElmt_::PrintCtx
void(* PrintCtx)(struct MpmCtx_ *)
Definition: util-mpm.h:166
MpmCtx_::max_pat_id
uint32_t max_pat_id
Definition: util-mpm.h:105
SCACOutputTable
struct SCACOutputTable_ SCACOutputTable
util-debug.h
MpmPattern_::next
struct MpmPattern_ * next
Definition: util-mpm.h:79
de_ctx
DetectEngineCtx * de_ctx
Definition: fuzz_siginit.c:17
MPM_AC
@ MPM_AC
Definition: util-mpm.h:35
DetectEngineThreadCtx_
Definition: detect.h:1060
SCACThreadCtx
struct SCACThreadCtx_ SCACThreadCtx
MpmPattern_::id
uint32_t id
Definition: util-mpm.h:73
MpmThreadCtx_::memory_size
uint32_t memory_size
Definition: util-mpm.h:50
detect.h
ThreadVars_
Per thread variable structure.
Definition: threadvars.h:58
SCACPatternList_::cs
uint8_t * cs
Definition: util-mpm-ac.h:32
MpmCtx_::minlen
uint16_t minlen
Definition: util-mpm.h:99
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.
Definition: util-mpm-ac.c:1022
SCACAddPatternCS
int SCACAddPatternCS(MpmCtx *, uint8_t *, uint16_t, uint16_t, uint16_t, uint32_t, SigIntId, uint8_t)
Add a case sensitive pattern. Although we have different calls for adding case sensitive and insensit...
Definition: util-mpm-ac.c:1185
SigGroupCleanup
int SigGroupCleanup(DetectEngineCtx *de_ctx)
Definition: detect-engine-build.c:2016
SCLogCritical
#define SCLogCritical(err_code,...)
Macro used to log CRITICAL messages.
Definition: util-debug.h:270
MpmPattern_::sids_size
uint32_t sids_size
Definition: util-mpm.h:76
SCReturn
#define SCReturn
Definition: util-debug.h:302
Packet_
Definition: decode.h:427
SCACCtx_::output_table
SCACOutputTable * output_table
Definition: util-mpm-ac.h:68
conf.h
SCACPatternList_::sids
SigIntId * sids
Definition: util-mpm-ac.h:40
MPM_INIT_HASH_SIZE
#define MPM_INIT_HASH_SIZE
Definition: util-mpm.h:29
SC_AC_FAIL
#define SC_AC_FAIL
Definition: util-mpm-ac.c:80
MpmTableElmt_::Prepare
int(* Prepare)(struct MpmCtx_ *)
Definition: util-mpm.h:164
StateQueue_::bot
int bot
Definition: util-mpm-ac-bs.c:90
util-mpm-ac.h
MpmPattern_
Definition: util-mpm.h:54
MpmTableElmt_::Search
uint32_t(* Search)(const struct MpmCtx_ *, struct MpmThreadCtx_ *, PrefilterRuleStore *, const uint8_t *, uint32_t)
Definition: util-mpm.h:165
SCACCtx_::pattern_id_bitarray_size
uint32_t pattern_id_bitarray_size
Definition: util-mpm-ac.h:57
MpmAddPatternCS
int MpmAddPatternCS(struct MpmCtx_ *mpm_ctx, uint8_t *pat, uint16_t patlen, uint16_t offset, uint16_t depth, uint32_t pid, SigIntId sid, uint8_t flags)
Definition: util-mpm.c:241
SCLogInfo
#define SCLogInfo(...)
Macro used to log INFORMATIONAL messages.
Definition: util-debug.h:217
SCACPatternList_::depth
uint16_t depth
Definition: util-mpm-ac.h:36
SigGroupBuild
int SigGroupBuild(DetectEngineCtx *de_ctx)
Convert the signature list into the runtime match structure.
Definition: detect-engine-build.c:1948
MpmPattern_::ci
uint8_t * ci
Definition: util-mpm.h:71
SCRealloc
#define SCRealloc(ptr, sz)
Definition: util-mem.h:50
SCACPatternList_::offset
uint16_t offset
Definition: util-mpm-ac.h:35
MPM_PATTERN_FLAG_NOCASE
#define MPM_PATTERN_FLAG_NOCASE
Definition: util-mpm.h:131
SCACThreadCtx_::total_calls
uint32_t total_calls
Definition: util-mpm-ac.h:80
SCACCtx_
Definition: util-mpm-ac.h:50
SCACDestroyCtx
void SCACDestroyCtx(MpmCtx *)
Destroy the mpm context.
Definition: util-mpm-ac.c:938
DetectEngineThreadCtxInit
TmEcode DetectEngineThreadCtxInit(ThreadVars *, void *, void **)
initialize thread specific detection engine context
Definition: detect-engine.c:3142
flags
uint8_t flags
Definition: decode-gre.h:0
suricata-common.h
DetectEngineThreadCtxDeinit
TmEcode DetectEngineThreadCtxDeinit(ThreadVars *, void *)
Definition: detect-engine.c:3354
MpmCtx_::pattern_cnt
uint32_t pattern_cnt
Definition: util-mpm.h:97
PmqFree
void PmqFree(PrefilterRuleStore *)
Cleanup and free a Pmq.
Definition: util-prefilter.c:125
SCLogError
#define SCLogError(err_code,...)
Macro used to log ERROR messages.
Definition: util-debug.h:257
MpmPattern_::offset
uint16_t offset
Definition: util-mpm.h:61
FatalError
#define FatalError(x,...)
Definition: util-debug.h:532
DetectEngineCtx_::sig_list
Signature * sig_list
Definition: detect.h:817
SCACPatternList_
Definition: util-mpm-ac.h:31
util-validate.h
SCMalloc
#define SCMalloc(sz)
Definition: util-mem.h:47
MpmPattern_::sids
SigIntId * sids
Definition: util-mpm.h:77
MpmPattern_::depth
uint16_t depth
Definition: util-mpm.h:64
MpmTableElmt_::DestroyCtx
void(* DestroyCtx)(struct MpmCtx_ *)
Definition: util-mpm.h:148
SCACCtx
struct SCACCtx_ SCACCtx
SCFree
#define SCFree(p)
Definition: util-mem.h:61
MpmACRegister
void MpmACRegister(void)
Register the aho-corasick mpm.
Definition: util-mpm-ac.c:1232
SC_ERR_FATAL
@ SC_ERR_FATAL
Definition: util-error.h:203
PmqSetup
int PmqSetup(PrefilterRuleStore *)
Setup a pmq.
Definition: util-prefilter.c:36
detect-parse.h
MpmCtx_::memory_cnt
uint32_t memory_cnt
Definition: util-mpm.h:102
SCACOutputTable_
Definition: util-mpm-ac.h:43
MpmCtx_::init_hash
MpmPattern ** init_hash
Definition: util-mpm.h:108
MpmPattern_::len
uint16_t len
Definition: util-mpm.h:56
DetectEngineCtxInit
DetectEngineCtx * DetectEngineCtxInit(void)
Definition: detect-engine.c:2394
SCACCtx_::state_table_u16
SC_AC_STATE_TYPE_U16(* state_table_u16)[256]
Definition: util-mpm-ac.h:60
mpm_table
MpmTableElmt mpm_table[MPM_TABLE_SIZE]
Definition: util-mpm.c:48
SCACInitThreadCtx
void SCACInitThreadCtx(MpmCtx *, MpmThreadCtx *)
Init the mpm thread context.
Definition: util-mpm-ac.c:865
SC_ERR_MEM_ALLOC
@ SC_ERR_MEM_ALLOC
Definition: util-error.h:31
suricata.h
SCACRegisterTests
void SCACRegisterTests(void)
Definition: util-mpm-ac.c:2289
AC_PID_MASK
#define AC_PID_MASK
Definition: util-mpm-ac.c:85
SCACPreparePatterns
int SCACPreparePatterns(MpmCtx *mpm_ctx)
Process the patterns added to the mpm, and create the internal tables.
Definition: util-mpm-ac.c:769
SCACOutputTable_::pids
uint32_t * pids
Definition: util-mpm-ac.h:45
MpmAddPattern
int MpmAddPattern(MpmCtx *mpm_ctx, uint8_t *pat, uint16_t patlen, uint16_t offset, uint16_t depth, uint32_t pid, SigIntId sid, uint8_t flags)
Definition: util-mpm.c:427
DetectEngineCtx_::flags
uint8_t flags
Definition: detect.h:812
MpmTableElmt_::DestroyThreadCtx
void(* DestroyThreadCtx)(struct MpmCtx_ *, struct MpmThreadCtx_ *)
Definition: util-mpm.h:149
AC_CASE_MASK
#define AC_CASE_MASK
Definition: util-mpm-ac.c:84
SCACCtx_::goto_table
int32_t(* goto_table)[256]
Definition: util-mpm-ac.h:66
MpmCtx_
Definition: util-mpm.h:88
SCACDestroyThreadCtx
void SCACDestroyThreadCtx(MpmCtx *, MpmThreadCtx *)
Destroy the mpm thread context.
Definition: util-mpm-ac.c:919
SCACPrintSearchStats
void SCACPrintSearchStats(MpmThreadCtx *mpm_thread_ctx)
Definition: util-mpm-ac.c:1192
SigIntId
#define SigIntId
Definition: suricata-common.h:296
SCACCtx_::single_state_size
uint32_t single_state_size
Definition: util-mpm-ac.h:72
MpmCtx_::ctx
void * ctx
Definition: util-mpm.h:89
MpmAddPatternCI
int MpmAddPatternCI(struct MpmCtx_ *mpm_ctx, uint8_t *pat, uint16_t patlen, uint16_t offset, uint16_t depth, uint32_t pid, SigIntId sid, uint8_t flags)
Definition: util-mpm.c:250
SCMemcmp
#define SCMemcmp(a, b, c)
Definition: util-memcmp.h:289
SCACPatternList_::sids_size
uint32_t sids_size
Definition: util-mpm-ac.h:39
MpmThreadCtx_::ctx
void * ctx
Definition: util-mpm.h:47
DEBUG_VALIDATE_BUG_ON
#define DEBUG_VALIDATE_BUG_ON(exp)
Definition: util-validate.h:111
MpmTableElmt_::RegisterUnittests
void(* RegisterUnittests)(void)
Definition: util-mpm.h:168
StateQueue_::top
int top
Definition: util-mpm-ac-bs.c:89
SCACAddPatternCI
int SCACAddPatternCI(MpmCtx *, uint8_t *, uint16_t, uint16_t, uint16_t, uint32_t, SigIntId, uint8_t)
Add a case insensitive pattern. Although we have different calls for adding case sensitive and insens...
Definition: util-mpm-ac.c:1160
StateQueue_::store
int32_t store[STATE_QUEUE_CONTAINER_SIZE]
Definition: util-mpm-ac-bs.c:88
SCACCtx_::state_table_u32
SC_AC_STATE_TYPE_U32(* state_table_u32)[256]
Definition: util-mpm-ac.h:62
UTHFreePackets
void UTHFreePackets(Packet **p, int numpkts)
UTHFreePackets: function to release the allocated data from UTHBuildPacket and the packet itself.
Definition: util-unittest-helper.c:468