The Near-Miss That Freezes the Matcher: Build a Worst-Case Regex Bench

Build a package-free Node 24 fixture bench for AI-generated regex correctness, state, near-misses, worker timeouts, and parser parity.

An AI coding assistant can produce a regular expression that looks compact, reads plausibly, and passes three friendly examples. That is still not enough evidence to put the matcher on a request path. A regex can return the right answer for normal input yet spend unexpectedly long rejecting a string that is almost valid.

The uncomfortable case is often a near-miss: a long prefix gives the engine many ways to satisfy overlapping repetitions, then one final character invalidates every route. A reviewer who tests only matches never visits that search space. A reviewer who pastes an unbounded stress string into the application’s main thread may discover it by freezing the process.

This guide builds a package-free Node 24 bench that keeps candidate matching inside disposable workers. It checks semantics against a simple parser, measures a bounded scaling series, demonstrates stateful flags and escaped fragments, and turns results into a review gate. The included candidate is intentionally suspect, so a HOLD result is useful evidence rather than a broken demonstration.

The bench does not prove asymptotic complexity, prove the absence of every bad input, or certify a production system. It creates reproducible regression evidence for one pattern, one contract, one runtime, and a deliberately small fixture range.

Choose the Exact Slot Before You Choose the Pattern

Start with the value being matched. Here it is a decoded projectKey field, not an entire URL, request body, log line, or arbitrary Unicode document. The contract is intentionally narrow: one to 64 UTF-16 code units; lowercase ASCII letters; optional single hyphens between nonempty letter runs; no leading, trailing, or doubled hyphen. Matching must cover the whole field.

That slot decision controls both correctness and exposure. If routing code extracts one path segment, test the decoded segment. If application code scans a 4 MB body, a 64-character benchmark is not representative. If a database already enforces a byte limit, record whether the matcher runs before or after that limit. Do not use an anchor as a substitute for tracing the real data boundary.

Contract question	Bench answer	Why it matters
What is the subject?	One decoded projectKey string	No accidental substring success and no hidden URL parsing assumptions.
Which characters are valid?	a through z, plus separator hyphens	w, locale rules, and case folding would describe a different language.
What is the size cap?	One to 64 code units before matching	The bench can include exact boundary fixtures and refuse larger stress inputs.
What is the acceptance rule?	The full field must satisfy the grammar	A successful search inside a bad value is still a rejection failure.

The candidate used below is ^(?=.{1,64}$)(?:[a-z]+-?)*[a-z]+$. It appears to encode the contract, but its repeated group and the final repeated class can divide the same letter run in many ways. Treat that observation as a review signal, not a universal static proof. Engine behavior depends on the exact pattern, input, flags, and implementation.

Build Four Fixture Families

A useful ledger contains positive, negative, near-miss, and length cases. Positives show what the business rule needs. Negatives distinguish neighboring languages that the regex must reject. Length cases lock the boundary. Near-misses preserve a long plausible prefix and fail late, where backtracking choices can become visible.

Family	Examples	Expected result	Failure it can reveal
Positive	a, alpha-beta, 64 letters	Match	Incorrect anchors, minimum lengths, or separator handling
Negative	empty, -alpha, alpha-, alpha--beta, Alpha, alpha_beta	No match	Substring acceptance or an overly broad character class
Near-miss	repeated a followed by !	No match within the deadline	Large rejection search after a plausible prefix
Length	64 letters and 65 letters	Match, then reject	Off-by-one limits or a cap enforced in the wrong layer

Keep literal expected answers in the ledger, but also compute them through an independent oracle. If both the regex and its tests were generated from the same mistaken explanation, a shared assumption can make every assertion green. The parser in the fixture walks characters and separator state; it does not execute the candidate pattern.

Near-miss generation should be boring and reviewable. Use a fixed series such as 8, 12, 16, 20, 24, 28, and 32 prefix letters followed by one forbidden character. Do not jump straight to a million-character payload. The largest included input is 65 code units, and every worker has a deadline no greater than 250 milliseconds.

Recognize Hazards Without Pretending to Solve Regex Analysis

OWASP’s ReDoS guidance highlights patterns with repetition inside repetition and alternatives or subexpressions that can match overlapping text. A late failing suffix can force a backtracking engine to revisit those choices. The sample candidate has overlapping repetitions over lowercase letters, so it deserves dynamic investigation and probably simplification.

That heuristic is not a theorem. A nested quantifier is not automatically exploitable, and a pattern that lacks the textbook shape is not automatically safe. Anchors do not place a time limit on matching. A maximum input length reduces exposure, but it does not tell you whether the worst allowed value fits the service budget. A quick result on one laptop does not establish behavior on another runtime version or architecture.

Static review should therefore produce questions: Can two repeated pieces consume the same characters? Does an optional separator create alternate partitions? Does a rejection happen only after most of the field has matched? Is the field size bounded before the regex runs? Then answer those questions with a simpler construction where possible, an independent parser, and isolated measurements.

The USENIX Security paper Freezing the Web studied real-world JavaScript regex denial-of-service risks and emphasized that problematic behavior reaches practical applications. It supports taking the issue seriously; it does not turn this small fixture into a proof about every engine or input.

Escape Dynamic Text and Test Stateful Flags Separately

Sometimes a pattern combines fixed syntax with text supplied by a user, configuration file, or earlier program step. That fragment must be treated as literal text unless the contract explicitly grants regex syntax. In ECMAScript 2026, RegExp.escape() provides the standard transformation. The fixture escapes docs/v1.0+beta? before placing it between anchors, then checks both a literal match and a nearby nonmatch.

Do not replace it casually with a short hand-written character replacement. The standard algorithm handles more than the most familiar punctuation, including cases where the first character could otherwise merge with preceding escape syntax. Node 24 exposes RegExp.escape(), but older runtimes may not. Feature-detect it, pin the runtime used by tests and deployment, or adopt an audited compatibility implementation. Silently calling a missing method is not a compatibility plan.

Flags create a different class of defect. With g or y, test() reads and writes lastIndex. Reusing the same object can therefore make identical calls produce different outcomes. Sticky matching also begins exactly at lastIndex. The fixture records both transitions using short, safe expressions on the main thread.

Decide whether the production API needs a stateless predicate or an iterator. For a predicate, construct a fresh regex, remove stateful flags, or reset lastIndex at an explicit boundary. Add repeated-call and interleaved-input fixtures. Do not diagnose a state leak as a performance problem, and do not let timing tests hide a semantic state bug.

Run Candidate Matching Only in Disposable Workers

Copy the next two blocks into one temporary directory as regex-worker.mjs and regex-bench.mjs. They use only Node built-ins. Run them with Node 24 using node regex-bench.mjs. The main file never constructs or executes the suspect candidate. It sends the source, flags, and bounded input to a worker; if the deadline expires, it terminates that worker and records a timeout.

regex-worker.mjs

import { parentPort, workerData } from 'node:worker_threads';
import { performance } from 'node:perf_hooks';

try {
  const regex = new RegExp(workerData.source, workerData.flags);
  const startedAt = performance.now();
  const matched = regex.test(workerData.input);

  parentPort.postMessage({
    status: 'completed',
    matched,
    lastIndex: regex.lastIndex,
    elapsedMs: Number((performance.now() - startedAt).toFixed(3)),
  });
} catch (error) {
  parentPort.postMessage({
    status: 'error',
    error: error instanceof Error ? error.message : String(error),
  });
}

regex-bench.mjs

import assert from 'node:assert/strict';
import { Worker } from 'node:worker_threads';

const candidate = {
  source: '^(?=.{1,64}$)(?:[a-z]+-?)*[a-z]+$',
  flags: '',
};

function runIsolated({ source, flags = '', input, timeoutMs = 200 }) {
  if (input.length > 65) throw new RangeError('fixture input exceeds the 65-code-unit bench cap');
  if (timeoutMs < 10 || timeoutMs > 250) throw new RangeError('deadline is outside the 10-250 ms bench range');

  return new Promise((resolve, reject) => {
    const worker = new Worker(new URL('./regex-worker.mjs', import.meta.url), {
      workerData: { source, flags, input },
    });
    let settled = false;

    const finish = (action, value) => {
      if (settled) return;
      settled = true;
      clearTimeout(timer);
      action(value);
    };

    const timer = setTimeout(async () => {
      if (settled) return;
      settled = true;
      clearTimeout(timer);
      await worker.terminate();
      resolve({ status: 'timeout', matched: null, elapsedMs: timeoutMs });
    }, timeoutMs);

    worker.once('message', (message) => finish(resolve, message));
    worker.once('error', (error) => finish(reject, error));
    worker.once('exit', (code) => {
      if (code !== 0 && !settled) {
        finish(reject, new Error('worker exited with code ' + code));
      }
    });
  });
}

function parseProjectKey(input) {
  if (input.length < 1 || input.length > 64) return false;
  let needLetter = true;

  for (const char of input) {
    const lowercaseAscii = char >= 'a' && char <= 'z';
    if (lowercaseAscii) {
      needLetter = false;
    } else if (char === '-' && !needLetter) {
      needLetter = true;
    } else {
      return false;
    }
  }

  return !needLetter;
}

const fixtures = [
  { group: 'positive', input: 'a', expected: true },
  { group: 'positive', input: 'alpha-beta', expected: true },
  { group: 'negative', input: '', expected: false },
  { group: 'negative', input: '-alpha', expected: false },
  { group: 'negative', input: 'alpha-', expected: false },
  { group: 'negative', input: 'alpha--beta', expected: false },
  { group: 'negative', input: 'Alpha', expected: false },
  { group: 'negative', input: 'alpha_beta', expected: false },
  { group: 'length', input: 'a'.repeat(64), expected: true },
  { group: 'length', input: 'a'.repeat(65), expected: false },
  { group: 'near-miss', input: 'a'.repeat(16) + '!', expected: false },
];

const findings = [];
const fixtureResults = [];

for (const fixture of fixtures) {
  assert.equal(parseProjectKey(fixture.input), fixture.expected, 'fixture ledger disagrees with parser oracle');
  const result = await runIsolated({ ...candidate, input: fixture.input });
  fixtureResults.push({ group: fixture.group, length: fixture.input.length, expected: fixture.expected, ...result });

  if (result.status !== 'completed') {
    findings.push({ kind: 'fixture-' + result.status, group: fixture.group, length: fixture.input.length });
  } else if (result.matched !== fixture.expected) {
    findings.push({ kind: 'semantic-mismatch', group: fixture.group, length: fixture.input.length });
  }
}

let heartbeatTicks = 0;
const heartbeat = setInterval(() => { heartbeatTicks += 1; }, 10);
const scaling = [];

for (const prefixLength of [8, 12, 16, 20, 24, 28, 32]) {
  const input = 'a'.repeat(prefixLength) + '!';
  const expected = parseProjectKey(input);
  const result = await runIsolated({ ...candidate, input, timeoutMs: 200 });
  scaling.push({ prefixLength, inputLength: input.length, expected, ...result });

  if (result.status === 'timeout') {
    findings.push({ kind: 'scaling-timeout', prefixLength });
  } else if (result.status !== 'completed' || result.matched !== expected) {
    findings.push({ kind: 'scaling-mismatch', prefixLength, status: result.status });
  }
}

clearInterval(heartbeat);
assert.ok(heartbeatTicks > 0, 'main-thread heartbeat did not advance');

assert.equal(typeof RegExp.escape, 'function', 'this fixture requires RegExp.escape');
const literal = 'docs/v1.0+beta?';
const literalRegex = new RegExp('^' + RegExp.escape(literal) + '$', 'u');
assert.equal(literalRegex.test(literal), true);
assert.equal(literalRegex.test('docs/v1x0+beta?'), false);

const globalRegex = /[a-z]+/g;
const stickyRegex = /[a-z]+/y;
stickyRegex.lastIndex = 1;
const stateTrace = {
  global: [
    { matched: globalRegex.test('abc'), lastIndex: globalRegex.lastIndex },
    { matched: globalRegex.test('abc'), lastIndex: globalRegex.lastIndex },
  ],
  sticky: { matched: stickyRegex.test('_abc'), lastIndex: stickyRegex.lastIndex },
};
assert.deepEqual(stateTrace.global, [
  { matched: true, lastIndex: 3 },
  { matched: false, lastIndex: 0 },
]);
assert.deepEqual(stateTrace.sticky, { matched: true, lastIndex: 4 });

console.log(JSON.stringify({
  runtime: process.version,
  candidate,
  releaseGate: findings.length === 0 ? 'RELEASE' : 'HOLD',
  findings,
  heartbeatTicks,
  stateTrace,
  fixtureResults,
  scaling,
}, null, 2));

The timeout begins before worker startup, so it is a wall-clock guard for the complete isolated attempt, not a pure matcher benchmark. That is conservative for a safety gate but noisy for microbenchmarking. If you need stable performance tracking, first measure a harmless worker baseline on the same machine, repeat each row, preserve raw samples, and compare like-for-like runtime and hardware.

The termination branch awaits worker.terminate(). An exception, nonzero exit, or malformed pattern becomes an explicit result instead of escaping into the application thread. Input and deadline guards prevent an enthusiastic reviewer from converting this teaching fixture into an unbounded load generator.

Read the Scaling Series as Evidence, Not a Complexity Proof

The scaling rows hold the invalid suffix constant while increasing only the valid-looking prefix. That makes the relationship easier to inspect. A sharp rise, a timeout at a larger row, or a timeout moving to a smaller row after a code change is actionable regression evidence. It does not by itself identify a mathematical complexity class.

Timeouts are censored observations: the matcher did not finish before this bench’s deadline. The true duration is unknown. Report them as timeout at 200 ms, not as a measured 200 ms execution and not as proof of exponential behavior. A completed 12 ms row is also not a safety guarantee for all strings of that length; the generator covers one deliberately chosen family.

The parser oracle answers the same contract without regex backtracking. For every completed candidate run, the bench compares the boolean result with the parser. A candidate that is fast but disagrees is still a HOLD. A candidate that agrees but times out is also a HOLD. Correctness and availability are independent release conditions.

The ten-millisecond interval is a coarse event-loop availability check. While a worker is busy or terminated, the main thread should continue ticking. The assertion catches the accidental regression where someone moves suspect regex.test() back into the main file. It does not model production request latency, garbage collection, CPU contention, or a pool saturated by many simultaneous workers.

Keep the JSON output with the candidate source, flags, Node version, fixture lengths, elapsed values, timeout locations, heartbeat ticks, and verdict. A future run can then compare the same bounded series. If the runtime changes, treat the result as a new baseline rather than silently mixing samples.

Turn Findings Into a Review Gate

Use a small decision table instead of arguing from one average time.

Observation	Decision	Next action
Candidate and parser disagree	HOLD	Resolve the contract or replace the pattern; add the value as a permanent fixture.
Any bounded row times out	HOLD	Simplify the expression, move validation to a parser, and rerun the same series.
g or y changes repeated-call behavior unexpectedly	HOLD	Remove reuse or define and test the lastIndex lifecycle.
Dynamic fragment is not escaped or runtime support is unknown	HOLD	Use RegExp.escape() under a pinned compatible runtime or an audited fallback.
All fixtures complete and agree within the approved budget	Eligible for review	Run broader integration, load, and observability checks before release.

Prefer a transparent parser when the field grammar is small. If a regex remains, ask a human reviewer to approve the exact slot, maximum length, pattern and flags, dynamic-fragment policy, near-miss generator, deadline, runtime version, and production fallback. Add monitoring for latency and worker termination without logging sensitive values.

AI can help enumerate fixtures, translate a written grammar into test cases, and explain a diff. It should not choose an availability budget, declare a static safety proof, or dismiss a timeout. Require every generated change to survive the frozen ledger and the parser oracle.

Sources and Scope

• ECMAScript 2026, Text Processing defines regular expression semantics, state including lastIndex, and RegExp.escape().
• Node.js 24 Worker Threads documents worker construction, messaging, lifecycle events, and termination used by the isolation harness.
• OWASP: Regular Expression Denial of Service describes risky repetition and overlap shapes and the importance of crafted failing input.
• Staicu and Pradel, “Freezing the Web” presents an empirical study of JavaScript regex denial-of-service risks in web applications.

Sources were checked for this Node 24 fixture on August 26, 2026. The code is a bounded teaching and regression harness, not a production sandbox, general regex analyzer, formal verification system, or guarantee against denial of service. Recheck the exact Node documentation and ECMAScript support when changing runtime versions.