Hacker News Reader

Comment by sequoia | Hacker News Reader

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.

View on HN

DoS with regex is a thing: 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-...

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

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

You probably want a regex engine that runs in linear time:

* Google's RE2 https://github.com/google/re2/wiki/WhyRE2

* https://github.com/laurikari/tre/

There is a good series of articles about the problem: 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.

Might have been a misdirect reply (although useful), but yeah, agree, linear-time regex engines are generally a much better idea.

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.

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

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

Reply on news.ycombinator.com