POSIX ERE with two bounded wildcard intervals exhausts memory during pattern compilation (5.0.0–7.8.2)

[wanderlust-n]

Summary

A pattern of the form .{0,N}literal.{0,M} with two sufficiently large
bounded wildcard intervals causes pathological memory growth during regex
compilation, continuing until an external memory limit or host exhaustion
terminates the process. A 1-byte input file is enough to trigger it. On an
uncapped host this exhausted all RAM and swap (we observed a single ugrep
process reach ~11 GiB anonymous memory in a real incident that took a
self-hosted server running live services offline for ~30 minutes before
the kernel OOM killer intervened); inside a 512 MiB cgroup it reaches the
cap and is OOM-killed within seconds.

Reproduction (memory-caged — recommended)

printf 'x' > f.txt

sudo systemd-run --wait --pipe \
  --unit=ugrep-oom-repro \
  --uid="$(id -u)" \
  -p MemoryMax=512M \
  -p MemorySwapMax=0 \
  -p RuntimeMaxSec=30 \
  -p OOMPolicy=kill \
  -- ugrep -E '.{0,70}dream.{0,90}' f.txt

The core command, shown bare only for illustration — running it uncaged
will consume all available memory:

ugrep -E '.{0,70}dream.{0,90}' f.txt

Results on all builds we tested (Ubuntu 24.04, x86_64):

Build	Source	Result	Runtime to 512 MiB cap
ugrep 5.0.0	Ubuntu 24.04 package 5.0.0+dfsg-1	cgroup OOM-kill	3.9 s
ugrep 7.5.0	built from tag v7.5.0 (eada75555a2b), ALL TESTS PASSED	cgroup OOM-kill	3.9 s
ugrep 7.8.2	built from tag v7.8.2, ALL TESTS PASSED	cgroup OOM-kill	5.7 s

All three used the same printf 'x' fixture and the same
-E '.{0,70}dream.{0,90}' pattern.

Narrowing (each verified in the same 512 MiB cage)

• Within this tested pattern family, both intervals are required to
  trigger the failure: .{0,70}dream and dream.{0,90} each complete
  instantly (~8 MiB peak). The paired form explodes.
• Interval size matters: paired .{0,8}dream.{0,8} completes
  instantly; paired {0,70}/{0,90} exhausts memory.
• The failure is independent of input size and content in all tested
  cases: a 1-byte file, 4 MB of y\n lines (zero matches), a single
  800 KB line with zero matches, and a 60 MB text fixture behave
  identically. -o, -i, and file-vs-stdin delivery make no difference.
• Attribution to compilation: the 1-byte, zero-match reproducer and
  the input ablations show that the growth is attributable to pattern
  compilation rather than input scanning.
• -P (PCRE2) is unaffected where available: the identical pattern
  with -P completes instantly (~7-8 MiB) on the Ubuntu 5.0.0 package and
  on a PCRE2-enabled 7.5.0 build, for both the 1-byte file and the 60 MB
  fixture. (Our from-tag builds above were compiled without PCRE2 —
  option -P is not available in this build configuration — so -P was
  not testable on those two binaries; this is a build-configuration fact,
  not a -P failure.)
• GNU grep (grep -E, 3.11) handles the same pattern and inputs in
  MiB-scale memory.

Expected

Bounded memory during pattern compilation, or a graceful diagnostic when
the compiled DFA would exceed a safe complexity or memory limit.

Context

This was discovered through ugrep 7.5.0 embedded in Anthropic's Claude
Code CLI, which transparently shadows grep. Multiple downstream
incidents are documented in anthropics/claude-code#67021. A later
downstream report also reproduces the corresponding escaped BRE form
through -G; the upstream stock-build matrix reported here specifically
verifies the POSIX ERE -E form.

Related reports

• Two regular expressions with poor performance #485 discusses pathological performance and possible DFA
  growth for leading-wildcard patterns, but does not include this 1-byte
  OOM reproducer or verification through ugrep 7.8.2.
• Bundled ugrep OOMs the host: -E with two bounded {0,N} intervals explodes DFA construction to multiple GB anthropics/claude-code#67021 documents the downstream embedded-ugrep
  incidents and the same minimal pattern family.

Environment

Ubuntu 24.04, x86_64; tag builds via ./build.sh (gcc); distribution
package from the Ubuntu archive.

Happy to test patches or provide more measurements.

AI-assisted investigation; all measurements were operator-verified.

[genivia-inc]

Thank you for sharing the details and suggestions. This is not acceptable performance. Sorry it happened.

There is a built-in threshold DFA::MAX_STATES to reject explosive growth cases. It's been tested to stay below 2GB memory use or about. Apparently there are cases when this doesn't suffice to reject this case and similar cases. Will tweak this threshold further.

Currently leading wildcard patterns may cause excessive DFA growth, something that is theoretically known with DFAs, but is not (yet) practically addressed in ugrep for leading wildcard patterns. Ugrep should not get the memory consumption over 2GB in the worst case as the threshold is designed to do (but needs improvement).

[genivia-inc]

The DFA size should be more forcefully constrained to not exceed the maximum number of opcode words of the virtual machine that performs the pattern matching efficiently. The VM max is 16,711,679 words which is 534MB total as each word is 32 bit. The VM opcode words are constructed after DFA construction. Limiting the DFA growth to predictably stay within this opcode size limit can be accomplished (larger DFA are useless anyway since they will be rejected after DFA construction by the opcode table compiler). This should really fix the problem once and for all. This is accomplished by tweaking the threshold checks. A quick investigation with a threshold formula based on DFA nodes and edges and VM memory parameters will suffice to always ensure that we don't run into excessive memory consumption.

With these threshold parameters, we find that the example below is still allowable, causing a large DFA and opcode table that together won't exceed 1GB of memory use:

$ ugrep -E '.{0,70}dream.{0,29}' TODO.md --stats=vm
...
VM: 906867 nodes (1266ms) 231247098 edges (1815ms) 10228822 opcode words (145ms)

The peak memory footprint of this run is 802,816,936 bytes which is reasonable. This took 3s on an ARM64.

But the following case already reaches the limits and is rejected:

$ ugrep -E '.{0,70}dream.{0,30}' TODO.md --stats=vm
f][\x80-\xbf]*){0,30}
                     \___exceeds complexity limits

The peak memory footprint of this case is 833,569,704 bytes. This took little over 3s to reject. Your example is also rejected with these same statistics.

I'll commit an update with this minor tweak so anyone can try this out.

[genivia-inc]

My plan for the future is to improve the leading wildcard regex pattern matching to handle numeric repetitions R{n,m} differently. There are known techniques for this that use counters associated with DFA states. Adding this capability to the VM is possible.