Re: Regular Expression Denial of Service

[Pavel Kankovsky <peak@xxxxxxxxxxxxxxxxxxxxxx>]

On Thu, 10 Sep 2009, Alex Roichman wrote:

> The art of attacking the Web by ReDoS is by finding inputs which cannot
> be matched by Regexes and on these Regexes a Regex-based Web systems get
> stuck.

It is a shame your presentation assumes a primitive NFA implementation
and does not take optimizations used by real implementations into account
(they are not even mentioned).

A quick test confirms PCRE does not backtrack when it evaluates regular
expressions like ^(a+)*$ and the rest of your "real examples of ReDos"
(because their ambiguity is optimized away) and something rather
convoluted like ^((a{1,2}){1,2}){1,10}$ is needed to trigger
backtracking. See "Backtracking" in perlre manpage.

-- 
Pavel Kankovsky aka Peak                          / Jeremiah 9:21        \
"For death is come up into our MS Windows(tm)..." \ 21st century edition /