From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS4713 221.184.0.0/13 X-Spam-Status: No, score=-3.8 required=3.0 tests=AWL,BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS,UNPARSEABLE_RELAY shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from neon.ruby-lang.org (neon.ruby-lang.org [221.186.184.75]) by dcvr.yhbt.net (Postfix) with ESMTP id 8C7D11F5AE for ; Thu, 6 May 2021 13:31:07 +0000 (UTC) Received: from neon.ruby-lang.org (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id 0C1CF1211DC; Thu, 6 May 2021 22:30:02 +0900 (JST) Received: from xtrwkhkc.outbound-mail.sendgrid.net (xtrwkhkc.outbound-mail.sendgrid.net [167.89.16.28]) by neon.ruby-lang.org (Postfix) with ESMTPS id 215421211D5 for ; Thu, 6 May 2021 22:29:58 +0900 (JST) Received: by filterdrecv-6bd97c8c5f-p4nzn with SMTP id filterdrecv-6bd97c8c5f-p4nzn-1-6093EF93-199 2021-05-06 13:30:59.86012406 +0000 UTC m=+663117.650761256 Received: from herokuapp.com (unknown) by geopod-ismtpd-6-2 (SG) with ESMTP id e7843qtaQdyTpaRHWu2gVw for ; Thu, 06 May 2021 13:30:59.789 +0000 (UTC) Date: Thu, 06 May 2021 13:30:59 +0000 (UTC) From: daniel@dan42.com Message-ID: References: Mime-Version: 1.0 X-Redmine-Project: ruby-master X-Redmine-Issue-Tracker: Feature X-Redmine-Issue-Id: 17837 X-Redmine-Issue-Author: sam.saffron X-Redmine-Sender: Dan0042 X-Mailer: Redmine X-Redmine-Host: bugs.ruby-lang.org X-Redmine-Site: Ruby Issue Tracking System X-Auto-Response-Suppress: All Auto-Submitted: auto-generated X-Redmine-MailingListIntegration-Message-Ids: 79807 X-SG-EID: =?us-ascii?Q?8sy4RigFvRTdBfCVJrT9zb2J88PC92TMQwdNgaWYaq5M0kkgXl+U=2FnJrVwhkbG?= =?us-ascii?Q?4pQxGGXtYjynSj5RCpix0oBP0PUQThcavjL94Y3?= =?us-ascii?Q?AGqd8c9Gj8Ki1vmByBonDaRFi9kAPstYbfG6xwI?= =?us-ascii?Q?meLsl9cAhpZSED+=2FtMwvmY60E7p1Q9Co1985Fuf?= =?us-ascii?Q?AMiexTNi9Rj5XKnEEbyJSGYulq3texHaBLA=3D=3D?= To: ruby-core@ruby-lang.org X-Entity-ID: b/2+PoftWZ6GuOu3b0IycA== X-ML-Name: ruby-core X-Mail-Count: 103760 Subject: [ruby-core:103760] [Ruby master Feature#17837] Add support for Regexp timeouts X-BeenThere: ruby-core@ruby-lang.org X-Mailman-Version: 2.1.15 Precedence: list Reply-To: Ruby developers List-Id: Ruby developers List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Errors-To: ruby-core-bounces@ruby-lang.org Sender: "ruby-core" Issue #17837 has been updated by Dan0042 (Daniel DeLorme). duerst (Martin D=FCrst) wrote in #note-14: > In a backtracking regular expression engine, backtracking occurs very oft= en. There are many cases of backtracking that are still totally harmless. Even if backtracking occurs very often, my thinking was that it occurs less= often than `CHECK_INTERRUPT_IN_MATCH_AT`. But now that I'm looking at rege= xec.c I'm not so sure anymore. I can't make heads or tails of that code. Bu= t still, the slowness of a regexp is directly correlated to how much backtr= acking occurs, so it would make sense to tie the timeout into that. Like, c= heck the timeout at every 256th backtrack or something like that. If anyone= can figure out what constitutes a "backtrack" in the regexec code. > Ideally, a regular expression engine would deal with most regular express= ions in a way similar to what RE2 (or any DFA-based implementation) does That's rather out of scope for this ticket isn't it? ---------------------------------------- Feature #17837: Add support for Regexp timeouts https://bugs.ruby-lang.org/issues/17837#change-91870 * Author: sam.saffron (Sam Saffron) * Status: Open * Priority: Normal ---------------------------------------- ### Background ReDoS are a very common security issue. At Discourse we have seen a few thr= ough 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, th= e key is for an attacker (or possibly innocent person) to supply either a p= roblematic Regexp or a bad string to test it with. ``` /A(B|C+)+D/ =3D~ "A" + "C" * 100 + "X" ``` Having a problem Regexp somewhere in a large app is a universal constant, i= t will happen as long as you are using Regexps. = Currently the only feasible way of supplying a consistent safeguard is by u= sing `Thread.raise` and managing all execution. This kind of pattern requir= es usage of a third party implementation. There are possibly issues with jR= uby 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=3Dnet-= 5.0 Java has nothing built in as far as I can tell: https://stackoverflow.com/q= uestions/910740/cancelling-a-long-running-regex-match Node has nothing built in as far as I can tell: https://stackoverflow.com/q= uestions/38859506/cancel-regex-match-if-timeout Golang and Rust uses RE2 which is not vulnerable to DoS by limiting feature= s (available in Ruby RE2 gem) ``` irb(main):003:0> r =3D RE2::Regexp.new('A(B|C+)+D') =3D> # irb(main):004:0> r.match("A" + "C" * 100 + "X") =3D> nil ``` ### Proposal Implement `Regexp.timeout` which allow us to specify a global timeout for a= ll Regexp operations in Ruby. = Per Regexp would require massive application changes, almost all web apps w= ould do just fine with a 1 second Regexp timeout. If `timeout` is set to `nil` everything would work as it does today, when s= et to second a "monitor" thread would track running regexps and time them o= ut according to the global value. ### Alternatives = I recommend against a "per Regexp" API as this decision is at the applicati= on level. You want to apply it to all regular expressions in all the gems y= ou 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-r= edos-cheat-sheet-a78d0ed7d865 -- = https://bugs.ruby-lang.org/ Unsubscribe: