# Position on the Rust language with optional strict provenance

I explain

- What I think the language should look like
- How we might support devs with tooling
- How this relates to CHERI

This is a living document, which I am refining as my understanding improves.

## Scope

Inspired by [Gankra's post](https://gankra.github.io/blah/fix-rust-pointers/) and elaborating on [the tracking issue](https://github.com/rust-lang/rust/issues/95228), we would like

- a pathway to a formally-defined execution model, so that we can tell bugs from non-bugs in `rustc`
- compilation to fast code — meaning that powerful alias analysis applies to common Rust code
- that a lot of existing unsafe code keeps working
- to keep supporting `inttoptr` for some niche use cases, like pointer compression or ["pointer in u32"](https://users.rust-lang.org/t/32-bit-pointers-to-the-heap/58255)
- to support CHERI very well for strict-provenance code
- to support CHERI decently without forcing the whole program to be strict-provenance
- to avoid weird miscompilations like https://www.ralfj.de/blog/2020/12/14/provenance.html
- to empower developers who write Unsafe Rust to learn and understand what they can do and what they can't do

We believe that pointer-to-int transmutes (not casts but transmutes) are incredibly rare. I agree that they [can't reasonably](https://github.com/rust-lang/unsafe-code-guidelines/issues/286#issuecomment-1085144431) [be supported](https://github.com/rust-lang/rust/pull/95547). Consider instead [migrating to `MaybeUninit<integer type>`](https://github.com/rust-lang/unsafe-code-guidelines/issues/286#issuecomment-1086218649).

## Proposal

I think the following approach gets us everything or 99% of what we want.

- We keep `usize as ptr` permissive as is, and we discourage its use. We don't change its meaning compared to what it meant before — it is definitely able to produce valid pointers in the right circumstances. For an idea of what it could mean formally, see [Formal memory models](#Formal-memory-models) below.

- We deprecate the `usize as ptr` syntax, to be replaced with something like `std::ptr::from_exposed` that can be documented better.

- We keep `ptr as usize` permissive as is, but we discourage their use.

- We deprecate the `ptr as usize` syntax, to be replaced with something [like](https://rust-lang.zulipchat.com/#narrow/stream/136281-t-lang.2Fwg-unsafe-code-guidelines/topic/Strict.20provenance/near/277455397) `ptr.expose_addr()` that can be documented better.

- We make any pointer-to-int transmute undefined behavior.

- MVP for CHERI is to only support strict-provenance operations.

- For CHERI, allow the user to opt in to a polyfill implementation of `std::ptr::from_exposed` and `ptr.expose_addr()`. Otherwise, those functions do not exist. The polyfills are only functional for pointers into allocations by Rust.

- [Polyfill proposal #1](#Appendix-CHERI-polyfill-1-more-secure) is the more secure one — it lets the hardware keep every allocation secure that hasn't been explicitly exposed.

- [Polyfill proposal #2](#Appendix-CHERI-polyfill-2-lower-overhead-still-more-secure-than-non-CHERI) has a lower overhead, but it has no real checks on `std::ptr::from_exposed`. Compared to traditional machines, the machine still traps on pointer reads from non-pointer memory, which is a major safety improvement on x64.

- For CHERI, we use the `*.CAP` instructions, not `*.DDC`.

- There is `ptr.addr()` which is fast on CHERI -- but `ptr.addr() as ptr` is principally UB.

- With the new `#[feature(strict_provenance)]` functions in `std::ptr`, we can convert `ptr.addr()`-based addresses back into real pointers, even on CHERI.

- We keep `std::ptr::invalid` as in nightly. This corresponds to "strict" `inttoptr`. It is UB to dereference these.

- We introduce a performance lint against `usize as ptr` and `ptr as usize` and their synonyms — because compared to their strict analogs, they have a performance cost, and (when compiling to CHERI) remove some safety

- All other ways to create a pointer (in particular various transmutes) are UB.

- For our memory model, we keep aiming for something like Stacked Borrows — which allows for permissive and strict provenance in the same program, but is difficult to understand.

- We aim to define a simpler submodel of our real memory model, which (1) only permits strict provenance `ptr2int2ptr`, and (2) is efficiently machine-checkable by Miri, and (3) can more easily be learned and understood by developers.

## Expected consequences

Then language-wise,

- We don't need no compiler flag, no opt-in, no opt-out

- We break pointer-to-int transmute

- We break pretty much nothing else (presumably, to be [investigated](https://rust-lang.zulipchat.com/#narrow/stream/136281-t-lang.2Fwg-unsafe-code-guidelines/topic/Strict.20provenance/near/277349017))

- This doesn't create new questions around FFI

- We can have much better stdlib documentation on all involved operations

- We plan to rewrite crates so `usize as ptr` and `ptr as usize` (and their legacy `as` spellings) are no longer used. This is only a performance improvement — the original still works.

- CHERI works well for strict-provenance programs

- CHERI works for permissive-provenance programs. There is a performance/memory cost compared to strict-provenance-only programs, but this is mostly isolated to call sites of `ptr.expose_addr()` and `std::ptr::from_exposed`.

- CHERI is fast after the ecosystem transitions over

- Compressed pointers keep working as they do now — and pretty fast on x64.

- Our relation with LLVM stays principally the same.

- But we have a "solid ground" for working on `rustc` — we know how it should behave.

- Transmuting / memory semantics [needs to be refined further](https://github.com/rust-lang/unsafe-code-guidelines/issues/286).

Then developers who want to write Unsafe Rust

- ...may want to write with strict provenance instead of permissive provenance
- ...will better understand Rust-with-only-strict-provenance
- ...will be more comfortable and successful writing Unsafe Rust without undefined behavior
- ...are empowered to check their understanding, simply by running enough tests through [strict-provenance Miri](https://github.com/rust-lang/miri/pull/2045)

Note: here strict provenance is a *tool* to write good Unsafe Rust. It is not necessary that every crate becomes strict-only-provenance. Once you have good Unsafe Rust, you can combine it with other crates and you don't have to worry how they have been written.

(Although strict provenance may still be slightly faster. And on CHERI, also safer.)

## Formal memory models

There are three memory models relevant for discussion. We list them in order of least UB to most UB.

### Model 1: plain Stacked Borrows -- we don't use this

This is pretty good already. It is a reasonable formal model, and we can check it with Miri.

In this model, there is no real distinction between ptr and int. (You can still only cast from references to ptr, not from references to int.)

But the compiler is limited from doing some optimizations. Take this example.

let mut storage : i8 = 0;

let x_ptr: *mut i8 = &mut storage as *mut i8;
let y: &mut i8 = &mut storage;

{
    //! ------------------------------------
    //!
    //! Pretend that the optimizer can only look
    //! inside this block. It is aware of only two
    //! variables:
    //!
    //!   - x_ptr : *mut i8
    //!   - y :     &mut i8

    let y_ptr = y as *mut i8
    *x_ptr = 12; // (1)
    *y_ptr = 34; // (2)
}

storage

Under plain SB, this code is valid and does not contain UB. But the compiler is not allowed to swap the assignments (1) and (2). This can realistically prevent other optimizations from kicking in.

### Model 2: Stacked Borrows with nondeterministically-tagged raw pointers -- proposal for full Rust with permissive provenance

In this model and below, `ptr` is *actually* something different from `usize`. Raw pointers have provenance, integers don't.

This lets the optimizer be better: now it is allowed to swap (1) and (2).

The example program becomes UB at point (1). You are not allowed to use a raw pointer when a newer `&mut` is active for the same location. (Here, that's `y`.)

This is a viable candidate for Rust's official memory model.

**The advantage of this model is that ptr2int2ptr is still allowed as it is today. (Only through cast, not through transmute.) Developers can pretty much treat ptr and usize as interchangable.**

The drawbacks of this model are:

- The mathematical details of this model are very complicated.
- Miri can't check against this model.

### Model 3: Stacked Borrows with strict provenance -- good for programmers and Miri

This model would be a "useful simplification" of Rust.

In this model, (1) is still UB. Additionally you're not able to cast integers to pointers any more.

The advantages are

- it's easy to understand everything that you're allowed to do
- Miri can check your program against this model with `-Zmiri-strict-provenance`.

### Appendix: a freak example of code with ptr2int2ptr that remains allowed with permissive provenance

There is no UB in this example under permissive provenance.

let mut storage : i8 = 0;

let x_int: usize = &mut storage as *mut i8 as usize;
let y: &mut i8 = &mut storage;

{
    //! ------------------------------------
    //!
    //!   - x_int : usize
    //!   - y :     &mut i8

    let y_ptr = y as *mut i8;
    let _ = y_ptr as usize;
    // The raw pointer receives provenance from the
    // conversion "y_ptr as usize" above! 🤯
    *(x_int as *mut i8) = 12;
    *y_ptr = 34;
}

storage

## Appendix: CHERI polyfill 1: more secure

This polyfill lets the hardware keep every allocation secure that hasn't been explicitly exposed. You can use `std::ptr::from_exposed`, but only if the address points into an allocation that is still live that has been exposed.

1. The runtime puts 1 byte of spacing between every allocation. *This is needed to map pointers unambiguously to allocations.*

2. The runtime maintains capabilities to all allocatable address ranges, hidden from the program. (It probably needs this anyway for `malloc`.)

3. There is a global [collection of live "exposed" allocations](https://rust-lang.zulipchat.com/#narrow/stream/136281-t-lang.2Fwg-unsafe-code-guidelines/topic/Strict.20provenance/near/277317047), each associated to a capability that's valid for the whole allocation.

4. `ptr.expose_addr()` looks in the state of the allocator to find the full address range of the allocation. Then it uses (2) to create a r/w capability for the whole allocation, and inserts into collection (3).

5. `std::ptr::from_exposed` looks in the collection (3) for the r/w capability for the whole allocation. If the collection does not contain such an allocation, a panic is raised.

6. `free` looks up the allocation in the collection (3), and removes it if it was there.

7. the ptr2int2ptr integer type ("`usize`") might be pointer-sized. Then it could contain the base+top+permissions; step (5) would apply them again.

8. the ptr2int2ptr integer type ("`usize`") might be address-sized. But then the program can observe that the base+top+permissions changed.

There are open questions around the fact that you can *observe* the base and top of a pointer. So the program can observe that `ptr2int2ptr(p) != p`.

## Appendix: CHERI polyfill 2: lower-overhead, still more secure than non-CHERI

With this polyfill, `int2ptr` is not checked at runtime, and the overhead of ptr2int2ptr is lower. However there is still a big advantage over non-CHERI machines: the machine prevents bad transmutes at runtime. These transmutes are UB anyway, but instead of leading to security vulnerabilities, a panic is raised. The program may even recover at runtime from bad transmutes.

1. The runtime puts 1 byte of spacing between every allocation. *This is needed to map pointers unambiguously to allocations.*

2. The runtime maintains capabilities to all allocatable address ranges, hidden from the program. (It probably needs this anyway for `malloc`.)

3. `ptr.expose_addr()` extracts the address portion of the capability.

4. `std::ptr::from_exposed` uses (2) to create a the r/w capability for the whole allocation.

5. the ptr2int2ptr integer type ("`usize`") might be pointer-sized. Then it could contain the base+top+permissions; step (4) would apply them again.

6. the ptr2int2ptr integer type ("`usize`") might be address-sized. But then the program can observe that the base+top+permissions changed.

There are open questions around the fact that you can *observe* the base and top of a pointer. So the program can observe that `ptr2int2ptr(p) != p`.

## Remarks

- In my understanding, strict-provenance-only doesn't gain us anything with regards to optimizations.

- Tackling the issue of integer sizes is desirable, but out of scope of this position document.

Original URL: https://rust-lang.zulipchat.com/#narrow/stream/136281-t-lang.2Fwg-unsafe-code-guidelines/topic/Strict.20provenance/near/277358112