Catastrophic Backtracking in Regular Expressions

Regular expressions are a powerful tool for matching patterns in text, but they can also be a source of performance issues if not used carefully. One such issue is “catastrophic backtracking” which occurs when a regular expression engine spends an excessive amount of time trying to match a string that doesn’t match the pattern.

Some regular expressions are looking simple, but can execute a very long time, and even “hang” the JavaScript engine.

Sooner or later most developers occasionally face such behavior. The typical symptom — a regular expression works fine sometimes, but for certain strings it “hangs”, consuming 100% of CPU.

In such case a web-browser suggests to kill the script and reload the page. Not a good thing for sure.

For server-side JavaScript such a regex may hang the server process, that’s even worse. So we definitely should take a look at it.

Catastrophic backtracking can also occur in JavaScript, which uses regular expressions in its built-in String.prototype.match() and RegExp.prototype.exec() methods.

Here’s an example of a regular expression in JavaScript that can cause catastrophic backtracking:

let pattern = /^(a+)*b/;
let input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
let match = input.match(pattern);

The regular expression ^(a+)*b is trying to match the string "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab" but it will cause the engine to explore an exponential number of possible match paths because of the use of unbounded repetition (*) which causes the engine to backtrack through each character one by one to find a "b" at the end.

To avoid catastrophic backtracking in JavaScript, you can use the same solutions as mentioned above, such as using bounded repetitions, avoiding nested quantifiers and use possessive quantifiers.

For example, instead of using ^(a+)*b use ^(a{1,10})*b. This limits the number of a's that can be matched and it will not cause catastrophic backtracking.

It’s important to keep in mind that when working with large inputs or when using regular expressions with complex patterns, it’s essential to keep an eye on performance and to test the regular expressions using different inputs to ensure that they’re not causing any issues.

For more details visit.

Happy Coding….