Hacker News Reader

Comment by bawolff | Hacker News Reader

> Another thought: since backreferences and lookaround are the features in JS regexes which _cause_ ReDOS,

This is incorrect. Other features can cause ReDOS.

The other problematic features have linear time algorithms that could be used, but generally are not used (i assume for better average case performance)

View on HN

Right. An example regex that can be slow is CSV parsing [1]:

.*,.*,.*,.*,.* etc.

I believe a timeout is a better (simpler) solution than to try to prevent 'bad' patterns. I use this approach in my own (tiny, ~400 lines) regex library [2]. I use a limit at most ~100 operations per input byte. So, without measuring wall clock time, which can be inaccurate.

[1]: https://stackoverflow.com/questions/2667015/is-regex-too-slo... [2]: https://github.com/thomasmueller/bau-lang/blob/main/src/test...

PHP tended towards this approach too. It did lead to security vulns though where people interpreted a timeout the same as not matching, so attackers made the input complicated to skip the security check (part of this is on php for making the difference between timeout and no match be null vs false, instead of just throwing an exception)

Yea, I can expand the description to include other features that may cause issues. Here is an example of how counting can cause latency too: https://www.usenix.org/system/files/sec22fall_turonova.pdf

A static analysis of the regular expression has the advantage that many problematic cases can be caught at compile time. Not all: the expression is sometimes generated at runtime. There's also a risk that too many cases might be rejected.

Did you consider a hybrid approach, where static analysis is used to get compiler warnings / errors, combined with limiting the number of operations at runtime? An API change might be needed, so instead of just "matches(regex)" a new method might be needed with a limit "matches(regex, opCountLimit)" and a different return type (true / false / timeout).

Reply on news.ycombinator.com