The number of combinations is irrelevant if you're not relying on randomness. Graphene sets the tag to a static value on deallocation[0] to prevent use-after-free, you don't even need to guess! The same is true for a lot of buffer overflows, as their allocator ensures two adjacent allocations have different tags, so unless the vuln allows you to skip ahead you'll always trigger a fault.

[0] https://github.com/GrapheneOS/hardened_malloc/blob/7481c8857...

We use the standard reserved tag (zero) for freed data but we also dynamically exclude the previous non-free tag for the current slot and the most recent adjacent non-free tags (i.e. the current tag for the adjacent slots or the previously used on if they're currently free). This provides a lot of deterministic protection against use-after-free especially when combined with our quarantine. It provides full deterministic protection against small or linear overflows. The fallback to probabilistic protection with 15 random values is still very valuable and does not mean only lowering exploit chance to 1/15. An exploit can require multiple invalid memory accesses. Side channels for leaking tag values aren't inherently usable in every case and an attacker can't simply choose the memory layout.

Interesting, fair point! I guess it helps for vulnerabilities that don't allow pointer control (which is probably a lot of them).