malloc hardening proposal

0001-malloc-Additional-checks-for-unsorted-bin-integrity-.patch

From c17165069c8430069527fcf2e9abf4377807cdc3 Mon Sep 17 00:00:00 2001
From: Istvan Kurucsai <pistukem@gmail.com>
Date: Sat, 5 Nov 2016 13:11:04 +0100
Subject: [PATCH 1/9] malloc: Additional checks for unsorted bin integrity I.

Ensure the following properties of chunks encountered during binning:
- victim chunk has reasonable size
- next chunk has reasonable size
- next->prev_size == victim->size
- valid double linked list
- PREV_INUSE of next chunk is unset

    * malloc/malloc.c (_int_malloc): Additional binning code checks.
---
 malloc/malloc.c | 37 ++++++++++++++++++++++++++++++++-----
 1 file changed, 32 insertions(+), 5 deletions(-)

diff --git a/malloc/malloc.c b/malloc/malloc.c
index 584edbf..448c241 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -3325,6 +3325,7 @@ _int_malloc (mstate av, size_t bytes)
   INTERNAL_SIZE_T size;             /* its size */
   int victim_index;                 /* its bin index */
 
+  mchunkptr next;                   /* next contiguous chunk */
   mchunkptr remainder;              /* remainder from a split */
   unsigned long remainder_size;     /* its size */
 
@@ -3469,12 +3470,38 @@ _int_malloc (mstate av, size_t bytes)
       while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
         {
           bck = victim->bk;
-          if (__builtin_expect (chunksize_nomask (victim) <= 2 * SIZE_SZ, 0)
-              || __builtin_expect (chunksize_nomask (victim)
-				   > av->system_mem, 0))
-            malloc_printerr (check_action, "malloc(): memory corruption",
-                             chunk2mem (victim), av);
           size = chunksize (victim);
+          next = chunk_at_offset (victim, size);
+
+          if (__glibc_unlikely (chunksize_nomask (victim) <= 2 * SIZE_SZ)
+              || __glibc_unlikely (chunksize_nomask (victim) > av->system_mem))
+            {
+              errstr = "malloc(): invalid size (unsorted)";
+              goto errout;
+            }
+          if (__glibc_unlikely (chunksize_nomask (next) < 2 * SIZE_SZ)
+              || __glibc_unlikely (chunksize_nomask (next) > av->system_mem))
+            {
+              errstr = "malloc(): invalid next size (unsorted)";
+              goto errout;
+            }
+          if (__glibc_unlikely ((prev_size (next) & ~(SIZE_BITS)) != size))
+            {
+              errstr = "malloc(): mismatching next->prev_size (unsorted)";
+              goto errout;
+            }
+          if (__glibc_unlikely (bck->fd != victim)
+              || __glibc_unlikely (victim->fd != unsorted_chunks (av)))
+            {
+              errstr = "malloc(): unsorted double linked list corrupted";
+              goto errout;
+            }
+          if (__glibc_unlikely (prev_inuse(next)))
+            {
+              errstr = "malloc(): invalid next->prev_inuse (unsorted)";
+              goto errout;
+            }
+
 
           /*
              If a small request, try to use last remainder if it is the
-- 
2.7.4

0002-malloc-Harden-unlink-further.patch

From 4bbde1d06c6fb83332b94e3658ce878c53b883a6 Mon Sep 17 00:00:00 2001
From: Istvan Kurucsai <pistukem@gmail.com>
Date: Sat, 5 Nov 2016 13:32:27 +0100
Subject: [PATCH 2/9] malloc: Harden unlink further.

This commit ensures that a single pointer at a known location
cannot be used as both the FD->bk and BK->fd links to pass the
integrity checks.

    * malloc/malloc.c (unlink): Additional integrity check.
---
 malloc/malloc.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/malloc/malloc.c b/malloc/malloc.c
index 448c241..517f834 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -1378,7 +1378,9 @@ typedef struct malloc_chunk *mbinptr;
 #define unlink(AV, P, BK, FD) {                                            \
     FD = P->fd;								      \
     BK = P->bk;								      \
-    if (__builtin_expect (FD->bk != P || BK->fd != P, 0))		      \
+    if (__builtin_expect (FD->bk != P, 0)				      \
+        || __builtin_expect (BK->fd != P, 0)				      \
+        || __builtin_expect (&(FD->bk) == &(BK->fd), 0))	              \
       malloc_printerr (check_action, "corrupted double-linked list", P, AV);  \
     else {								      \
         FD->bk = BK;							      \
-- 
2.7.4

0003-malloc-Add-check-for-top-size-corruption.patch

From f3e90756829a7df0c8f87f9a4671f8b9532e14eb Mon Sep 17 00:00:00 2001
From: Istvan Kurucsai <pistukem@gmail.com>
Date: Sat, 5 Nov 2016 13:37:12 +0100
Subject: [PATCH 3/9] malloc: Add check for top size corruption.

Ensure that the size of top is below av->system_mem.

    * malloc/malloc.c (_int_malloc): Check top size.
---
 malloc/malloc.c | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/malloc/malloc.c b/malloc/malloc.c
index 517f834..6aed08f 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -3829,6 +3829,13 @@ _int_malloc (mstate av, size_t bytes)
 
       if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
         {
+          if (__glibc_unlikely ((unsigned long) (size) > 
+                                (unsigned long) (av->system_mem)))
+            {
+              errstr = "malloc(): corrupted top chunk";
+              goto errout;
+            }
+
           remainder_size = size - nb;
           remainder = chunk_at_offset (victim, nb);
           av->top = remainder;
-- 
2.7.4

0004-malloc-Ensure-that-the-consolidated-fast-chunk-has-a.patch

From ecdd68721606d57ae52d54019e0e7b8b8729a20b Mon Sep 17 00:00:00 2001
From: Istvan Kurucsai <pistukem@gmail.com>
Date: Sat, 5 Nov 2016 13:48:32 +0100
Subject: [PATCH 4/9] malloc: Ensure that the consolidated fast chunk has a
 sane size.

    * malloc/malloc.c (malloc_consolidate): Add size check.
---
 malloc/malloc.c | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/malloc/malloc.c b/malloc/malloc.c
index 6aed08f..4836adb 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -4166,6 +4166,7 @@ static void malloc_consolidate(mstate av)
   mfastbinptr*    fb;                 /* current fastbin being consolidated */
   mfastbinptr*    maxfb;              /* last fastbin (for loop control) */
   mchunkptr       p;                  /* current chunk being consolidated */
+  unsigned int    idx;                /* fastbin index of current chunk */
   mchunkptr       nextp;              /* next chunk to consolidate */
   mchunkptr       unsorted_bin;       /* bin header */
   mchunkptr       first_unsorted;     /* chunk to link to */
@@ -4203,6 +4204,14 @@ static void malloc_consolidate(mstate av)
       p = atomic_exchange_acq (fb, NULL);
       if (p != 0) {
 	do {
+	  idx = fastbin_index (chunksize (p));
+	  if ((&fastbin (av, idx)) != fb) {
+	    malloc_printerr (check_action, 
+			     "malloc_consolidate(): invalid chunk size",
+			     chunk2mem(p), av);
+	    return;
+	  }
+
 	  check_inuse_chunk(av, p);
 	  nextp = p->fd;
 
-- 
2.7.4

0005-malloc-Harden-the-forward-and-backward-coalescing-in.patch

From 26e9d1d09b79ca818f103586d375a72b17867c8f Mon Sep 17 00:00:00 2001
From: Istvan Kurucsai <pistukem@gmail.com>
Date: Sat, 5 Nov 2016 14:06:18 +0100
Subject: [PATCH 5/9] malloc: Harden the forward and backward coalescing in
 free.

Ensure that the coalesced chunks have matching sizes in their
head and tail.

    * malloc/malloc.c (_int_free): Additional integrity checks.
---
 malloc/malloc.c | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

diff --git a/malloc/malloc.c b/malloc/malloc.c
index 4836adb..5420b72 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -3884,6 +3884,7 @@ _int_free (mstate av, mchunkptr p, int have_lock)
   INTERNAL_SIZE_T size;        /* its size */
   mfastbinptr *fb;             /* associated fastbin */
   mchunkptr nextchunk;         /* next contiguous chunk */
+  mchunkptr nextnextchunk;     /* second next contiguous chunk */
   INTERNAL_SIZE_T nextsize;    /* its size */
   int nextinuse;               /* true if nextchunk is used */
   INTERNAL_SIZE_T prevsize;    /* size of previous contiguous chunk */
@@ -4043,8 +4044,14 @@ _int_free (mstate av, mchunkptr p, int have_lock)
     /* consolidate backward */
     if (!prev_inuse(p)) {
       prevsize = prev_size (p);
-      size += prevsize;
       p = chunk_at_offset(p, -((long) prevsize));
+      if (__glibc_unlikely (prevsize != chunksize(p)))
+        {
+          errstr = "free(): invalid prev_size";
+          goto errout;
+        }
+
+      size += prevsize;
       unlink(av, p, bck, fwd);
     }
 
@@ -4054,6 +4061,13 @@ _int_free (mstate av, mchunkptr p, int have_lock)
 
       /* consolidate forward */
       if (!nextinuse) {
+	nextnextchunk = next_chunk (nextchunk);
+	if (__glibc_unlikely (prev_size (nextnextchunk) != nextsize))
+	  {
+	    errstr = "free(): invalid next size";
+	    goto errout;
+	  }
+
 	unlink(av, nextchunk, bck, fwd);
 	size += nextsize;
       } else
-- 
2.7.4

0006-malloc-Check-the-alignment-of-mmapped-chunks-before-.patch

From fd978f966e9a2e58f4c88b7d45a9cf6216ed993a Mon Sep 17 00:00:00 2001
From: Istvan Kurucsai <pistukem@gmail.com>
Date: Sun, 6 Nov 2016 17:08:57 +0100
Subject: [PATCH 6/9] malloc: Check the alignment of mmapped chunks before
 unmapping.

    * malloc/malloc.c (munmap_chunk): Verify chunk alignment.
---
 malloc/malloc.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/malloc/malloc.c b/malloc/malloc.c
index 5420b72..b319889 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -2800,6 +2800,7 @@ static void
 internal_function
 munmap_chunk (mchunkptr p)
 {
+  size_t pagesize = GLRO (dl_pagesize);
   INTERNAL_SIZE_T size = chunksize (p);
 
   assert (chunk_is_mmapped (p));
@@ -2810,13 +2811,15 @@ munmap_chunk (mchunkptr p)
     return;
 
   uintptr_t block = (uintptr_t) p - prev_size (p);
+  uintptr_t mem = (uintptr_t) chunk2mem(p);
   size_t total_size = prev_size (p) + size;
   /* Unfortunately we have to do the compilers job by hand here.  Normally
      we would test BLOCK and TOTAL-SIZE separately for compliance with the
      page size.  But gcc does not recognize the optimization possibility
      (in the moment at least) so we combine the two values into one before
      the bit test.  */
-  if (__builtin_expect (((block | total_size) & (GLRO (dl_pagesize) - 1)) != 0, 0))
+  if (__glibc_unlikely ((block | total_size) & (pagesize - 1)) != 0
+      || __glibc_unlikely (!powerof2 (mem & (pagesize - 1))))
     {
       malloc_printerr (check_action, "munmap_chunk(): invalid pointer",
                        chunk2mem (p), NULL);
-- 
2.7.4

0007-malloc-Ensure-lower-bound-on-chunk-size-in-__libc_re.patch

From 8a0e4d1c3d35e225fb3a1d2917912fc302a553af Mon Sep 17 00:00:00 2001
From: Istvan Kurucsai <pistukem@gmail.com>
Date: Sun, 6 Nov 2016 17:54:22 +0100
Subject: [PATCH 7/9] malloc: Ensure lower bound on chunk size in
 __libc_realloc.

Under some circumstances, a chunk size of SIZE_SZ could lead to an underflow
when calculating the length argument of memcpy.

   * malloc/malloc.c (__libc_realloc): Check chunk size.
---
 malloc/malloc.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/malloc/malloc.c b/malloc/malloc.c
index b319889..c404dde 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -2993,8 +2993,9 @@ __libc_realloc (void *oldmem, size_t bytes)
      accident or by "design" from some intruder.  We need to bypass
      this check for dumped fake mmap chunks from the old main arena
      because the new malloc may provide additional alignment.  */
-  if ((__builtin_expect ((uintptr_t) oldp > (uintptr_t) -oldsize, 0)
-       || __builtin_expect (misaligned_chunk (oldp), 0))
+  if ((__glibc_unlikely ((uintptr_t) oldp > (uintptr_t) -oldsize)
+       || __glibc_unlikely (misaligned_chunk (oldp))
+       || __glibc_unlikely (oldsize <= 2 * SIZE_SZ))
       && !DUMPED_MAIN_ARENA_CHUNK (oldp))
     {
       malloc_printerr (check_action, "realloc(): invalid pointer", oldmem,
-- 
2.7.4

0008-malloc-Add-more-integrity-checks-to-mremap_chunk.patch

From ab065bef3de6fcf3130a714c5f0c1c58f41c55e3 Mon Sep 17 00:00:00 2001
From: Istvan Kurucsai <pistukem@gmail.com>
Date: Sun, 6 Nov 2016 18:19:18 +0100
Subject: [PATCH 8/9] malloc: Add more integrity checks to mremap_chunk.

Similarly to the ones in munmap_chunk, ensure that the mapped region begins at
a page boundary, that the size is page-aligned and that the offset of the
chunk into its page is a power of 2.

    * malloc/malloc.c (mremap_chunk): Additional checks.
---
 malloc/malloc.c | 16 +++++++++++++---
 1 file changed, 13 insertions(+), 3 deletions(-)

diff --git a/malloc/malloc.c b/malloc/malloc.c
index c404dde..451ac91 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -2847,16 +2847,26 @@ mremap_chunk (mchunkptr p, size_t new_size)
   char *cp;
 
   assert (chunk_is_mmapped (p));
-  assert (((size + offset) & (GLRO (dl_pagesize) - 1)) == 0);
+
+  uintptr_t block = (uintptr_t) p - offset;
+  uintptr_t mem = (uintptr_t) chunk2mem(p);
+  size_t total_size = offset + size;
+  if (__glibc_unlikely ((block | total_size) & (pagesize - 1)) != 0
+      || __glibc_unlikely (!powerof2 (mem & (pagesize - 1))))
+    {
+      malloc_printerr (check_action, "mremap_chunk(): invalid pointer",
+                       chunk2mem (p), NULL);
+      return 0;
+    }
 
   /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
   new_size = ALIGN_UP (new_size + offset + SIZE_SZ, pagesize);
 
   /* No need to remap if the number of pages does not change.  */
-  if (size + offset == new_size)
+  if (total_size == new_size)
     return p;
 
-  cp = (char *) __mremap ((char *) p - offset, size + offset, new_size,
+  cp = (char *) __mremap ((char *) block, total_size, new_size,
                           MREMAP_MAYMOVE);
 
   if (cp == MAP_FAILED)
-- 
2.7.4

0009-malloc-Verify-the-integrity-of-mmapped-chunks-in-cal.patch

From 6507b75fd1b2b111b2606b0531789379cfe67982 Mon Sep 17 00:00:00 2001
From: Istvan Kurucsai <pistukem@gmail.com>
Date: Sun, 6 Nov 2016 18:38:57 +0100
Subject: [PATCH 9/9] malloc: Verify the integrity of mmapped chunks in calloc.

    * malloc/malloc.c (__libc_calloc): Check mmapped chunks.
---
 malloc/malloc.c | 13 +++++++++++++
 1 file changed, 13 insertions(+)

diff --git a/malloc/malloc.c b/malloc/malloc.c
index 451ac91..437c314 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -3274,6 +3274,19 @@ __libc_calloc (size_t n, size_t elem_size)
   /* Two optional cases in which clearing not necessary */
   if (chunk_is_mmapped (p))
     {
+      size_t pagesize = GLRO (dl_pagesize);
+      INTERNAL_SIZE_T offset = prev_size (p);
+      INTERNAL_SIZE_T size = chunksize (p);
+      uintptr_t block = (uintptr_t) p - offset;
+      size_t total_size = offset + size;
+      if (__glibc_unlikely ((block | total_size) & (pagesize - 1)) != 0
+          || __glibc_unlikely (!powerof2 ((uintptr_t) mem & (pagesize - 1))))
+        {
+          malloc_printerr (check_action, "calloc(): invalid mmapped chunk",
+                           chunk2mem (p), NULL);
+          return 0;
+        }
+
       if (__builtin_expect (perturb_byte, 0))
         return memset (mem, 0, sz);
 
-- 
2.7.4