[PATCH] malloc: Improve tcache double-free detection

[Wilco Dijkstra]

Hi Ben,

So I don't believe this patch actually improves "double free detection" - there is
only one tcache_key per process, ie. a double free in a different thread will simply
write the same key again to the same location. The 2 existing checks on the
pointer and key should be able to detect this. So I think this may only increase
protection against corruption (like use after free) for cases the pointer swizzling is
not able to detect this.

Also I measured the performance effect of your patches on Neoverse V2.
The results are as follows for taking best of 3 runs:

bench-malloc-thread 1: 4.1% slowdown with latest patch, 0% with previous 2
bench-malloc-thread 32:  7.1% slowdown with latest patch, 0% with previous 2

bench-malloc-simple (ST case): 6% slowdown with all 3 patches, 3% with latest
bench-malloc-simple (MT case): 3% slowdown with all 3 patches, 0.5% with latest
bench-malloc-simple (thread arena): 2.5% slowdown with all 3 patches, 0% with latest
average slowdown for all cases: 3.9% with all 3 patches, 1.2% with latest

> The potential cost in this patch comes from reading e->key in
> tcache_get_n. Given that we haven't read from e prior to this point,
> this is moderately likely to be a cache miss. However, the very next
> thing that tcache_get_n does is read from e->next, which is located 8
> bytes before e->key. Without the patch, *this* was moderately likely
> to be a cache miss, but is now almost certain to be a cache hit. In
> other words, the cost of this patch should be one extra cache hit, and
> one extra unlikely branch. So, not much :)

If you look at the profile, more than half of the code in malloc/free critical path
is doing absolutely nothing - it's checking whether tcache or malloc are initialized
or doing security checks. And yes, all this adds up to significant overheads.

This "simple" change adds 8 instructions to the critical path! 3 are used for the
extra global load of tcache_key, and because it needs an extra callee-save, there
are also 2 extra load/store instructions, plus 3 more for the 2nd load, compare
and branch. That's a LOT of extra instructions to execute in the critical malloc path
that was 42 instructions (now 50), even on a very wide core like Neoverse V2
that does 8 instructions per cycle...

So overall the cost doesn't seem worth the potential extra security...

>> Also I am wondering whether the pointer swizzling will already detect most of these cases already?
>
> To defeat pointer swizzling, an attacker needs only to leak a heap
> address.

I don't believe pointer swizzling can be so easily defeated - you need to not just
leak a pointer, you need the ability to overwrite a pointer with one that is swizzled
in a way that is useful to the attacker. When one is able to use gadgets that swizzle
pointers you have already lost...

>> In the future, I believe reserving a common field in the header for all block types would enable more general detection of double free and buffer overwrites.
>
> Sounds very reasonable to me, as long as you're okay with adding this
> extra memory overhead to every allocation.

There are at least 32 unused bits in the header of each block on 64-bit targets,
so you could store a key in there to detect buffer overflows both on allocated
and freed blocks. Whether it can be done cheaply is another question of course.

Cheers,
Wilco