Skip to content

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

Closed

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.

Activity

  1. added
    bugUnintended behavior or logic failure in the engine
    core-engineModifications to the central physics and parsing engine
    on Jul 28, 2026
  2. added a commit that references this issue on Jul 30, 2026
    62803bc
  3. added this to the v2.4.6 milestone on Aug 1, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

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

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions