Improper handling for double free in large chunks

[insuyun]

Hi. Emery.
This is the issue for Dieharder that we discussed.
I am making this issue to keep track it for further discussion.
I also attached the PoC that you further minimized.

Thank you.

#include <iostream>
using namespace std;

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#ifndef __APPLE__
#include <malloc.h>
#endif

#include <assert.h>

void* p[256];
uintptr_t buf[256];

int main() {
#ifndef __APPLE__
  p[1] = malloc((65536 + 16) / 2);
#endif
  p[2] = malloc(65536 + 16);
  free(p[2]);
  p[4] = malloc(0x30000);
  //////  free(p[1]);
  // Check we don't free a legitimate memory
  assert(p[2] != p[4] && p[2] != p[4]);  /// Emery: this assertion is redundant -- you only need one clause.
  // [VULN] Double free
  free(p[2]);
  ///p[5] = malloc(65536);
  p[6] = malloc(65536 + 16);
  free(p[4]);
  p[7] = malloc(65536 + 16);
  // [BUG] Found overlap
  // p[7]=0x7f52347c4000 (size=65568), p[6]=0x7f52347c4000 (size=65552)
  cout << p[6] << ", " << p[7] << endl;
  assert(p[6] == p[7]);
}

[emeryberger]

As far as I can tell, this is not a bug in DieHard. This code confuses corruption due to double-frees with aliasing when DieHard (legally and correctly) returns the same memory address after it has been freed. DieHard correctly ignores calls to free already-freed large memory: see https://github.com/emeryberger/DieHard/blob/master/src/include/largeheap.h#L29.

DieHard allocates large objects via mmap. Your first malloc call invokes mmap under the covers. The subsequent free call then invokes munmap, releasing this memory back to the OS. The next malloc call invokes mmap, which gets the original memory back from the OS plus enough to hold the remainder. Contrary to the assertion, it is legal for p[4] to have memory starting at the same address as p[2] since p[2]'s memory has been discarded. The rest of the code, AFAICT, exhibits exactly the same issue. The subsequent call to free(p[4]), for example, is just aliasing p[6], so it's as if you called free(p[6]), and so it is legal and correct for p[7] to have the same memory address.

[insuyun]

Hi, Emery. As so far as I believe, a secure allocator should properly maintain the state of freed pointer (aka dangling pointer). In the theoretical case, we can think an ideal allocator that has a hash table that maps a pointer and its state (e.g., allocated or free). Every malloc() call, we register an allocated state in the hash table, and every free() call we mark free in the state. In this model, this ideal allocator detect double free using a recorded state, and the secure allocator should be indistinguishable from this ideal allocator (at least for double free). So if p[2] and p[4] are same, this would be totally acceptable because the pointer triggering double free is perfectly valid. i.e., free(p[2]) == free(p[4] <- this is valid). But, as you can see in the assertion, p[2] and p[4] are different pointers, which mean that freeing p[2] should be prevented because it is a dangling pointer according to our previous model. I didn't look at the detail of this implementation, but it looks like the hash table (https://github.com/emeryberger/DieHard/blob/master/src/include/largeheap.h#L29) seems doing exactly same thing that I described in the ideal allocator, but I don't know why this double free is allowed. I need to take a look the code more carefully.

[emeryberger]

By your logic, in a secure allocator, a freed object would never be recycled? I of course disagree. The only issue here is that, unlike for small objects in DieHard/er, large objects are immediately reused (depending on the OS), where as small objects are probabilistically highly unlikely to be reused immediately. But reuse is inevitable and required in a practical memory allocator, else it would leak memory.

[insuyun]

Surely not. Recycling is required. So this is totally fine

ptr1 = malloc(sz1); // allocated[ptr1] = true
free(ptr1); // allocated[ptr1] = false
ptr2 = malloc(sz2); // allocated[ptr2] = true
assert(ptr1 == ptr2); // <- this implies that allocated[ptr1] = true
free(ptr1); <- Even though this is double free, ptr1 is alias of ptr2, which is a valid pointer

But the issue here is that

ptr1 = malloc(sz1); // allocated[ptr1] = true
free(ptr1); // allocated[ptr1] = false
ptr2 = malloc(sz2); // allocated[ptr2] = true
assert(ptr1 != ptr2);
free(ptr1);  // allocated[ptr1] = false <- needs to be prevented. 

[insuyun]

So I think it is better to be forceful (i.e., abort if get() returns false) to prevent this kind of case.
(I am not sure it is fine to do like this though).

[insuyun]

FYI, microsoft/mimalloc#161 (comment)

[emeryberger]

There is no reason whatsoever for ptr1 to not equal ptr2. The only way that assertion is true in general (for objects in the same size class) is if the memory allocator never reclaims memory.

[insuyun]

If ptr1 and ptr2 belong to the same size class, ptr1 and ptr2 will be same if they are reclaimed. But in this PoC (#12 (comment)), ptr1 and ptr2 are different because we claim different sizes. I think you have tested this.

According to our previous discussion, you said

"OK, I had a chance to look at this. Now I see what is going on. What is happening is pretty straightforward. Large objects (>64K) are just allocated and freed via mmap (DieHard(er) effectively is doing nothing but acting as a wrapper to mmap/munmap, except for tracking sizes). Your program is unmapping a large chunk, and it's getting recycled by the OS. I could indeed track freed chunks to make sure this doesn't happen twice, probably just by overloading how I manage sizes. I will take a look at this."

So I thought that you also agree with this problem.

[emeryberger]

First, with respect to my previous statement, I was wrong. DieHard/er does not in fact try to unmap things twice, and per GitHub blame, that logic has been in place for a long time (at least 8 years).

Second, I hope you will agree that:

• a memory allocator that reclaims memory must eventually reuse addresses
• it is legal for an allocator to merge freed memory of different sizes
• the internal use of size classes is a detail that is generally unknown to the user; so it's legal for two objects of arbitrary sizes to "be in the same size class"

Given all these things, it's not at all clear what you behavior you consider to be a bug, per se.

[insuyun]

I totally agree with your second part. But, the current issue is not related to reclaiming, but the validity (and its checking) of a pointer to be freed. A secure allocator (or other allocator) need to prevent use of a dangling pointer (i.e., double free). For example, ptmalloc2, which follows your second part, still can detect double free in the PoC. If I run the PoC with ptmalloc2, it will give me an error double free or corruption (top). Similarly in Guarder (./bibopheap.hh:1049: Double free or invalid free problem found on object 0x6fcfef56b000). I believe your second requirement is not necessary condition to allow this double free.

[insuyun]

I think you agree with that a secure allocator should not allow to free an invalid object. Then what is the invalid object? In my understanding, the invalid object is the object that is not returned by the allocator or an object that is freed. It is not dependent whether its backed memory is allocated (or reclaimed) because we agree that freeing a middle pointer e.g. free(malloc(16)+8) should not be allowed. In this concept, I think the double freed object in the PoC should be considered as invalid one and needs to be checked.

[emeryberger]

An invalid object is one that was never returned by malloc. Where is the invalid object in this discussion?

[emeryberger]

An object that has been freed is not an invalid object, as long as it was generated by malloc.

[emeryberger]

I also do not necessarily agree that malloc(16)+8 should be rejected; it's a policy decision as to whether frees when applied to interior pointers should be ignored.

[emeryberger]

IIRC DieHard/er treats such calls to free as calls to the object itself (ignoring the offset), silently converting invalid pointers to valid ones.

[insuyun]

An invalid object is one that was never returned by malloc. Where is the invalid object in this discussion?

I also think that an object, which is freed, should be treated as invalid. Then, do you think freed object should be also freeable? I guess not. Here what I mean a valid or an invalid object is related to free(). The valid object means that it is fine to be freed, and the invalid one is not.

I also do not necessarily agree that malloc(16)+8 should be rejected; it's a policy decision as to whether frees when applied to interior pointers should be ignored.

Yes. I think ignoring seems to be fine, too.

I found that DieHarder's decision for double free is quite generous. But I still believe this is problematic because the PoC breaks an important invariant in the allocator for security --- allocated (or live) memory should not be overlapped.

BTW, thank you for your time.

[emeryberger]

That invariant is decidedly not being broken (unless something is seriously wrong). Allocated memory definitely does not overlap: that's a key correctness requirement of any allocator, secure or otherwise.

[insuyun]

Actually, in the PoC, p[6] is not p[4], which means that p[6] is live. But, the next allocated memory p[7] is same with p[6], which mean they are overlapped.

... 
  p[6] = malloc(65536 + 16);
  assert(p[6] != p[4]); <- added
  free(p[4]);
  p[7] = malloc(65536 + 16);
  assert(p[6] == p[7]);
...

[emeryberger]

No, DieHard/er is not returning overlapped memory.

Yes, p[4] is in fact an alias to p[6]. All of the array entries end up aliasing each other.

To make clear what is happening, I instrumented DieHard to print out the addresses of all allocated "large" memory during execution of your PoC code. Remember that under the covers, all of these malloc and free calls are being served by mmap and munmap. The number 4396056576 is an address.

  malloc(65552) = 4396056576   /*   p[2] = malloc(65536 + 16); */
  free(4396056576)             /*   free(p[2]); */
  malloc(196608) = 4396056576  /*   p[4] = malloc(0x30000); */
  free(4396056576)             /*   free(p[2]); */
  malloc(65552) = 4396056576   /*   p[6] = malloc(65536 + 16); */
  free(4396056576)             /*   free(p[4]); */
  malloc(65552) = 4396056576   /*   p[7] = malloc(65536 + 16); */

I hope this helps. All that is happening is that a chunk of memory starting at the same address is being repeatedly allocated and freed.

[insuyun]

No. I modified the PoC for printing out allocated memory.

#ifndef __linux__
#error "Only for Linux"
#endif

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>

void* p[256];
uintptr_t buf[256];

int main() {
  p[1] = malloc((65536 + 16) / 2);
  fprintf(stderr, "p[1] = %p\n", p[1]);
  p[2] = malloc(65536 + 16);
  fprintf(stderr, "p[2] = %p\n", p[2]);
  free(p[2]);
  p[4] = malloc(0x30000);
  fprintf(stderr, "p[4] = %p\n", p[4]);
  assert(p[2] != p[4]);
  free(p[2]);
  p[6] = malloc(65536 + 16);
  fprintf(stderr, "p[6] = %p\n", p[6]);
  assert(p[6] != p[4]);
  free(p[4]);
  p[7] = malloc(65536 + 16);
  fprintf(stderr, "p[7] = %p\n", p[7]);
  assert(p[6] == p[7]);
}

This is how I got the result.

$ cat /etc/issue
Ubuntu 18.04 LTS \n \lx86_64 GNU/Linux
$ gcc -o poc poc.c
$ LD_PRELOAD=$(pwd)/DieHard/src/dieharder.so ./poc
p[1] = 0x7ff1f0b09000
p[2] = 0x7ff1f0aee000
p[4] = 0x7ff1f0acf000
p[6] = 0x7ff1f0aee000
p[7] = 0x7ff1f0aee000

As you can see, p[6] is not alias of p[4] in Ubuntu 18.04.
I think you have told me that your testing environment is Mac OS.
Let me port our tool to check whether we can find the similar issue in Mac OS.

[insuyun]

#ifndef __APPLE__
#error "Only for Mac OS"
#endif

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <malloc/malloc.h>

void* p[256];
uintptr_t buf[256];

int main() {
  p[0] = malloc(1333062);
  fprintf(stderr, "p[0]: %p - %p\n", p[0], p[0] + 1333062);

  p[1] = malloc(1333099);
  fprintf(stderr, "p[1]: %p - %p\n", p[1], p[1] + 1333099);

  free(p[0]);
  fprintf(stderr, "free(p[0]);\n");

  p[2] = malloc(3999254);
  fprintf(stderr, "p[2]: %p - %p\n", p[2], p[2] + 3999254);

  free(p[2]);
  fprintf(stderr, "free(p[2]);\n");

  free(p[1]);
  fprintf(stderr, "free(p[1]);\n");

  p[3] = malloc(3999248);
  fprintf(stderr, "p[3]: %p - %p\n", p[3], p[3] + 3999248);

  free(p[1]);
  fprintf(stderr, "free(p[1]); // double free\n");

  assert(p[3] != p[1]);
  fprintf(stderr, "// NOTE: p[3] (%p) != p[1] (%p)\n", p[3], p[1]);

  p[4] = malloc(1333072);
  fprintf(stderr, "p[4]: %p - %p\n", p[4], p[4] + 1333072);

  assert((p[3] <= p[4] && p[4] < p[3] + 3999248));
  fprintf(stderr, "// OVERLAP: p[3] (%p) <= p[4] (%p) < p[3] + its size (%p)\n", p[3], p[4], p[3] + 3999248);
}

This is PoC found for Mac OS. It can be reproduced as follows:

$ gcc -o poc poc.c
$ DYLD_INSERT_LIBRARIES=$(pwd)/DieHard/src/dieharder.dylib ./poc
p[0]: 0x10d7cd000 - 0x10d912746
p[1]: 0x10d913000 - 0x10da5876b
free(p[0]);
p[2]: 0x10da59000 - 0x10de29616
free(p[2]);
free(p[1]);
p[3]: 0x10d7cd000 - 0x10db9d610
free(p[1]); // double free
// NOTE: p[3] (0x10d7cd000) != p[1] (0x10d913000)
p[4]: 0x10d913000 - 0x10da58750
// OVERLAP: p[3] (0x10d7cd000) <= p[4] (0x10d913000) < p[3] + its size (0x10db9d610)

As you can see, p[1] is not overlapped with p[3], which is live memory. Thus, p[3] should be live and will be overlapped with newly allocated memory p[4].

[emeryberger]

I will look at this later but to be clear, fprintf allocates memory, so that's a potential confound. There's also ASLR at play. In any event, let's back up: is mmap a safe allocator or not? That's all that DieHard/er is using for such objects. If you want to claim that mmap is unsafe, fine, but realize that's what you are claiming.

[insuyun]

Ok. Let me know after you look this issue. As so far as I know, fprintf will allocate memory if it enables buffering, which is not the case for stderr. I believe mmap is an unsafe allocator as everybody believes. So I think that it's secure allocator's job to properly use mmap. If an alloator redirects its allocation to the unsafe allocator, can it be secure? I don't think so. Thank you again for your time.

[insuyun]

FYI, this is poc annoated with its syscall. I think the problem is that DieHarder calls munmap twice for p[1], which is 0x10A84C000 in this execution.

  // mmap(0x0, 0x146000, 0x7, 0x1002, 0xFFFFFFFFFFFFFFFF, 0x0)		 = 0x10A706000 0
  p[0] = malloc(1333062);
  // mmap(0x0, 0x146000, 0x7, 0x1002, 0xFFFFFFFFFFFFFFFF, 0x0)		 = 0x10A84C000 0
  p[1] = malloc(1333099);
  // munmap(0x10A706000, 0x146000)		 = 0 0
  free(p[0]);
  // mmap(0x0, 0x3D1000, 0x7, 0x1002, 0xFFFFFFFFFFFFFFFF, 0x0)		 = 0x10A992000 0
  p[2] = malloc(3999254);
  // munmap(0x10A992000, 0x3D1000)		 = 0 0
  free(p[2]);
  // munmap(0x10A84C000, 0x146000)		 = 0 0
  free(p[1]);
  // mmap(0x0, 0x3D1000, 0x7, 0x1002, 0xFFFFFFFFFFFFFFFF, 0x0)		 = 0x10A706000 0
  p[3] = malloc(3999248);
  // munmap(0x10A84C000, 0x28B000)		 = 0 0
  free(p[1]);
  assert(p[3] != p[1]);
  // mmap(0x0, 0x146000, 0x7, 0x1002, 0xFFFFFFFFFFFFFFFF, 0x0)		 = 0x10A84C000 0
  p[4] = malloc(1333072);
  assert((p[3] <= p[4] && p[4] < p[3] + 3999248));

[tsgates]

Emery,

  // munmap(0x10A84C000, 0x28B000)		 = 0 0
  free(p[1]);

  // mmap(0x0, 0x146000, 0x7, 0x1002, 0xFFFFFFFFFFFFFFFF, 0x0)		 = 0x10A84C000 0
  p[4] = malloc(1333072);

The secure behavior of an allocator is to recognize the state of p[1] (i.e., already freed) and prevent it from being munmap(). What we found here is that, the underlying memory layout of alloced/freed chunks due to this particular sequence of alloc/free calls used in this PoC has the security implication. It means that the following malloc() returns an overlapping chunk, which an attacker can leverage to craft the original memory region.

This is indeed a standard, yet easier-kind exploitation technique (i.e., much lesser complex than typical heap exploitation techniques in ptmalloc). In real-world applications, say web browsers, this behavior can be easily leveraged to achieve a full RCE. Note that, we are also planning to create a CTF problem based on this technique to exploit a DieHarder-protected program.

[insuyun]

Hi, emery.

Sorry for very very late investigation of this problem.
I was busy with finishing my phd.
I recently start another project about heap allocators and re-check this issue.

Here is the root cause of this issue.
Current diehard's large heap marks that all pointers at page-size intervals are valid (source).
This allows to free an invalid memory (e.g., double free in the previous poc) as a valid one,
and makes it to overlap with existing one (this is behavior of mmap).

Here is more simpler and intuitive poc to demonstrate this issue.

#ifndef __linux__
#error "Only for Linux"
#endif

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <sys/mman.h>

int main() {
  char* p1 = malloc(65536 + 0x1000);
  char* p2 = p1 + 0x1000;
  free(p2); // This is considered as a valid pointer!
  char* p3 = malloc(65536);
  assert(p2 == p3);
}

According to the POSIX spec, freeing an invalid pointer is actually undefined behavior. So as an allocator, it is also ok to work like this. However, in general, modern allocators (e.g., scudo, freeguard, ..) prohibited this. Similarly, in dieharder, small allocations do not have such behaviors. May I ask you why you choose this kind of design for large allocation?

Best,
Insu Yun