Re: [PATCH] malloc/malloc.c: Mitigate null-byte overflow attacks

[Florian Weimer <fweimer at redhat dot com>]

On 10/27/2017 05:17 AM, Moritz Eckert wrote:
> diff --git a/malloc/malloc.c b/malloc/malloc.c
> index d3fcadd20e..73fc98d2c3 100644
> --- a/malloc/malloc.c
> +++ b/malloc/malloc.c
> @@ -1426,6 +1426,12 @@ typedef struct malloc_chunk *mbinptr;
>         }									      \
>   }
>   
> +/* Check if prev_size is consistent with size*/
> +#define prev_size_is_sane(p, prevsize) {				   \
> +    if (__builtin_expect (prevsize !=  chunksize (p), 0))		      \
> +        malloc_printerr ("corrupted size vs. prev_size");		      \
> +}
> +
>   /*
>      Indexing
>   
> @@ -4227,6 +4233,7 @@ _int_free (mstate av, mchunkptr p, int have_lock)
>         prevsize = prev_size (p);
>         size += prevsize;
>         p = chunk_at_offset(p, -((long) prevsize));
> +      prev_size_is_sane(p, prevsize)
>         unlink(av, p, bck, fwd);
>       }

More context for the unpatched code:

    /* consolidate backward */
    if (!prev_inuse(p)) {
      prevsize = prev_size (p);
      size += prevsize;
      p = chunk_at_offset(p, -((long) prevsize));
      unlink(av, p, bck, fwd);
    }

I'm not really familiar with the malloc code, so I'll try to summarize 
my understanding.

p is the pointer being freed.  I assume the goal is to mitigate a 
single-byte overwrite of the lowest byte of the chunk header for p.  The 
overwrite clears the PREV_INUSE bit, and therefore triggers 
reinterpretation of the allocated object contents as heap metadata 
because free will now read the previous size (prev_size) at p.  The 
value of prev_size is very likely under the control of the exploit 
writer because it comes *before* the overwritten byte.  So I think it 
would still be feasible to install a fake chunk and conduct an 
unlink-based attack.

As far as I can tell, there are three ways to mitigate single-NUL write 
attacks reliably:

(1) Store the chunk size (with the PREV_INUSE) in something else but 
little-endian format.  We could use big endian, or simply a rotated 
representation, whatever has lower run-time overhead.  (This is 
something which could be done as part of the heap protector, or by 
itself.  The existing accessor macros should directly support this.)

(2) Flip the meaning of the PREV_INUSE bit, so that the attacker would 
have to write a non-NUL byte.

(3) Always allocate at least one byte more than the application needs, 
so that single-byte overflows never touch metadata.  The heap arena 
layout does not need the a full word of metadata for allocated chunks:

  * 32-bit: 1 MiB per heap, minimum allocation 8, 17 bit counter
  * 64-bit: 64 MiB per heap, minimum allocation 16, 22 bit counter

So we could compress the header to 3 bytes: We can encode the IS_MMAPPED 
bit with an otherwise impossible size counter and store the actual chunk 
size in a separate field.  The PREV_INUSE and NON_MAIN_ARENA bits would 
still be needed.  And we would have to use mmap for large allocations 
instead of sbrk even on the main arena.


Thanks,
Florian