Testing regex with reverse generation

I had a regex once that passed 37 hand-written tests. First fuzz run found a crash in 200ms. That’s what this post is about: testing regex with reverse generation using pointybeard/reverse-regex to generate strings guaranteed to match a regex, so you can test your validation code against inputs you didn’t think of.

Normal regex checks whether a string fits a pattern. This library does the reverse: give it a pattern, it gives you back strings that match. If your regex passes strings through to processing code, you want to know every string it lets through is one your code can handle. This is how you find out.

Regex syntax crash course

If you already know regex basics, skip to the next section. If not: a regex is a compact way to describe a string pattern. In PHP you use PCRE functions preg_match(), preg_replace(), etc. and wrap patterns in delimiters like /pattern/.

<?php

// Does the string look like a date in YYYY-MM-DD format?
$pattern = '/^\d{4}-\d{2}-\d{2}$/';

if (preg_match($pattern, '2024-07-14')) {
    echo "Valid date format\n";   // ← printed
}

if (preg_match($pattern, '14-07-2024')) {
    echo "Valid date format\n";   // ← NOT printed
}

?>

The building blocks you’ll see most often:

Regex as leaky abstractions

Joel Spolsky coined “leaky abstraction” for tools that hide complexity but make you understand the guts when something breaks. Regex is a textbook case.

Look at this email validator:

<?php

$pattern = '/^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$/';

?>

Looks fine. Until it’s not (spoiler: it never is, except in illustration post on Internet).

The abstraction leaks because:

• Edge case blindness: you test the 5-6 inputs you already thought of, ship it, and the bugs live in the thousands of strings you never considered.
• Catastrophic backtracking: nested quantifiers like (a+)+can make the engine explore an exponential number of paths on certain inputs. Looks fine in dev, hangs in production. PHP caps backtracking, so at least you won’t OOM too much.
• Silent scope changes: someone refactors the pattern to handle a new case, fixes that, breaks an old one. A regex is just a string; no type system, no compiler. Only a runtime failure later.

The root problem: testing a regex by hand is sampling, not probing. You pick winners and a few losers. The bugs live in the inputs you didn’t imagine.

Fuzz testing your regex

Fuzz testing means feeding a system large volumes of automatically generated inputs to find crashes, hangs, or wrong results. Applied to regex, the question shifts from “does my pattern accept the strings I wrote down?” to “does it accept exactly the strings it should, across wildly varied inputs?”

Two directions

Most devs test one direction: string → regex → match/no-match. There’s a second direction that’s just as useful: generate strings guaranteed to match, then verify your downstream code handles all of them, or you recognize them for what they are: valid or garbage.

Think about a phone number parser: you have a regex that accepts +31-6-12345678. You write ten examples by hand. A reverse generator produces ten thousand structurally valid variants in seconds. Does your parser handle all of them? You’ll find out.

When it shines: reverse generation is most useful when a regex validates input before processing. You want to prove every string validation passes is also a string your processing code handles gracefully: no silent truncation, no type errors, no format assumptions baked into the parser. Just plain reality check.

Reverse regex: what it is and how to install it

A reverse regex generator takes a pattern and produces strings guaranteed to match. Instead of checking a string against a pattern, it walks the pattern’s parse tree, makes random choices at every branch and quantifier, and assembles valid output.

We’ll use pointybeard/reverse-regex, a maintained fork of icomefromthenet/ReverseRegex. It parses PCRE patterns into a generator tree with a pluggable random source.

The pipeline: lexer → token stream → parser → generator tree → generate() with random source. You don’t need to care about the internals to use it, but it’s nice to know what’s happening.

Install

composer require pointybeard/reverse-regex

The tool requires PHP 7.2+. It works without a warning until PHP 8.3, then starts running into deprecations, but it keeps working fine. Load the autoloader and import the four classes:

<?php

use ReverseRegex\Lexer;
use ReverseRegex\Random\SimpleRandom;
use ReverseRegex\Parser;
use ReverseRegex\Generator\Scope;

require 'vendor/autoload.php';

?>

The basic pattern

Every generation call follows the same structure:

<?php

$pattern   = '[a-z]{5}';          // your pattern (no delimiters!)

$lexer     = new Lexer($pattern);
$random    = new SimpleRandom();
$parser    = new Parser($lexer, new Scope(), new Scope());
$generator = $parser->parse()->getResult();

$result = '';
$generator->generate($result, $random);

echo $result;  // e.g. "xqwjm"

?>

Unlike preg_match(), this library doesn’t use PCRE delimiters. Pass the bare pattern: no slashes or any other alpha-numeric delimiter, and no flags.

Examples: simple to complex

In the next examles, I’ll reuse the same boilerplate: just plug in the pattern and run it.

Fixed literal

A fixed string always generates itself. Boring but it confirms the setup works.

<?php

$pattern = 'hello';
// Always: "hello"

?>

Character class with exact repetition

A slug or token pattern: fixed-length lowercase alphanumeric.

<?php

$pattern = '[a-z0-9]{10}';
// Sample: "j2ydisgoks"  "4rtnxkqpaw"  "m8vlcez1ij"

?>

Range quantifier

{3,8} means the library picks a random length between 3 and 8 on each call. Good for exercising code that handles variable-length input.

<?php

$pattern = '[A-Z]{3,8}';
// Sample: "QRTXM"  "AZPLWKBJ"  "NYF"

?>

Digit shorthands

\d expands to [0-9]. Good for numeric formats.

<?php

$pattern = '\d{4}-\d{2}-\d{2}';
// Sample: "1983-06-27"  "2041-11-03"  "0719-88-54"

?>

Notice 0719-88-54 matches the pattern — four digits, dash, two digits, dash, two digits — but month 88 doesn’t exist. The regex describes a format, not real calendar dates. This is exactly the kind of edge case reverse testing surfaces.

Alternation

| picks one branch at random. Run the generator lots of times to hit every branch.

<?php

$pattern = '(GET|POST|PUT|PATCH|DELETE)';
// Sample: "POST"  "DELETE"  "GET"  "PATCH"

// See the distribution across all five methods:
for ($i = 0; $i < 1000; $i++) {
    $result = '';
    $generator->generate($result, $random);
    $counts[$result] = ($counts[$result] ?? 0) + 1;
}
print_r($counts);

?>

Groups with alternation and quantifiers

Nest groups, quantifiers, and alternation for structured output.

<?php

// A "word": either 4-6 lowercase letters or 2-3 uppercase letters
$pattern = '([a-z]{4,6}|[A-Z]{2,3})';
// Sample: "mxpqlr"  "BT"  "hwzk"  "KJP"

?>

Structured format — product SKU

Combine everything into realistic values: a SKU like CAT-XXXX-###.

<?php

$pattern = '[A-Z]{2,3}-[A-Z]{4}-\d{3}';
// Sample: "EL-QRTW-847"  "MNP-XKZB-031"  "AV-YJLM-509"

?>

Structured format — IPv4 address

The generator produces valid-looking addresses, including ones outside the 0–255 range. Format validation only gets you so far.

<?php

$pattern = '\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}';
// Sample: "192.4.255.18"  "7.841.0.63"  "10.0.0.1"
// "7.841.0.63" matches the pattern. Not a real IP.

?>

Full fuzz test harness

A reusable helper that generates strings from a pattern and runs a callable assertion against each. Drop this in your test suite.

<?php

declare(strict_types=1);

use ReverseRegex\Lexer;
use ReverseRegex\Random\SimpleRandom;
use ReverseRegex\Parser;
use ReverseRegex\Generator\Scope;

require 'vendor/autoload.php';

function fuzzPattern(string $pattern, int $count, callable $check): void
{
    $lexer     = new Lexer($pattern);
    $random    = new SimpleRandom();
    $parser    = new Parser($lexer, new Scope(), new Scope());
    $generator = $parser->parse()->getResult();

    for ($i = 0; $i < $count; $i++) {
        $sample = '';
        $generator->generate($sample, $random);
        $check($sample);
    }
}

// ── Example: fuzz test a SKU parser ──────────────────────
fuzzPattern(
    '[A-Z]{2,3}-[A-Z]{4}-\d{3}',
    10_000,
    function (string $sku) {
        $parts = explode('-', $sku);
        assert(count($parts) === 3,      "Expected 3 parts, got: {$sku}");
        assert(ctype_upper($parts[0]),   "Category not uppercase: {$sku}");
        assert(ctype_digit($parts[2]),   "Suffix not numeric: {$sku}");
    }
);

echo "All 10,000 SKUs parsed correctly.\n";

?>

Reproducibility with a seeded random

SimpleRandom is non-deterministic. When a fuzz run finds a failure, you’ll want to replay it. Pin the seed with srand():

<?php

srand(42);   // same seed = same string sequence every time

$result = '';
$generator->generate($result, $random);

?>

PHPUnit tip: log the seed at the start of each test run. CI flags a failure → re-run with that seed → identical strings → reproducible bug.

Limits of reverse regex

It’s a good tool. It’s not magic. Here are some aspects to keep in mind when using it.

Volume matters

One generated string tells you almost nothing. A pattern with ten character classes, each with 62 possibilities, is an astronomical search space. Budget 1,000+ iterations in unit tests, 10,000+ in dedicated fuzz runs.

Nobody wants to read generated strings

Someone called Xqmpklzt or a licence plate VB-047-RMQZare structurally correct and semantically garbage. Great for testing, terrible for failure messages, demo databases, or anything a human has to read. If you need to test these or seed databases, it might be better to rely on Faker, for more realistic values.

Unbounded quantifiers are dangerous

* and + have no upper bound. The library interprets them as PHP_INT_MAX max repetitions. In practice it usually doesn’t go crazy, but \w+ could theoretically produce a million-character string. Use {n,m} ranges with sane limits. It is safer for generating data, but also for the validation regex.

Format ≠ semantics

The generator guarantees structural matches. It can’t enforce month ≤ 12, IP octets ≤ 255, valid IBAN checksums, or deliverable email addresses. If your validation relies on rules not encoded in the regex, the generated output only probes the structural layer.

Unsupported PCRE features

Lookaheads (?=...), lookbehinds (?<=...), backreferences \1, named captures (?P...), and Unicode \p{...} aren’t supported. Test your pattern in isolation before wiring it into a fuzz harness.

No negative testing

Reverse generation only produces strings that match. For near-misses, off-by-one, or single-character-outside-class cases, you still write those by hand or use a mutation-based approach.

Testing regex with reverse generation: use it, don’t rely on it

Reverse regex is one layer. Combine it with hand-written edge cases for semantics, property-based testing libraries for wider mutation, and integration tests against real-world data. No single technique covers everything. Together they make your regex much harder to fool.