Re: [RFC] ld: Add random filling for unspecified section contents

[Andrew Burgess <andrew.burgess@embecosm.com>]

Nick,

Thanks for taking the time to review.

* Nick Clifton <nickc@redhat.com> [2017-04-20 14:43:06 +0100]:

> > I'd like to propose the following feature, the ability for the linker
> > to randomise the fill data within a section (right now we can only
> > provide a fixed fill pattern).
> > 
> > One use case for such a feature would be to pad out a data section
> > while making it slightly harder for someone else examining the object
> > file to determine which parts of the section are actual content, and
> > which parts are padding.
> 
> I have to say that I do not think there will be much real gain from this 
> feature.  Surely an attacker can examine the symbol table to determine
> the last addressed point in a padded data section and use that as a guide
> to what is real data and what is padding.

The situation in which I'm making use of this feature is really
outside of the ELF.  I'm linking code for an embeded target where
the code/data that is eventually loaded onto the device is extracted
from the ELF, so there's no symbol table, of section/segment table to
reveal any information.

All I have is a fixed sized area of memory that, ideally, will be
initialised, exactly, with the contents of a particular section from
the ELF.

As the environment in which this particular embeded device operates is
_extremely_ paranoid about security a request was made that I avoid
using a fixed pattern to pad out data regions.

Even given the lack of symbol/section/segment information, this random
fill, is clearly still security-through-obscurity, real analysis of
device behaviour would undoubtedly still reveal what is or is not real
data, but it's more a case of every-little-helps...

> 
> But anyway...
> 
> > At the moment I'm using jrand48, this isn't thread-safe, but does take
> > it's seed as an argument for each call.
> 
> What about using jrand48_r instead ?

That I suspect will suffer from the same issue of unavailability on
some targets.  The particular target that I know about would be Mingw
(that is a target we support, right?) where as far as I can tell /
figure out, there are very few random APIs available.  I don't
directly have access to such a target for testing so I'm pretty
limited in what I can figure out.

> 
> > The problem is that I'm pretty sure this function is not available on
> > every platform we target, and I'm not sure what the right thing to use
> > instead is.
> 
> Write a configure check for the function and only use it if available ?
> 
> > I'm wondering if the right thing to do is to add a reentrant random
> > number API to libiberty and use that.  However, I'm open to any
> > suggestions for what the right thing to do might be.
> 
> How about using random(), setstate() and initstate() - all provided by 
> libiberty ?   That should provide wider availability, although not thread
> safety.

I originally avoided that as it seemed a little clunky, but, I suspect
my only other option is writing a jrand48_r like thing in libiberty
(which I'd rather avoid), so I've taken your suggestion and switched
to a random/setstate/initstate solution.

Would you be OK with this in tree?

Thanks,
Andrew

---

ld: Add random filling for unspecified section contents

This commit allows a user to fill unspecified regions of a section with
random contents instead of the fixed fill patterns that they are
currently limited too.  This is done by extending the two mechanisms
that exist for specifying fill patterns to detect the special expression
'RANDOM'.  Here is an example of an output section with 16 bytes of
trailing random data:

  .data : {
    *(.data)
    FILL(RANDOM)
    . += 0x10
  }

this could alternatively be written as:

  .data : {
    *(.data)
    . += 0x10
  } =RANDOM

Included is a mechanism for forcing the random seed used for generating
the fill content to a known value, this allows reproducible output files
to be generated if this is required.  This is done using the new command
line switch '--random-fill-seed=VALUE'.

The random filling technique can be used to obfuscate the contents of a
section, where there is some genuine content and some padding.  Using a
fixed pattern for the padding might allow an observer to figure out
which bytes are content and which are padding, in some security
conscious environments this might not be desirable.

The idea is that providing random fill for the padding makes it slightly
harder to figure out what is padding and what is genuine content.

ld/ChangeLog:

	* ldexp.c (exp_get_fill): Spot 'RANDOM' expression, and initialise
	'random' flag in fill_type result.
	* ldlang.c (print_fill_statement): Print something suitable for
	RANDOM fill.
	* ldlang.h (struct _fill_type): Add 'random' field.
	* ldlex.h (enum option_values): Add OPTION_RANDOM_FILL_SEED.
	* ldmain.c: Add 'time.h' include.
	(init_random_seed): New function to initialise 'random_fill_state'
	in 'link_info'.
	(main): Call new function init_random_seed.
	* ldwrite.c (build_link_order): Initialise 'random' flag in the
	bfd_link_order.
	* lexsup.c (ld_options): Add 'random-fill-seed' entry.
	(parse_args): Handle OPTION_RANDOM_FILL_SEED.
	* ld.texinfo (Options): Document '--random-fill-seed' option.
	(Output Section Data): Document 'FILL(RANDOM)'.
	(Output Section Fill): Document '=RANDOM'.
	* testsuite/ld-scripts/fill.t: Add random fill test.
	* testsuite/ld-scripts/fill.d: Extend expected results.

include/ChangeLog:

	* bfdlink.h (struct bfd_link_info): Add 'random_fill_state'.
	(struct bfd_link_order): Add 'random' flag.

bfd/ChangeLog:

	* linker.c (default_data_link_order): Handle filling section with
	random values.
---
 bfd/ChangeLog                  |  5 +++++
 bfd/linker.c                   | 33 +++++++++++++++++++++++++++++++--
 include/ChangeLog              |  5 +++++
 include/bfdlink.h              |  6 ++++++
 ld/ChangeLog                   | 22 ++++++++++++++++++++++
 ld/ld.texinfo                  | 35 +++++++++++++++++++++++++++++++++++
 ld/ldexp.c                     | 11 +++++++++++
 ld/ldlang.c                    | 13 +++++++++----
 ld/ldlang.h                    |  1 +
 ld/ldlex.h                     |  1 +
 ld/ldmain.c                    | 13 +++++++++++++
 ld/ldwrite.c                   |  1 +
 ld/lexsup.c                    | 15 +++++++++++++++
 ld/testsuite/ld-scripts/fill.d |  1 +
 ld/testsuite/ld-scripts/fill.t |  2 ++
 15 files changed, 158 insertions(+), 6 deletions(-)

diff --git a/bfd/linker.c b/bfd/linker.c
index 2f56b46..78e92d5 100644
--- a/bfd/linker.c
+++ b/bfd/linker.c
@@ -2448,7 +2448,7 @@ default_data_link_order (bfd *abfd,
   size_t fill_size;
   bfd_byte *fill;
   file_ptr loc;
-  bfd_boolean result;
+  bfd_boolean result, fill_random;
 
   BFD_ASSERT ((sec->flags & SEC_HAS_CONTENTS) != 0);
 
@@ -2458,7 +2458,36 @@ default_data_link_order (bfd *abfd,
 
   fill = link_order->u.data.contents;
   fill_size = link_order->u.data.size;
-  if (fill_size == 0)
+  fill_random = link_order->u.data.random;
+  if (fill_random)
+    {
+      bfd_byte *p;
+      long int val;
+      PTR ostate;
+
+      fill = (bfd_byte *) bfd_malloc (size);
+      if (fill == NULL)
+        return FALSE;
+
+      ostate = setstate (info->random_fill_state);
+      p = fill;
+      while (size > sizeof (val))
+        {
+          val = random ();
+          memcpy (p, &val, sizeof (val));
+          p += sizeof (val);
+          size -= sizeof (val);
+        }
+
+      if (size > 0)
+        {
+          val = random ();
+          memcpy (p, &val, size);
+        }
+      size = link_order->size;
+      setstate (ostate);
+    }
+  else if (fill_size == 0)
     {
       fill = abfd->arch_info->fill (size, bfd_big_endian (abfd),
 				    (sec->flags & SEC_CODE) != 0);
diff --git a/include/bfdlink.h b/include/bfdlink.h
index cb4bad9..9ecba68 100644
--- a/include/bfdlink.h
+++ b/include/bfdlink.h
@@ -620,6 +620,10 @@ struct bfd_link_info
 
   /* The version information.  */
   struct bfd_elf_version_tree *version_info;
+
+  /* When filling sections with random values, this is the state
+     information used by the random number generator.  */
+  char random_fill_state [256];
 };
 
 /* This structures holds a set of callback functions.  These are called
@@ -787,6 +791,8 @@ struct bfd_link_order
 	} indirect;
       struct
 	{
+          /* If true then fill the contents with random values.  */
+          bfd_boolean random;
 	  /* Size of contents, or zero when contents should be filled by
 	     the architecture-dependent fill function.
 	     A non-zero value allows filling of the output section
diff --git a/ld/ld.texinfo b/ld/ld.texinfo
index 2626b5d..fd504bb 100644
--- a/ld/ld.texinfo
+++ b/ld/ld.texinfo
@@ -2452,6 +2452,16 @@
 
 Passing @code{none} for @var{style} disables the setting from any
 @code{--build-id} options earlier on the command line.
+
+@kindex --random-fill-seed=@var{value}
+@item --random-fill-seed=@var{value}
+When using @code{FILL} or @samp{=@var{fillexp}} to fill section
+contents with random values (@pxref{Output Section Fill} and
+@ref{Output Section Data}) if reproducible output is required, for
+example, in the case of testing, then passing @var{value} will
+override the random seed usually set by the linker.  Passing the same
+random seed to subsequent runs will cause the same random values to be
+generated for each link.
 @end table
 
 @c man end
@@ -4687,8 +4697,11 @@
 @end smallexample
 
 @kindex FILL(@var{expression})
+@kindex FILL(RANDOM)
 @cindex holes, filling
 @cindex unspecified memory
+@cindex fill pattern
+@cindex fill pattern, random
 You may use the @code{FILL} command to set the fill pattern for the
 current section.  It is followed by an expression in parentheses.  Any
 otherwise unspecified regions of memory within the section (for example,
@@ -4705,6 +4718,14 @@
 FILL(0x90909090)
 @end smallexample
 
+If the expression @samp{RANDOM} is used the any unspecified memory
+will be filled with random values.  This is an example of how to use
+@samp{RANDOM}:
+
+@smallexample
+FILL(RANDOM)
+@end smallexample
+
 The @code{FILL} command is similar to the @samp{=@var{fillexp}} output
 section attribute, but it only affects the
 part of the section following the @code{FILL} command, rather than the
@@ -5058,8 +5079,12 @@
 @node Output Section Fill
 @subsubsection Output Section Fill
 @kindex =@var{fillexp}
+@kindex =RANDOM
+@cindex holes, filling
+@cindex unspecified memory
 @cindex section fill pattern
 @cindex fill pattern, entire section
+@cindex fill pattern, random
 You can set the fill pattern for an entire section by using
 @samp{=@var{fillexp}}.  @var{fillexp} is an expression
 (@pxref{Expressions}).  Any otherwise unspecified regions of memory
@@ -5083,6 +5108,16 @@
 @end group
 @end smallexample
 
+If the @var{fillexp} @samp{RANDOM} is used then any unspecified
+regions of memory will be filled with random values.
+
+Here is a simple example:
+@smallexample
+@group
+SECTIONS @{ .text : @{ *(.text) @} =RANDOM @}
+@end group
+@end smallexample
+
 @node Overlay Description
 @subsection Overlay Description
 @kindex OVERLAY
diff --git a/ld/ldexp.c b/ld/ldexp.c
index 792e21e..b4c03fd 100644
--- a/ld/ldexp.c
+++ b/ld/ldexp.c
@@ -1548,6 +1548,15 @@ exp_get_fill (etree_type *tree, fill_type *def, char *name)
   if (tree == NULL)
     return def;
 
+  if (tree->type.node_class == etree_name
+      && strcmp (tree->name.name, "RANDOM") == 0)
+    {
+      fill = (fill_type *) xmalloc (sizeof (*fill));
+      fill->random = 1;
+      fill->size = 0;
+      return fill;
+    }
+
   exp_fold_tree_no_dot (tree);
   if (!expld.result.valid_p)
     {
@@ -1562,6 +1571,7 @@ exp_get_fill (etree_type *tree, fill_type *def, char *name)
       unsigned char *dst;
       unsigned char *s;
       fill = (fill_type *) xmalloc ((len + 1) / 2 + sizeof (*fill) - 1);
+      fill->random = 0;
       fill->size = (len + 1) / 2;
       dst = fill->data;
       s = (unsigned char *) expld.result.str;
@@ -1593,6 +1603,7 @@ exp_get_fill (etree_type *tree, fill_type *def, char *name)
       fill->data[2] = (val >>  8) & 0xff;
       fill->data[3] = (val >>  0) & 0xff;
       fill->size = 4;
+      fill->random = 0;
     }
   return fill;
 }
diff --git a/ld/ldlang.c b/ld/ldlang.c
index 266c099..86c63f6 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -4286,10 +4286,15 @@ print_fill_statement (lang_fill_statement_type *fill)
 {
   size_t size;
   unsigned char *p;
-  fputs (" FILL mask 0x", config.map_file);
-  for (p = fill->fill->data, size = fill->fill->size; size != 0; p++, size--)
-    fprintf (config.map_file, "%02x", *p);
-  fputs ("\n", config.map_file);
+  if (fill->fill->random)
+    fputs (" FILL mask RANDOM\n", config.map_file);
+  else
+    {
+      fputs (" FILL mask 0x", config.map_file);
+      for (p = fill->fill->data, size = fill->fill->size; size != 0; p++, size--)
+	fprintf (config.map_file, "%02x", *p);
+      fputs ("\n", config.map_file);
+    }
 }
 
 static void
diff --git a/ld/ldlang.h b/ld/ldlang.h
index a833672..538edc0 100644
--- a/ld/ldlang.h
+++ b/ld/ldlang.h
@@ -35,6 +35,7 @@ typedef enum
 
 struct _fill_type
 {
+  int random;
   size_t size;
   unsigned char data[1];
 };
diff --git a/ld/ldlex.h b/ld/ldlex.h
index dac152b..dab7512 100644
--- a/ld/ldlex.h
+++ b/ld/ldlex.h
@@ -146,6 +146,7 @@ enum option_values
   OPTION_PRINT_MEMORY_USAGE,
   OPTION_REQUIRE_DEFINED_SYMBOL,
   OPTION_ORPHAN_HANDLING,
+  OPTION_RANDOM_FILL_SEED,
 };
 
 /* The initial parser states.  */
diff --git a/ld/ldmain.c b/ld/ldmain.c
index e049de3..1e3efa5 100644
--- a/ld/ldmain.c
+++ b/ld/ldmain.c
@@ -49,6 +49,7 @@
 #endif
 
 #include <string.h>
+#include <time.h>
 
 #ifdef HAVE_SBRK
 #if !HAVE_DECL_SBRK
@@ -193,6 +194,17 @@ ld_bfd_error_handler (const char *fmt, va_list ap)
   (*default_bfd_error_handler) (fmt, ap);
 }
 
+/* Initialise the RANDOM_FILL_SEED field of global LINK_INFO based on the
+   current time.  */
+
+static void
+init_random_seed (void)
+{
+  unsigned int seed = (unsigned int) time (NULL);
+  initstate (seed, link_info.random_fill_state,
+             sizeof (link_info.random_fill_state));
+}
+
 int
 main (int argc, char **argv)
 {
@@ -298,6 +310,7 @@ main (int argc, char **argv)
 #ifdef DEFAULT_FLAG_COMPRESS_DEBUG
   link_info.compress_debug = COMPRESS_DEBUG_GABI_ZLIB;
 #endif
+  init_random_seed ();
 
   ldfile_add_arch ("");
   emulation = get_emulation (argc, argv);
diff --git a/ld/ldwrite.c b/ld/ldwrite.c
index 1cd111d..4896977 100644
--- a/ld/ldwrite.c
+++ b/ld/ldwrite.c
@@ -298,6 +298,7 @@ build_link_order (lang_statement_union_type *statement)
 	link_order->offset = statement->padding_statement.output_offset;
 	link_order->u.data.contents = statement->padding_statement.fill->data;
 	link_order->u.data.size = statement->padding_statement.fill->size;
+	link_order->u.data.random = statement->padding_statement.fill->random;
       }
       break;
 
diff --git a/ld/lexsup.c b/ld/lexsup.c
index 0b7d497..5e89154 100644
--- a/ld/lexsup.c
+++ b/ld/lexsup.c
@@ -535,6 +535,9 @@ static const struct ld_option ld_options[] =
   { {"orphan-handling", required_argument, NULL, OPTION_ORPHAN_HANDLING},
     '\0', N_("=MODE"), N_("Control how orphan sections are handled."),
     TWO_DASHES },
+  { {"random-fill-seed", required_argument, NULL, OPTION_RANDOM_FILL_SEED},
+    '\0', N_("=VALUE"), N_("Set initial seed for random fill generation."),
+    TWO_DASHES },
 };
 
 #define OPTION_COUNT ARRAY_SIZE (ld_options)
@@ -1562,6 +1565,18 @@ parse_args (unsigned argc, char **argv)
 	    einfo (_("%P%F: invalid argument to option"
 		     " \"--orphan-handling\"\n"));
 	  break;
+
+        case OPTION_RANDOM_FILL_SEED:
+          {
+            char *end;
+            unsigned int seed = (unsigned int) strtoul (optarg, &end, 0);
+            if (*end)
+              einfo (_("%P%F: unable to parse `%s' for option"
+                       " \"--random-fill-seed\"\n"), optarg);
+            initstate (seed, link_info.random_fill_state,
+                       sizeof (link_info.random_fill_state));
+          }
+          break;
 	}
     }
 
diff --git a/ld/testsuite/ld-scripts/fill.d b/ld/testsuite/ld-scripts/fill.d
index 8dd789b..5c7e7b5 100644
--- a/ld/testsuite/ld-scripts/fill.d
+++ b/ld/testsuite/ld-scripts/fill.d
@@ -27,3 +27,4 @@ Contents of section .text:
  [0-9a-f]+ 03030303 00345600 00004567 000089ab .*
  [0-9a-f]+ (deadbeef|efbeadde) 00004567 000089ab 0000cdef .*
  [0-9a-f]+ 00004567 000089ab 0000cdef 00000123 .*
+ [0-9a-f]+ [0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f] .*
\ No newline at end of file
diff --git a/ld/testsuite/ld-scripts/fill.t b/ld/testsuite/ld-scripts/fill.t
index 835e009..3ced09c 100644
--- a/ld/testsuite/ld-scripts/fill.t
+++ b/ld/testsuite/ld-scripts/fill.t
@@ -16,5 +16,7 @@ SECTIONS
     LONG (0xdeadbeef)
     . += 12;
     . += 16;
+    FILL (RANDOM)
+    . += 4;
   } =0xcafebabe
 }
-- 
2.5.1