|
The regular expression denial of service (ReDoS)〔 〕 is an algorithmic complexity attack that produces a denial-of-service by providing a regular expression that takes a very long time to evaluate. The attack exploits the fact that most regular expression implementations have exponential time worst case complexity: the time taken can grow exponentially in relation to input size. An attacker can thus cause a program to spend an effectively infinite amount of time processing by providing such a regular expression, either slowing down or becoming unresponsive.〔 〕〔 〕 ==Description== Regular expression matching can be done by building a finite-state automaton. Regular expressions can be easily converted to nondeterministic automata (NFAs), in which for each state and input symbol there may be several possible next states. After building the automaton, several possibilities exist: * the engine may convert it to a deterministic finite-state automaton (DFA) and run the input through the result; * the engine may try one by one all the possible paths until a match is found or all the paths are tried and fail ("backtracking").〔 〕〔 〕 * the engine may consider all possible paths through the nondeterministic automaton in parallel; * the engine may convert the nondeterministic automaton to a DFA lazily (''i.e.'', on the fly, during the match). Of the above algorithms, the first two are problematic. The first is problematic because a deterministic automaton could have up to states where is the number of states in the nondeterministic automaton; thus, the conversion from NFA to DFA may take exponential time. The second is problematic because a nondeterministic automaton could have an exponential number of paths of length , so that walking through an input of length will also take exponential time.〔 〕 The last two algorithms, however, do not exhibit pathological behavior. Note that for non-pathological regular expressions the problematic algorithms are usually fast, and in practice one can expect them to "compile" a regular expression 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.〔Lazy computation of the DFA can usually reach the speed of deterministic automatons while keeping worst case behavior similar to simulation of an NFA. However, it is considerably more complex to implement and can use more memory.〕 Regular expression denial of service occurs when these expectations are applied to regular expressions provided by the user, and malicious regular expressions provided by the user trigger the worst-case complexity of the regular expression matcher. While regex algorithms can be written in an efficient way, most regular expression engines in existence extend the regular expression languages with additional constructs that cannot always be solved efficiently. Such extended patterns essentially force the implementation of regular expression in most programming languages to use backtracking. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ReDoS」の詳細全文を読む スポンサード リンク
|