RFA/RFC: Add stack recursion limit to libiberty's demangler

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

RFA/RFC: Add stack recursion limit to libiberty's demangler

Nick Clifton
Hi Ian,

  Libiberty's demangler seems to be a favourite target of people looking
  to file new CVEs by fuzzing strings and I have finally gotten tired of
  reviewing them all.  So I would like to propose a patch to add support
  for placing a recursion limit on the demangling functions.

  The patch adds a new demangling option - DMGL_RECURSE_LIMIT - which
  needs to be present in order for the new code to take affect.   So
  current users of the libiberty library will not be affected[*].
  The patch also adds a new function - cplus_demangle_set_recursion_limit()
  - which can be used to probe and/or set the limit.

  When the option is in effect a few of the demangler functions will use
  static counters to make sure that they have not been called
  recursively too many times.  I only chose those functions for which I
  could find filed PRs that triggered this kind of problem.  But with
  the stack limiting framework in place it would be easy to add checks
  to other functions, should they prove necessary.

  I also encountered one binary that could trigger stack exhaustion in
  d_demangle_callback where it tries to allocate stack space to hold
  component and substitution arrays.  So the patch includes a check
  for this situation as well.
 
  There does not appear to be any error reporting framework for the
  demangler functions, so when a recursion limit is reached the
  functions just return a failure/NULL result.

  I have tested the patch with a variety of different binutils builds
  and also bootstrapped an x86_64-pc-linux-gnu toolchain.  No new
  failures were found.

  What do you think, is this approach reasonable ?

Cheers
  Nick

[*] Actually I also have a patch for the binutils to modify the
addr2line, c++filt, nm and objdump programs to make use of this new
feature, should it be accepted into libiberty.

Patches:

include/ChangeLog
2018-11-29  Nick Clifton  <[hidden email]>

        * demangle.h (DMGL_RECURSE_LIMIT): Define.
        (cplus_demangle_set_recursion_limit): Prototype.

libiberty/ChangeLog
2018-11-29  Nick Clifton  <[hidden email]>

        PR 87675
        PR 87636
        * cp-demangle.c (demangle_recursion_limit): New static
        variable.
        (d_function_type): Add recursion counter.  If the recursion
        limit is enabled and reached, return with a failure result.
        (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_demangle_set_recursion): New function.  Sets and/or
        returns the current stack recursion limit.
        * cplus-dem.c (demangle_nested_args): Add recursion counter.  If
        the recursion limit is enabled and reached, return with a
        failure result.


diff --git a/include/demangle.h b/include/demangle.h
index b8d57cf295..426b5880aa 100644
--- a/include/demangle.h
+++ b/include/demangle.h
@@ -65,6 +65,8 @@ extern "C" {
 #define DMGL_DLANG (1 << 16)
 #define DMGL_RUST (1 << 17) /* Rust wraps GNU_V3 style mangling.  */
 
+#define DMGL_RECURSE_LIMIT (1 << 18) /* Enable limits on the depth of recursion in mangled strings.  */
+
 /* If none of these are set, use 'current_demangling_style' as the default. */
 #define DMGL_STYLE_MASK (DMGL_AUTO|DMGL_GNU|DMGL_LUCID|DMGL_ARM|DMGL_HP|DMGL_EDG|DMGL_GNU_V3|DMGL_JAVA|DMGL_GNAT|DMGL_DLANG|DMGL_RUST)
 
@@ -716,6 +718,15 @@ cplus_demangle_print_callback (int options,
                                struct demangle_component *tree,
                                demangle_callbackref callback, void *opaque);
 
+/* Set a limit on the amount of recursion allowed in mangled strings.
+   Only effective if the DMGL_RECURSE_LIMIT option has been set.
+   Returns the previous value of the recursion limit.
+   Ignores settings a limit of 0 or 1.
+   Note - setting the limit is not a thread-safe operation.  */
+
+extern unsigned long
+cplus_demangle_set_recursion_limit (unsigned long limit);
+  
 #ifdef __cplusplus
 }
 #endif /* __cplusplus */
diff --git a/libiberty/cp-demangle.c b/libiberty/cp-demangle.c
index 3f2a097e7f..a6aeac58a3 100644
--- a/libiberty/cp-demangle.c
+++ b/libiberty/cp-demangle.c
@@ -568,6 +568,11 @@ static int d_demangle_callback (const char *, int,
                                 demangle_callbackref, void *);
 static char *d_demangle (const char *, int, size_t *);
 
+/* A limit on the amount of recursion allowed in mangled strings.
+   Only effective if the DMGL_RECURSE_LIMIT option has been set.
+   The initial value of 1024 is an arbitrary choice.  */
+static unsigned long demangle_recursion_limit = 1024;
+
 #define FNQUAL_COMPONENT_CASE \
     case DEMANGLE_COMPONENT_RESTRICT_THIS: \
     case DEMANGLE_COMPONENT_VOLATILE_THIS: \
@@ -2843,21 +2848,34 @@ d_ref_qualifier (struct d_info *di, struct demangle_component *sub)
 static struct demangle_component *
 d_function_type (struct d_info *di)
 {
-  struct demangle_component *ret;
+  static unsigned long recursion_level = 0;
+  struct demangle_component *ret = NULL;
 
-  if (! d_check_char (di, 'F'))
-    return NULL;
-  if (d_peek_char (di) == 'Y')
+  if ((di->options & DMGL_RECURSE_LIMIT)
+      && recursion_level > demangle_recursion_limit)
     {
-      /* Function has C linkage.  We don't print this information.
- FIXME: We should print it in verbose mode.  */
-      d_advance (di, 1);
+      /* FIXME: There ought to be a way to report that the recursion limit
+ has been reached.  */
+      return NULL;
     }
-  ret = d_bare_function_type (di, 1);
-  ret = d_ref_qualifier (di, ret);
 
-  if (! d_check_char (di, 'E'))
-    return NULL;
+  recursion_level ++;
+  if (d_check_char (di, 'F'))
+    {
+      if (d_peek_char (di) == 'Y')
+ {
+  /* Function has C linkage.  We don't print this information.
+     FIXME: We should print it in verbose mode.  */
+  d_advance (di, 1);
+ }
+      ret = d_bare_function_type (di, 1);
+      ret = d_ref_qualifier (di, ret);
+      
+      if (! d_check_char (di, 'E'))
+ ret = NULL;
+    }
+
+  recursion_level --;
   return ret;
 }
 
@@ -6227,6 +6246,20 @@ d_demangle_callback (const char *mangled, int options,
 
   cplus_demangle_init_info (mangled, options, strlen (mangled), &di);
 
+  /* PR 87675 - Check for a mangled string that is so long
+     that we do not have enough stack space to demangle it.  */
+  if ((options & DMGL_RECURSE_LIMIT)
+      /* This check is a bit arbitrary, since what we really want to do is to
+ compare the sizes of the di.comps and di.subs arrays against the
+ amount of stack space remaining.  But there is no portable way to do
+ this, so instead we use the recursion limit as a guide to the maximum
+ size of the arrays.  */
+      && di.num_comps > demangle_recursion_limit)
+    {
+      /* FIXME: We need a way to indicate that a stack limit has been reached.  */
+      return 0;
+    }
+
   {
 #ifdef CP_DYNAMIC_ARRAYS
     __extension__ struct demangle_component comps[di.num_comps];
@@ -6309,6 +6342,22 @@ d_demangle (const char *mangled, int options, size_t *palc)
   return dgs.buf;
 }
 
+/* Set a limit on the amount of recursion allowed in mangled strings.
+   Only effective if the DMGL_RECURSE_LIMIT option has been set.
+   Returns the previous value of the recursion limit.
+   Ignores settings a limit of 0 or 1.
+   Note - setting the limit is not a thread-safe operation.  */
+
+unsigned long
+cplus_demangle_set_recursion_limit (unsigned long limit)
+{
+  unsigned long result = demangle_recursion_limit;
+
+  if (limit > 1)
+    demangle_recursion_limit = limit;
+  return result;
+}
+
 #if defined(IN_LIBGCC2) || defined(IN_GLIBCPP_V3)
 
 extern char *__cxa_demangle (const char *, char *, size_t *, int *);
diff --git a/libiberty/cplus-dem.c b/libiberty/cplus-dem.c
index 6d58bd899b..5b97b8de7b 100644
--- a/libiberty/cplus-dem.c
+++ b/libiberty/cplus-dem.c
@@ -4692,10 +4692,21 @@ static int
 demangle_nested_args (struct work_stuff *work, const char **mangled,
                       string *declp)
 {
+  static unsigned long recursion_level = 0;
   string* saved_previous_argument;
   int result;
   int saved_nrepeats;
 
+  if ((work->options & DMGL_RECURSE_LIMIT)
+      && recursion_level > cplus_demangle_set_recursion_limit (0))
+    {
+      /* FIXME: There ought to be a way to report that the recursion limit
+ has been reached.  */
+      return 0;
+    }
+
+  recursion_level ++;
+
   /* The G++ name-mangling algorithm does not remember types on nested
      argument lists, unless -fsquangling is used, and in that case the
      type vector updated by remember_type is not used.  So, we turn
@@ -4722,6 +4733,7 @@ demangle_nested_args (struct work_stuff *work, const char **mangled,
   --work->forgetting_types;
   work->nrepeats = saved_nrepeats;
 
+  --recursion_level;
   return result;
 }
 


binutils/ChangeLog
2018-11-29  Nick Clifton  <[hidden email]>

        * addr2line.c (demangle_flags): New static variable.
        (long_options): Add --recurse-limit.
        (translate_address): Pass demangle_flags to bfd_demangle.
        (main): Handle --recuse-limit option.
        * cxxfilt.c (flags): Add DMGL_RECURSE_LIMIT.
        (long_options): Add --recurse-limit.
        (main): Handle --recuse-limit option.
        * dlltool.c (gen_def_file): Include DMGL_RECURSE_LIMIT in flags
        passed to cplus_demangle.
        * nm.c (demangle_flags): New static variable.
        (long_options): Add --recurse-limit.
        (main): Handle --recurse-limit.
        * objdump.c (demangle_flags): New static variable.
        (usage): Add --recurse-limit.
        (long_options): Add --recurse-limit.
        (objdump_print_symname): Pass demangle_flags to bfd_demangle.
        (disassemble_section): Likewise.
        (dump_dymbols): Likewise.
        (main): Handle --recurse-limit.
        * prdbg.c (demangle_flags): New static variable.
        (tg_variable): Pass demangle_flags to demangler.
        (tg_start_function): Likewise.
        * stabs.c (demangle_flags): New static variable.
        (stab_demangle_template): Pass demangle_flags to demangler.
        (stab_demangle_v3_argtypes): Likewise.
        (stab_demangle_v3_arg): Likewise.
        * doc/binutuls.texi: Document new command line options.
        * NEWS: Mention the new feature.
        * testsuite/config/default.exp (CXXFILT): Define if not already
        defined.
        (CXXFILTFLAGS): Likewise.
        * testsuite/binutils-all/cxxfilt.exp: New file.  Runs a few
        simple tests of the cxxfilt program.


diff --git a/binutils/NEWS b/binutils/NEWS
index a3ee86ef7f..ce236e5a31 100644
--- a/binutils/NEWS
+++ b/binutils/NEWS
@@ -1,5 +1,10 @@
 -*- text -*-
 
+* The addr2line, c++filt, nm and objdump tools now have a limit on the maximum amount of recursion
+  that is allowed whilst demangling strings.  The default value for this
+  limit is 1024.  The --recurse-limit=N option can be used to change the
+  limit, or remove it entirely if N is zero.
+
 * Objdump's --disassemble option can now take a parameter, specifying the
   starting symbol for disassembly.  Disassembly will continue from this
   symbol up to the next symbol.
diff --git a/binutils/addr2line.c b/binutils/addr2line.c
index 008e62026e..822f990bad 100644
--- a/binutils/addr2line.c
+++ b/binutils/addr2line.c
@@ -45,6 +45,9 @@ static bfd_boolean do_demangle; /* -C, demangle names.  */
 static bfd_boolean pretty_print; /* -p, print on one line.  */
 static bfd_boolean base_names; /* -s, strip directory names.  */
 
+/* Flags passed to the name demangler.  */
+static int demangle_flags = DMGL_PARAMS | DMGL_ANSI | DMGL_RECURSE_LIMIT;
+
 static int naddr; /* Number of addresses to process.  */
 static char **addr; /* Hex addresses to process.  */
 
@@ -59,6 +62,8 @@ static struct option long_options[] =
   {"functions", no_argument, NULL, 'f'},
   {"inlines", no_argument, NULL, 'i'},
   {"pretty-print", no_argument, NULL, 'p'},
+  {"recurse-limit", required_argument, NULL, 'r'},
+  {"recursion-limit", required_argument, NULL, 'r'},  
   {"section", required_argument, NULL, 'j'},
   {"target", required_argument, NULL, 'b'},
   {"help", no_argument, NULL, 'H'},
@@ -91,6 +96,7 @@ usage (FILE *stream, int status)
   -s --basenames         Strip directory names\n\
   -f --functions         Show function names\n\
   -C --demangle[=style]  Demangle function names\n\
+  -r --recurse-limit=<N> Set the recursion limit for name demangling\n\
   -h --help              Display this information\n\
   -v --version           Display the program's version\n\
 \n"));
@@ -289,7 +295,7 @@ translate_addresses (bfd *abfd, asection *section)
                     name = "??";
                   else if (do_demangle)
                     {
-                      alloc = bfd_demangle (abfd, name, DMGL_ANSI | DMGL_PARAMS);
+                      alloc = bfd_demangle (abfd, name, demangle_flags);
                       if (alloc != NULL)
                         name = alloc;
                     }
@@ -442,7 +448,7 @@ main (int argc, char **argv)
   file_name = NULL;
   section_name = NULL;
   target = NULL;
-  while ((c = getopt_long (argc, argv, "ab:Ce:sfHhij:pVv", long_options, (int *) 0))
+  while ((c = getopt_long (argc, argv, "ab:Ce:r:sfHhij:pVv", long_options, (int *) 0))
  != EOF)
     {
       switch (c)
@@ -469,6 +475,18 @@ main (int argc, char **argv)
       cplus_demangle_set_style (style);
     }
   break;
+ case 'r':
+  {
+    unsigned long limit = strtoul (optarg, NULL, 0);
+    if (limit > 1)
+      {
+ cplus_demangle_set_recursion_limit (limit);
+ demangle_flags |= DMGL_RECURSE_LIMIT;
+      }
+    else
+      demangle_flags &= ~ DMGL_RECURSE_LIMIT;
+  }
+  break;
  case 'e':
   file_name = optarg;
   break;
diff --git a/binutils/cxxfilt.c b/binutils/cxxfilt.c
index e7272445c9..f5a23a3cc7 100644
--- a/binutils/cxxfilt.c
+++ b/binutils/cxxfilt.c
@@ -29,7 +29,7 @@
 #include "safe-ctype.h"
 #include "bucomm.h"
 
-static int flags = DMGL_PARAMS | DMGL_ANSI | DMGL_VERBOSE;
+static int flags = DMGL_PARAMS | DMGL_ANSI | DMGL_VERBOSE | DMGL_RECURSE_LIMIT;
 static int strip_underscore = TARGET_PREPENDS_UNDERSCORE;
 
 static const struct option long_options[] =
@@ -42,6 +42,8 @@ static const struct option long_options[] =
   {"no-verbose", no_argument, NULL, 'i'},
   {"types", no_argument, NULL, 't'},
   {"version", no_argument, NULL, 'v'},
+  {"recurse-limit", required_argument, NULL, 'r'},
+  {"recursion-limit", required_argument, NULL, 'r'},
   {NULL, no_argument, NULL, 0}
 };
 
@@ -102,6 +104,7 @@ Options are:\n\
   fprintf (stream, "\
   [-p|--no-params]            Do not display function arguments\n\
   [-i|--no-verbose]           Do not show implementation details (if any)\n\
+  [-r|--recurse-limit <N>]    Set recursion limit to <N>.  [Default 1024]\n\
   [-t|--types]                Also attempt to demangle type encodings\n\
   [-s|--format ");
   print_demangler_list (stream);
@@ -180,7 +183,7 @@ main (int argc, char **argv)
 
   expandargv (&argc, &argv);
 
-  while ((c = getopt_long (argc, argv, "_hinps:tv", long_options, (int *) 0)) != EOF)
+  while ((c = getopt_long (argc, argv, "_hinpr:s:tv", long_options, (int *) 0)) != EOF)
     {
       switch (c)
  {
@@ -195,6 +198,18 @@ main (int argc, char **argv)
  case 'p':
   flags &= ~ DMGL_PARAMS;
   break;
+ case 'r':
+  {
+    unsigned long limit = strtoul (optarg, NULL, 0);
+    if (limit > 1)
+      {
+ cplus_demangle_set_recursion_limit (limit);
+ flags |= DMGL_RECURSE_LIMIT;
+      }
+    else
+      flags &= ~ DMGL_RECURSE_LIMIT;
+  }
+  break;
  case 't':
   flags |= DMGL_TYPES;
   break;
diff --git a/binutils/dlltool.c b/binutils/dlltool.c
index 2c751241f1..963d541b8e 100644
--- a/binutils/dlltool.c
+++ b/binutils/dlltool.c
@@ -1802,7 +1802,7 @@ gen_def_file (void)
   for (i = 0, exp = d_exports; exp; i++, exp = exp->next)
     {
       char *quote = strchr (exp->name, '.') ? "\"" : "";
-      char *res = cplus_demangle (exp->internal_name, DMGL_ANSI | DMGL_PARAMS);
+      char *res = cplus_demangle (exp->internal_name, DMGL_ANSI | DMGL_PARAMS | DMGL_RECURSE_LIMIT);
 
       if (res)
  {
diff --git a/binutils/doc/binutils.texi b/binutils/doc/binutils.texi
index 9954adf484..ac10d582ce 100644
--- a/binutils/doc/binutils.texi
+++ b/binutils/doc/binutils.texi
@@ -769,7 +769,8 @@ nm [@option{-A}|@option{-o}|@option{--print-file-name}] [@option{-a}|@option{--d
    [@option{-s}|@option{--print-armap}] [@option{-t} @var{radix}|@option{--radix=}@var{radix}]
    [@option{-u}|@option{--undefined-only}] [@option{-V}|@option{--version}]
    [@option{-X 32_64}] [@option{--defined-only}] [@option{--no-demangle}]
-   [@option{--plugin} @var{name}] [@option{--size-sort}] [@option{--special-syms}]
+   [@option{--plugin} @var{name}] [@option{--recurse-limit=}@var{N}]
+   [@option{--size-sort}] [@option{--special-syms}]
    [@option{--synthetic}] [@option{--with-symbol-versions}] [@option{--target=}@var{bfdname}]
    [@var{objfile}@dots{}]
 @c man end
@@ -939,6 +940,17 @@ for more information on demangling.
 @item --no-demangle
 Do not demangle low-level symbol names.  This is the default.
 
+@item --recurse-limit=@var{N}
+@itemx --recursion-limit @var{N}
+Sets a limit on the amount of recursion performed whilst demangling
+strings.  Since the name mangling formats allow for an inifinite
+level of recursion it is possible to create strings whose decoding
+will exhaust the amount of stack space available on the host machine,
+triggering a memory fault.  The limit tries to prevent this from
+happening by restricting recursion to a maximum amount.  The default
+value for this limit is 1024.  To disable the limit set its value to
+0.
+
 @item -D
 @itemx --dynamic
 @cindex dynamic symbols
@@ -2098,6 +2110,7 @@ objdump [@option{-a}|@option{--archive-headers}]
         [@option{--adjust-vma=}@var{offset}]
         [@option{--dwarf-depth=@var{n}}]
         [@option{--dwarf-start=@var{n}}]
+        [@option{--recurse-limit=@var{n}}]
         [@option{--special-syms}]
         [@option{--prefix=}@var{prefix}]
         [@option{--prefix-strip=}@var{level}]
@@ -2174,6 +2187,17 @@ mangling styles. The optional demangling style argument can be used to
 choose an appropriate demangling style for your compiler. @xref{c++filt},
 for more information on demangling.
 
+@item --recurse-limit=@var{N}
+@itemx --recursion-limit @var{N}
+Sets a limit on the amount of recursion performed whilst demangling
+strings.  Since the name mangling formats allow for an inifinite
+level of recursion it is possible to create strings whose decoding
+will exhaust the amount of stack space available on the host machine,
+triggering a memory fault.  The limit tries to prevent this from
+happening by restricting recursion to a maximum amount.  The default
+value for this limit is 1024.  To disable the limit set its value to
+0.
+
 @item -g
 @itemx --debugging
 Display debugging information.  This attempts to parse STABS
@@ -3403,6 +3427,7 @@ c++filt [@option{-_}|@option{--strip-underscore}]
         [@option{-p}|@option{--no-params}]
         [@option{-t}|@option{--types}]
         [@option{-i}|@option{--no-verbose}]
+        [@option{-r} @var{N}|@option{--recurse-limit=}@var{N}]
         [@option{-s} @var{format}|@option{--format=}@var{format}]
         [@option{--help}]  [@option{--version}]  [@var{symbol}@dots{}]
 @c man end
@@ -3507,6 +3532,18 @@ demangled to ``signed char''.
 Do not include implementation details (if any) in the demangled
 output.
 
+@item -r @var{N}
+@itemx --recurse-limit=@var{N}
+@itemx --recursion-limit @var{N}
+Sets a limit on the amount of recursion performed whilst demangling
+strings.  Since the name mangling formats allow for an inifinite
+level of recursion it is possible to create strings whose decoding
+will exhaust the amount of stack space available on the host machine,
+triggering a memory fault.  The limit tries to prevent this from
+happening by restricting recursion to a maximum amount.  The default
+value for this limit is 1024.  To disable the limit set its value to
+0.
+
 @item -s @var{format}
 @itemx --format=@var{format}
 @command{c++filt} can decode various methods of mangling, used by
@@ -3580,6 +3617,7 @@ c++filt @var{option} @var{symbol}
 addr2line [@option{-a}|@option{--addresses}]
           [@option{-b} @var{bfdname}|@option{--target=}@var{bfdname}]
           [@option{-C}|@option{--demangle}[=@var{style}]]
+          [@option{-r} @var{N}|@option{--recurse-limit=}@var{N}]
           [@option{-e} @var{filename}|@option{--exe=}@var{filename}]
           [@option{-f}|@option{--functions}] [@option{-s}|@option{--basename}]
           [@option{-i}|@option{--inlines}]
@@ -3705,6 +3743,22 @@ Read offsets relative to the specified section instead of absolute addresses.
 Make the output more human friendly: each location are printed on one line.
 If option @option{-i} is specified, lines for all enclosing scopes are
 prefixed with @samp{(inlined by)}.
+
+@item -r @var{N}
+@itemx --recurse-limit=@var{N}
+@itemx --recursion-limit @var{N}
+Sets a limit on the amount of recursion performed whilst demangling
+strings.  Since the name mangling formats allow for an inifinite
+level of recursion it is possible to create strings whose decoding
+will exhaust the amount of stack space available on the host machine,
+triggering a memory fault.  The limit tries to prevent this from
+happening by restricting recursion to a maximum amount.  The default
+value for this limit is 1024.  To disable the limit set its value to
+0.
+
+Note this option is only effective if the @option{-C} or
+@option{--demangle} option has been enabled.
+
 @end table
 
 @c man end
diff --git a/binutils/nm.c b/binutils/nm.c
index bc4fccb5fc..e26a88afc5 100644
--- a/binutils/nm.c
+++ b/binutils/nm.c
@@ -162,6 +162,8 @@ static int line_numbers = 0; /* Print line numbers for symbols.  */
 static int allow_special_symbols = 0;  /* Allow special symbols.  */
 static int with_symbol_versions = 0; /* Include symbol version information in the output.  */
 
+static int demangle_flags = DMGL_ANSI | DMGL_PARAMS | DMGL_RECURSE_LIMIT;
+
 /* When to print the names of files.  Not mutually exclusive in SYSV format.  */
 static int filename_per_file = 0; /* Once per file, on its own line.  */
 static int filename_per_symbol = 0; /* Once per symbol, at start of line.  */
@@ -194,9 +196,13 @@ static const char *plugin_target = NULL;
 static bfd *lineno_cache_bfd;
 static bfd *lineno_cache_rel_bfd;
 
-#define OPTION_TARGET 200
-#define OPTION_PLUGIN (OPTION_TARGET + 1)
-#define OPTION_SIZE_SORT (OPTION_PLUGIN + 1)
+enum long_option_values
+{
+  OPTION_TARGET = 200,
+  OPTION_PLUGIN,
+  OPTION_SIZE_SORT,
+  OPTION_RECURSE_LIMIT
+};
 
 static struct option long_options[] =
 {
@@ -217,6 +223,8 @@ static struct option long_options[] =
   {"print-file-name", no_argument, 0, 'o'},
   {"print-size", no_argument, 0, 'S'},
   {"radix", required_argument, 0, 't'},
+  {"recurse-limit", required_argument, NULL, OPTION_RECURSE_LIMIT},
+  {"recursion-limit", required_argument, NULL, OPTION_RECURSE_LIMIT},
   {"reverse-sort", no_argument, &reverse_sort, 1},
   {"size-sort", no_argument, 0, OPTION_SIZE_SORT},
   {"special-syms", no_argument, &allow_special_symbols, 1},
@@ -245,6 +253,7 @@ usage (FILE *stream, int status)
                           `gnu', `lucid', `arm', `hp', `edg', `gnu-v3', `java'\n\
                           or `gnat'\n\
       --no-demangle      Do not demangle low-level symbol names\n\
+      --recurse-limit=N  Set demangling recursion limit to N.  [Default 1024]\n\
   -D, --dynamic          Display dynamic symbols instead of normal symbols\n\
       --defined-only     Display only defined symbols\n\
   -e                     (ignored)\n\
@@ -407,7 +416,7 @@ print_symname (const char *form, const char *name, bfd *abfd)
 {
   if (do_demangle && *name)
     {
-      char *res = bfd_demangle (abfd, name, DMGL_ANSI | DMGL_PARAMS);
+      char *res = bfd_demangle (abfd, name, demangle_flags);
 
       if (res != NULL)
  {
@@ -1687,6 +1696,18 @@ main (int argc, char **argv)
       cplus_demangle_set_style (style);
     }
   break;
+ case OPTION_RECURSE_LIMIT:
+  {
+    unsigned long limit = strtoul (optarg, NULL, 0);
+    if (limit > 1)
+      {
+ cplus_demangle_set_recursion_limit (limit);
+ demangle_flags |= DMGL_RECURSE_LIMIT;
+      }
+    else
+      demangle_flags &= ~ DMGL_RECURSE_LIMIT;
+  }
+  break;
  case 'D':
   dynamic = 1;
   break;
diff --git a/binutils/objdump.c b/binutils/objdump.c
index 21f1284319..e275f6f06d 100644
--- a/binutils/objdump.c
+++ b/binutils/objdump.c
@@ -120,6 +120,8 @@ static size_t prefix_length;
 static bfd_boolean unwind_inlines; /* --inlines.  */
 static const char * disasm_sym; /* Disassembly start symbol.  */
 
+static int demangle_flags = DMGL_ANSI | DMGL_PARAMS | DMGL_RECURSE_LIMIT;
+
 /* A structure to record the sections mentioned in -j switches.  */
 struct only
 {
@@ -252,6 +254,7 @@ usage (FILE *stream, int status)
                                   The STYLE, if specified, can be `auto', `gnu',\n\
                                   `lucid', `arm', `hp', `edg', `gnu-v3', `java'\n\
                                   or `gnat'\n\
+      --recurse-limit=N          Set demangling recursion limit to N.  [Default 1024]\n\
   -w, --wide                     Format output for more than 80 columns\n\
   -z, --disassemble-zeroes       Do not skip blocks of zeroes when disassembling\n\
       --start-address=ADDR       Only process data whose address is >= ADDR\n\
@@ -302,6 +305,7 @@ enum option_values
     OPTION_DWARF_DEPTH,
     OPTION_DWARF_CHECK,
     OPTION_DWARF_START,
+    OPTION_RECURSE_LIMIT,
     OPTION_INLINES
   };
 
@@ -333,6 +337,8 @@ static struct option long_options[]=
   {"line-numbers", no_argument, NULL, 'l'},
   {"no-show-raw-insn", no_argument, &show_raw_insn, -1},
   {"prefix-addresses", no_argument, &prefix_addresses, 1},
+  {"recurse-limit", required_argument, NULL, OPTION_RECURSE_LIMIT},
+  {"recursion-limit", required_argument, NULL, OPTION_RECURSE_LIMIT},
   {"reloc", no_argument, NULL, 'r'},
   {"section", required_argument, NULL, 'j'},
   {"section-headers", no_argument, NULL, 'h'},
@@ -884,7 +890,7 @@ objdump_print_symname (bfd *abfd, struct disassemble_info *inf,
   if (do_demangle && name[0] != '\0')
     {
       /* Demangle the name.  */
-      alloc = bfd_demangle (abfd, name, DMGL_ANSI | DMGL_PARAMS);
+      alloc = bfd_demangle (abfd, name, demangle_flags);
       if (alloc != NULL)
  name = alloc;
     }
@@ -2290,7 +2296,7 @@ disassemble_section (bfd *abfd, asection *section, void *inf)
   if (do_demangle && name[0] != '\0')
     {
       /* Demangle the name.  */
-      alloc = bfd_demangle (abfd, name, DMGL_ANSI | DMGL_PARAMS);
+      alloc = bfd_demangle (abfd, name, demangle_flags);
       if (alloc != NULL)
  name = alloc;
     }
@@ -3268,7 +3274,7 @@ dump_symbols (bfd *abfd ATTRIBUTE_UNUSED, bfd_boolean dynamic)
       /* If we want to demangle the name, we demangle it
  here, and temporarily clobber it while calling
  bfd_print_symbol.  FIXME: This is a gross hack.  */
-      alloc = bfd_demangle (cur_bfd, name, DMGL_ANSI | DMGL_PARAMS);
+      alloc = bfd_demangle (cur_bfd, name, demangle_flags);
       if (alloc != NULL)
  (*current)->name = alloc;
       bfd_print_symbol (cur_bfd, stdout, *current,
@@ -3927,6 +3933,18 @@ main (int argc, char **argv)
       cplus_demangle_set_style (style);
     }
   break;
+ case OPTION_RECURSE_LIMIT:
+  {
+    unsigned long limit = strtoul (optarg, NULL, 0);
+    if (limit > 1)
+      {
+ cplus_demangle_set_recursion_limit (limit);
+ demangle_flags |= DMGL_RECURSE_LIMIT;
+      }
+    else
+      demangle_flags &= ~ DMGL_RECURSE_LIMIT;
+  }
+  break;
  case 'w':
   do_wide = wide_output = TRUE;
   break;
diff --git a/binutils/prdbg.c b/binutils/prdbg.c
index 4b9fa06c26..c981555521 100644
--- a/binutils/prdbg.c
+++ b/binutils/prdbg.c
@@ -286,6 +286,8 @@ static const struct debug_write_fns tg_fns =
   pr_end_function, /* Same, does nothing.  */
   tg_lineno
 };
+
+static int demangle_flags = DMGL_ANSI | DMGL_PARAMS | DMGL_RECURSE_LIMIT;
 
 /* Print out the generic debugging information recorded in dhandle.  */
 
@@ -2600,7 +2602,7 @@ tg_variable (void *p, const char *name, enum debug_var_kind kind,
 
   dname = NULL;
   if (info->demangler)
-    dname = info->demangler (info->abfd, name, DMGL_ANSI | DMGL_PARAMS);
+    dname = info->demangler (info->abfd, name, demangle_flags);
 
   from_class = NULL;
   if (dname != NULL)
@@ -2661,7 +2663,7 @@ tg_start_function (void *p, const char *name, bfd_boolean global)
 
   dname = NULL;
   if (info->demangler)
-    dname = info->demangler (info->abfd, name, DMGL_ANSI | DMGL_PARAMS);
+    dname = info->demangler (info->abfd, name, demangle_flags);
 
   if (! substitute_type (info, dname ? dname : name))
     return FALSE;
diff --git a/binutils/stabs.c b/binutils/stabs.c
index bf53607560..dcd2aba57f 100644
--- a/binutils/stabs.c
+++ b/binutils/stabs.c
@@ -215,6 +215,8 @@ static debug_type stab_demangle_v3_arg
   (void *, struct stab_handle *, struct demangle_component *, debug_type,
    bfd_boolean *);
 
+static int demangle_flags = DMGL_ANSI | DMGL_RECURSE_LIMIT;
+
 /* Save a string in memory.  */
 
 static char *
@@ -4517,7 +4519,7 @@ stab_demangle_template (struct stab_demangle_info *minfo, const char **pp,
 
       free (s1);
 
-      s3 = cplus_demangle (s2, DMGL_ANSI);
+      s3 = cplus_demangle (s2, demangle_flags);
 
       free (s2);
 
@@ -5243,7 +5245,7 @@ stab_demangle_v3_argtypes (void *dhandle, struct stab_handle *info,
   void *mem;
   debug_type *pargs;
 
-  dc = cplus_demangle_v3_components (physname, DMGL_PARAMS | DMGL_ANSI, &mem);
+  dc = cplus_demangle_v3_components (physname, DMGL_PARAMS | demangle_flags, &mem);
   if (dc == NULL)
     {
       stab_bad_demangle (physname);
@@ -5418,7 +5420,7 @@ stab_demangle_v3_arg (void *dhandle, struct stab_handle *info,
  /* We print this component to get a class name which we can
    use.  FIXME: This probably won't work if the template uses
    template parameters which refer to an outer template.  */
- p = cplus_demangle_print (DMGL_PARAMS | DMGL_ANSI, dc, 20, &alc);
+ p = cplus_demangle_print (DMGL_PARAMS | demangle_flags, dc, 20, &alc);
  if (p == NULL)
   {
     fprintf (stderr, _("Failed to print demangled template\n"));
@@ -5498,7 +5500,7 @@ stab_demangle_v3_arg (void *dhandle, struct stab_handle *info,
  /* We print this component in order to find out the type name.
    FIXME: Should we instead expose the
    demangle_builtin_type_info structure?  */
- p = cplus_demangle_print (DMGL_PARAMS | DMGL_ANSI, dc, 20, &alc);
+ p = cplus_demangle_print (DMGL_PARAMS | demangle_flags, dc, 20, &alc);
  if (p == NULL)
   {
     fprintf (stderr, _("Couldn't get demangled builtin type\n"));
diff --git a/binutils/testsuite/config/default.exp b/binutils/testsuite/config/default.exp
index b34e45cd20..9ecfcf3e15 100644
--- a/binutils/testsuite/config/default.exp
+++ b/binutils/testsuite/config/default.exp
@@ -93,6 +93,12 @@ if ![info exists WINDRES] then {
 if ![info exists DLLTOOL] then {
     set DLLTOOL [findfile $base_dir/dlltool]
 }
+if ![info exists CXXFILT] then {
+    set CXXFILT [findfile $base_dir/cxxfilt]
+}
+if ![info exists CXXFILTFLAGS] then {
+    set CXXFILTFLAGS ""
+}
 
 if ![file isdirectory tmpdir] {catch "exec mkdir tmpdir" status}
 
--- /dev/null 2018-11-29 08:15:54.667999248 +0000
+++ binutils/testsuite/binutils-all/cxxfilt.exp 2018-11-29 13:09:29.789147447 +0000
@@ -0,0 +1,44 @@
+#   Copyright (C) 2018 Free Software Foundation, Inc.
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA.
+
+proc test_cxxfilt {options mangled_string demangled_string} {
+    global CXXFILT
+    global CXXFILTFLAGS
+    
+    set testname "cxxfilt: demangling $mangled_string"
+    set got [binutils_run $CXXFILT "$options $CXXFILTFLAGS $mangled_string"]
+
+    if ![regexp $demangled_string $got] then {
+ fail "$testname"
+ verbose 0 "expected: $demangled_string"
+ return
+    }
+
+    pass $testname
+}
+
+# Mangled and demangled strings stolen from libiberty/testsuite/demangle-expected.
+test_cxxfilt {} \
+    "AddAlignment__9ivTSolverUiP12ivInteractorP7ivTGlue" \
+    "ivTSolver::AddAlignment(unsigned int, ivInteractor ., ivTGlue .)*"
+
+test_cxxfilt {--format=lucid} \
+    "__ct__12strstreambufFPFl_PvPFPv_v" \
+    "strstreambuf..strstreambuf(void .(.)(long), void (.)(void .))*"
+
+test_cxxfilt {--recurse-limit=2} \
+    "Z3fooiPiPS_PS0_PS1_PS2_PS3_PS4_PS5_PS6_PS7_PS8_PS9_PSA_PSB_PSC_" \
+    "foo(int, int., int.., int..., int...., int....., int......, int......., int........, int........., int.........., int..........., int............, int............., int.............., int...............)*"
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler

Scott Gayou
Thank you for looking into this Nick. I've been staring at a few of these
CVEs off-and-on for a few days, and the following CVEs all look like
duplicates:

CVE-2018-17985: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87335
CVE-2018-18484: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87636
CVE-2018-18701: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87675
CVE-2018-18700: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87681

There may be more. I think Mitre is scanning the gnu bugzilla and assigning
CVEs? This does look like a legitimate very low criticality "denial of
service", but generating new CVEs for every unique poc file against the
same root cause doesn't seem useful. Perhaps some of these should be
rejected?

--
Scott Gayou / Red Had Product Security
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler

Pedro Alves-7
In reply to this post by Nick Clifton
Hi Nick,

On 11/29/2018 03:01 PM, Nick Clifton wrote:
>  static struct demangle_component *
>  d_function_type (struct d_info *di)
>  {
> -  struct demangle_component *ret;
> +  static unsigned long recursion_level = 0;

Did you consider making this be a part of struct d_info instead?
IIRC, d_info is like a "this" pointer, passed around pretty
much everywhere.

I think going in the direction of making the demangler harder to use
in an efficient thread-safe manner is undesirable, even if the feature
is optional.  E.g., in GDB, loading big binaries, demangling is very high
in profiles, and so we've kicked around the desire to parallelize
it (e.g., by parallelizing the reading/interning of DSO files, instead of
reading all of them sequentially).  Having to synchronize access to the
demangler would be quite unfortunate.  If possible, it'd be great
to avoid making work toward that direction harder.  (Keeping in mind that
if this recursion detection feature is useful for binutils, then it should
also be useful for GDB.)

Thanks,
Pedro Alves
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler

Ian Lance Taylor
Pedro Alves <[hidden email]> writes:

> Hi Nick,
>
> On 11/29/2018 03:01 PM, Nick Clifton wrote:
>>  static struct demangle_component *
>>  d_function_type (struct d_info *di)
>>  {
>> -  struct demangle_component *ret;
>> +  static unsigned long recursion_level = 0;
>
> Did you consider making this be a part of struct d_info instead?
> IIRC, d_info is like a "this" pointer, passed around pretty
> much everywhere.
>
> I think going in the direction of making the demangler harder to use
> in an efficient thread-safe manner is undesirable, even if the feature
> is optional.  E.g., in GDB, loading big binaries, demangling is very high
> in profiles, and so we've kicked around the desire to parallelize
> it (e.g., by parallelizing the reading/interning of DSO files, instead of
> reading all of them sequentially).  Having to synchronize access to the
> demangler would be quite unfortunate.  If possible, it'd be great
> to avoid making work toward that direction harder.  (Keeping in mind that
> if this recursion detection feature is useful for binutils, then it should
> also be useful for GDB.)

I agree.  Using static variables here seems problematic.  Right now as
far as I know the demangler has no static variables at all.

Ian
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler

Nick Clifton
In reply to this post by Nick Clifton
Hi Ian,

  *sigh* it is always the way.  You post a patch and five minutes later
  you find a bug in it.  In this case it turned out that I had forgotten
  that gcc has its own copy of the libiberty sources, so the bootstrap
  test that I had run did not use the patched sources.  Doh.  When I did
  rerun the bootstrap with the patched sources it failed because I had
  forgotten to use the CP_STATIC_IF_GLIBCPP_V3 macro when declaring the
  new cplus_demangle_set_recursion_limit() function.

  I am attaching a revised patch with this bug fixed, and an updated
  changelog entry as I have found a few more CVE PRs that it fixes.

  Also - Tom and Pedro have raised the issue that the patch introduces
  a new static variable to the library that is not thread safe.  I am
  not sure of the best way to address this problem.  Possibly the
  variable could be made thread local ?  Are there any other static
  variables in libiberty that face the same issue ?
 
Cheers
  Nick

libiberty/ChangeLog
2018-11-29  Nick Clifton  <[hidden email]>

        PR 87681
        PR 87675
        PR 87636
        PR 87335
        * cp-demangle.c (demangle_recursion_limit): New static
        variable.
        (d_function_type): Add recursion counter.  If the recursion
        limit is enabled and reached, return with a failure result.
        (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_demangle_set_recursion): New function.  Sets and/or
        returns the current stack recursion limit.
        * cplus-dem.c (demangle_nested_args): Add recursion counter.  If
        the recursion limit is enabled and reached, return with a
        failure result.


Index: libiberty/cp-demangle.c
===================================================================
--- libiberty/cp-demangle.c (revision 266657)
+++ libiberty/cp-demangle.c (working copy)
@@ -62,6 +62,7 @@
       cplus_demangle_fill_dtor
       cplus_demangle_print
       cplus_demangle_print_callback
+      cplus_demangle_set_recursion_limit
    and other functions defined in the file cp-demint.c.
 
    This file also defines some other functions and variables which are
@@ -181,6 +182,9 @@
 #define cplus_demangle_init_info d_init_info
 static void d_init_info (const char *, int, size_t, struct d_info *);
 
+#define cplus_demangle_set_recursion_limit d_set_recursion_level
+static  unsigned int d_set_recursion_limit (unsigned int);
+
 #else /* ! defined(IN_GLIBCPP_V3) */
 #define CP_STATIC_IF_GLIBCPP_V3
 #endif /* ! defined(IN_GLIBCPP_V3) */
@@ -2852,21 +2856,34 @@
 static struct demangle_component *
 d_function_type (struct d_info *di)
 {
-  struct demangle_component *ret;
+  static unsigned long recursion_level = 0;
+  struct demangle_component *ret = NULL;
 
-  if (! d_check_char (di, 'F'))
-    return NULL;
-  if (d_peek_char (di) == 'Y')
+  if ((di->options & DMGL_RECURSE_LIMIT)
+      && recursion_level > demangle_recursion_limit)
     {
-      /* Function has C linkage.  We don't print this information.
- FIXME: We should print it in verbose mode.  */
-      d_advance (di, 1);
+      /* FIXME: There ought to be a way to report that the recursion limit
+ has been reached.  */
+      return NULL;
     }
-  ret = d_bare_function_type (di, 1);
-  ret = d_ref_qualifier (di, ret);
 
-  if (! d_check_char (di, 'E'))
-    return NULL;
+  recursion_level ++;
+  if (d_check_char (di, 'F'))
+    {
+      if (d_peek_char (di) == 'Y')
+ {
+  /* Function has C linkage.  We don't print this information.
+     FIXME: We should print it in verbose mode.  */
+  d_advance (di, 1);
+ }
+      ret = d_bare_function_type (di, 1);
+      ret = d_ref_qualifier (di, ret);
+      
+      if (! d_check_char (di, 'E'))
+ ret = NULL;
+    }
+
+  recursion_level --;
   return ret;
 }
 
@@ -6242,6 +6259,20 @@
 
   cplus_demangle_init_info (mangled, options, strlen (mangled), &di);
 
+  /* PR 87675 - Check for a mangled string that is so long
+     that we do not have enough stack space to demangle it.  */
+  if ((options & DMGL_RECURSE_LIMIT)
+      /* This check is a bit arbitrary, since what we really want to do is to
+ compare the sizes of the di.comps and di.subs arrays against the
+ amount of stack space remaining.  But there is no portable way to do
+ this, so instead we use the recursion limit as a guide to the maximum
+ size of the arrays.  */
+      && (unsigned long) di.num_comps > demangle_recursion_limit)
+    {
+      /* FIXME: We need a way to indicate that a stack limit has been reached.  */
+      return 0;
+    }
+
   {
 #ifdef CP_DYNAMIC_ARRAYS
     __extension__ struct demangle_component comps[di.num_comps];
@@ -6324,6 +6355,23 @@
   return dgs.buf;
 }
 
+/* Set a limit on the amount of recursion allowed in mangled strings.
+   Only effective if the DMGL_RECURSE_LIMIT option has been set.
+   Returns the previous value of the recursion limit.
+   Ignores settings a limit of 0 or 1.
+   Note - setting the limit is not a thread-safe operation.  */
+
+CP_STATIC_IF_GLIBCPP_V3
+unsigned long
+cplus_demangle_set_recursion_limit (unsigned long limit)
+{
+  unsigned long result = demangle_recursion_limit;
+
+  if (limit > 1)
+    demangle_recursion_limit = limit;
+  return result;
+}
+
 #if defined(IN_LIBGCC2) || defined(IN_GLIBCPP_V3)
 
 extern char *__cxa_demangle (const char *, char *, size_t *, int *);
Index: libiberty/cplus-dem.c
===================================================================
--- libiberty/cplus-dem.c (revision 266657)
+++ libiberty/cplus-dem.c (working copy)
@@ -4693,10 +4693,21 @@
 demangle_nested_args (struct work_stuff *work, const char **mangled,
                       string *declp)
 {
+  static unsigned long recursion_level = 0;
   string* saved_previous_argument;
   int result;
   int saved_nrepeats;
 
+  if ((work->options & DMGL_RECURSE_LIMIT)
+      && recursion_level > cplus_demangle_set_recursion_limit (0))
+    {
+      /* FIXME: There ought to be a way to report that the recursion limit
+ has been reached.  */
+      return 0;
+    }
+
+  recursion_level ++;
+
   /* The G++ name-mangling algorithm does not remember types on nested
      argument lists, unless -fsquangling is used, and in that case the
      type vector updated by remember_type is not used.  So, we turn
@@ -4723,6 +4734,7 @@
   --work->forgetting_types;
   work->nrepeats = saved_nrepeats;
 
+  --recursion_level;
   return result;
 }
 
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler

Nick Clifton
In reply to this post by Scott Gayou
Hi Scott,

> Thank you for looking into this Nick. I've been staring at a few of these CVEs off-and-on for a few days, and the following CVEs all look like duplicates:
>
> CVE-2018-17985: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87335
> CVE-2018-18484: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87636
> CVE-2018-18701: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87675
> CVE-2018-18700: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87681

Yes, essentially they are.  They actually trigger stack exhaustion at
different places inside libiberty, but the root cause is the same.
I am also happy to say that my proposed patch fixes *all* of these PRs.

> Perhaps some of these should be rejected?

That would nice, but I think that if the patch is accepted then the
issue should be resolved and we should stop seeing this kind of CVE.

(I must admit that my motivation for creating this patch in the first
place is that I am fed up with the amount of hassle that is involved
each time a new CVE is created.  Especially when they are essentially
all the same bug).

Cheers
  Nick


Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler

Jakub Jelinek
In reply to this post by Nick Clifton
On Fri, Nov 30, 2018 at 08:38:48AM +0000, Nick Clifton wrote:
>   Also - Tom and Pedro have raised the issue that the patch introduces
>   a new static variable to the library that is not thread safe.  I am
>   not sure of the best way to address this problem.  Possibly the
>   variable could be made thread local ?  Are there any other static

Please don't.  That has a cost for all the programs that link against
libstdc++ or any other library that includes the demangler, even when they
don't use the demangler at all (99.9% of the users).
Most of the demangler functions pass around a pointer to a struct with
context, can't this be added in there?

        Jakub
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler

Nick Clifton
Hi Jakub,

>>   Also - Tom and Pedro have raised the issue that the patch introduces
>>   a new static variable to the library that is not thread safe.  I am
>>   not sure of the best way to address this problem.  Possibly the
>>   variable could be made thread local ?  Are there any other static
>
> Please don't.

OK. :-)

> Most of the demangler functions pass around a pointer to a struct with
> context, can't this be added in there?

Not without modifying the current demangling interface.  The problem is
that the context structure is created for each invocation of a demangling
function (from outside the library), and no state is preserved across
demangling calls.  Thus in order to have a recursion limit which is
configurable by the caller, you either need to have a global variable or
else extend the demangling interface to include a recursion limit parameter.

I did consider just having a fixed limit, that the user cannot change, but
I thought that this might be rejected by reviewers.  (On the grounds that
different limits are appropriate to different execution environments).
Note - enabling or disabling the recursion limit is controlled by a separate
feature of the proposed patch, ie the new DMGL_RECURSE_LIMIT flag in the
options field of the cplus_demangleXXX() functions.  But there is not enough
room in the options field to also include a recursion limit value.

Cheers
  Nick



Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler

Pedro Alves-7
In reply to this post by Pedro Alves-7
On 11/30/2018 08:26 AM, Nick Clifton wrote:

> Hi Pedro, Hi Tom,
>
>> Pedro> E.g., in GDB, loading big binaries, demangling is very high
>> Pedro> in profiles, and so we've kicked around the desire to parallelize
>> Pedro> it
>
> I did consider this, but I encountered two problems:
>
>   1. I wanted users of the demangling functions to be able to change
>      the recursion limit.  So for example in environments with a very
>      limited amount of stack space the limit could be reduced.  This
>      is one of the purposes of the cplus_demangle_set_recursion_limit()
>      function.
>
>      Since a new d_info structure is created every time a string is demangled
>      the only way to implement cplus_demangle_set_recursion_limit would
>      be to have it set the value that is used to initialize the field in
>      the structure, which is basically back to where we are now.

That's a lesser evil.  With the proposed cplus_demangle_set_recursion_limit
interface, you essentially end up with an interface that makes all threads in
the process end up with the same limit.  There's precedent for global options
in the current_demangling_style global, set by the cplus_demangle_set_style
function.  That's one I recalled, there may be others.  I'd prefer interfaces
that pass down the options as arguments, or a pointer to an options struct, but
that's not the main issue.

The main issue is the current recursion level counter.
That's the static variable that I had pointed at:

  d_function_type (struct d_info *di)
  {
    [...]
 +  static unsigned long recursion_level = 0;
    [...]
 +  recursion_level ++;
    [...]
 +  recursion_level --;
    return ret;
 }

Even if we go with a recursion limit per process, this recursion
level count must be moved to d_info for thread-safety without
synchronization.

>
>   2. I wanted to be able to access the recursion limit from code
>      in cplus-dem.c, which does not use the d_info structure.  

That should just mean a bit of plumbing is in order to pass down
either a d_info structure or something like it?

> This was
>      the other purpose of the cplus_demangler_set_recursion_limit()
>      function - it allows the limit to be read without changing it.
>
> As an alternative I did consider adding an extra parameter to the
> cplus_demangle(), cplus_demangle_opname() and related functions.  But
> this would make them non-backwards compatible and I did not want to
> do that.

I'd say that ideally, we'd aim at the interface we want, and then go
from there.  If changing interfaces is a problem, we can always add
a new entry point and keep the old as backward compatibility.  
But is it (a problem)?  Do we require ABI compatibility here?

But again, the main issue I'm seeing is the recursion level counter,
not the global limit.

> I would imagine that changing the recursion limit would be a very
> rare event, possibly only ever done once in an executable's runtime,
> so I doubt that there will ever be any real-life thread safety
> problems associated with it.  But I do understand that this is just
> an assumption, not a guarantee.
See above.

Thanks,
Pedro Alves
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler

Michael Matz
In reply to this post by Nick Clifton
Hi,

On Fri, 30 Nov 2018, Nick Clifton wrote:

> Not without modifying the current demangling interface.  The problem is
> that the context structure is created for each invocation of a
> demangling function (from outside the library), and no state is
> preserved across demangling calls.  Thus in order to have a recursion
> limit which is configurable by the caller, you either need to have a
> global variable or else extend the demangling interface to include a
> recursion limit parameter.
>
> I did consider just having a fixed limit, that the user cannot change,
> but I thought that this might be rejected by reviewers.  (On the grounds
> that different limits are appropriate to different execution
> environments). Note - enabling or disabling the recursion limit is
> controlled by a separate feature of the proposed patch, ie the new
> DMGL_RECURSE_LIMIT flag in the options field of the cplus_demangleXXX()
> functions.  But there is not enough room in the options field to also
> include a recursion limit value.
Or we decide to not ignore this part of the GNU coding standard ...

> 4.2 Writing Robust Programs
>  
> Avoid arbitrary limits on the length or number of any data structure,
> including file names, lines, files, and symbols, by allocating all data
> structures dynamically. In most Unix utilities, “long lines are silently
> truncated”. This is not acceptable in a GNU utility.

... just because script kiddies do mindless fuzzing work.  I realize that
you didn't implement a fixed limit, but IMHO it's bordering with that.

But re the static variables: you have two, once the recursion depth, and
once the limit.

The limit can be a static variable just fine, you state, as part of the
interface that it sets global state, and if that needs to happen from
multiple threads that the user must synchronize.  This is fine because
there won't be many calls to constantly change that limit.

The current depth needs to be part of the d_info (resp. workstuff)
structure, avoiding the thread-unsafety.

Another crazy idea: do encode the limit in the option field.  If you
declare that the limit is a power of two (which IMHO doesn't
materially change the usefullness of such limit) then you only need to
encode the log2 of it, for which 5 bits are plenty enough (you can encode
limits from 1 to 1<<32 then).


Ciao,
Michael.
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler

Ian Lance Taylor
In reply to this post by Nick Clifton
Nick Clifton <[hidden email]> writes:

> I did consider just having a fixed limit, that the user cannot change, but
> I thought that this might be rejected by reviewers.  (On the grounds that
> different limits are appropriate to different execution environments).
> Note - enabling or disabling the recursion limit is controlled by a separate
> feature of the proposed patch, ie the new DMGL_RECURSE_LIMIT flag in the
> options field of the cplus_demangleXXX() functions.  But there is not enough
> room in the options field to also include a recursion limit value.

I think it would be fine to have a large fixed limit plus a flag to
disable the limit.  I can't think of any reason why a program would want
to change the limit unless it has complete trust in the symbols it is
demangling, and in that case it may as well simply disable the limit.

Ian
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler

Jakub Jelinek
On Fri, Nov 30, 2018 at 05:55:52AM -0800, Ian Lance Taylor wrote:

> Nick Clifton <[hidden email]> writes:
>
> > I did consider just having a fixed limit, that the user cannot change, but
> > I thought that this might be rejected by reviewers.  (On the grounds that
> > different limits are appropriate to different execution environments).
> > Note - enabling or disabling the recursion limit is controlled by a separate
> > feature of the proposed patch, ie the new DMGL_RECURSE_LIMIT flag in the
> > options field of the cplus_demangleXXX() functions.  But there is not enough
> > room in the options field to also include a recursion limit value.
>
> I think it would be fine to have a large fixed limit plus a flag to
> disable the limit.  I can't think of any reason why a program would want
> to change the limit unless it has complete trust in the symbols it is
> demangling, and in that case it may as well simply disable the limit.

Well, disabling the limit is what the people fuzzing it will use then
and report it still crashes.
We'd need to document that if somebody asks for no limit, then we don't
consider any cases of running as out of stack etc. as bugs, and simply
people shouldn't set that on when running on untrusted symbols.

        Jakub
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler

Ian Lance Taylor
In reply to this post by Michael Matz
Michael Matz <[hidden email]> writes:

> On Fri, 30 Nov 2018, Nick Clifton wrote:
>
>> Not without modifying the current demangling interface.  The problem is
>> that the context structure is created for each invocation of a
>> demangling function (from outside the library), and no state is
>> preserved across demangling calls.  Thus in order to have a recursion
>> limit which is configurable by the caller, you either need to have a
>> global variable or else extend the demangling interface to include a
>> recursion limit parameter.
>>
>> I did consider just having a fixed limit, that the user cannot change,
>> but I thought that this might be rejected by reviewers.  (On the grounds
>> that different limits are appropriate to different execution
>> environments). Note - enabling or disabling the recursion limit is
>> controlled by a separate feature of the proposed patch, ie the new
>> DMGL_RECURSE_LIMIT flag in the options field of the cplus_demangleXXX()
>> functions.  But there is not enough room in the options field to also
>> include a recursion limit value.
>
> Or we decide to not ignore this part of the GNU coding standard ...
>
>> 4.2 Writing Robust Programs
>>  
>> Avoid arbitrary limits on the length or number of any data structure,
>> including file names, lines, files, and symbols, by allocating all data
>> structures dynamically. In most Unix utilities, “long lines are silently
>> truncated”. This is not acceptable in a GNU utility.
>
> ... just because script kiddies do mindless fuzzing work.  I realize that
> you didn't implement a fixed limit, but IMHO it's bordering with that.

That section is "Writing Robust Programs."  Robustness guarantees have
to be different for utilities and servers.  A robust server doesn't
crash because of arbitrary user input, but there are servers that
demangle names that are provided by the user.  So we need two modes for
the demangler: one that takes anything and sometimes crashes, for
utilities like c++filt, and one that doesn't crash, for servers.  And it
seems like that is what Nick is suggesting.

Ian
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler [v3]

Nick Clifton
In reply to this post by Jakub Jelinek
Hi Guys,

>> I think it would be fine to have a large fixed limit plus a flag to
>> disable the limit.

Great - in which case please may I present version 3 of the patch.  In
this version:

  * The cplus_demangle_set_recursion_limit() function has been removed
    and instead a new constant - DEMANGLE_RECURSION_LIMIT - is defined in
    demangle.h.

  * The recursion counters in cp-demangle.c have been merged into one
    counter, now contained in the d_info structure.

  * In cplus-dem.c the recursion counter has been moved into the work
    structure.

  * The description of the DMGL_RECURSE_LIMIT option in demangle.h has
    been enhanced to add a note that if the option is not used, then
    bug reports about stack overflows in the demangler will be rejected.

  * The binutils patch has been updated to reflect these changes.  The
    addr2line, cxxfilt, nm and objdump programs now have two new options
    --recurse-limit and --no-recurse-limit, with --recurse-limit being
    the default.  The documentation is updated to describe these options
    and to also add a note about bug reports being rejected if
    --no-recurse-limit is used.

What do you think, is this version acceptable ?

Cheers
  Nick

libiberty/ChangeLog
2018-11-29  Nick Clifton  <[hidden email]>

        PR 87681
        PR 87675
        PR 87636
        PR 87335
        * cp-demangle.h (struct d_info): Add recursion_limit field.
        * cp-demangle.c (d_function_type): If the recursion limit is
        enabled and reached, return with a failure result.
        (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.
        (demangle_nested_args): If the recursion limit is enabled and
        reached, return with a failure result.

include/ChangeLog
2018-11-29  Nick Clifton  <[hidden email]>

        * demangle.h (DMGL_RECURSE_LIMIT): Define.
        (DEMANGLE_RECURSION_LIMIT): Prototype.

binutils/ChangeLog
2018-11-29  Nick Clifton  <[hidden email]>

        * addr2line.c (demangle_flags): New static variable.
        (long_options): Add --recurse-limit and --no-recurse-limit.
        (translate_address): Pass demangle_flags to bfd_demangle.
        (main): Handle --recurse-limit and --no-recurse-limit options.
        * cxxfilt.c (flags): Add DMGL_RECURSE_LIMIT.
        (long_options): Add --recurse-limit and --no-recurse-limit.
        (main): Handle new options.
        * dlltool.c (gen_def_file): Include DMGL_RECURSE_LIMIT in flags
        passed to cplus_demangle.
        * nm.c (demangle_flags): New static variable.
        (long_options): Add --recurse-limit and --no-recurse-limit.
        (main): Handle new options.
        * objdump.c (demangle_flags): New static variable.
        (usage): Add --recurse-limit and --no-recurse-limit.
        (long_options): Likewise.
        (objdump_print_symname): Pass demangle_flags to bfd_demangle.
        (disassemble_section): Likewise.
        (dump_dymbols): Likewise.
        (main): Handle new options.
        * prdbg.c (demangle_flags): New static variable.
        (tg_variable): Pass demangle_flags to demangler.
        (tg_start_function): Likewise.
        * stabs.c (demangle_flags): New static variable.
        (stab_demangle_template): Pass demangle_flags to demangler.
        (stab_demangle_v3_argtypes): Likewise.
        (stab_demangle_v3_arg): Likewise.
        * doc/binutuls.texi: Document new command line options.
        * NEWS: Mention the new feature.
        * testsuite/config/default.exp (CXXFILT): Define if not already
        defined.
        (CXXFILTFLAGS): Likewise.
        * testsuite/binutils-all/cxxfilt.exp: New file.  Runs a few
        simple tests of the cxxfilt program.

binutils-demangler-recursion-limit.3.patch (25K) Download Attachment
libiberty-demangler-recursion-limit.3.patch (6K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler [v3]

Jakub Jelinek
Hi!

Just spelling nitpicking.

On Fri, Nov 30, 2018 at 05:41:35PM +0000, Nick Clifton wrote:
> +  order to dmangle truely complicated names, but it also leaves the tools

truly? Multiple times.

> +The @option{-r} option is a snyonym for the

synonym? Multiple times.

        Jakub
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler [v3]

Pedro Alves-7
In reply to this post by Nick Clifton
On 11/30/2018 05:41 PM, Nick Clifton wrote:

> @@ -4693,10 +4694,21 @@
>  demangle_nested_args (struct work_stuff *work, const char **mangled,
>                        string *declp)
>  {
> +  static unsigned long recursion_level = 0;
>    string* saved_previous_argument;
>    int result;
>    int saved_nrepeats;
>  
> +  if ((work->options & DMGL_RECURSE_LIMIT)
> +      && work->recursion_level > DEMANGLE_RECURSION_LIMIT)
> +    {
> +      /* FIXME: There ought to be a way to report that the recursion limit
> + has been reached.  */
> +      return 0;
> +    }
> +
> +  recursion_level ++;
> +

There's still a static recursion level counter here?

Thanks,
Pedro Alves
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler

Cary Coutant
In reply to this post by Ian Lance Taylor
> That section is "Writing Robust Programs."  Robustness guarantees have
> to be different for utilities and servers.  A robust server doesn't
> crash because of arbitrary user input, but there are servers that
> demangle names that are provided by the user.  So we need two modes for
> the demangler: one that takes anything and sometimes crashes, for
> utilities like c++filt, and one that doesn't crash, for servers.  And it
> seems like that is what Nick is suggesting.

In order to handle arbitrary user input without crashing, perhaps the
demangler should switch from recursive descent parsing to a state
machine, where exhaustion of resources can be handled gracefully.

-cary
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler [v3]

Richard Biener-2
In reply to this post by Nick Clifton
On Fri, Nov 30, 2018 at 6:41 PM Nick Clifton <[hidden email]> wrote:

>
> Hi Guys,
>
> >> I think it would be fine to have a large fixed limit plus a flag to
> >> disable the limit.
>
> Great - in which case please may I present version 3 of the patch.  In
> this version:
>
>   * The cplus_demangle_set_recursion_limit() function has been removed
>     and instead a new constant - DEMANGLE_RECURSION_LIMIT - is defined in
>     demangle.h.
>
>   * The recursion counters in cp-demangle.c have been merged into one
>     counter, now contained in the d_info structure.
>
>   * In cplus-dem.c the recursion counter has been moved into the work
>     structure.
>
>   * The description of the DMGL_RECURSE_LIMIT option in demangle.h has
>     been enhanced to add a note that if the option is not used, then
>     bug reports about stack overflows in the demangler will be rejected.

Shouldn't we make it fool-proof by instead introducing a DMGL_NO_RECURSION_LIMIT
flag and when not set default to limiting recursion?

>   * The binutils patch has been updated to reflect these changes.  The
>     addr2line, cxxfilt, nm and objdump programs now have two new options
>     --recurse-limit and --no-recurse-limit, with --recurse-limit being
>     the default.  The documentation is updated to describe these options
>     and to also add a note about bug reports being rejected if
>     --no-recurse-limit is used.
>
> What do you think, is this version acceptable ?
>
> Cheers
>   Nick
>
> libiberty/ChangeLog
> 2018-11-29  Nick Clifton  <[hidden email]>
>
>         PR 87681
>         PR 87675
>         PR 87636
>         PR 87335
>         * cp-demangle.h (struct d_info): Add recursion_limit field.
>         * cp-demangle.c (d_function_type): If the recursion limit is
>         enabled and reached, return with a failure result.
>         (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.
>         (demangle_nested_args): If the recursion limit is enabled and
>         reached, return with a failure result.
>
> include/ChangeLog
> 2018-11-29  Nick Clifton  <[hidden email]>
>
>         * demangle.h (DMGL_RECURSE_LIMIT): Define.
>         (DEMANGLE_RECURSION_LIMIT): Prototype.
>
> binutils/ChangeLog
> 2018-11-29  Nick Clifton  <[hidden email]>
>
>         * addr2line.c (demangle_flags): New static variable.
>         (long_options): Add --recurse-limit and --no-recurse-limit.
>         (translate_address): Pass demangle_flags to bfd_demangle.
>         (main): Handle --recurse-limit and --no-recurse-limit options.
>         * cxxfilt.c (flags): Add DMGL_RECURSE_LIMIT.
>         (long_options): Add --recurse-limit and --no-recurse-limit.
>         (main): Handle new options.
>         * dlltool.c (gen_def_file): Include DMGL_RECURSE_LIMIT in flags
>         passed to cplus_demangle.
>         * nm.c (demangle_flags): New static variable.
>         (long_options): Add --recurse-limit and --no-recurse-limit.
>         (main): Handle new options.
>         * objdump.c (demangle_flags): New static variable.
>         (usage): Add --recurse-limit and --no-recurse-limit.
>         (long_options): Likewise.
>         (objdump_print_symname): Pass demangle_flags to bfd_demangle.
>         (disassemble_section): Likewise.
>         (dump_dymbols): Likewise.
>         (main): Handle new options.
>         * prdbg.c (demangle_flags): New static variable.
>         (tg_variable): Pass demangle_flags to demangler.
>         (tg_start_function): Likewise.
>         * stabs.c (demangle_flags): New static variable.
>         (stab_demangle_template): Pass demangle_flags to demangler.
>         (stab_demangle_v3_argtypes): Likewise.
>         (stab_demangle_v3_arg): Likewise.
>         * doc/binutuls.texi: Document new command line options.
>         * NEWS: Mention the new feature.
>         * testsuite/config/default.exp (CXXFILT): Define if not already
>         defined.
>         (CXXFILTFLAGS): Likewise.
>         * testsuite/binutils-all/cxxfilt.exp: New file.  Runs a few
>         simple tests of the cxxfilt program.
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler [v3]

Nick Clifton
Hi Richard,

>>   * The description of the DMGL_RECURSE_LIMIT option in demangle.h has
>>     been enhanced to add a note that if the option is not used, then
>>     bug reports about stack overflows in the demangler will be rejected.
>
> Shouldn't we make it fool-proof by instead introducing a DMGL_NO_RECURSION_LIMIT
> flag and when not set default to limiting recursion?

Well I wanted the patch to be backwards compatible. Just on the
general principle of not surprising users/programmers by changing
things without telling them first.

I could change this of course, but I would rather have Ian's blessing
first.

Cheers
  Nick
Reply | Threaded
Open this post in threaded view
|

Re: RFA/RFC: Add stack recursion limit to libiberty's demangler

Nick Clifton
In reply to this post by Cary Coutant
Hi Cary,

> In order to handle arbitrary user input without crashing, perhaps the
> demangler should switch from recursive descent parsing to a state
> machine, where exhaustion of resources can be handled gracefully.

I think that that would be a better long term fix for the problem,
but it is not one that I have time to work on right now.

My main goal with this patch submission is to stop the flood of PR
and CVEs about mangled inputs that trigger stack exhaustion.  Being
able to properly demangle such inputs would be nice, but not something
that I think should be a priority.  I think that in real life no
program is ever going to generate a mangled name that is sufficiently
complex to trigger a seg-fault this way, so the only real purpose of
the patch is to resolve these PRs and stop more from being filed.

Cheers
  Nick


1234