Question about secure mode and relationship to DieHarder

[insuyun]

Hi, all.
I am currently evaluating my tool, ArcHeap: https://arxiv.org/pdf/1903.00503.pdf

I saw mimalloc has secure mode, so I am testing it with my tool.
And it seems it has the similar bug with DieHarder (https://github.com/emeryberger/DieHard).

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

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

int main() {
  p[0] = malloc(622616);
  p[1] = malloc(655362);
  p[2] = malloc(786432);
  free(p[2]);
  // [VULN] Double free
  free(p[2]);
  p[3] = malloc(786456);
  // [BUG] Found overlap
  // p[3]=0x429b2ea2000 (size=917504), p[1]=0x429b2e42000 (size=786432)
  fprintf(stderr, "p1: %p-%p, p2: %p-%p\n", p[3], p[3] + 917504, p[1], p[1] + 786432);
}
// The number of actions: 16
// [INFO] EVENT_OVERLAP is detected

This PoC always returns overlapping chunk in my Linux machine.
Does it based on https://github.com/emeryberger/DieHard, so it has the same bug?
Or is it just collision?

[daanx]

Hi Insu -- I skimmed the paper and it looks like very interesting work!

mimalloc is not based on DieHard(er) so there is no direct relation there. Also, mimalloc secure mode has limited mitigations at present. It:

• places guard pages around each mimalloc page (usually 64k) to prevent overflowing into other mimalloc pages or mimalloc metadata
• encodes the free list to prevent overwriting with known values
• randomizes allocations (so the next allocation cannot be predicted)

These mitigations all help against buffer overflow exploits. However, they do not yet mitigate against other application bugs like double free :-( I would like to harden the secure mode further though and add further checks like invalid pointer free's and detecting free list corruption (both easy to add). Double free detection is harder though to do efficiently.

Anyway, if you are interested I would like to learn more how we can further strengthen the secure mode of mimalloc; Feel free to contact me by email to discuss it more.

[daanx]

To follow up, in the latest dev version I included a stronger secure mode enabled when defining MI_SECURE=4 (normally it is 3). This adds double free check, corrupted free list check, and invalid pointer free checks. The performance is more impacted but seems not too bad as all checks use an initial "quick" check before using the more expensive method; Seems about 5% to 25% slower on most benchmarks -- but more testing is needed :-)

I hope this will be interesting to check with your new tool.

Ps: to enable the more secure mode, define MI_SECURE=4 in the mimalloc-types.h header, or edit the CMakeLists.txt to use list(APPEND mi_defines MI_SECURE=4) (on line 79) and build in the out/secure folder (which sets -DMI_SECURE=ON for cmake))

[insuyun]

Thanks you for your quick reply.
It is very interesting that mimalloc have similar behavior with DieHarder
even though it is not based on DieHarder.

Let me try the more secure version and let you know.
Thank you!

[insuyun]

If I compiled correctly,

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

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

int main() {
  // [INFO] Command buffer: 0x327b2000
  // [INFO] Input size: 182
  p[0] = malloc(712352);
  p[1] = malloc(786432);
  free(p[0]);
  // [VULN] Double free
  free(p[0]);
  p[2] = malloc(786440);
  p[3] = malloc(917504);
  p[4] = malloc(786440);
  // [BUG] Found overlap
  // p[4]=0x433f1402000 (size=917504), p[1]=0x433f14c2000 (size=786432)
  fprintf(stderr, "p1: %p-%p, p2: %p-%p\n", p[4], p[4] + 917504, p[1], p[1] + 786432);
}
// The number of actions: 26
// [INFO] EVENT_OVERLAP is detected

This gives me very reliable chunk overlaps even with MI_SECURE=4

[daanx]

Ouch -- just pushed a fix (the wrong block was tested for free list membership before).
Let me know how it goes.

I think the current method should catch the vast majority of double-free bugs (with MI_SECURE=4), but it does not always work:

1. if the whole mimalloc page/segment is freed and reused again it may not detect the double-free of blocks in there. (try a test where you allocate a some objects, and then free everything, allocate again, and then do a double free on an early allocation -- Mmm, maybe the page needs to be reused though with a different block size for the detection to fail -- maybe not so easy to set this up).
2. huge (>64MiB) and large objects (>1MiB) double frees are not always detected (as they reduce to situation 1)
3. double frees from different threads are not checked (as yet, but can be done efficiently too I think).

It feels like situation 1 is generally unavoidable if one wants a reasonable efficient implementation that re-uses memory well???

[insuyun]

Thanks. Let me check the latest version.

We also think the situation 1 is unavoidable.
Therefore, ArcHeap excludes the case
when a victim object for double free is already re-claimed.

For example, we don't consider the case like

void* a = malloc(0x100);
free(a);
void* b = malloc(0x100);
assert(a == b); // reclaimed
free(a); 
// although it is double free,
// this is a valid object for an allocator
// so there is no way to detect this as a  freed object.
// ArcHeap excludes such case

[insuyun]

Ok. I tested it. As you mentioned, ArcHeap can find some cases that overlapping chunks can happen, but it is not reliable as before, which was nearly 100%.
If you are fine, I think it would be fine to close this issue.

[daanx]

Well -- I hope you will still email me as I am quite interested to learn more on how to make mimalloc more secure and perhpaps we can work together on more advanced mitigation; it would be great to protect in-depth against any future as yet unknown attack modes (like the guard pages do). Best, Daan

[insuyun]

Sure. I think it would be nice to eliminate this kind of case completely. We also applied ArcHeap to other allocators and found many exploit primitives, but failed for Scudo, Guader, and FreeGaurd.

Maybe it would be interesting to see how they handle such cases and we can do the similar thing with mimalloc without losing too much performance.

Then, I think it would be better to leave this issue and close later.

[insuyun]

FYI, we open-sourced our tool (https://github.com/sslab-gatech/ArcHeap).