Search papers, labs, and topics across Lattice.
This paper introduces the Two-Phase Memory Automaton (2PMFA) to precisely model Regular Expressions with Backreferences (REwB) semantics and identify denial-of-service vulnerabilities. The authors derive necessary conditions for backreferences to induce super-linear backtracking runtime, even with linear sink ambiguity, and identify three vulnerability patterns. They then develop detection and attack-construction algorithms, discovering 45 previously unknown REwB vulnerabilities in the Snort intrusion detection ruleset with quadratic or worse runtime, and demonstrate practical exploits.
Backreferences in regular expressions can induce quadratic or worse runtime vulnerabilities, even when existing detectors fail to flag them, enabling denial-of-service attacks and alert bypasses.
This paper presents the first systematic 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, develop detection and attack-construction algorithms, and validate them in practice. Using the Snort intrusion detection ruleset, our evaluation identifies 45 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.
