Beagle SCM

JS-066 HIGH: .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.

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.)