Skip to content

Backtracking has a cache, and a timeout

Level: 301 · anyone who runs a regex over input they do not control

One line: Since Ruby 3.2, Onigmo memoizes its backtracking, so /^(a|a)*$/ against 5,000 characters answers at once and Regexp.linear_time? says so in advance; a backreference turns the cache off, and Regexp.timeout or Regexp.new(..., timeout:) is the guard for those patterns.

A backtracking regex engine tries one alternative, and on failure goes back and tries the next. (a|a)* followed by something that cannot match gives it two choices per character and nothing to stop it trying every combination — 2⁵⁰⁰⁰ of them for the input below. That is regular-expression denial of service, ReDoS. Ruby 3.2 added a cache of the positions and pattern states the engine has already tried, which makes many such matches linear (Feature #19104 ↗), together with Regexp.linear_time? and Regexp.timeout=.

Verified output of backtracking_has_a_cache_rb.rb — regenerated by tools/run_examples.py, never hand-typed.

  Regexp.linear_time?(/^(a|a)*$/)                true
  /^(a|a)*$/ =~ "a" * 5000 + "b"                 nil

  Regexp.linear_time?(/^(a|a)*\1$/)              false
  Regexp.timeout (the process-wide limit)        nil
  Regexp.new(..., timeout: 0.5), 40 a's and b    Regexp::TimeoutError: regexp match timeout

Reading the output

  • Regexp.linear_time? is true for /^(a|a)*$/, and the match against 5,000 as and a b returns nil without a pause.
  • Add a backreference and the answer is false. What \1 must match depends on what the group captured earlier, and the engine does not use the cache for such a pattern.
  • Regexp.timeout is nil by default: no process-wide limit at all.
  • A per-regex timeout turns a hang into an exception. The backreference version on 40 as would run for far longer than anyone would wait; with timeout: 0.5 it raises Regexp::TimeoutError.

What to do

  • In a service that matches anything a user sent, set Regexp.timeout = 1.0 (or less) at boot. It applies to every regex in the process that does not set its own.
  • Assert Regexp.linear_time? on the patterns that face user input, in a test, so that a backreference added in review fails the build instead of a server.

If you are coming from another language

Perl finishes the same match at once too:

Verified output of backtracking_has_a_cache_pl.pl — regenerated by tools/run_examples.py, never hand-typed.

  ("a" x 5000) . "b" =~ /^(a|a)*$/   no match, within a second

Python's re has neither a cache nor a timeout. Run in a child process with a three-second limit, 12 as finish and 40 do not:

Verified output of backtracking_has_a_cache_py.py — regenerated by tools/run_examples.py, never hand-typed.

  12 a's and a b: finished, matched = False
  40 a's and a b: still running after 3 s, killed

The Encodings library's PCRE2 — the other regex engine ↗ is the same trade from the other side: ripgrep's default engine is linear by construction, and PCRE2 buys backreferences by backtracking.