Skip to main content
Glama
regex-quality

regex-quality

by XlogicX

regex-quality

An MCP server that helps a calling LLM produce regexes that are concise, correct, and performant. It supplies the formal ground truth the model lacks: it generates adversarial input, measures time-blowup (NFA backtracking) and memory-blowup (RE2 DFA), checks correctness, and returns a structured verdict the model iterates against. The model composes; this server checks.

It is a modern Python port of XlogicX/8ball (benchrexes.pl + nfagen.pl), keeping the behaviour and dropping the brittle goto-driven Perl string-surgery where it helps.

For even more context to why this project exists, a blog form is here: https://xlogicx.micro.blog/2026/06/27/language-is-forgiving-regex-isnt.html

What it does

  • Evil/benign string generation — pump a regex to its catastrophic input (gen_evil) and to a minimal matching baseline (gen_benign).

  • NFA time metric — time evil vs benign in a killable subprocess, sweep increasing pump sizes, and classify growth linear | polynomial | exponential.

  • DFA memory metric — compile under google-re2 across a max_mem sweep to find the memory cliff.

  • Correctness — check intended positives match and negatives don't.

  • Diagnose + analyze — name the dangerous construct and the family of safe rewrites, and give a single accept/reject verdict. Never auto-rewrites.

Related MCP server: regex-le-mcp

Setup

Requires Python 3.11+.

python3 -m venv .venv
.venv/bin/pip install -e .

Run the MCP server (stdio transport):

.venv/bin/regex-quality-mcp

Register it with an MCP client, e.g. Claude Code:

claude mcp add regex-quality -- /abs/path/to/.venv/bin/regex-quality-mcp

MCP tools

tool

returns

gen_evil(pattern, qlimit=50)

{evil_string, fails_match, timed_out}

gen_benign(pattern)

{string, matches}

redos_bench(pattern, engine="python", timeout_ms=2000, qlimit=50)

{verdict, growth, evil_ms, benign_ms, delta_ms, timed_out, evil_string, curve…}

re2_memory(pattern)

{fail_level_bytes, mem_needed_bytes, compiles_anywhere, levels…}

test_cases(pattern, positives, negatives, engine="python")

{passed, false_positives, false_negatives, errors}

analyze(pattern, positives, negatives, engine="python", …)

correctness + NFA verdict + DFA memory + named construct + safe-rewrite family + accepted

suggest_rewrites(pattern, positives?, negatives?, engine="python", equivalence_mode="auto", fuzz_n=2000, seed=0)

{original, original_verdict, candidates:[…], best, any_safe_equivalent} — verified safe rewrites only

fix_until_safe(pattern, positives?, negatives?, engines=["python"], max_iterations=5, equivalence_mode="auto", fuzz_n=2000, seed=0)

{fixed_pattern, applied_strategies, per_engine, equivalence, iterations, success, failure_reason}

analyze_matrix(pattern, positives?, negatives?, engines=<all>)

{per_engine:{engine:{available, growth, verdict, curve, skipped_reason…}}, dfa, correctness, dangerous_constructs, overall_accepted, status}

See docs/SUCCESS.md for how the calling model should drive the loop, and docs/ALGORITHM.md for the ported algorithm and its known limitations.

Rewrite, fix, and multi-engine tools

  • suggest_rewrites — mechanically generates candidate safe rewrites of the dangerous construct(s) analyze locates (require_separator, factor_prefix, atomic_group, possessive) and returns only those that are verified: correctness on your test cases, non-super-linear growth on the engine, and language equivalence to the original. Equivalence is exact (DFA via Brzozowski derivatives) when both patterns are in the regular subset, else seeded differential fuzzing. A candidate is safe/best only if all three hold.

  • fix_until_safe — drives suggest_rewrites in a loop and returns a single guaranteed-safe equivalent (safe on every requested engine and equivalent to the input) or an honest success:false with a failure_reason and the closest candidate. Never fabricates a fix.

  • analyze_matrix — runs the growth classification across engines (Python re/regex, RE2, Node/V8, Go, Java, PCRE2) and returns a per-engine matrix. The same pattern can be exponential on a backtracking engine yet linear on an automaton engine (RE2/Go). Missing engines are reported, never omitted.

The no-silent-success contract

This server exists because a tool that fails silently is worse than no tool. So:

  • Never "safe"/"accepted" for an unverified condition. A rewrite is reported safe only when correctness, growth, and equivalence are all verified.

  • Unavailable engines are surfaced, not skipped. If an engine isn't installed, the output carries available:false + skipped_reason; the overall verdict becomes unverified (never accepted). We never silently substitute engines.

  • Timeouts ≠ agreement. If a fuzz comparison can't complete (e.g. a catastrophic original), equivalence is reported as not established, never as equivalent.

  • Determinism. All fuzzing takes a seed (default 0) and is reproducible.

  • Self-DoS-proof. Every candidate match — including fuzz batches — runs under the killable subprocess + hard-timeout isolation.

equivalence_mode: exact (regular subset only; refuses irregular honestly), fuzz (differential), or auto (exact when both regular, else fuzz). Exact results carry exact:true (a proof); fuzz results carry exact:false (evidence — can disprove, can only support).

Definition of done

analyze accepts a regex only if it (a) matches all intended positives and rejects all intended negatives on the target engine, and (b) shows no super-linear NFA growth on that engine, and (c) compiles within a configurable RE2 memory bound. Deterministic and repeatable.

from regex_quality.analyze import analyze
analyze("^(t+k?)+z$",      ["tz","tktz","ttktttz"], ["z","tkkz","tt"]).accepted   # False (EXPONENTIAL)
analyze("^t+(?:kt+)*k?z$", ["tz","tktz","ttktttz"], ["z","tkkz","tt"]).accepted   # True  (LINEAR, equivalent)

Engine is first-class

Vulnerability is a property of regex AND engine. The NFA metric defaults to Python re; modern Perl and RE2 optimize many catastrophes away, while Python re and Node/V8 don't. Check the engine you actually deploy on.

Project layout

src/regex_quality/   the package
  expand, lastlexeme, generate, tokenizer   string generation + AST parser
  worker, _match_worker.{py,js,go}, engines killable subprocess + engine registry
  nfa_bench, dfa_bench, diagnose, correctness, analyze   the core metrics/verdict
  derivatives, fuzz, equivalence            exact (DFA) + differential equivalence
  rewrites, suggest, matrix                 suggest_rewrites / fix_until_safe / analyze_matrix
  server                                    FastMCP server (9 tools)
tests/               maintained pytest suite (incl. the acceptance oracles)
parity/              verbatim-Perl oracle + parity harness + REPORT.md
reference/           vendored benchrexes.pl / nfagen.pl
docs/                ALGORITHM.md, SUCCESS.md

Engines

The NFA growth metric runs on any installed engine; analyze_matrix reports the whole registry. Detected at runtime (never assumed):

engine

family

status

python (stdlib re)

backtracking

always available

regex (PyPI module)

backtracking

available (pinned dep)

re2 (google-re2)

automaton (linear)

always available

node / v8

backtracking

available if node on PATH

go

automaton (linear)

wired; needs the go toolchain

java

backtracking

detection only (worker not wired — no stdlib JSON)

pcre2

backtracking

detection only (no binding/CLI wired)

Tests & parity

.venv/bin/python -m pytest                 # full suite (81 tests)

The parity harness diffs the Python port against the verbatim Perl string-generation subs over the 8ball corpora (~92% exact match; the rest are the documented newline-in-class corner). It needs perl plus Try::Tiny, IO::CaptureOutput, Time::Out and PERL5LIB set; the pytest skips cleanly when they're absent.

PERL5LIB="$HOME/perl5/lib/perl5" python parity/run_parity.py   # regenerate REPORT.md

Provenance & license

The algorithmic core of this project is XlogicX/8ball — the original, hand-written Perl ReDoS benchmarking engine (evil/benign string generation and the NFA-time / DFA-memory metrics). That hand-coded engine is the seed and the source of truth this work is verified against. The Python port and modernization, plus the equivalence/rewrite/multi-engine tooling layered on top, were substantially developed with Claude Code (AI-assisted), directed against the 8ball behaviour.

Licensed under the MIT License.

Available Tools

9 tools
analyzeA

Composite verdict: accept pattern only if it (a) passes all test cases, (b) shows no super-linear NFA growth on the engine, and (c) compiles within the RE2 memory bound. On rejection, names the dangerous construct and the family of safe rewrites to try. Does not auto-rewrite.

Inputs: pattern (required), engine, qlimit, negatives, +3 more. Returns: object

analyze_matrixA

Classify NFA growth for one pattern across MULTIPLE regex engines and return a per-engine matrix. Use this to decide whether a pattern is safe on the engine you actually deploy on -- the same regex can be exponential on a backtracking engine (Python re/regex, Node/V8, PCRE2, Java) yet linear on an automaton engine (RE2, Go).

Every requested engine appears in per_engine: installed ones with a measured growth verdict + curve, missing ones with available=false and a skipped_reason (never silently omitted). DFA/memory analysis runs once (engine-independent); correctness runs once on a reference engine. overall_accepted is true only if the pattern is safe on every requested engine that is available AND none were unavailable; otherwise the result is honestly unverified. Default engines covers the whole registry (python, regex, re2, node, go, java, pcre2).

Inputs: pattern (required), engines, negatives, positives, +1 more. Returns: object

fix_until_safeA

Drive suggest_rewrites in a loop and return a GUARANTEED-safe equivalent or an honest failure. Use this when you want the server to do the iteration for you and hand back a single fixed pattern you can trust.

success=true requires the fixed pattern to be verified non-super-linear on EVERY requested engine (default ["python"]) AND provably/empirically equivalent to the original input. If no such pattern exists, or a requested engine isn't installed, returns success=false with failure_reason and the closest candidate -- never a fabricated fix. Deterministic for a given seed.

Inputs: pattern (required), seed, fuzz_n, engines, +5 more. Returns: object

gen_benignC

Generate a minimal string that pattern matches quickly (the baseline).

Inputs: pattern (required), engine, timeout_ms. Returns: object

gen_evilB

Generate an adversarial string that pumps pattern and then fails to match, forcing maximal backtracking. Returns the evil string and whether it fails to match (a timeout counts as failing -- it's the vulnerability).

Inputs: pattern (required), engine, qlimit, timeout_ms. Returns: object

re2_memoryB

Sweep RE2 max_mem to find the DFA compile-memory cliff: the largest cap at which compilation fails and the smallest at which it succeeds.

Inputs: pattern (required). Returns: object

redos_benchA

Time the evil vs benign string AND sweep increasing pump sizes to classify growth as linear / polynomial / exponential. The verdict names the engine.

Inputs: pattern (required), engine, qlimit, timeout_ms. Returns: object

suggest_rewritesA

Mechanically generate safe-rewrite CANDIDATES for a ReDoS-prone pattern and return only the ones that are VERIFIED. Use this when analyze/redos_bench flags a pattern as super-linear and you want a concrete, drop-in replacement rather than just the name of a technique.

Each candidate is independently checked: correctness on your positives/ negatives, non-super-linear growth on engine, AND language equivalence to the original (exact DFA comparison when both are regular, else seeded differential fuzzing). A candidate is marked safe/chosen as best ONLY if all three hold -- never an unverified guess. best is null when nothing verifies. Deterministic for a given seed. Note: atomic-group/possessive candidates need a modern engine (Python re>=3.11, PCRE2, Java); RE2/Go can't parse them, which the candidate notes call out.

Inputs: pattern (required), seed, engine, fuzz_n, +4 more. Returns: object

test_casesA

Check pattern matches all positives and rejects all negatives (each in a killable subprocess). Returns pass plus any false positives/negatives.

Inputs: pattern (required), negatives (required), positives (required), engine, +1 more. Returns: object

Tool Schema Changelog

Recent tool additions, removals, and schema changes observed during successful MCP inspections.

Loading tool schema changelog…

    TDQS

    A3.7/5.0

    Scored across 9 tools

    Disambiguation4/5

    Most tools serve distinct purposes: generation, benchmarking, memory, testing, analysis, rewriting, and fixing. However, analyze, analyze_matrix, and redos_bench all involve growth classification and could be confused by an agent; detailed descriptions mitigate but don't eliminate the overlap.

    Naming Consistency3/5

    Naming mixes verb-led patterns (gen_benign, suggest_rewrites, analyze_matrix) with noun-phrases (redos_bench, re2_memory, test_cases) and a bare verb (analyze). All names are snake_case and descriptive, but the pattern is not uniform.

    Tool Count5/5

    9 tools cover the full workflow of regex safety: generation, benchmarking, memory analysis, correctness testing, composite analysis, rewrite suggestion, and automated fixing. Each tool earns its place with a distinct function.

    Completeness5/5

    The server provides end-to-end coverage from generating attack strings to verifying safe rewrites, including multi-engine classification. No obvious dead ends; fix_until_safe offers a guaranteed outcome or honest failure.

    Maintenance

    ActivityInactive
    ResponsivenessNo recent community issues

    Related MCP Connectors

    Related MCP Servers

    • F
      license
      Not graded
      quality
      C
      maintenance
      RegexForge gives AI agents a reliable way to get a regex without asking an LLM to hallucinate one. Pass in labeled examples (strings that should match, strings that shouldn't) plus an optional description; get back the regex, a proof matrix showing it handles every example, and a backtracking-risk audit flagging catastrophic-backtracking patterns. Pure symbolic synthesis over a template bank with
      -
    • A
      license
      Not graded
      quality
      B
      maintenance
      Provides a tool to extract and validate regex patterns from text content, including flags, positions, and ReDoS risk assessment. Enables AI agents to identify potentially dangerous regular expressions in code or files without needing filesystem access.
      2
      MIT
    • A
      license
      A
      quality
      D
      maintenance
      Enables AI agents to explain regex patterns in plain English and statically assess ReDoS risk before shipping, without executing the pattern or requiring an API key.
      2
      MIT
    • A
      license
      Not graded
      quality
      D
      maintenance
      Enables users to statically analyze regular expressions for catastrophic-backtracking (ReDoS) risk through real AST parsing rather than executing the pattern, flagging nested quantifiers, ambiguous alternation, and backreferences. It also generates candidate proof-of-concept attack strings with a timeout-guarded test snippet and suggests JavaScript-safe rewrites.
      MIT