Regular Expression Denial of Service Induced by Backreferences

Yichen Liu, Stony Brook University; Berk Çakar, Purdue University; Aman Agrawal and Minseok Seo, Stony Brook University; James C. Davis, Purdue University; Dongyoon Lee, Stony Brook University

This paper presents the a systematic and theoretical study of denial-of-service vulnerabilities in Regular Expressions with Backreferences (REwB). We introduce the Two-Phase Memory Automaton (2PMFA), an automaton model that precisely captures REwB semantics. Using this model, we derive necessary conditions under which backreferences induce super-linear backtracking runtime, even when sink ambiguity is linear, a regime where existing detectors report no vulnerability. Based on these conditions, we identify three vulnerability patterns and validate them in practice. Using the Snort intrusion detection ruleset, our evaluation identifies 48 previously unknown REwB vulnerabilities with quadratic or worse runtime. We further demonstrate practical exploits against Snort, including slowing rule evaluation by 0.6-1.2 seconds and bypassing alerts by triggering PCRE's matching limit.

USENIX Security '26 Open Access Sponsored by
King Abdullah University of Science and Technology (KAUST)

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {320797,
author = {Yichen Liu and Berk {\c C}akar and Aman Agrawal and Minseok Seo and James C. Davis and Dongyoon Lee},
title = {Regular Expression Denial of Service Induced by Backreferences},
booktitle = {35th USENIX Security Symposium (USENIX Security 26)},
year = {2026},
isbn = {978-1-939133-58-8},
address = {Baltimore, MD},
pages = {1867--1886},
url = {https://www.usenix.org/conference/usenixsecurity26/presentation/liu-yichen},
publisher = {USENIX Association},
month = aug
}

Presentation Video