regex-quality
Click on "Deploy Server".
Wait a few minutes for the server to deploy. Once ready, it will show a "Started" state.
In the chat, type
@followed by the MCP server name and your instructions, e.g., "@regex-quality Check regex '^(a+)+$' for exponential backtracing"
That's it! The server will respond to your query, and you can continue using it as needed.
Here is a step-by-step guide with screenshots.
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-re2across amax_memsweep 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-mcpRegister it with an MCP client, e.g. Claude Code:
claude mcp add regex-quality -- /abs/path/to/.venv/bin/regex-quality-mcpMCP tools
tool | returns |
|
|
|
|
|
|
|
|
|
|
| correctness + NFA verdict + DFA memory + named construct + safe-rewrite family + |
|
|
|
|
|
|
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)analyzelocates (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 issafe/bestonly if all three hold.fix_until_safe— drivessuggest_rewritesin a loop and returns a single guaranteed-safe equivalent (safe on every requested engine and equivalent to the input) or an honestsuccess:falsewith afailure_reasonand the closest candidate. Never fabricates a fix.analyze_matrix— runs the growth classification across engines (Pythonre/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 becomesunverified(neveraccepted). 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.mdEngines
The NFA growth metric runs on any installed engine; analyze_matrix reports the
whole registry. Detected at runtime (never assumed):
engine | family | status |
| backtracking | always available |
| backtracking | available (pinned dep) |
| automaton (linear) | always available |
| backtracking | available if |
| automaton (linear) | wired; needs the |
| backtracking | detection only (worker not wired — no stdlib JSON) |
| 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.mdProvenance & 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 toolsanalyzeA
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
Scored across 9 tools
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 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.
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.
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
Related MCP Connectors
Run regexes on real engines (JavaScript, RE2/Go) against test strings, and prove ReDoS safety.
Detects catastrophic-backtracking (ReDoS) regex risk via AST parsing, with JS-safe rewrites.
Explain a regex in plain English and detect catastrophic backtracking risk.
Test your AI agents for security and safety weaknesses, and re-verify the fixes.
Related MCP Servers
- FlicenseNot gradedqualityCmaintenanceRegexForge 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-
- AlicenseNot gradedqualityBmaintenanceProvides 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.2MIT
- AlicenseAqualityDmaintenanceEnables 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.2MIT
- AlicenseNot gradedqualityDmaintenanceEnables 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