/* * Sleelavirin(TM) native Aho-Corasick content matcher - implementation. * Max Rupplin - MEARVK LLC - 2026. * * Original implementation. No code copied from any third-party AV engine. * * Design (see antivirus/SCANNING-CONCEPTS-GLOSSARY.md): * 1. Insert every pattern into a trie (one child slot per byte value, 0..255). * 2. BFS from the root to build failure links (longest proper suffix that is * also a trie node) and to chain each node to the nearest failure-ancestor * that itself carries outputs ("output link"). * 3. Scan: for each input byte follow goto edges, using failure links on a * miss, and emit every pattern terminating at the current node. * * Case handling. Global lowercasing of the whole input is WRONG when some * patterns are case-sensitive and contain ASCII letters (their bytes would be * folded too). We therefore keep TWO independent single-case automata: * - a case-sensitive trie scanned over the raw buffer, and * - a case-insensitive trie (patterns stored lowercased) scanned over a * lazily-built lowercased copy of the buffer. * The public sleelavirin_ac_t owns both; each pattern goes into exactly one. */ #include "sleelavirin_ac.h" #include #include #define SLV_AC_ALPHABET 256u typedef struct slv_ac_output { uint32_t pattern_id; uint32_t length; char *name; /* owned copy, or NULL */ uint8_t severity; struct slv_ac_output *next; } slv_ac_output_t; typedef struct slv_ac_node { int32_t children[SLV_AC_ALPHABET]; /* node index, or -1 */ int32_t fail; slv_ac_output_t *outputs; int32_t out_link; /* nearest failure-ancestor with outputs, or -1 */ } slv_ac_node_t; /* One single-case automaton. */ typedef struct { slv_ac_node_t *nodes; size_t node_count; size_t node_capacity; size_t pattern_count; } slv_ac_trie_t; struct sleelavirin_ac { slv_ac_trie_t cs; /* case-sensitive */ slv_ac_trie_t ci; /* case-insensitive */ size_t pattern_count; size_t max_pattern_len; int compiled; }; static uint8_t lower_ascii(uint8_t c) { return (c >= 'A' && c <= 'Z') ? (uint8_t)(c + ('a' - 'A')) : c; } static int32_t trie_node_alloc(slv_ac_trie_t *t) { size_t i; if (t->node_count == t->node_capacity) { size_t newcap = t->node_capacity ? t->node_capacity * 2u : 64u; slv_ac_node_t *grown; if (newcap > (size_t)INT32_MAX) return -1; grown = (slv_ac_node_t *)realloc(t->nodes, newcap * sizeof(*grown)); if (!grown) return -1; t->nodes = grown; t->node_capacity = newcap; } { slv_ac_node_t *n = &t->nodes[t->node_count]; for (i = 0; i < SLV_AC_ALPHABET; ++i) n->children[i] = -1; n->fail = 0; n->outputs = NULL; n->out_link = -1; } return (int32_t)t->node_count++; } static int trie_init(slv_ac_trie_t *t) { memset(t, 0, sizeof(*t)); return (trie_node_alloc(t) == 0) ? 0 : -1; /* root is node 0 */ } static void trie_free(slv_ac_trie_t *t) { size_t i; for (i = 0; i < t->node_count; ++i) { slv_ac_output_t *o = t->nodes[i].outputs; while (o) { slv_ac_output_t *next = o->next; free(o->name); free(o); o = next; } } free(t->nodes); t->nodes = NULL; t->node_count = t->node_capacity = t->pattern_count = 0; } static int trie_add(slv_ac_trie_t *t, const uint8_t *pattern, size_t length, int lower, uint32_t pattern_id, const char *name, uint8_t severity) { int32_t cur = 0; size_t i; slv_ac_output_t *out; for (i = 0; i < length; ++i) { uint8_t b = lower ? lower_ascii(pattern[i]) : pattern[i]; int32_t next = t->nodes[cur].children[b]; if (next < 0) { next = trie_node_alloc(t); if (next < 0) return -1; /* realloc may have moved the array; re-read cur each iteration. */ t->nodes[cur].children[b] = next; } cur = next; } out = (slv_ac_output_t *)calloc(1, sizeof(*out)); if (!out) return -1; out->pattern_id = pattern_id; out->length = (uint32_t)length; out->severity = severity; if (name) { size_t n = strlen(name); out->name = (char *)malloc(n + 1u); if (!out->name) { free(out); return -1; } memcpy(out->name, name, n + 1u); } out->next = t->nodes[cur].outputs; t->nodes[cur].outputs = out; ++t->pattern_count; return 0; } static int trie_compile(slv_ac_trie_t *t) { int32_t *queue; size_t head = 0, tail = 0; uint32_t c; if (t->node_count == 0) return 0; queue = (int32_t *)malloc(t->node_count * sizeof(*queue)); if (!queue) return -1; for (c = 0; c < SLV_AC_ALPHABET; ++c) { int32_t child = t->nodes[0].children[c]; if (child >= 0) { t->nodes[child].fail = 0; queue[tail++] = child; } } while (head < tail) { int32_t u = queue[head++]; for (c = 0; c < SLV_AC_ALPHABET; ++c) { int32_t v = t->nodes[u].children[c]; int32_t f; if (v < 0) continue; /* failure link: walk u's failure chain to a node with edge c. */ f = t->nodes[u].fail; while (f != 0 && t->nodes[f].children[c] < 0) f = t->nodes[f].fail; if (t->nodes[f].children[c] >= 0 && t->nodes[f].children[c] != v) f = t->nodes[f].children[c]; else f = 0; t->nodes[v].fail = f; /* output link: nearest failure-ancestor carrying outputs. */ t->nodes[v].out_link = (t->nodes[f].outputs != NULL) ? f : t->nodes[f].out_link; queue[tail++] = v; } } free(queue); return 0; } static long trie_scan(const slv_ac_trie_t *t, const uint8_t *buffer, size_t length, sleelavirin_ac_cb cb, void *user_data, int *stop) { int32_t cur = 0; size_t i; long matches = 0; if (t->node_count == 0) return 0; for (i = 0; i < length; ++i) { uint8_t b = buffer[i]; int32_t emit; while (cur != 0 && t->nodes[cur].children[b] < 0) cur = t->nodes[cur].fail; if (t->nodes[cur].children[b] >= 0) cur = t->nodes[cur].children[b]; emit = cur; while (emit >= 0) { slv_ac_output_t *o = t->nodes[emit].outputs; while (o) { sleelavirin_ac_match_t m; m.pattern_id = o->pattern_id; m.end_offset = (uint64_t)i + 1u; m.length = o->length; m.name = o->name; m.severity = o->severity; ++matches; if (cb(&m, user_data) != 0) { *stop = 1; return matches; } o = o->next; } emit = t->nodes[emit].out_link; } } return matches; } sleelavirin_ac_t *sleelavirin_ac_create(void) { sleelavirin_ac_t *ac = (sleelavirin_ac_t *)calloc(1, sizeof(*ac)); if (!ac) return NULL; if (trie_init(&ac->cs) != 0 || trie_init(&ac->ci) != 0) { trie_free(&ac->cs); trie_free(&ac->ci); free(ac); return NULL; } return ac; } void sleelavirin_ac_destroy(sleelavirin_ac_t *ac) { if (!ac) return; trie_free(&ac->cs); trie_free(&ac->ci); free(ac); } int sleelavirin_ac_add(sleelavirin_ac_t *ac, const uint8_t *pattern, size_t length, uint32_t pattern_id, const char *name, uint8_t severity, int nocase) { int rc; if (!ac || !pattern || length == 0) return -1; if (ac->compiled) return -2; if (length > (size_t)UINT32_MAX) return -1; rc = nocase ? trie_add(&ac->ci, pattern, length, 1, pattern_id, name, severity) : trie_add(&ac->cs, pattern, length, 0, pattern_id, name, severity); if (rc != 0) return -1; ++ac->pattern_count; if (length > ac->max_pattern_len) ac->max_pattern_len = length; return 0; } int sleelavirin_ac_compile(sleelavirin_ac_t *ac) { if (!ac) return -1; if (ac->compiled) return 0; if (trie_compile(&ac->cs) != 0) return -1; if (trie_compile(&ac->ci) != 0) return -1; ac->compiled = 1; return 0; } long sleelavirin_ac_scan(const sleelavirin_ac_t *ac, const uint8_t *buffer, size_t length, sleelavirin_ac_cb cb, void *user_data) { long total = 0, n; int stop = 0; if (!ac || !ac->compiled || !cb) return -1; if (!buffer && length) return -1; /* Case-sensitive pass over raw bytes. */ n = trie_scan(&ac->cs, buffer, length, cb, user_data, &stop); if (n < 0) return -1; total += n; if (stop) return total; /* Case-insensitive pass over a lowercased copy (only if such patterns * exist, to avoid an allocation and second pass otherwise). */ if (ac->ci.pattern_count > 0 && length > 0) { uint8_t *lowered = (uint8_t *)malloc(length); size_t i; if (!lowered) return -1; for (i = 0; i < length; ++i) lowered[i] = lower_ascii(buffer[i]); n = trie_scan(&ac->ci, lowered, length, cb, user_data, &stop); free(lowered); if (n < 0) return -1; total += n; } return total; } size_t sleelavirin_ac_pattern_count(const sleelavirin_ac_t *ac) { return ac ? ac->pattern_count : 0u; } size_t sleelavirin_ac_max_pattern_len(const sleelavirin_ac_t *ac) { return ac ? ac->max_pattern_len : 0u; }