Beagle SCM

JS-066: .gitignore glob is catastrophically backtrackable (ReDoS)

shared/util/ignore.js's glob() (the IGNOGlob port behind be status/ls wt-scan) implements */** by recursing on EVERY suffix with no memoization, so a pattern like *a*a*a*a*az against a long non-matching path is exponential. .gitignore is untrusted — a checkout writes attacker-controlled content and load() walks UP to $HOME stacking every .gitignore — and match() runs once per worktree entry, so a hostile repo wedges the single-threaded runtime. Method: Issues.

Input

Context

• shared/util/ignore.js:39 glob(pat,str) is the matcher.
• :51-53 ** branch: for (t=si..len) glob(subPat, str.slice(t)) — recurse on every suffix, NO memo on (pi,si), NO iteration cap.
• :56-62 * branch: same per-suffix recursion (stops past a /); two * segments in one pattern multiply → exponential on a non-match.
• :52 :59 each step allocates fresh pat.slice/str.slice substrings, amplifying the constant factor on top of the exponential blowup.
• :104 :109 :113 tryMatch calls glob per pattern; :113 retries at every dir level for unanchored-with-slash, multiplying the call count.
• Untrusted input: load() :176 reads .gitignore per dir; :168-184 walks anchor→$HOME// stacking up to 64 files; match() :190-204 runs setDecideDeep→glob per scanned wt entry → one hostile pattern + one long path hangs be status/ls (cited GET).

Goals

• glob() runs in time linear (or near-linear) in pat.length+str.length for ALL patterns, including adversarial *a*a*…*az vs a long non-match.
• A repro test that today hangs (or exceeds a wall-clock budget) and after the fix returns no-match promptly, with identical match/no-match verdicts to native IGNOGlob on the existing parity corpus.

Constraints

• Pure JS over io.stat/io.mmap/io.getenv; no C, no dog. Byte-equivalent verdicts to dog/git/IGNO.c (IGNOGlob/TryMatch) on the parity suite.
• Keep *=non-/, **=across-/, ?=one-char semantics exactly; do not regress the dir/-prefix or negation rules. Scope: glob() (+ tiny helpers).

WIP

Design decisions

• SUPERSEDED (review feedback): a hand-rolled matcher (two-pointer / DP) is STILL "manual parsing" — abc.mkd forbids it; the JS analogue of the ragel rule is to TRANSLATE the glob to a RegExp and let the engine match. Landed: compile pat→ONE cached RegExp (*→[^/]*, **→.* swallowing one /, ?→[^/], else escaped literal; no [...] classes — the C glob has none).
• A str.length ** star-runs work budget skips a degenerate multi-* glob → no-match (fail-safe), since JS RegExp BACKTRACKS (it is not a ragel DFA).
• (original plan, replaced) a linear two-pointer matcher.

TODOs

• REGRESSED/never landed: re-do glob()→cached-RegExp + work budget in the CURRENT shared/util/ignore.js (:39-70 is the recursive per-suffix matcher again).
• Re-add the repro test/ignore.js (*a*a*…*az bomb <2s + native-parity corpus).

Blockers and bummers

• 2026-07-07 audit: the 2026-06-25 working-tree fix is NOT in the be/ shard — glob() (ignore.js:39) recurses on every suffix for */** (:52,:59), no memo, no budget, per-step pat.slice/str.slice; no test/ignore.js exists. Presumably lost in the beagle-ext catch-up/JSQUE-016 reorg (027beac9+); still exploitable.
• 2026-07-10 revision: still OPEN — glob() shared/util/ignore.js:39-73 still recurses per-suffix (:52 *, :59 ), no RegExp-translate, no memo/budget; no test/ignore.js; no landed fix in be log

Outcome

• (pending — the earlier "implemented in the working tree" claim did not survive into the be/ tree; see the 2026-07-07 audit note above. Design stands: RegExp translate, NOT a hand-rolled DP matcher — abc.mkd forbids manual parsing.)