A Dart regex that cannot be made to hang

The Problem: Catastrophic Backtracking

FFI binding to Google's RE2. Matching runs in linear time, so no catastrophic backtracking.

Here is a validator that ships in a lot of Dart code. It checks that a string is a list of words separated by single spaces:

final ok = RegExp(r'^(\w+\s?)*$');

It works. Type a name, a tag list, a short label, and it returns true or false quickly. Then someone sends 31 characters of x with no trailing separator and the isolate stops answering.

I timed it. On Apple Silicon, Dart 3.11, dart:core RegExp takes 5.15 seconds to reject that 31-character input against ^(\w+\s?)*$. It is trying every way to divide the input between the outer * and the inner \w+, and there are exponentially many.

The textbook case (a+)+$ is worse: 29 characters of a take 2.77 seconds, and 31 characters did not finish while I waited. Each two extra characters roughly quadruples the time. This is ReDoS. It needs no traffic and no botnet, just one request carrying the right string against a regex you already shipped.

I filed this against the SDK. dart-lang/sdk#61284 was closed as intended: dart:core RegExp backtracks by design, and making it linear-time is not on the roadmap. The fix has to come from not using a backtracking engine on input you do not control.

Enter RE2

The engine that does not backtrack - RE2 - is Google's regex library. It matches in time linear in the length of the input, because it does not explore alternatives by trying and retrying.

• The same ^(\w+\s?)*$ against the same 31-character input takes 25 microseconds.
• The (a+)+$ case that dart:core could not finish at 31 characters returns in about 30 microseconds.
• On a 100,001-character input, RE2 answers in about 1 millisecond. dart:core would not finish this century.

Using re2 in Dart

re2 is an FFI package that binds RE2 into Dart. The API is close to RegExp:

import 'package:re2/re2.dart';

final re = Re2(r'^(\w+\s?)*$');
try {
  re.hasMatch('x' * 31); // ~25 us, returns false
  re.firstMatch('one two three');
} finally {
  re.dispose();
}

Re2 holds a native compiled program, so it has a dispose(). There is a NativeFinalizer behind it as a backstop, but call dispose when you are done. The failure mode cannot occur, which is the point.

Safety Guarantees

Not every nested quantifier is dangerous. The email pattern everyone copies:

^([\w.-])+@(([\w-])+\.)+([a-zA-Z0-9]{2,4})+$

has loops inside loops and stays fast even on a long almost-matching address. The literal dot between the loops fixes where each repetition ends, so there is nothing to retry.

The danger is not nesting, it is ambiguity: two loops that can each claim the same characters. That is hard to see by reading a pattern, and harder to be sure about across every pattern in a codebase and every pattern a user might submit.

The argument for RE2 is not that your regex is unsafe. It is that on this engine the unsafe case does not exist, so you do not have to be sure. re2 enforces that at construction.

RE2 has no backreferences and no lookaround, and those are the features that make matching exponential. A pattern that uses them is rejected when you build it, not when it is handed an expensive input:

try {
  Re2(r'(\w+)\1'); // backreference
} on FormatException catch (e) {
  print('rejected at construction: ${e.message}');
}

A Re2 that constructs is a Re2 that runs in linear time.

There are two more guards for untrusted input:

• Re2.escape(s) turns a fragment into a pattern that matches that string literally, for when you interpolate user text into a pattern:

  final re = Re2('name:\\s*${Re2.escape(userInput)}');
  

• Re2(pattern, maxBytes: N) rejects a pattern whose compiled program exceeds N bytes, so an attacker cannot hand you a pattern that is linear-time but enormous.

Testing Many Rules in One Pass

A rule engine, a WAF, or a log classifier runs a request against N patterns. With RegExp that is N separate matches, each one able to blow up. Re2Set compiles them into one automaton and reports which matched in a single linear scan:

final rules = Re2Set.compile([
  r'(?i)union\s+select',
  r'<script',
  r'\.\./',
]);

try {
  rules.matches('GET /../../etc/passwd'); // {2}
  rules.matches("id=1' UNION SELECT pw FROM t"); // {0}
} finally {
  rules.dispose();
}

matches returns the set of indices that fired, in the list order you compiled. N rules, one pass, no per-rule backtracking.

When Not to Use It

This is an FFI package, and that has a cost. On trusted input, re2 is not faster than dart:core. The FFI boundary costs roughly 2×, and dart:core is well optimized for the ordinary case. If you are matching a pattern you wrote against input you produced, keep using RegExp. The only reason to reach for this is the linear-time guarantee on untrusted patterns or untrusted input.

It needs a native library, so you need a C++ toolchain or a prebuilt binary, and it does not run on the web. There is no native regex engine in a browser, and a silent dart:core fallback there would hand you the ReDoS back on the one platform where you cannot escape it, so re2 does not pretend to work on web at all. On Flutter targets that link native code it does work. I verified flutter test runs a match and flutter build macos links the library.

The rule stays simple. Trusted input, use dart:core. Input or patterns from outside, use an engine where the five-second answer is not reachable.