# wasmer-0001: Ruleset Vec<Rule> O(n) linear scan on every network operation

**Severity:** HIGH
**CWE:** CWE-407 (Algorithmic Complexity — linear membership test in hot loop)
**Speedup:** >10x at N=100 rules (each socket op costs 2 full scans)
**Target:** wasmer (wasmerio/wasmer)
**Files:**
- `lib/virtual-net/src/ruleset.rs:670` — `rules: Arc<RwLock<Vec<Rule>>>`
- `lib/virtual-net/src/ruleset.rs:682` — `ruleset.iter().any(|r| r.blocks_socket(addr, dir))`
- `lib/virtual-net/src/ruleset.rs:687` — `ruleset.iter().any(|r| r.allows_socket(addr, dir))`
- `lib/virtual-net/src/ruleset.rs:698` — `ruleset.iter().any(|r| r.blocks_domain(domain))`
- `lib/virtual-net/src/ruleset.rs:703` — `ruleset.iter().any(|r| r.allows_domain(domain))`

## Description

`Ruleset` stores network firewall rules in a `Vec<Rule>`. Every call to
`allows_socket()` or `allows_domain()` performs **two** full linear scans
through all rules: one to check for a blocking rule, one to check for an
allowing rule.

These methods are called on every network operation:
- `listen_tcp` / `bind_udp` — `host.rs:80,113`
- `connect_tcp` — `host.rs:172`
- `resolve` — `host.rs:203`
- `try_accept` — `host.rs:250`
- `try_send_to` (UDP) — `host.rs:867`

With N rules and M socket operations: **O(N * M)** total work.

A WebAssembly server handling high-throughput networking (e.g. a WCGI handler
serving many requests, each making outbound connections) will degrade linearly
as rules accumulate.

## Root Cause

Rules are heterogeneous (`IPV4`, `IPV6`, `DNS`, `Neg`) making exact-match
hashing non-trivial, but they can be **partitioned by type at insert time**
into separate vectors. For socket checks only `IPV4`, `IPV6`, and `Neg` rules
are relevant; DNS rules can be skipped entirely. For domain checks only `DNS`
and `Neg(DNS)` rules matter. This cuts the scan size by the proportion of
irrelevant rule types.

The deeper fix: build two pre-indexed structures at rule-add time:
1. An IP trie / prefix-indexed map for `IPV4`/`IPV6` rules — O(prefix_len) lookup
2. A `HashMap<domain, PortSpec>` for DNS rules — O(1) lookup

## Patch

See `patch/wasmer-0001.patch`

## Complexity Before

`allows_socket()` with N rules: **O(N)** per call (two passes)
M calls: **O(N * M)**

## Complexity After (partition fix)

`allows_socket()` with N_ip IP rules and N_dns DNS rules (N = N_ip + N_dns):
**O(N_ip)** per call — DNS rules never visited
M calls: **O(N_ip * M)** — bounded by IP rule count only

With trie/HashMap fix: **O(1)** amortized per call.

## Reproduction

```
cd defects/wasmer/unit && javac -d . *.java && java -ea unit.RulesetLinearScanTest
```
