1

I was reading this article (about ReDos). The examples they give are pretty simple but I'm sure such regex can hide everywhere. If there is any way to test if a regex is evil without spending a lot of time trying to find the NFA used by the regex engine, I would be very happy to know it.

Thank you very much.

5
  • 4
    This is more complicated than it seems. Finding the runtime of an algorithm without executing it is a problem of computer science which is still unsolved. Regular expressions are not turing-complete, so this is a simplified case, but it is still not easy.
    – Philipp
    Aug 18, 2015 at 7:47
  • I thought it was solved for NFA. I must be wrong then. Thank you :)
    – DARK_DUCK
    Aug 18, 2015 at 7:53
  • I am not a computer scientist. I don't know if it is solved for NFA or not.
    – Philipp
    Aug 18, 2015 at 7:56
  • 1
    You can fuzzy test your inputs to check if they're ReDoS vulnerable owasp.org/index.php/Fuzzing
    – Purefan
    Aug 18, 2015 at 7:59
  • 1
    While it is difficult to determine whether an arbitrary regex is evil, it is much easier to find classes of regexes which are definitely not evil. For example, regexes that do not contain grouping with repetition will not be evil. I'd expect limiting the accepted regexes to such a class to be feasible in many real life scenarios. Aug 18, 2015 at 10:10

1 Answer 1

2

The answer is that you don't know. This is the classic halting problem.

Basically you should not allow users to set their own regexs wherever possible. If you do allow them to set their own regex, then you could mitigate it in other ways such as only allowing them to set regexs when it affect their own service, or by setting execution timeouts. You could possibly flag long running regexs so you are aware if any of your users are attempting a ReDos.

0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .