Linear regex algorithm
54 views
Skip to first unread message
Jardel Matias
Feb 6, 2024, 7:59:04 AM2/6/24
to v8-dev
Recently, we have witnessed a surge in ReDoS (Regular Expression Denial of Service) issues, and the root cause behind these occurrences lies in the regex engine we employ for matching patterns. There is a library called re2, which serves as a wrapper for Google's re2 engine. This library resolves all regex patterns in linear time, albeit lacking support for backreferences and look-arounds.
Upon researching this matter, it becomes evident that prominent projects are grappling with this problem. Languages such as Rust and Go have successfully mitigated these issues long ago. Considering the impact of ReDoS on Node.js, particularly its tendency to stall the event loop, it seems prudent to integrate this functionality into the Node.js codebase.
For further insights into the severity of ReDoS vulnerabilities, you may refer to the following resources:
https://snyk.io/blog/redos-vulnerabilities-in-npm-spikes-by-143-and-xss-continues-to-grow/
https://swtch.com/~rsc/regexp/regexp1.html
To solve this problem maybe we can implementing a regex algorithm that operates in linear time, such as the Thompson implementation detailed in this link, is a worthwhile endeavor.
A had open the issues in Node Js issues page, take a look https://github.com/nodejs/node/issues/51659
Best regards,
Jardel Matias
Upon researching this matter, it becomes evident that prominent projects are grappling with this problem. Languages such as Rust and Go have successfully mitigated these issues long ago. Considering the impact of ReDoS on Node.js, particularly its tendency to stall the event loop, it seems prudent to integrate this functionality into the Node.js codebase.
For further insights into the severity of ReDoS vulnerabilities, you may refer to the following resources:
https://snyk.io/blog/redos-vulnerabilities-in-npm-spikes-by-143-and-xss-continues-to-grow/
https://swtch.com/~rsc/regexp/regexp1.html
To solve this problem maybe we can implementing a regex algorithm that operates in linear time, such as the Thompson implementation detailed in this link, is a worthwhile endeavor.
A had open the issues in Node Js issues page, take a look https://github.com/nodejs/node/issues/51659
Best regards,
Jardel Matias
Claudia
Feb 7, 2024, 11:32:49 AM2/7/24
to v8-dev
You may be interested in the following links:
- https://v8.dev/blog/non-backtracking-regexp
- https://es.discourse.group/t/safe-regex-engine-to-prevent-redos-attack/450/6
- https://es.discourse.group/t/re2-consider-having-it-as-alternative-engine-choice/1388/15
V8 does impose a bound currently on some regexps, but not all.
Jardel Matias
Feb 7, 2024, 2:04:01 PM2/7/24
to v8-...@googlegroups.com
Yes, it's exactly this, thanks for your help!
Best regards,
Jardel Matias
Best regards,
Jardel Matias
--
--
v8-dev mailing list
v8-...@googlegroups.com
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to v8-dev+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/v8-dev/e943bd00-788c-481d-96c3-653cad6473c6n%40googlegroups.com.
Reply all
Reply to author
Forward
0 new messages