How does Rust's provenance model interact with ARM MTE's hardware provenance?

[ais523]

There have been some discussions in this repository about how Rust's provenance model interacts with CHERI, a hardware platform that tracks provenance.

There's another hardware platform that has a level of provenance tracking: ARM MTE (there's more technical information here). This one's interesting in that it has already been deployed to consumers (on certain mobile phones running Android) and thus is in active use at the moment (and because many parts of Android are written in Rust, there's therefore a backwards-compatibility situation to think about).

Unlike CHERI, which aims to guarantee that it catches all the memory-safety issues that are in scope, ARM MTE aims to probabilistically catch memory safety errors (in order to, e.g., make them more obvious in testing). Its provenance model works like this:

• Each memory address has a "tag" (in ARM MTE terminology) that's equivalent to a provenance in Rust terminology. Only pointers with the appropriate provenance are allowed to access the address.
• A pointer contains 56 address bits, 4 provenance bits, and 4 bits that are ignored by the hardware. Unlike on CHERI, the provenance part of a pointer isn't guarded against being modified maliciously – you can read and write it with the normal instructions for reading and writing memory.
• When performing memory access, the hardware acts as-if it checks the pointer's provenance bits against a 4-bit hash of the memory's provenance. (Internally, the hardware only stores the hashes – the machine-code instruction to give memory a new random provenance works by generating a random 4-bit number and acting as though it's the provenance's hash.) As such, if you access memory using the wrong provenance, there is a 13 in 14 chance that it will trap and a 1 in 14 chance that the mistake will be uncaught (0x0 and 0xF aren't used as hash values).

For backwards compatibility with existing programs, ARM MTE is by default configured to pretend that the provenance bits are actually address bits (and although I don't know for certain, I think this is how ARM MTE versions of Rust currently view them). This works for heap memory because new heap provenances are created by the memory allocator, so if the allocator allocates some memory and discovers that (e.g.) its provenance hashes to 4, it can pretend that the memory it's allocating is actually stored at an address which naturally has a 4 in the relevant part of the pointer, and so the programs don't notice that anything has changed. This view does, however, mean that "provenance narrowing" on a reborrow is not something that's visible to the hardware, and thus a program written under this view will never trap if a pointer/reference that's only supposed to be able to access one part of an allocation is used to access a different part (meaning that the hardware is not, even probabilistically, enforcing the entire memory model). Under this view, everything except the heap is given a single provenance, so only mistakes involving heap memory are caught.

The ARM MTE documentation also suggests that compilers might want to use ARM MTE tags for stack memory, by giving a different tag for each variable on the stack (i.e. effectively meaning that each stack allocation has its own provenance). Unlike the previous case, this would be visible to existing programs, in that if the provenance bits are viewed as address bits, stack frames would no longer be contiguous in memory (e.g. if stack frame 1 contains variables a and b, and stack frame 2 contains a variable c, it's possible for c's address to be between that of a and b). In Rust's abstract machine, this difference is observable, but I don't think it's currently relevant – I don't think there's currently a guarantee that stack frames are contiguous, and the vast majority of programs don't care. (Programs/libraries that do stack unwinding might care, and would probably need special code for the platform.)

I guess there are two main questions that this platform raises:

1. Are we currently making (or might we want to make in the future) any guarantees that contradict the way that ARM MTE works, and/or might we want to make such guarantees in the future?
2. How should strict provenance APIs and exposed provenance APIs interpret the provenance bits? Both "interpret them as address bits" and "interpret them as provenance bits" seem like possible models (even exposed provenance can be implemented under the latter because you can ask the processor what the correct provenance for a piece of memory is). The former is likely to be more efficient, but has a number of conceptual downsides (although I'm not sure that any of them would cause problems in practice).

One thing that can probably be ruled out: retagging a reference in Rust effectively creates a new provenance, and in theory it would be nice to track that in the hardware in a BorrowSanitizer sort of way, but too many things go wrong when you try. The problem is that Rust has a stack of provenances with which you can access any memory address (Stacked Borrows is named after its own version of this, but a similar sort of stack turns up in every other provenance model I've experimented with and I think there are theoretical reasons for that), whereas ARM MTE only allows one hardware provenance for any piece of memory at a time. Conceptually, a &mut reference gives the memory a new provenance requirement as it's created and then returns to the original provenance requirement when it's dropped, but safe code allows leaking/forgetting a &mut reference and thus doing that would break safe code. Additionally, if the provenance of memory can change while it's allocated, from_exposed_provenance wouldn't be able to work out the correct provenance to use (but I think CHERI also has that problem).

[RalfJung]

There have been some discussions in this repository about how Rust's provenance model interacts with CHERI, a hardware platform that tracks provenance.

I have to already interrupt here -- CHERI tracks capabilities and those are not the same as provenance. I think we have to be careful in keeping them apart. There are similarities of course, but there are also differences: most importantly of course, provenance is entirely "ghost state", it doesn't exist at runtime. And crucially, even on CHERI, provenance ghost state exists as a separate concept on top of capabilities. Pointers with the same capabilities can have different provenance (and potentially pointers with the same provenance can have the different capabilities).

[RalfJung]

Moving on towards the arm part ---

First of all, if you haven't already then please have a look at the related rust-lang/rfcs#3700 which discusses an operation that would let code update the currently active tag of a memory protection mechanism in an AM-compatible way.

Each memory address has a "tag" (in ARM MTE terminology) that's equivalent to a provenance in Rust terminology.

Again, this is highly misleading terminology. It is definitely not equivalent; even your description already highlights several differences. Let's just call this a "tag" and avoid any confusion arising from using the same name for distinct but related concepts.

When performing memory access, the hardware acts as-if it checks the pointer's provenance bits against a 4-bit hash of the memory's provenance.

I am confused, what is it a hash of? Pointers carry 4 bits, every memory byte/region has a 4 bit "required tag", you just compare those... I don't understand how a hash function would factor in here.

For backwards compatibility with existing programs, ARM MTE is by default configured to pretend that the provenance bits are actually address bits (and although I don't know for certain, I think this is how ARM MTE versions of Rust currently view them).

Yes, that has been the mental model so far. (There have been Zulip discussions about this.)

This view does, however, mean that "provenance narrowing" on a reborrow is not something that's visible to the hardware, and thus a program written under this view will never trap if a pointer/reference that's only supposed to be able to access one part of an allocation is used to access a different part

Correct. That seems fundamental: with such a reborrow (and more generally with SB/TB), there are multiple distinct Rust provenances that are allowed to access the memory, but this hardware model can only model a single active tag, so all those provenances must correspond to the same tag by necessity.

(You even said this later. I'd prefer if you wouldn't first raise what now looks like a rhetorical question that prompts an answer to then answer it yourself 3 paragraphs down.)

Unlike the previous case, this would be visible to existing programs, in that if the provenance bits are viewed as address bits, stack frames would no longer be contiguous in memory

Stack frames are already not contiguous in memory in Miri. This is entirely fine, we make no guarantees at all about where stack or heap memory gets allocated. As far as the Rust Abstract Machine is concerned, there's one big uniform address space and every allocation (stack/heap/static/...) sits at some arbitrary place anywhere in this memory.

How should strict provenance APIs and exposed provenance APIs interpret the provenance bits? Both "interpret them as address bits" and "interpret them as provenance bits" seem like possible models

There's no such thing as a "provenance bit" so I don't know what you mean by that variant. Provenance (the Rust term) is always "abstract/ghost data" that is attached to a real (address) byte.

[Diggsey]

There's no such thing as a "provenance bit" so I don't know what you mean by that variant. Provenance (the Rust term) is always "abstract/ghost data" that is attached to a real (address) byte.

I think what they're asking is: does ptr.addr() mask away the tag when converting to a usize (with that tag being re-generated automatically when using with_exposed_provenance) or do we pretend the tag is just part of the address.

AFAICT as well both options would work.

[ais523]

That seems fundamental: with such a reborrow (and more generally with SB/TB), there are multiple distinct Rust provenances that are allowed to access the memory, but this hardware model can only model a single active tag, so all those provenances must correspond to the same tag by necessity.

There is an alternative way to do it (not one that's better – but theoretically possible): when you mutably borrow/reborrow a piece of memory, you change its MTE-tag, and when the borrow ends, you change it back to the original MTE-tag. As such, putting all the provenances on the same tag is a matter of convenience rather than necessity – in theory, provenances from outside a mutable borrow could be tagged differently from provenances inside.

This alternative way would be impractical in practice for two reasons: a) you would have to store the old tag somewhere to be able to change back to it, b) the opsem doesn't have a clear view of "when the reborrow ends" (because it doesn't take lifetimes into account and there isn't a requirement to "correctly" drop mutable references) and thus has to approximate it by looking for actual uses of a provenance that's further back on the stack.

But I view this alternative way as, in effect, the underlying theoretical provenance model of Rust that the operational semantics is trying to conservatively approximate. For example, Stacked Borrows approximates it using the following two rules:

1. accessing memory that has been mutably borrowed without going via the reference in question implies that the borrow has ended; and
2. passing a mutable reference as a function argument implies that its borrow will still be active at the end of the function call.

(In general, most of the problems with formulating an operational semantics for Rust are based on the fact that the concept of "a mutable borrow has ended" isn't "directly visible" to the semantics, given that it's possible to things like leak or forget mutable references, and given that lifetimes aren't generally involved in the semantics either. If not for that, there would be a very simple opsem model in which a value moves to a different place in memory when it's mutably borrowed (leaving behind a hole that's undefined behavior to access), and moved back when the borrow ends. In this model, the mutable-borrow component of provenance becomes conflated with the address, in that values that have different mutable-borrow provenance also have different addresses, although you need to ignore the "provenance part" of the address when converting to an integer. ARM MTE is interesting because it is conceptually implementing a model like that, by making the MTE-tag part of the pointer value.)

I'm sorry for implying that the mutable-borrow-induced portion of provenance was the entirety of what provenance was about: it's the provenance component I've been primarily focusing on recently when studying Rust operational semantics, so I've been using "provenance" as mental shorthand for it and forgot that the word would include the other components too.

I think what they're asking is: does ptr.addr() mask away the tag when converting to a usize (with that tag being re-generated automatically when using with_exposed_provenance) or do we pretend the tag is just part of the address.

Yes, this was one of my main questions, given that both methods work (either treating the MTE-tag bits as part of the reference's address for strict-provenance API purposes, or treating them as part of the provenance). If you were using the "re-MTE-tag on borrow, revert to the previous tag on unborrow" technique, they would have to be treated as part of the provenance (otherwise reborrowing a reference would change its address, which would violate stable guarantees). But if you keep the tag you get from the allocator in place permanently, treating them as address bits works too.

[RalfJung]

But I view this alternative way as, in effect, the underlying theoretical provenance model of Rust that the operational semantics is trying to conservatively approximate.

Uh... okay. That's not how it is meant though. The entire point is to say that unsafe code may do anything that's compatible with the operational model. It would IMO be wrong to use MTE in a way that rejects UB-free unsafe code.

[ais523]

I don't think it would reject UB-free unsafe code. The documentation for std::ptr says

When creating a mutable reference, then while this reference exists, the memory it points to must not get accessed (read or written) through any other pointer or reference not derived from this reference.

If creating a mutable reference MTE-retags memory, then any access based on the reference would be using the new MTE-tag (and thus not rejected by MTE), and so any access that caused an MTE tag fault would not have been derived from the reference in question and thus would have been UB.

The tricky part is the "while this reference exists" – in order for the model to work correctly, you have to restore the previous MTE tag at the moment the mutable reference no longer exists (because it is no longer enforcing its UB restriction).

[RalfJung]

All those docs are preliminary until we standardize on some aliasing model, then they will be replaced with "follow whatever that model says" (or tower-style "here's some approximate easy rules that ensure you are on the safe side; click here for the exact rules").

[ais523]

OK, I'll express it as "this MTE-retagging system would only trap on unsafe code if that code did something that is currently UB according to the documentation", whilst acknowledging that there are some unsafe operations that would trap under that system but that we may want to eventually permit.

[RalfJung]

I would say it's currently in a grey area. Anyway I don't think quibbling over terms is very useful here; the point is that the docs you quote are vague and under-specified, we definitely want to specify them more precisely eventually, and the options currently being considered for that all allow code which this kind of MTE scheme could not support.