Algorithmic Complexity Vulnerabilities in Regular Expression Engines

66 concepts21 papers1 proposal

Regular expressions (regex) are ubiquitous in modern software engineering, serving as the foundational "grammarware" for input validation, data parsing, and string manipulation. However, their concise syntax masks a profound computational reality: regex evaluation can trigger catastrophic resource exhaustion. This phenomenon, known as Regular Expression Denial of Service (ReDoS), transforms simple string matching into an algorithmic complexity vulnerability. While developers often treat regular expressions as a standardized, plug-and-play utility, a fragmented landscape of engine-specific behaviors, hidden performance traps, and theoretical limits challenges both automated security tools and human intuition.

The Mechanics of Catastrophic Backtracking

To understand why regular expressions fail catastrophically, one must look at how traditional regex engines execute a match. Most major programming languages (such as JavaScript, Python, and Java) rely on backtracking-based engines. When a regular expression contains structural ambiguities—specifically, overlapping quantified sub-expressions—the engine can find multiple valid paths to match the same prefix of an input string. As explained by Hassan et al., this creates a state of "infinite ambiguity."

Regex: (a+)+b
Input: aaaaaaaaaaaaaaaaaaaaaaaaaaca

When presented with an "evil string" that matches the ambiguous prefix (aaa...) but fails at the very end (ca), a backtracking engine does not simply fail immediately. Instead, it is forced to exhaustively explore every single permutation of paths that could potentially satisfy the pattern. As noted by Zheng et al. and Huang et al., this results in an exponential or high-polynomial explosion of execution time. The engine spends billions of cycles shifting characters between nested loops, freezing the underlying service and consuming 100% CPU.

The Portability Myth and Engine Families

A core driver of ReDoS vulnerabilities in production is the widespread misconception that regular expressions are a universal language. In an empirical study, Michael et al. demonstrated that regular expressions exhibit severe semantic and performance portability issues when moved across programming languages.

The authors categorize regex engines into distinct "performance families." For instance, languages like JavaScript, Python, and Java belong to a "slow" family that relies heavily on backtracking, whereas Go and Rust utilize "fast" engines built on deterministic finite automata (DFAs). When developers copy a regex pattern vetted in a fast engine and paste it into a slow engine, they risk introducing unexpected ReDoS vulnerabilities.

Furthermore, Michael et al. highlight that roughly 10% of regular expressions exhibit significant performance variations across language pairs. Many suffer from undocumented semantic differences that alter matching behavior entirely, leading to silent logic errors. This cross-engine divergence isn't unique to regex; similar semantic discrepancies plague database query languages during transpilation, as seen in SQL and SPARQL implementations (Saparina; Carey et al.).

The Illusion of Safety in Non-Backtracking Engines

To mitigate catastrophic backtracking, security advocates often recommend switching to non-backtracking engines that guarantee linear-time execution relative to the input string length (Barlas et al.). These engines avoid backtracking by simulating a DFA or tracking all possible Non-deterministic Finite Automata (NFA) states simultaneously.

However, the authors of Su et al. demonstrated that non-backtracking engines are not inherently immune to ReDoS. Instead of time complexity exploding due to backtracking steps, these engines suffer from a DFA state blow-up vulnerability.

[NFA States] --(Determinization on-the-fly)--> [DFA States Explode]

When an engine encounters highly non-deterministic patterns or complex character sets (such as UTF-8), it must construct new DFA states on the fly during execution. Attackers can craft specific strings that traverse acyclic paths in the underlying automaton, forcing the engine into its worst-case space complexity. This triggers an explosion of states, causing massive memory consumption and processing delays during lazy DFA compilation. Thus, the algorithmic complexity vulnerability shifts from path exploration to state construction.

Theoretical Boundaries and Advanced Features

Why can't we simply build a perfect static analysis tool to detect and fix all ReDoS vulnerabilities? The answer lies in the theoretical complexity of extended regular expression features. Modern regex dialects include advanced capabilities like back-references (e.g., matching a duplicated word via \1) and lookaround assertions.

As Dürr et al. point out, incorporating back-references into regular expressions fundamentally alters their mathematical properties, rendering basic static analysis tasks completely undecidable. There is no computable function that can bound the size disparity or predict the execution behavior of these extended patterns.

Consequently, current theoretical frameworks for identifying super-linear execution time often explicitly exclude these features (Hassan et al.), leaving a dangerous gap in automated security auditing. This mirrors broader theoretical limits in formal language theory, where determining language inclusion or distance for complex automata quickly scales to ExpTime-complete or undecidable territories (Chatterjee et al.).

The Modern Attack Surface and Developer Awareness

In practice, the threat of ReDoS has intensified with the rise of modern web APIs. While traditional HTML forms typically rely on simple, well-vetted validation patterns, modern API specifications (such as OpenAPI or Swagger schemas) frequently embed complex, custom regular expressions designed by developers to validate deeply nested JSON payloads. Barlas et al. showed that these custom API schemas represent a massive, overlooked attack surface for specification-driven ReDoS exploitation.

Compounding this technical risk is a severe human-centric challenge. As documented by Bhuiyan et al. and Michael et al., a vast majority of developers remain entirely unaware of ReDoS mechanisms or perceive them as low-severity issues. Because academic detection tools often analyze regex patterns in isolation without considering the broader application context, developers frequently dismiss warnings, leaving catastrophic backtracking vulnerabilities active in production environments.

Key Foundational Work

Preface of Special Issue on Theoretical Aspects of Computer Science (2013) — contributed 3 concept elements to this direction.
Edit Distance for Pushdown Automata (2017) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_algorithmic_complexity_vulnerabilities_71710323,
  title = {algorithmic complexity vulnerabilities},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/algorithmic-complexity-vulnerabilities/rdr_7171032335924423b101b965b9b28133},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_algorithmic_complexity_vulnerabilities_71710323_v1,
  title = {algorithmic complexity vulnerabilities},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/algorithmic-complexity-vulnerabilities/rdr_7171032335924423b101b965b9b28133/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake