[PATCH] malloc: Improve tcache double-free detection

[Ben Kallus]

Hi,

> As a general comment, do have performance results of your recent malloc
changes? Do you use a methodology to decide the performance vs security
tradeoffs?

> Malloc is performance critical, and these changes affect key critical paths, so
we have to be sure the extra checks are either very low cost or bring essential
security gains.

In all of my patches, I'm shooting for very low cost. If there's a
performance regression, I've done something wrong.

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 :)

This is corroborated by the results of running the malloc-simple and
malloc-thread benchtests, which show no differences as a result of
applying this patch on my AMD64 desktop. I'd be happy to test on other
platforms if you'd like.

> Note this only works if the tcache is never full - it's tiny, and when you overflow to fastbin the multiple free detection fails.

True. It would be wise to use a key field in the fastbin as well;
there's enough unused space in the struct for it! I'd be happy to
write that up and send that patch along once there's a verdict on this
patch.

> 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. To defeat this patch, an attacker needs to be able to leak
the tcache key (i.e., read from a tcache chunk after it's been freed).
With both mitigations, an attacker needs both pieces of information. I
think the benefits of this are straightforward, so long as the patch
doesn't degrade performance.

> Why do we have 2 separate mechanisms that try to detect almost the same cases here?

The current set of mitigations does not detect any cross-thread
double-frees, and doesn't protect against heap buffer overflows from
an attacker who can leak a heap address.

This patch can detect cross-thread double-frees in the tcache, and can
protect against heap buffer overflows from an attacker who can leak a
heap address but cannot leak the tcache key. This raises the bar for
attackers without introducing a noticeable performance penalty.

> 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.

Thanks for the feedback!
Ben