Regexp matching causes a time-complexity explosion problem as known as ReDoS (https://en.wikipedia.org/wiki/ReDoS). ReDoS has become serious vulnerability in many places in recent years, and Ruby is no exception. The following is the incomplete list of such vulnerability reports:
These reports have been addressed by fixing the library/software implementation. But, if the language’s Regexp implementation becomes safe, the vulnerability is fundamentally archived.
For a few months, Ruby has implemented a Regexp matching timeout (https://bugs.ruby-lang.org/issues/17837). It is one of the useful methods for preventing ReDoS vulnerability, but it is a problem that setting a correct timeout value is hard. This value is depending on input length, environment, network status, system load, etc. When the value is too small, a system may be broken, but when the value is too large, it is not useful for preventing ReDoS.
Therefore, as a new way to prevent ReDoS, we propose to introduce cache-based optimization for Regexp matching. As CS fundamental knowledge, automaton matching result depends on the position of input and state. In addition, matching time explosion is caused for repeating to arrive at the same position and state many times. Then, ReDoS can be prevented when pairs of position, and state arrived once is recorded (cached). In fact, under such an optimization, it is known as the matching time complexity is linear against input size [1].
[1]: Davis, James C., Francisco Servant, and Dongyoon Lee. "Using selective memoization to defeat regular expression denial of service (ReDoS)." 2021 IEEE symposium on security and privacy (SP). IEEE, 2021. https://www.computer.org/csdl/proceedings-article/sp/2021/893400a543/1oak988ThvO
See the following example.
$ ruby --version
ruby 3.2.0preview2 (2022-09-09 master 35cfc9a3bb) [arm64-darwin21]
$ time ruby -e '/^(a|a)*$/ =~ "a" * 28 + "b"'
ruby -e '/^(a|a)*$/ =~ "a" * 28 + "b"' 8.49s user 0.04s system 98% cpu 8.663 total
$ ./miniruby --version
ruby 3.2.0dev (2022-10-27T13:39:56Z recache bc59b7cc1e) [arm64-darwin21]
$ time ./miniruby -e '/^(a|a)*$/ =~ "a" * 28 + "b"'
./miniruby -e '/^(a|a)*$/ =~ "a" * 28 + "b"' 0.01s user 0.01s system 8% cpu 0.310 total
In this example, using ruby v3.2.0-preview2, matching /^(a|a)*$/ against "a" * 28 + "b" takes 8.6 seconds because matching time of this Regexp takes exponentially against "a" * N + "b" form string. But, using the patched version of ruby, it takes 0.01 seconds. Incredibly it is 860 times faster because matching is done in linear time.
By this optimization, the matching time is linear to the input size. It sounds secure and good. Unfortunately, when Regexp uses some extension (e.g. look-around, back-reference, subexpression call), the optimization is not applied. Also, the optimization needs a bit more memory for caching. However, we have already investigated that they are not so the major problems (See the "Limitation" section).
Implementation¶The basic cache implementation is complete at this time and can be found in the following Pull Request.
https://github.com/ruby/ruby/pull/6486
Some tests seem to be failed, but it is no problem! Because the failed tests are for Regexp timeout, optimization works correctly and so they failed as expected. Of course, we need to fix these tests before merging.
Implementation notes:
Cache-based optimization is not applied in the following cases:
/(a{2,3})*/). It is an implementation issue entirely, but we believe it is hard to support this case correctly./(a|b){100000,200000}/). The cache table size is proportional to the product of the number of cache points of regex and input size. In this case, since the number of cache points becomes too large, the optimization cannot be applied.Experiments were conducted to investigate how these limitations are problematic in practice. We used ObjectSpace to collect Regexps and investigate whether they could be optimized and the number of cache points. Regexps were collected from the standard library, Webrick, and Rails. See the following gist for the details (https://gist.github.com/makenowjust/83e1e75a2d7de8b956e93bdac004a06b).
The experiments result is shown in the following table.
Collected from # Regexp # non-optimizable Maximum number of cache points stdlib 1009 86 (8.52%) 81 Webrick 356 44 (12.36%) 20 Rails 759 74 (7.75%) 27 TotalThis result shows that the percentage of non-optimizable Regexp is less than 10%, and the amount of memory used for optimization is about 10 times the length of the string (81/8, for a bit array) at worst in this case. It is considered that a sufficient number of Regexp can be optimized in practice.
Specification¶The detailed specification has been fixed yet. We have some ideas and we would like to discuss them.
Regexp#.timeout= and Regexp#timeout=)l (linear) or r (regular) sounds good, but I am not sure which is the best.Thank you.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.3