Regex 1.5.5 charges empty expressions against the compilation budget

An optimizer can remove an empty expression from its output while still spending time processing it. The regex crate's compilation budget missed that distinction. A pattern could request an enormous number of empty repetitions, consume substantial CPU time, and never produce enough compiled instructions to exceed the memory-based limit intended to stop it.

The 8 March security advisory identifies this as CVE-2022-24713. Versions through 1.5.4 are affected, and 1.5.5 contains the fix. The advisory specifically concerns services accepting untrusted regular expressions. It says there is no known vulnerability here when trusted expressions process untrusted search text.

I am impressed by Rust's semantics, but this case concerns a guarantee beyond memory safety. A program can avoid invalid memory accesses while spending unreasonable time on an attacker-selected expression. Resource behavior remains part of the contract for a library intended to handle untrusted patterns.

The relevant input is the expression

The crate documentation in version 1.5.5 distinguishes untrusted expressions from untrusted search text. The matching engines have documented time complexity in terms of the expression and search input. Expression compilation has separate limits intended to prevent unreasonable growth in the compiled representation.

That separation prevents a common misreading of regular-expression advisories. A service accepting text to search is not necessarily accepting a pattern to compile. The attacker needs influence over the input involved in the defective phase. Here the advisory identifies user-controlled patterns as the exposure condition.

For example, a service with a fixed validation pattern has a different relationship to this bug from a search service that compiles a pattern supplied in each request. This is a comparison of interfaces, not a claim about a particular deployment. The latter gives the requester control over the compiler's work.

The crate's documented defenses are also relevant to the disclosure. The advisory says bounded handling of untrusted patterns is part of the API guarantee. This is therefore a defect in an intended protection. Users were not necessarily making an unsupported assumption by relying on the default mitigations.

Empty output concealed repeated work

Andrew Gallant's fix commit explains the failure. Compiling an empty subexpression does not add a bytecode instruction in this implementation. A large repetition asks the compiler to process that subexpression repeatedly, even though the resulting program does not grow accordingly.

That creates a gap between the quantity used as a guard and the resource being exhausted. The guard observes the compiled object's size. The attack consumes CPU while repeatedly producing no additional compiled object. A size check can remain below its threshold throughout the expensive computation.

The patch's tests include a noncapturing empty group with an extremely large repetition count. Other tests construct empty results through chained repetitions, zero repetitions of a nonempty expression, and an empty alternative. The syntax varies while the relevant internal behavior remains the repeated compilation of emptiness.

This is why a denylist of a few suspicious strings would be inadequate. The advisory explicitly rejects that approach because there are effectively unlimited expressions that can exploit the weakness. The compiler must account for the shared mechanism after parsing has exposed it.

That principle matters beyond this particular grammar. Textual filters operate on how a request is written. Compiler resource limits need to account for the work implied by the parsed representation. Different strings can request equivalent or similarly expensive internal processing.

The disclosure credits Addison Crump with reporting the issue and helping review the correction. Gallant developed the fix, with Pietro Albini coordinating the disclosure. That division of work connects the public advisory to the implementation and the regression cases used to examine it.

The fix accounts for work without allocating it

The compiler already tracked additional instruction-related bytes for indirect allocations. The patch uses that accounting mechanism to charge the size of an instruction whenever it compiles an empty subexpression. It does not need to insert an actual instruction solely to make the limit effective.

The new empty-expression helper updates that extra accounting and returns the same empty compilation result. Repetition can therefore reach the ordinary size limit even though the representation retains its optimization of omitting empty instructions. This restores rejection without requiring the output program to contain redundant operations.

That distinction is useful. The number is an accounting charge used to bound a compilation, not a claim that the operation physically allocated that many bytes. Its purpose is to make the existing budget responsive to a form of work that previously evaded it.

The patch also changes the path that finishes a sequence containing no compiled expression. It routes that case through the empty helper too. Handling only the most obvious empty node would miss another route by which the compiler can arrive at the same no-output result.

My preference is for this kind of correction to follow the internal semantics. A syntactic special case for one reported pattern would leave the protection dependent on how a caller spelled it. Charging the compiler's empty result addresses the shared operation that the tests exercise in several ways.

The regression tests check rejection

The fix includes tests asserting that these large empty constructions return an error. Its comments are precise about what that proves. The tests establish that compilation eventually rejects the expression under the size policy. They do not directly establish a particular wall-clock deadline.

That is a useful limit on interpreting test evidence. A functional assertion about error versus success is stable and directly tied to the accounting change. A performance deadline would introduce another claim about the machine and execution environment. The patch explains the expected resource improvement through the mechanism while keeping the regression assertion narrower.

The older behavior could eventually compile successfully after spending a long time on the pattern. Returning an error is therefore itself a changed result, not merely a faster implementation of the same outcome. Applications accepting user patterns already need to handle compilation failure, and this fix restores the budget as another legitimate reason for rejection.

For an API exposing user-selected patterns, that error belongs in the normal request path. Treating every compilation failure as an internal panic would obscure the distinction between an invalid or excessive request and a defect in the service. The application controls how it communicates the rejected pattern to its caller.

Matching limits address a separate phase

The versioned crate documentation describes bounded behavior when a lazy DFA would otherwise grow too much during matching. Its cache can clear states and, if that happens too often, fall back to another engine with fixed memory requirements. That addresses work while searching text with an already compiled expression.

Those matching mechanisms do not repair an earlier compilation loop. A service must first obtain the compiled expression before the search engine can apply its policy. The security boundary therefore includes both phases when callers can choose patterns and search text.

The documented size_limit and dfa_size_limit controls likewise concern different internal resources. Their existence should not be flattened into a statement that one setting limits every cost of a regular expression. The defaults are intended to be useful, while the application still needs to understand which phase a configurable allowance affects.

This is also why the advisory's scope matters. It does not withdraw the crate's matching guarantees or identify every trusted pattern as unsafe. It reports a specific bypass in handling untrusted compilation requests and supplies a version that restores accounting for the missing work.

Updating the crate repairs the intended protection

The advisory recommends an immediate upgrade for users accepting user-controlled expressions. The fixed version is 1.5.5. A Rust compiler update alone does not describe that dependency change, because the affected code is in the regex crate used by the application.

A dependency requirement and the resolved version are also different pieces of evidence. The application needs the fixed crate in the dependency set used for its build. Stating only that a manifest allows a recent version does not identify the implementation contained in an existing artifact.

I regard the account of empty expressions as the most useful part of this disclosure. The protective limit existed, but its measured quantity failed to include work that generated no output instructions. The repair preserves the optimized representation while making that work count toward the compilation budget that callers were already entitled to rely on.