Catastrophic backtracking and ReDoS

PCRE2 needed 655,360 turns of its matching loop to refuse eighteen a characters and one x on the pattern ^(a+)+$, and every four more characters multiplied the count by sixteen. The extra + outside the group is easy to type and hard to spot, but patterns of this family have taken real sites down: in 2016 Stack Overflow was unavailable for 34 minutes after a trim pattern of the \s+$ kind met a post with about 20,000 consecutive whitespace characters.

This lesson names the four shapes behind catastrophic backtrackingcatastrophic backtracking: What happens when a backtracking engine meets a pattern that can split one text in many ways and every way fails: it tries them all before it gives up, so the work grows exponentially or polynomially with the text's length., shows how their work grows with the input, tells that incident from its postmortem, and gives you a safe way to reproduce the problem and a static check that catches most of them. The rewrites that turn a weak pattern into a fast one belong to the lesson on writing fast regexes.

The four shapes of catastrophic backtracking

Every catastrophic case this lesson shows is one of four shapes a backtracking engine cannot escape without trying every option in turn:

• Nested quantifiersnested quantifier: A quantifier on a group whose body holds another quantifier at its top level, such as the inner + inside the outer + of (a+)+. When nothing in the body fixes where one round ends and the next begins, the outer repetition can split a run many ways: the shape of exponential backtracking., where a quantifierquantifier: The part of a pattern that says how many times the atom before it may repeat: * for zero or more, + for one or more, ? for zero or one, or a count in braces such as {2,5}. More in “Repetition with *, +, ? and {m,n}” contains another: (a+)+, (?:\w+)*, (\w+\s?)+.
• Overlapping alternativesoverlapping alternatives: Alternatives of a repeated group that can read the same text in more than one way, as in (a|aa)+, where aa is either one aa or two a. Each stretch that can be read two ways doubles the number of splits a backtracking engine may have to try. inside a repeated group, where the branches can split the same text more than one way: (a|aa)+, (in|put|input)+ (an input is also in then put).
• Adjacent overlapping quantifiers, where two consecutive repetitions want the same characters: .*.*=, \d+\d+, .*(?:.*=.*).
• End-anchored runs with no left anchor, where a quantified class is followed by $ and the engine tries it from every start position: \s+$, [-A-Za-z0-9]+$.

The first three send the engine into a tree of splits. On the pattern ^(a+)+$, every a character in the subject can belong to the current run of the outer + or start a new one, so the number of ways to split a run of a characters doubles each time the run grows by one. The subject aaa! has four splits; aaaaa! has sixteen; aaaaaaaaaaaaaaaaaa! (18 a characters and the one !) more than 130,000. Each split ends at the same !, the engine does not know that ahead of time, so it tries every one of them.

r"""How two of the four shapes grow as the input grows, counted by PCRE2 10.49 itself.

The subject modifier find_limits_noheap makes pcre2test run the match again and again, lowering the match limit
until the attempt stops completing, and print the smallest value that still works. The match limit counts the turns
PCRE2 takes round its matching loop, so the printed number is the work the attempt needed: a deterministic count, not
a duration. The subject \[a]{N} is pcre2test's way of writing N copies of the character a; this run keeps N at 18 or
below, which holds every attempt well under a second on this machine, so two runs are byte-identical.

Shapes 3 and 4 (adjacent overlapping quantifiers and an end-anchored run) count polynomially in a trace, but PCRE2's
own optimisations keep them cheap at these small sizes: a static checker tells them apart from a safe pattern instead,
which the next example shows.
"""

from pcre2_session import run

run(r"""
# shape 1: a nested quantifier (an inner + inside an outer +)
/^(a+)+$/
    \[a]{10}x\=find_limits_noheap
    \[a]{14}x\=find_limits_noheap
    \[a]{18}x\=find_limits_noheap

# shape 2: overlapping alternatives (a is also a prefix of aa, so a run can be split two ways)
/^(a|aa)+$/
    \[a]{10}x\=find_limits_noheap
    \[a]{14}x\=find_limits_noheap
    \[a]{18}x\=find_limits_noheap

# a safe pattern on the same inputs, for contrast
/^a+$/
    \[a]{10}x\=find_limits_noheap
    \[a]{18}x\=find_limits_noheap
""")

$ pcre2test -q patterns.txt   (PCRE2 10.49)
# shape 1: a nested quantifier (an inner + inside an outer +)
/^(a+)+$/
    \[a]{10}x\=find_limits_noheap
Minimum match limit = 2560
Minimum depth limit = 23
No match
    \[a]{14}x\=find_limits_noheap
Minimum match limit = 40960
Minimum depth limit = 31
No match
    \[a]{18}x\=find_limits_noheap
Minimum match limit = 655360
Minimum depth limit = 39
No match

# shape 2: overlapping alternatives (a is also a prefix of aa, so a run can be split two ways)
/^(a|aa)+$/
    \[a]{10}x\=find_limits_noheap
Minimum match limit = 697
Minimum depth limit = 23
No match
    \[a]{14}x\=find_limits_noheap
Minimum match limit = 4789
Minimum depth limit = 31
No match
    \[a]{18}x\=find_limits_noheap
Minimum match limit = 32836
Minimum depth limit = 39
No match

# a safe pattern on the same inputs, for contrast
/^a+$/
    \[a]{10}x\=find_limits_noheap
Minimum match limit = 2
Minimum depth limit = 2
No match
    \[a]{18}x\=find_limits_noheap
Minimum match limit = 2
Minimum depth limit = 2
No match

The counts the engine itself prints are the proof. The match limitmatch limit: A cap on the steps of the matching loop of PCRE2 that turns a runaway match into an error instead of an endless run. pcre2test reports error -47 when it is reached, and PHP returns false. More in “Regex in PCRE2, PHP and Perl” caps the turns of PCRE2’s matching loop (pcre2api), and pcre2test lowers that cap until the attempt stops completing, so the number is a count of work, not a duration (pcre2test, “Finding minimum limits”). The nested shape ^(a+)+$ costs 2,560 turns for ten a characters, 40,960 for fourteen, and 655,360 for eighteen: multiplied by sixteen every time the subject grows by four. The overlapping-alternatives shape ^(a|aa)+$ grows exponentially too, at a lower rate: 697 turns at ten, 4,789 at fourteen and 32,836 at eighteen, about seven times more for every four characters. The safe pattern ^a+$ costs 2 turns on either input, because its + has nothing to backtrack to.

Exponential and polynomial, told apart by growth

The four shapes split into two families, told apart by how fast the count grows as the input grows. In an exponential shape, every extra character multiplies the work by a fixed factor: the nested shape above doubles it, so a twenty-character subject already needs millions of turns and a forty-character one trillions. In a polynomialpolynomial backtracking: A backtracking cost that grows as a polynomial of the input length, such as the n^2 of \s+$ or the n^3 of .*(?:.*=.*). It stays small on short inputs and grows large on long ones: at n^2, ten times the length costs a hundred times the work. shape of degree d, the work grows roughly as the input length raised to the d-th power. A degree-two case on 20,000 characters needs about 200 million checks, which is slow but finishes; a degree-three case on the same input needs about 20,000 times as many, which is hours of work at a hundred million checks a second.

Drag n to compare the two families. At n = 30 the O(n²) bar is about nine microseconds and the O(2ⁿ) bar about ten seconds, already past the one-second line; at n = 40 the O(2ⁿ) bar passes three hours while the O(n²) bar stays under a millisecond. Every ten more characters multiply the exponential bar by about a thousand.

A static checker names the family from the pattern alone. recheck returns the growth class for each pattern below:

"""What two static ReDoS checkers say about the four shapes and about a safe pattern.

recheck 4.5.0 reads a pattern and decides, from its structure alone, whether a backtracking engine can need more
than linear time on some input, and if so how that time grows: exponential, or polynomial with its degree. The
automaton checker always returns the same verdict for the same pattern, so this run is deterministic. The second
block runs ESLint 10.13.0 with eslint-plugin-regexp 3.3.1's recommended rules on the same patterns written as
JavaScript literals, so the two checkers can be compared on the same page. Each checker reports the rule name only;
the pattern it builds to confirm a verdict is never printed.
"""

from redos_session import recheck, lint

recheck([
    r"^(a+)+$",         # shape 1: nested quantifier
    r"^(a|aa)+$",       # shape 2: overlapping alternatives
    r".*(?:.*=.*)",     # shape 3: adjacent overlapping quantifiers
    r"\s+$",            # shape 4: an end-anchored run (the Stack Overflow trim)
    r"(\w+)\1",         # a backreference: the automaton checker cannot decide it
    r"^a+$",            # a safe pattern of the same letter, for contrast
])

print()

lint(r"""
const nested = /^(a+)+$/;
const overlap = /^(a|aa)+$/;
const adjacent = /.*(?:.*=.*)/;
const trim = /\s+$/;
const backref = /(\w+)\1/;
const safe = /^a+$/;
""")

print()

# the recommended set alone does not flag the Stack Overflow trim pattern; the no-super-linear-move rule does, but
# it is NOT in the recommended set, so a project that only turns the recommended set on has to add it by hand. The
# same six patterns again, with that rule added.
lint(r"""
const nested = /^(a+)+$/;
const overlap = /^(a|aa)+$/;
const adjacent = /.*(?:.*=.*)/;
const trim = /\s+$/;
const backref = /(\w+)\1/;
const safe = /^a+$/;
""", extra=["regexp/no-super-linear-move"])

$ recheck 4.5.0, automaton checker
/^(a+)+$/      vulnerable  exponential
/^(a|aa)+$/    vulnerable  exponential
/.*(?:.*=.*)/  vulnerable  polynomial, degree 3
/\s+$/         vulnerable  polynomial, degree 2
/(\w+)\1/      unknown     not decided (back-reference)
/^a+$/         safe        linear

$ eslint 10.13.0 with eslint-plugin-regexp 3.3.1, recommended rules
  1 | const nested = /^(a+)+$/;
  2 | const overlap = /^(a|aa)+$/;
  3 | const adjacent = /.*(?:.*=.*)/;
  4 | const trim = /\s+$/;
  5 | const backref = /(\w+)\1/;
  6 | const safe = /^a+$/;
line 1, column 19: regexp/no-super-linear-backtracking
line 1, column 19: regexp/no-misleading-capturing-group
line 3, column 19: regexp/no-super-linear-backtracking
line 3, column 21: regexp/no-useless-non-capturing-group
line 3, column 24: regexp/optimal-quantifier-concatenation
5 problems

$ eslint 10.13.0 with eslint-plugin-regexp 3.3.1, recommended rules + regexp/no-super-linear-move
  1 | const nested = /^(a+)+$/;
  2 | const overlap = /^(a|aa)+$/;
  3 | const adjacent = /.*(?:.*=.*)/;
  4 | const trim = /\s+$/;
  5 | const backref = /(\w+)\1/;
  6 | const safe = /^a+$/;
line 1, column 19: regexp/no-super-linear-backtracking
line 1, column 19: regexp/no-misleading-capturing-group
line 3, column 19: regexp/no-super-linear-backtracking
line 3, column 19: regexp/no-super-linear-move
line 3, column 21: regexp/no-useless-non-capturing-group
line 3, column 24: regexp/no-super-linear-move
line 3, column 24: regexp/optimal-quantifier-concatenation
line 4, column 15: regexp/no-super-linear-move
line 5, column 19: regexp/no-super-linear-move
9 problems

^(a+)+$ and ^(a|aa)+$ are exponential; \s+$, the Stack Overflow trim pattern, is polynomial of degree 2; and .*(?:.*=.*), two runs that both take any character, is polynomial of degree 3. The pattern ^a+$ without the outer repetition is safe and linear.

Why one slow match is a denial of service

Node.js runs on one thread per worker. A .test() call is a synchronous operation, so while it runs no other callback on that worker can run: not another request, not a timer, not an I/O completion, not a promise microtask. The example below schedules a timer with zero delay, then runs a regex match on the same thread, and prints each event in the order it fired. The timer fires after the match returns, no matter how long the match takes.

// A Node.js server runs on a single thread per worker, so one slow regex match blocks every other callback waiting
// on that worker: incoming requests, I/O completions, timers. This program schedules a timer with no delay, then
// runs a regex match on the same thread, and prints every event in the order it fired. The timer never fires
// during the match: there is no second thread for it to run on. The match below takes milliseconds on this short
// input; in a worst case the same shape can hold the thread for seconds, and every other request has to wait.

console.log("1  scheduling a 0 ms timer");
setTimeout(() => console.log("4  timer fires: the match had finished first"), 0);

console.log("2  starting the match");
new RegExp("^(a+)+$").test("a".repeat(20) + "!");
console.log("3  match finished");

1  scheduling a 0 ms timer
2  starting the match
3  match finished
4  timer fires: the match had finished first

For a short match that lasts milliseconds this is harmless. The ReDoSReDoS: A denial-of-service weakness caused by a regular-expression match that runs for a very long time on a worst-case input, blocking the thread it runs on. OWASP calls it Regular expression Denial of Service and CWE-1333 lists it as inefficient regular-expression complexity. problem is that a pattern of the four shapes above, on an input chosen to meet the worst case, can hold the thread for seconds or minutes. OWASP’s community page describes the attack class, and CWE-1333 names the weakness “Inefficient Regular Expression Complexity”: a pattern whose worst case a request can trigger when the service accepts the input the pattern runs on. One slow match on one request becomes an outage when the request pool has no spare worker left.

The best-known public incident shows the whole chain, from one slow match to a site that no visitor can reach.

Stack Overflow, in 2016. A malformed post held roughly 20,000 consecutive whitespace characters, and it sat in the home page list, so a trim pattern ran on it at every home page view. The pattern’s right half was [\s\u200c]+$; the postmortem names \s+$ as the simpler form of the same problem. Twenty thousand spaces followed by a character that is not a space make the engine try \s+$ from every one of them, which the postmortem’s arithmetic puts at 199,990,000 checks. The home page was also the load balancer’s health check, so once it answered too slowly the balancer took the web servers out of rotation. The site was unavailable for 34 minutes, and the regex was replaced with a substring function.

What removes the wall. A limit or a rewrite keeps a backtracking engine in check; an engine that never backtracks has no such wall. Go’s regexp and Rust’s regex build an automaton from the pattern and read the subject once: Go’s documentation promises time linear in the size of the input, and Rust’s bounds the work by the pattern’s size times the input’s. The lesson on untrusted patterns and input shows when a service should move its patterns to such an engine.

Reproducing it safely on your own pattern

Suspecting a pattern of yours is not the same as proving it. Running it in a shell with your worst guess at an input can hang the shell for minutes, or hours, with no answer. The honest way is to run the match under a limit, so the attempt either returns a number or ends with “I gave up”. Three limits do that job on the engines this track covers:

• V8, the engine inside Node.js, has an experimental flag, --enable-experimental-regexp-engine-on-excessive-backtracks, that moves a match to its non-backtracking engine once it has backtracked too often: 50,000 times by default, a number --regexp-backtracks-before-fallback changes. Node passes such V8 options on from its own command line. The match then finishes in time proportional to the input, for a pattern with no backreference, no lookaround, no large counted repetition and neither the i nor the u flag, the cases the V8 post lists.
• PCRE2 reads a cap on its matching loop ((*LIMIT_MATCH=n) in the pattern, or an API option), and pcre2test can search for the minimum cap under which an attempt still completes, as the first example of this lesson did.
• Python’s third-party regex module takes timeout= on each call; after that many seconds a TimeoutError is raised instead of an answer. Python’s own re has no match timeout.

The example below runs ^(a+)+$ on your own 32 a characters followed by a stray ! under two settings of V8. The first setting leaves the backtracking engine alone and the session stops the program after one second; the second turns the experimental fallback on and the engine prints false at once.

r"""Reproduce a slow match safely on your own pattern, under a Node.js V8 flag that stops it.

The first run has no flag: V8 is still backtracking after one second, and the session stops it. The second run adds
--enable-experimental-regexp-engine-on-excessive-backtracks, which moves the match to a non-backtracking engine once
the backtracking engine passes a threshold (--regexp-backtracks-before-fallback sets the threshold; the default is
50,000). The engine prints false at once, and the limit is never reached. Change PATTERN to your own and INPUT to a
short case that cannot match, and press Run.
"""

from v8_session import run

# plain Node.js: the match is still running after the limit, so the session stops it
run([], r"""
const PATTERN = /^(a+)+$/;
const INPUT = "a".repeat(32) + "!";
console.log(PATTERN.test(INPUT));
""", limit=1)

print()

# with the experimental fallback flag: the engine moves the match to a non-backtracking engine and prints false
run(["--enable-experimental-regexp-engine-on-excessive-backtracks"], r"""
const PATTERN = /^(a+)+$/;
const INPUT = "a".repeat(32) + "!";
console.log(PATTERN.test(INPUT));
""", limit=1)

$ node probe.mjs
(stopped after 1 s: the program was still running)

$ node --enable-experimental-regexp-engine-on-excessive-backtracks probe.mjs
false

Change PATTERN and INPUT to the pattern and the shortest failing text that match your case. The limit protects your machine, and the second run tells you what the real answer would be. For patterns that run on PCRE2 or in a Python service, the equivalent idea is a match limit or a timeout on each call.

Checking a pattern before it ships

A limit protects a live service and tells you whether a match is slow. A static checker tells you whether a pattern has one of the four shapes without running it, so the finding fails the build on the weak pattern and passes on the fix. Two ReDoS checkersReDoS checker: A static analyser that reads a regex pattern and reports whether a backtracking engine can need more than linear time on some input, and if so with what growth class. recheck and the eslint-plugin-regexp rules no-super-linear-backtracking and no-super-linear-move are the checkers this track uses. are widely used:

• recheck reads a pattern and returns a verdict with a growth class (exponential, or polynomial with its degree), using an automaton checker that always returns the same answer for the same pattern.
• eslint-plugin-regexp runs inside ESLint and reports every regex literal in a JavaScript source. Two of its rules cover the shapes of this lesson: no-super-linear-backtracking for the exponential and some polynomial cases, and no-super-linear-move for a run that a pattern with no start anchor tries again from every position, as \s+$ does.

Each checker has gaps. The example above runs both on the four shapes, and the ESLint blocks show the gaps directly: the recommended ruleset includes no-super-linear-backtracking, so the plugin flags ^(a+)+$ and .*(?:.*=.*) but reports nothing on ^(a|aa)+$ (recheck calls it exponential) and nothing on \s+$ (recheck calls it polynomial of degree 2). Adding regexp/no-super-linear-move to the project’s rules catches \s+$, as the second ESLint block shows, and still reports nothing on ^(a|aa)+$. The backreferencesbackreference: A pattern element that names a previously captured group and matches exactly the text that group holds at that moment, written \1 for the first group, \k<name> or (?P=name) for a named one depending on the flavour. More in “Backreferences: matching the same text again” that (\w+)\1 relies on put the pattern outside what recheck’s automaton checker can decide: it returns unknown, which the lesson’s run reports as not decided. The added rule does report it, for the \w+ it tries from every start.

The reader can draw two rules from the table. One checker is not enough: a build that only runs the ESLint recommended set misses \s+$ and (\w+)\1, and neither ESLint rule set reports ^(a|aa)+$, which recheck calls exponential. And a verdict is only as useful as the checker’s model: a pattern with a backreference needs a different kind of test, which the lesson on reviewing regexes you did not write covers.

Practise

Rewriting a weak pattern is the subject of the lesson on writing fast regexes. Before you rewrite, you have to be able to see the shape in the first place, which is what the exercise asks for: a small structural check that reports a group repeated by + or * whose body holds another + or * at its top level, or two alternatives that start with the same character. It is a rough screen: it flags some safe patterns and does not look for the end-anchored run, which is why the two checkers above stay in the build beside it.

// Flag a pattern that carries a nested quantifier (see prompt.md for the exact rule).
//
// The starter always returns false, so the "weak patterns" tests fail at once. Walk the pattern one atom at a time:
// read an escape as one unit, a character class as one unit, and a group as a pair of parentheses with a body of
// its own. Then, for every group followed by + or *, ask whether its body holds a + or * at its top level, or two
// top-level alternatives that start with the same character.

/**
 * @param {string} pattern
 * @returns {boolean}
 */
export function hasNestedQuantifier(pattern) {
  return false;
}

import { test, assert } from 'mysmartcopilot:test';
import { hasNestedQuantifier } from './flag.mjs';

const WEAK = [
  '^(a+)+$',
  '^(a|aa)+$',
  '^(\\w+)*$',
  '^(.*.*)+$',
  '^(\\d|\\d\\d)+$',
  '^([a)]+)+$',
  '^([\\)a]+)+$',
  '^([\\]a]+)+$',
  '^(?<n>a+)+$',
  '^((?:ab)+)+$',
];

const SAFE = [
  '^a+$',
  '^(ab)+$',
  '^[a-z]+$',
  '(\\w+)',
  '((?:ab){3})+',
  '\\d+',
  '[a+]+',
  '(a+)?',
  '^[(]a+[)]$',
  '^\\(a+\\)+$',
  '^[a\\]]+$',
  '^([)]a)+$',
];

test('weak patterns are flagged', () => {
  for (const pattern of WEAK) {
    assert.equal(hasNestedQuantifier(pattern), true, `${pattern} should be flagged`);
  }
});

test('safe patterns are not flagged', () => {
  for (const pattern of SAFE) {
    assert.equal(hasNestedQuantifier(pattern), false, `${pattern} should not be flagged`);
  }
});

test('a + inside a character class is not a quantifier', () => {
  assert.equal(hasNestedQuantifier('[a+]+'), false);
});

test('an escaped + is not a quantifier', () => {
  assert.equal(hasNestedQuantifier('(\\+a)+'), false);
});

"""Flag a pattern that carries a nested quantifier (see prompt.md for the exact rule).

The starter always returns False, so the "weak patterns" tests fail at once. Walk the pattern one atom at a time:
read an escape as one unit, a character class as one unit, and a group as a pair of parentheses with a body of its
own. Then, for every group followed by + or *, ask whether its body holds a + or * at its top level, or two
top-level alternatives that start with the same character.
"""


def has_nested_quantifier(pattern: str) -> bool:
    """Return True when a group repeated by + or * holds another + or *, or two alternatives with the same start."""
    return False

"""Sample tests for flag.py: patterns that should be flagged, and patterns that should pass."""

from flag import has_nested_quantifier

WEAK = [
    r"^(a+)+$",
    r"^(a|aa)+$",
    r"^(\w+)*$",
    r"^(.*.*)+$",
    r"^(\d|\d\d)+$",
    r"^([a)]+)+$",
    r"^([\)a]+)+$",
    r"^([\]a]+)+$",
    r"^(?<n>a+)+$",
    r"^((?:ab)+)+$",
]

SAFE = [
    r"^a+$",
    r"^(ab)+$",
    r"^[a-z]+$",
    r"(\w+)",
    r"((?:ab){3})+",
    r"\d+",
    r"[a+]+",
    r"(a+)?",
    r"^[(]a+[)]$",
    r"^\(a+\)+$",
    r"^[a\]]+$",
    r"^([)]a)+$",
]


def test_weak_patterns_are_flagged():
    for pattern in WEAK:
        assert has_nested_quantifier(pattern) is True, f"{pattern} should be flagged"


def test_safe_patterns_are_not_flagged():
    for pattern in SAFE:
        assert has_nested_quantifier(pattern) is False, f"{pattern} should not be flagged"


def test_class_with_plus_is_not_a_quantifier():
    # Inside a character class, + is a literal character.
    assert has_nested_quantifier(r"[a+]+") is False


def test_escaped_plus_is_not_a_quantifier():
    # A backslash before + makes it a literal character.
    assert has_nested_quantifier(r"(\+a)+") is False

Now put the ideas of this lesson to the test. The check below picks the concept you handle least well first, with a reason on every choice at the moment you choose it:

Interview questions

Warm-up: what are the four shapes that drive catastrophic backtracking, and what do all four have in common?

A backtracking engine goes catastrophic when a pattern lets one subject be split into many ways, and the engine does not know in advance that each will fail. The four shapes are a nested quantifier such as (a+)+, overlapping alternatives inside a repetition such as (a|aa)+, adjacent repetitions that want the same characters such as .*.*=.* or \d+\d+, and an end-anchored run tried from every start, such as \s+$. All four have the same cause: there is more than one way to assign the subject to the pattern’s atoms, every assignment reaches the same failure point, and every assignment has to be tried. The first two grow exponentially with the input; the last two grow polynomially. A pattern of any of the four shapes is a weakness listed by OWASP’s ReDoS page and CWE-1333, and a worst-case input makes its service slow or unresponsive.

Two deeper questions go further: one on triaging a mix of flagged patterns before they merge, and one on diagnosing a slow endpoint on a service you own without hanging your laptop. Choose your opening move for each, then see where its page begins:

Key takeaways

• Catastrophic backtracking comes in four shapes: nested quantifiers, overlapping alternatives inside a repetition, adjacent repetitions that want the same characters, and an end-anchored run tried from every start.
• The shapes split by growth: nested and overlapping grow exponentially with the input length, adjacent and end-anchored grow polynomially; a static checker names the family from the pattern alone.
• One slow match blocks the whole worker on a Node.js server, so a worst-case input on any single request can starve every other request on that worker and turn one bad pattern into a denial of service.
• The 2016 Stack Overflow outage ran a trim pattern on about 20,000 whitespace characters at every home page view, failed the load balancer’s health check, kept the site unavailable for 34 minutes, and was fixed by replacing the regex with a substring function; an engine that never backtracks, such as Go’s regexp or Rust’s regex, has no such wall.
• Reproduce a suspected pattern under a limit, not a stopwatch: V8’s experimental fallback flag, PCRE2’s match limit, or a per-call timeout in Python’s regex module.
• One ReDoS checker is not enough: recheck leaves a backreference undecided, ESLint’s recommended rules miss \s+$, and neither ESLint rule set reports ^(a|aa)+$.