State Machines and Regular Expressions

A turnstile, a traffic light and Lantern's query lexer from Chapter 13 are the same kind of machine: a fixed set of states and a rule for which state comes next on each input. A regular expression describes that kind of machine, and run as a machine it checks any text in one pass, one step per character, whatever the pattern.

Most regex engines in daily use do not run it that way. They search by trial and error, and on the wrong pattern the number of trials doubles with every character. One pattern typed into Lantern's staff search box can pin a search worker for minutes, and the cost does not come from the text being long. It comes from the engine underneath the pattern.

Finite State Machines

A finite state machine has a set of states, one start state, some accepting states and a transition for each input symbol from each state. It reads its input one symbol at a time and follows the arrow that symbol selects. Its only memory is which state it is in. When the input ends, it answers yes if it stopped in an accepting state and no otherwise.

A turnstile has two states. A coin moves it from locked to unlocked, a push moves it back, and a push on a locked turnstile or a coin on an unlocked one changes nothing. An order in a shop has a handful of states, from placed to paid to shipped. Lantern's lexer in Chapter 13 has four: between tokens, inside a word, inside a number and inside a phrase. It moves between them on each character it reads, and that is why lexing a query is linear in the query's length.

A Regex Is a Machine

A regular expression is built from three operations: one thing after another, a choice between alternatives and repetition. In 1968 Ken Thompson showed that each operation builds a small piece of machine, and that the pieces snap together into one machine for the whole pattern. A pattern for "one or more a's, then the end of the text" becomes three states: a start, a state for being inside a run of a's and an accepting state for having reached the end.

The machine can be run by tracking every state it could be in at once. Read a character, move every live state along its arrows and keep the set of states that survive. The set can never hold more states than the machine has, so each character costs at most the size of the pattern, and a whole match costs the length of the text times the size of the pattern. That bound holds for every pattern and every input. When the set of live states empties, the match has failed, and the machine knows it at once.

Backtracking Engines

The engines in Python's re module, Perl, PCRE, Java, JavaScript and .NET's default mode work differently. They try one path at a time. When the pattern offers a choice, such as how many characters a repetition should take, the engine picks one option, carries on and on failure returns to the last choice point and tries the next option. This is the backtracking search of Chapter 9, run by the regex engine on your behalf.

They are built this way for a reason. Backtracking makes features easy that a finite machine cannot provide at all: a backreference, which demands that a later part of the text repeat an earlier captured part, and lookaround, which checks what comes before or after a position without consuming it. On ordinary input the first path usually succeeds and a backtracking engine is fast. The price is the worst case. When every path fails, the engine must try every path, and the number of paths can grow exponentially with the input.

Catastrophic Backtracking

The pattern (a+)+$ asks for one or more groups, each of one or more a's, followed by the end of the text. Give it a run of a's followed by an exclamation mark. Before it can report failure, a backtracking engine tries every way to split the run between the inner repetition and the outer one. Each gap between two a's can be a cut or not, so every extra a doubles the number of splits: 8 ways for four a's, about 8 million for twenty-four. Every one of them fails at the exclamation mark.

import re, time

for n in (24, 25, 26, 27):
    text = "a" * n + "!"
    t = time.perf_counter()
    re.match(r"(a+)+$", text)          # 0.57 s, 1.13 s, 2.28 s, 4.57 s
    print(n, time.perf_counter() - t)

re.match(r"a+$", "a" * 27 + "!")          # under a microsecond, once compiled

The loop above times the nested pattern on runs of 24 to 27 a's, each followed by an exclamation mark, and the last line runs the plain pattern "one or more a's, then the end" on the longest input. On the Python 3.15 release candidate on an Apple M1 Max laptop, 24 a's took 0.57 seconds to fail. Each extra character doubled it: 1.13 seconds, 2.28, 4.57. At that rate 30 a's take about 37 seconds, and a run on the same machine while it was busy with other work measured 70. The plain pattern accepts exactly the same strings and fails in under a microsecond, because it can only give characters back one at a time.

The Frozen Search Worker

Lantern lets library staff search titles by regex. A cataloguer looking for titles made only of words and spaces types ^(\w+\s?)*$: any number of groups, each a word followed by an optional space. It looks harmless, and on every title that matches it is fast. Every title that ends in punctuation fails, and fails slowly, because a word can be cut into smaller words in every possible way when the space after each piece is optional.

Measured on the same machine, "Do Androids Dream of Electric Sheep?", 36 characters with a question mark at the end, took about two and a half seconds to fail. Adding one letter to the last word doubled it to 5 seconds, and a second letter to 10. Ten letters added to the original title would take over 40 minutes. The same title without its question mark matches in about a microsecond. With 2 million records in the catalogue, the cataloguer's search does not stop at the first slow title. It pays that price on every long title that ends in punctuation.

While it runs, the worker process sits at 100% of one core. Searches queued behind it wait, then time out. The HTTP timeout frees the caller, but not the CPU: the match keeps running until it finishes, and Python's re has no match timeout of its own. The famous public case is Cloudflare on 2 July 2019. A new firewall rule containing the fragment .*(?:.*=.*) drove the processors that serve Cloudflare's HTTP traffic to nearly 100% across its network, and the outage lasted 27 minutes. That blow-up was polynomial rather than exponential: timed on Python 3.15 with a semicolon required after it, the reduced fragment took 124 milliseconds to fail on 1,000 characters and nearly a second on 2,000, eight times the time for twice the text. Polynomial was enough. On 20 July 2016 Stack Overflow was down for 34 minutes when a whitespace-trimming pattern met a post with about 20,000 consecutive spaces and did about 200 million character checks on it, a quadratic cost.

Engines With a Guarantee

RE2 from Google, Go's regexp package and Rust's regex crate run the machine instead of an open-ended backtracking search. Each guarantees time linear in the input for a given pattern, and Rust's documentation states the bound as the pattern size times the text length. They give up the features that need backtracking: backreferences and most lookaround are not available at all. Cloudflare's post-mortem committed to moving its firewall to RE2 or Rust's engine for that guarantee.

Any service that runs a pattern it did not write, or its own pattern on text it did not write, is exposed. A firewall, a log pipeline, a form validator and a search box all qualify. The attack is called ReDoS, regular-expression denial of service, and it needs no volume: one crafted string pins one core. The defence is the engine and a limit on input length, not a careful reviewer. Where a backtracking engine stays, Python's re has offered two tools since 3.11: possessive quantifiers and atomic groups, which refuse to give characters back once taken. Rewritten either way, or plainly as a word followed by groups of one space and a word, the cataloguer's pattern rejects the 36-character title in about a microsecond.