Preliminary research
Regular Expression Denial of Service Induced by Backreferences
AI-collected research leads through 22 September 2026, including targeted additions between broader 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
- Published by
- usenix.org
- Topic
- Other
In the archive
Related sources
- Regular Expression Denial of Service Induced by Backreferences (Paper) Whitepaper
- Regular Expression Denial of Service Induced by Backreferences
- Artifact
Tags
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; this one was last captured on .