safe-bash sed/awk NFA: capture-state explosion — Pattern.find never yields and under-accounts state memory ~12× (143-byte script: 2–3 s uninterruptible, 500 MB RSS, exit 2)

[kamilio]

Where: packages/safe-bash/src/commands/text-programs/regex.ts — Pattern.find (~lines 198-241). The match loop is fully synchronous: budget.step() only calls signal.throwIfAborted(), and the time-based yield in Budget.checkpoint (text-programs/shared.ts:38) is never reached from inside find. The state budget is an estimate, not a measurement: queued threads are priced at 32 + groupCount * 16 bytes and visited states at state.length * 2 + 32, while each thread retains a freshly copied captures array and each visited state is a joined string held in a per-position Set.

PoC (143 bytes, default limits, createAgentCommands()):

printf 'a%.0s' $(seq 1 8000) > /work/a
sed -E 's/(a*)(a*)(a*)(a*)(a*)(a*)(a*)(a*)(a*)(a*)(a*)(a*)(a*)(a*)(a*)(a*)(a*)(a*)(a*)(a*)b/X/' /work/a

Measured (three consecutive runs of the same script):

run	ms	peak heap MB	RSS MB	event-loop ticks seen	expected (10 ms)
0	2198	78	268	10	220
1	3311	192	278	10	331
2	2913	155	378	10	291

Exit 2, stderr sed: regular expression state buffer limit exceeded. Peak heap reached 412 MB / RSS 517 MB in an earlier sweep of the same shape. The command's maxBufferBytes is 32 MiB, so live memory runs ~12× the accounted cap. Independent re-run on a second machine: 1019 ms, 8 of 102 ticks, RSS 272 MB.

Related:

• Abort delivery is late. A host AbortSignal.timeout(500) returned at 2033 ms (second machine: returned exit 2 at 1019 ms, abort never observed).
• Same shape reaches awk: awk '/(a*)…(a*)b/{print "m"}' on 4000 a → 2901 ms, +73 MB.
• Fewer groups buy more time: 5 groups on a 2000-char line → 6656 ms; 2 groups → 3619 ms, terminated on the 5 000 000-step limit instead (≈0.7 µs native work per "step").
• Budget is per invocation, so it's loopable: three sequential seds → 23 088 ms; ShellLimitError: maxCpuMs fired at 31 033 ms against a 30 000 ms deadline.
• xargs -P 4 multiplies it: peak heap 161 MB (-P 1) → 287 MB (-P 2); RSS 269 → 454 MB (-P 4).

Impact: (d) — a 143-byte script starves the event loop for 1–3 s per invocation (aborts and the wall-clock timer cannot fire during the stretch) and drives several hundred MB of RSS while accounting believes it is inside 32 MiB. Under --max-old-space-size=128 it survived (198–216 MB RSS), so not a fatal OOM, but it is CPU and memory theft against co-resident work, and the same class as the closed abort-starvation finding (#595) in a different engine.

Fix: call the time-based budget.checkpoint() from inside the find position loop so aborts and yields engage; charge real allocation (retained captures copies + per-state Set overhead) rather than the 32 + groups*16 estimate, or cap capture-group count × thread count.

Found in security audit v3 (2026-09-07).

[kamilio]

Validated, fixed, and verified on remote main at 9b791fa. Pattern.find now suspends within matching work and pre-admits jointly retained NFA storage; all seven production callers, including nl, await it. Captures, backreferences, byte handling, and cancellation identity are covered. Initial focused RED: 11 failures; final NFA/stream-format cohort: 440/440 passes. Full package sweep exercised 22,120 tests with 22,055 passes and 63 explicit skips; its only two failures were older synchronous jq test callers, migrated without changing assertions and rerun in a 102/102 passing cohort. No uninterrupted clean rerun is claimed for that sweep. Selected maintained build, final root lint, 166 browser-engine tests, site build, and inspected actual-browser command output pass. No unmeasured heap/RSS ratio is claimed. Release monitoring continues separately.

[kamilio]

Release verified: commit 9b791fa is on main, and scoped release run 34196772474 succeeded. @poe-platform/safe-bash@0.1.435 published September 8, 2026 at 06:58:12 UTC. Pages run 34196772505 also succeeded. This confirms scoped publication, not completion of the separate root poe-code release.