Memory Tagging Extension (MTE) is an ARMv8 extension to detect stale pointers by associating a small allocation tag with each memory granule and embedding the same tag in the pointer. When a pointer is dereferenced, the pointer tag must match the memory tag. If an object has been freed and reused with a different tag, the access fails. It's used on Android and on iOS.
I've been looking a bit at GrapheneOS' hardened_malloc during my lunch break, and found the following todo in the MTE section of the README file:
[future] store previous random tag and increment it to get the next tag for that slot to provide deterministic use-after-free detection through multiple cycles of memory reuse
I sent a pull-request implementing this scheme, without doing a statistical analysis first, assuming that the scheme was an improvement. In retrospect, it was obviously a mistake.
With four-bit MTE tags, there are 16 possible values, from 0 to 15. In both
hardened_malloc and stock Bionic, the value 0 is reserved for freed/unused
memory, leaving 15 usable allocation tags.
Repeated guesses aren't really an issue, as an MTE tag mismatch terminates the process, and attackers on mobile platforms usually don't have a way to force an application to spawn an arbitrary number of subprocesses to quickly bruteforce the tags, obtain privileges, and suppress the notifications of MTE crashes from the other processes. So the only interesting question here is the probability of evasion of an attacker doing a stale access. Under this model, reuse count does not change the random scheme's one-shot probability after the first reuse. It only determines when the attacker must commit to the stale access.
For each allocation, hardened_malloc constructs an exclusion mask containing:
- the reserved tag
0; - the slot's previous tag;
- the left neighbor's tag;
- the right neighbor's tag.
It then picks a random tag amongst the available remaining values.
As the previous tag is always excluded, the first reuse of a freed slot cannot accidentally reuse the stale pointer's tag. On later reuses, the stale tag becomes eligible again. For example:
[tag: 0 | … ]: the object isn't allocated[tag: 5 | … ]: the object is allocated and assigned tag5[tag: 0 | … ]: the object is freed and assigned tag0[tag: 9 | … ]: the object is allocated again and assigned a tag different than0and than5, in our case,9.[tag: 0 | … ]: the object is freed and assigned tag0[tag: 5 | … ]: the object is allocated again and assigned a tag different than0and than9, in our case,5again.
Ignoring neighbor collisions, there are 14 choices after excluding tag 0 and
the slot's previous tag. The probability of reusing the stale tag is therefore
⅟₁₄, which is approximately 7.14%.
Now, hardened_malloc excludes neighboring tags when generating an MTE tag for
a given allocation, making detection of linear overflows deterministic. If the
previous tag and one neighbor tag are distinct, there are 13 possible tags, so
⅟₁₃ (~7.69%). With two distinct neighbor tags, there are
12 possible tags, so ⅟₁₂ (~8.3%). Of course, if a
neighbor object is freed/stale (and is thus using the MTE tag 0,) the
probability goes back to ~7.7%. If both are, we're back to ~7.1%.
With a cycle scheme, tags are chosen sequentially while still skipping excluded
values of course. For example, an object tagged with 14 would be set to 0
when freed, then to 15 when reallocated, then 0 when freed, then 1 when
reallocated, then 0 when freed, then 2 when reallocated, and so on. This
ensures that stale tag can not return during the first 14 reuses, but it'll
always do every 15th iteration. With fixed neighbor exclusions, the cycle can
be shorter because skipped tags are removed from the sequence. With two
distinct neighboring tags, the collision occurs after 13 reuses.
| Chosen reuse | Random risk without neighbours | Random risk without neighbours | Cyclic risk without neighbours | Cyclic risk with neighbours |
|---|---|---|---|---|
| 1 | 0.0% | 0.0% | 0% | 0% |
| 2 | 8.3% | 7.1% | 0% | 0% |
| 3 | 8.3% | 7.1% | 0% | 0% |
| 4 | 8.3% | 7.1% | 0% | 0% |
| 5 | 8.3% | 7.1% | 0% | 0% |
| 6 | 8.3% | 7.1% | 0% | 0% |
| 7 | 8.3% | 7.1% | 0% | 0% |
| 8 | 8.3% | 7.1% | 0% | 0% |
| 9 | 8.3% | 7.1% | 0% | 0% |
| 10 | 8.3% | 7.1% | 0% | 0% |
| 11 | 8.3% | 7.1% | 0% | 0% |
| 12 | 8.3% | 7.1% | 0% | 0% |
| 13 | 8.3% | 7.1% | 0% | 100% |
| 14 | 8.3% | 7.1% | 0% | 0% |
| 15 | 8.3% | 7.1% | 100% | 0% |
The cyclic scheme is useful if the application can guarantee that an attacker can't force the allocator to perform an arbitrary number of cycles, which thanks to hardened_malloc's quarantine feature is likely non-trivial, but not impossible. To me, having a 7.1% to 8.3% chance is better than a deterministic 100% every cycle, so the pull-request was closed, and I sent another one to remove the todo.
One might be tempted to suggest to use the cyclic scheme up until right before
the tag reuse, but this would increase complexity to only bring reuse chances
to 0% for len(cycle) - 2 allocations, which isn't worthwhile on long-running
applications with a significant amount of allocations/deallocations, or when an
attacker can influence the amount of allocations recycling.
Other schemes exist, like "even-odd alternation" to ensure that a tag for a reuse is always different, but it's strictly worse than keeping note of the previously used tag, as it reduces the size of the available by a factor two: 1,3,5,7,9,11,13,15 and 2,4,6,8,10,12,14, so with no allocated neighbours, ⅟₂·⅟₈+⅟₂·⅟₇ (~13.3%), and ⅟₂·⅟₈+⅟₂·⅟₅ (16.2%) in the worst case with two neighbours using even tags.
"Spatial even-odd alternation" assigns even or odd tags per chunk, so that linear overflows are deterministically caught, but it's worse than simply looking at neighbors, and has a chance of of ⅟₈ (12.5%) for odd tags and ⅟₇ (~14.2%) for even ones.