The attack exploits the fact that many[2] regular expression implementations have super-linear worst-case complexity; on certain regex-input pairs, the time taken can grow polynomially or exponentially in relation to the input size.
An attacker can thus cause a program to spend substantial time by providing a specially crafted regular expression and/or input.
is the number of states in the nondeterministic automaton; thus, the conversion from NFA to DFA may take exponential time.
Note that for non-pathological regular expressions, the problematic algorithms are usually fast, and in practice, one can expect them to "compile" a regex in O(m) time and match it in O(n) time; instead, simulation of an NFA and lazy computation of the DFA have O(m2n) worst-case complexity.
Such extended patterns essentially force the implementation of regex in most programming languages to use backtracking.
The most severe type of problem happens with backtracking regular expression matches, where some patterns have a runtime that is exponential in the length of the input string.
All three of the above regular expressions will exhibit exponential runtime when applied to strings of the form
on a backtracking expression engine, it will take a significantly long time to complete, and the runtime will approximately double for each extra a before the !.
An example of such a pattern is "a*b?a*x", when the input is an arbitrarily long sequence of "a"s. So-called "evil" or vulnerable regexes have been found in online regular expression repositories.
Note that it is enough to find a vulnerable subexpression in order to attack the full regex: These two examples are also susceptible to the input aaaaaaaaaaaaaaaaaaaaaaaa!.
Therefore, in most cases, regular expression denial of service can be avoided by removing the possibility for the user to execute arbitrary patterns on the server.
Alternatively, a malicious page could hang the user's web browser or cause it to use arbitrary amounts of memory.
However, if a vulnerable regex exists on the server-side already, then an attacker may instead be able to provide an input that triggers its worst-case behavior.
In the case of a web application, the programmer may use the same regular expression to validate input on both the client and the server side of the system.
An attacker could inspect the client code, looking for evil regular expressions, and send crafted input directly to the web server in order to hang it.