Add Safe-Linking to fastbins

Safe-Linking is a security mechanism that protects single-linked
lists (such as the fastbins) from being tampered by attackers. The
mechanism makes use of randomness from ASLR (mmap_base), and when
combined with chunk alignment integrity checks, it protects the
pointers from being hijacked by an attacker.

While Safe-Unlinking protects double-linked lists (such as the small
bins), there wasn't any similar protection for attacks against
single-linked lists. This solution protects against 3 common attacks:
  * Partial pointer override: modifies the lower bytes (Little Endian)
  * Full pointer override: hijacks the pointer to an attacker's location
  * Unaligned chunks: pointing the list to an unaligned address

The design assumes an attacker doesn't know where the heap is located,
and uses the ASLR randomness to "sign" the single-linked pointers. We
mark the pointer as P and the location in which it is stored as L, and
the calculation will be:
  * PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
  * *L = PROTECT(P)

This way, the random bits from the address L (which start at the bits
in the PAGE_SHIFT position), will be merged with the LSB of the stored
protected pointer. This protection layer prevents an attacker from
modifying the pointer into a controlled value.

An additional check that the chunks are MALLOC_ALIGNed adds an
important layer:
  * Attackers can't point to illegal (unaligned) memory addresses
  * Attackers must guess correctly the alignment bits

On standard 32 bit Linux machines, an attacker will directly fail 7
out of 8 times, and on 64 bit machines it will fail 15 out of 16
times.

The proposed solution adds 3-4 asm instructions per malloc()/free()
and therefore has only minor performance implications if it has
any. A similar protection was added to Chromium's version of TCMalloc
in 2013, and according to their documentation the performance overhead
was less than 2%.

Signed-off-by: Eyal Itkin <eyalit@checkpoint.com>

1 files changed, 4 insertions, 2 deletions

diff --git a/libc/stdlib/malloc-standard/malloc.c b/libc/stdlib/malloc-standard/malloc.c
index 1a6d4dc1c..1f898eb29 100644
--- a/libc/stdlib/malloc-standard/malloc.c
+++ b/libc/stdlib/malloc-standard/malloc.c
@@ -260,12 +260,13 @@ void __do_check_malloc_state(void)
 	    assert(p == 0);
 
 	while (p != 0) {
+	    CHECK_PTR(p);
 	    /* each chunk claims to be inuse */
 	    __do_check_inuse_chunk(p);
 	    total += chunksize(p);
 	    /* chunk belongs in this bin */
 	    assert(fastbin_index(chunksize(p)) == i);
-	    p = p->fd;
+	    p = REVEAL_PTR(&p->fd, p->fd);
 	}
     }
 
@@ -855,7 +856,8 @@ void* malloc(size_t bytes)
     if ((unsigned long)(nb) <= (unsigned long)(av->max_fast)) {
 	fb = &(av->fastbins[(fastbin_index(nb))]);
 	if ( (victim = *fb) != 0) {
-	    *fb = victim->fd;
+	    CHECK_PTR(victim);
+	    *fb = REVEAL_PTR(&victim->fd, victim->fd);
 	    check_remalloced_chunk(victim, nb);
 	    retval = chunk2mem(victim);
 	    goto DONE;