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 http://www.regular-expressions.info/atomic.html[atomic grouping]
• Use http://www.regular-expressions.info/possessive.html[possessive quantifiers]
• Rewrite the pattern with no nested repetition.
• Where possible use a https://devopedia.org/regex-engines[text-directed engine].

References

See https://learn.secdim.com/course/stackoverflow-outage[StackOverflow Outage] mini course on SecDim Learn

Where possible use a text-directed engine.