Course contentsShow
← Security
Lesson 1175 of 3,05224. Application Security - Input ValidationFree lesson

ReDoS Fundamentals and Catastrophic Backtracking

Understanding how certain regex patterns cause exponential time complexity through backtracking in the matching engine.

ReDoS Fundamentals and Catastrophic Backtracking

What you'll learn: How poorly written regular expressions can be weaponized to cause denial-of-service attacks through exponential processing time.

The Core Problem

Regular Expression Denial of Service (ReDoS) occurs when a regex engine gets trapped in a catastrophic backtracking loop. Instead of validating input in milliseconds, the engine can take seconds, minutes, or even hang indefinitely—all from a carefully crafted malicious string.

How Catastrophic Backtracking Works

Think of backtracking like exploring a maze with dead ends. The regex engine tries one path through your pattern, and when it fails, it backtracks to try alternative paths. With certain patterns, the number of paths to explore grows exponentially with input length.

The Classic Evil Pattern

Patterns with nested or overlapping repetition are especially dangerous:

(a+)+
(a*)*
(a|a)*
(a|ab)+

For the pattern (a+)+ matching against input aaaaaaaaaaX (10 a's followed by X), the engine must try:

  • All a's in first group, none in second
  • 9 a's in first, 1 in second
  • 8 in first, 2 in second
  • 8 in first, 1-1 split across two iterations...

This creates 2^n possible paths the engine must exhaust before declaring failure.

Real-World Impact

An attacker who discovers a vulnerable regex in your validation logic can submit specially crafted input that causes:

  • CPU to spike to 100%
  • Request timeouts
  • Application unavailability
  • Resource exhaustion affecting all users

A string just 30 characters long can freeze a server for hours with the right vulnerable pattern.

Key Takeaway: Certain regex patterns with overlapping or nested quantifiers cause exponential time complexity through backtracking—attackers exploit this with crafted input to create denial-of-service conditions known as ReDoS.