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=-2.5 required=3.0 tests=AWL,BAYES_00, DKIM_ADSP_CUSTOM_MED,FORGED_GMAIL_RCVD,FREEMAIL_FORGED_FROMDOMAIN, FREEMAIL_FROM,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,SPF_HELO_NONE,SPF_PASS,UNPARSEABLE_RELAY shortcircuit=no autolearn=no 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 C97531F5AE for ; Wed, 28 Apr 2021 07:25:39 +0000 (UTC) Received: from neon.ruby-lang.org (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id 29F9A120CF2; Wed, 28 Apr 2021 16:24:34 +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 75E9D120CF2 for ; Wed, 28 Apr 2021 16:24:31 +0900 (JST) Received: by filterdrecv-57858cd75-hkwtt with SMTP id filterdrecv-57858cd75-hkwtt-1-60890DEC-9 2021-04-28 07:25:32.104596664 +0000 UTC m=+61368.378104275 Received: from herokuapp.com (unknown) by ismtpd0166p1mdw1.sendgrid.net (SG) with ESMTP id iuvtpGOGQTWRftvymy9HOQ for ; Wed, 28 Apr 2021 07:25:32.052 +0000 (UTC) Date: Wed, 28 Apr 2021 07:25:32 +0000 (UTC) From: sam.saffron@gmail.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: sam.saffron 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: 79686 X-SG-EID: =?us-ascii?Q?GD31AXMrLYtZC3ZmvheLkg5nAqKYtjT=2Fa5aksj98ZWP41hX0At6jW=2FJ8AU4zQZ?= =?us-ascii?Q?o2S+eWzMhU4=2FL2ZfQhsuQoBAhS7ytbhnrrc7EOm?= =?us-ascii?Q?beOC75WG0PR6jqCYVnHd8mnbfYufz3s5uwyUpCt?= =?us-ascii?Q?cSFmG7wSfa5F0FDRRIjgwO9PIIoybZOMw7pkeGD?= =?us-ascii?Q?IoZU27oCOpwYISpz3A2QIGLpDBfDknMgj2g=3D=3D?= To: ruby-core@ruby-lang.org X-Entity-ID: b/2+PoftWZ6GuOu3b0IycA== X-ML-Name: ruby-core X-Mail-Count: 103639 Subject: [ruby-core:103639] [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="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ruby-core-bounces@ruby-lang.org Sender: "ruby-core" Issue #17837 has been updated by sam.saffron (Sam Saffron). I wonder if even a lightweight SIGVTALRM may be too much of a performance hit? On the upside though not needing to think about a background thread is nice! If we are doing a background thread implementation I would recommend dropping fidelity. That way every 100ms (or something else reasonable) we would walk all threads checking for a particular regexp execution. If you see the same globally increasing "regexp run number" twice you know it has been running for at least 100ms. That way ultra short regexps pay almost no cost (log regexp_run_number++ in thread local storage is about all) ---------------------------------------- Feature #17837: Add support for Regexp timeouts https://bugs.ruby-lang.org/issues/17837#change-91735 * 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') => # 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/