How I Audit JavaScript Regexes for Catastrophic Backtracking

I maintain a developer-tools site called CodeSwap, which features browser-based utilities and technical guides. While assessing the regular-expression tools, I sought a reliable method to determine whether a regex is merely slow or capable of consuming significant CPU resources using a specific input.

The answer was not a straightforward list of patterns labeled as "safe" or "unsafe." Instead, it involved a systematic audit process: identifying ambiguous repetition, crafting a failing input, measuring performance growth across various lengths, rewriting the pattern, and repeating the performance measurement.

The timings I used for this process were obtained from a Node.js 22 test run, which was originally part of the CodeSwap guide. While hardware and engine versions may change, the overall growth curve remains a valuable indicator. The core issue lies in the presence of multiple valid paths, followed by a single failure.

Most JavaScript regular expressions utilize backtracking, which involves the engine making a greedy choice. If something later fails, the engine revisits earlier choices. This behavior is generally harmless unless the same characters can be divided or matched in numerous ways. For example, consider the pattern /^ ( a+ ) + $ /. The inner a+ can consume one or many 'a' characters, while the outer + can repeat that group one or many times.

For an input consisting solely of 'a' characters, the first path succeeds quickly. However, adding a single character that cannot match forces the engine to explore an exponentially increasing number of partitions before returning false.

The OWASP Regular Expression Denial of Service (ReDoS) guide highlights this pattern as a warning sign, noting the presence of repetition within a repeated group and overlapping alternatives inside repetition. Another indication of potential issues includes the use of nested quantifiers and overlapping alternatives within repetition. A useful test input is not a random long string but rather a string that allows the risky portion to match repeatedly and then fail at the end.

To illustrate this, I created a function called measure that takes a length parameter. It generates an input string by repeating 'a' characters to the specified length, followed by a '!'. The function then measures the time taken for the vulnerable regex to match the input and returns an object containing the length, matched result, and the milliseconds taken for the measurement.

By testing strings of lengths 20, 22, 24, 26, 28, and 30, I observed the following pattern:

- 20 characters: 6 ms

- 22 characters: 25 ms

- 24 characters: 98 ms

- 26 characters: 402 ms

- 28 characters: 1,494 ms

- 30 characters: 6,060 ms

This data shows that every two added characters multiplied the time by roughly four. This exponential growth is the evidence I look for: a slow result accompanied by accelerated growth as the input length increases.

It is crucial not to run unknown patterns against unbounded input on a production request thread. Instead, use short, controlled samples in an isolated test process or worker and stop before the duration becomes disruptive.

The two primary shapes I examine first are:

1. A quantified group containing another quantifier, such as (a+)+

2. Overlapping alternatives under repetition, like /^ ( a | aa ) + $ /

My review checklist includes checking for nested repetition, overlapping alternatives, a forced failure due to an anchor or required literal after the ambiguous part, input length bounds, and measuring the growth pattern of the regex. Runtime isolation is also essential. If patterns or inputs are untrusted, they should be evaluated in a worker, subprocess, or engine with an enforceable timeout.

In addition to checking for these patterns, I recommend explicit minimum and maximum length limits, as suggested by OWASP's input-validation guidance. This can help reduce the impact of mistakes that may survive review. While static checks are helpful, measurement is crucial for confirming the presence of catastrophic backtracking and ensuring that a rewritten pattern remains linear in performance across the same family of inputs.

I developed a browser-based ReDoS checker that looks for ambiguous structures and can perform a bounded timing probe locally within the browser. However, it is important to note that this tool is a review aid, not a security certification. It does not upload patterns or test inputs to a server.

The longer catastrophic backtracking and ReDoS guide contains the full measurement table and additional examples. In my maintenance process, the key takeaway is to treat regex complexity similar to ordinary algorithmic complexity. A pattern may appear functionally correct for normal tests but still pose a risk when faced with a carefully chosen input.

By adopting a systematic audit approach and prioritizing readability and simplicity in regex patterns, developers can minimize the risk of catastrophic backtracking and ensure the security and performance of their applications.