update PNVI-ae-udi paper URL

[web.git] / personal / _posts / 2022-04-11-provenance-exposed.md

diff --git a/personal/_posts/2022-04-11-provenance-exposed.md b/personal/_posts/2022-04-11-provenance-exposed.md
index ae036243e1765f0312f550fa3b1d7e7a8f09cdf3..6ab04f538b7c72e851dd600ec717816602ec159c 100644 (file)
--- a/personal/_posts/2022-04-11-provenance-exposed.md
+++ b/personal/_posts/2022-04-11-provenance-exposed.md
@@ -17,18 +17,20 @@ There's a lot of information packed into this post, so better find a comfortable
 
 In case you don't know what I mean by "pointer provenance", you can either read that previous blog post or the [Strict Provenance documentation](https://doc.rust-lang.org/nightly/core/ptr/index.html#provenance).
 The gist of it is that a pointer consists not only of the address that it points to in memory, but also of its *provenance*: an extra piece of "shadow state" that is carried along with each pointer and that tracks which memory the pointer has permission to access and when.
 
 In case you don't know what I mean by "pointer provenance", you can either read that previous blog post or the [Strict Provenance documentation](https://doc.rust-lang.org/nightly/core/ptr/index.html#provenance).
 The gist of it is that a pointer consists not only of the address that it points to in memory, but also of its *provenance*: an extra piece of "shadow state" that is carried along with each pointer and that tracks which memory the pointer has permission to access and when.

-This is required to make sense of restrictions like "pointer arithmetic can never be used to construct a pointer that is valid for a different allocation than the one it started out in" (even with operations like Rust's [`wrapping_offset`](https://doc.rust-lang.org/std/primitive.pointer.html#method.wrapping_offset) that *do* allow out-of-bounds pointer arithmetic), or "use-after-free is Undefined Behavior, even if you checked that there is a new allocation at the same address as the old one".
+This is required to make sense of restrictions like "use-after-free is Undefined Behavior, even if you checked that there is a new allocation at the same address as the old one".

 Architectures like CHERI make this "shadow state" explicit (pointers are bigger than usual so that they can explicitly track which part of memory they are allowed to access),
 but even when compiling for AMD64 CPUs, compilers act "as if" pointers had such extra state -- it is part of the specification, part of the Abstract Machine, even if it is not part of the target CPU.
 
 ## Dead cast elimination considered harmful
 
 Architectures like CHERI make this "shadow state" explicit (pointers are bigger than usual so that they can explicitly track which part of memory they are allowed to access),
 but even when compiling for AMD64 CPUs, compilers act "as if" pointers had such extra state -- it is part of the specification, part of the Abstract Machine, even if it is not part of the target CPU.
 
 ## Dead cast elimination considered harmful
 

-The key ingredient that will help us understand the nuances of provenance is `restrict`, a C keyword to promise that a given pointer `x` does not alias any other pointer not derived from `x`.
+The key ingredient that will help us understand the nuances of provenance is `restrict`, a C keyword to promise that a given pointer `x` does not alias any other pointer not derived from `x`.[^restrict]

 This is comparable to the promise that a `&mut T` in Rust is unique.
 However, just like last time, we want to consider the limits that `restrict` combined with integer-pointer casts put on an optimizing compiler -- so the actual programming language that we have to be concerned with is the IR of that compiler.
 Nevertheless I will use the more familiar C syntax to write down this example; you should think of this just being notation for the "obvious" equivalent function in LLVM IR, where `restrict` is expressed via `noalias`.
 Of course, if we learn that the IR has to put some limitations on what code may do, this also applies to the surface language -- so we will be talking about all three (Rust, C, LLVM) quite a bit.
 
 This is comparable to the promise that a `&mut T` in Rust is unique.
 However, just like last time, we want to consider the limits that `restrict` combined with integer-pointer casts put on an optimizing compiler -- so the actual programming language that we have to be concerned with is the IR of that compiler.
 Nevertheless I will use the more familiar C syntax to write down this example; you should think of this just being notation for the "obvious" equivalent function in LLVM IR, where `restrict` is expressed via `noalias`.
 Of course, if we learn that the IR has to put some limitations on what code may do, this also applies to the surface language -- so we will be talking about all three (Rust, C, LLVM) quite a bit.
 

+[^restrict]: The exact semantics of `restrict` are subtle and I am not aware of a formal definition. (Sadly, the one in the C standard does not really work, as you can see when you try to apply it to my example.) My understanding is as follows: `restrict` promises that this pointer, and all pointers derived from it, will not be used to perform memory accesses that *conflict* with any access done by pointers outside of that set. A "conflict" arises when two memory accesses overlap and at least one of them is a write. This promise is scoped to the duration of the function call when `restrict` appears in an argument type; I have no good idea for what the scope of the promise is in other situations.
+

 With all that out of the way, consider the following program:
 {% highlight c %}
 #include <stdio.h>
 With all that out of the way, consider the following program:
 {% highlight c %}
 #include <stdio.h>


@@ -76,7 +78,7 @@ static int uwu(int *restrict x, int *restrict y) {
 
   int *y2 = y-1;
   uintptr_t y2addr = (uintptr_t)y2;
 
   int *y2 = y-1;
   uintptr_t y2addr = (uintptr_t)y2;

-  int *ptr = (int*)y2addr;
+  int *ptr = (int*)y2addr; // <-- using y2addr

   *ptr = 1;
 
   return *x;
   *ptr = 1;
 
   return *x;


@@ -102,12 +104,12 @@ static int uwu(int *restrict x, int *restrict y) {
   int *ptr = (int*)y2addr;
   *ptr = 1;
 
   int *ptr = (int*)y2addr;
   *ptr = 1;
 

-  return 0;
+  return 0; // <-- hard-coded return value

 }
 
 int main() {
 }
 
 int main() {

-  int i = 0;
-  int res = uwu(&i, &i);
+  int i[2] = {0, 0};
+  int res = uwu(&i[0], &i[1]);

   // Now this prints 0!
   printf("%d\n", res);
 }
   // Now this prints 0!
   printf("%d\n", res);
 }


@@ -115,9 +117,9 @@ int main() {
 We started out with a program that always prints `1`, and ended up with a program that always prints `0`.
 This is bad news. Our optimizations changed program behavior. That must not happen! What went wrong?
 
 We started out with a program that always prints `1`, and ended up with a program that always prints `0`.
 This is bad news. Our optimizations changed program behavior. That must not happen! What went wrong?
 

-Fundamentally, this is the same situation as in the previous blog post: this
-example demonstrates that either the original program already had Undefined
-Behavior, or (at least) one of the optimizations is wrong. However, the only possibly suspicious part of the original program is a pointer-integer-pointer round-trip -- and if casting integers to pointers is allowed, *surely* that must work.
+Fundamentally, this is the same situation as in the previous blog post: this example demonstrates that either the original program already had Undefined Behavior, or (at least) one of the optimizations is wrong.
+However, the only possibly suspicious part of the original program is a pointer-integer-pointer round-trip -- and if casting integers to pointers is allowed, *surely* that must work.
+I will, for the rest of this post, assume that replacing `x` by `(int*)(uintptr_t)x` is always allowed.

 So, which of the optimizations is the wrong one?
 
 ## The blame game
 So, which of the optimizations is the wrong one?
 
 ## The blame game


@@ -161,7 +163,7 @@ To explain what that side-effect is, we have to get deep into the pointer proven
 Specifically, `x` has permission to access `i[0]` (declared in `main`), and `y` has permission to access `i[1]`.[^dyn]
 `y2` just inherits the permission from `y`.
 
 Specifically, `x` has permission to access `i[0]` (declared in `main`), and `y` has permission to access `i[1]`.[^dyn]
 `y2` just inherits the permission from `y`.
 

-[^dyn]: Actually, this is not quite how `restrict` works. The exact set of locations these pointers can access is determined *dynamically*, and the only constraint is that they cannot be used to access *the same location* (except if both are just doing a load). However, I carefully picked this example so that these subtleties do not change anything.
+[^dyn]: As mentioned in a previous footnote, this is not actually how `restrict` works. The exact set of locations these pointers can access is determined *dynamically*, and the only constraint is that they cannot be used to access *the same location* (except if both are just doing a load). However, I carefully picked this example so that these subtleties should not change anything.

 
 But which permission does `ptr` get?
 Since integers do not carry provenance, the details of this permission information are lost during a pointer-integer cast, and have to somehow be 'restored' at the integer-pointer cast.
 
 But which permission does `ptr` get?
 Since integers do not carry provenance, the details of this permission information are lost during a pointer-integer cast, and have to somehow be 'restored' at the integer-pointer cast.


@@ -194,10 +196,12 @@ This may sound like bad news for low-level coding tricks like pointer tagging (s
 Do we have to optimize this code less just because of corner cases like the above?
 As it turns out, no we don't -- there are some situations where it is perfectly fine to do a pointer-integer cast *without* having the "exposure" side-effect.
 Specifically, this is the case if we never intend to cast the integer back to a pointer!
 Do we have to optimize this code less just because of corner cases like the above?
 As it turns out, no we don't -- there are some situations where it is perfectly fine to do a pointer-integer cast *without* having the "exposure" side-effect.
 Specifically, this is the case if we never intend to cast the integer back to a pointer!

-That might seem like a niche case, but it turns out that most of the time, we can avoid 'bare' integer-pointer casts, and instead use an operation like [`with_addr`](https://doc.rust-lang.org/nightly/std/primitive.pointer.html#method.with_addr) that explicitly specifies which provenance to use for the newly created pointer.
+That might seem like a niche case, but it turns out that most of the time, we can avoid 'bare' integer-pointer casts, and instead use an operation like [`with_addr`](https://doc.rust-lang.org/nightly/std/primitive.pointer.html#method.with_addr) that explicitly specifies which provenance to use for the newly created pointer.[^with_addr]

 This is more than enough for low-level pointer shenanigans like pointer tagging, as [Gankra demonstrated](https://gankra.github.io/blah/tower-of-weakenings/#strict-provenance-no-more-getting-lucky).
 Rust's [Strict Provenance experiment](https://doc.rust-lang.org/nightly/std/ptr/index.html#strict-provenance) aims to determine whether we can use operations like `with_addr` to replace basically all integer-pointer casts.
 
 This is more than enough for low-level pointer shenanigans like pointer tagging, as [Gankra demonstrated](https://gankra.github.io/blah/tower-of-weakenings/#strict-provenance-no-more-getting-lucky).
 Rust's [Strict Provenance experiment](https://doc.rust-lang.org/nightly/std/ptr/index.html#strict-provenance) aims to determine whether we can use operations like `with_addr` to replace basically all integer-pointer casts.
 

+[^with_addr]: `with_addr` has been unstably added to the Rust standard library very recently. Such an operation has been floating around in various discussions in the Rust community for quite a while, and it has even made it into [an academic paper](https://iris-project.org/pdfs/2022-popl-vip.pdf) under the name of `copy_alloc_id`. Who knows, maybe one day it will find its way into the C standard as well. :)
+

 As part of Strict Provenance, Rust now has a second way of casting pointers to integers, `ptr.addr()`, which does *not* "expose" the permission of the underlying pointer, and hence can be treated like a pure operation![^experiment]
 We can do shenanigans on the integer representation of a pointer *and* have all these juicy optimizations, as long as we don't expect bare integer-pointer casts to work.
 As a bonus, this also makes Rust work nicely on CHERI *without* a 128bit wide `usize`, and it helps Miri, too.
 As part of Strict Provenance, Rust now has a second way of casting pointers to integers, `ptr.addr()`, which does *not* "expose" the permission of the underlying pointer, and hence can be treated like a pure operation![^experiment]
 We can do shenanigans on the integer representation of a pointer *and* have all these juicy optimizations, as long as we don't expect bare integer-pointer casts to work.
 As a bonus, this also makes Rust work nicely on CHERI *without* a 128bit wide `usize`, and it helps Miri, too.


@@ -257,7 +261,7 @@ So what are the alternatives?
 Well, I would argue that the alternative is to treat the original program (after translation to Rust) as having Undefined Behavior.
 There are, to my knowledge, generally two reasons why people might want to transmute a pointer to an integer:
 - Chaining many `as` casts is annoying, so calling `mem::transmute` might be shorter.
 Well, I would argue that the alternative is to treat the original program (after translation to Rust) as having Undefined Behavior.
 There are, to my knowledge, generally two reasons why people might want to transmute a pointer to an integer:
 - Chaining many `as` casts is annoying, so calling `mem::transmute` might be shorter.

-- The code doesn't actually care about the *integer* per se, it just needs *some way* to hold arbitrary data in a container of a given time.
+- The code doesn't actually care about the *integer* per se, it just needs *some way* to hold arbitrary data in a container of a given type.

 
 The first kind of code should just use `as` casts, and we should do what we can (via lints, for example) to identify such code and get it to use casts instead.[^compat]
 Maybe we can adjust the cast rules to remove the need for chaining, or add some [helper methods](https://doc.rust-lang.org/nightly/std/primitive.pointer.html#method.expose_addr) that can be used instead.
 
 The first kind of code should just use `as` casts, and we should do what we can (via lints, for example) to identify such code and get it to use casts instead.[^compat]
 Maybe we can adjust the cast rules to remove the need for chaining, or add some [helper methods](https://doc.rust-lang.org/nightly/std/primitive.pointer.html#method.expose_addr) that can be used instead.


@@ -293,7 +297,8 @@ This is the entire reason why all of this "untagged pointer" mess exists.
 Under this brave new world, I can entirely ignore pointer-integer round-trips when designing memory models for Rust.
 Once that design is done, support for pointer-integer round-trips can be added as follows:
 - When a pointer is cast to an integer, its provenance (whatever information it is that the model attaches to pointers -- in Stacked Borrows, this is called the pointer's *tag*) is marked as "exposed".
 Under this brave new world, I can entirely ignore pointer-integer round-trips when designing memory models for Rust.
 Once that design is done, support for pointer-integer round-trips can be added as follows:
 - When a pointer is cast to an integer, its provenance (whatever information it is that the model attaches to pointers -- in Stacked Borrows, this is called the pointer's *tag*) is marked as "exposed".

-- When an integer is cast to a pointer, we *guess* the provenance that the new pointer should have from among all the provenances that have been previously marked as "exposed". (And I mean *all* of them, not just the ones that have been exposed "at the same address" or anything like that. People will inevitably do imperfect round-trips where the integer is being offset before being cast back to a pointer, and we should support that. As far as I know, this doesn't really cost us anything in terms of optimizations.)
+- When an integer is cast to a pointer, we *guess* the provenance that the new pointer should have from among all the provenances that have been previously marked as "exposed".
+  (And I mean *all* of them, not just the ones that have been exposed "at the same address" or anything like that. People will inevitably do imperfect round-trips where the integer is being offset before being cast back to a pointer, and we should support that. As far as I know, this doesn't really cost us anything in terms of optimizations.)

 
 This "guess" does not need to be described by an algorithm.
 Through the magic that is formally known as [angelic non-determinism](https://en.wikipedia.org/wiki/Angelic_non-determinism), we can just wave our hands and say "the guess will be maximally in the programmer's favor": if *any* possible choice of (previously exposed) provenance makes the program work, then that is the provenance the new pointer will get.
 
 This "guess" does not need to be described by an algorithm.
 Through the magic that is formally known as [angelic non-determinism](https://en.wikipedia.org/wiki/Angelic_non-determinism), we can just wave our hands and say "the guess will be maximally in the programmer's favor": if *any* possible choice of (previously exposed) provenance makes the program work, then that is the provenance the new pointer will get.


@@ -313,7 +318,8 @@ And who knows, maybe there *is* a clever way that Miri can actually get reasonab
 It doesn't have to be perfect to be useful.
 
 What I particularly like about this approach is that it makes pointer-integer round-trips a purely local concern.
 It doesn't have to be perfect to be useful.
 
 What I particularly like about this approach is that it makes pointer-integer round-trips a purely local concern.

-With an approach like Stacked Borrows "untagged pointers", *every* memory operation has to define how it handles such pointers -- complexity increases globally, and even when reasoning about Strict Provenance code we have to keep in mind that some pointers in other parts of the program might be "untagged".
+With an approach like Stacked Borrows "untagged pointers", *every* memory operation has to define how it handles such pointers.
+Complexity increases globally, and even when reasoning about Strict Provenance code we have to keep in mind that some pointers in other parts of the program might be "untagged".

 In contrast, this "guessing maximally in your favor"-based approach is entirely local; code that does not syntactically contain exposing pointer-integer or integer-pointer casts can literally forget that such casts exist at all.
 This is true both for programmers thinking about their `unsafe` code, and for compiler authors thinking about optimizations.
 Compositionality at its finest!
 In contrast, this "guessing maximally in your favor"-based approach is entirely local; code that does not syntactically contain exposing pointer-integer or integer-pointer casts can literally forget that such casts exist at all.
 This is true both for programmers thinking about their `unsafe` code, and for compiler authors thinking about optimizations.
 Compositionality at its finest!


@@ -322,7 +328,7 @@ Compositionality at its finest!
 
 I have talked a lot about my vision for "solving" pointer provenance in Rust.
 What about other languages?
 
 I have talked a lot about my vision for "solving" pointer provenance in Rust.
 What about other languages?

-As you might have heard, C is moving towards making [PNVI-ae-udi](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2577.pdf) an official recommendation for how to interpret the C memory model.
+As you might have heard, C is moving towards making [PNVI-ae-udi](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2676.pdf) an official recommendation for how to interpret the C memory model.

 With C having so much more legacy code to care about and many more stakeholders than Rust does, this is an impressive achievement!
 How does it compare to all I said above?
 
 With C having so much more legacy code to care about and many more stakeholders than Rust does, this is an impressive achievement!
 How does it compare to all I said above?
 


@@ -336,7 +342,11 @@ However, if/when a more precise model of C with `restrict` emerges, I don't thin
 The "udi" part of the name means "user disambiguation", and is basically the mechanism by which an integer-pointer cast in C "guesses" the provenance it has to pick up.
 The details of this are complicated, but the end-to-end effect is basically exactly the same as in the "best possible guess" model I have described above!
 Here, too, my vision for Rust aligns very well with the direction C is taking.
 The "udi" part of the name means "user disambiguation", and is basically the mechanism by which an integer-pointer cast in C "guesses" the provenance it has to pick up.
 The details of this are complicated, but the end-to-end effect is basically exactly the same as in the "best possible guess" model I have described above!
 Here, too, my vision for Rust aligns very well with the direction C is taking.

-(The set of valid guesses in C is just a lot more restricted since they do not have `wrapping_offset`. That means they can actually feasibly give an algorithm for how to do the guessing.)
+(The set of valid guesses in C is just a lot more restricted since they do not have `wrapping_offset`, and the model does not cover `restrict`.
+That means they can actually feasibly give an algorithm for how to do the guessing.
+They don't have to invoke scary terms like "angelic non-determinism", but the end result is the same -- and to me, the fact that it is equivalent to angelic non-determinism is what justifies this as a reasonable semantics.
+Presenting this as a concrete algorithm to pick a suitable provenance is then just a stylistic choice.)
+Kudos go to Michael Sammler for opening my eyes to this interpretation of "user disambiguation", and arguing that angelic non-determinism might not be such a crazy idea after all.

 
 What is left is the question of how to handle pointer-integer transmutation, and this is where the roads are forking.
 PNVI-ae-udi explicitly says loading from a union field at integer type exposes the provenance of the pointer being loaded, if any.
 
 What is left is the question of how to handle pointer-integer transmutation, and this is where the roads are forking.
 PNVI-ae-udi explicitly says loading from a union field at integer type exposes the provenance of the pointer being loaded, if any.


@@ -415,15 +425,18 @@ We already have no choice but treat pointer-integer casts as an operation with s
 
 I discussed above how my vision for Rust relates to the direction C is moving towards.
 What does that mean for the design space of LLVM?
 
 I discussed above how my vision for Rust relates to the direction C is moving towards.
 What does that mean for the design space of LLVM?

-Which changes need to be made to fix (potential) miscompilations in LLVM and to make it compatible with these ideas for C and/or Rust?
+Which changes would have to be made to fix (potential) miscompilations in LLVM and to make it compatible with these ideas for C and/or Rust?

 Here's the list of open problems I am aware of:
 Here's the list of open problems I am aware of:

-- LLVM needs to stop [removing `inttoptr(ptrtoint(_))`](https://bugs.llvm.org/show_bug.cgi?id=34548) and stop doing [replacement of `==`-equal pointers](https://bugs.llvm.org/show_bug.cgi?id=35229).
+- LLVM would have to to stop [removing `inttoptr(ptrtoint(_))`](https://github.com/llvm/llvm-project/issues/33896) and stop doing [replacement of `==`-equal pointers](https://github.com/llvm/llvm-project/issues/34577).

 - As the first example shows, LLVM also needs to treat `ptrtoint` as a side-effecting operation that has to be kept around even when its result is unused. (Of course, as with everything I say here, there can be special cases where the old optimizations are still correct, but they need extra justification.)
 - I think LLVM should also treat `inttoptr` as a side-effecting (and, in particular, non-deterministic) operation, as per the last example. However, this could possibly be avoided with a `noalias` model that specifically accounts for new kinds of provenance being synthesized by casts. (I am being vague here since I don't know what that provenance needs to look like.)
 
 So far, this all applies to LLVM as a Rust and C backend equally, so I don't think there are any good alternatives.
 On the plus side, adapting this strategy for `inttoptr` and `ptrtoint` means that the recent LLVM ["Full Restrict Support"](https://lists.llvm.org/pipermail/llvm-dev/2019-March/131127.html) can also handle pointer-integer round-trips "for free"!
 
 - As the first example shows, LLVM also needs to treat `ptrtoint` as a side-effecting operation that has to be kept around even when its result is unused. (Of course, as with everything I say here, there can be special cases where the old optimizations are still correct, but they need extra justification.)
 - I think LLVM should also treat `inttoptr` as a side-effecting (and, in particular, non-deterministic) operation, as per the last example. However, this could possibly be avoided with a `noalias` model that specifically accounts for new kinds of provenance being synthesized by casts. (I am being vague here since I don't know what that provenance needs to look like.)
 
 So far, this all applies to LLVM as a Rust and C backend equally, so I don't think there are any good alternatives.
 On the plus side, adapting this strategy for `inttoptr` and `ptrtoint` means that the recent LLVM ["Full Restrict Support"](https://lists.llvm.org/pipermail/llvm-dev/2019-March/131127.html) can also handle pointer-integer round-trips "for free"!
 

+Adding `with_addr`/`copy_alloc_id` to LLVM is not strictly necessary, since it can be implemented with `getelementptr` (without `inbounds`).
+However, optimizations don't seem to always deal well with that pattern, so it might still be a good idea to add this as a primitive operation to LLVM.
+

 Where things become more subtle is around pointer-integer transmutation.
 If LLVM wants to keep doing replacement of `==`-equal integers (which I strongly assume to be the case), *something* needs to give: my first example, with casts replaced by transmutation, shows a miscompilation.
 If we focus on doing an `i64` load of a pointer value (e.g. as in the LLVM IR produced by `transmute_union`, or pointer-based transmutation in Rust), what are the options?
 Where things become more subtle is around pointer-integer transmutation.
 If LLVM wants to keep doing replacement of `==`-equal integers (which I strongly assume to be the case), *something* needs to give: my first example, with casts replaced by transmutation, shows a miscompilation.
 If we focus on doing an `i64` load of a pointer value (e.g. as in the LLVM IR produced by `transmute_union`, or pointer-based transmutation in Rust), what are the options?