76 static void SCACRegisterTests(
void);
80 #define SC_AC_FAIL (-1)
82 #define STATE_QUEUE_CONTAINER_SIZE 65536
84 #define AC_CASE_MASK 0x80000000
85 #define AC_PID_MASK 0x7FFFFFFF
86 #define AC_CASE_BIT 31
88 static int construct_both_16_and_32_state_tables = 0;
105 static void SCACGetConfig(
void)
125 static inline size_t SCACCheckSafeSizetMult(
size_t a,
size_t b)
128 if (b > 0 && a > SIZE_MAX / b) {
129 SCLogError(
"%" PRIuMAX
" * %" PRIuMAX
" > %" PRIuMAX
130 " would overflow size_t calculating buffer size",
131 (uintmax_t)a, (uintmax_t)b, (uintmax_t)SIZE_MAX);
145 static inline int SCACReallocState(
SCACCtx *ctx, uint32_t
cnt)
162 size_t oldsize = SCACCheckSafeSizetMult((
size_t) ctx->
state_count,
165 SCLogDebug(
"oldsize %"PRIuMAX
" size %"PRIuMAX
" cnt %d ctx->state_count %u",
178 memset(((uint8_t *)ctx->
output_table + oldsize), 0, (size - oldsize));
195 static void SCACShrinkState(
SCACCtx *ctx)
203 SCLogDebug(
"oldsize %d newsize %d ctx->allocated_state_count %u "
204 "ctx->state_count %u: shrink by %d bytes", oldsize,
217 static inline int SCACInitNewState(
MpmCtx *mpm_ctx)
239 for (ascii_code = 0; ascii_code < 256; ascii_code++) {
254 static void SCACSetOutputState(int32_t state, uint32_t pid,
MpmCtx *mpm_ctx)
261 for (i = 0; i < output_state->no_of_entries; i++) {
262 if (output_state->pids[i] == pid)
268 output_state->no_of_entries *
sizeof(uint32_t));
270 SCFree(output_state->pids);
271 output_state->pids = NULL;
274 output_state->pids = ptmp;
276 output_state->pids[output_state->no_of_entries - 1] = pid;
291 static inline void SCACEnter(uint8_t *pattern, uint16_t pattern_len, uint32_t pid,
296 int32_t newstate = 0;
302 for (i = 0; i < pattern_len; i++) {
312 for (p = i; p < pattern_len; p++) {
313 newstate = SCACInitNewState(mpm_ctx);
314 ctx->
goto_table[state][pattern[p]] = newstate;
320 SCACSetOutputState(state, pid, mpm_ctx);
331 static inline void SCACCreateGotoTable(
MpmCtx *mpm_ctx)
343 for (ascii_code = 0; ascii_code < 256; ascii_code++) {
352 static inline void SCACDetermineLevel1Gap(
MpmCtx *mpm_ctx)
358 memset(map, 0,
sizeof(map));
363 for (u = 0; u < 256; u++) {
366 int32_t newstate = SCACInitNewState(mpm_ctx);
373 static inline int SCACStateQueueIsEmpty(
StateQueue *q)
381 static inline void SCACEnqueue(
StateQueue *q, int32_t state)
386 for (i = q->
bot; i < q->top; i++) {
387 if (q->
store[i] == state)
397 FatalError(
"Just ran out of space in the queue. Please file a bug report on this");
403 static inline int32_t SCACDequeue(
StateQueue *q)
409 FatalError(
"StateQueue behaving weirdly. Please file a bug report on this");
424 static inline void SCACClubOutputStates(int32_t dst_state, int32_t src_state,
435 for (i = 0; i < output_src_state->no_of_entries; i++) {
436 for (j = 0; j < output_dst_state->no_of_entries; j++) {
437 if (output_src_state->pids[i] == output_dst_state->pids[j]) {
441 if (j == output_dst_state->no_of_entries) {
445 (output_dst_state->no_of_entries *
sizeof(uint32_t)));
447 SCFree(output_dst_state->pids);
448 output_dst_state->pids = NULL;
451 output_dst_state->pids = ptmp;
453 output_dst_state->pids[output_dst_state->no_of_entries - 1] =
454 output_src_state->pids[i];
467 static inline void SCACCreateFailureTable(
MpmCtx *mpm_ctx)
489 for (ascii_code = 0; ascii_code < 256; ascii_code++) {
490 int32_t temp_state = ctx->
goto_table[0][ascii_code];
491 if (temp_state != 0) {
492 SCACEnqueue(q, temp_state);
497 while (!SCACStateQueueIsEmpty(q)) {
499 r_state = SCACDequeue(q);
500 for (ascii_code = 0; ascii_code < 256; ascii_code++) {
501 int32_t temp_state = ctx->
goto_table[r_state][ascii_code];
504 SCACEnqueue(q, temp_state);
510 SCACClubOutputStates(temp_state, ctx->
failure_table[temp_state],
525 static inline void SCACCreateDeltaTable(
MpmCtx *mpm_ctx)
531 if ((ctx->
state_count < 32767) || construct_both_16_and_32_state_tables) {
544 for (ascii_code = 0; ascii_code < 256; ascii_code++) {
549 SCACEnqueue(q, temp_state);
552 while (!SCACStateQueueIsEmpty(q)) {
553 r_state = SCACDequeue(q);
555 for (ascii_code = 0; ascii_code < 256; ascii_code++) {
556 int32_t temp_state = ctx->
goto_table[r_state][ascii_code];
558 SCACEnqueue(q, temp_state);
570 if (!(ctx->
state_count < 32767) || construct_both_16_and_32_state_tables) {
586 for (ascii_code = 0; ascii_code < 256; ascii_code++) {
590 SCACEnqueue(q, temp_state);
593 while (!SCACStateQueueIsEmpty(q)) {
594 r_state = SCACDequeue(q);
596 for (ascii_code = 0; ascii_code < 256; ascii_code++) {
597 int32_t temp_state = ctx->
goto_table[r_state][ascii_code];
599 SCACEnqueue(q, temp_state);
613 static inline void SCACClubOutputStatePresenceWithDeltaTable(
MpmCtx *mpm_ctx)
618 uint32_t temp_state = 0;
620 if ((ctx->
state_count < 32767) || construct_both_16_and_32_state_tables) {
621 for (state = 0; state < ctx->
state_count; state++) {
622 for (ascii_code = 0; ascii_code < 256; ascii_code++) {
630 if (!(ctx->
state_count < 32767) || construct_both_16_and_32_state_tables) {
631 for (state = 0; state < ctx->
state_count; state++) {
632 for (ascii_code = 0; ascii_code < 256; ascii_code++) {
643 static inline void SCACInsertCaseSensitiveEntriesForPatterns(
MpmCtx *mpm_ctx)
649 for (state = 0; state < ctx->
state_count; state++) {
665 static void SCACPrintDeltaTable(
MpmCtx *mpm_ctx)
670 printf(
"##############Delta Table##############\n");
673 for (j = 0; j < 256; j++) {
674 if (SCACGetDelta(i, j, mpm_ctx) != 0) {
675 printf(
" %c -> %d\n", j, SCACGetDelta(i, j, mpm_ctx));
689 static void SCACPrepareStateTable(
MpmCtx *mpm_ctx)
694 SCACInitNewState(mpm_ctx);
696 SCACDetermineLevel1Gap(mpm_ctx);
699 SCACCreateGotoTable(mpm_ctx);
701 SCACCreateFailureTable(mpm_ctx);
703 SCACCreateDeltaTable(mpm_ctx);
705 SCACClubOutputStatePresenceWithDeltaTable(mpm_ctx);
708 SCACInsertCaseSensitiveEntriesForPatterns(mpm_ctx);
711 SCACShrinkState(ctx);
714 SCACPrintDeltaTable(mpm_ctx);
736 SCLogDebug(
"no patterns supplied to this mpm_ctx");
748 uint32_t i = 0, p = 0;
751 while(node != NULL) {
797 SCACPrepareStateTable(mpm_ctx);
801 if (ctx->
parray[i] != NULL) {
826 if (mpm_ctx->
ctx != NULL)
830 if (mpm_ctx->
ctx == NULL) {
868 if (ctx->
parray != NULL) {
871 if (ctx->
parray[i] != NULL) {
900 uint32_t state_count;
901 for (state_count = 0; state_count < ctx->
state_count; state_count++) {
911 for (i = 0; i < (mpm_ctx->
max_pat_id + 1); i++) {
957 for (uint32_t i = 0; i < buflen; i++) {
958 state = state_table_u16[state & 0x7FFF][
u8_tolower(buf[i])];
959 if (state & 0x8000) {
962 for (uint32_t k = 0; k < no_of_entries; k++) {
977 if (!(bitarray[(lower_pid) / 8] & (1 << ((lower_pid) % 8)))) {
978 bitarray[(lower_pid) / 8] |= (1 << ((lower_pid) % 8));
991 if (!(bitarray[pids[k] / 8] & (1 << (pids[k] % 8)))) {
992 bitarray[pids[k] / 8] |= (1 << (pids[k] % 8));
1003 for (uint32_t i = 0; i < buflen; i++) {
1004 state = state_table_u32[state & 0x00FFFFFF][
u8_tolower(buf[i])];
1005 if (state & 0xFF000000) {
1008 for (uint32_t k = 0; k < no_of_entries; k++) {
1010 const uint32_t lower_pid = pids[k] & 0x0000FFFF;
1024 if (!(bitarray[(lower_pid) / 8] & (1 << ((lower_pid) % 8)))) {
1025 bitarray[(lower_pid) / 8] |= (1 << ((lower_pid) % 8));
1038 if (!(bitarray[pids[k] / 8] & (1 << (pids[k] % 8)))) {
1039 bitarray[pids[k] / 8] |= (1 << (pids[k] % 8));
1069 uint16_t
offset, uint16_t depth, uint32_t pid,
1094 uint16_t
offset, uint16_t depth, uint32_t pid,
1104 printf(
"MPM AC Information:\n");
1105 printf(
"Memory allocs: %" PRIu32
"\n", mpm_ctx->
memory_cnt);
1106 printf(
"Memory alloced: %" PRIu32
"\n", mpm_ctx->
memory_size);
1107 printf(
" Sizeof:\n");
1108 printf(
" MpmCtx %" PRIuMAX
"\n", (uintmax_t)
sizeof(
MpmCtx));
1109 printf(
" SCACCtx: %" PRIuMAX
"\n", (uintmax_t)
sizeof(
SCACCtx));
1110 printf(
" MpmPattern %" PRIuMAX
"\n", (uintmax_t)
sizeof(
MpmPattern));
1111 printf(
" MpmPattern %" PRIuMAX
"\n", (uintmax_t)
sizeof(
MpmPattern));
1112 printf(
"Unique Patterns: %" PRIu32
"\n", mpm_ctx->
pattern_cnt);
1113 printf(
"Smallest: %" PRIu32
"\n", mpm_ctx->
minlen);
1114 printf(
"Largest: %" PRIu32
"\n", mpm_ctx->
maxlen);
1115 printf(
"Total states in the state table: %" PRIu32
"\n", ctx->
state_count);
1149 static int SCACTest01(
void)
1156 memset(&mpm_ctx, 0,
sizeof(
MpmCtx));
1166 const char *buf =
"abcdefghjiklmnopqrstuvwxyz";
1169 (uint8_t *)buf, strlen(buf));
1174 printf(
"1 != %" PRIu32
" ",
cnt);
1181 static int SCACTest02(
void)
1188 memset(&mpm_ctx, 0,
sizeof(
MpmCtx));
1198 const char *buf =
"abcdefghjiklmnopqrstuvwxyz";
1200 (uint8_t *)buf, strlen(buf));
1205 printf(
"0 != %" PRIu32
" ",
cnt);
1212 static int SCACTest03(
void)
1219 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1233 const char *buf =
"abcdefghjiklmnopqrstuvwxyz";
1235 (uint8_t *)buf, strlen(buf));
1240 printf(
"3 != %" PRIu32
" ",
cnt);
1247 static int SCACTest04(
void)
1254 memset(&mpm_ctx, 0,
sizeof(
MpmCtx));
1265 const char *buf =
"abcdefghjiklmnopqrstuvwxyz";
1267 (uint8_t *)buf, strlen(buf));
1272 printf(
"1 != %" PRIu32
" ",
cnt);
1279 static int SCACTest05(
void)
1286 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1297 const char *buf =
"abcdefghjiklmnopqrstuvwxyz";
1299 (uint8_t *)buf, strlen(buf));
1304 printf(
"3 != %" PRIu32
" ",
cnt);
1311 static int SCACTest06(
void)
1318 memset(&mpm_ctx, 0,
sizeof(
MpmCtx));
1327 const char *buf =
"abcd";
1329 (uint8_t *)buf, strlen(buf));
1334 printf(
"1 != %" PRIu32
" ",
cnt);
1341 static int SCACTest07(
void)
1347 memset(&mpm_ctx, 0,
sizeof(
MpmCtx));
1360 MpmAddPatternCS(&mpm_ctx, (uint8_t *)
"AAAAAAAAAA", 10, 0, 0, 4, 0, 0);
1362 MpmAddPatternCS(&mpm_ctx, (uint8_t *)
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
1369 const char *buf =
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
1371 (uint8_t *)buf, strlen(buf));
1379 static int SCACTest08(
void)
1386 memset(&mpm_ctx, 0,
sizeof(
MpmCtx));
1402 printf(
"0 != %" PRIu32
" ",
cnt);
1409 static int SCACTest09(
void)
1416 memset(&mpm_ctx, 0,
sizeof(
MpmCtx));
1427 (uint8_t *)
"ab", 2);
1432 printf(
"1 != %" PRIu32
" ",
cnt);
1439 static int SCACTest10(
void)
1446 memset(&mpm_ctx, 0,
sizeof(
MpmCtx));
1456 const char *buf =
"01234567890123456789012345678901234567890123456789"
1457 "01234567890123456789012345678901234567890123456789"
1459 "01234567890123456789012345678901234567890123456789"
1460 "01234567890123456789012345678901234567890123456789";
1462 (uint8_t *)buf, strlen(buf));
1467 printf(
"1 != %" PRIu32
" ",
cnt);
1474 static int SCACTest11(
void)
1481 memset(&mpm_ctx, 0,
sizeof(
MpmCtx));
1485 if (
MpmAddPatternCS(&mpm_ctx, (uint8_t *)
"he", 2, 0, 0, 1, 0, 0) == -1)
1487 if (
MpmAddPatternCS(&mpm_ctx, (uint8_t *)
"she", 3, 0, 0, 2, 0, 0) == -1)
1489 if (
MpmAddPatternCS(&mpm_ctx, (uint8_t *)
"his", 3, 0, 0, 3, 0, 0) == -1)
1491 if (
MpmAddPatternCS(&mpm_ctx, (uint8_t *)
"hers", 4, 0, 0, 4, 0, 0) == -1)
1500 const char *buf =
"he";
1501 result &= (
SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1504 result &= (
SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1507 result &= (
SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1510 result &= (
SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1519 static int SCACTest12(
void)
1526 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1538 const char *buf =
"abcdefghijklmnopqrstuvwxyz";
1540 (uint8_t *)buf, strlen(buf));
1545 printf(
"2 != %" PRIu32
" ",
cnt);
1552 static int SCACTest13(
void)
1559 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1564 const char pat[] =
"abcdefghijklmnopqrstuvwxyzABCD";
1565 MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat,
sizeof(pat) - 1, 0, 0, 0, 0, 0);
1570 const char *buf =
"abcdefghijklmnopqrstuvwxyzABCD";
1572 (uint8_t *)buf, strlen(buf));
1577 printf(
"1 != %" PRIu32
" ",
cnt);
1584 static int SCACTest14(
void)
1591 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1596 const char pat[] =
"abcdefghijklmnopqrstuvwxyzABCDE";
1597 MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat,
sizeof(pat) - 1, 0, 0, 0, 0, 0);
1602 const char *buf =
"abcdefghijklmnopqrstuvwxyzABCDE";
1604 (uint8_t *)buf, strlen(buf));
1609 printf(
"1 != %" PRIu32
" ",
cnt);
1616 static int SCACTest15(
void)
1623 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1628 const char pat[] =
"abcdefghijklmnopqrstuvwxyzABCDEF";
1629 MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat,
sizeof(pat) - 1, 0, 0, 0, 0, 0);
1634 const char *buf =
"abcdefghijklmnopqrstuvwxyzABCDEF";
1636 (uint8_t *)buf, strlen(buf));
1641 printf(
"1 != %" PRIu32
" ",
cnt);
1648 static int SCACTest16(
void)
1655 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1660 const char pat[] =
"abcdefghijklmnopqrstuvwxyzABC";
1661 MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat,
sizeof(pat) - 1, 0, 0, 0, 0, 0);
1666 const char *buf =
"abcdefghijklmnopqrstuvwxyzABC";
1668 (uint8_t *)buf, strlen(buf));
1673 printf(
"1 != %" PRIu32
" ",
cnt);
1680 static int SCACTest17(
void)
1687 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1692 const char pat[] =
"abcdefghijklmnopqrstuvwxyzAB";
1693 MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat,
sizeof(pat) - 1, 0, 0, 0, 0, 0);
1698 const char *buf =
"abcdefghijklmnopqrstuvwxyzAB";
1700 (uint8_t *)buf, strlen(buf));
1705 printf(
"1 != %" PRIu32
" ",
cnt);
1712 static int SCACTest18(
void)
1719 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1724 const char pat[] =
"abcde"
1730 MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat,
sizeof(pat) - 1, 0, 0, 0, 0, 0);
1735 const char *buf =
"abcde""fghij""klmno""pqrst""uvwxy""z";
1737 (uint8_t *)buf, strlen(buf));
1742 printf(
"1 != %" PRIu32
" ",
cnt);
1749 static int SCACTest19(
void)
1756 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1761 const char pat[] =
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
1762 MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat,
sizeof(pat) - 1, 0, 0, 0, 0, 0);
1767 const char *buf =
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
1769 (uint8_t *)buf, strlen(buf));
1774 printf(
"1 != %" PRIu32
" ",
cnt);
1781 static int SCACTest20(
void)
1788 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1793 const char pat[] =
"AAAAA"
1800 MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat,
sizeof(pat) - 1, 0, 0, 0, 0, 0);
1805 const char *buf =
"AAAAA""AAAAA""AAAAA""AAAAA""AAAAA""AAAAA""AA";
1807 (uint8_t *)buf, strlen(buf));
1812 printf(
"1 != %" PRIu32
" ",
cnt);
1819 static int SCACTest21(
void)
1826 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1837 (uint8_t *)
"AA", 2);
1842 printf(
"1 != %" PRIu32
" ",
cnt);
1849 static int SCACTest22(
void)
1856 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1868 const char *buf =
"abcdefghijklmnopqrstuvwxyz";
1870 (uint8_t *)buf, strlen(buf));
1875 printf(
"2 != %" PRIu32
" ",
cnt);
1882 static int SCACTest23(
void)
1889 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1900 (uint8_t *)
"aa", 2);
1905 printf(
"1 != %" PRIu32
" ",
cnt);
1912 static int SCACTest24(
void)
1919 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1930 (uint8_t *)
"aa", 2);
1935 printf(
"1 != %" PRIu32
" ",
cnt);
1942 static int SCACTest25(
void)
1949 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1960 const char *buf =
"ABCDEFGHIJKLMNOPQRSTUVWXYZ";
1962 (uint8_t *)buf, strlen(buf));
1967 printf(
"3 != %" PRIu32
" ",
cnt);
1974 static int SCACTest26(
void)
1981 memset(&mpm_ctx, 0x00,
sizeof(
MpmCtx));
1991 const char *buf =
"works";
1993 (uint8_t *)buf, strlen(buf));
1998 printf(
"3 != %" PRIu32
" ",
cnt);
2005 static int SCACTest27(
void)
2012 memset(&mpm_ctx, 0,
sizeof(
MpmCtx));
2022 const char *buf =
"tone";
2024 (uint8_t *)buf, strlen(buf));
2029 printf(
"0 != %" PRIu32
" ",
cnt);
2036 static int SCACTest28(
void)
2042 memset(&mpm_ctx, 0,
sizeof(
MpmCtx));
2052 const char *buf =
"tONE";
2054 (uint8_t *)buf, strlen(buf));
2062 static int SCACTest29(
void)
2064 uint8_t buf[] =
"onetwothreefourfivesixseveneightnine";
2065 uint16_t buflen =
sizeof(buf) - 1;
2069 memset(&th_v, 0,
sizeof(th_v));
2078 "alert tcp any any -> any any "
2079 "(content:\"onetwothreefourfivesixseveneightnine\"; sid:1;)");
2082 "alert tcp any any -> any any "
2083 "(content:\"onetwothreefourfivesixseveneightnine\"; fast_pattern:3,3; sid:2;)");
2103 static int SCACTest30(
void)
2109 memset(&mpm_ctx, 0,
sizeof(
MpmCtx));
2119 const char *buf1 =
"abcdefghijklmnopqrstuvwxyz";
2120 uint32_t
cnt =
SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf1, strlen(buf1));
2122 const char *buf2 =
"xyzxyzxyzxyzxyzxyzxyza";
2123 cnt =
SCACSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf2, strlen(buf2));
2131 void SCACRegisterTests(
void)