3 ms·
For anybody who's lost: Russ Cox is the original author of re2, a fast C++ library implementing regular expressions that are guaranteed to run in linear-time.
by jffry 5y ago
For anybody who's lost: Russ Cox is the original author of re2, a fast C++ library implementing regular expressions that are guaranteed to run in linear-time.
There's a collection of articles they wrote talking about regexes and various pitfalls: https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/
- deathanatos 5y agoThis is still relevant today, too. The last several JavaScript vulns. that people at my company have had to upgrade around were because of accidentally quadratic regex in JavaScript. One poor library[1] was attempting to match a header whose grammar was a whoppingly complex, 1#token (this is in the HTTP spec's notation: it means 1 or more `token`s, comma separated with optional whitespace around the comma) and hit this, by trying to split the incoming values with, / *, */ I was shocked that this wasn't compiled to a DFA. (I checked, too: my JS exhibited the behavior in the bug report.) This is, I also think, another reason why "simple" text protocols are not really so simple. The grammar above is "trivial", and yet, this is the end result. I don't feel like the library is particularly at fault: I doubt I would have caught this in code review. [1]: https://www.npmjs.com/advisories/1748 https://www.npmjs.com/advisories/1748