7 ms·

Yep. I remember years ago seeing the website for some guy who proudly listed all the CVEs he'd discovered. Clearly he'd written some scanning tool to look at re

Yep. I remember years ago seeing the website for some guy who proudly listed all the CVEs he'd discovered. Clearly he'd written some scanning tool to look at regexes in open source projects and was creating CVEs for anything that might result in exponential time execution or whatever.

gorgoiler 4mo ago
It sounds like an interesting case study. Do these things get reported with a patch?: (a) add a new function that does regular expressions searching / matching with a resource checker (eg a timer); (b) write a local linter that reports an error for any use of the builtin regular expression tools; (c) fix all the lint warnings; (d) commit the linter.
- jamesfinlayson 4mo ago
  No I think he was just looking to raise his profile, not to help.
- edelbitter 4mo ago
  This stuff has been brewing for years, but since technically you could fix all instances with minimal StackOverflow downtime [1] and a slightly different pattern, few people worked on either using engines with data structures less prone to the worst case or adding the generic workarounds for those that have them. e.g. in cPython, until 3.11, there was no support for atomic grouping (roughly translation: "never backtrack inside of this expression"). There is little useful advice a linter can give, if there is no predictable-runtime way to express what you want within a single match step, because you really do want to unwind the stack and check for repeats (just without any of the exponential runtime stuff, please). [1]: https://meta.stackoverflow.com/questions/328376/why-does-stack-overflow-use-a-backtracking-regex-implementation https://meta.stackoverflow.com/questions/328376/why-does-sta...
- mmsc 4mo ago
  already exists: https://joshua.hu/comparing-redos-detection-tools https://joshua.hu/comparing-redos-detection-tools. `recheck` and `redos-detector` are definitely the best. there's even an eslint plugin for the latter: https://github.com/tjenkinson/eslint-plugin-redos-detector https://github.com/tjenkinson/eslint-plugin-redos-detector
tryauuum 4mo ago
That's a real issue, took cloudflare down once...
- swiftcoder 4mo ago
  It's only a real issue if it is in runtime code that parses untrusted input. 99% of the regex lints/CVEs that get flagged our way are in build-time code.
  - tryauuum 4mo ago
    I don't fully get you. Do you mean untrusted regex or untrusted data it operates on? And to be honest, even if the regex is trusted (came from a developer) and the data as well (something predictable and structured) we are still not protected from the developer using extremely stupid regex and breaking everything

gorgoiler 4mo ago

It sounds like an interesting case study. Do these things get reported with a patch?: (a) add a new function that does regular expressions searching / matching with a resource checker (eg a timer); (b) write a local linter that reports an error for any use of the builtin regular expression tools; (c) fix all the lint warnings; (d) commit the linter.

jamesfinlayson 4mo ago
No I think he was just looking to raise his profile, not to help.
edelbitter 4mo ago
This stuff has been brewing for years, but since technically you could fix all instances with minimal StackOverflow downtime [1] and a slightly different pattern, few people worked on either using engines with data structures less prone to the worst case or adding the generic workarounds for those that have them. e.g. in cPython, until 3.11, there was no support for atomic grouping (roughly translation: "never backtrack inside of this expression"). There is little useful advice a linter can give, if there is no predictable-runtime way to express what you want within a single match step, because you really do want to unwind the stack and check for repeats (just without any of the exponential runtime stuff, please). [1]: https://meta.stackoverflow.com/questions/328376/why-does-stack-overflow-use-a-backtracking-regex-implementation https://meta.stackoverflow.com/questions/328376/why-does-sta...
mmsc 4mo ago
already exists: https://joshua.hu/comparing-redos-detection-tools https://joshua.hu/comparing-redos-detection-tools. `recheck` and `redos-detector` are definitely the best. there's even an eslint plugin for the latter: https://github.com/tjenkinson/eslint-plugin-redos-detector https://github.com/tjenkinson/eslint-plugin-redos-detector

tryauuum 4mo ago

That's a real issue, took cloudflare down once...

swiftcoder 4mo ago
It's only a real issue if it is in runtime code that parses untrusted input. 99% of the regex lints/CVEs that get flagged our way are in build-time code.
- tryauuum 4mo ago
  I don't fully get you. Do you mean untrusted regex or untrusted data it operates on? And to be honest, even if the regex is trusted (came from a developer) and the data as well (something predictable and structured) we are still not protected from the developer using extremely stupid regex and breaking everything