The regex that froze a shipped app for two minutes

A Dart developer opened an issue on the SDK last year with a title that is easy to skip past: "Application got stuck after runing regex.allMatches(text)." The report is short. They had an ordinary URL-validation pattern, they ran it over some text with allMatches, and the app locked up for about two minutes on a real device before coming back.

The Dart team looked at it and closed it as intended. Not a bug in the SDK, not a platform defect: the pattern itself was the problem. That verdict is correct, and it is also the uncomfortable part, because it means the same failure is sitting in a lot of shipped code right now, waiting for the wrong input.

Why a normal pattern hangs

Dart's built-in RegExp, like the regex engines in JavaScript, Python, Java and most others, is a backtracking engine. To decide whether a string matches, it explores possibilities, and when one path fails it backs up and tries another. For most patterns that is fine. For patterns with a nested quantifier, one repetition inside another, the number of paths it has to explore can grow exponentially with the length of the input.

The textbook example is (a+)+$. The inner a+ can claim the run of a's a dozen different ways, the outer + multiplies those choices, and the trailing $ forces the engine to try every combination before it can conclude there is no match. Real URL and email patterns hide the same shape inside something that looks reasonable in review, which is exactly why the issue above got shipped.

Here is what that pattern costs on my machine (Apple M4 Pro, Dart 3.11), giving RegExp.hasMatch a string of n a's followed by a b so it never quite matches:

 input length   dart:core RegExp.hasMatch
           22   43 ms
           24   170 ms
           26   684 ms
           28   2,741 ms
           30   11,055 ms

 input length   dart:core RegExp.hasMatch
           22   43 ms
           24   170 ms
           26   684 ms
           28   2,741 ms
           30   11,055 ms

Read the last two rows again. Going from 28 to 30 characters, two extra bytes, takes the match from under three seconds to over eleven. Every step of two quadruples the time. At 40 characters the answer arrives some time next week. If that input is a URL an attacker can shape, or a validation rule a user can configure, a single short string takes a core offline. That is the whole shape of a ReDoS, a regular-expression denial of service.

The fix is not write a better regex

The usual advice is to rewrite the pattern to avoid nested quantifiers. It works until the next pattern, and it does not help at all when the pattern comes from outside your code. The more durable fix is to run the match on an engine that cannot backtrack in the first place.

Google's RE2 is that engine. It compiles a pattern to a finite automaton and matches in time linear in the input length, with no exponential cliff, ever. The trade is deliberate: RE2 drops the features that force backtracking, namely backreferences and lookaround. In exchange you get a guarantee, and you find out a pattern is unsupported when you compile it, not when it hangs in production.

re2 binds RE2 to Dart over dart:ffi. The same catastrophic pattern, this time through re2:

import 'package:re2/re2.dart';

final re = Re2(r'(a+)+$');
print(re.hasMatch('a' * 1000000 + 'b')); // false, in about 3 ms
re.dispose();
 input length   re2.hasMatch
           28   0.01 ms
    1,000,000   2.9 ms

import 'package:re2/re2.dart';

final re = Re2(r'(a+)+$');
print(re.hasMatch('a' * 1000000 + 'b')); // false, in about 3 ms
re.dispose();
 input length   re2.hasMatch
           28   0.01 ms
    1,000,000   2.9 ms

A million characters in about three milliseconds, against thirty characters in eleven seconds. For hostile input the two engines are not in the same category.

Where this belongs

You do not want RE2 everywhere. For patterns and input you both control, the built-in RegExp is faster to reach for and supports backreferences. The place for a linear-time engine is the boundary: validating a URL, email or identifier that arrived over the network, applying a redaction or filter rule someone else configured, scanning a log line an attacker can influence. Anywhere the pattern or the text is not fully yours, a backtracking engine is a latent two-minute freeze, and a linear-time one simply is not.

re2 is on pub.dev with the benchmark above reproducible in its bench/ directory, so you can run these numbers on your own hardware rather than trust mine.

pub.dev: https://pub.dev/packages/re2

source: https://github.com/Yusufihsangorgel/re2

The frozen app in that SDK issue did nothing unusual. It called allMatches on a pattern that passed code review. That is what makes this worth an afternoon of your attention: the failure does not look like a bug until the input finds it.