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 leaves three orders of magnitude of headroom for realistic input and is still imperceptible for interactive use; anything that blows past it is treated as pathological and returns ErrPatternCompileTimeout.

How much headroom does 100 ms really leave?

Plenty for ordinary patterns, and less than you would guess for repetition-heavy ones. Filling the full 1 KiB cap with repeated bounded repetitions — (abc|def|ghi){0,999} over and over — takes around 100 ms to compile on a developer machine and is rejected roughly half the time. That pattern is silly, but it is valid, and nobody wrote it to attack you.

The consequence to design for: ErrPatternCompileTimeout means "too expensive here, right now", not "this pattern is malicious". A slower or busier machine crosses the threshold sooner. The measured table shows where the knee is, and What regexutil does not do covers what the bound does not protect.

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: why rejections are kept thin — and where that breaks down

Attacker-controlled text in your logs is a small denial of service of its own: whoever chooses the pattern chooses what fills your log storage, and what a later reader of those logs sees. So the length and timeout rejections are deliberately thin. ErrPatternTooLong carries the pattern's length and nothing else; ErrPatternCompileTimeout carries fixed remediation advice. The pattern text appears in neither.

The invalid-syntax path is the exception, and it is worth knowing about. ErrPatternInvalid wraps Go's own parse error, and that message quotes the expression that failed to parse — usually the whole pattern:

error parsing regexp: missing closing ]: `[unclosed`: regex pattern is invalid

That is exactly what an operator needs to find their missing bracket, and exactly what you do not want to write to a log sink fed by strangers. The package cannot decide which of those you are, so the call site has to: return the message to whoever wrote the pattern, and log only the sentinel when the source is untrusted. Does the error contain the pattern? has the concrete pattern for it.

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.