[BUG] Possible Denial of Service #667
Comments
kbrock
added a commit
to kbrock/i18n
that referenced
this issue
Jun 13, 2023
From what I can see, this is done in linear time: 4*O(n) This tokenizer change converts that to something a little quicker: 3*O(n) Seems that not using a capture group and something other than split would be a big win. Other than that, the changes were meager. I used https://regex101.com/ (and pcre2) to evaluate the cost of the TOKENIZER. I verified with cruby 3.0.6 ``` /(%%\{[^\}]+\}|%\{[^\}]+\})/ =~ '%{{'*9999)+'}' /(%%\{[^\}]+\}|%\{[^\}]+\})/ ==> 129,990 steps /(%?%\{[^\}]+\})/ ==> 129,990 steps /(%%?\{[^\}]+\})/ ==> 99,992 steps (simple savings of 25%) <=== /(%%?\{[^%}{]+\})/ ==> 89,993 steps (limiting variable contents has minimal gains) ``` Also of note are the null/simple cases: ``` /x/ =~ '%{{'*9999)+'}' /x/ ==> 29,998 steps /(x)/ ==> 59,996 steps /%{x/ ==> 49,998 steps /(%%?{x)/ ==> 89,993 steps ``` And the plain string that doesn't fair too much worse than the specially crafted string ``` /x/ =~ 'abb'*9999+'c' /x/ ==> 29,999 /(%%?{x)/ ==> 59,998 /(%%?\{[^\}]+\})/ ==> 59,998 /(%%\{[^\}]+\}|%\{[^\}]+\})/ ==> 89,997 ``` per ruby-i18n#667
kbrock
added a commit
to kbrock/i18n
that referenced
this issue
Jun 13, 2023
From what I can see, this is done in linear time: 4*O(n) This tokenizer change converts that to something a little quicker: 3*O(n) Seems that not using a capture group and something other than split would be a big win. Other than that, the changes were meager. I used https://regex101.com/ (and pcre2) to evaluate the cost of the TOKENIZER. I verified with cruby 3.0.6 ``` /(%%\{[^\}]+\}|%\{[^\}]+\})/ =~ '%{{'*9999)+'}' /(%%\{[^\}]+\}|%\{[^\}]+\})/ ==> 129,990 steps /(%?%\{[^\}]+\})/ ==> 129,990 steps /(%%?\{[^\}]+\})/ ==> 99,992 steps (simple savings of 25%) <=== /(%%?\{[^%}{]+\})/ ==> 89,993 steps (limiting variable contents has minimal gains) ``` Also of note are the null/simple cases: ``` /x/ =~ '%{{'*9999)+'}' /x/ ==> 29,998 steps /(x)/ ==> 59,996 steps /%{x/ ==> 49,998 steps /(%%?{x)/ ==> 89,993 steps ``` And comparing against a the plain string of the same length. ``` /x/ =~ 'abb'*9999+'c' /x/ ==> 29,999 /(%%?{x)/ ==> 59,998 /(%%?\{[^\}]+\})/ ==> 59,998 /(%%\{[^\}]+\}|%\{[^\}]+\})/ ==> 89,997 ``` per ruby-i18n#667
|
@Akash-Karmakar-e3082 you passed in a 40k character string, and it was going through character by character. It had 4 checks per character, so it was 40k * 3 checks. If you have reason to believe that this with exponentially take longer, please share how you came to that conclusion. Also, can you share a quick example of why someone would localize content that was entered by a user? (An admin does not count. if the admin is nefarious, then they may as well just format the disk and be done) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
What I tried to do
Slow regex is being used:
https://github.com/ruby-i18n/i18n/blob/master/lib/i18n/backend/interpolation_compiler.rb#L24-L25
What I expected to happen
What actually happened
Versions of i18n, rails, and anything else you think is necessary
Bonus points for providing an application or a small code example which reproduces the issue.
The text was updated successfully, but these errors were encountered: