Beagle SCM

DOG-015 MED: IGNOGlob catastrophic backtracking — ReDoS from an untrusted .gitignore

dog/git/IGNO.c's IGNOGlob (IGNO.c:24-66) recurses on EVERY */** suffix with no memoization and no step budget: for(;;){ if(IGNOGlob(pat,tail)) return YES; if(empty) break; used1(tail); } (:36-40, :46-51). A single crafted pattern like *a*a*a*…*a*b matched against a long non-matching path is exponential-time, and ** nesting compounds it. .gitignore files come from cloned/untrusted repositories, and every worktree scan (be status, diff, post) routes through IGNOMatch per chain-file × per pattern (≤256) × per path prefix — so a hostile repo shipping a crafted .gitignore hangs the process. Method: Issues.

Input

Context

• IGNO.c:24-66 recursive matcher; pattern length bounded only by the mmap'd

  file, so ~40 wildcards effectively hangs.

• Untrusted source: .gitignore from a clone; IGNOMatch fans it across chain

  files, ≤256 patterns, and path prefixes.

Goals

• Linear-time star matching (single backtrack pointer, the standard `git

  wildmatch` technique) OR a hard recursion/step budget that fails closed.

• Match semantics unchanged for the well-formed patterns the tests cover.

Constraints

• dog/git libdog, ABC style; behaviour-preserving on the existing IGNO tests.
• The pointer-poke rewrite of the SAME matcher is tracked under PTR-002; do the

  algorithm fix and the slice cleanup together to avoid touching it twice.

WIP

TODOs

• T1 repro: property/fuzz case timing *a*…*b against a long non-match; assert

  it completes under a step budget (dog/fuzz has no IGNO target today).

• T2 replace recursion with the iterative wildmatch (or add a step budget).
• T3 fold in the PTR-002 slice cleanup of the same function.

Blockers and bummers

• Audit 2026-07-07: re-verified in libdog HEAD 79612854 — unbudgeted recursion still at IGNO.c:24-51. NOTHING landed; a budgeted igno_glob (IGNO_GLOB_BUDGET 200000, fail-closed) IS implemented in worktree ~/src/DOG-015 (git/IGNO.c), UNLANDED.

Outcome

• OPEN — filed 2026-07-06, the libdog code-quality review session.