Evil Regex

Regular expressions are commonly used to validate strings, but seemingly simple patterns can sometimes behave unexpectedly and become "Evil Regex". Let’s assume we are going to validate a Linux file path and have a regex pattern like *expression*.match(/(\\\\/.+)+$/)this simple-looking regex that checks whether the expression is valid or not. These patterns can be exploited to cause performance issues, a vulnerability known as Regular Expression Denial of Service (ReDoS).

Let's consider a scenario where we're validating a simple expression like "/../n". This works fine for short inputs, but as the length of the expression increases, the processing time grows significantly. This happens because, for backtracking regex engines with nested quantifiers, the worst-case time complexity is O(2^n).

For example, in a Node.js environment, this becomes especially problematic because the event loop is blocked during regex evaluation, effectively halting all other processes.

Using "Evil Regex" patterns is strongly discouraged because they can lead to significant backtracking, where the regex engine attempts to explore all possible solutions. This excessive backtracking can cause severe performance degradation, especially with large or specifically crafted inputs. However, in scenarios where such regex patterns are unavoidable, the V8 engine in Node.js provides a helpful feature. By enabling the experimental regex engine with the following flag:

-enable-experimental-regexp-engine-on-excessive-backtracks

The below graphs show how much time (milliseconds) it takes for different lengths with or without the flag.

References:

https://www.nearform.com/insights/the-secrets-behind-high-performance-with-node-js/

https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS

https://nodejs.org/en/learn/asynchronous-work/dont-block-the-event-loop#blocking-the-event-loop-redos

https://grep.app/search?q=(a%2B)%2B%24