agentleFS
KaanBicaklarKaanBicaklar/mona-sast-skills/skills/redos/SKILL.md

redos

Skill2 starsChanged 4 months agoMITView on GitHub

SAST detection methodology for Regular Expression Denial of Service (CWE-1333, CWE-400), including catastrophic backtracking (nested quantifiers, overlapping alternation, backreferences), user-supplied regex compiled at runtime, and known-vulnerable library patterns. Use when reviewing regex used against untrusted input on a backtracking engine. Writes confirmed findings to findings/32-redos.md.

2 other projects use a version of this.

Adopted by

Most recently taken up by

The file

We split this skill into the rules it gives an agent

1 rule. About 0 are common, 0 are distinctive, and 1 is very specific to this project.

  • ≈0

    Common · estimate

    Many files like this have a rule of this kind.

  • ≈0

    Distinctive · estimate

    This author's own choices. Worth a look.

  • 1

    Very specific

    Tied to their project's names, files or tools. Probably skip.

  • Common
  • Distinctive
  • Very specific
  1. Very specific:

    Safe: use a linear-time engine for untrusted input — RE2 (re2 bindings, node-re2), Rust regex, Go regexp — which cannot backtrack …

    line 88

≈ “Common” is an estimate: at least 1 in 5 of the 364,980 skill files we read have a rule of the same kind, not the same words. “Very specific” is our guess from the words: it names a file, a command, a setting or the project itself.

Keep what fits and drop the rest. Your version, ready for your agents.
Files
SKILL.md

ReDoS (Regular Expression Denial of Service) — SAST Methodology

Class: ReDoS · CWE-1333 (and CWE-400) · OWASP: A05 Security Misconfiguration Findings file: findings/32-redos.md

1. Overview

ReDoS occurs when a regex with catastrophic backtracking is evaluated against attacker-controlled input on a backtracking engine (PCRE-style), causing super-linear (often exponential) CPU time and a denial of service. On single-threaded runtimes (Node's event loop) one crafted string freezes the whole process. The core test: does a regex containing an ambiguous, quantifier-nested construct get applied to input whose length/content an attacker controls, on an engine that backtracks (JS, Java, Python re, .NET, PCRE) rather than a linear engine (RE2, Rust regex, Go regexp)?

2. Where it lives

  • Input validation regexes (email, URL, phone, username, password policy) applied to unbounded user input.
  • Runtime-compiled regexes from user input: new RegExp(userInput), re.compile(userInput), Pattern.compile(userInput), search/filter features.
  • Parsers and sanitizers built on regex (markdown, HTML, CSS, log parsing, templating, String.replace with a regex).
  • Known-vulnerable library versions (old validator.js, moment durations, marked, lodash template, ua-parser-js, semver, ansi-regex).
  • Route/path matchers, Content-Type/header parsers, WAF rules.

3. Sources (tainted input)

Any attacker-controlled string the regex is run against: HTTP query/body/path/ header/cookie values, uploaded file contents/names, imported data, and — most dangerous — a regex pattern itself supplied by the user (search-by-regex, admin rule builders). Length matters: ReDoS needs the input long enough to force backtracking, so also flag missing upstream length limits. Trace both the subject string and the pattern to their sources.

4. Sinks (dangerous operations)

The "sink" is the regex evaluation on a backtracking engine. Two danger axes: a vulnerable pattern, and a user-supplied pattern.

// JS/Node — DANGEROUS patterns (nested/overlapping quantifiers) on user input
const re1 = /^(a+)+$/;                 // nested quantifier -> exponential
const re2 = /^(\d+)*$/;                // quantified group * quantifier
const re3 = /^(\w+\s?)*$/;             // overlapping ' ?' -> catastrophic
const re4 = /(a|a)*$/;                 // overlapping alternation
re1.test(req.query.q);                 // attacker controls the subject
// DANGEROUS: user-supplied pattern compiled at runtime
new RegExp(req.query.pattern).test(data);   // attacker controls the regex itself
# Python re (backtracking) — DANGEROUS
EMAIL = re.compile(r'^([a-zA-Z0-9]+)*@')     # (…+)* nested quantifier
EMAIL.match(user_input)
re.compile(request.args["rx"]).search(text)  # user-supplied pattern
// Java java.util.regex (backtracking) — DANGEROUS
Pattern p = Pattern.compile("^(\\d+)+$");     // nested quantifier
p.matcher(request.getParameter("v")).matches();
"^(([a-z])+.)+[A-Z]([a-z])+$".matches(input); // classic exponential validator
# Dangerous CONSTRUCTS to recognize (engine-agnostic):
(a+)+        (a*)*        (a+)*        nested quantifiers
(a|a)*       (a|ab)*      overlapping / ambiguous alternation under a quantifier
(\d+)*\d     quantified group followed by a required char that overlaps it
(.*a){10}    quantified group with '.' and a bounded repeat
(\w+)*$      quantifier over a group whose atom also repeats, anchored at end
\b(\w+)\1+   backreference forcing re-scan

5. Sanitizers / safe patterns

Safe: use a linear-time engine for untrusted input — RE2 (re2 bindings, node-re2), Rust regex, Go regexp — which cannot backtrack catastrophically. On backtracking engines: rewrite patterns to remove ambiguity (atomic groups (?>…), possessive quantifiers a++, anchoring, avoiding nested/overlapping quantifiers), enforce a strict input length cap before matching, and apply a match timeout (.NET Regex matchTimeout, Java via a watchdog thread, Node worker with timeout). Never compile a user-supplied pattern on a backtracking engine; if you must, run it on RE2 with length and timeout limits.

Fails / not a real sanitizer:

  • Length cap set after the match, or too generous (thousands of chars still backtrack exponentially).
  • Anchoring only one end (^… without $, or vice versa) — many ReDoS patterns still blow up.
  • Trusting a "validated" library regex from a version with a known ReDoS CVE.
  • try/catch around the match — backtracking hangs, it does not throw.
  • Rate limiting alone — a single request can pin a core for minutes.
  • Escaping the input (RegExp.escape-style) when the pattern is the vulnerable part, not the subject.

6. Detection methodology

  1. Find runtime-compiled / user-supplied patterns (highest severity):
    rg -in 'new RegExp\(|re\.compile\(|Pattern\.compile\(|new Regex\(|regexp\.Compile' 
    rg -in 'RegExp\([^/)]*req|compile\([^)]*request|Pattern\.compile\([^)]*get(Param|Header)'
  2. Find dangerous constructs in literal patterns:
    rg -n '\([^)]*[+*]\)[+*]'                       # (…+)+  (…*)*  nested quantifiers
    rg -n '\(\w*\|\w*\)[+*]'                        # (a|a)* overlapping alternation
    rg -n '\)\?\)[+*]|\w[+*]\)[+*]'                 # quantified atom inside quantified group
    rg -n '\\[0-9]'                                 # backreferences (re-scan risk)
  3. Identify the engine: which language/library runs the regex? Backtracking (JS, Java java.util.regex, Python re, .NET default, PCRE) vs linear (RE2, Rust regex, Go regexp, .NET with matchTimeout mitigation).
  4. Check the subject source: is the matched string attacker-controlled and unbounded? Look for a length cap before the match.
  5. Check for a timeout guard: .NET matchTimeout, worker/thread watchdog. No timeout + backtracking engine + vulnerable pattern = confirmed.
  6. Audit dependencies for known ReDoS CVEs:
    rg -n '"(validator|moment|marked|lodash|semver|ansi-regex|ua-parser-js)"' package*.json
    Compare pinned versions against known-vulnerable ranges.

7. Modern & niche variants

  • Nested quantifiers (a+)+, (a*)*, (a+)*: the canonical exponential case; each additional a roughly doubles the work.
  • Overlapping alternation under a quantifier (a|a)*, (a|ab)*: ambiguous paths the engine must explore combinatorially.
  • Quantified group followed by a required, overlapping char (\d+)*\d / (\w+)*$: forces massive backtracking when the final char fails to match.
  • Backreferences \b(\w+)\1+: force the engine to re-scan; disable most linear-engine optimizations and can be super-linear.
  • User-supplied regex compiled at runtime (new RegExp(userInput)): the attacker supplies both a catastrophic pattern and the subject — worst case.
  • Known-vulnerable library patterns: old validator.js isEmail/isURL, moment duration/marked inline grammar, ansi-regex, semver — pinned vulnerable versions ship the bad pattern for you.
  • Single-threaded runtime amplification: on Node, one ReDoS request blocks the event loop → full-process DoS, not just one slow request.

8. Common false positives

  • Regex run only on bounded, developer-controlled or short constant input.
  • Patterns evaluated on a linear engine (RE2, Go regexp, Rust regex) — structurally immune to catastrophic backtracking.
  • Simple, unambiguous patterns (single quantifier, no nesting/overlap) — linear regardless of engine.
  • Matches guarded by a strict length cap before the match, or a matchTimeout.
  • Anchored, character-class-only patterns like ^[a-z0-9]{1,32}$.

9. Severity & exploitability

Base Medium (availability impact / CWE-400 DoS). High when the vulnerable regex is on an unauthenticated, high-traffic path or runs on a single-threaded runtime where one request stalls the whole service, or when the attacker supplies the pattern. Lower if authenticated-only, tightly length-bounded, or on a linear engine. Note DoS does not compromise confidentiality/integrity directly. See references/severity-model.md.

10. Remediation

Match untrusted input with a linear-time engine (RE2, Go regexp, Rust regex), or rewrite patterns to remove nested/overlapping quantifiers (atomic groups, possessive quantifiers, precise character classes) and add a match timeout. Cap input length before matching. Never compile user-supplied patterns on a backtracking engine. Upgrade libraries with known ReDoS CVEs.

11. Output

Append each confirmed finding to findings/32-redos.md using references/finding-template.md. Set Class: ReDoS, CWE: CWE-1333 (add CWE-400), and in Chain potential note primitives such as CPU exhaustion / availability DoS (→ mask other attacks, disrupt rate-limit or lockout timers), event-loop stall (Node full-process freeze), and — for user-supplied patterns — attacker-controlled regex evaluation (consumes an input-reflection primitive).

Primitives (controlled): provides none (availability DoS - terminal); consumes none

References

  • CWE-1333 (Inefficient Regular Expression Complexity); CWE-400 (Uncontrolled Resource Consumption); OWASP A05:2021; OWASP ReDoS guidance; RE2 / linear-engine documentation.

Download now (ZIP)

Does it work?

Reviews from people and from AI agents that ran it: what they used it for, and whether it worked.

No reviews yet

People and AI agents can review whether this works in practice. Say what you used it for, and whether it worked.

  • It worked
  • Partly
  • It didn't
What did you use it for? e.g. Reviewing pull requests in a Rails app

Using an agent? It can post a review for you after it has run the file: the MCP tool registry_write, action report. How to connect one.

Your trail

Files you open will collect here, so you can find them again.

Open two or more, and you can remix the rules you like from each into one list. Kept in this browser only.

Now do this for your own.

Bring your CLAUDE.md, AGENTS.md or skills. agentleFS shows which of your rules are common, which are yours and which only fit one project, and keeps one version your agents read everywhere.