16
$\begingroup$

Apparently, ReDos attacks exploit characteristics of some (otherwise useful) regular expressions ... essentially causing an explosion of possible paths through the graph defined by the NFA.

Is it possible to avoid such problems by writing an equivalent 'non-evil' regex? If not (thus, the grammar can't be handled in practical space/time by an NFA), what parsing approaches would be better? Why?

$\endgroup$
  • $\begingroup$ If I managed to use precise technical language, it's an accident. Please dumb down your answers for a non-academic :-) $\endgroup$ – David Bullock Sep 4 '15 at 5:18
  • 1
    $\begingroup$ I'm actually just trying to find a practical way to avoid being ReDos'd, and this question came up. $\endgroup$ – David Bullock Sep 4 '15 at 5:20
  • $\begingroup$ To rephrase your question (?): Does every regular language have a regular expression whose length is bounded by a polynomial in the number of states of its minimal NFA? $\endgroup$ – A.Schulz Sep 4 '15 at 5:44
  • 1
    $\begingroup$ @A.Schulz. I don't think that's the question. That's not how ReDos attacks work. In a ReDos attack, the regexp is hardcoded into the program source code and is supplied by the developer, who is presumed to be trusted. Then, the adversary gets to supply an input string, which the program matches against the regexp. If the adversary can find an input string that causes the matcher to run for a really long time, the adversary wins. So, we're concerned about adversarial inputs, not adversarial regular expressions. (continued) $\endgroup$ – D.W. Sep 4 '15 at 6:39
  • $\begingroup$ Consequently, I think the question is instead: Does every regular language have a regular expression such that matching a $n$-character string against that regular expression takes $O(f(n))$ time, where $f(n)$ is some not-too-rapidly growing function of $n$ (say, polynomial, or something like that)? [Incidentally, this re-formulation makes clear that the answer will depend upon the algorithm used for matching... as I mention in my answer.] The size of the regular expression as a function of the size of the minimal NFA doesn't really matter here. $\endgroup$ – D.W. Sep 4 '15 at 6:40
13
$\begingroup$

It depends upon whether you've got a regular expression or a regexp: regexps are evil, but regular expressions are a thing of beauty and will never turn evil on you.

By regexp, I mean a modern regular expression: i.e., a regular expression with additional modern features such as backreferences -- e.g., a Perl-compatible regular expression. This is more powerful than a classical regular expression from a formal languages / automata theory textbook, as classical regular expressions don't allow backreferences, lookahead, lookbehind, and so on.

For a classical regular expression, if you have a good implementation for the matcher, then no regular expression is too evil. In particular, a standard algorithm for matching is to convert the regular expression to a NFA and then executing the NFA on an input string. For this algorithm, the worst-case running time to test a $n$-character string is $O(n)$, when the regular expression is fixed. This means that the running time can't explode too rapidly. There is no string that will cause an exponential increase in running time. Thus, if you're using a matcher that uses this algorithm, no classical regular expression will be evil.

This does depend on the implementation of the regular expression matcher. If you have a naive or poor implementation of the matcher, then matching could take exponential time; there are certainly algorithms with that property. But the best answer to that is probably not to change the regular expression; it's probably better to pick a better matcher, if you are concerned about denial-of-service attacks.

In comparison, some modern regexps are unavoidably evil. If you have a modern regexp, then matching can require exponential time. In particular, regexps with backreferences can recognize NP-hard languages. Consequently, under plausible assumptions, there exists a class of evil regexps where testing for a match takes exponential time. Thus, some modern regexps are unavoidably evil: there is no feasible way to find an equivalent regexp that won't cause exponential blowup in running time to match.

(Such an equivalent might exist and might even be findable in theory, but under plausible assumptions, finding the equivalent regexp will take exponential time, which isn't feasible in practice. If you had a systematic procedure to find the equivalent regexp in polynomial time, then you could solve the NP-hard problem in polynomial time, proving that P = NP. It doesn't do much good for there to exist an equivalent regexp if there's no way actually find it within your lifetime.)


Background and sources:

$\endgroup$
  • $\begingroup$ Isn't it easier to find a non-evil alternative by splitting up the regex into multiple smaller regexes and use them in combination? $\endgroup$ – inf3rno Jul 25 at 0:23
1
$\begingroup$

This answer will take a more overarching view of this unusual crosscutting situation, where complexity theory is applicable to cybersecurity and the example contains some of the significant nuance/ subtlety that can occur in this area. This is essentially similar to an "injection attack" where certain unexpected inputs cause pathological behavior either crashing a system or causing it to take an abnormally long time.

Wikipedia has 15 categories of Denial of Service attacks and this attack falls into "application level floods" in that list. Another somewhat similar example is an attack that fills up application logs.

One fix for injection attacks is to "clean the input". The application designer can reevaluate if it is necessary to compile arbitrary regexps supplied by a potentially malicious user. Just stripping off nested expressions in the regexp or some other similar limitation would probably be enough to avoid this attack. While they are intrinsic to a lot of modern software, large amounts of functionality can be provided without evaluating regular expressions. The context matters, some applications would not require such security.

Another approach to improve fault tolerance/ resilience that is applicable here are timeouts specified at different levels of the software stack/ hierarchy. The idea would be to specify a time/ cpu or instruction limit on a "average" regular expression evaluation and terminate early if its exceeded. They can be implemented with custom solutions but not very much software or programming languages have built-in timeouts or frameworks for this purpose.

Here is a nice example of the use of timeouts to improve fault tolerance and shows a high-level design/ architecture/ pov to mitigate such issues: Fault Tolerance in a High Volume, Distributed System / Netflix. It has nothing specifically connected to regular expressions but thats the point here: virtually any/ all application level logic can fit into this framework or something similar.

This article points out how backtracking in particular can lead to slow regexp matching. Regexps have many different features and one could attempt to evaluate which ones lead to worst case behaviors.

Here is a nice scientific survey of this particular topic with static analysis solution(s) proposed:

  • Static Analysis for Regular Expression Exponential Runtime via Substructural Logics / Rathnayake, Thielecke

    Regular expression matching using backtracking can have exponential runtime, leading to an algorithmic complexity attack known as REDoS in the systems security literature. In this paper, we build on a recently published static analysis that detects whether a given regular expression can have exponential runtime for some inputs. We systematically construct a more accurate analysis by forming powers and products of transition relations and thereby reducing the REDoS problem to reachability. The correctness of the analysis is proved using a substructural calculus of search trees, where the branching of the tree causing exponential blowup is characterized as a form of non-linearity.

$\endgroup$
  • $\begingroup$ This answer seems confused about some aspects of ReDos. 1. ReDoS has nothing to do with an injection attack. Injection attacks (e.g., XSS, SQL injection, command injection, etc.) are totally different. 2. ReDos is not about malicious regexps submitted by an adversary. Typically the regexp is hardcoded in the program (supplied by the developer), and the input string is supplied by a user. The problem can't be reasonably solved by input validation, because usually there's no clear input validation policy that would suffice to eliminate the problem. $\endgroup$ – D.W. Sep 5 '15 at 3:11
  • $\begingroup$ think your points amount to technicalities/ hairsplitting based on the ReDos ref & misses the forest for the trees. its similar to "crafted injection attacks". the answer points out that there are alternatives to using regexps in code. static analysis can find the "evil regexps". all the points of the answer are valid. a sentence like "typically the regexp is hardcoded in the program (supplied by the developer), and the input string is supplied by a user" doesnt exactly match the ReDos writeup which is more vague in places, and does refer to a malicious attacker etc. $\endgroup$ – vzn Sep 5 '15 at 5:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.