# zeek-0001: CWE-407 — O(n²) rule deduplication in per-packet signature matching

**Severity:** HIGH
**File:** `src/RuleMatcher.cc:51`, called at lines 875, 917, 952, 961, 975, 994
**Status:** PATCHED

## Description

`is_member_of()` performs a linear `std::ranges::find` over `matched_rules` (an
`int_list` = `std::vector<std::intptr_t>`) to check whether a rule has already fired.
It is called **6 times per packet per connection** inside the per-packet signature
matching engine (`Match()`, `ExecPureRules()`, `ExecRulePurely()`, `EvalRuleConditions()`,
`ExecRuleActions()`, `ExecRule()`).

As rules fire across a connection's lifetime, `matched_rules` grows. For a deployment
with R active signature rules, each check is O(R). With 6 calls per packet and P packets
per connection:

  Cost per connection = O(P × R²)

For monitored high-throughput links with large rulesets (enterprise IDS may load
hundreds to thousands of signatures), this is quadratic in both packets and rule count.

## Root Cause

```cpp
// RuleMatcher.cc:51
static bool is_member_of(const int_list& l, int_list::value_type v) {
    return std::ranges::find(l, v) != l.end();  // O(R) linear scan every call
}

// RuleMatcher.h:219
int_list matched_rules;  // std::vector<std::intptr_t> — grows as rules match
```

Called at:
- `RuleMatcher.cc:875`  — skip rule already fired (inside hdr_test loop per packet)
- `RuleMatcher.cc:917`  — ExecRulePurely: skip already-matched
- `RuleMatcher.cc:952`  — EvalRuleConditions: check precondition rule
- `RuleMatcher.cc:961`  — EvalRuleConditions: check negated precondition
- `RuleMatcher.cc:975`  — ExecRuleActions: check opposite direction
- `RuleMatcher.cc:994`  — ExecRule: early exit if already matched

## Fix

Replace `int_list matched_rules` with `std::unordered_set<std::intptr_t>` in
`RuleEndpointState`. Membership check becomes O(1). Insert (in `ExecRuleActions`)
also becomes O(1) amortized.

If order must be preserved for iteration elsewhere, use an auxiliary set alongside
the existing vector. But the `matched_rules` field is only ever checked for membership
(never iterated), so the set is a pure replacement.

## Patch

See `patch/zeek-0001.patch`

## Benchmark

See `unit/ZeekRuleMatcherTest.java` — R=500 rules, P=1000 packets:
- Slow (vector): O(R²×P) = ~250M ops
- Fast (hash set): O(R×P) = ~500K ops
- Speedup: ~500×
