Suricata

Reported by Communications Security Establishment (CSE):

## Summary

The AC-KS multi-pattern matcher computes the size of its packed delta/next-state table as `int size = ctx->state_count * ctx->bytes_per_state * ctx->alphabet_storage;`, storing the product of three unsigned-derived operands in a signed 32-bit `int`. When the Aho-Corasick automaton built from the loaded ruleset has roughly two million states or more, this product overflows `INT_MAX`. In the common case the resulting negative `int` is sign-extended to an enormous `size_t`, `SCCalloc()` fails, and Suricata exits cleanly via `FatalError`. In the rarer wrap-to-small-positive case (≥ ~4.19 M states), `SCCalloc()` returns a tiny buffer that is then written far past its end by the per-state population loop, corrupting the heap during engine initialisation. The sibling `util-mpm-ac.c` matcher guards the equivalent computation with `SCACCheckSafeSizetMult()`; `util-mpm-ac-ks.c` has no such guard.

## Affected Piece of Code

- **File:** `src/util-mpm-ac-ks.c`
- **Function / Location:** `SCACTileClubOutputStatePresenceWithDeltaTable()` ~L660-668
- **Subsystem:** util-mpm-spm — Multi-pattern and single-pattern matchers (Aho-Corasick, Hyperscan, Boyer-Moore)

```c
// src/util-mpm-ac-ks.c
651 static void SCACTileClubOutputStatePresenceWithDeltaTable(MpmCtx *mpm_ctx)
652 {
653     SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
654     SCACTileCtx *ctx = search_ctx->init_ctx;
...
659     /* Allocate next-state table. */
660     int size = ctx->state_count * ctx->bytes_per_state * ctx->alphabet_storage;
661     void *state_table = SCCalloc(1, size);
662     if (unlikely(state_table == NULL)) {
663         FatalError("Error allocating memory");
664     }
665     ctx->state_table = state_table;
666
667     mpm_ctx->memory_cnt++;
668     mpm_ctx->memory_size += size;
...
677     for (state = 0; state < ctx->state_count; state++) {
678         for (aa = 0; aa < ctx->alphabet_size; aa++) {
679             int next_state = ctx->goto_table[state][aa];
680             int next_state_outputs = ctx->output_table[next_state].no_of_entries;
681             ctx->SetNextState(ctx, state, aa, next_state, next_state_outputs);
682         }
683     }
```

## The Bug

### Arithmetic

At L660 the three multiplicands have the following declared types (`src/util-mpm-ac-ks.h`):

- `ctx->state_count` — `uint32_t` (`.h:94`)
- `ctx->bytes_per_state` — `uint8_t` (`.h:107`)
- `ctx->alphabet_storage` — `uint16_t` (`.h:104`)

After C integer promotion, `bytes_per_state` and `alphabet_storage` are promoted to `int`, then the usual arithmetic conversions against the `uint32_t` left operand force the whole multiplication to be performed in **`uint32_t`**. This means the multiplication itself is well-defined modular arithmetic (not signed-overflow UB); the danger lies in the subsequent narrowing of the `uint32_t` result into the signed `int size` lvalue (implementation-defined when the value exceeds `INT_MAX`) and in the modular wrap of the `uint32_t` itself.

In the large-automaton path, `SCACTileCreateDeltaTable()` (L618-624) forces `bytes_per_state = 4` and `alphabet_storage = 256` whenever `state_count ≥ 32767`. The per-state factor is therefore `4 * 256 = 1024`. Two thresholds follow:

1. **`state_count ≥ 2,097,152`** — the `uint32_t` product `state_count * 1024` exceeds `INT_MAX` (2,147,483,647). Storing it into `int size` yields a negative value on the two's-complement targets Suricata supports. That negative `int` is then passed as the second argument of `SCCalloc(1, size)`; the implicit conversion to `size_t` sign-extends it to roughly `1.8 × 10^19` bytes. `calloc` rejects the request, `state_table == NULL`, and the process exits via `FatalError("Error allocating memory")` at L663.

2. **`state_count ≥ 4,194,304`** — the `uint32_t` product itself wraps modulo `2^32`. For example, `state_count = 4,194,305` gives `4,194,305 * 1024 = 4,294,968,320 ≡ 1024 (mod 2^32)`, so `size == 1024`. `SCCalloc(1, 1024)` succeeds and returns a 1 KiB buffer. The loop at L677-683 then iterates over all `4,194,305` states and, for each, calls `ctx->SetNextState`, which on this path is `SCACTileSetState4Bytes` (L539-553). That setter computes `state_table[state * 256 + aa] = encoded_next_state;` against an `int32_t *` view of the buffer — i.e. it writes `4,194,305 * 256 * 4 ≈ 4 GiB` of data into a 1 KiB allocation, a massive heap out-of-bounds write during engine initialisation.

`SCACTileInitNewState()` (L257-282) places no upper bound on `state_count`; it simply `realloc`s the temporary `goto_table` upward as patterns are inserted. Nothing in `util-mpm-ac-ks.c` checks the product before allocating. By contrast, the equivalent code in the default AC matcher uses `SCACCheckSafeSizetMult()` (`src/util-mpm-ac.c:113,139,150,152`) for exactly this purpose; the AC-KS variant simply never received the same hardening.

### Call chain / reachability

The vulnerable line executes only during detection-engine **build time** — i.e. when rules are compiled at startup or during a live rule-reload — never on the packet path:

```
main()
 → PostConfLoadedDetectSetup() / LoadSignatures()        src/suricata.c:2571,2726
  → SigLoadSignatures()                                   src/detect-engine-loader.c:384
   → SigGroupBuild()                                       src/detect-engine-loader.c:515
                                                           → src/detect-engine-build.c:2295
    → DetectMpmPrepare{Builtin,App,Pkt,Frame}Mpms()        src/detect-engine-build.c:2331-2334
     → mpm_table[MPM_AC_KS].Prepare
        = SCACTilePreparePatterns                          src/detect-engine-mpm.c:803-837
                                                           registered at util-mpm-ac-ks.c:1383
      → SCACTilePrepareStateTable()                        util-mpm-ac-ks.c:733
       → SCACTileCreateDeltaTable()                        util-mpm-ac-ks.c:561
          (sets bytes_per_state=4, alphabet_storage=256
           when state_count ≥ 32767, L618-624)
       → SCACTileClubOutputStatePresenceWithDeltaTable()   util-mpm-ac-ks.c:651
          → L660  int size = ...                           ← overflow
```

### Required configuration / field values

- `mpm-algo: ac-ks` in `suricata.yaml` (non-default; default is `auto`, which selects Hyperscan if available, otherwise plain AC).
- A little-endian host — `ac-ks` is rejected on big-endian builds at `src/detect-engine-mpm.c:919-923`.
- An administrator-supplied ruleset whose `content:` patterns, when inserted into a single MPM group, generate **≥ 2,097,152** Aho-Corasick states (negative-`int` / `FatalError` path) or **≥ 4,194,305** states (undersized-allocation / heap-OOB path).

Vulnerability class: **integer-overflow** leading to undersized allocation and heap out-of-bounds write (worst case) or controlled abort (common case).

## Reproduction Results

**Status: analytically derived only — not executed.** No network packet can reach this code; the entire input surface is the locally-trusted YAML configuration plus rule files consumed at process start or live reload. There is therefore no PCAP/PDU artefact to produce.

Conceptual reproduction (not executed):

1. Build Suricata on a little-endian 64-bit host with ≥ 16 GiB RAM. The transient `goto_table` `SCRealloc` in `SCACTileInitNewState()` (`util-mpm-ac-ks.c:237`) must succeed at roughly 8 GiB before L660 is ever reached; this is the main practical blocker.
2. In `suricata.yaml` set:
   ```yaml
   mpm-algo: ac-ks
   detect:
     profile: high        # or sgh-mpm-context: single
   ```
   so that all payload `content:` patterns are placed into one shared MPM context.
3. Generate a rule file containing enough distinct, non-prefix-sharing `content:` patterns to create > 4,194,304 AC states. Since each non-shared pattern byte contributes one trie node, ~4.2 million bytes of unique pattern material suffices. Example generator:
   ```
   for i in 0 .. 524288:
       emit: alert tcp any any -> any any (content:"|XX XX XX XX XX XX XX XX|"; sid:<i>; rev:1;)
   ```
   where the 8-byte hex content is the big-endian encoding of `i`. 524,289 rules × 8 bytes ≈ 4,194,312 unique trie nodes plus the root state.
4. Run:
   ```
   suricata -c suricata.yaml -S huge.rules -r /dev/null
   ```
5. Expected behaviour:
   - At `state_count ≈ 2.1 M`: `SCCalloc` receives a negative `int` → ~18 EB `size_t` → allocation fails → `FatalError("Error allocating memory")`, clean exit.
   - At `state_count ≈ 4.19 M` (only if the 8 GiB `goto_table` realloc succeeded first): `SCCalloc(1, 1024)` succeeds, then `SCACTileSetState4Bytes` writes ~4 GiB past the 1 KiB heap buffer → SIGSEGV / heap corruption during engine init, before any traffic is inspected.

**Blockers preventing a concrete trigger in this audit:** (a) reaching the small-positive wrap first requires an ~8 GiB transient `goto_table` allocation to succeed, which is environment-dependent and was not available in the test harness; (b) the input is administrator-controlled rules/config, not network traffic, so there is no remote trigger to craft.

## Severity

**LOW.**

The defect is **not network-attacker reachable**. The only inputs that influence `state_count` are the locally trusted ruleset and the non-default `mpm-algo: ac-ks` configuration option. The most likely concrete outcome is a clean `FatalError` abort at engine start or rule-reload — effectively a self-inflicted denial of service by an administrator who loads a pathological ruleset. The worst case — reachable only on hosts where an ~8 GiB `goto_table` realloc succeeds — is a drastically undersized `state_table` followed by a multi-gigabyte heap out-of-bounds write during initialisation, which crashes the process before any traffic is inspected. There is no remote code execution, no information leak, and no detection bypass. This is a robustness / hardening gap that mirrors a check the sibling `util-mpm-ac.c` already has.

## Suggested Fix

Compute the allocation size in `size_t` with explicit overflow checking, mirroring `SCACCheckSafeSizetMult()` in `util-mpm-ac.c`, and `FatalError` on overflow. Minimal patch:

```diff
--- a/src/util-mpm-ac-ks.c
+++ b/src/util-mpm-ac-ks.c
@@ -657,9 +657,15 @@ static void SCACTileClubOutputStatePresenceWithDeltaTable(MpmCtx *mpm_ctx)
     uint32_t state = 0;

     /* Allocate next-state table. */
-    int size = ctx->state_count * ctx->bytes_per_state * ctx->alphabet_storage;
+    size_t size = (size_t)ctx->state_count * (size_t)ctx->bytes_per_state;
+    if (ctx->bytes_per_state != 0 && size / ctx->bytes_per_state != ctx->state_count)
+        FatalError("ac-ks state table size overflow");
+    size_t size2 = size * (size_t)ctx->alphabet_storage;
+    if (ctx->alphabet_storage != 0 && size2 / ctx->alphabet_storage != size)
+        FatalError("ac-ks state table size overflow");
+    size = size2;
     void *state_table = SCCalloc(1, size);
     if (unlikely(state_table == NULL)) {
         FatalError("Error allocating memory");
     }
```

A cleaner long-term fix is to factor `SCACCheckSafeSizetMult()` out of `util-mpm-ac.c` into a shared header (e.g. `util-mpm.h`) and reuse it here. The same `int size = …` pattern also appears in `SCACTileCreateFailureTable()` and in `SCACTileDestroyCtx()` at L979; both should be changed to `size_t` at the same time.