regexbench

Evaluate a regex the way a benchmark should.

Scoring generated regular expressions by string comparison is wrong: (ab)+ and ab(ab)* are the same language and different strings. And a pattern that passes every test can still hang a production server.

regexbench answers the three questions that actually matter — is it the same language, does it behave, and is it safe to run.

Semantic equivalence

Both patterns compile to DFAs and the automata are compared, which is the DFA-EQ metric used in the regex generation literature.

from regexbench import equivalent

bool(equivalent(r"(ab)+", r"ab(ab)*"))      # True
bool(equivalent(r"[0-9]+", r"[0-9][0-9]*"))  # True

result = equivalent(r"a+", r"a*")
result.verdict     # <Verdict.DIFFERENT>
result.witness     # '' — the shortest string telling them apart

Witnesses are shortest-first and real: every one is a string you can paste into re.fullmatch to see the difference yourself.

When it says it doesn't know. Backreferences make a pattern non-regular, and equivalence is then formally undecidable. Rather than guess, the verdict is UNDECIDABLE:

equivalent(r"(a)\1", r"aa").verdict     # <Verdict.UNDECIDABLE>
equivalent(r"(?=a)ab", r"ab").verdict   # <Verdict.UNSUPPORTED>

The two are kept apart on purpose. Lookaround is regular — it only escapes the regular languages when combined with backreferences — so refusing it is a statement about this engine, not about the problem. UNDECIDABLE means nothing can answer; UNSUPPORTED means this does not.

Shorthand classes follow re, which means Unicode. \d matches every Unicode digit, so it is not [0-9]:

equivalent(r"\d", "[0-9]").verdict     # <Verdict.DIFFERENT>
equivalent(r"\d", "[0-9]").witness     # '٣'

That is pedantic and it is also what re does — and check() runs the real re, so an engine that called them equivalent would contradict the tool it lives in.

Match semantics

Equivalence and scoring default to full matches, like re.fullmatch. Not every benchmark means that, and the disagreement is silent — a reference written for re.search simply looks wrong when full-matched.

from regexbench import Semantics, equivalent

equivalent("a", ".*a.*").verdict                              # DIFFERENT
equivalent("a", ".*a.*", semantics=Semantics.SEARCH).verdict  # EQUIVALENT

Under SEARCH, p is rewritten to .*p.* around whatever it already anchors, so there is still exactly one notion of equivalence underneath. The wildcards distribute over a top-level alternation, because in a|b$ the anchor constrains b and says nothing about a.

Measured on Re(gEx|DoS)Eval: its reference expressions pass 100% of their own tests under search and 94.0% under fullmatch. Choosing wrong there would score 46 gold patterns as failing the tests they were written for.

Dialects

The natural-language-to-regex corpora are not written in Python syntax. They use dk.brics.automaton notation, where & is intersection and ~ is complement — and Python's re compiles both as ordinary literals without complaint.

from regexbench import Dialect, equivalent

# In Python this is the literal "a&b". In dk.brics it is the empty language.
equivalent("(a)&(b)", r"a\&b").verdict                        # EQUIVALENT
equivalent("(a)&(b)", r"a\&b", dialect=Dialect.BRICS).verdict # DIFFERENT

equivalent("([0-9])&([0-4])", "[0-4]", dialect=Dialect.BRICS).verdict  # EQUIVALENT

& appears in 22.8% of KB13 and 27.3% of NL-RX, ~ in 7.6% and 17.2%. The dialect is never sniffed, because both readings compile and only one is right.

The grammar follows dk.brics.automaton exactly, including precedence — union binds loosest, then intersection, then concatenation, then repetition, then complement. Note that equivalence with both complement and intersection is non-elementary, not merely PSPACE-complete: deeply nested &/~ is refused with UNSUPPORTED once determinization passes a state budget, rather than run until the machine gives up.

ReDoS safety

Two passes. Structural analysis finds the shapes that backtrack catastrophically and says why; an empirical pass then runs the pattern against attack strings under a timeout to catch what the structural pass doesn't model.

from regexbench import screen

screen(r"(a+)+").risk        # <Risk.EXPONENTIAL>
screen(r"(a+)+").reason      # 'a quantifier wraps a quantified group...'
screen(r"\d{3}-\d{4}").risk  # <Risk.SAFE>

SAFE means "no known-bad shape and no blow-up on what we tried". That is a screening result, not a proof.

The structural pass covers three of the five vulnerability families named in the ICPC 2024 study of LLM-generated regexes: nested quantifiers, exponential overlapping disjunction, and polynomial overlapping adjacency. Exponential overlapping adjacency and starting-with-large-quantifier are not modelled structurally and are only caught when the empirical pass happens to trip them. That study also found LLM-generated regexes skew toward polynomial ReDoS — the cheaper family to miss, and the one a short attack string is least likely to expose.

Running untrusted patterns

Python's re has no timeout, and a pathological pattern spins inside a single C call that no signal or thread can interrupt. The only reliable escape is a separate process:

from regexbench import safe_search, MatchTimeout

try:
    safe_search(r"(a+)+$", "a" * 40 + "!", timeout=0.5)
except MatchTimeout:
    ...   # the process was killed; your server is still up

Costs milliseconds per call. Use it for model output and user input; use re directly for patterns you wrote.

Scoring against examples

from regexbench import Task, evaluate

task = Task(
    prompt="three digits, a hyphen, four digits",
    positives=["123-4567"],
    negatives=["123-456", "abc"],
    reference=r"[0-9]{3}-[0-9]{4}",
)

report = evaluate(r"[0-9][0-9][0-9]-[0-9]{4}", task)
report.correctness.accuracy   # 1.0
report.equivalence.verdict    # <Verdict.EQUIVALENT>
report.usable                 # True — correct *and* safe

usable is the one to gate on: never a ReDoS liability, never proven different from the reference, and perfect on whatever examples exist. A pattern that passes every example it was given can still be known-wrong — #[0-9a-f]{6} passes a hex-colour task whose examples happen to be lowercase — and the reference settles it.

Benchmarks

Scores are comparable only when they are computed on the same problems, so loaders are included for the corpora this literature reports on. No dataset is redistributed; you download the files and pass the path.

from regexbench.datasets import load_regexeval, load_deep_regex, load_tasks

tasks = load_regexeval("RegexEval.json")      # 762 real prompts, with tests
tasks = load_deep_regex("datasets/KB13")      # 824 gold patterns, no examples
tasks = load_tasks("my_eval.jsonl")           # your own

Each loader sets the semantics and dialect the corpus actually uses. Loaders never filter: a record this engine cannot represent is still returned and surfaces as UNSUPPORTED when scored, because a corpus quietly reduced to its easy half reports a number nobody can interpret.

See docs/benchmarks.md for where to download each one and what coverage to expect.

Scoring a whole model

from regexbench import run

report = run(tasks, predictions, name="my-model", workers=8)
print(report.table(ks=(1, 5)))

my-model
762 tasks, 762 answered
  pass@1               77.0%
  dfa-eq@1             56.2%  (whole corpus — a lower bound)
  dfa-eq@1 (decided)   74.9%  (engine limits excluded — model only)
  exact@1              55.4%
  usable@1             65.4%
  vulnerable@1         12.1%  (lower is better)
  180 task(s) undecidable — counted against dfa-eq, excluded from dfa-eq (decided)

predictions is a mapping from task name to the pattern, or to a list of sampled patterns, or a sequence aligned with the tasks. All metrics use the unbiased pass@k estimator, so they line up with published numbers.

A metric no task can answer is None, not zero — KB13 ships no examples, and a 0% pass@1 would read as a model failing a question nobody asked it.

dfa-eq is reported twice, because one number cannot answer both honest questions. The plain figure counts undecidable comparisons as failures: how much of the corpus was verified correct, a lower bound that cannot flatter. The (decided) figure drops those tasks from the denominator: how much of what could be checked was correct, the model alone. On KB13 the gold answers themselves score 51.1% and 100.0% — a 49-point spread that is not a model result at all, but the \b gap in this engine.

CLI

regexbench eq '[0-9]+' '[0-9][0-9]*'        # equivalent
regexbench eq --search 'a' '.*a.*'          # equivalent
regexbench eq --brics '([0-9])&([0-4])' '[0-4]'
regexbench safety '(a+)+'                   # exponential
regexbench check '\d{3}' task.json          # 5/5 (100%)

regexbench run regexeval RegexEval.json --predictions preds.json --k 1 5

Exit codes are meaningful, so these compose in CI: 0 on equivalent/safe/all passing, 1 otherwise.

run also takes --use-reference, which scores every task against its own gold answer. That sounds circular and is the cheapest sanity check available: if pass@1 comes back well below 100%, the dataset is loaded with the wrong match semantics and every later number is meaningless.

Supported syntax

The equivalence engine covers the genuinely regular subset: literals, escapes (\d \w \s and negations), ., character classes with ranges and negation, * + ? {m,n}, alternation, and grouping. In the BRICS dialect it also covers intersection (&), complement (~), any-string (@) and the empty language (#) — all regular operations, computed on the automata directly. Anything else returns UNSUPPORTED or UNDECIDABLE rather than a wrong answer.

Word boundaries (\b, \B) are supported. They look like lookaround and are not: the condition depends only on the two characters either side of a position, so a finite automaton can carry it in one bit of state. Deciding it does require the alphabet to tell word characters from the rest, which is why "every other character" is two symbols here rather than one.

In the dk.brics dialect this is a deliberate deviation from the spec, which escapes \b to the literal character b. The corpora mean a boundary and their paired descriptions say so — KB13 glosses .*\b[A-Za-z]*er\b.* as "lines using words ending in 'er'", which the literal reading does not describe.

\B follows Python rather than mathematics: it is ¬\b everywhere except the empty string, which re refuses even though no boundary exists there. Patterns scored here are run by re, so re is what gets modelled.

Install

pip install regexbench

Python 3.10+. No runtime dependencies — stdlib only, deliberately, so this drops into a training or CI pipeline without dragging anything with it.

Status

Alpha: the API will change, and the version is 0.x for that reason. What is stable is the discipline — every number in this README and in docs/benchmarks.md came from a run, and the equivalence engine is differential-tested against Python's own re on every release.

Known limits, in the order they cost you coverage:

Correctness scoring and ReDoS screening have no such limit — they run the real re engine and work on any pattern it compiles.

Contributing

See CONTRIBUTING.md. The short version: a wrong answer is worse than no answer, so anything the engine cannot decide has to say so.

Changes are listed in CHANGELOG.md.

License

Apache-2.0.