[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Xen-devel] [PATCH 16/22] libelf: check loops for running away



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@xxxxxxxxxxxxx>

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;
@@ -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;
         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);
 }
 
 /* ------------------------------------------------------------------------ */
diff --git a/xen/include/xen/libelf.h b/xen/include/xen/libelf.h
index 87e6f40..f23a344 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
+
 /* ------------------------------------------------------------------------ */
 
 /* Macros for accessing the input image and output area. */
-- 
1.7.2.5


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel


 


Rackspace

Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.