Suricata

Reported by Communications Security Establishment (CSE):

## Summary

The Aho-Corasick multi-pattern matcher (`SCACSearch`) stores case-sensitive pattern IDs
with only bit 31 used as the case flag, leaving bits 0–30 for the PID. The u16 search
branch correctly recovers the PID with `AC_PID_MASK` (0x7FFFFFFF), but the u32 branch —
taken whenever the automaton has ≥ 32767 states — recovers it with the literal
`0x0000FFFF`, silently discarding PID bits 16–30. When a deployment loads more than
65536 distinct case-sensitive fast-patterns into a single AC context, every pattern with
internal id ≥ 65536 is looked up in the wrong `pid_pat_list[]` slot at match time. The
result is a deterministic detection bypass for those signatures (and possible
false-positive firing of the aliased signature). The truncated index stays in-bounds and
the offset/length arithmetic is still bounded, so no memory-safety violation occurs.

## Affected Piece of Code

- **File:** `src/util-mpm-ac.c`
- **Function / Location:** `SCACSearch()` u32 branch, ~L913–960 (specifically L923)
- **Subsystem:** util-mpm-spm — Multi-pattern and single-pattern matchers (Aho-Corasick,
  Hyperscan, Boyer-Moore)

```c
/* /home/omuser/claude/suricata/src/util-mpm-ac.c */
913      } else {
914          register SC_AC_STATE_TYPE_U32 state = 0;
915          const SC_AC_STATE_TYPE_U32(*state_table_u32)[256] = ctx->state_table_u32;
916          for (uint32_t i = 0; i < buflen; i++) {
917              state = state_table_u32[state & 0x00FFFFFF][u8_tolower(buf[i])];
918              if (state & 0xFF000000) {
919                  const uint32_t no_of_entries = ctx->output_table[state & 0x00FFFFFF].no_of_entries;
920                  const uint32_t *pids = ctx->output_table[state & 0x00FFFFFF].pids;
921                  for (uint32_t k = 0; k < no_of_entries; k++) {
922                      if (pids[k] & AC_CASE_MASK) {
923                          const uint32_t lower_pid = pids[k] & 0x0000FFFF;   /* BUG: should be AC_PID_MASK (0x7FFFFFFF) */
924                          const SCACPatternList *pat = &pid_pat_list[lower_pid];
925                          const int offset = i - pat->patlen + 1;
926
927                          if (offset < (int)pat->offset || (pat->depth && i > pat->depth))
928                              continue;
929                          if (pat->endswith && (uint32_t)offset + pat->patlen != buflen)
930                              continue;
931
932                          if (SCMemcmp(pat->cs, buf + offset,
933                                       pat->patlen) != 0) {
```

For comparison, the construction code that encodes the PID and the sibling u16 branch
that decodes it correctly:

```c
/* construction — src/util-mpm-ac.c:574-578 */
for (k = 0; k < ctx->output_table[state].no_of_entries; k++) {
    if (ctx->pid_pat_list[ctx->output_table[state].pids[k]].cs != NULL) {
        ctx->output_table[state].pids[k] &= AC_PID_MASK;          /* 0x7FFFFFFF */
        ctx->output_table[state].pids[k] |= ((uint32_t)1 << AC_CASE_BIT);
    }
}

/* u16 search branch — src/util-mpm-ac.c:876-878 */
if (pids[k] & AC_CASE_MASK) {
    const uint32_t lower_pid = pids[k] & AC_PID_MASK;              /* correct */
    const SCACPatternList *pat = &pid_pat_list[lower_pid];
```

## The Bug

### Encoding vs. decoding mismatch

During automaton construction (`SCACInsertCaseSensitiveEntriesForPatterns`, L570–580),
every case-sensitive pattern ID stored in `output_table[].pids[]` is encoded as:

```
pids[k] = (original_pid & AC_PID_MASK) | (1u << AC_CASE_BIT);
         = (original_pid & 0x7FFFFFFF) | 0x80000000;
```

Only bit 31 is the flag; bits 0–30 carry the PID. `max_pat_id` is a plain `uint32_t`
that is incremented unbounded for every unique pattern added (`util-mpm.c:463`,
`p->id = mpm_ctx->max_pat_id++`). Nothing in `SCACPreparePatterns()` or
`MpmAddPattern()` caps it at 16 bits.

At search time, the u16-state branch (taken when `ctx->state_count < 32767`) correctly
inverts this encoding with `pids[k] & AC_PID_MASK` (L877). The u32-state branch —
entered at L913 precisely when the ruleset is large enough that PID > 65535 becomes
plausible — instead uses the hard-coded literal `0x0000FFFF` (L923). For any
case-sensitive pattern whose internally assigned `id ≥ 65536`, bits 16–30 are dropped
and `lower_pid` becomes `id mod 65536`.

### Consequences of the wrong index

`pid_pat_list[lower_pid]` then resolves to a *different, valid* `SCACPatternList` entry
(the array is `calloc`'d with `max_pat_id + 1` elements at L683, so
`lower_pid ≤ 65535 < max_pat_id + 1` is always in-bounds). The aliased entry's `patlen`,
`cs`, `offset`, `depth`, `endswith`, and `sids` are used in place of the real ones:

1. **Detection bypass.** `SCMemcmp(pat->cs, buf + offset, pat->patlen)` at L932 compares
   the *wrong* literal against the haystack. In the overwhelmingly common case the bytes
   differ, the loop `continue`s, and the intended signature's `sids` are never pushed
   into the `PrefilterRuleStore`. The rule never reaches the candidate list in
   `DetectRun()` and produces no alert.
2. **False positive / cross-fire.** If the aliased slot's `cs`/`patlen` happen to match
   the bytes at `buf + offset` (e.g. one pattern is a suffix of the other), the *wrong*
   `pat->sids` are pushed via `PrefilterAddSids()` (L939), and the de-dup `bitarray` bit
   is set/tested for the wrong PID (L937–938), which can additionally suppress a later
   legitimate hit on the aliased pattern.
3. **No OOB read.** Although the title mentions OOB read as the apparent risk, analysis
   shows the access stays bounded:
   - `lower_pid` is always a valid index into `pid_pat_list` (see above).
   - A negative `offset = i - pat->patlen + 1` from a *longer* aliased `patlen` is
     rejected by `offset < (int)pat->offset` at L927 (`pat->offset` is `uint16_t`, so
     the cast yields a value ≥ 0 and any negative `offset` fails the check).
   - The upper bound holds because `offset + pat->patlen == i + 1 ≤ buflen`, so
     `SCMemcmp` never reads past the haystack end.
   - If the aliased slot is a nocase pattern (`cs == NULL`), its `patlen` field is 0, so
     `SCMemcmp(NULL, _, 0)` is a no-op.

### Call chain from the wire to L923

```
capture-thread slot
  → FlowWorker()                         src/flow-worker.c:562
    → Detect()                           src/flow-worker.c:403/457 → src/detect.c:2846/2860
      → DetectRun()                      src/detect.c:106
        → DetectRunPrefilterPkt()        src/detect.c:622
          → Prefilter()                  src/detect-engine-prefilter.c:219
            → engine->cb.Prefilter == PrefilterPktPayload()
                                         src/detect-engine-payload.c:116
              → mpm_table[MPM_AC].Search == SCACSearch()
                                         src/util-mpm-ac.c:854
                  buf    = p->payload
                  buflen = p->payload_len
                  ctx->state_count >= 32767  → u32 branch at L913
                  pids[k] has bit31 set (set at L576-577) → L922 true
                  lower_pid = pids[k] & 0x0000FFFF        → L923 truncates
```

### Required field values / preconditions

- `mpm-algo: ac` (the pure-software Aho-Corasick matcher; non-default when Hyperscan is
  compiled in).
- `detect.sgh-mpm-context: single`, so that all fast-patterns are concentrated into one
  `MpmCtx`.
- ≥ 65537 *unique* case-sensitive fast-pattern strings registered into that `MpmCtx`, so
  that at least one receives internal `id ≥ 65536`. This many distinct strings also
  guarantees `state_count ≥ 32767`, forcing the u32 table and the buggy branch.
- Attacker sends a packet whose payload contains the literal bytes of one of those
  high-PID patterns.

**Vulnerability class:** network-reachable logic bypass (mis-indexed lookup); originally
suspected OOB read ruled out on closer analysis.

## Reproduction Results

**Precondition (operator-side, not attacker-controllable):**

1. `suricata.yaml`:
   ```yaml
   mpm-algo: ac
   detect:
     sgh-mpm-context: single
   ```

2. Generate a rule file with > 65536 rules, each carrying a unique case-sensitive
   `content` that is selected as the fast-pattern and lands in the same payload MPM
   context:
   ```sh
   for i in $(seq 1 70000); do
     printf 'alert udp any any -> any 9999 (msg:"r%d"; content:"UNIQPATTERN%07d"; fast_pattern; sid:%d; rev:1;)\n' $i $i $i
   done > big.rules
   ```
   All 70000 contents are 18-byte unique case-sensitive strings. With
   `sgh-mpm-context: single` they are all added to one `MpmCtx` via `MpmAddPattern()`,
   where each new unique pattern gets `p->id = mpm_ctx->max_pat_id++`
   (`util-mpm.c:463`). The 65537th distinct pattern therefore receives internal
   pid 65536. The 70000 distinct strings also push `state_count` well past 32767, so
   `SCACPrepareStateTable()` builds the u32 table.

3. Start Suricata with this rules file. The build is memory-heavy but loads;
   `SCACPreparePatterns()` imposes no 16-bit cap on `max_pat_id`.

**Attacker step (network):**

4. Send one UDP datagram to `<sensor-monitored-host>:9999` whose payload is exactly the
   18 ASCII bytes of the pattern that received internal pid 65536. Assuming
   `MpmAddPattern()` is invoked in rule-load order, that is the literal for sid 65537:
   ```
   payload = 55 4e 49 51 50 41 54 54 45 52 4e 30 30 36 35 35 33 37
           = "UNIQPATTERN0065537" 
   ```
   Full frame: any L2/L3 that Suricata decodes — e.g. Ethernet / IPv4 / UDP dport 9999,
   UDP payload = the 18 bytes above.

**Expected vs. actual:**

5. *Expected:* alert for sid 65537.
   *Actual:* `SCACSearch()` walks the automaton to the accepting state;
   `pids[k] = 0x80010000`; L923 computes `lower_pid = 0x80010000 & 0x0000FFFF = 0`;
   `pid_pat_list[0].cs = "UNIQPATTERN0000001"`;
   `SCMemcmp("UNIQPATTERN0000001", "UNIQPATTERN0065537", 18) != 0` → `continue`. sid
   65537's `sids` never enter `det_ctx->pmq`, `DetectRun()` never evaluates the rule,
   and no alert is emitted. (Conversely, if the aliased slot's `cs`/`patlen` happened to
   match the bytes at `buf + offset`, the *wrong* `sids` would be pushed — a false
   positive.)

**Reproduction status:** *Analytical only.* The trigger was not exercised live because
the precondition requires building and loading a > 64k-pattern AC context whose u32
state table is multi-GB, which is outside the scope of this static-analysis audit.
However, every step in the chain is deterministic source-level arithmetic, and an
exhaustive search of the AC code path found no guard that caps `max_pat_id` at 16 bits
or otherwise prevents `pid ≥ 65536` from reaching L923.

## Severity

**LOW.**

The defect causes a deterministic detection bypass — and in edge cases a false-positive
cross-fire — for every case-sensitive fast-pattern whose internally assigned pattern-id
is ≥ 65536 while the AC matcher is in its u32-state mode. There is no crash and no
out-of-bounds read or write: the truncated index is always inside the `calloc`'d
`pid_pat_list` (sized `max_pat_id + 1`, L683), negative offsets are filtered at L927,
and the upper bound `offset + patlen == i + 1 ≤ buflen` holds for the `SCMemcmp`.

Exploitability is gated entirely by operator configuration: the deployment must (a)
explicitly select `mpm-algo: ac` (non-default when Hyperscan is available) **and** (b)
concentrate > 65536 unique fast-patterns into a single MPM context (e.g.
`sgh-mpm-context: single` with an extremely large ruleset). This combination is very
uncommon in production. The attacker contributes only a single packet containing a known
signature literal.

## Suggested Fix

Use the same mask that the construction code (L576–577) and the u16 search branch (L877)
already use. One-line patch:

```diff
--- a/src/util-mpm-ac.c
+++ b/src/util-mpm-ac.c
@@ -920,7 +920,7 @@ uint32_t SCACSearch(const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx,
                 const uint32_t *pids = ctx->output_table[state & 0x00FFFFFF].pids;
                 for (uint32_t k = 0; k < no_of_entries; k++) {
                     if (pids[k] & AC_CASE_MASK) {
-                        const uint32_t lower_pid = pids[k] & 0x0000FFFF;
+                        const uint32_t lower_pid = pids[k] & AC_PID_MASK;
                         const SCACPatternList *pat = &pid_pat_list[lower_pid];
                         const int offset = i - pat->patlen + 1;
```

Optionally, add a defensive assertion in `SCACPreparePatterns()` that
`mpm_ctx->max_pat_id < AC_CASE_MASK` to document the invariant that the PID never
collides with the case-flag bit.