[PATCH] malloc: Fix [BZ #22853] weak randomization on thread arenas.

[Adhemerval Zanella]

On 23/03/2020 14:06, iripoll wrote:
> Hi!
> 
>> Thanks for the work. However, patch discussion is done through the
>> email list [1].  Could you re-send it on the libc-alpha?
>>
>> It seems that alignment restriction was added originally to simplify
>> the heap_for_ptr macro and I think it should be added on patch
>> description (stating there is no other restriction about arena
>> alignment).
> 
>   Regarding the comments in the code, we don't know what would be the
> best way to describe the patch. We don't know if the code shall be
> commented with respect to the previous code or if it would be better
> to describe the operation of the new heap_for_ptr macro (which can be
> tricky). Please, add the comments that you think are better.

Thanks for follow this up, in fact I was about to send this very
patch in your behalf.  I will comment below.

> 
>> Also, would be possible to add a testcase? I am not sure which
>> approach would be better (a maillist discussion might give some
>> ideas). Maybe by parametrize the mmap entropy information you
>> compiled on arch-specific files (similar to the stackinfo.h), create
>> N thread that run M allocation, record the output, and compare the
>> histogram with the expected entropy with a certain margin.
> 
>   The patch (in the mail) contains both the fix and a new test
> [tst-arena-aslr.c] that checks the effective randomization of the
> malloc on threads and compares it with that of the mmap. That way
> the test shall be platform independent.
> 
>   Although the security issue affects the entropy of the dynamic
> memory requested by the threads, it is necessary to launch 1000
> processes to have different memory layouts samples. Remember that
> ASLR does not change on a per processes basis (fork) but it is
> renewed every new binary image (exec).

Right, we might need to handle and tune if it takes too much
time (specially on some architectures).

> 
>> Finally, please also add the outcome of the
>> bench-malloc-{simple,thread} with and without the patch.
> 
> 
>   The output of the test is:
> 
> --------  If failed (three lines) ------
> FAIL: malloc arena ASLR.
>   Expected value: 29 random bits
>   But got:        15 random bits
> 
> --------  If passed (one line) -------
> PASS: malloc arena ASLR.
> 
>   The test is passed if the random bits of the thread malloc is
> greater or equal to the random bits of mmap(). With a small
> tolerance. This way (testing greater or equal than) the test will
> also pass if additional entropy is add to the heaps in the future.
> 
>   Important: the test does not estimate the entropy accurately! because
> it is not the goal of the test. A more accurate estimation would need
> much more samples and a more complex algorithm, which is heavy. In fact,
> the actual entropy is 28 bits and 14 in x86_64, but the test gives 29
> and 15 for mmap and thread's mallocs respectively.

Alright, the main issue is not that it calculates entropy inaccurately,
but if it accuses false-positives. I tried to code something similar,
and checking on the testcase provided it seems too fragile to give
meaningful results. So I think we should dropped it for now.

> 
> 
> Regards,
> Ismael and Hector.
> 
> 
> https://sourceware.org/bugzilla/show_bug.cgi?id=22853
> Signed-off-by: Ismael Ripoll <iripoll@disca.upv.es>
> Co-Authored-By: Hector Marco-Gisbert <hmarco@hmarco.org>
> ---
>  malloc/Makefile         |   3 +
>  malloc/arena.c          |  25 ++++-
>  malloc/tst-arena-aslr.c | 213 ++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 236 insertions(+), 5 deletions(-)
>  create mode 100644 malloc/tst-arena-aslr.c
> 
> diff --git a/malloc/Makefile b/malloc/Makefile
> index 984045b5b9..dc845b1c24 100644
> --- a/malloc/Makefile
> +++ b/malloc/Makefile
> @@ -39,6 +39,8 @@ tests := mallocbug tst-malloc tst-valloc tst-calloc tst-obstack \
>       tst-malloc-too-large \
>       tst-malloc-stats-cancellation \
>       tst-tcfree1 tst-tcfree2 tst-tcfree3 \
> +     tst-arena-aslr \
> +
> 
>  tests-static := \
>       tst-interpose-static-nothread \

No '\' on last item.

> @@ -99,6 +101,7 @@ $(objpfx)tst-malloc-thread-exit: $(shared-thread-library)
>  $(objpfx)tst-malloc-thread-fail: $(shared-thread-library)
>  $(objpfx)tst-malloc-fork-deadlock: $(shared-thread-library)
>  $(objpfx)tst-malloc-stats-cancellation: $(shared-thread-library)
> +$(objpfx)tst-arena-aslr: $(shared-thread-library)
> 
>  # Export the __malloc_initialize_hook variable to libc.so.
>  LDFLAGS-tst-mallocstate = -rdynamic

Ok.

> diff --git a/malloc/arena.c b/malloc/arena.c
> index cecdb7f4c4..416559e269 100644
> --- a/malloc/arena.c
> +++ b/malloc/arena.c
> @@ -122,10 +122,15 @@ int __malloc_initialized = -1;
>          ptr = arena_get2 ((size), NULL);                      \
>    } while (0)
> 
> -/* find the heap and corresponding arena for a given ptr */
> -
> +/* find the heap and corresponding arena for a given ptr.  Note that
> +   heap_info is not HEAP_MAX_SIZE aligned any more. But a random
> +   offset from the expected alignment, known by the process. This way
> +   it is fast to get the head of the area and be ASLR friendly.
> +*/

Style: capitalize 'style' and two space after period.

> +static unsigned long __arena_rnd;

The variable is static, so no need to double underscore to handle
namespace issues.  Also I think we should use uintptr_t for its
type.

>  #define heap_for_ptr(ptr) \
> -  ((heap_info *) ((unsigned long) (ptr) & ~(HEAP_MAX_SIZE - 1)))
> +  ((heap_info *) ((((unsigned long) ptr-__arena_rnd) & ~(HEAP_MAX_SIZE - 1)) \
> +                  |  __arena_rnd))
>  #define arena_for_chunk(ptr) \
>    (chunk_main_arena (ptr) ? &main_arena : heap_for_ptr (ptr)->ar_ptr)
> 

I would prefer if we use static inline functions instead. For the
version I was intended to send, I used:

  static inline heap_info *
  heap_for_ptr (mchunkptr ptr)
  {
    return (heap_info *) ((((uintptr_t) ptr - arena_rnd)
                          & ~(HEAP_MAX_SIZE - 1)) | arena_rnd);
  }
  
  static inline struct malloc_state *
  arena_for_chunk (mchunkptr ptr)
  {
   return chunk_main_arena (ptr) ? &main_arena : heap_for_ptr (ptr)->ar_ptr;
  }


> @@ -293,6 +298,11 @@ ptmalloc_init (void)
> 
>    __malloc_initialized = 0;
> 
> +  size_t pagesize = GLRO (dl_pagesize);
> +  /* Get the entropy from the already existing ASLR. */
> +  __arena_rnd = ((unsigned long)&__arena_rnd) & (HEAP_MAX_SIZE-1) &
> +                ~(pagesize-1);
> +
>  #ifdef SHARED
>    /* In case this libc copy is in a non-default namespace, never use brk.
>       Likewise if dlopened from statically linked program.  */

The mmap arena size would be at most HEAP_MAX_SIZE << 1, which is
134217728 for 64 bit or 2097152 for 32 bit and the heap_info size
is 32 bytes on 64 bits and 16 on 32 bits.  So it would requires 
at least 22 bits for 64 bits and 17 bits for 32 bits to fully
randomize heap_info (if I didn't make any confusion here).

And relying on ASLR entropy solely covers it only for some architectures,
with the issue that it does not help for architectures that do not
support ARCH_HAS_ELF_RANDOMIZE.

So I think it would be better to use some bits from AT_RANDOM and maybe
refactor dl-osinfo.h to handle it transparently (currently it uses only 
up to 64 bits for stack check and pointer guard).  

Another option would be to either refactor Florian suggestion to use
SHA256 with AT_RANDOM, which gives us some more bits to work.  

In a long term I think the better alternative is to have a more robust
source of entropy, such as the arc4random.

Also, some style issues (like space after & and between operators).

[1] https://sourceware.org/pipermail/libc-alpha/2020-March/112042.html

> @@ -490,6 +500,11 @@ new_heap (size_t size, size_t top_pad)
>          {
>            p2 = (char *) (((unsigned long) p1 + (HEAP_MAX_SIZE - 1))
>                           & ~(HEAP_MAX_SIZE - 1));
> +          /* The heap_info is at a random offset from the alignment to
> +             HEAP_MAX_SIZE. */
> +          p2 = (char *) ((unsigned long) p2 | __arena_rnd);
> +          if (p1 + HEAP_MAX_SIZE <= p2)
> +            p2 -= HEAP_MAX_SIZE;
>            ul = p2 - p1;
>            if (ul)
>              __munmap (p1, ul);

Ok.

> @@ -500,12 +515,12 @@ new_heap (size_t size, size_t top_pad)
>        else
>          {
>            /* Try to take the chance that an allocation of only HEAP_MAX_SIZE
> -             is already aligned. */
> +             is already aligned to __arena_rnd. */
>            p2 = (char *) MMAP (0, HEAP_MAX_SIZE, PROT_NONE, MAP_NORESERVE);
>            if (p2 == MAP_FAILED)
>              return 0;
> 
> -          if ((unsigned long) p2 & (HEAP_MAX_SIZE - 1))
> +          if (((unsigned long) p2 & (HEAP_MAX_SIZE - 1)) != __arena_rnd)
>              {
>                __munmap (p2, HEAP_MAX_SIZE);
>                return 0;

Ok.

> diff --git a/malloc/tst-arena-aslr.c b/malloc/tst-arena-aslr.c
> new file mode 100644
> index 0000000000..c285111e1c
> --- /dev/null
> +++ b/malloc/tst-arena-aslr.c
> @@ -0,0 +1,213 @@
> +/* Bug 22853: aslr on thread's malloc weakened due to arena alignment.
> +   https://sourceware.org/bugzilla/show_bug.cgi?id=22853

No need to reference the full bug report link.

> +   Copyright (C) 2020 Free Software Foundation.
> +   Copying and distribution of this file, with or without modification,
> +   are permitted in any medium without royalty provided the copyright
> +   notice and this notice are preserved. This file is offered as-is,
> +   without any warranty.  */

This Copyright disclaimer does not follow the model one used for
newer files.

> +
> +#include <assert.h>
> +#include <errno.h>
> +#include <stdio.h>
> +#include <stdlib.h>
> +#include <unistd.h>
> +#include <sys/types.h>
> +#include <sys/wait.h>
> +#include <libc-diag.h>
> +#include <pthread.h>
> +#include <string.h>
> +#include <sys/mman.h>
> +
> +/* Bits that are considered to be acceptable: */
> +#define TOLERANCE 1
> +/* Samples to be run but statisticaly accurate: */
> +#define NR_SAMPLES 1000
> +
> +/* Size to be allocated in the thread's arena pool. */
> +#define MALLOC_ALLOCATED_SIZE  400
> +
> +/* Data structure sent by the sampler to the tester. */
> +struct sample_t
> +{
> +  size_t obj_mmap;
> +  size_t obj_arena;
> +} sample;
> +
> +size_t pagesize;
> +
> +static void *
> +thread_main(void * dummy)
> +{
> +    sample.obj_arena = (size_t) malloc (MALLOC_ALLOCATED_SIZE);
> +    pthread_exit(0);
> +}
> +
> +/* Creates a thread to sample malloc and mmap addresses, and writes
> +   the result to stdout. */
> +static void
> +sampler(void)
> +{
> +    int ret;
> +    pthread_t th;
> +    pthread_attr_t attrs;
> +
> +    ret = pthread_attr_init (&attrs);
> +    if (0 != ret)
> +      {
> +        perror ("pthread_attr_init");
> +        abort ();
> +      }
> +    sample.obj_mmap = (size_t)mmap( (void *)0x0, pagesize,
> +                                    PROT_READ | PROT_WRITE,
> +                                    MAP_PRIVATE | MAP_ANONYMOUS, -1 ,0);
> +    if (!sample.obj_mmap)
> +      {
> +        perror ("mmap");
> +        abort ();
> +      }
> +    if (pthread_create (&th, &attrs, thread_main, NULL))
> +      {
> +        perror ("pthread_create");
> +        abort ();
> +      }
> +    if (pthread_join (th, NULL))
> +      {
> +        perror ("pthread_join");
> +        abort ();
> +      }
> +    if (sizeof (sample) != write (1, &sample, sizeof (sample)))
> +      {
> +        perror ("write sampler");
> +        abort ();
> +      }
> +    exit(0);
> +}
> +
> +
> +struct statitics_t
> +{
> +  size_t min, max, and, or;
> +};
> +
> +static void
> +stats_init (struct statitics_t *st)
> +{
> +  st->min = st->and = ~0;
> +  st->max = st->or = 0;
> +}
> +
> +static void
> +stats_account (struct statitics_t *st, size_t value)
> +{
> +  st->min = value < st->min ? value : st->min;
> +  st->max = value > st->max ? value : st->max;
> +  st->and &= value;
> +  st->or |= value;
> +}
> +
> +/* Flipping bits, this is a "pourman" entroy estimator. There are much
> +   better and accurate entropy estimators, but they need more samples
> +   and mote time... which do not worth it. */
> +static int
> +stats_pmentropy (struct statitics_t *st)
> +{
> +
> +  return __builtin_popcountll(st->and ^ st->or);
> +}
> +
> +#if 0
> +/* Debugging the test. Not needed for production testing */
> +void
> +stats_print (struct statitics_t *st)
> +{
> +  printf ("[%18zx %18zx] %18zx %18zx %18zx %18zx %d\n", st->min, st->max,
> +          (st->max >> 2) + (st->min >> 2),
> +          st->and,
> +          st->or,
> +          st->and ^ st->or,
> +          stats_pmentropy(st));
> +}
> +#endif
> +
> +static int
> +do_test (int argc, char **argv)
> +{
> +  pid_t child;
> +  int tube[2];
> +  int wstatus;
> +  int i, mmap_entropy, arena_entropy;
> +  struct sample_t sample;
> +  struct statitics_t stats_mmap, stats_arena;
> +
> +  pagesize = sysconf (_SC_PAGESIZE);
> +
> +  if ( (2 == argc) && !strcmp (argv[1],"sample"))
> +    {
> +      sampler(); /* The role of this process is to sample one address. */
> +      exit(0);
> +    }
> +
> +  /* The role of this part is to launch NR_SAMPLES samplers and
> +     collect the output. */
> +  assert (pipe(tube) == 0);
> +
> +  stats_init (&stats_mmap);
> +  stats_init (&stats_arena);
> +
> +  /* Collect all the samples. */
> +  for (i = 0; i < NR_SAMPLES ; i++)
> +    {
> +      child = fork ();
> +      if (child < 0)
> +        {
> +          perror ("fork");
> +          exit (1);
> +        }
> +      if (0 == child)
> +        {
> +          assert (dup2(tube[1],1) != -1);
> +          execl (argv[0], argv[0], "sample", NULL);
> +          perror ("execl");
> +          abort ();
> +        }
> +      if (TEMP_FAILURE_RETRY (read(tube[0], &sample, sizeof (sample)))
> +          != sizeof (sample))
> +        {
> +          printf ("Error: can not read from child process\n");
> +      abort ();
> +        }
> +      if (TEMP_FAILURE_RETRY (waitpid (child, &wstatus, 0) != child) ||
> +          (wstatus != 0))
> +        {
> +          printf ("Error: waitpid for child process\n");
> +      abort ();
> +        }
> +      stats_account (&stats_mmap, sample.obj_mmap);
> +      stats_account (&stats_arena, sample.obj_arena);
> +    }
> +
> +  /* Compute the actual entropy and analyze the results. */
> +  mmap_entropy = stats_pmentropy (&stats_mmap);
> +  arena_entropy = stats_pmentropy (&stats_arena);
> +
> +  if ((arena_entropy + TOLERANCE) < mmap_entropy)
> +    {
> +      printf ("FAIL: malloc arena ASLR.\n");
> +      printf ("  Expected value: %d random bits\n", mmap_entropy);
> +      printf ("  But got:        %d random bits\n", arena_entropy);
> +
> +      /* stats_print(&stats_mmap);
> +         stats_print(&stats_arena); */
> +      return 1;
> +    }
> +  printf ("PASS: malloc arena ASLR.\n");
> +  return 0;
> +}
> +
> +#define TEST_FUNCTON_ARGV do_test
> +#include "../test-skeleton.c"> +
> +/* Local Variables: */
> +/* c-file-style: "gnu" */
> +/* c-basic-offset: 2 */
> +/* End: */