Proposed Patch for Bug 69687

Proposed Patch for Bug 69687

[Marcel Böhme]

Hi,

Please find attached the proposed patch for Bug 69687: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69687

* Limiting the length of the mangled string to 264k characters.
* Limiting the loop iterations to 256 (max. of C++ function parameters).

--- a/libiberty/cplus-dem.c
+++ b/libiberty/cplus-dem.c
@@ -847,6 +847,13 @@ 
 char *
 cplus_demangle (const char *mangled, int options)
 {
+  /** Limit the maximum length of mangled.
+   * C++ Std, Annex B (Implementation quantities): 
+   * - Number of characters in an internal identifier or macro name [1 024]. 
+   * - Arguments in one function call [256]. */ 
+  if (mangled && strlen (mangled) > 263168) 
+    return xstrdup (mangled);
+
   char *ret;
   struct work_stuff work[1];
@@ -4488,6 +4495,8 @@ 
            {
              return (0);
            }
+         /* C++ Standard Annex B: Parameters in one function definition [256].*/
+         if (r > 256) r = 256;
          while (work->nrepeats > 0 || --r >= 0)
            {
              tem = work -> typevec[t];

Best regards,
- Marcel

Re: Proposed Patch for Bug 69687

[Mike Stump]

On Mar 2, 2016, at 12:33 AM, Marcel Böhme <boehme.marcel@gmail.com> wrote:
> Please find attached the proposed patch for Bug 69687: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69687
> 
> * Limiting the length of the mangled string to 264k characters.

No.  This isn’t in the spirit of GNU software.

> * Limiting the loop iterations to 256 (max. of C++ function parameters).

No.

Instead, find the bit of the code that is wrong and fix that.  From the PR:

> The function string_need (cplus-dem.c:4751) checks whether sufficient memory is available to append size-of-arg more characters. If not, xrealloc decl with n=2*(length of decl + length of arg) characters. Since n is a signed int, n wraps over at some iteration.

So, check for overflow, or better use unsigned values that are large enough to never overflow.  With no possibility for overflow, you can then retest the bug and see if there are any other failure modes and fix those.

Re: Proposed Patch for Bug 69687

[Bernd Schmidt]

On 03/02/2016 06:22 PM, Mike Stump wrote:
>
> So, check for overflow, or better use unsigned values that are large
> enough to never overflow.  With no possibility for overflow, you can
> then retest the bug and see if there are any other failure modes and
> fix those.

What C standard can we assume for libiberty? I was looking at patching 
this and discovered that SIZE_MAX is defined only for C99, so I'm 
leaning towards retaining the ints and using INT_MAX.


Bernd

Re: Proposed Patch for Bug 69687

[Marcel Böhme]

Thanks Mike. I have revised the patch and removed the limits.

While perhaps less security critical, without the limits on the loop count (r) the test cases will still consume all your memory and effectively freeze GDB.

* Before any realloc, check for overflow.
* string_need now returns 1 if the allocation was successful.
* all clients of string_need refrain from extending the string anything if string_need was unsuccessful.

>  better use unsigned values that are large enough to never overflow. 
Throughout cplus-dem.c, the length of a string is measured as pointer difference. So, technically length is of type ptrdiff_t which is signed.

— a/libiberty/cplus-dem.c
+++ b/libiberty/cplus-dem.c
@@ -55,6 +55,7 @@
 void * malloc ();
 void * realloc ();
 #endif
+#include <limits.h>
 
 #include <demangle.h>
 #undef CURRENT_DEMANGLING_STYLE
@@ -379,7 +380,7 @@
 
 static int arm_special (const char **, string *);
 
-static void string_need (string *, int);
+static int string_need (string *, int);
 
 static void string_delete (string *);
 
@@ -4254,7 +4255,9 @@
        }
       else
        {
-         work -> typevec_size *= 2;
+         if (work -> typevec_size > INT_MAX / 2)
+            return;
+          work -> typevec_size *= 2;
          work -> typevec
            = XRESIZEVEC (char *, work->typevec, work->typevec_size);
        }
@@ -4281,7 +4284,9 @@
        }
       else
        {
-         work -> ksize *= 2;
+         if (work -> ksize > INT_MAX / 2)
+            return; 
+          work -> ksize *= 2;
          work -> ktypevec
            = XRESIZEVEC (char *, work->ktypevec, work->ksize);
        }
@@ -4294,7 +4299,8 @@
 
 /* Register a B code, and get an index for it. B codes are registered
    as they are seen, rather than as they are completed, so map<temp<char> >
-   registers map<temp<char> > as B0, and temp<char> as B1 */
+   registers map<temp<char> > as B0, and temp<char> as B1. Returns -1
+   if registration was unsuccessful. */
 
 static int
 register_Btype (struct work_stuff *work)
@@ -4310,7 +4316,9 @@
        }
       else
        {
-         work -> bsize *= 2;
+         if (work -> bsize > INT_MAX / 2)
+            return -1;
+          work -> bsize *= 2;
          work -> btypevec
            = XRESIZEVEC (char *, work->btypevec, work->bsize);
        }
@@ -4328,6 +4336,8 @@
 {
   char *tem;
 
+  if (index < 0)
+    return;
   tem = XNEWVEC (char, len + 1);
   memcpy (tem, start, len);
   tem[len] = '\0';
@@ -4591,7 +4601,8 @@
   const char *tem;
 
   string_appendn (declp, (*mangled), scan - (*mangled));
-  string_need (declp, 1);
+  if (! string_need (declp, 1))
+     return 0;
   *(declp -> p) = '\0';
 
   /* Consume the function name, including the "__" separating the name
@@ -4747,7 +4758,7 @@
 
 /* a mini string-handling package */
 
-static void
+static int 
 string_need (string *s, int n)
 {
   int tem;
@@ -4765,11 +4776,14 @@
     {
       tem = s->p - s->b;
       n += tem;
+      if ( n > INT_MAX / 2) 
+        return 0;
       n *= 2;
       s->b = XRESIZEVEC (char, s->b, n);
       s->p = s->b + tem;
       s->e = s->b + n;
     }
+    return 1;
 }
 
 static void
@@ -4811,7 +4825,8 @@
   if (s == NULL || *s == '\0')
     return;
   n = strlen (s);
-  string_need (p, n);
+  if (! string_need (p, n))
+    return;
   memcpy (p->p, s, n);
   p->p += n;
 }
@@ -4824,7 +4839,8 @@
   if (s->b != s->p)
     {
       n = s->p - s->b;
-      string_need (p, n);
+      if (! string_need (p, n))
+        return;
       memcpy (p->p, s->b, n);
       p->p += n;
     }
@@ -4835,7 +4851,8 @@
 {
   if (n != 0)
     {
-      string_need (p, n);
+      if (! string_need (p, n))
+        return;
       memcpy (p->p, s, n);
       p->p += n;
     }
@@ -4866,7 +4883,8 @@
 
   if (n != 0)
     {
-      string_need (p, n);
+      if (! string_need (p, n))
+        return;
       for (q = p->p - 1; q >= p->b; q--)
        {
          q[n] = q[0];

Re: Proposed Patch for Bug 69687

[Mike Stump]

On Mar 3, 2016, at 6:21 AM, Bernd Schmidt <bschmidt@redhat.com> wrote:
> What C standard can we assume for libiberty? I was looking at patching this and discovered that SIZE_MAX is defined only for C99, so I'm leaning towards retaining the ints and using INT_MAX.

As long as you don’t need a constant…  you can also do something like:

#ifndef SIZE_MAX
#define SIZE_MAX   (sizeof (size_t) == sizeof (int) ? INT_MAX : sizeof (size_t) == sizeof (long) ? LONG_MAX : (abort (), 0))
#endif

but, you need to consider the signedness of it.  A size bounded by int might be annoying if an int was 16 bits, but, we don’t care about such platforms hosting gcc, so, not a problem in reality.  Once we get to 32-biit (or more), we’re good.  No one better have a symbol >2 billion bytes.  And if they do, they can submit that patch to fix it in about 1000 years.  :-)  I think an INT_MAX only version is fine.

Re: Proposed Patch for Bug 69687

[Mike Stump]

On Mar 3, 2016, at 6:55 AM, Marcel Böhme <boehme.marcel@gmail.com> wrote:
> I have revised the patch and removed the limits.

I looked at the patch, I can find no more unreasonable limits!  Wonderful.  Hope someone will finish off the review and approve.

Re: Proposed Patch for Bug 69687

[Manuel López-Ibáñez]

On 03/03/16 14:21, Bernd Schmidt wrote:
> On 03/02/2016 06:22 PM, Mike Stump wrote:
>>
>> So, check for overflow, or better use unsigned values that are large
>> enough to never overflow.  With no possibility for overflow, you can
>> then retest the bug and see if there are any other failure modes and
>> fix those.
>
> What C standard can we assume for libiberty? I was looking@patching this and
> discovered that SIZE_MAX is defined only for C99, so I'm leaning towards
> retaining the ints and using INT_MAX.

Retaining INT_MAX should be ok in this case, since that should allow pretty 
large mangled strings. As far as I know, the only users of libiberty are GDB 
and GCC, and GDB only because they have not completely moved to gnulib yet. GCC 
is C++, GDB assumes C90 but it is moving to C++ anyway, so it could be bumped 
to SIZE_MAX later.

However, it would be much better to add to libiberty something like gnulib's 
x2realloc and x2nrealloc and use that because:

* It is more concise.
* Avoid duplication.
* libiberty should be replaced by gnulib eventually
* error-handling is shared with xrealloc, which gives both more consistency and 
more flexibility.

Of course, there is an even better fix: Add to the GCC repository enough gnulib 
modules to use directly the x2realloc from gnulib, make the demangler use that. 
GDB is already using some gnulib modules, so it should not be a problem for 
them. It is a bit more work in the short term, but re-implementing function by 
function a lower quality implementation of the whole gnulib seems much worse in 
the long run.

Cheers,

	Manuel.

Re: Proposed Patch for Bug 69687

[Bernd Schmidt]

On 03/03/2016 04:18 PM, Mike Stump wrote:
> On Mar 3, 2016, at 6:55 AM, Marcel Böhme <boehme.marcel@gmail.com> wrote:
>> I have revised the patch and removed the limits.
>
> I looked at the patch, I can find no more unreasonable limits!  Wonderful.  Hope someone will finish off the review and approve.

Marcel, if you haven't contributed before, we'll need a copyright 
assignment from you before we can accept the patch. Do you already have 
one on file?


Bernd

Re: Proposed Patch for Bug 69687

[Marcel Böhme]

On 4 Mar 2016, at 1:43 AM, Bernd Schmidt <bschmidt@redhat.com> wrote:
> 
> On 03/03/2016 04:18 PM, Mike Stump wrote:
>> On Mar 3, 2016, at 6:55 AM, Marcel Böhme <boehme.marcel@gmail.com> wrote:
>>> I have revised the patch and removed the limits.
>> 
>> I looked at the patch, I can find no more unreasonable limits!  Wonderful.  Hope someone will finish off the review and approve.
> 
> Marcel, if you haven't contributed before, we'll need a copyright assignment from you before we can accept the patch. Do you already have one on file?
> 
> 
> Bernd
> 


Hi Bernd, I have requested the disclaimer form as per /gd/gnuorg/Copyright/request-disclaim.changes

Thanks,
- Marcel

Re: Proposed Patch for Bug 69687

[Joseph Myers]

[-- Attachment #1: Type: text/plain, Size: 722 bytes --]

On Thu, 3 Mar 2016, Mike Stump wrote:

> On Mar 3, 2016, at 6:21 AM, Bernd Schmidt <bschmidt@redhat.com> wrote:
> > What C standard can we assume for libiberty? I was looking at patching this and discovered that SIZE_MAX is defined only for C99, so I'm leaning towards retaining the ints and using INT_MAX.
> 
> As long as you donÂ’t need a constantÂ…  you can also do something like:
> 
> #ifndef SIZE_MAX
> #define SIZE_MAX   (sizeof (size_t) == sizeof (int) ? INT_MAX : sizeof (size_t) == sizeof (long) ? LONG_MAX : (abort (), 0))
> #endif

If you don't require usability in #if (so can use casts), ((size_t) -1) 
suffices as a value of SIZE_MAX (size_t is always unsigned).

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: Proposed Patch for Bug 69687

[Marcel Böhme]

Hi Bernd: I submitted the filled disclaimer form on March 4th. Now, a representative of FSF mentioned that the copyright assignment is ready on their end.

Can someone please go ahead and review the patch?

Best regards,
- Marcel


> On 4 Mar 2016, at 1:43 AM, Bernd Schmidt <bschmidt@redhat.com> wrote:
> 
> On 03/03/2016 04:18 PM, Mike Stump wrote:
>> On Mar 3, 2016, at 6:55 AM, Marcel Böhme <boehme.marcel@gmail.com> wrote:
>>> I have revised the patch and removed the limits.
>> 
>> I looked at the patch, I can find no more unreasonable limits!  Wonderful.  Hope someone will finish off the review and approve.
> 
> Marcel, if you haven't contributed before, we'll need a copyright assignment from you before we can accept the patch. Do you already have one on file?
> 
> 
> Bernd
> 

Re: Proposed Patch for Bug 69687

[Bernd Schmidt]

On 03/03/2016 03:55 PM, Marcel Böhme wrote:
> @@ -4254,7 +4255,9 @@

Please use "diff -p" so that we get information about which function is 
being patched. Are all the places being patched really problematic ones 
where an input file could realistically cause an overflow, or just the 
string functions?

>          }
>         else
>          {
> -         work -> typevec_size *= 2;
> +         if (work -> typevec_size > INT_MAX / 2)
> +            return;

I'm concerned about just returning without any kind of error indication. 
Not sure what we should be calling from libiberty, but I was thinking 
maybe xmalloc_failed.

> @@ -4765,11 +4776,14 @@
>       {
>         tem = s->p - s->b;
>         n += tem;
> +      if ( n > INT_MAX / 2)
> +        return 0;
>         n *= 2;
>         s->b = XRESIZEVEC (char, s->b, n);
>         s->p = s->b + tem;
>         s->e = s->b + n;
>       }

Might also want to guard against overflow from the first addition.


Bernd

Re: Proposed Patch for Bug 69687

[Marcel Böhme]

Hi Bernd,

> Are all the places being patched really problematic ones where an input file could realistically cause an overflow, or just the string functions?
The loop in demangle_args allows to call the patched register*- and remember*-methods arbitrarily often. So, those should also overflow at some point.
Found a few other segmentation faults in libiberty that I’ll report and patch separately.

> I'm concerned about just returning without any kind of error indication. Not sure what we should be calling from libiberty, but I was thinking maybe xmalloc_failed.
Done. Now, clients of libiberty freeze for about 80 seconds and consume about 3GB of memory before exiting with "out of memory allocating 2147483647 bytes after a total of 3221147648 bytes”.

> Might also want to guard against overflow from the first addition.
Done.

Index: libiberty/cplus-dem.c
===================================================================
--- libiberty/cplus-dem.c	(revision 234607)
+++ libiberty/cplus-dem.c	(working copy)
@@ -55,6 +55,7 @@ Boston, MA 02110-1301, USA.  */
 void * malloc ();
 void * realloc ();
 #endif
+#include <limits.h>
 
 #include <demangle.h>
 #undef CURRENT_DEMANGLING_STYLE
@@ -4254,6 +4255,8 @@ remember_type (struct work_stuff *work, 
 	}
       else
 	{
+	  if (work -> typevec_size > INT_MAX / 2)
+	    xmalloc_failed (INT_MAX);
 	  work -> typevec_size *= 2;
 	  work -> typevec
 	    = XRESIZEVEC (char *, work->typevec, work->typevec_size);
@@ -4281,6 +4284,8 @@ remember_Ktype (struct work_stuff *work,
 	}
       else
 	{
+	  if (work -> ksize > INT_MAX / 2)
+	    xmalloc_failed (INT_MAX);
 	  work -> ksize *= 2;
 	  work -> ktypevec
 	    = XRESIZEVEC (char *, work->ktypevec, work->ksize);
@@ -4310,6 +4315,8 @@ register_Btype (struct work_stuff *work)
 	}
       else
 	{
+	  if (work -> bsize > INT_MAX / 2)
+	    xmalloc_failed (INT_MAX);
 	  work -> bsize *= 2;
 	  work -> btypevec
 	    = XRESIZEVEC (char *, work->btypevec, work->bsize);
@@ -4764,6 +4771,8 @@ string_need (string *s, int n)
   else if (s->e - s->p < n)
     {
       tem = s->p - s->b;
+      if (n > INT_MAX / 2 - tem)
+        xmalloc_failed (INT_MAX); 
       n += tem;
       n *= 2;
       s->b = XRESIZEVEC (char, s->b, n);

Re: Proposed Patch for Bug 69687

[Bernd Schmidt]

On 03/31/2016 06:56 AM, Marcel Böhme wrote:
> Hi Bernd,
>
>> Are all the places being patched really problematic ones where an input file could realistically cause an overflow, or just the string functions?
> The loop in demangle_args allows to call the patched register*- and remember*-methods arbitrarily often. So, those should also overflow at some point.
> Found a few other segmentation faults in libiberty that IÂ’ll report and patch separately.
>
>> I'm concerned about just returning without any kind of error indication. Not sure what we should be calling from libiberty, but I was thinking maybe xmalloc_failed.
> Done. Now, clients of libiberty freeze for about 80 seconds and consume about 3GB of memory before exiting with "out of memory allocating 2147483647 bytes after a total of 3221147648 bytes”.
>
>> Might also want to guard against overflow from the first addition.
> Done.

>
> Index: libiberty/cplus-dem.c
> ===================================================================
> --- libiberty/cplus-dem.c	(revision 234607)
> +++ libiberty/cplus-dem.c	(working copy)
> @@ -55,6 +55,7 @@ Boston, MA 02110-1301, USA.  */
>   void * malloc ();
>   void * realloc ();
>   #endif
> +#include <limits.h>
>
>   #include <demangle.h>
>   #undef CURRENT_DEMANGLING_STYLE

Forgot about this issue, sorry. At least this needs guarding with #ifdef 
HAVE_LIMITS_H, as in the other files in libiberty. Several of them also 
go to trouble to define the macros if limits.h is missing; not sure how 
much of an issue that is nowadays, but you might want to adapt something 
like the code from strtol.c:

#ifndef ULONG_MAX
#define ULONG_MAX       ((unsigned long)(~0L))          /* 0xFFFFFFFF */
#endif

#ifndef LONG_MAX
#define LONG_MAX        ((long)(ULONG_MAX >> 1))        /* 0x7FFFFFFF */
#endif

Mind trying that and doing a full test run as described in my other mail?


Bernd

Re: Proposed Patch for Bug 69687

[Marcel Böhme]

> 
> Forgot about this issue, sorry. At least this needs guarding with #ifdef HAVE_LIMITS_H, as in the other files in libiberty. Several of them also go to trouble to define the macros if limits.h is missing; not sure how much of an issue that is nowadays, but you might want to adapt something like the code from strtol.c:
> 
> #ifndef ULONG_MAX
> #define ULONG_MAX       ((unsigned long)(~0L))          /* 0xFFFFFFFF */
> #endif
> 
> #ifndef LONG_MAX
> #define LONG_MAX        ((long)(ULONG_MAX >> 1))        /* 0x7FFFFFFF */
> #endif
> 
> Mind trying that and doing a full test run as described in my other mail?

Regression tested on x86_64-pc-linux-gnu (make check). Checked PR69687 is resolved (via binutils); even for our definition of INT_MAX.
No test cases added since the test would take up to 2 minutes and end in xmalloc_failed even in the successful case.

Thanks,
- Marcel

--

Index: libiberty/cplus-dem.c
===================================================================
--- libiberty/cplus-dem.c	(revision 234663)
+++ libiberty/cplus-dem.c	(working copy)
@@ -56,6 +56,13 @@ void * malloc ();
 void * realloc ();
 #endif
 
+#ifdef HAVE_LIMITS_H
+#include <limits.h>
+#endif
+#ifndef INT_MAX
+# define INT_MAX       (int)(((unsigned int) ~0) >> 1)          /* 0x7FFFFFFF */ 
+#endif
+
 #include <demangle.h>
 #undef CURRENT_DEMANGLING_STYLE
 #define CURRENT_DEMANGLING_STYLE work->options
@@ -4256,6 +4263,8 @@ remember_type (struct work_stuff *work,
 	}
       else
 	{
+          if (work -> typevec_size > INT_MAX / 2)
+	    xmalloc_failed (INT_MAX);
 	  work -> typevec_size *= 2;
 	  work -> typevec
 	    = XRESIZEVEC (char *, work->typevec, work->typevec_size);
@@ -4283,6 +4292,8 @@ remember_Ktype (struct work_stuff *work,
 	}
       else
 	{
+          if (work -> ksize > INT_MAX / 2)
+	    xmalloc_failed (INT_MAX);
 	  work -> ksize *= 2;
 	  work -> ktypevec
 	    = XRESIZEVEC (char *, work->ktypevec, work->ksize);
@@ -4312,6 +4323,8 @@ register_Btype (struct work_stuff *work)
 	}
       else
 	{
+          if (work -> bsize > INT_MAX / 2)
+	    xmalloc_failed (INT_MAX);
 	  work -> bsize *= 2;
 	  work -> btypevec
 	    = XRESIZEVEC (char *, work->btypevec, work->bsize);
@@ -4766,6 +4779,8 @@ string_need (string *s, int n)
   else if (s->e - s->p < n)
     {
       tem = s->p - s->b;
+      if (n > INT_MAX / 2 - tem)
+        xmalloc_failed (INT_MAX); 
       n += tem;
       n *= 2;
       s->b = XRESIZEVEC (char, s->b, n);