redos 0.1.0

Find regular expressions vulnerable to catastrophic backtracking (ReDoS) in Python code.

redos

Find regular expressions vulnerable to catastrophic backtracking (ReDoS) — fast, static, and dependency-free.

A single innocent-looking regex like (\w+)+$ can take exponential time on a crafted input — long enough to freeze a request handler and take a service down. redos finds those patterns without importing or running your code: it parses your source with the standard-library ast module, then inspects the parsed structure of every literal regex for the constructs that cause catastrophic backtracking.

It has zero runtime dependencies, runs in CI (non-zero exit on findings), and is tuned for a low false-positive rate — patterns that Python's own regex engine rewrites into a safe, linear form are deliberately left alone.

Demo

The examples/sample project contains two vulnerable regexes so you can try it immediately: redos examples/sample.

Installation

pip install redos

Or run from a checkout without installing:

PYTHONPATH=src python -m redos path/to/project

Usage

# Scan the current directory
redos .

# Scan a specific file or package
redos path/to/your_package

# Machine-readable output for tooling
redos . --format json

# Skip directories (repeatable); common ones are skipped by default
redos . --exclude examples --no-fail

Example

$ redos examples/sample
Scanned 3 regular-expression patterns. Found 2 possible ReDoS risks:

  examples/sample/validators.py:9  re.compile(...)
    pattern: ^(\w+)+$
    [high] Nested quantifier: a repeated group that itself repeats (such as (a+)+) can backtrack exponentially.

  examples/sample/validators.py:12  re.compile(...)
    pattern: ^(a|a)+$
    [high] Ambiguous alternation under a repeat: two branches can match the same text, which can backtrack exponentially.

Exit codes

Code	Meaning
0	No risky patterns found
1	One or more risky patterns found
2	Error (e.g. path not found)

Pass --no-fail to always exit 0 (useful when you only want the report).

What it detects

redos reports two well-understood causes of catastrophic backtracking:

• Nested quantifiers — a repeated group that itself repeats, such as (a+)+, (a*)*, ([a-z]+)+, or (\w+)*.
• Ambiguous alternation under a repeat — alternatives that can match the same text inside a repeat, such as (a|a)+, or a . branch like (.|a)*.

It analyses the regex after Python's parser applies its optimisations, so patterns the engine makes safe — e.g. common-prefix factoring in (abc|abd)+, or (\w|\d)+ collapsing to a single character class — are not flagged.

Only literal patterns passed to re (or regex) functions are analysed. Patterns built from variables or expressions are skipped on purpose, so the tool never guesses and never invents findings.

How it works

1. Scan each .py file with ast and collect every literal pattern passed to a known regex function (re.compile, re.match, re.search, …).
2. Parse each pattern with the standard-library regular-expression parser to get its real structure (the same structure the engine executes).
3. Inspect that structure for nested unbounded quantifiers and ambiguous alternation under a repeat, reporting each with its file, line, and reason.

Use it as a pre-commit hook

Add this to your project's .pre-commit-config.yaml and redos runs on every commit:

repos:
  - repo: https://github.com/gazzycodes/redos
    rev: v0.1.0
    hooks:
      - id: redos

Then pre-commit install once, or run it on demand with pre-commit run redos --all-files.

Use it in CI (GitHub Actions)

- uses: actions/setup-python@v5
  with:
    python-version: "3.x"
- run: pip install redos
- run: redos .

The non-zero exit on findings fails the job automatically.

Development

git clone https://github.com/gazzycodes/redos
cd redos
PYTHONPATH=src python -m unittest discover -s tests -v

Contributions are welcome — please open an issue or PR.

License

MIT — see LICENSE.