[ruby-core:105793] [Ruby master Feature#17837] Add support for Regexp timeouts

Issue #17837 has been updated by Dan0042 (Daniel DeLorme).


There are other tradeoffs to consider
* `Regexp.backtrack_limit=` is deterministic, and will stop execution after a certain amount of "processing" regardless of how many threads are busy
* `Regexp.timeout=` will stop a regexp after a certain time regardless of how other many threads are busy or the nature/composition of the regexp

Personally I don't care much for the `Regexp.timeout` approach; I consider that `backtrack_limit` is a better indicator of ReDOS (e.g 1M backtracks in 1s may be ok, but 10M backtracks in 1s is not).
So if we're mixing the two approaches I would like some control over this, such as `Regexp.backtrack_limit = a..b` where the time limit is enabled after `a` backtracks and `b` is the hard backtrack limit.



Eregon (Benoit Daloze) wrote in #note-34:
> What if the time between two backtracks is much larger for some Regexp, isn't that possible with many characters being matched and then at the end a possible backtrack? (e.g., something like `/(a{100000}|b{100000})*/`)
> If so, it sounds like 10000 backtracks could be either microseconds or seconds, i.e., not necessarily related to time, and the approach would not work for some Regexps which backtrack.

I don't think we need to worry that much about a regexp custom-made to be slow. ReDOS is about custom-made _strings_ that trigger backtracking in very plain, regular-looking regexps. In CVE-2021-22880, a regexp as simple as `/^-?\D+[\d,]+\.\d{2}$/` was the source of the trouble. I think it's ok to think of ReDOS protection in terms of such real-life regexps like that one, and not the realm of all possible weird regexps. And I think these real-life regexps will have a predictable relationship between number of backtracks and time.

> IMHO a better solution to this is use a automaton-based regexp engine (which always matches in linear time)

It may indeed be "better", but when will it be available? `Regexp.backtrack_limit=` is available right now, which makes it "better" by default, IMHO.

The `Regexp.backtrack_limit=` approach is
* simple
* deterministic
* almost no overheard
* available now

`Regexp.timeout=` sounds "easy to use in practical applications" but it's also a bit arbitrary. What timeout to use? 5 seconds? Why 5? In reality we should measure how long regexps take to execute and then fix a limit based on the largest valid measured value. And at that point there's no reason why time it easier to measure than backtracks.

----------------------------------------
Feature #17837: Add support for Regexp timeouts
https://bugs.ruby-lang.org/issues/17837#change-94311

* Author: sam.saffron (Sam Saffron)
* Status: Open
* Priority: Normal
----------------------------------------
### Background

ReDoS are a very common security issue. At Discourse we have seen a few through the years. https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS

In a nutshell there are 100s of ways this can happen in production apps, the key is for an attacker (or possibly innocent person) to supply either a problematic Regexp or a bad string to test it with.

```
/A(B|C+)+D/ =~ "A" + "C" * 100 + "X"
```

Having a problem Regexp somewhere in a large app is a universal constant, it will happen as long as you are using Regexps. 


Currently the only feasible way of supplying a consistent safeguard is by using `Thread.raise` and managing all execution. This kind of pattern requires usage of a third party implementation. There are possibly issues with jRuby and Truffle when taking approaches like this.

### Prior art

.NET provides a `MatchTimeout` property per: https://docs.microsoft.com/en-us/dotnet/api/system.text.regularexpressions.regex.matchtimeout?view=net-5.0

Java has nothing built in as far as I can tell: https://stackoverflow.com/questions/910740/cancelling-a-long-running-regex-match

Node has nothing built in as far as I can tell: https://stackoverflow.com/questions/38859506/cancel-regex-match-if-timeout


Golang and Rust uses RE2 which is not vulnerable to DoS by limiting features (available in Ruby RE2 gem)

```
irb(main):003:0> r = RE2::Regexp.new('A(B|C+)+D')
=> #<RE2::Regexp /A(B|C+)+D/>
irb(main):004:0> r.match("A" + "C" * 100 + "X")
=> nil
```

### Proposal

Implement `Regexp.timeout` which allow us to specify a global timeout for all Regexp operations in Ruby. 

Per Regexp would require massive application changes, almost all web apps would do just fine with a 1 second Regexp timeout.

If `timeout` is set to `nil` everything would work as it does today, when set to second a "monitor" thread would track running regexps and time them out according to the global value.

### Alternatives 

I recommend against a "per Regexp" API as this decision is at the application level. You want to apply it to all regular expressions in all the gems you are consuming.

I recommend against a move to RE2 at the moment as way too much would break 


### See also: 

https://people.cs.vt.edu/davisjam/downloads/publications/Davis-Dissertation-2020.pdf
https://levelup.gitconnected.com/the-regular-expression-denial-of-service-redos-cheat-sheet-a78d0ed7d865





-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:[e-mail]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>