1. Backtracking (in the context of regular expressions and algorithms) is a trial‑and‑error process where the engine tries one possible path, and if that path fails, it goes back (“backtracks”) and tries another.
Think of backtracking like this:
“Try option A.
If it doesn’t work, rewind and try option B.
If that doesn’t work, rewind further and try option C…”
This is fine when there are only a few options.
It becomes dangerous when the number of options grows exponentially.
What is catastrophic backtracking?
Catastrophic backtracking happens when:
- A regex has nested repetition or ambiguity
- The engine must try an enormous number of paths
- Matching time becomes extremely slow
Example :
^(a+)+$
Why it’s bad:
a+already repeats- Wrapping it in
()+creates nested repetition - The engine keeps retrying the same matches in different groupings
Just adding one more character to the input can double execution time.
What is ReDoS
A ReDoS vulnerability stands for Regular Expression Denial of Service. It is a type of Denial‑of‑Service (DoS) attack that exploits how some regular expressions are evaluated.
ReDoS happens when a specially crafted input causes a regular expression to take an extremely long time to evaluate, consuming CPU and making an application unresponsive.
Why backtracking causes ReDoS
Backtracking itself is normal.
It becomes a vulnerability when attackers can control the input.
Attack flow:
- Attacker sends specially crafted input
- Regex engine enters massive backtracking
- CPU usage spikes
- Application becomes unresponsive
In Node.js or single‑threaded environments:
- One slow regex = entire server blocked
What makes it a vulnerability?
ReDoS becomes a security vulnerability when:
- A regex is evaluated on untrusted input
- The regex or the input can be influenced by an attacker
- The regex runs on a shared or single-threaded resource (e.g. Node.js event loop)
An attacker can then:
- Send a single request
- Tie up CPU
- Block all other users
