Re: regcomp(3) Multiple Vulnerabilities

["Carlos O'Donell" <carlos at systemhalted dot org>]

On Fri, Feb 17, 2012 at 9:00 AM, Vladimir Levijev
<vladimir.levijev@gmail.com> wrote:
> I'm a developer at Zabbix and we use (and have been using for many
> years) libc/regex to provide extended regular expressions support in
> our product. Recently we discovered that using a certain valid
> (correct me if I'm wrong here) regexp it's possible to crash/hang our
> programs on GNU/Linux. The result is either crash or 100% CPU load and
> constant memory leak (something like 100 MB in 5 minutes).
>
> An example patterns that do that:
>
> crash: ".*{10,}{10,}{10,}{10,}{10,}"
> hang: ".*{10,}{10,}{10,}{10,}"
> hang: (.*+++++++++++++++++++++++++++++(\w+))
>
> Example usage:
>
> $ echo foo | grep -E ".*{10,}{10,}{10,}{10,}{10,}"
> Segmentation fault
>
> Here is a link to our issue in our issue tracker:
>
> https://support.zabbix.com/browse/ZBX-4625
>
> Platform used: Debian "Squeeze" (stable), eglibc version: 2.11.3-2
>
> Debian issue tracker:
>
> http://security-tracker.debian.org/tracker/CVE-2010-4052
>
> One of the sources describing the issue in more detail:
>
> http://securityreason.com/securityalert/8003
>
> I have asked eglibc guys about the issue and they pointed out that
> this is rather an FSF GLIBC issue:
>
> http://www.eglibc.org/archives/issues/msg00116.html
>
> I have tried to get more info how other libc implementations handle
> such situations and it appeared NetBSD guys has fixed this issue (see
> revision 1.30):
>
> http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/regex/regcomp.c?only_with_tag=MAIN
>
> I'm sure you are aware of that problem and probably sick of
> discussions about it :-) but here go my questions anyway:
>
> 1. Are you planning to do anything regarding this issue and if yes,
> are there any timelines?

Personally I don't plan to do anything.

I don't think this is a bug.

> 2. If the answer of the question above is negative, do you know of any or
> can you recommend any workaround/solution for regcomp() users to handle
> such situations? We are not considering moving to other library, for
> us this is too big effort. Perhaps you could recommend some input
> validator/filter that could be used before feeding the regexp to regcomp()?

Workaround?

Yes...

* Create a thread.
* Give the thread a stack of size M bytes.
* Allocate an alternate signal stack for the thread of size S bytes.
* Have the thread run the regcomp.
* If the thread catches a SIGSEGV, tear down the thread, increase M
and S and start again.

or

* Create a new process.
* Set the resource limit.
* Have the process run the regcomp.
* Watch for a SIGSEGV, ter down the process, increase the resource
limit and start again.

Validator?

Not easily. The regex is a program. It would seem to me that
estimating the regex resource utilization is equivalent to the halting
problem? You would need an implementation simulator that would need to
be updated with the implementation which would give an *estimate* in
bytes, but that wouldn't solve the problem. Eventually the *estimate*
is sufficiently close to the remaining resources that your uncertainty
of the estimate might or might not cause the application to crash.

The only safe solution would be:
* Have the user pre-allocate all resources.
* Provide pre-allocated resources to a new regcomp interface called
regcomp_mem for the sake of discussion.
* The new regcomp_mem tries to compute the regcomp and fails with REG_ESPACE.
* User allocates more space and tries again.

This solution is almost identical to the thread/process suggestion
above but doesn't involve a new interface.

There would have to be strong community consensus around adding a new
regcomp interface.

Cheers,
Carlos.