Why Regular Expressions in Go Are Safe but Often Slow

Go's regexp package has an unusual promise for a regular expression library: every match runs in time proportional to the length of the input, whatever the pattern. That is a safety property that the engines in Python, Java, JavaScript, Ruby and PCRE do not have, and it is the reason a Go server can accept a regular expression from a user without a denial of service. It is also the reason regexp loses benchmarks. This article shows both sides with two small programs: one pattern that makes a backtracking engine take seconds and Go take microseconds, and one set of searches where the safe engine is up to 115 times slower than a plain string search.

It follows regexp against manual parsing, which has the practical fixes. For plain searching see fast string search. The cornerstone is the Go performance guide.

The lab

package main

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

func timeIt(f func()) time.Duration {
	f() // warm up
	best := time.Hour
	for i := 0; i < 5; i++ {
		t := time.Now()
		f()
		if d := time.Since(t); d < best {
			best = d
		}
	}
	return best
}

var sink bool

func main() {
	evil := regexp.MustCompile(`^(a+)+$`)
	fmt.Println("Go: ^(a+)+$ against n letters a followed by b (the classic catastrophic case)")
	for _, n := range []int{20, 28, 1000, 10000, 100000} {
		s := strings.Repeat("a", n) + "b"
		d := timeIt(func() { sink = evil.MatchString(s) })
		fmt.Printf("  n=%-7d %12v\n", n, d)
	}

	fmt.Println()
	fmt.Println("Go: the same 1 MB of text searched for the same word four ways")
	text := strings.Repeat("the quick brown fox jumps over the lazy dog. ", 22000)
	text += "needle"
	fmt.Printf("  text is %d bytes\n", len(text))
	cases := []struct {
		name string
		f    func()
	}{
		{"strings.Contains", func() { sink = strings.Contains(text, "needle") }},
		{`regexp "needle" (literal)`, func() { sink = regexp.MustCompile(`needle`).MatchString(text) }},
		{`regexp "ne+dle" (needs the engine)`, func() { sink = regexp.MustCompile(`ne+dle`).MatchString(text) }},
		{`regexp "(?i)needle"`, func() { sink = regexp.MustCompile(`(?i)needle`).MatchString(text) }},
		{`regexp "\w+ dog\. needle"`, func() { sink = regexp.MustCompile(`\w+ dog\. needle`).MatchString(text) }},
	}
	for _, c := range cases {
		d := timeIt(c.f)
		fmt.Printf("  %-36s %12v   %6.0f MB/s\n", c.name, d, float64(len(text))/d.Seconds()/1e6)
	}
}

import re, signal, sys, time

class Slow(Exception):
    pass

def alarm(_s, _f):
    raise Slow()

signal.signal(signal.SIGALRM, alarm)
pat = re.compile(r"^(a+)+$")
print("Python re (a backtracking engine): ^(a+)+$ against n letters a followed by b")
for n in (16, 20, 24, 26, 28):
    s = "a" * n + "b"
    signal.alarm(20)
    t = time.perf_counter()
    try:
        pat.match(s)
        print(f"  n={n:<3} {time.perf_counter() - t:10.3f} s")
    except Slow:
        print(f"  n={n:<3} gave up after 20 s")
    signal.alarm(0)

set -e
go build -o app .
./app
echo
python3 backtrack.py
rm -f app

Go: ^(a+)+$ against n letters a followed by b (the classic catastrophic case)
  n=20             583ns
  n=28             833ns
  n=1000         26.25µs
  n=10000       263.25µs
  n=100000    3.528542ms

Go: the same 1 MB of text searched for the same word four ways
  text is 990006 bytes
  strings.Contains                        252.792µs     3916 MB/s
  regexp "needle" (literal)                 253.5µs     3905 MB/s
  regexp "ne+dle" (needs the engine)      254.041µs     3897 MB/s
  regexp "(?i)needle"                   16.849166ms       59 MB/s
  regexp "\w+ dog\. needle"             28.920583ms       34 MB/s

Python re (a backtracking engine): ^(a+)+$ against n letters a followed by b
  n=16       0.002 s
  n=20       0.037 s
  n=24       0.586 s
  n=26       2.273 s
  n=28       9.043 s

The Go program times ^(a+)+$ against a string of n letters a followed by a b, which cannot match, then times five searches of a 990 KB text for the word "needle" at its end. The Python program runs the same pattern in Python's re with a 20 second alarm. Each Go time is the best of five runs, and the pattern is compiled inside the timed call for the searches, which adds a few microseconds that are small next to the 250 µs and above they report.

Part one: the pattern that kills a backtracking engine

^(a+)+$ asks for one or more groups of one or more a's up to the end. On aaaa...ab it cannot succeed, and a backtracking engine proves that by trying every way to split the a's into groups before giving up: with n letters there are about 2 to the power of n ways.

Python's time grew by a factor of 4 for every two letters added, which is the signature of exponential growth. The extrapolation is that 40 letters would take about 10 hours. A web service that runs such a pattern on a request field is one request away from a stuck process; this class of bug is called ReDoS (regular expression denial of service) and it has taken down real sites.

Go's time grew by a factor of 10 for every factor of 10 in length: 26 µs, 263 µs, 3.5 ms. That is linear. The reason is the algorithm. Go's engine, derived from Russ Cox's RE2, never backtracks. It simulates the automaton for the pattern by tracking all the states it could be in after each byte, so each input byte costs at most one step per state. The work is bounded by the pattern size times the input size, whatever the pattern says.

Three consequences follow. First, you can compile and run patterns that come from users, configuration or a database without fearing the input. Second, there are things the engine cannot express because they need backtracking: lookahead, lookbehind and backreferences are not supported, and regexp.Compile returns an error for them. Third, the guarantee is about the growth of time, not its size, and the constants are not small.

Part two: what the guarantee costs

Searching a 990,006 byte text (the sentence "the quick brown fox jumps over the lazy dog. " repeated, with "needle" at the end):

A literal costs nothing. When the pattern starts with a literal string (here needle, or ne followed by a repeat), the engine extracts the prefix and scans for it with the same fast byte search that strings.Index uses, and only then runs the automaton. The first three rows are within 1 percent of each other. Putting a literal at the front of a pattern is the cheapest optimisation there is.

Case insensitivity removes the literal. (?i)needle can start with any of two characters per letter, so there is no single byte string to scan for, and the engine falls back to stepping through its states for every byte. That is 66 times slower than the literal search. If you only need case insensitive matching of ASCII text, lower casing the text once, or using strings.EqualFold on candidates, is much cheaper.

A pattern that starts with a class does the same. The last pattern begins with a word character class, which matches almost everywhere in English text, so the engine has to follow candidate matches from nearly every position: 34 MB/s, 115 times slower than the literal.

The engine has several strategies inside. For a simple anchored pattern with no ambiguity it uses a fast "one pass" matcher; for small patterns on short inputs it uses a bit state backtracker, which is bounded in memory; for everything else it runs the general automaton. You do not choose among them, and the pattern's shape decides.

What to do with this

1. Keep user supplied patterns in Go and be glad of the guarantee. Cap the pattern length and the input length anyway, since memory and time still scale linearly.
2. Start patterns with a literal whenever the format allows. A line oriented search for error: followed by the details is fast. A search for (?i)error is not.
3. Pre filter with strings.Contains for a required word before running a heavier regexp on each line.
4. Replace regexp with string functions for fixed formats (the log parser went from 1,246 ns to 37 ns).
5. Know the missing features. If you need lookaround or backreferences, no Go regexp can do it. A parser, or a third party backtracking library with explicit limits, can, at the price of the guarantee.
6. Look for the 66 times cliff in profiles. A search that is suddenly slow after someone adds (?i) or a leading .* or a word class is this effect.

Checklist

• Go's regexp is linear in the input: 26 µs for 1,000 letters and 3.5 ms for 100,000 on a pattern that took Python 9 seconds at 28.
• No lookahead, lookbehind or backreferences.
• A leading literal gives string search speed (3.9 GB/s); (?i) and leading classes give 34 to 59 MB/s.
• Compile once and cap input size.
• Prefer strings for fixed formats.

The engine is described in Russ Cox's regular expression matching series and the supported syntax in the regexp/syntax package.