Bugtraq mailing list archives
Re: Regular Expression Denial of Service
From: Pavel Kankovsky <peak () argo troja mff cuni cz>
Date: Sun, 13 Sep 2009 20:32:37 +0200 (CEST)
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 /
Current thread:
- Regular Expression Denial of Service Alex Roichman (Sep 11)
- Re: Regular Expression Denial of Service Gadi Evron (Sep 11)
- Re[2]: Regular Expression Denial of Service Thierry Zoller (Sep 11)
- Re: Regular Expression Denial of Service Gadi Evron (Sep 11)
- Re: Re[2]: Regular Expression Denial of Service Jeffrey Walton (Sep 14)
- Re[2]: Regular Expression Denial of Service Thierry Zoller (Sep 11)
- Re: Regular Expression Denial of Service Pavel Kankovsky (Sep 14)
- Re: Regular Expression Denial of Service Pavel Kankovsky (Sep 14)
- <Possible follow-ups>
- Re: Regular Expression Denial of Service hackerwebzine (Sep 28)
- Re: Regular Expression Denial of Service Gadi Evron (Sep 11)