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@eu.citrix.com>
Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>

v8: Fix the two loops in libelf-dominfo.c; the comment about
     PT_NOTE and SHT_NOTE wasn't true because the checks did
     "continue", not "break".
    Add a comment about elf_note_next's expectations of the caller's
     loop conditions (which most plausible callers will follow anyway).

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.

1 files changed, 24 insertions, 9 deletions

diff --git a/tools/libxc/xc_dom_elfloader.c b/tools/libxc/xc_dom_elfloader.c
index 75e469a451..3b835ee5d6 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);