Issue #19720 has been updated by Eregon (Benoit Daloze). nobu (Nobuyoshi Nakada) wrote in #note-2:
We introduced `Regexp.linear_time?` in order to check the linear-ness by **external** utilities.
You can also check dynamically created regexps.
Interesting. However that initialize monkey-patch does not get called for literal Regexps (`ruby -r./reghook.rb -e 'p /(a)?\1/' #=> /(a)?\1/`). And even if it did, how could the external utility ensure it is loaded early enough, e.g., before RubyGems? It seems very difficult. So while `Regexp.linear_time?` is useful, I think it is far better to have a warning category in core for this. I think that is the only way to guarantee an application does not use any non-linear Regexp. ---------------------------------------- Feature #19720: Warning for non-linear Regexps https://bugs.ruby-lang.org/issues/19720#change-103469 * Author: Eregon (Benoit Daloze) * Status: Open * Priority: Normal ---------------------------------------- I believe the best way to solve ReDoS is to ensure all Regexps used in the process are linear. Using `Regexp.timeout = 5.0` or so does not really prevent ReDoS, given enough requests causing that timeout the servers will still be very unresponsive. To this purpose, we should make it easy to identify non-linear Regexps and fix them. I suggest we either use 1. a performance warning (enabled with `Warning[:performance] = true`, #19538) or 2. a new regexp warning category (enabled with `Warning[:regexp] = true`). I think we should warn only once per non-linear Regexp, to avoid too many such warnings. We could warn as soon as the Regexp is created, or on first match. On first match might makes more sense for Ruby implementations which compile the Regexp lazily (since that is costly during startup), and also avoids warning for Regexps which are never used (which can be good or bad). OTOH, if the warning is enabled, we could always compile the Regexp eagerly (or at least checks whether it's linear), and that would then provide a better way to guarantee that all Regexps created so far are linear. Because warnings are easily customizable, it is also possible to e.g. `raise/abort` on such a warning, if one wants to ensure their application does not use a non-linear Regexp and so cannot be vulnerable to ReDoS: ```ruby Warning.extend Module.new { def warn(message, category: nil, **) raise message if category == :regexp super end } ``` A regexp warning category seems better for that as it makes it easy to filter by category, if a performance warning one would need to match the message which is less clean. As a note, TruffleRuby already has a similar warning, as a command-line option: ``` $ truffleruby --experimental-options --warn-truffle-regex-compile-fallback -e 'Gem' truffleruby-dev/lib/mri/rubygems/version.rb:176: warning: Regexp /\A\s*([0-9]+(?>\.[0-9a-zA-Z]+)*(-[0-9A-Za-z-]+(\.[0-9A-Za-z-]+)*)?)?\s*\z/ at_start=false encoding=US-ASCII requires backtracking and will not match in linear time truffleruby-dev/lib/mri/rubygems/requirement.rb:105: warning: Regexp /\A\s*(=|!=|>|<|>=|<=|~>)?\s*([0-9]+(?>\.[0-9a-zA-Z]+)*(-[0-9A-Za-z-]+(\.[0-9A-Za-z-]+)*)?)\s*\z/ at_start=false encoding=US-ASCII requires backtracking and will not match in linear time ``` So the warning message could be like `FILE:LINE: warning: Regexp /REGEXP/ requires backtracking and might not match in linear time and might cause ReDoS` or more concise: `FILE:LINE: warning: Regexp /REGEXP/ requires backtracking and might cause ReDoS` -- https://bugs.ruby-lang.org/