Regex with untrusted patterns and input

A search box that compiles whatever a visitor types is running their code on your server. Give your own box, backed by Node’s default engine, the pattern ^(a+)+$ and a line of 34 letters a followed by a !, which it cannot match, and the match does not finish: it is still running after three seconds, on the one thread that serves every other request.

Untrusted regex reaches your code two ways: a user supplies the patternuntrusted pattern: A regular expression that comes from outside your team, such as one a visitor types into a search or filter box. It must be treated as code, because the wrong pattern can make a backtracking engine run for a very long time., or a user supplies the input your own pattern runs on. This lesson designs one search feature that is safe against both. You will treat a user pattern as code, choose between a linear engine, a hard deadline, engine limits and an input cap, escape text that was never meant to be a pattern, and keep the engine patched so its own bugs do not become yours.

Two ways untrusted regex reaches your code

The first question to ask of any regex that touches the outside world is which part came from outside. There are only two answers, and they need different defences. Either the pattern is untrusted, as in a search box, a filter builder or a product that lets customers write their own alert rules; or the pattern is yours and the text is untrusted, as in a form field, a request header, an uploaded file or a log line. The table names each case and the defence that fits it:

Both cases share one failure: a slow match that blocks the thread, a denial of service from a regex, which catastrophic backtracking and ReDoS covers in full. The defences below each remove or cap that risk in one of the two cases, and a real feature combines several.

A user’s pattern is code you agreed to run

When a visitor types a pattern, you are not reading data; you are accepting a tiny program and promising to run it. Most such programs are harmless, but you cannot assume so, because one pattern is enough. The program below hands a pattern a visitor might type, ^(a+)+$, to Node’s default engine on a line of 34 letters a and a final !. A linear engine would answer false at once; the default engine does not answer at all before the session stops it:

"""A user types the pattern ^(a+)+$ into a search box, and someone later searches a
line of 34 letters a followed by one that cannot match. On Node's default engine
the match keeps going; this session stops the program after three seconds and says
so, instead of printing a time that depends on the computer."""

from v8_session import run

run([], r'''
const userPattern = /^(a+)+$/;          // a pattern a visitor typed
const line = "a".repeat(34) + "!";       // a line it cannot match
console.log(userPattern.test(line));     // never reaches here in time
''', limit=3)

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

The output is the whole point: the match is still running when the session ends it, because on a backtrackingbacktracking: How a backtracking engine reacts to a failure: it returns to its most recent choice point, restores the text position it had there, and tries the next alternative. More in “How an engine finds a match, step by step” engine this shape tries a number of ways to split the run that grows explosively with the line length. Catastrophic backtracking and ReDoS names the four shapes that do this; here it is enough to know that a user can type one, so a user pattern needs a bound on how long it may run before you let it near a request thread.

A linear engine takes the risk away

The cleanest fix for an untrusted pattern is an engine that no pattern can push past linear time. A RE2RE2: A regular-expression library and syntax from Google whose primary guarantees include match time linear in the input, which is why it leaves out backreferences and lookaround. Go's regexp package accepts its syntax. More in “Regex in Go, RE2 and re2js”-style engine follows every path through the pattern at once, so its match time is linear in the length of the text whatever the pattern does. Go’s regexp package is one, and it checks every pattern when it compiles it. The program below accepts a few filters a visitor might save, refuses the two that need features RE2 does not have, and then runs the nested quantifier ^(a+)+$ on a line of 100,000 letters a and a final !, which it cannot match:

// A search service lets visitors save their own filter patterns. Go's regexp
// accepts only RE2 syntax, so a pattern that would need backtracking is refused
// when the filter is saved, not while a request runs. The refusal is the guard.
package main

import (
	"fmt"
	"regexp"
	"strings"
)

func saveFilter(p string) {
	if _, err := regexp.Compile(p); err != nil {
		fmt.Printf("refused   %-14s %v\n", p, err)
		return
	}
	fmt.Printf("accepted  %-14s compiles\n", p)
}

func main() {
	// Filters a visitor might type. Two of them need features RE2 does not have.
	for _, p := range []string{
		`error|warn`,  // plain alternation
		`\b\d{3,5}\b`, // a bounded number
		`(\w+) \1`,    // a backreference
		`(?=.*fail)`,  // a lookahead
		`^(a+)+$`,     // a nested quantifier
	} {
		saveFilter(p)
	}

	// A saved filter run on a long line that cannot match. RE2 answers within a
	// bound it fixes before it starts, so no input can make this search slow.
	re := regexp.MustCompile(`^(a+)+$`)
	line := strings.Repeat("a", 100000) + "!"
	fmt.Printf("match on %d characters: %v\n", len(line), re.MatchString(line))
}

accepted  error|warn     compiles
accepted  \b\d{3,5}\b    compiles
refused   (\w+) \1       error parsing regexp: invalid escape sequence: `\1`
refused   (?=.*fail)     error parsing regexp: invalid or unsupported Perl syntax: `(?=`
accepted  ^(a+)+$        compiles
match on 100001 characters: false

Two filters are refused when they are saved, not while a request runs: the backreference (\w+) \1 with invalid escape sequence, and the lookahead (?=.*fail) with invalid or unsupported Perl syntax. The nested quantifier ^(a+)+$ compiles and answers false on 100,001 characters, because RE2 runs even that shape in linear timelinear-time matching: A guarantee that, for a fixed pattern, the time a match takes grows at most in proportion to the length of the text, whatever the text holds. Go's regexp gives it by following every path of the pattern at once. More in “Regex in Go, RE2 and re2js”. The cost is the two refusals: a non-backtracking enginenon-backtracking engine: A regex engine that matches without backtracking, so its run time stays proportional to the length of the input. .NET's RegexOptions.NonBacktracking is one; in exchange it refuses lookaround, backreferences, atomic and balancing groups, conditionals and the start anchor \G. More in “Regex in Java, .NET, Ruby and Rust” refuses a backreferencebackreference: 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”, and RE2 refuses a lookaroundlookaround: A family of zero-width assertions that test the text to one side of the current position without consuming it: lookahead looks forward and lookbehind looks back. A pattern can require or forbid what surrounds a match this way. More in “Lookahead: conditions without consuming text” as well, so a feature that needs one cannot use this engine. Backtracking engines versus automata engines explains why and covers re2js, a JavaScript port of RE2, and Regex in Java, .NET, Ruby and Rust covers Rust’s regex crate and .NET’s NonBacktracking option.

Read each platform’s own terms before you hand it visitor patterns, though. A linear engine’s time still grows with the size of the pattern as well as the text, so Rust’s documentation advises keeping patterns from outside short and setting a small limit on their compiled size. Microsoft says .NET’s NonBacktracking option and its match timeouts protect patterns your team wrote from expensive input and are no security boundary against hostile patterns; for searches typed by users it suggests a restricted search syntax or Regex.Escape instead of compiling what they typed.

V8 has an experimental linear engine too, reached through Node’s flags. The run below turns it on two ways: a fallback after too much backtracking, and the l flag, which runs a pattern on the linear engine from the start and refuses one it cannot run there:

"""V8 has an experimental linear-time engine, reached two ways through Node's V8
flags. These flags are experimental: the behaviour here is Node 24.21.0's, not a
promise about every release, so test it before you rely on it.

The first flag moves a match that backtracks too often onto the linear engine. The
second turns on the l flag, which runs a pattern on the linear engine from the
start and refuses one that cannot run there, such as a backreference."""

from v8_session import run

# Fall back to the linear engine after too many backtracks.
run(["--enable-experimental-regexp-engine-on-excessive-backtracks"], r'''
const line = "a".repeat(34) + "!";
console.log(/^(a+)+$/.test(line));
''', limit=3)

# The l flag: linear from the start, and a refusal for a backreference.
run(["--enable-experimental-regexp-engine"], r'''
const line = "a".repeat(34) + "!";
console.log(/^(a+)+$/l.test(line));
try {
  new RegExp("^(a+)\\1$", "l");
} catch (e) {
  console.log(e.name + ": " + e.message);
}
''', limit=3)

$ node --enable-experimental-regexp-engine-on-excessive-backtracks probe.mjs
false
$ node --enable-experimental-regexp-engine probe.mjs
false
SyntaxError: Invalid regular expression: /^(a+)\1$/l: Cannot be executed in linear time

The fallback flag answers false at once on the same shape that hung a moment ago, and the l flag does too; a backreference under l is refused with Cannot be executed in linear time. These are experimental flags, so test them on your own patterns and your own Node version before you rely on them rather than treating them as settled.

A hard deadline when the engine still backtracks

Sometimes you cannot change the engine: the feature needs lookaround, or the platform has no linear option. Then the next defence is a hard deadline. Run the match somewhere you can stop, and stop it when it passes a time limit, so a slow match cannot block the thread that serves other requests. In Node that place is a worker thread. The program runs a user pattern in a worker and terminates the worker at a deadline; it prints the outcome, never a measured time, because a real runaway would take far longer than the limit:

// A hard deadline when the engine can still backtrack: run the visitor's pattern
// in a worker thread, and stop the worker when it runs past its deadline. The main
// thread stays free to answer every other request. The outcome is printed, never a
// measured time, because a real runaway match would take far longer than this.
import { Worker, isMainThread, parentPort, workerData } from 'node:worker_threads';

if (!isMainThread) {
  // In the worker: compile and run the visitor's pattern. On a line it cannot
  // match this call does not return before the deadline.
  const re = new RegExp(workerData.pattern);
  parentPort.postMessage(re.test(workerData.line));
} else {
  const DEADLINE_MS = 200;
  const pattern = '^(a+)+$'; // a pattern a visitor typed
  const line = 'a'.repeat(42) + '!'; // a line it cannot match
  const worker = new Worker(new URL(import.meta.url), { workerData: { pattern, line } });
  const timer = setTimeout(() => {
    worker.terminate();
    console.log(`stopped after ${DEADLINE_MS} ms: the search ran past its deadline`);
  }, DEADLINE_MS);
  worker.on('message', (answer) => {
    clearTimeout(timer);
    console.log(`answered in time: ${answer}`);
  });
}

stopped after 200 ms: the search ran past its deadline

The worker is stopped and the main thread stays available. The MySmartCoPilot regex tester works the same way: it runs the visitor’s pattern in a Web Worker and stops it after 1.5 seconds, with a message that the pattern is too slow on that text.

Several engines offer a deadline without a worker. The third-party Python regex module takes a timeout= in seconds, which turns a runaway match into an error you can catch:

"""The third-party regex module for Python takes a timeout= in seconds: a match that
runs longer raises TimeoutError, which you can catch and turn into a clear reply. A
timeout fires only for the shapes that run long, and only when you set it, so it is
a backstop, not a reason to skip the other defences."""

from regex_session import regex

line = "a" * 34 + "!"  # a line neither pattern can match

# One shape runs long enough for the cap to fire.
try:
    print("(a|aa)+ :", regex.match(r"^(a|aa)+$", line, timeout=1.0))
except TimeoutError as error:
    print("(a|aa)+ : TimeoutError:", error)

# Another answers at once, well inside the same cap.
print("(a+)+   :", regex.match(r"^(a+)+$", line, timeout=1.0))
print("regex", regex.__version__)

(a|aa)+ : TimeoutError: regex timed out
(a+)+   : None
regex 2026.9.29

One shape raises TimeoutError; the other answers before the limit, so the cap never fires on it. That is the shape of a match timeoutmatch timeout: A limit on how long one matching call may run, after which the engine gives up with an error instead of an answer. Python's re has none; the third-party regex module takes timeout= in seconds. More in “Python regex techniques and the regex module” everywhere: .NET takes one on the constructor, and Microsoft lists it among the defences for untrusted input; Ruby has Regexp.timeout, which is nil by default. But a timeout only helps when it is set, and it fires only after the time is spent, so never promise that one will catch every slow pattern: it is a backstop, not a guarantee.

Engine limits that count the work, and a cap on the input

A deadline measures time; an engine limit counts steps, which is deterministic and does not depend on the machine’s load. PCRE2 caps the steps of its matching loop at a 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”, and the verb (*LIMIT_MATCH=n) at the start of a pattern lowers it. The run below first reports how many steps a worst-case line needs as the line grows, then shows a low cap turning a worst-case line into an error instead of a runaway:

"""PCRE2 counts the steps of its matching loop and stops at a limit instead of running
away. The subject modifier find_limits_noheap makes pcre2test report the smallest match
and depth limits a subject needs, and the verb (*LIMIT_MATCH=n) at the start of a pattern
lowers the cap, so a worst-case line fails as an error. Subjects are kept short on purpose:
\\[a]{8} stands for eight letters a, and the count climbs fast with the length of the line."""

from pcre2_session import run

run(r'''
# The match-loop steps a worst-case line needs, as the line grows.
/^(a+)+$/
    \[a]{8}!\=find_limits_noheap
    \[a]{12}!\=find_limits_noheap
    \[a]{16}!\=find_limits_noheap

# The same pattern with a low cap: a worst-case line ends as an error, not a runaway.
/(*LIMIT_MATCH=1000)^(a+)+$/
    \[a]{20}!
''')

$ pcre2test -q patterns.txt   (PCRE2 10.49)
# The match-loop steps a worst-case line needs, as the line grows.
/^(a+)+$/
    \[a]{8}!\=find_limits_noheap
Minimum match limit = 640
Minimum depth limit = 19
No match
    \[a]{12}!\=find_limits_noheap
Minimum match limit = 10240
Minimum depth limit = 27
No match
    \[a]{16}!\=find_limits_noheap
Minimum match limit = 163840
Minimum depth limit = 35
No match

# The same pattern with a low cap: a worst-case line ends as an error, not a runaway.
/(*LIMIT_MATCH=1000)^(a+)+$/
    \[a]{20}!
Failed: error -47: match limit exceeded

The minimum match limit climbs from 640 at eight letters to 10,240 at twelve and 163,840 at sixteen, sixteenfold for every four more letters, which is why a short worst-case line already shows the risk. With (*LIMIT_MATCH=1000) a line of twenty letters fails with error -47: match limit exceeded, a clear error rather than a hung thread. PHP wraps the same PCRE2 behind pcre.backtrack_limit, and reports it through a return value a caller must read carefully:

<?php
// PHP's PCRE caps backtracking at pcre.backtrack_limit. Past the cap, preg_match
// returns false (not 0), and preg_last_error_msg says why. A caller that reads only
// 0 or 1 cannot tell a non-match from a cap, so always check for false and the error.
ini_set('pcre.backtrack_limit', '1000');

$line = str_repeat('a', 20) . '!';
$result = preg_match('/^(a+)+$/', $line);
var_dump($result);
echo preg_last_error_msg(), "\n";

// A plain match on the same input still answers and reports no error.
$ok = preg_match('/^a+$/', str_repeat('a', 20));
var_dump($ok);
echo preg_last_error_msg(), "\n";

echo 'PCRE2 ', explode(' ', PCRE_VERSION)[0], "\n";

bool(false)
Backtrack limit exhausted
int(1)
No error
PCRE2 10.44

Past the limit, preg_match returns false, not 0, and preg_last_error_msg says Backtrack limit exhausted. A caller that reads only 0 or 1 cannot tell a stopped match from a clean no-match, so always check for false and the error. All of these cap the work; none of them caps the input. The cheapest guard of all is an input length capinput length cap: A limit on the length of the text, or pattern, a feature will accept, checked before matching begins, which shrinks the worst case of every pattern. A short input can still be slow on a backtracking engine, so a cap works beside a safe pattern or a deadline. checked before matching: OWASP’s input validation guidance is to bound the input’s length before matching, and to check on the server as well as in the browser, because a request can skip the browser. A cap shrinks the worst case for every pattern, but it cannot make a slow pattern fast: twenty letters were already enough to pass the 1,000-step cap above.

Escape text that is not a pattern, and keep engines patched

The second threat case, a user supplying text rather than a pattern, has its own defence. When a visitor types search text, you do not want it read as a pattern at all: a dot should be a dot and an asterisk an asterisk. Escapingtext escaping: Turning a piece of text into a pattern that matches it literally, by escaping every character that would otherwise be special, so that user search text is never read as regex syntax. the text returns a pattern that matches it literally. RegExp.escape does this in JavaScript, and the same text goes in both the browser and Node:

// A visitor types search text, not a pattern. RegExp.escape turns every character
// into one that matches itself, so the search finds that exact text and treats
// 1.5*(x) as six ordinary characters, not as a quantifier and a group.
const term = "1.5*(x)";
const escaped = RegExp.escape(term);
console.log(escaped);
const re = new RegExp(escaped);
console.log(re.test("y = 1.5*(x) + 2"));
console.log(re.test("y = 15xxx"));

\x31\.5\*\(x\)
true
false

import re

# A visitor types search text, not a pattern. re.escape makes every character match
# itself, so the search finds the exact text and never reads * or ( as syntax.
term = "1.5*(x) a-b"
escaped = re.escape(term)
print(escaped)
pattern = re.compile(escaped)
print(bool(pattern.search("value 1.5*(x) a-b here")))
print(bool(pattern.search("1 5 x a b")))

1\.5\*\(x\)\ a\-b
True
False

Each turns the term into a pattern where every special character is escaped, so the search finds the exact text and a crafted term cannot reshape the pattern or slow it down. RegExp.escape also writes the leading 1 as \x31: it escapes a first digit or letter in hex, so that, joined after an escape such as \1 in a bigger pattern, the character is not read as part of that escape. Other platforms have the same tool: Go’s regexp.QuoteMeta, PHP’s preg_quote, Java’s Pattern.quote and .NET’s Regex.Escape.

A regex engine is itself software that can have bugs. The PCRE2 advisory GHSA-r9hj-j2rw-4q3m describes an out-of-bounds write in the engine’s JIT matching code, a memory-safety bug in versions 10.48 and earlier that is fixed in 10.49, and it notes that a service which runs only patterns it trusts is not exposed: one more reason to treat a user pattern as code. The response to any such advisory is to update to the fixed version and to find every bundled copy, because a language runtime often ships its own build of the engine. PHP bundles its own PCRE2, and the copy in PHP 8.5.11 here reports version 10.44, older than that fix and not the system’s.

Patching is the one defence on this list that no pattern, engine or limit can replace, because the flaw is in the code that runs every pattern. Treat the engine as a dependency with a version you track, and the two threat cases plus a patched engine cover the whole surface a regex exposes.

Designing one safe search feature

No single defence fits every feature, so the design question is which to combine. The choice turns on three facts: who writes the pattern, whether it needs lookaround or a backreference, and whether your platform offers a linear engine. Answer them in the table, and it marks the defences that fit your case and the ones to drop:

A linear engine is ruled out the moment a user pattern needs a backreference or lookaround, or the platform has none; escaping is ruled out the moment the user means the text as a pattern; a deadline and an input cap fit almost anywhere, because they limit the cost rather than the features. With the defences chosen, they run in a fixed order on every request, cheapest guard first. Step through one safe search, from the request to a reply or a clear error:

The length cap runs first, because it is a plain length check and the cheapest way to reject a huge input before the engine does any work. Only inputs within the limits go on to be escaped (search text) or compiled on a linear engine (a pattern), and the match itself runs under a deadline, so every path ends in an answer or an error the visitor can act on.

Practise

The exercise builds the feature this lesson designed: a safeSearch that a visitor can call in a text mode and a pattern mode. It escapes search text, refuses a pattern that holds a backreference, a lookaround or a quantifier inside a quantifier, caps the pattern and the line length, refuses a mode it does not know, and returns every error as a value rather than throwing. The starter returns every line, so the first test fails at once until you add the guards:

// A log search a visitor can call in two modes. Finish it so that text mode treats
// the query as literal text, pattern mode refuses the unsafe shapes and caps the
// length, both modes skip over-long lines, and an invalid pattern is returned as an
// error rather than thrown.

export const MAX_PATTERN = 200; // the longest pattern a visitor may send
export const MAX_LINE = 2000; // the longest line that is worth matching

export function safeSearch(mode, query, lines) {
  // TODO: in text mode, escape the query with RegExp.escape before you build it.
  // TODO: in pattern mode, refuse backreferences, lookaround, a nested quantifier
  //       and a pattern over MAX_PATTERN, then compile with errors returned as values.
  // TODO: in both modes, skip any line longer than MAX_LINE.
  return { ok: true, matches: lines };
}

import { test, assert } from 'mysmartcopilot:test';
import { safeSearch } from './search.mjs';

const LINES = ['error 500', 'warn 1.5*(x)', 'ok', '12,34 done'];

test('text mode treats the query as literal text', () => {
  const r = safeSearch('text', '1.5*(x)', LINES);
  assert.ok(r.ok);
  assert.deepEqual(r.matches, ['warn 1.5*(x)']);
});

test('text mode reads a dot as a dot, not as any character', () => {
  const r = safeSearch('text', 'error.500', LINES);
  assert.ok(r.ok);
  assert.deepEqual(r.matches, []);
});

test('pattern mode runs a safe pattern', () => {
  const r = safeSearch('pattern', '\\d+,\\d+', LINES);
  assert.ok(r.ok);
  assert.deepEqual(r.matches, ['12,34 done']);
});

test('pattern mode refuses a backreference', () => {
  assert.equal(safeSearch('pattern', '(\\w+) \\1', LINES).ok, false);
});

test('pattern mode refuses a lookahead', () => {
  assert.equal(safeSearch('pattern', '(?=.*fail)', LINES).ok, false);
});

test('pattern mode refuses a quantifier inside a quantifier', () => {
  assert.equal(safeSearch('pattern', '(a+)+$', LINES).ok, false);
});

test('a pattern over the length cap is refused', () => {
  assert.equal(safeSearch('pattern', 'a'.repeat(300), LINES).ok, false);
});

test('an invalid pattern is an error value, not a thrown error', () => {
  const r = safeSearch('pattern', '(', LINES);
  assert.equal(r.ok, false);
  assert.ok(typeof r.error === 'string');
});

test('an unknown mode is refused, never searched', () => {
  const r = safeSearch('regex', 'error', LINES);
  assert.equal(r.ok, false);
  assert.ok(typeof r.error === 'string');
});

test('a line over the length cap never matches', () => {
  const long = 'x'.repeat(5000) + ' error';
  const r = safeSearch('text', 'error', [long, 'error here']);
  assert.ok(r.ok);
  assert.deepEqual(r.matches, ['error here']);
});

# A log search a visitor can call in two modes. Finish it so that text mode treats
# the query as literal text, pattern mode refuses the unsafe shapes and caps the
# length, both modes skip over-long lines, and an invalid pattern is returned as an
# error rather than raised.

MAX_PATTERN = 200  # the longest pattern a visitor may send
MAX_LINE = 2000  # the longest line that is worth matching


def safe_search(mode, query, lines):
    # TODO: in text mode, escape the query with re.escape before you build it.
    # TODO: in pattern mode, refuse backreferences, lookaround, a nested quantifier
    #       and a pattern over MAX_PATTERN, then compile with errors returned as values.
    # TODO: in both modes, skip any line longer than MAX_LINE.
    return {"ok": True, "matches": lines}

"""Sample tests for safe_search: safe and unsafe queries, an unknown mode and one very long line. None depends on timing."""

from search import safe_search

LINES = ["error 500", "warn 1.5*(x)", "ok", "12,34 done"]


def test_text_mode_is_literal():
    r = safe_search("text", "1.5*(x)", LINES)
    assert r["ok"] is True
    assert r["matches"] == ["warn 1.5*(x)"]


def test_text_mode_dot_is_a_dot():
    r = safe_search("text", "error.500", LINES)
    assert r["ok"] is True
    assert r["matches"] == []


def test_pattern_mode_runs_safe_pattern():
    r = safe_search("pattern", r"\d+,\d+", LINES)
    assert r["ok"] is True
    assert r["matches"] == ["12,34 done"]


def test_pattern_mode_refuses_backreference():
    assert safe_search("pattern", r"(\w+) \1", LINES)["ok"] is False


def test_pattern_mode_refuses_lookahead():
    assert safe_search("pattern", r"(?=.*fail)", LINES)["ok"] is False


def test_pattern_mode_refuses_nested_quantifier():
    assert safe_search("pattern", r"(a+)+$", LINES)["ok"] is False


def test_pattern_over_cap_is_refused():
    assert safe_search("pattern", "a" * 300, LINES)["ok"] is False


def test_invalid_pattern_is_an_error_value():
    r = safe_search("pattern", "(", LINES)
    assert r["ok"] is False
    assert isinstance(r["error"], str)


def test_unknown_mode_is_refused():
    r = safe_search("regex", "error", LINES)
    assert r["ok"] is False
    assert isinstance(r["error"], str)


def test_long_line_never_matches():
    long_line = "x" * 5000 + " error"
    r = safe_search("text", "error", [long_line, "error here"])
    assert r["ok"] is True
    assert r["matches"] == ["error here"]

Then work through the self-check. It starts from the idea you have shown least and explains every choice as soon as you make it:

Interview questions

Warm-up: name the two ways untrusted regex reaches a service, and the defence that fits each.

Untrusted regex is either a pattern a user supplies, as in a search box, a filter builder or customer-written alert rules, or input a user supplies to a pattern you wrote, such as a form field, a header or an uploaded file. For an untrusted pattern the defences are a linear-time engine, whose time stays linear in the text whatever the pattern, or a hard deadline on a worker or a match timeout when the engine must still backtrack. For untrusted input to your own pattern, cap the length before matching, keep the pattern clear of the slow shapes, and escape any user text that is meant as text rather than as a pattern. Both cases share one failure, a slow match that blocks the thread, so in both the goal is a bound on how long a match may run.

Two design questions take these defences into features this lesson did not build. Decide your first move on each, then open its first step:

Key takeaways

• Untrusted regex reaches a service two ways, a user-supplied pattern and user-supplied input, and each needs its own defence, so the first question is always which part came from outside.
• A pattern a user typed is code you agreed to run, and on a backtracking engine a small pattern can block the thread, so a user pattern needs a bound on its time, not just a successful compile.
• A linear-time engine removes the explosive case of a slow user pattern, because its time stays linear in the text whatever the pattern, at the cost of refusing backreferences and, in most such engines, lookaround.
• When the engine must still backtrack, a hard deadline on a worker, a match timeout or an engine limit such as PCRE2’s (*LIMIT_MATCH) caps the damage, and an input length cap shrinks the worst case for any pattern.
• Escape user text with a tool such as RegExp.escape or re.escape so it is matched literally, and keep every bundled copy of the engine patched, because the engine’s own bugs become your service’s.
• A safe feature stacks these defences in a fixed order, cheapest guard first, so every request ends in an answer or a clear error rather than a blocked thread.