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 /
