Regular expression engines rely on backtracking to evaluate patterns against input. Certain regex patterns lead to non-linear backtracking, where the evaluation time grows polynomially with input size.
Regular expression engines use backtracking to try all possible execution paths when evaluating a pattern against an input. In some cases, this leads to non-linear backtracking where the worst-case evaluation time grows polynomially (e.g., O(n²) or O(n³)) with the input size. While not as severe as catastrophic backtracking, such patterns can significantly degrade application performance when processing large or untrusted inputs.
This rule reports regular expressions that exhibit non-linear backtracking behavior.
To fix a regular expression with non-linear backtracking, consider the following strategies:
. with negated character classes to exclude separators where applicable (e.g., [^,]* instead of
.* before ,).{1,5} to limit repetitions.The following examples illustrate two distinct causes of non-linear backtracking. The first shows a pattern that is polynomial when unanchored: without a start anchor, the engine retries the pattern at every position, leading to quadratic evaluation time when there is no match. The second shows ambiguous alternation, which causes quadratic backtracking regardless of anchoring because multiple alternatives can match the same input in different ways.
/a+b/.test(input); // Noncompliant - polynomial backtracking when the pattern does not match
/(a|aa)+/.test(input); // Noncompliant - ambiguous alternation causes quadratic backtracking
Adding a start anchor prevents the engine from retrying at every position:
/^a+b/.test(input); // Compliant - anchor eliminates redundant backtracking positions
Restructuring the alternation to eliminate the overlap removes the quadratic behavior:
/a+/.test(input); // Compliant - unambiguous