Skip to content

safe-bash: ${x#*pat}/${x%pat*}/${x//*pat/} are O(n²) with a 64 M-unit ledger — 3 KB value = 10 s, 5 KB value burns the full 30 s CPU budget #666

Closed

Description

@kamilio

Where: packages/safe-bash/src/shell/runtime.ts ~:4583-4620 — parameterPattern tries every prefix/suffix length and calls matchTokens (src/shell/pattern.ts:80+) per candidate; for a *-containing pattern each attempt is itself linear, so the removal is O(n²) at 2 µs/step. The work ledger is sized limit*4+1024 = 64 M units (:4586), far more than 30 s can process, so maxCpuMs/maxWallClockMs is the binding limit. Interruptible (abort honored at the deadline).

PoC (~60 bytes, default limits):

x=$(printf "%05000d" 0); echo ${x#*1} | wc -c

Variants: ${x##*1}, ${x%1*}, ${x/#*1/}, ${x//*1/}.

Measured: 1 KB → 691 ms; 3 KB → 9 958 ms (${x##*1} 7 026 ms, ${x/%*1/} 10 808 ms; re-verified independently: 9 887 ms); 5 KB → maxWallClockMs at 30 003 ms; 10 KB … 1 MB → maxCpuMs/maxWallClockMs at ~30 s, result never produced. Control: case $x in *1) on the same 3 KB value → 3–18 ms.

Impact: (d) — a 60-byte script pins the thread for the full wall clock per exec, loopable across execs. Same class as closed #623/#634 (under-priced work ledger), different mechanism.

Fix: for *-anchored removals compute the match once (single backtracking scan with an end-position search for longest/shortest) instead of trying every split; or charge length per candidate against a ledger sized to real CPU (≈1–2 M units), not 4 × maxExpansionBytes.

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

Activity

  1. kamilio commented on Sep 8, 2026

    @kamilio
    MemberAuthor

    Validated and fixed on main at 8a1f223. Parameter-pattern operations now compute reusable match boundaries instead of rescanning candidate substrings; global replacement reuses the same table. Bounded witnesses changed global no-match reads from 291/1799/12559 to 23/47/95 at input sizes 8/16/32. Work and table memory are admitted through existing budgets; shortest/longest, anchoring, Unicode and cancellation controls pass. Delivery: maintained build, 282 runner checks, complete package suite with 22,153 passes and 63 skips, guarded root lint, and 166 playground tests. Built-public 8 KiB case matches Bash; browser 2 KiB case succeeds, while its tighter 64 KiB profile refuses 8 KiB without raising limits. Evidence: docs/plans/bugfix-666-pattern-boundaries.md. Remote main verified; release monitored separately.

  2. kamilio commented on Sep 8, 2026

    @kamilio
    MemberAuthor

    Scoped release verified: run 34200967739 succeeded for exact delivered main commit 8a1f223. This verifies scoped package publication; the separate root poe-code release remains independently monitored.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions