libelf: check all pointer accesses

We change the ELF_PTRVAL and ELF_HANDLE types and associated macros:

 * PTRVAL becomes a uintptr_t, for which we provide a typedef
   elf_ptrval.  This means no arithmetic done on it can overflow so
   the compiler cannot do any malicious invalid pointer arithmetic
   "optimisations".  It also means that any places where we
   dereference one of these pointers without using the appropriate
   macros or functions become a compilation error.

   So we can be sure that we won't miss any memory accesses.

   All the PTRVAL variables were previously void* or char*, so
   the actual address calculations are unchanged.

 * ELF_HANDLE becomes a union, one half of which keeps the pointer
   value and the other half of which is just there to record the
   type.

   The new type is not a pointer type so there can be no address
   calculations on it whose meaning would change.  Every assignment or
   access has to go through one of our macros.

 * The distinction between const and non-const pointers and char*s
   and void*s in libelf goes away.  This was not important (and
   anyway libelf tended to cast away const in various places).

 * The fields elf->image and elf->dest are renamed.  That proves
   that we haven't missed any unchecked uses of these actual
   pointer values.

 * The caller may fill in elf->caller_xdest_base and _size to
   specify another range of memory which is safe for libelf to
   access, besides the input and output images.

 * When accesses fail due to being out of range, we mark the elf
   "broken".  This will be checked and used for diagnostics in
   a following patch.

   We do not check for write accesses to the input image.  This is
   because libelf actually does this in a number of places.  So we
   simply permit that.

 * Each caller of libelf which used to set dest now sets
   dest_base and dest_size.

 * In xc_dom_load_elf_symtab we provide a new actual-pointer
   value hdr_ptr which we get from mapping the guest's kernel
   area and use (checking carefully) as the caller_xdest area.

 * The STAR(h) macro in libelf-dominfo.c now uses elf_access_unsigned.

 * elf-init uses the new elf_uval_3264 accessor to access the 32-bit
   fields, rather than an unchecked field access (ie, unchecked
   pointer access).

 * elf_uval has been reworked to use elf_uval_3264.  Both of these
   macros are essentially new in this patch (although they are derived
   from the old elf_uval) and need careful review.

 * ELF_ADVANCE_DEST is now safe in the sense that you can use it to
   chop parts off the front of the dest area but if you chop more than
   is available, the dest area is simply set to be empty, preventing
   future accesses.

 * We introduce some #defines for memcpy, memset, memmove and strcpy:
    - We provide elf_memcpy_safe and elf_memset_safe which take
      PTRVALs and do checking on the supplied pointers.
    - Users inside libelf must all be changed to either
      elf_mem*_unchecked (which are just like mem*), or
      elf_mem*_safe (which take PTRVALs) and are checked.  Any
      unchanged call sites become compilation errors.

 * We do _not_ at this time fix elf_access_unsigned so that it doesn't
   make unaligned accesses.  We hope that unaligned accesses are OK on
   every supported architecture.  But it does check the supplied
   pointer for validity.

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>

v7: Remove a spurious whitespace change.

v5: Use allow_size value from xc_dom_vaddr_to_ptr to set xdest_size
     correctly.
    If ELF_ADVANCE_DEST advances past the end, mark the elf broken.
    Always regard NULL allowable region pointers (e.g. dest_base)
     as invalid (since NULL pointers don't point anywhere).

v4: Fix ELF_UNSAFE_PTR to work on 32-bit even when provided 64-bit
     values.
    Fix xc_dom_load_elf_symtab not to call XC_DOM_PAGE_SIZE
     unnecessarily if load is false.  This was a regression.

v3.1:
    Introduce a change to elf_store_field to undo the effects of
     the v3.1 change to the previous patch (the definition there
     is not compatible with the new types).

v3: Fix a whitespace error.

v2 was Acked-by: Ian Campbell <ian.campbell@citrix.com>

v2: BUGFIX: elf_strval: Fix loop termination condition to actually work.
    BUGFIX: elf_strval: Fix return value to not always be totally wild.
    BUGFIX: xc_dom_load_elf_symtab: do proper check for small header size.
    xc_dom_load_elf_symtab: narrow scope of `hdr_ptr'.
    xc_dom_load_elf_symtab: split out uninit'd symtab.class ref fix.
    More comments on the lifetime/validity of elf-> dest ptrs etc.
    libelf.h: write "obsolete" out in full
    libelf.h: rename "dontuse" to "typeonly" and add doc comment
    elf_ptrval_in_range: Document trustedness of arguments.
    Style and commit message fixes.

4 files changed, 123 insertions, 14 deletions

diff --git a/xen/common/libelf/libelf-dominfo.c b/xen/common/libelf/libelf-dominfo.c
index ba0dc83732..b9a4e25b3e 100644
--- a/xen/common/libelf/libelf-dominfo.c
+++ b/xen/common/libelf/libelf-dominfo.c
@@ -254,7 +254,7 @@ int elf_xen_parse_guest_info(struct elf_binary *elf,
     int len;
 
     h = parms->guest_info;
-#define STAR(h) (*(h))
+#define STAR(h) (elf_access_unsigned(elf, (h), 0, 1))
     while ( STAR(h) )
     {
         elf_memset_unchecked(name, 0, sizeof(name));
diff --git a/xen/common/libelf/libelf-loader.c b/xen/common/libelf/libelf-loader.c
index f7fe28308f..878552ef08 100644
--- a/xen/common/libelf/libelf-loader.c
+++ b/xen/common/libelf/libelf-loader.c
@@ -24,23 +24,25 @@
 
 /* ------------------------------------------------------------------------ */
 
-int elf_init(struct elf_binary *elf, const char *image, size_t size)
+int elf_init(struct elf_binary *elf, const char *image_input, size_t size)
 {
     ELF_HANDLE_DECL(elf_shdr) shdr;
     uint64_t i, count, section, offset;
 
-    if ( !elf_is_elfbinary(image) )
+    if ( !elf_is_elfbinary(image_input) )
     {
         elf_err(elf, "%s: not an ELF binary\n", __FUNCTION__);
         return -1;
     }
 
     elf_memset_unchecked(elf, 0, sizeof(*elf));
-    elf->image = image;
+    elf->image_base = image_input;
     elf->size = size;
-    elf->ehdr = (elf_ehdr *)image;
-    elf->class = elf->ehdr->e32.e_ident[EI_CLASS];
-    elf->data = elf->ehdr->e32.e_ident[EI_DATA];
+    elf->ehdr = ELF_MAKE_HANDLE(elf_ehdr, (elf_ptrval)image_input);
+    elf->class = elf_uval_3264(elf, elf->ehdr, e32.e_ident[EI_CLASS]);
+    elf->data = elf_uval_3264(elf, elf->ehdr, e32.e_ident[EI_DATA]);
+    elf->caller_xdest_base = NULL;
+    elf->caller_xdest_size = 0;
 
     /* Sanity check phdr. */
     offset = elf_uval(elf, elf->ehdr, e_phoff) +
@@ -300,7 +302,7 @@ int elf_load_binary(struct elf_binary *elf)
 
 ELF_PTRVAL_VOID elf_get_ptr(struct elf_binary *elf, unsigned long addr)
 {
-    return elf->dest + addr - elf->pstart;
+    return ELF_REALPTR2PTRVAL(elf->dest_base) + addr - elf->pstart;
 }
 
 uint64_t elf_lookup_addr(struct elf_binary * elf, const char *symbol)
diff --git a/xen/common/libelf/libelf-private.h b/xen/common/libelf/libelf-private.h
index 0d4dcf665d..0bd9e66e52 100644
--- a/xen/common/libelf/libelf-private.h
+++ b/xen/common/libelf/libelf-private.h
@@ -86,6 +86,19 @@ do { strncpy((d),(s),sizeof((d))-1);            \
 
 #endif
 
+#undef memcpy
+#undef memset
+#undef memmove
+#undef strcpy
+
+#define memcpy  MISTAKE_unspecified_memcpy
+#define memset  MISTAKE_unspecified_memset
+#define memmove MISTAKE_unspecified_memmove
+#define strcpy  MISTAKE_unspecified_strcpy
+  /* This prevents libelf from using these undecorated versions
+   * of memcpy, memset, memmove and strcpy.  Every call site
+   * must either use elf_mem*_unchecked, or elf_mem*_safe. */
+
 #endif /* __LIBELF_PRIVATE_H_ */
 
 /*
diff --git a/xen/common/libelf/libelf-tools.c b/xen/common/libelf/libelf-tools.c
index fa7dedd2b1..08ab0279de 100644
--- a/xen/common/libelf/libelf-tools.c
+++ b/xen/common/libelf/libelf-tools.c
@@ -20,28 +20,100 @@
 
 /* ------------------------------------------------------------------------ */
 
-uint64_t elf_access_unsigned(struct elf_binary * elf, const void *ptr,
-                             uint64_t offset, size_t size)
+void elf_mark_broken(struct elf_binary *elf, const char *msg)
 {
+    if ( elf->broken == NULL )
+        elf->broken = msg;
+}
+
+const char *elf_check_broken(const struct elf_binary *elf)
+{
+    return elf->broken;
+}
+
+static int elf_ptrval_in_range(elf_ptrval ptrval, uint64_t size,
+                               const void *region, uint64_t regionsize)
+    /*
+     * Returns true if the putative memory area [ptrval,ptrval+size>
+     * is completely inside the region [region,region+regionsize>.
+     *
+     * ptrval and size are the untrusted inputs to be checked.
+     * region and regionsize are trusted and must be correct and valid,
+     * although it is OK for region to perhaps be maliciously NULL
+     * (but not some other malicious value).
+     */
+{
+    elf_ptrval regionp = (elf_ptrval)region;
+
+    if ( (region == NULL) ||
+         (ptrval < regionp) ||              /* start is before region */
+         (ptrval > regionp + regionsize) || /* start is after region */
+         (size > regionsize - (ptrval - regionp)) ) /* too big */
+        return 0;
+    return 1;
+}
+
+int elf_access_ok(struct elf_binary * elf,
+                  uint64_t ptrval, size_t size)
+{
+    if ( elf_ptrval_in_range(ptrval, size, elf->image_base, elf->size) )
+        return 1;
+    if ( elf_ptrval_in_range(ptrval, size, elf->dest_base, elf->dest_size) )
+        return 1;
+    if ( elf_ptrval_in_range(ptrval, size,
+                             elf->caller_xdest_base, elf->caller_xdest_size) )
+        return 1;
+    elf_mark_broken(elf, "out of range access");
+    return 0;
+}
+
+void elf_memcpy_safe(struct elf_binary *elf, elf_ptrval dst,
+                     elf_ptrval src, size_t size)
+{
+    if ( elf_access_ok(elf, dst, size) &&
+         elf_access_ok(elf, src, size) )
+    {
+        /* use memmove because these checks do not prove that the
+         * regions don't overlap and overlapping regions grant
+         * permission for compiler malice */
+        elf_memmove_unchecked(ELF_UNSAFE_PTR(dst), ELF_UNSAFE_PTR(src), size);
+    }
+}
+
+void elf_memset_safe(struct elf_binary *elf, elf_ptrval dst, int c, size_t size)
+{
+    if ( elf_access_ok(elf, dst, size) )
+    {
+        elf_memset_unchecked(ELF_UNSAFE_PTR(dst), c, size);
+    }
+}
+
+uint64_t elf_access_unsigned(struct elf_binary * elf, elf_ptrval base,
+                             uint64_t moreoffset, size_t size)
+{
+    elf_ptrval ptrval = base + moreoffset;
     int need_swap = elf_swap(elf);
     const uint8_t *u8;
     const uint16_t *u16;
     const uint32_t *u32;
     const uint64_t *u64;
 
+    if ( !elf_access_ok(elf, ptrval, size) )
+        return 0;
+
     switch ( size )
     {
     case 1:
-        u8 = ptr + offset;
+        u8 = (const void*)ptrval;
         return *u8;
     case 2:
-        u16 = ptr + offset;
+        u16 = (const void*)ptrval;
         return need_swap ? bswap_16(*u16) : *u16;
     case 4:
-        u32 = ptr + offset;
+        u32 = (const void*)ptrval;
         return need_swap ? bswap_32(*u32) : *u32;
     case 8:
-        u64 = ptr + offset;
+        u64 = (const void*)ptrval;
         return need_swap ? bswap_64(*u64) : *u64;
     default:
         return 0;
@@ -122,6 +194,28 @@ const char *elf_section_name(struct elf_binary *elf,
     return elf_strval(elf, elf->sec_strtab + elf_uval(elf, shdr, sh_name));
 }
 
+const char *elf_strval(struct elf_binary *elf, elf_ptrval start)
+{
+    uint64_t length;
+
+    for ( length = 0; ; length++ ) {
+        if ( !elf_access_ok(elf, start + length, 1) )
+            return NULL;
+        if ( !elf_access_unsigned(elf, start, length, 1) )
+            /* ok */
+            return ELF_UNSAFE_PTR(start);
+    }
+}
+
+const char *elf_strfmt(struct elf_binary *elf, elf_ptrval start)
+{
+    const char *str = elf_strval(elf, start);
+
+    if ( str == NULL )
+        return "(invalid)";
+    return str;
+}
+
 ELF_PTRVAL_CONST_VOID elf_section_start(struct elf_binary *elf, ELF_HANDLE_DECL(elf_shdr) shdr)
 {
     return ELF_IMAGE_BASE(elf) + elf_uval(elf, shdr, sh_offset);