SEA (Software Engineering Analytics) Lab, Virginia Tech

Many regex engines built into the current generation of programming languages today (e.g., PHP, Perl, Java, JavaScript, etc.) rely on Spencer's backtracking based algorithm. Unfortunately, these engines expose applications to an understudied denial of-service attack vector called Regular Expression Denial of Service (ReDoS). We are trying address the four main problems that contribute to the unsafety of regexes: the difficulty of composing safe (non-SL) regexes, the difficulty of fixing unsafe (SL) regexes, the limitation (SL runtime) of regex engines, and the unsafety of some extended features.