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?
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:
Which languages do Perl-compatible regular expressions recognize? and Expressiveness of modern regular expressions provide references to justify that modern regexps can recognize NP-hard languages.
How to simulate backreferences, lookaheads, and lookbehinds in finite state automata? and When a regexp is not a Regular Expression? can be helpful to understand the difference between regular expressions and regexps.
This article from Russ Cox has a nice explanation of two different ways of building a regular expression matcher, and explains why the running time if you use the proper algorithm is linear in the length of the input string (when the regular expression is held fixed and its length is treated as a constant). In particular, the NFA-based algorithm -- also known as the Thompson algorithm -- has linear worst-case running time. It also shows how some popular languages have regexp implementations that can go exponential on some regexps, and it discusses which aspects of modern regexps can introduce exponential running times.
In this post I assume P != NP. More to the point, when I refer to "plausible assumptions", I am referring to the exponential time hypothesis.
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.
