USENIX Security 26 - Regular Expression Denial of Service Induced by Backreferences @UsenixOrg
USENIX Security 26 - Regular Expression Denial of Service Induced by Backreferences  @UsenixOrg
Uploaded October 2026 | Updated November 2026, 5 days ago
USENIX Security '26 - 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.

View the full USENIX Security '26 program at usenix.org/conference/usenixsecurity26/technical-sessions
USENIX Security 26 - Regular Expression Denial of Service Induced by BackreferencesUSENIX Security 26 - Cordyceps: Covert Control Attacks on LLMs via Data PoisoningSREcon26 Europe/Middle East/Africa - The Isolation Paradox: How Sharding a Multi-Tenant Platform...SREcon26 Europe/Middle East/Africa - An Anthropologists View of Site Reliability EngineeringSREcon26 Europe/Middle East/Africa - Lightning Talk - Learn You a Solver for Great GoodWOOT 26 - You Have Been LaTeXpOsEd: A Large-Scale Systematic Analysis of Information Leakage...VehicleSec 26 - ESCAR Talk: CAUTION: HIGH VOLTAGE, LOW SECURITY – A Familiar Tale of...SREcon24 Europe/Middle East/Africa - OMG WTF SSO: A Beginner’s Guide to Single Sign-On...VehicleSec 26 - Charge It to My Neighbor: A Relay Attack on ISO 15118 Plug and Charge PaymentUSENIX Security 26 - B-Privacy: Defining and Enforcing Privacy in Weighted VotingNSDI 26 - CCC: Re-architecting Delay-based Congestion Control in Datacenter NetworksVehicleSec 26 - Reversing a Brake ECU Firmware Update
USENIX |

USENIX Security '26 - Regular Expression Denial of Service Induced by Backreferences

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER