[RFC][PATCH 6/7] malloc: Add more integrity checks to mremap_chunk.

[RFC][PATCH 6/7] malloc: Add more integrity checks to mremap_chunk.

[Istvan Kurucsai]

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 f0c54fa..503d061 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -2843,16 +2843,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

[RFC][PATCH 3/7] malloc: Ensure that the consolidated fast chunk has a sane size.

[Istvan Kurucsai]

    * 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 34310a2..873aa29 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -4165,6 +4165,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 */
@@ -4202,6 +4203,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

[RFC][PATCH 7/7] malloc: Check the alignment of mmapped chunks before unmapping.

[Istvan Kurucsai]

    * 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 503d061..f84e51a 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -2799,6 +2799,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));
@@ -2809,13 +2810,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

[RFC][PATCH 2/7] malloc: Additional checks for unsorted bin integrity I.

[Istvan Kurucsai]

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 458b57d..34310a2 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -3326,6 +3326,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 */
 
@@ -3470,12 +3471,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

[RFC][PATCH 0/7] Additonal integrity checks for the malloc implementation

[Istvan Kurucsai]

This patch set tries to improve on the current integrity checks in malloc. The goal was to eliminate known exploitation techniques with the simplest possible changes. A quick overview of the individual patches:

(1/7) An attempt at hardening the `use_top` part of malloc against corruption and pivoting of the top chunk, known as the House of Force [1]. The possibility of extending the top chunk from an mmapped arena into another remains.

(2/7) The binning code in malloc is rather attacker-friendly [2][3]. Change this by enforcing as many invariants as possible on chunks from the unsorted bin.

(3/7) `malloc_consolidate` contains no integrity checks beside the ones in `unlink`. This can be abused by an attacker in a couple of ways [4]. The patch limits the possibilities significantly.

(4/7) Fix an unsigned underflow and subsequent wild memcpy that can be triggered by a corrupted chunk size in `__libc_realloc` [5]. 

(5/7) By corrupting the `IS_MMAPPED` bit of a free chunk, an attacker can force calloc to return an uninitialized chunk [6]. The patch adds checks to the `IS_MMAPPED` path in calloc, even though the protection is not complete.

(6/7), (7/7): Additional checks around the unmapping and remapping of chunks, which are abusable in different ways [7]. Also feels somewhat incomplete but still an improvement.

The tests passed but I did no profiling. The performance impact of the mmap related parts shouldn't be noticeable, the others I'm not sure about. I already did copyright assignment.


[1]: https://github.com/shellphish/how2heap/blob/master/house_of_force.c 
[2]: https://www.contextis.com/documents/120/Glibc_Adventures-The_Forgotten_Chunks.pdf
[3]: https://github.com/shellphish/how2heap/blob/master/unsorted_bin_attack.c
[4]: http://tukan.farm/2016/09/04/fastbin-fever/ 
[5]: http://tukan.farm/2016/11/03/once-upon-a-realloc/
[6]: http://tukan.farm/2016/10/14/scraps-of-notes/
[7]: http://tukan.farm/2016/07/27/munmap-madness/

Istvan Kurucsai (7):
  malloc: Add check for top size corruption.
  malloc: Additional checks for unsorted bin integrity I.
  malloc: Ensure that the consolidated fast chunk has a sane size.
  malloc: Ensure lower bound on chunk size in __libc_realloc.
  malloc: Verify the integrity of mmapped chunks in calloc.
  malloc: Add more integrity checks to mremap_chunk.
  malloc: Check the alignment of mmapped chunks before unmapping.

 malloc/malloc.c | 92 ++++++++++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 81 insertions(+), 11 deletions(-)

-- 
2.7.4

[RFC][PATCH 4/7] malloc: Ensure lower bound on chunk size in __libc_realloc.

[Istvan Kurucsai]

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 873aa29..424c69d 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -2989,8 +2989,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

[RFC][PATCH 5/7] malloc: Verify the integrity of mmapped chunks in calloc.

[Istvan Kurucsai]

    * 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 424c69d..f0c54fa 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -3260,6 +3260,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

[RFC][PATCH 1/7] malloc: Add check for top size corruption.

[Istvan Kurucsai]

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 aa45626..458b57d 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -3801,6 +3801,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

Re: [RFC][PATCH 0/7] Additonal integrity checks for the malloc implementation

[DJ Delorie]

These look good to me, assuming they've passed "make check".  Could use
test cases for the hackery we're trying to prevent, but that shouldn't
stop the patches from going in.

After you have consensus, will you need someone to check these in for
you?

Re: [RFC][PATCH 0/7] Additonal integrity checks for the malloc implementation

[Istvan Kurucsai]

They passed make check, I will look into adding tests next week. Yes,
I would need someone to check them in.

Thanks.

On Thu, Jun 1, 2017 at 10:19 PM, DJ Delorie <dj@redhat.com> wrote:
>
> These look good to me, assuming they've passed "make check".  Could use
> test cases for the hackery we're trying to prevent, but that shouldn't
> stop the patches from going in.
>
> After you have consensus, will you need someone to check these in for
> you?

Re: [RFC][PATCH 0/7] Additonal integrity checks for the malloc implementation

[Istvan Kurucsai]

Quick update: I didn't find the time to do it this week and will be
leaving for vacation, so the soonest I can look into adding tests will
be two weeks from now.

On Sat, Jun 3, 2017 at 10:43 AM, Istvan Kurucsai <pistukem@gmail.com> wrote:
> They passed make check, I will look into adding tests next week. Yes,
> I would need someone to check them in.
>
> Thanks.
>
> On Thu, Jun 1, 2017 at 10:19 PM, DJ Delorie <dj@redhat.com> wrote:
>>
>> These look good to me, assuming they've passed "make check".  Could use
>> test cases for the hackery we're trying to prevent, but that shouldn't
>> stop the patches from going in.
>>
>> After you have consensus, will you need someone to check these in for
>> you?

Re: [RFC][PATCH 0/7] Additonal integrity checks for the malloc implementation

[Istvan Kurucsai]

The recent malloc hardening patches sent in just reminded me of these
which I completely forgot about. Should I resubmit them actualized for
the current state of the malloc code?

On Thu, Jun 8, 2017 at 9:20 PM, Istvan Kurucsai <pistukem@gmail.com> wrote:
> Quick update: I didn't find the time to do it this week and will be
> leaving for vacation, so the soonest I can look into adding tests will
> be two weeks from now.
>
> On Sat, Jun 3, 2017 at 10:43 AM, Istvan Kurucsai <pistukem@gmail.com> wrote:
>> They passed make check, I will look into adding tests next week. Yes,
>> I would need someone to check them in.
>>
>> Thanks.
>>
>> On Thu, Jun 1, 2017 at 10:19 PM, DJ Delorie <dj@redhat.com> wrote:
>>>
>>> These look good to me, assuming they've passed "make check".  Could use
>>> test cases for the hackery we're trying to prevent, but that shouldn't
>>> stop the patches from going in.
>>>
>>> After you have consensus, will you need someone to check these in for
>>> you?

Re: [RFC][PATCH 0/7] Additonal integrity checks for the malloc implementation

[DJ Delorie]

Istvan Kurucsai <pistukem@gmail.com> writes:
> The recent malloc hardening patches sent in just reminded me of these
> which I completely forgot about. Should I resubmit them actualized for
> the current state of the malloc code?

If they need tweaking, please resubmit.  Else just ping the original,
linking the copy in the archives for reference.

Thanks!