Regular-expression Denial Of Service or ReDos happens when a regular expression engine requires an exponential amount of steps to recognise a string. The engine uses a significant amount of resources and results in a denial-of-service.

The patters (quantifiers) that result in a ReDos are known as evil patterns or explosive quantifier. An evil pattern has nested operators (e.g. + *) that matches in more the one way. They create an inner (e.g. x+) and outer loop (e.g. (x+) *) that exponentially increase the number of possible paths. Evil patterns can appear as an expression or a sub-expression.

Remediation

We can fix ReDoS in a number of ways. Every technique is a like a Swiss cheese that we align one after another to minimise likelihood of the vulnerability:

• Set a time-out for regex matcher (e.g. return false after 5s)
• Use atomic grouping
• Use possessive quantifiers
• Rewrite the pattern with no nested repetition.
• Where possible use a text-directed engine.

References

See StackOverflow Outage mini course on SecDim Learn

Where possible use a text-directed engine.

Metadata

• Severity: medium
• Slug: redos

CWEs

• 1333: Inefficient Regular Expression Complexity

OWASP

• A05:2021: Security Misconfiguration