Preliminary research

Regular Expression Denial of Service Induced by Backreferences

Yichen Liu, Berk Çakar, Aman Agrawal, Minseok Seo, James C. Davis and Dongyoon Lee

AI-collected research leads through 3 November 2026, including a November–October–September missed-article review and a targeted multilingual search alongside earlier community-source sweeps. Unranked, incomplete, not community-vetted, and subject to change.

ReDoS theory assumes Kleene regexes and the NFAs that model them, which cannot express backreferences - so Python, Perl, PHP, Ruby and Java fall outside it. A Two-Phase Memory Automaton captures backreference semantics and yields conditions for super-linear backtracking where sink ambiguity is linear and existing detectors report nothing; 45 unknown vulnerabilities were found in the Snort ruleset.

Record

Researcher

Yichen Liu, Berk Çakar, Aman Agrawal, Minseok Seo, James C. Davis and Dongyoon Lee

In the archive

• Collected in the 2026 preliminary research sweep

Related sources

• Paper
• Preprint
• Artifact

Tags

• redos
• dos
• algorithmic-complexity
• static-analysis
• detection
• owasp-a04-2021
• owasp-a09-2021

This page is the archive's own catalogue record. The research is the work of Yichen Liu, Berk Çakar, Aman Agrawal, Minseok Seo, James C. Davis and Dongyoon Lee, first published at the original source. Preserved copies are kept so the citation survives its host.