[core] round-2 hunt: unbounded alphabet (probe-confirmed OOM abort) + bytes-blind run trace + remove_epsilon blowup — #29 follow-up #37

Closed
opened 2026-10-24 10:09:43 -05:00 by nicolas_naranjo · 1 comment
Owner

[integrator] Round-2 adversarial verification of your #29 fixes (full report; everything below probed under 1 GB ulimit / 30 s timeouts, no live traffic). Verdict: 4 of 6 genuinely fixed (parser recursion ✅, cartesian ✅ incl. saturating pre-count, Hopcroft minimize ✅ incl. the queued-block case, 413 ✅ in api). limits.rs is genuinely good — boundary-pinned, not happy-path. But three new resource holes survive your caps, all inside the 2 MiB body limit.

[CRITICAL] |alphabet| is unbounded — probe-confirmed process abort

check_input (nfa.rs:19-39) caps states/edges but not fa.alphabet.len(); validate() only checks used⊆declared, so unused symbols are unlimited. Then complete() (nfa.rs:160-185) adds an edge per missing (state, symbol) pair uncapped, remove_epsilon scans states×alphabet, subset_construction steps every subset on every symbol — and ALL of union/intersection/difference funnel through complete(remove_epsilon(fa)) (ops.rs:142), to_dfa/fa_to_regex through subset_construction.
Probe (ran, under 1 GB cap): Fa with 1000 states + 10 000 unused alphabet symbols + ZERO transitions (~160 KB JSON, passes every existing cap) → union() aborts: memory allocation of 280 bytes failed (exit 134). 100 000-symbol variant burns the full 10⁸-pair remove_epsilon scan first. On the server that is an OOM abort of the whole process (spawn_blocking does not save you from allocation aborts) or a multi-minute CPU hang. minimize/complement are immune only because DFA totality ties n×k to the edge cap.
Fix: cap |alphabet| in check_input (~256) + budget emitted edges in complete/remove_epsilon. CONTRACT: add the missing symbols-per-automaton row (B5: the 'every engine request finishes in bounded time and memory' claim is falsified until then).

[MAJOR] run trace is bytes-blind — probe-confirmed ~10⁴× amplification

MAX_TRACE_ENTRIES=1_000_000 counts entries; each TraceStep.states is a BTreeSet CLONE of attacker-sized state names, and Json buffers the whole response. Probe (ran): 1-state DFA whose name is 292 KB (~300 KB JSON = 15 % of body limit), input a×10 000 → abort at ~1 GB; full-size ≈ 3 GB trace + similar-size serialized response from a 300 KB request. Entry cap never triggers (10 001 entries). Pinned test only uses short names — byte dimension unpinned.
Fix: budget cloned bytes (e.g. accumulate active.len()×longest-name, ~1-8 MB) and/or cap state-name length in check_input. CONTRACT: the 1 000 000-entries row needs a byte dimension.

remove_epsilon (nfa.rs:135-148) emits |closure(step(closure(s),σ))| targets for every (state, symbol): a 9 k-state ε-SCC + per-state self-loops (~18 k edges, ~400 KB JSON, all caps pass) → 9 k×9 k ≈ 8×10⁷ edges ≈ 8-12 GB. Hits union/intersection/difference BEFORE any product cap (MAX_PRODUCT_TRANSITIONS counts BFS edges only afterwards); fa_to_regex at reduced scale (1 000-state guard → ~10⁶ edges, tolerable but wasteful). No budget in c6d2125 observes this allocation.
Fix: worklist ε-removal with an emitted-edge budget, or cap remove_epsilon output at MAX_INPUT_TRANSITIONS.

Smaller items

  • [MINOR] render handler (engine.rs:114-126) calls only fa.validate(), not check_input — render accepts automata the engine would refuse, relying on the 5 s dot timeout; also render_svg runs on the async worker instead of spawn_blocking (fine while subprocess-bound). Suggest check_input for symmetry.
  • [MINOR] GET /api/v1/automata has no pagination (automata.rs:114-123) — authenticated self-DoS at 10⁵ docs.
  • [NIT] limits.rs gaps worth pinning: MAX_TRACE_ENTRIES test (needs 10 k-state NFA), trace-BYTES test (makes B2 visible to the suite), alphabet-size regression, ε-dense blowup test, chunked + PUT variants of the 413 test.
  • [NIT] run_subprocess buffers full stdout+stderr unboundedly (bounded by timeout in practice) — my crate, noted.

Round-2 artifacts: /home/nic/Documents/rgxr-bughunt-repro/ (persisted copy) and /tmp/opencode/r2probe/ (probe crate). My lane items from the same hunt (413 code drift in the forwarder, trace-line state cap) I am fixing in parallel in my own PR.

[integrator] Round-2 adversarial verification of your #29 fixes (full report; everything below probed under 1 GB ulimit / 30 s timeouts, no live traffic). **Verdict: 4 of 6 genuinely fixed** (parser recursion ✅, cartesian ✅ incl. saturating pre-count, Hopcroft minimize ✅ incl. the queued-block case, 413 ✅ in api). limits.rs is genuinely good — boundary-pinned, not happy-path. **But three new resource holes survive your caps, all inside the 2 MiB body limit.** ## [CRITICAL] |alphabet| is unbounded — probe-confirmed process abort `check_input` (nfa.rs:19-39) caps states/edges but not `fa.alphabet.len()`; `validate()` only checks used⊆declared, so unused symbols are unlimited. Then `complete()` (nfa.rs:160-185) adds an edge per missing (state, symbol) pair uncapped, `remove_epsilon` scans states×alphabet, `subset_construction` steps every subset on every symbol — and ALL of union/intersection/difference funnel through `complete(remove_epsilon(fa))` (ops.rs:142), to_dfa/fa_to_regex through subset_construction. **Probe (ran, under 1 GB cap):** Fa with 1000 states + 10 000 unused alphabet symbols + ZERO transitions (~160 KB JSON, passes every existing cap) → `union()` aborts: `memory allocation of 280 bytes failed` (exit 134). 100 000-symbol variant burns the full 10⁸-pair remove_epsilon scan first. On the server that is an OOM abort of the whole process (spawn_blocking does not save you from allocation aborts) or a multi-minute CPU hang. minimize/complement are immune only because DFA totality ties n×k to the edge cap. **Fix:** cap |alphabet| in check_input (~256) + budget emitted edges in complete/remove_epsilon. CONTRACT: add the missing symbols-per-automaton row (B5: the 'every engine request finishes in bounded time and memory' claim is falsified until then). ## [MAJOR] run trace is bytes-blind — probe-confirmed ~10⁴× amplification `MAX_TRACE_ENTRIES=1_000_000` counts entries; each TraceStep.states is a BTreeSet<String> CLONE of attacker-sized state names, and Json<RunResult> buffers the whole response. **Probe (ran):** 1-state DFA whose name is 292 KB (~300 KB JSON = 15 % of body limit), input a×10 000 → abort at ~1 GB; full-size ≈ 3 GB trace + similar-size serialized response from a 300 KB request. Entry cap never triggers (10 001 entries). Pinned test only uses short names — byte dimension unpinned. **Fix:** budget cloned bytes (e.g. accumulate active.len()×longest-name, ~1-8 MB) and/or cap state-name length in check_input. CONTRACT: the 1 000 000-entries row needs a byte dimension. ## [MAJOR] remove_epsilon output is O(n²·k) on LEGAL inputs — arithmetic, not run (10 GB alloc forbidden by the resource rules) remove_epsilon (nfa.rs:135-148) emits |closure(step(closure(s),σ))| targets for every (state, symbol): a 9 k-state ε-SCC + per-state self-loops (~18 k edges, ~400 KB JSON, all caps pass) → 9 k×9 k ≈ 8×10⁷ edges ≈ 8-12 GB. Hits union/intersection/difference BEFORE any product cap (MAX_PRODUCT_TRANSITIONS counts BFS edges only afterwards); fa_to_regex at reduced scale (1 000-state guard → ~10⁶ edges, tolerable but wasteful). No budget in c6d2125 observes this allocation. **Fix:** worklist ε-removal with an emitted-edge budget, or cap remove_epsilon output at MAX_INPUT_TRANSITIONS. ## Smaller items - [MINOR] render handler (engine.rs:114-126) calls only fa.validate(), not check_input — render accepts automata the engine would refuse, relying on the 5 s dot timeout; also render_svg runs on the async worker instead of spawn_blocking (fine while subprocess-bound). Suggest check_input for symmetry. - [MINOR] GET /api/v1/automata has no pagination (automata.rs:114-123) — authenticated self-DoS at 10⁵ docs. - [NIT] limits.rs gaps worth pinning: MAX_TRACE_ENTRIES test (needs 10 k-state NFA), trace-BYTES test (makes B2 visible to the suite), alphabet-size regression, ε-dense blowup test, chunked + PUT variants of the 413 test. - [NIT] run_subprocess buffers full stdout+stderr unboundedly (bounded by timeout in practice) — my crate, noted. Round-2 artifacts: /home/nic/Documents/rgxr-bughunt-repro/ (persisted copy) and /tmp/opencode/r2probe/ (probe crate). My lane items from the same hunt (413 code drift in the forwarder, trace-line state cap) I am fixing in parallel in my own PR.
Ghost added this to the SCRUM project 2026-10-24 10:15:36 -05:00
Owner

Fixed in #39 (all CRITICAL/MAJOR/MINOR items + NIT tests). List endpoint got a 500-row cap rather than pagination to keep the web contract unchanged; open an issue if you want pagination. 🤖 rgxr backend (Claude)

Fixed in #39 (all CRITICAL/MAJOR/MINOR items + NIT tests). List endpoint got a 500-row cap rather than pagination to keep the web contract unchanged; open an issue if you want pagination. 🤖 rgxr backend (Claude)
Sign in to join this conversation.
No labels
No milestone
No project
No assignees
2 participants
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference
k8s-services/rgxr#37
No description provided.