3 ms·

What sort of regular expression pitfalls can cause this sort of CPU utilization? I know they're possible but I am curious about specific examples of something s

What sort of regular expression pitfalls can cause this sort of CPU utilization? I know they're possible but I am curious about specific examples of something similar to what caused Cloudflare's issue here.

novas0x2a 7y ago
Some regex languages allow backtracking, and backtracking is usually the thing that causes regexes to blow up in resource cost: https://www.regular-expressions.info/catastrophic.html https://www.regular-expressions.info/catastrophic.html
- edwintorok 7y ago
  You probably want a regex engine that runs in linear time: * Google's RE2 https://github.com/google/re2/wiki/WhyRE2 https://github.com/google/re2/wiki/WhyRE2 * https://github.com/laurikari/tre/ https://github.com/laurikari/tre/ There is a good series of articles about the problem: https://swtch.com/~rsc/regexp/regexp3.html https://swtch.com/~rsc/regexp/regexp3.html I would strongly recommend deploying such a regular expression matcher to avoid problems like this. There are examples in the above article that you can use to test anything in your production deployment that accepts regular expressions to see how well it copes.
  - novas0x2a 7y ago
    Might have been a misdirect reply (although useful), but yeah, agree, linear-time regex engines are generally a much better idea.
roro159 7y ago
DoS with regex is a thing: https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS https://www.owasp.org/index.php/Regular_expression_Denial_of... StackOverflow had a similar case a while back: https://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016 https://stackstatus.net/post/147710624694/outage-postmortem-...
- andreareina 7y ago
  HN discussion of the StackOverflow incident: https://news.ycombinator.com/item?id=12131909 https://news.ycombinator.com/item?id=12131909
ErikCorry 7y ago
For examples check the bugs that were duped into https://bugs.chromium.org/p/v8/issues/detail?id=430 https://bugs.chromium.org/p/v8/issues/detail?id=430
tyingq 7y ago
There's also other similar things in this space, like hash table collisions that can eat CPU.
RcouF1uZ4gsC 7y ago
Part of the problem is that "regular expressions" are not really regular expressions in the Chomsky sense. Regular languages have some very nice properties relating to how they can be evaluated. Some regular expression engines have features that pulls the expressions from being a regular language into more complexity.

novas0x2a 7y ago

Some regex languages allow backtracking, and backtracking is usually the thing that causes regexes to blow up in resource cost: https://www.regular-expressions.info/catastrophic.html https://www.regular-expressions.info/catastrophic.html

edwintorok 7y ago
You probably want a regex engine that runs in linear time: * Google's RE2 https://github.com/google/re2/wiki/WhyRE2 https://github.com/google/re2/wiki/WhyRE2 * https://github.com/laurikari/tre/ https://github.com/laurikari/tre/ There is a good series of articles about the problem: https://swtch.com/~rsc/regexp/regexp3.html https://swtch.com/~rsc/regexp/regexp3.html I would strongly recommend deploying such a regular expression matcher to avoid problems like this. There are examples in the above article that you can use to test anything in your production deployment that accepts regular expressions to see how well it copes.
- novas0x2a 7y ago
  Might have been a misdirect reply (although useful), but yeah, agree, linear-time regex engines are generally a much better idea.

roro159 7y ago

DoS with regex is a thing: https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS https://www.owasp.org/index.php/Regular_expression_Denial_of... StackOverflow had a similar case a while back: https://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016 https://stackstatus.net/post/147710624694/outage-postmortem-...

andreareina 7y ago
HN discussion of the StackOverflow incident: https://news.ycombinator.com/item?id=12131909 https://news.ycombinator.com/item?id=12131909

ErikCorry 7y ago

For examples check the bugs that were duped into https://bugs.chromium.org/p/v8/issues/detail?id=430 https://bugs.chromium.org/p/v8/issues/detail?id=430

tyingq 7y ago

There's also other similar things in this space, like hash table collisions that can eat CPU.

RcouF1uZ4gsC 7y ago

Part of the problem is that "regular expressions" are not really regular expressions in the Chomsky sense. Regular languages have some very nice properties relating to how they can be evaluated. Some regular expression engines have features that pulls the expressions from being a regular language into more complexity.