parse_dup_op duplicates the tree exponentially when using repeated +

[Eduardo A. Bustamante López]

Hi guys,

I reported this bug: https://sourceware.org/bugzilla/show_bug.cgi?id=20095

I'm wondering if I reported it to the proper place. It's a variant of a bug
raised/reported by Jim Meyering
(https://sourceware.org/bugzilla/show_bug.cgi?id=17150). In that case, the
issue was a memory problem (the repeated repetition operators consumed memory
exponentially, leading to memory allocation failures and null pointer
dereferencing).

Which I think was also assigned a CVE number:

  http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2010-4051

This case is a cpu usage problem. Given enough repetition operators, the
program will consume exponential amounts of cpu time (since for every repetiton
operator, it duplicates the data structure that holds the regex, or part of
it).

I'm not even sure why regcomp in libc allows for repeated use of +'s or {n,m}
like that. The regcomp implementation in FreeBSD has a similar issue (check the
BUGS section here: https://www.freebsd.org/cgi/man.cgi?query=regcomp&sektion=3&apropos=0&manpath=freebsd
), but at least it treats the .++ case for ERE correctly (as an invalid
expression).

-- 
Eduardo Bustamante
https://dualbus.me/