Regular Expression Denial of Service Induced by Backreferences

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...