4 ms·

According to their ticket https://bugs.ruby-lang.org/issues/19104 https://bugs.ruby-lang.org/issues/19104 they are using memoization to defeat regular express

According to their ticket https://bugs.ruby-lang.org/issues/19104 https://bugs.ruby-lang.org/issues/19104 they are using memoization to defeat regular expression denial of service (ReDoS)

rurban 4y ago
Same trick as perl5 changed to recently. Not related to re2 at all.
- burntsushi 4y ago
  Yes, but there is an interesting clarification here. RE2 has used the "caching" approach documented in the Ruby bug ticket linked for quite some time (since its birth?): https://github.com/google/re2/blob/954656f47fe8fb505d4818da1e128417a79ea500/re2/bitstate.cc#L144-L145 https://github.com/google/re2/blob/954656f47fe8fb505d4818da1... It is mentioned only briefly in Cox's article on regex matching in the wild. Look for the word "bitstate": https://swtch.com/~rsc/regexp/regexp3.html https://swtch.com/~rsc/regexp/regexp3.html I didn't know Perl had implemented this trick too. The paper[1] cited in the Ruby bug ticket was published very recently. When I first read the Ruby bug ticket, I immediately wondered how they sidestepped the memory use problem. The paper's abstract seems to suggest there is some technique for doing so, as it rebuffs the idea of doing "full" memoization. Alas, I do not have access the paper. (Which is fucking ridiculous.) [1]: https://ieeexplore.ieee.org/abstract/document/9519427 https://ieeexplore.ieee.org/abstract/document/9519427
  - duckerude 4y ago
    One of the authors mirrored the paper: https://fservant.github.io/papers/DavisServantLee-SelectiveMemo-IEEE-SP21.pdf https://fservant.github.io/papers/DavisServantLee-SelectiveM...
    - burntsushi 4y ago
      Thanks!
  - burntsushi 4y ago
    OK, now that I have access to the paper, it does very briefly acknowledge RE2: > while caching is used to accelerate backtracking in Perl and a rare path in RE2. Although I wouldn't call it rare. It's probably used every time one wants capturing groups and the regex isn't one pass (pretty common) and the input isn't too big (like, say, a line in a log file). The actual part of the paper that contains the key contribution (memoization but with less space) is fairly dense and I don't have the time right now to look more closely. But it looks like it might be applicable to RE2, Go's regexp package and Rust's regex crate. All three already use already use bounded backtracking (i.e., "full caching"), but if the space usage could be cut back, then it would increase the opportunity of using the bounded backtracker. Namely, all three put a bound on `size(regex) * size(haystack)`. If the search needs something bigger than that bound, then the backtracker isn't used. But if memory usage were instead much less than `size(regex) * size(haystack)`, then the backtracker could be used more often. (Which is a good thing since it's generally faster than a full Thompson NFA simulation.)

According to their ticket https://bugs.ruby-lang.org/issues/19104 https://bugs.ruby-lang.org/issues/19104 they are using memoization to defeat regular expression denial of service (ReDoS)

rurban 4y ago

Same trick as perl5 changed to recently. Not related to re2 at all.

burntsushi 4y ago
Yes, but there is an interesting clarification here. RE2 has used the "caching" approach documented in the Ruby bug ticket linked for quite some time (since its birth?): https://github.com/google/re2/blob/954656f47fe8fb505d4818da1e128417a79ea500/re2/bitstate.cc#L144-L145 https://github.com/google/re2/blob/954656f47fe8fb505d4818da1... It is mentioned only briefly in Cox's article on regex matching in the wild. Look for the word "bitstate": https://swtch.com/~rsc/regexp/regexp3.html https://swtch.com/~rsc/regexp/regexp3.html I didn't know Perl had implemented this trick too. The paper[1] cited in the Ruby bug ticket was published very recently. When I first read the Ruby bug ticket, I immediately wondered how they sidestepped the memory use problem. The paper's abstract seems to suggest there is some technique for doing so, as it rebuffs the idea of doing "full" memoization. Alas, I do not have access the paper. (Which is fucking ridiculous.) [1]: https://ieeexplore.ieee.org/abstract/document/9519427 https://ieeexplore.ieee.org/abstract/document/9519427
- duckerude 4y ago
  One of the authors mirrored the paper: https://fservant.github.io/papers/DavisServantLee-SelectiveMemo-IEEE-SP21.pdf https://fservant.github.io/papers/DavisServantLee-SelectiveM...
  - burntsushi 4y ago
    Thanks!
- burntsushi 4y ago
  OK, now that I have access to the paper, it does very briefly acknowledge RE2: > while caching is used to accelerate backtracking in Perl and a rare path in RE2. Although I wouldn't call it rare. It's probably used every time one wants capturing groups and the regex isn't one pass (pretty common) and the input isn't too big (like, say, a line in a log file). The actual part of the paper that contains the key contribution (memoization but with less space) is fairly dense and I don't have the time right now to look more closely. But it looks like it might be applicable to RE2, Go's regexp package and Rust's regex crate. All three already use already use bounded backtracking (i.e., "full caching"), but if the space usage could be cut back, then it would increase the opportunity of using the bounded backtracker. Namely, all three put a bound on `size(regex) * size(haystack)`. If the search needs something bigger than that bound, then the backtracker isn't used. But if memory usage were instead much less than `size(regex) * size(haystack)`, then the backtracker could be used more often. (Which is a good thing since it's generally faster than a full Thompson NFA simulation.)