# ReDoS / catastrophic-regex pre-scan (ARION service)

Deterministic scanner for the regex-denial-of-service family across
Python, JS/TS, PHP, Ruby, Java/Kotlin, C#, Go and Rust sources: (1)
**nested quantifiers with an ambiguous iteration boundary** —
`(a+)+`, `(\w+)+`, `([a-z]+\s*)+` — the exponential-blowup shape,
detected by checking whether the inner repeat's character class can
also start the next iteration or overlap the following atom — so the
forced-boundary shapes that look identical but are linear-time —
`(?:-[a-z0-9]+)*` slug patterns, `(?:\d+,)+` comma groups,
`(?:\n[ \t]*)+` whitespace blocks — stay silent; (2) **repeating
groups whose alternation branches can match the same text** —
`(\w|\d)+`, `(a|aa)+`, `(.|x)*` — decided by real character-class
set algebra plus a leftover-can-reenter rule for literal prefixes, so
`(foo|foobar)+` and `(ab|ba)+` (uniquely decodable) stay silent;
(3) **adjacent unbounded repeats with overlapping classes** —
`\w+\w+`, `.*.*`, `[0-9]+[0-9.]*` — a lone pair only enumerates O(n)
split points, so it tiers LOW; MEDIUM when chained (3+) or inside a
repeating group; (4) **regexes built from non-literals** — `new
RegExp(x)`, `RegExp(`…${x}…`)`, `re.compile(x)`, `preg_match($p)`,
`Pattern.compile(x)`, `regexp.Compile(x)`, `Regex::new(x)` — HIGH
when the source expression is request-derived (req./request./$_GET/
$_POST/argv/args./getParameter/…), LOW when an escape call guards it
(`escapeRegExp`/`re.escape`/`preg_quote`/`Regex.Escape`/`QuoteMeta`),
silent when the name constant-folds to a quoted literal in the same
file (the literal is still analyzed at its own site) or wraps
`X.source`; (5) **file-level reachability advisory** — a flagged
dangerous pattern plus a `.test`/`.match`/`re.search`/`preg_match`
application against request-derived input in the same file. No
server, no network — every check is a property of the line, the call
window, or the file.

**Honest scope:** this is a *pre-scan*, not an audit. It cannot prove
a given input reaches the pattern, that the runtime lacks a match
timeout, or that a sanitizing wrapper exists — a FLAG means "this
construction can be driven into exponential/quadratic backtracking or
builds a pattern from input; review it". Go (`regexp`) and Rust
(`regex`) engines are RE2-class — linear-time — so pattern-shape
classes are suppressed there and only dynamic-pattern construction is
reported. A clean report is not proof the code is ReDoS-safe.

## Coverage

- **`REDOS-NESTED-QUANT` (HIGH; MEDIUM when the outer repeat is a
  bounded `{n,m}`)** — a repeating group whose body contains a
  repeat-capable atom AND the iteration boundary is ambiguous: the
  repeat's class overlaps the next consumable atom (`a*b*` inside a
  `+` group), or the branch can end on the repeat and its class
  overlaps a branch first-atom (`(a+)+`, `([a-z]+\s*)+`). Bounded
  outer quantifiers (`{0,4}`) cap the exponent — tier MEDIUM.
- **`REDOS-OVERLAP-ALT` (HIGH; MEDIUM via negated classes or bounded
  outer)** — a repeating group whose top-level branches overlap:
  identical or superset first-atoms (`\w|\d`, `.` vs any), a literal
  prefix whose leftover can start a new iteration (`a|aa` yes,
  `foo|foobar` no — 'bar' cannot begin a piece), or an empty-nullable
  branch (MEDIUM). Unique-decodability is approximated by a one-step
  Sardinas–Patterson check.
- **`REDOS-ADJACENT-REPEAT` (LOW; MEDIUM in-group or chained)** — two
  consecutive repeat-capable atoms whose character classes intersect.
- **`REDOS-USER-PATTERN` (MEDIUM; HIGH request-derived; LOW escaped)** —
  a regex constructed from a non-literal: variable, template/f-string
  interpolation, string concat, `%`-format, or a `.format()`/computed
  expression whose args are not all literals.
- **`REDOS-INPUT-APPLIED` (MEDIUM, file-level)** — a flagged pattern
  and a request-input application site coexist in one file.

## False-positive controls

Comment-stripped scan (line + `/* */` blocks), import lines skipped,
test/spec paths downgraded a tier, JS `/`-literals only read in regex
position (division stays silent), `{n}` exact counts and `?` optionals
are never "repeats", lazy `*?` suffixes parsed correctly, regex-shaped
string literals are analyzed wherever they sit (pattern-ish var names
or meta-dense no-space bodies) while prose strings stay silent, quoted
call-site masking keeps `"Use re.compile() instead."` out, and
constant folding suppresses `re.compile(MODULE_TEMPLATE)` while still
catching `_OPT_TMPL.format(delim=d)` — a genuinely dynamic arg.

## Usage

```
python3 redos_prescan.py <file-or-dir> [--json]
python3 redos_prescan.py --selftest     # 65 vectors
```

Stdlib only. Exit 0 = no HIGH/MEDIUM findings, 1 = findings, 2 = usage.