Skip to content

Threat model & the two defences

This page explains the reasoning regexutil is built on: why an untrusted regex is a denial-of-service surface even in Go, why the risk lives in compilation rather than matching, and why the package layers a length cap and a timeout rather than either alone. It ports and expands the package's own design notes.

RE2 makes matching safe — and only matching

Go's regexp package is built on RE2. RE2 guarantees that a match runs in time linear in the length of the input, with no backtracking. That is what rules out the classic "catastrophic backtracking" denial of service — the family of attacks where a pattern like (a+)+$ against a non-matching input sends a Perl-, PCRE-, or Java-style engine into exponential time at match time. In Go, that specific attack does not work.

It is tempting to stop there and conclude that untrusted patterns are safe in Go. They are not. RE2's guarantee is about matching a compiled program against an input. It says nothing about the cost of turning a pattern string into that compiled program in the first place.

Compilation is not guaranteed linear

regexp.Compile parses the pattern and builds an automaton. That construction is not guaranteed to be linear in the pattern's length. A pathological pattern can make it spend measurable wall-clock time and allocate an automaton of many thousands of states. Shapes that behave badly at compile time include:

  • Nested unbounded repetition — e.g. (a+)+b, where repetition is stacked on repetition.
  • Deeply nested alternation — many layers of (...|...) grouped inside one another.
  • Very long repetition chains — bounded repetitions with large counts, or long runs of quantified groups, that expand into a large state count.

The damage is not an exponential match; it is a single regexp.Compile call that burns CPU and memory building the program. In a long-running server that is a latency spike and an allocation surge. In a CLI it can hang the update flow; in an interactive TUI it can freeze the render loop while one compile churns. The unbounded call is the whole risk:

// The caller of userPattern controls how long this runs and how much it allocates.
re, err := regexp.Compile(userPattern)

Two defences, applied uniformly

regexutil wraps that call with two bounds. Both matter; neither is sufficient alone.

1. A byte-length cap (MaxPatternLength, 1024)

Oversize patterns are rejected before any compile work begins. The length is checked first; if it exceeds MaxPatternLength, the call returns ErrPatternTooLong without ever calling regexp.Compile. Legitimate filename globs and search queries are short, so a 1 KiB cap is generous for real input while removing the entire class of "enormous pattern" attacks cheaply.

2. A wall-clock compile timeout (DefaultCompileTimeout, 100 ms)

The length cap cannot catch a short but pathological pattern — (a+)+b is a handful of bytes. So the compile itself is run under a wall-clock timeout. A well-behaved 1 KiB pattern compiles in well under a millisecond, so a 100 ms bound is two orders of magnitude of headroom and still imperceptible for interactive use; anything that blows past it is treated as pathological and returns ErrPatternCompileTimeout.

Why both — defence in depth

The two bounds cover each other's gap:

  • A length cap alone would still let a short pathological pattern allocate a huge automaton before anyone noticed.
  • A timeout alone would let a legitimately large pattern begin allocating before the clock runs out — you would pay the memory cost up to the deadline.

Checking length first is also an optimisation: the cheapest rejection (a length comparison) fires before the more expensive guarded compile is ever set up.

The goroutine-leak tradeoff

regexp.Compile is not context-aware — there is no way to ask it to stop partway through. So the timeout path launches the compile in a goroutine and returns to the caller when the timeout fires, while that goroutine keeps running until the compile finishes (or, for a truly pathological input, effectively forever).

This is a deliberate, bounded leak, and the reasoning is:

  • The number of distinct pathological patterns a single process ever sees is small, so the number of such orphaned goroutines is small.
  • Each holds a single compile's working set — one automaton under construction, not an unbounded resource.
  • The caller gets its error immediately and can carry on; it is never blocked by the runaway compile.

The alternative — blocking the caller until a pathological compile completes — is exactly the freeze the package exists to prevent. If a future Go release exposes a context-aware compile, this path should migrate to it.

Logging: rejections never echo the pattern

Rejection errors are annotated with the pattern's length and the kind of rejection (too long, timed out) — never the offending pattern text itself. Logging attacker-controlled pattern content would hand an attacker a way to fill your logs with material of their choosing (log amplification / injection). If you have a genuine need to show the pattern to an operator, do that from a trusted-source context, where the source is not attacker-controlled and log amplification is not a concern.

Call-site discipline: only bound what crosses a trust boundary

The defences exist for patterns that originate outside the binary. Apply them exactly there and nowhere else:

  • Do route through CompileBounded / CompileBoundedTimeout any pattern from a config file, CLI flag, TUI input, HTTP payload, or message queue.
  • Do not wrap a literal pattern known at build time — you control it, it carries no DoS risk, and the bounds are pure overhead. Keep using regexp.MustCompile:
// Build-time literal: trusted, so MustCompile is correct.
var tagRE = regexp.MustCompile(`^v\d+\.\d+\.\d+$`)

Getting this boundary right is the point: bound the untrusted patterns rigorously, and leave the trusted ones alone.