[Bug demangler/87675] New: Stack Overflow in function next_is_type_qual() in cp-demangle.c, as demonstrated by "nm -C"

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

[Bug demangler/87675] New: Stack Overflow in function next_is_type_qual() in cp-demangle.c, as demonstrated by "nm -C"

kargl at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87675

            Bug ID: 87675
           Summary: Stack Overflow in function next_is_type_qual() in
                    cp-demangle.c, as  demonstrated by "nm -C"
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: demangler
          Assignee: unassigned at gcc dot gnu.org
          Reporter: N1705695H at e dot ntu.edu.sg
  Target Milestone: ---

Created attachment 44874
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=44874&action=edit
POC

An issue was discovered in cp-demangle.c in GNU libiberty, as distributed in
GNU Binutils 2.31. Stack Exhaustion occurs in the C++ demangling functions
provided by libiberty, and there is a stack consumption problem caused by
recursive stack frames: next_is_type_qua() and cplus_demangle_type()

Please use the "./nm -C $POC" to reproduce the bug. This result can trigger
different Stack Overflow, you can try several times.

To reproduce this bug. You need to build bintuils-2.31 with ASAN. Here is the
compile Option. Another approach is to set the break Point and debug it, as the
stack overflow didn't crash the program.

> CC=clang LDFLAGS="-ldl" CFLAGS="-DFORTIFY_SOURCE=2 -fstack-protector-all -fsanitize=undefined,address -fno-omit-frame-pointer -g -O0 -Wno-error" ./configure --disable-shared --disable-gdb --disable-libdecnumber --disable-sim

The ASAN dumps the stack trace as follows:

> ASAN:DEADLYSIGNAL
> =================================================================
> ==9864==ERROR: AddressSanitizer: stack-overflow on address 0x7fff9e5c9f58 (pc > 0x0000009684ac bp 0x000000000000 sp 0x7fff9e5c9f58 T0)
>     #0 0x9684ab in next_is_type_qual cp-demangle.c:2290
>     #1 0x9684ab in cplus_demangle_type cp-demangle.c:2387
>     #2 0x9684ab in next_is_type_qual cp-demangle.c:2290
>     #3 0x9684ab in cplus_demangle_type cp-demangle.c:2387
>     #4 0x9684ab in next_is_type_qual cp-demangle.c:2290
>     #5 0x9684ab in cplus_demangle_type cp-demangle.c:2387
>     #6 0x9684ab in next_is_type_qual cp-demangle.c:2290
>     #7 0x9684ab in cplus_demangle_type cp-demangle.c:2387
>     #8 0x9684ab in next_is_type_qual cp-demangle.c:2290
>     #9 0x9684ab in cplus_demangle_type cp-demangle.c:2387
>     #10 0x9684ab in next_is_type_qual cp-demangle.c:2290
>     #11 0x9684ab in cplus_demangle_type cp-demangle.c:2387
>     #12 0x9684ab in next_is_type_qual cp-demangle.c:2290
>     #13 0x9684ab in cplus_demangle_type cp-demangle.c:2387
>     #14 0x9684ab in next_is_type_qual cp-demangle.c:2290
>     #15 0x9684ab in cplus_demangle_type cp-demangle.c:2387
>     #16 0x9684ab in next_is_type_qual cp-demangle.c:2290
>     #17 0x9684ab in cplus_demangle_type cp-demangle.c:2387
>     #18 0x9684ab in next_is_type_qual cp-demangle.c:2290
>     #19 0x9684ab in cplus_demangle_type cp-demangle.c:2387
>     #20 0x9684ab in next_is_type_qual cp-demangle.c:2290
>     #21 0x9684ab in cplus_demangle_type cp-demangle.c:2387
>     ...
>     # 0xc5800000c22  (<unknown module>)

> SUMMARY: AddressSanitizer: stack-overflow cp-demangle.c:2290 in next_is_type_qual
> ==9864==ABORTING
> 00000000 AAborted
Reply | Threaded
Open this post in threaded view
|

[Bug demangler/87675] Stack Overflow in function next_is_type_qual() in cp-demangle.c, as demonstrated by "nm -C"

kargl at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87675

Michael Matz <matz at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |matz at gcc dot gnu.org

--- Comment #1 from Michael Matz <matz at gcc dot gnu.org> ---
One of usual fuzzer fake CVEs.

This is basically a similar "problem" like initially reported in
  https://sourceware.org/bugzilla/show_bug.cgi?id=23008
where I actually analyzed it.  The problem is that C++ mangled names
have a recursive structure.  For demonstration purposes let's assume that the
character 'F' in a mangled name means "here come nested template arguments,
described next", then you need to recurse down to decode those nested args,
and if the next character is 'F' as well, you just recurse down again.  So
a mangled "name" with a million 'F' characters in succession will need
a recursion depth of a million.

So, when you feed the demangler such a name a stack overflow is expected.
Exactly when the overflow occurs depends on how the demangler is compiled,
i.e. how much stack space is needed from one to the next recursion level
(sometimes the recursion is tail recursion, so in some compilation modes
can even be elided and so lead to non-exhaustion).

Many characters of the mangled names have this property, so there are multiple
variants of names that all lead to stack exhaustion, so the fuzzers were able
to create many different testcases:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85122 (aka bugzilla PR23008)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85452
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87335
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87636
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87675
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87681

Unfortunately they now also started to submit fake CVEs for these, like this
one (CVE-2018-18701) or CVE-2018-18700 (aka bug 87681).

If libiberty ever implements a check for this (which essentially can only be an
arbitrary limit, which is frowned upon, especially as it must be very small, as
people might have their stack limit set very low) fine, if not, also fine.
Until then feeding such names to any demangling tool leads to stack exhaustion
and hence segfault.  Like any other memory exhaustion not a security bug.
Reply | Threaded
Open this post in threaded view
|

[Bug demangler/87675] Stack Overflow in function next_is_type_qual() in cp-demangle.c, as demonstrated by "nm -C"

kargl at gcc dot gnu.org
In reply to this post by kargl at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87675

Scott Gayou <sgayou at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sgayou at redhat dot com

--- Comment #2 from Scott Gayou <sgayou at redhat dot com> ---
As Michael said, this seems to be one of a large number of duplicates.

At least CVE-2018-18484, CVE-2018-18701, and CVE-2018-18700 seems to be a
duplicates. I can only reproduce one of them via setting a lower ulimit -s, and
the crashes all appear to be in cp-demangle.c. The call flows are similar yet
slightly different. My guess is that a recursion limit would fix all of these
hence they are the same root issue.

If upstream agrees, the duplicate CVE assignments can potentially be rejected.
Let me know if anyone else has any evidence or arguments that these are
different -- it is possible I made a mistake in the analysis.
Reply | Threaded
Open this post in threaded view
|

[Bug demangler/87675] Stack Overflow in function next_is_type_qual() in cp-demangle.c, as demonstrated by "nm -C"

kargl at gcc dot gnu.org
In reply to this post by kargl at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87675

--- Comment #3 from Scott Gayou <sgayou at redhat dot com> ---
My last comment was a bit confusing. I can reproduce 2/3 on a standard system,
and the other 1/3 requires dropping ulimit -s down a bit. (to 4096).
Reply | Threaded
Open this post in threaded view
|

[Bug demangler/87675] Stack Overflow in function next_is_type_qual() in cp-demangle.c, as demonstrated by "nm -C"

kargl at gcc dot gnu.org
In reply to this post by kargl at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87675

--- Comment #4 from N1705695H at e dot ntu.edu.sg ---
(In reply to Scott Gayou from comment #3)
> My last comment was a bit confusing. I can reproduce 2/3 on a standard
> system, and the other 1/3 requires dropping ulimit -s down a bit. (to 4096).

Hi,

I don't think you've made a clear analysis of the problem. This has nothing to
do with how much stack memory you set up. No matter how big your stack memory
is, it can still run out. The test case only give a small number of characters.
As you can imagine, you can still run out of memory by giving a lot of
characters.

In detail, the program requires the amount of resource such as time, memory,
power, etc. Memory exhaustion problems in the server can occur circumstantially
when programs are provided with inputs that exhibit worst-case behavior.
However, the high space complexity of the algorithm or poorly-designed programs
consume much more memory than necessary under well-conceived inputs. In
particular, stack memory is very limited. An attacker may use own function call
or multiple functions to call each other, exhausting stack memory. In other
words, no matter how large your stack memory is, it will always run out(by
given more "Z" or "U"). No matter how big you set it up, it's ultimately
limited.

The problem itself is very difficult to fix. The problem is that C++ mangled
names have a recursive structure. Simple restriction cycles are not necessarily
good. Moreover, these examples give different stack frames. This is cause by
giving different string input. Some are call itself. Some are call different
function. In fact, it's hard to set recursive limits on every function.
Recursion limit would not fix all of these hence they are different root
cause(Loop calls involving six functions in a finite function stack frame).
Reply | Threaded
Open this post in threaded view
|

[Bug demangler/87675] Stack Overflow in function next_is_type_qual() in cp-demangle.c, as demonstrated by "nm -C"

kargl at gcc dot gnu.org
In reply to this post by kargl at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87675

--- Comment #5 from Nick Clifton <nickc at gcc dot gnu.org> ---
Author: nickc
Date: Fri Dec  7 10:33:30 2018
New Revision: 266886

URL: https://gcc.gnu.org/viewcvs?rev=266886&root=gcc&view=rev
Log:
Add a recursion limit to libiberty's demangling code.  The limit is enabled by
default, but can be disabled via a new demangling option.

include * demangle.h (DMGL_NO_RECURSE_LIMIT): Define.
        (DEMANGLE_RECURSION_LIMIT): Define

        PR 87681
        PR 87675
        PR 87636
        PR 87350
        PR 87335
libiberty * cp-demangle.h (struct d_info): Add recursion_level field.
        * cp-demangle.c (d_function_type): Add recursion counter.
        If the recursion limit is reached and the check is not disabled,
        then return with a failure result.
        (cplus_demangle_init_info): Initialise the recursion_level field.
        (d_demangle_callback): If the recursion limit is enabled, check
        for a mangled string that is so long that there is not enough
        stack space for the local arrays.
        * cplus-dem.c (struct work): Add recursion_level field.
        (squangle_mop_up): Set the numb and numk fields to zero.
        (work_stuff_copy_to_from): Handle the case where a btypevec or
        ktypevec field is NULL.
        (demangle_nested_args): Add recursion counter.  If
        the recursion limit is not disabled and reached, return with a
        failure result.

Modified:
    trunk/include/ChangeLog
    trunk/include/demangle.h
    trunk/libiberty/ChangeLog
    trunk/libiberty/cp-demangle.c
    trunk/libiberty/cp-demangle.h
    trunk/libiberty/cplus-dem.c
Reply | Threaded
Open this post in threaded view
|

[Bug demangler/87675] Stack Overflow in function next_is_type_qual() in cp-demangle.c, as demonstrated by "nm -C"

kargl at gcc dot gnu.org
In reply to this post by kargl at gcc dot gnu.org
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87675

Nick Clifton <nickc at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
                 CC|                            |nickc at gcc dot gnu.org
         Resolution|---                         |FIXED

--- Comment #6 from Nick Clifton <nickc at gcc dot gnu.org> ---
Fixed by commit 266886.