Skip to content

spec_exposure's unbounded [^\]]* ReDoS is copy-pasted across 28 languages, including already-merged yacc #713

Description

@squid-protocol

Summary

Found while closing #584 (groovy strict-parsing tests). The spec_exposure signature's regex pattern -- \[(?:\s*SPEC\s*-\s*\d+|spec|audit)[^\]]*\] (or close variants) -- is copy-pasted nearly identically across the majority of LANGUAGE_DEFINITIONS entries, and the vast majority of copies still carry the unbounded [^\]]* that causes real, confirmed O(n^2) catastrophic backtracking on an unclosed tag (\d+ and the trailing [^\]]* both greedily match digits with no closing ] ever present, so the engine backtracks by re-scanning an ever-shrinking suffix).

This exact bug class was already found and fixed twice in this epic -- for shell and sqlite -- but never swept systemically across the rest of the registry.

Confirmed severity

Directly measured ReDoS scaling (not just pattern-shape suspicion) on 3 sample languages:

python: n=2000 0.0019s -> n=4000 0.0075s -> n=8000 0.0286s -> n=16000 0.1154s
yacc:   n=2000 0.0018s -> n=4000 0.0072s -> n=8000 0.0286s -> n=16000 0.1141s
go:     n=2000 0.0020s -> n=4000 0.0073s -> n=8000 0.0289s -> n=16000 0.1142s

Consistent ~4x slowdown per input-size doubling -- genuine quadratic scaling, not linear. This is a real DoS vector: GitGalaxy's entire purpose is scanning untrusted/third-party repositories, and a single crafted or accidentally-malformed file (an unclosed [SPEC- tag followed by a long run of digits) in any of the affected languages could hang a scan.

Affected languages (confirmed via direct pattern inspection of LANGUAGE_DEFINITIONS, not guessed)

28 languages still carry the unbounded, vulnerable form: python, javascript, typescript, java, csharp, go, rust, cpp, c, php, ruby, swift, kotlin, html, css, assembly, perl, embedded_python, dart, dockerfile, matlab, solidity, objective-c, yacc, m4, scheme, tcl, groovy (groovy fixed as part of #584/#712).

Already correctly bounded (fixed in this epic): shell, sqlite.

No vulnerable bracket class at all (not affected): powershell, fortran, agc_assembly, lua, haskell, cobol, zig, apex, scala, livecode, makefile, abap.

yacc is notable: its own strict-parsing issue (#616) is already closed and merged (#700), because that closure's ReDoS test used a letter-only adversarial payload that doesn't trigger the digit/[^\]]* overlap -- a reminder that ReDoS payloads should be varied (digits vs letters vs symbols), not just sized, when probing a given quantifier.

The fix

Mechanical and low-risk -- the exact same change already proven correct twice in this file: bound [^\]]* to [^\]]{0,300} (generous enough for any realistic spec/audit tag, matching the cap already used for shell/sqlite). No behavior change for any realistic input, only removes the pathological-input hang.

Scope

  1. Apply the {0,300} bound to all 27 remaining vulnerable languages (groovy already done).
  2. Re-verify golden crucible in both venvs -- expect zero or near-zero diff (the bound only affects pathologically long unclosed tags, not realistic content), but confirm rather than assume per the doc's own "zero-diff isn't automatically clean" rule.
  3. Add a ReDoS regression test per affected language's existing strict-parsing test section where one exists, or a single dedicated cross-language test if that's cleaner, verified via multi-point scaling (2k/4k/8k/16k/32k) with a digit-heavy payload specifically (not just letters), given the yacc miss above.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugUnintended behavior or logic failure in the enginecore-engineModifications to the central physics and parsing engine

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions