I am aware of Regular Expression Denial of Service (ReDoS). Is there any reasonable way to allow users to create custom regexes while guaranteeing that they don't submit an exponentially slow pattern?
-
You are lacking details. Platform, usage, etc.– whatsisnameCommented Jun 14, 2017 at 2:57
-
8Instead of trying to avoid the user submitting a bad regex, perhaps a solution where after a certain period of time you cancel the execution?– SamuelCommented Jun 14, 2017 at 3:14
Add a comment
|
4 Answers
The problem with regular expressions is not the regex itself, but that the regex engine that has all kinds of “convenient” features like backtracking. Therefore, using a regex engine without these features avoids.
Regular expressions the computer science concept can always be matched in linear time after they are compiled to a finite state machine. So a state-machine based regex engine can't be used for ReDoS. However, the necessary state machines may become rather large in pathological examples. But limiting the available memory tends to be easier than limiting the available computation time.
The RE2 engine was developed specifically to deal with untrusted regexes and was designed for linear-time execution.
Another alternative is assembling the regexes yourself from a simplified notation. For example, you might allow users to use glob patterns (like *.txt). You can then parse that in a way that prevents backtracking, e.g. by disallowing nesting and only using greedy quantifiers. For many use cases, a simplified pattern notation is completely sufficient.
Analyzing a regular expression to see whether it will be slow or not, without the analysis becoming slow itself, amounts to solving the halting problem. In other words, it's not possible to find a correct and complete solution.
You can, of course, find a solution that is correct and incomplete. For instance, you could work with a restrictive white list of features that are safe to use (e.g. character classes yes, repetition no...). This would allow you to pass a lot of uncritical regexes, reject all critical ones, and (wrongly) reject some that are okay, but too complicated to prove safe automatically.
answered Jun 14, 2017 at 6:12
-
3Do you have a citation for your first statement? I would be interested in seeing such a proof. Regexes are not Turing-complete, so the halting problem may not apply. Commented Jun 14, 2017 at 8:10
-
3@SebastianRedl It's true that strictly speaking, regular expressions are not Turing-complete, but all regex libraries in popular use have extensions that make them no longer regular. Restricting your users to literally regular expressions could, in fact, be a good solution for this situation. Commented Jun 14, 2017 at 8:16
-
2@KilianFoth: IIRC, even true regular expressions (in the CompSci sense of the word) can require an exponential amount of backtracking. But since they're not Turing-complete, for any given regex it is theoretically possible to establish this upper bound. However, this leaves open two problems: determining the upper bound automatically is a non-trivial task, and the result may give unreasonably high results (as in, an upper bound much higher than the expected time).– MSaltersCommented Jun 14, 2017 at 9:54
-
@msalters any true regular expression is mechanically convertable to a deterministic finite state automaton, I.e. it is always possible to match the expression without backtracking at all. Your FSA might get unreasonably large, of course, but that suggests that a limit to the number of states in the generated FSA is a sufficient solution to prevent the attack in question.– JulesCommented Jun 18, 2017 at 14:58
As author of re parser for lazarus project I would say there are no ways to understand for any given regular expression what resources it will consume on a given text.
Without spending the same resources I mean (at least in big-O meaning).
So the best approach - run re parser in separate thread and kill it after timeout.
In addition to the other answers, a solution may also be to roll your own regex library, that allows performance instrumentation during execution, and thus providing the means to kill the execution halfway through if some criteria is met.
Similarly, you could run the regexes on another thread and kill the threads if they take too long.
answered Jun 14, 2017 at 16:20
