CODEWITHSUNDEEP
regex
allencharp
allencharp

Reputation: 1161

why evil regular expression will cause ReDoS?

Currently I am looking into ReDoS: Regular express denial of Service

some bad(evil) regular expression will cause low performance of validation

but why.... I search for wiki and owasp, the answer is mainly for NFA DFA that I could hardly understand....

Could anyone help me with some good sample of explaination....?

Upvotes: 0

Views: 410

Answers (1)

Bohemian
Bohemian

Reputation: 425318

It's called Catastrophic Backtracking.

It occurs when there's no match, but there are O(2n) ways to not match that must all be explored before returning false.

The example in the linked article from https://www.regular-expressions.info is (x+x+)+y, which when used with input of xxxxxxxxxx will take about 2500 steps to discover there's no match. Add one x and it takes 5000 steps, and so on. With input of 100 xs, you're talking billions of years of computing time.

The reason is there are m ways that x+x+ can match m xs and there are n / m ways that (x+x+) can be repeated over n xs and m can be an arbitrary number less than n. The exploration tree is like a binary tree of ways of carving up the input, leading to the time complexity of O(2n).

Upvotes: 2

Related Questions