Potential security issues in mimalloc-secure

[insuyun]

Hi! @ironore15 and I are working for research on secure allocators.

During research, we have found several potential security issues in mimalloc-secure mode.
We want to get your feedback regarding these issue.s

• Metadata leakage

We found that metadata can be leaked even in secure mode.

Here is the proof of concept code.

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

int main(void) {
    void *p1 = malloc(32);  // prevent calling mi_segment_free
    void *p2 = malloc(64);  // page with xblock_size = 64
    free(p2);  // calling _mi_page_retire
    void *p3 = malloc(-8);  // trigger mi_heap_collect with MI_FORCE
    void *p4 = malloc(128);  // alloc page with same page_area
    fprintf(stderr, "%p\n", ((void **)p4)[8]);
}

If we run the code in Ubuntu 18.04, it shows like this.

$ LD_PRELOAD=./libmimalloc-secure.so ./test
0x41cb4a160092279d

As you can see, ((void **)p4)[8] contains encoded metadata of mimalloc heap.
We believe that it breaks your attempt to remove internal data in secure mode.

It happens because _mi_page_free doesn't remove metadata of free_list. In the above PoC, when we call malloc(-8), which is huge page, mimalloc calls _mi_page_free to reclaim used pages. A page with xblock_size=64 from p2 is also one of reclaimed pages. Then, the next malloc(128) will reuse the previous page, which contains an encoded free_list.

I think one way to fix this issue is that we can zero-out page in secure mode.

• Heap spray

In mimalloc-secure mode, an attacker can allocate a fixed memory address and bypass ASLR.
Here is PoC code.

#include <stdio.h>
#include <stdlib.h>
int main(void) {
    void *p = malloc(0x40000000000);
    *(int *)0x7FFFFFFF000 = 0;
    return 0;
}

This always exit successfully without segmentation fault.

It happens because eager commit option and mmap with aligned hint address. When segment is initially allocated, it calls _mi_mem_alloc_aligned. On UNIX system, it internally calls mi_unix_mmapx with addr is NULL, and mi_os_get_aligned_hint to get address for segment. In the following the code, (1 << 42) ~ (1 << 43) are only valid segment address. Since Eager commit is enabled default, very large allocation, e.g., malloc(1 << 42), will always alloc memory address between 0x7FFFFFFF000 ~ 0x80000000000.

We believe that one easy way to mitigate this is to disable eager commit in secure mode.
But I am not sure that it fits with mimalloc's design descision.

Best,
Insu Yun

[daanx]

Hi Insu & @ironore15 -- thank you for finding these issues! quite ingenious :-)
(as an aside, maybe research things like this work better as an email discussion at first? the issue even reads like an email to me :-) )

1. Yes, that is a metadata leak. Generally not good except this is the free-list metadata which is already considered compromised by mimalloc since it is interspersed among regular user allocated blocks. That is why mimalloc encodes the free list using the secret keys from the actual page metadata (which resides outside user data with a guard page in-between). Moreover, I am quite sure that when you get a fresh page (the one that was just freed in your example) the keys are updated and thus the old linked-list metadata has no meaning anymore.

   So, we (a) already consider linked list data compromised, and (b) the data from the POC is stale. Still, mimalloc tries to not make it easy to get to it, and in the POC it is very easy :-) I will first verify if the data is always stale (and if not, make sure we refresh the
   keys in all cases) -- that seems to be enough though and cheaper than zeroing.

2. Ouch, also looks not good. However, it took me a while to understand what is going on and I am not sure how bad/real this is? As I understand it: (a) mimalloc generates a random start address between 4TiB and 8Tib (4<<40 and 8<<40) that is aligned to the segment size (in 1.7.0, 4 MiB (4<<20)). then (b) the POC allocates 4TiB so the final segment size memory before 8TiB will always be part of what is allocated, and the area between (8TiB - 4MiB) up to 8TiB points to valid memory. This allows the POC to allocate memory at a fixed address.

   I do not yet understand what eager commit has to do with this -- I think this always happens?

   Also, I am not sure how bad this is as the returned block address is still random; we can only predict it will cover a particular range of addresses. Usually, ASLR prevents an attacker from knowing an address that was allocated by the system (say, virtual method tables) but in this case the attacker only knows that some part of a block that was allocated by the attacker themselves will be at a specific address.

   and I don't think we can prevent this problem in general: the limit of virtual addresses in Linux now is 128TiB so if one allocates a block of about that size there is no way to return a randomized address. If one allocates a block of 64TiB than even randomizing the address over 64TiB would still leave some predictable memory just before 64TiB. Perhaps we need to limit the max allocation size? Or I guess start increasing the random address space beyond the first 4-8TiB for larger allocations. I need to think a bit more about this.

Best, Daan

[insuyun]

Hi, Dann.

Thanks to your quick response.

1. Good. Let us know after you verify.

2. Sorry, I think its our fault.
   I also agree that this issue is not relevant to eager commit.
   It's because MAP_NORESERVE is always turned on in mimalloc.
   I think one way to prevent this is that just turning off MAP_NORESERVE to disable overcommit.

I think this issue can have several potential security problems.
First, of all, using the allocation success as an oracle, an attacker can break ASLR.
For example, allocate a very large chunk and see if it is allocated.
Using this we can conclude where the hole exist, which gives us address information.
Here is more detailed explantation.

More generally, I believe that it weakens ASLR.
For example, this issue can make attack feasible even
though the exploit requires an address value,
which is prohibited in a normal ASLR setting.

Best,
Insu Yun

[bhardwajs]

@insuyun @daanx - It might be best to take this offline through MSRC. Here is an example process for MSVC STL: https://github.com/microsoft/STL/blob/main/SECURITY.md

[daanx]

Thanks Insu -- and thanks for the link, looks like an interesting paper. I have been wanting to do better ASLR anyways -- I feel just using a random base address may be too weak and it would be better to randomly spread out even more. Fixing this issue may be a good opportunity to revise this.

[insuyun]

Thank you @bhardwajs and Dann.
Let me know after your discussion.
Best,
Insu Yun

[daanx]

Thanks for mentioning MSRC and providing a link Sumit. That is the proper channel to report severe issues (although it might still be better to contact me first over email).

I think in this particular case it seems ok to keep discussing here though as the current issue would be not easy to exploit. Also, often with security issues for allocators it is debatable whether the behavior is ok or not (see here for example).

[insuyun]

Oh. I thought that you have an internal line for communicating with msrc. As Daan said, its not a big issue that msrc officially handles.

I totally agree with Daan that it is often debatable which behavior is fine in a secure allocator. That is one of our motivations for this research.

We have found several interesting behaviors in many allocators. But we selectively reported them if we believe that this can be really problematic
(e.g., SamAinsworth/MarkUs-sp2020#3, bwickman97/ffmalloc#1).

For example, we decided to report first issue(metadata) because we found your attempts to limit metadata leakage. So we conclude that it seems to violate your expectation.

We also reported the second one(spray) because it is an unique issue in mimalloc, which cannot be observable in other secure allocators that we tested.

[daanx]

I pushed an initial fix for the second issue -- simply not using hinting for allocations over 1GiB to ensure enough randomness (and falling back to the OS for alignment for larger than 1GiB allocations). Still investigating the first issue but it looks actually ok.
(also, I changed the initial hint area to start between 2 and 6TiB to be better on pre-windows 8)