Re: [PATCH 16/22] libelf: check loops for running away

[Andrew Cooper <andrew.cooper3@citrix.com>]

On 07/06/13 19:27, Ian Jackson wrote:
> Ensure that libelf does not have any loops which can run away
> indefinitely even if the input is bogus.  (Grepped for \bfor, \bwhile
> and \bgoto in libelf and xc_dom_*loader*.c.)
>
> Changes needed:
>  * elf_note_next uses the note's unchecked alleged length, which might
>    wrap round.  If it does, return ELF_MAX_PTRVAL (0xfff..fff) instead,
>    which will be beyond the end of the section and so terminate the
>    caller's loop.  Also check that the returned psuedopointer is sane.
>  * In various loops over section and program headers, check that the
>    calculated header pointer is still within the image, and quit the
>    loop if it isn't.
>  * Some fixed limits to avoid potentially O(image_size^2) loops:
>     - maximum length of strings: 4K (longer ones ignored totally)
>     - maximum total number of ELF notes: 65536 (any more are ignored)
>  * Check that the total program contents (text, data) we copy or
>    initialise doesn't exceed twice the output image area size.
>  * Remove an entirely useless loop from elf_xen_parse (!)
>  * Replace a nested search loop in in xc_dom_load_elf_symtab in
>    xc_dom_elfloader.c by a precomputation of a bitmap of referenced
>    symtabs.
>
> We have not changed loops which might, in principle, iterate over the
> whole image - even if they might do so one byte at a time with a
> nontrivial access check function in the middle.
>
> This is part of the fix to a security issue, XSA-55.
>
> Signed-off-by: Ian Jackson <ian.jackson@eu.citrix.com>
>
> v5: Fix regression due to wrong image size loop limit calculation.
>     Check return value from xc_dom_malloc.
>
> v4: Fix regression due to misplacement of test in elf_shdr_by_name
>      (uninitialised variable).
>     Introduce fixed limits.
>     Avoid O(size^2) loops.
>     Check returned psuedopointer from elf_note_next is correct.
>     A few style fixes.
>
> v3: Fix a whitespace error.
>
> v2: BUGFIX: elf_shdr_by_name, elf_note_next: Reject new <= old, not just <.
>     elf_shdr_by_name: Change order of checks to be a bit clearer.
>     elf_load_bsdsyms: shdr loop check, improve chance of brokenness detection.
>     Style fixes.
> ---
>  tools/libxc/xc_dom_elfloader.c     |   33 ++++++++++++++++++------
>  xen/common/libelf/libelf-dominfo.c |   48 ++++++++++++++++++++++++------------
>  xen/common/libelf/libelf-loader.c  |   47 +++++++++++++++++++++++++++++++++-
>  xen/common/libelf/libelf-tools.c   |   28 +++++++++++++++++++-
>  xen/include/xen/libelf.h           |    3 ++
>  5 files changed, 130 insertions(+), 29 deletions(-)
>
> diff --git a/tools/libxc/xc_dom_elfloader.c b/tools/libxc/xc_dom_elfloader.c
> index eb2e3d2..81c2519 100644
> --- a/tools/libxc/xc_dom_elfloader.c
> +++ b/tools/libxc/xc_dom_elfloader.c
> @@ -28,6 +28,7 @@
>
>  #include "xg_private.h"
>  #include "xc_dom.h"
> +#include "xc_bitops.h"
>
>  #define XEN_VER "xen-3.0"
>
> @@ -118,6 +119,7 @@ static elf_errorstatus xc_dom_load_elf_symtab(struct xc_dom_image *dom,
>      ELF_PTRVAL_CHAR hdr;
>      size_t size;
>      unsigned h, count, type, i, tables = 0;
> +    unsigned long *strtab_referenced = NULL;
>
>      if ( elf_swap(elf) )
>      {
> @@ -218,22 +220,35 @@ static elf_errorstatus xc_dom_load_elf_symtab(struct xc_dom_image *dom,
>                symtab, maxaddr);
>
>      count = elf_shdr_count(&syms);
> +    /* elf_shdr_count guarantees that count is reasonable */
> +
> +    strtab_referenced = xc_dom_malloc(dom, bitmap_size(count));
> +    if ( strtab_referenced == NULL )
> +        return -1;
> +    bitmap_clear(strtab_referenced, count);
> +    /* Note the symtabs @h linked to by any strtab @i. */
> +    for ( i = 0; i < count; i++ )
> +    {
> +        shdr2 = elf_shdr_by_index(&syms, i);
> +        if ( elf_uval(&syms, shdr2, sh_type) == SHT_SYMTAB )
> +        {
> +            h = elf_uval(&syms, shdr2, sh_link);
> +            if (h < count)
> +                set_bit(h, strtab_referenced);
> +        }
> +    }
> +
>      for ( h = 0; h < count; h++ )
>      {
>          shdr = ELF_OBSOLETE_VOIDP_CAST elf_shdr_by_index(&syms, h);
> +        if ( !elf_access_ok(elf, ELF_HANDLE_PTRVAL(shdr), 1) )
> +            /* input has an insane section header count field */
> +            break;
>          type = elf_uval(&syms, shdr, sh_type);
>          if ( type == SHT_STRTAB )
>          {
> -            /* Look for a strtab @i linked to symtab @h. */
> -            for ( i = 0; i < count; i++ )
> -            {
> -                shdr2 = elf_shdr_by_index(&syms, i);
> -                if ( (elf_uval(&syms, shdr2, sh_type) == SHT_SYMTAB) &&
> -                     (elf_uval(&syms, shdr2, sh_link) == h) )
> -                    break;
> -            }
>              /* Skip symtab @h if we found no corresponding strtab @i. */
> -            if ( i == count )
> +            if ( !test_bit(h, strtab_referenced) )
>              {
>                  if ( elf_64bit(&syms) )
>                      elf_store_field(elf, shdr, e64.sh_offset, 0);
> diff --git a/xen/common/libelf/libelf-dominfo.c b/xen/common/libelf/libelf-dominfo.c
> index 0b07002..b0ba4d8 100644
> --- a/xen/common/libelf/libelf-dominfo.c
> +++ b/xen/common/libelf/libelf-dominfo.c
> @@ -221,7 +221,8 @@ elf_errorstatus elf_xen_parse_note(struct elf_binary *elf,
>  static unsigned elf_xen_parse_notes(struct elf_binary *elf,
>                                 struct elf_dom_parms *parms,
>                                 ELF_PTRVAL_CONST_VOID start,
> -                               ELF_PTRVAL_CONST_VOID end)
> +                               ELF_PTRVAL_CONST_VOID end,
> +                               unsigned *total_note_count)
>  {
>      unsigned xen_elfnotes = 0;
>      ELF_HANDLE_DECL(elf_note) note;
> @@ -233,6 +234,12 @@ static unsigned elf_xen_parse_notes(struct elf_binary *elf,
>            ELF_HANDLE_PTRVAL(note) < parms->elf_note_end;
>            note = elf_note_next(elf, note) )
>      {
> +        if ( *total_note_count >= ELF_MAX_TOTAL_NOTE_COUNT )
> +        {
> +            elf_mark_broken(elf, "too many ELF notes");
> +            break;
> +        }
> +        (*total_note_count)++;
>          note_name = elf_note_name(elf, note);
>          if ( note_name == NULL )
>              continue;

elf_note_name() will currently actually return note->desc if namesz is 0
or overflows.

Confusingly, the reference I am using
(http://www.skyfree.org/linux/references/ELF_Format.pdf) indicates that
namesz = 0 and name[0]='\0' is reserved for system use, yet in
contradition to the statement that padding is only required if
necessary.  The arguably more-real libelf from elf-utils appears to
ignore the edge case listed above.

Unfortunately, it appears that very little in this loop is resilient to
stupidly-large namesz or descsz. the note_name == NULL check looks to do
the wrong thing if there "note" points to a malformed note.


> @@ -473,6 +480,7 @@ elf_errorstatus elf_xen_parse(struct elf_binary *elf,
>      ELF_HANDLE_DECL(elf_phdr) phdr;
>      unsigned xen_elfnotes = 0;
>      unsigned i, count, more_notes;
> +    unsigned total_note_count = 0;
>
>      elf_memset_unchecked(parms, 0, sizeof(*parms));
>      parms->virt_base = UNSET_ADDR;
> @@ -487,6 +495,13 @@ elf_errorstatus elf_xen_parse(struct elf_binary *elf,
>      for ( i = 0; i < count; i++ )
>      {
>          phdr = elf_phdr_by_index(elf, i);
> +        /*
> +         * This test also arranges for the loop to terminate if the
> +         * input file has a ridiculous value for the header count: The
> +         * first putative header outside the input image will appear
> +         * to have type 0 (since out-of-range accesses read as 0) and
> +         * PT_NOTE != 0.
> +         */
>          if ( elf_uval(elf, phdr, p_type) != PT_NOTE )
>              continue;
>
> @@ -499,7 +514,8 @@ elf_errorstatus elf_xen_parse(struct elf_binary *elf,
>
>          more_notes = elf_xen_parse_notes(elf, parms,
>                                   elf_segment_start(elf, phdr),
> -                                 elf_segment_end(elf, phdr));
> +                                 elf_segment_end(elf, phdr),
> +                                 &total_note_count);
>          if ( more_notes == ELF_NOTE_INVALID )
>              return -1;
>
> @@ -517,12 +533,17 @@ elf_errorstatus elf_xen_parse(struct elf_binary *elf,
>          {
>              shdr = elf_shdr_by_index(elf, i);
>
> +            /*
> +             * See above re guarantee of loop termination.
> +             * SHT_NOTE != 0.
> +             */
>              if ( elf_uval(elf, shdr, sh_type) != SHT_NOTE )
>                  continue;
>
>              more_notes = elf_xen_parse_notes(elf, parms,
>                                       elf_section_start(elf, shdr),
> -                                     elf_section_end(elf, shdr));
> +                                     elf_section_end(elf, shdr),
> +                                     &total_note_count);
>
>              if ( more_notes == ELF_NOTE_INVALID )
>                  return -1;
> @@ -540,20 +561,15 @@ elf_errorstatus elf_xen_parse(struct elf_binary *elf,
>       */
>      if ( xen_elfnotes == 0 )
>      {
> -        count = elf_shdr_count(elf);
> -        for ( i = 0; i < count; i++ )
> +        shdr = elf_shdr_by_name(elf, "__xen_guest");
> +        if ( ELF_HANDLE_VALID(shdr) )
>          {
> -            shdr = elf_shdr_by_name(elf, "__xen_guest");
> -            if ( ELF_HANDLE_VALID(shdr) )
> -            {
> -                parms->guest_info = elf_section_start(elf, shdr);
> -                parms->elf_note_start = ELF_INVALID_PTRVAL;
> -                parms->elf_note_end   = ELF_INVALID_PTRVAL;
> -                elf_msg(elf, "%s: __xen_guest: \"%s\"\n", __FUNCTION__,
> -                        elf_strfmt(elf, parms->guest_info));
> -                elf_xen_parse_guest_info(elf, parms);
> -                break;
> -            }
> +            parms->guest_info = elf_section_start(elf, shdr);
> +            parms->elf_note_start = ELF_INVALID_PTRVAL;
> +            parms->elf_note_end   = ELF_INVALID_PTRVAL;
> +            elf_msg(elf, "%s: __xen_guest: \"%s\"\n", __FUNCTION__,
> +                    elf_strfmt(elf, parms->guest_info));
> +            elf_xen_parse_guest_info(elf, parms);
>          }
>      }
>
> diff --git a/xen/common/libelf/libelf-loader.c b/xen/common/libelf/libelf-loader.c
> index 937c99b..47957aa 100644
> --- a/xen/common/libelf/libelf-loader.c
> +++ b/xen/common/libelf/libelf-loader.c
> @@ -75,6 +75,9 @@ elf_errorstatus elf_init(struct elf_binary *elf, const char *image_input, size_t
>      for ( i = 0; i < count; i++ )
>      {
>          shdr = elf_shdr_by_index(elf, i);
> +        if ( !elf_access_ok(elf, ELF_HANDLE_PTRVAL(shdr), 1) )
> +            /* input has an insane section header count field */
> +            break;
>          if ( elf_uval(elf, shdr, sh_type) != SHT_SYMTAB )
>              continue;
>          elf->sym_tab = shdr;
> @@ -170,6 +173,9 @@ void elf_parse_bsdsyms(struct elf_binary *elf, uint64_t pstart)
>      for ( i = 0; i < elf_shdr_count(elf); i++ )
>      {
>          shdr = elf_shdr_by_index(elf, i);
> +        if ( !elf_access_ok(elf, ELF_HANDLE_PTRVAL(shdr), 1) )
> +            /* input has an insane section header count field */
> +            break;
>          type = elf_uval(elf, shdr, sh_type);
>          if ( (type == SHT_STRTAB) || (type == SHT_SYMTAB) )
>              sz = elf_round_up(elf, sz + elf_uval(elf, shdr, sh_size));
> @@ -224,6 +230,9 @@ do {                                            \
>
>      for ( i = 0; i < elf_shdr_count(elf); i++ )
>      {
> +        elf_ptrval old_shdr_p;
> +        elf_ptrval new_shdr_p;
> +
>          type = elf_uval(elf, shdr, sh_type);
>          if ( (type == SHT_STRTAB) || (type == SHT_SYMTAB) )
>          {
> @@ -235,8 +244,16 @@ do {                                            \
>               elf_hdr_elm(elf, shdr, sh_offset, maxva - symtab_addr);
>               maxva = ELF_OBSOLETE_VOIDP_CAST elf_round_up(elf, (unsigned long)maxva + sz);
>          }
> -        shdr = ELF_MAKE_HANDLE(elf_shdr, ELF_HANDLE_PTRVAL(shdr) +
> -                            (unsigned long)elf_uval(elf, elf->ehdr, e_shentsize));
> +        old_shdr_p = ELF_HANDLE_PTRVAL(shdr);
> +        new_shdr_p = old_shdr_p + elf_uval(elf, elf->ehdr, e_shentsize);
> +        if ( new_shdr_p <= old_shdr_p ) /* wrapped or stuck */
> +        {
> +            elf_mark_broken(elf, "bad section header length");
> +            break;
> +        }
> +        if ( !elf_access_ok(elf, new_shdr_p, 1) ) /* outside image */
> +            break;
> +        shdr = ELF_MAKE_HANDLE(elf_shdr, new_shdr_p);
>      }
>
>      /* Write down the actual sym size. */
> @@ -256,6 +273,9 @@ void elf_parse_binary(struct elf_binary *elf)
>      for ( i = 0; i < count; i++ )
>      {
>          phdr = elf_phdr_by_index(elf, i);
> +        if ( !elf_access_ok(elf, ELF_HANDLE_PTRVAL(phdr), 1) )
> +            /* input has an insane program header count field */
> +            break;
>          if ( !elf_phdr_is_loadable(elf, phdr) )
>              continue;
>          paddr = elf_uval(elf, phdr, p_paddr);
> @@ -278,11 +298,20 @@ elf_errorstatus elf_load_binary(struct elf_binary *elf)
>      ELF_HANDLE_DECL(elf_phdr) phdr;
>      uint64_t i, count, paddr, offset, filesz, memsz;
>      ELF_PTRVAL_VOID dest;
> +    /*
> +     * Let bizarre ELFs write the output image up to twice; this
> +     * calculation is just to ensure our copying loop is no worse than
> +     * O(domain_size).
> +     */
> +    uint64_t remain_allow_copy = (uint64_t)elf->dest_size * 2;
>
>      count = elf_uval(elf, elf->ehdr, e_phnum);
>      for ( i = 0; i < count; i++ )
>      {
>          phdr = elf_phdr_by_index(elf, i);
> +        if ( !elf_access_ok(elf, ELF_HANDLE_PTRVAL(phdr), 1) )
> +            /* input has an insane program header count field */
> +            break;
>          if ( !elf_phdr_is_loadable(elf, phdr) )
>              continue;
>          paddr = elf_uval(elf, phdr, p_paddr);
> @@ -290,6 +319,20 @@ elf_errorstatus elf_load_binary(struct elf_binary *elf)
>          filesz = elf_uval(elf, phdr, p_filesz);
>          memsz = elf_uval(elf, phdr, p_memsz);
>          dest = elf_get_ptr(elf, paddr);
> +
> +        /*
> +         * We need to check that the input image doesn't have us copy
> +         * the whole image zillions of times, as that could lead to
> +         * O(n^2) time behaviour and possible DoS by a malicous ELF.
> +         */
> +        if ( remain_allow_copy < memsz )
> +        {
> +            elf_mark_broken(elf, "program segments total to more"
> +                            " than the input image size");
> +            break;
> +        }
> +        remain_allow_copy -= memsz;
> +
>          elf_msg(elf, "%s: phdr %" PRIu64 " at 0x%"ELF_PRPTRVAL" -> 0x%"ELF_PRPTRVAL"\n",
>                  __func__, i, dest, (ELF_PTRVAL_VOID)(dest + filesz));
>          if ( elf_load_image(elf, dest, ELF_IMAGE_BASE(elf) + offset, filesz, memsz) != 0 )
> diff --git a/xen/common/libelf/libelf-tools.c b/xen/common/libelf/libelf-tools.c
> index 6543f33..ef13b0d 100644
> --- a/xen/common/libelf/libelf-tools.c
> +++ b/xen/common/libelf/libelf-tools.c
> @@ -131,7 +131,16 @@ uint64_t elf_round_up(struct elf_binary *elf, uint64_t addr)
>
>  unsigned elf_shdr_count(struct elf_binary *elf)
>  {
> -    return elf_uval(elf, elf->ehdr, e_shnum);
> +    unsigned count = elf_uval(elf, elf->ehdr, e_shnum);
> +    uint64_t max = elf->size / sizeof(Elf32_Shdr);
> +    if (max > ~(unsigned)0)
> +        max = ~(unsigned)0; /* Xen doesn't have limits.h :-/ */
> +    if (count > max)
> +    {
> +        elf_mark_broken(elf, "far too many section headers");
> +        count = max;
> +    }
> +    return count;
>  }
>
>  unsigned elf_phdr_count(struct elf_binary *elf)
> @@ -149,6 +158,9 @@ ELF_HANDLE_DECL(elf_shdr) elf_shdr_by_name(struct elf_binary *elf, const char *n
>      for ( i = 0; i < count; i++ )
>      {
>          shdr = elf_shdr_by_index(elf, i);
> +        if ( !elf_access_ok(elf, ELF_HANDLE_PTRVAL(shdr), 1) )
> +            /* input has an insane section header count field */
> +            break;

It occurs to me here that elf_access_ok appears to checks the range
[&shdr, &shdr+1] (&shdr relative to start of elf).

Should this not be be elf_access_ok(elf, ELF_HANDLE_PTRVAL(shdr), sizeof
*shdr) ?

(It is getting quite late so I might be completely confused on this point)

>          sname = elf_section_name(elf, shdr);
>          if ( sname && !strcmp(sname, name) )
>              return shdr;
> @@ -204,6 +216,11 @@ const char *elf_strval(struct elf_binary *elf, elf_ptrval start)
>          if ( !elf_access_unsigned(elf, start, length, 1) )
>              /* ok */
>              return ELF_UNSAFE_PTR(start);
> +        if ( length >= ELF_MAX_STRING_LENGTH )
> +        {
> +            elf_mark_broken(elf, "excessively long string");
> +            return NULL;
> +        }
>      }
>  }
>
> @@ -327,7 +344,14 @@ ELF_HANDLE_DECL(elf_note) elf_note_next(struct elf_binary *elf, ELF_HANDLE_DECL(
>      unsigned namesz = (elf_uval(elf, note, namesz) + 3) & ~3;
>      unsigned descsz = (elf_uval(elf, note, descsz) + 3) & ~3;
>
> -    return ELF_MAKE_HANDLE(elf_note, ELF_HANDLE_PTRVAL(note) + elf_size(elf, note) + namesz + descsz);
> +    elf_ptrval ptrval = ELF_HANDLE_PTRVAL(note)
> +        + elf_size(elf, note) + namesz + descsz;
> +
> +    if ( ( ptrval <= ELF_HANDLE_PTRVAL(note) || /* wrapped or stuck */
> +           !elf_access_ok(elf, ELF_HANDLE_PTRVAL(note), 1) ) )
> +        ptrval = ELF_MAX_PTRVAL; /* terminate caller's loop */
> +
> +    return ELF_MAKE_HANDLE(elf_note, ptrval);

The ptrval check is still suscpetable to a double overflow from
slightly-larger-than-half-UINT_MAX namesz and descsz.  Also, the
rounding up at the top is susceptible to overflow.


>  }
>
>  /* ------------------------------------------------------------------------ */
> diff --git a/xen/include/xen/libelf.h b/xen/include/xen/libelf.h
> index e4588de..4ca6b8f 100644
> --- a/xen/include/xen/libelf.h
> +++ b/xen/include/xen/libelf.h
> @@ -51,6 +51,9 @@ typedef void elf_log_callback(struct elf_binary*, void *caller_data,
>
>  #endif
>
> +#define ELF_MAX_STRING_LENGTH 4096
> +#define ELF_MAX_TOTAL_NOTE_COUNT 65536
> +

With a view to stupidly-long elf notes, should probably have
ELF_MAX_NOTE_{NAME,DESC}_LENGTH here.

~Andrew

>  /* ------------------------------------------------------------------------ */
>
>  /* Macros for accessing the input image and output area. */
> --
> 1.7.2.5
>