BugTraq
Regular Expression Denial of Service Sep 10 2009 02:23PM
Alex Roichman (Alexr Checkmarx com) (3 replies)
Re: Regular Expression Denial of Service Sep 13 2009 07:35PM
Pavel Kankovsky (peak argo troja mff cuni cz)
Re: Regular Expression Denial of Service Sep 13 2009 06:32PM
Pavel Kankovsky (peak argo troja mff cuni cz)
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 /

[ reply ]
Re: Regular Expression Denial of Service Sep 11 2009 04:21PM
Gadi Evron (ge linuxbox org) (1 replies)
Re[2]: Regular Expression Denial of Service Sep 11 2009 05:06PM
Thierry Zoller (Thierry zoller lu) (2 replies)
Re: Re[2]: Regular Expression Denial of Service Sep 11 2009 09:35PM
Jeffrey Walton (noloader gmail com)
Re: Regular Expression Denial of Service Sep 11 2009 09:10PM
Gadi Evron (ge linuxbox org)


 

Privacy Statement
Copyright 2010, SecurityFocus