4 ms·

> Nothing else should know where `q` even is, let alone modify it behind the scenes. What am I missing? The variable iq knows where q is, no? uintptr_t iq =

> Nothing else should know where `q` even is, let alone modify it behind the scenes. What am I missing? The variable iq knows where q is, no? uintptr_t iq = (uintptr_t)q; If you (the compiler) can't analyze beyond that, that's the end of the story: the address escaped somewhere. If you can... well then not only that, but a decision was made on it: if (iq == ip) And then a write was performed on an address that you clearly can't prove was uncontaminated with q's address: *(char*)iq = 10;

jcranmer 2y ago
That's sort of the crux of the issue: what constitutes exposing a pointer? Half the time, within the compiler, a pointer-to-integer conversion is essentially a nop cast instruction that can be optimized away if unused or freely deleted (e.g., roundtrip pointer-to-integer-to-pointer) or slide addressing information before and after the pointer. The other half the time, it's an important leaks-the-address operation that can't be triggered because, you know, that causes things to be leaked. It's Schrödinger's side effects, they both matter and don't matter, and you don't know if it ends up doing so or not until you open the box. It's a complete mess, and ultimately entirely incoherent, inconsistent semantics that is begging for a fix. Even worse, if you read all the compiler documentation, you'll find strong assertions that provenance is carried solely by data dependence (including through integers). The compiler optimizations for integers explicitly disclaim preservation of data dependence, which is why the leading model for pointer provenance (PVNI) is "integers don't have provenance, therefore pointer-to-int is an address-exposing operation." But even more annoyingly, the semantics at the IR level imply that memory is untyped, which kind of means every load or store of a pointer is an implicit integer conversion, but that doesn't actually happen in practice, except that memory is frequently converted to an integer if you're just copying from one block of memory to another and it's just a mess of several optimizations are broken in weird, unexpected ways that no one really realized until people started trying to apply formal semantics to compiler optimizations and found these soundness holes. And the most annoying part of all are the people sitting on the sidelines yelling at us "pointers are integers, why are you guys making this all so complicated?"
- jkrejcha 2y ago
  > That's sort of the crux of the issue: what constitutes exposing a pointer? A lot of the people who subscribe to "optimization 3 is clearly wrong" make the argument that the answer is... everything is always exposed, whether it be (uintptr_t)0x42, some valid stack pointer, or anywhere else for that matter. This certainly tracks with the model that many C (and systems programmers, more generally) expect the language semantics to represent. It disables a lot of optimizations to make these assumptions, but the argument generally is that many of those optimizations were likely extremely tenuous in the first place and have potentially dubious benefits outside of contrived benchmarks. This also was the point of the "restrict" and "register" keywords to tell the compiler "hey you can assume these things don't alias with each other" or "hey use registers for this variable", etc. It's clear that a demand for this type of language semantics exists, as most large projects you can probably think of have flags that disable a lot of the alias assumptions (everything from Linux to Firefox to Clang (in some cases) to Chrome, etc) and some compilers (such as MSVC) don't bother with many of the alias assumptions in the first place (which affects anything built with those compilers).
  - dataflow 2y ago
    > A lot of the people who subscribe to "optimization 3 is clearly wrong" make the argument that the answer is... everything is always exposed For anyone reading this, note that that's not what I'm arguing -- my argument very specifically depends on the exposure of q: https://news.ycombinator.com/item?id=42906600 https://news.ycombinator.com/item?id=42906600
    - jkrejcha 2y ago
      Yeah, this does make the "read pointer from user input" case (which is actually sometimes useful) a bit weird however but it seems pretty obvious that ptr-to-int should probably be exposing at the very least
      - dataflow 2y ago
        > Yeah, this does make the "read pointer from user input" case (which is actually sometimes useful) a bit weird I think it works out quite reasonably and elegantly, actually. If you can prove that an address wasn't leaked -- then you can assume the program behavior is independent of any pointer read from user input, and thus optimize as if the pointer wasn't read from user input. Otherwise, you assume the address was leaked, and thus must act as if the target might overlap said address. > however but it seems pretty obvious that ptr-to-int should probably be exposing at the very least I don't think that's necessary, but it's certainly a valid way to write a compiler. (I say this because I don't think (void)(uintptr_t)ptr; should be considered exposing, for example.)
Veserv 2y ago
In the original code, it stores through q. In the optimized example: *(char*)iq = 10 -> *(char*)(uintptr_t)(p + 1) = 10 After that optimization pass, there is no store to q. C assumes that you can not store to a different object without doing out-of-bounds pointer arithmetic and that out-of-bounds pointer arithmetic is illegal, therefore it assumes that q is not stored during that store. The problem is that the optimizer replaced a plain store through q with a illegal out-of-bounds pointer arithmetic store (because it was sneakily done in non-pointer land). That causes the "safety" checking (that can check less because of that invariant) to be insufficient. The problem is not leaking q, it is blindly replacing a legal construct with an "illegal" construct. The specific problem here being the pointer cast which turned a integer into a pointer. You have no clue where that points to without analyzing the value of that integer. As such, the assumption should be: "can store anywhere, all loads everywhere in the program are suspect" when that occurs. You can then utilize pointer provenance to prove that "no, we do know where this can point to, the optimization/caching party is back on". Leaking did not occur because they saved the address of q. "Leaking" occurred because they cast a integer to a pointer which can "leak" a pointer to literally anything.
- dataflow 2y ago
  > Leaking did not occur because they saved the address of q. "Leaking" occurred because they cast a integer to a pointer which can "leak" a pointer to literally anything. No - please see the following comment, I respond to this same comment there: https://news.ycombinator.com/item?id=42906600 https://news.ycombinator.com/item?id=42906600
  - Veserv 2y ago
    I agree that you could choose semantics such that as soon as you take the address of a object that any store anywhere could alias it, so it is no longer legal to ever cache the value unless you prove the store does not overlap. But, the key thing here is that if the programmer wrote: *(p+1) = 10; print(q[0]); It is entirely reasonable and legal for the compiler to optimize that to: *(p+1) = 10; print(0); Because the abstract model says that stores to one object can not alias another object. You, as the programmer, are required to not author out-of-bounds stores and a good compiler could detect illegal constructs. However, in this case, the optimizer transformed a legal, well-formed construct into a illegal construct and then optimized as if it was always a illegal construct. Focusing on directly preventing such transforms and why such transforms should be illegal (pointing out the legal -> illegal thing they enable) minimizes the changes needed to the model.

jcranmer 2y ago

That's sort of the crux of the issue: what constitutes exposing a pointer? Half the time, within the compiler, a pointer-to-integer conversion is essentially a nop cast instruction that can be optimized away if unused or freely deleted (e.g., roundtrip pointer-to-integer-to-pointer) or slide addressing information before and after the pointer. The other half the time, it's an important leaks-the-address operation that can't be triggered because, you know, that causes things to be leaked. It's Schrödinger's side effects, they both matter and don't matter, and you don't know if it ends up doing so or not until you open the box. It's a complete mess, and ultimately entirely incoherent, inconsistent semantics that is begging for a fix. Even worse, if you read all the compiler documentation, you'll find strong assertions that provenance is carried solely by data dependence (including through integers). The compiler optimizations for integers explicitly disclaim preservation of data dependence, which is why the leading model for pointer provenance (PVNI) is "integers don't have provenance, therefore pointer-to-int is an address-exposing operation." But even more annoyingly, the semantics at the IR level imply that memory is untyped, which kind of means every load or store of a pointer is an implicit integer conversion, but that doesn't actually happen in practice, except that memory is frequently converted to an integer if you're just copying from one block of memory to another and it's just a mess of several optimizations are broken in weird, unexpected ways that no one really realized until people started trying to apply formal semantics to compiler optimizations and found these soundness holes. And the most annoying part of all are the people sitting on the sidelines yelling at us "pointers are integers, why are you guys making this all so complicated?"

jkrejcha 2y ago
> That's sort of the crux of the issue: what constitutes exposing a pointer? A lot of the people who subscribe to "optimization 3 is clearly wrong" make the argument that the answer is... everything is always exposed, whether it be (uintptr_t)0x42, some valid stack pointer, or anywhere else for that matter. This certainly tracks with the model that many C (and systems programmers, more generally) expect the language semantics to represent. It disables a lot of optimizations to make these assumptions, but the argument generally is that many of those optimizations were likely extremely tenuous in the first place and have potentially dubious benefits outside of contrived benchmarks. This also was the point of the "restrict" and "register" keywords to tell the compiler "hey you can assume these things don't alias with each other" or "hey use registers for this variable", etc. It's clear that a demand for this type of language semantics exists, as most large projects you can probably think of have flags that disable a lot of the alias assumptions (everything from Linux to Firefox to Clang (in some cases) to Chrome, etc) and some compilers (such as MSVC) don't bother with many of the alias assumptions in the first place (which affects anything built with those compilers).
- dataflow 2y ago
  > A lot of the people who subscribe to "optimization 3 is clearly wrong" make the argument that the answer is... everything is always exposed For anyone reading this, note that that's not what I'm arguing -- my argument very specifically depends on the exposure of q: https://news.ycombinator.com/item?id=42906600 https://news.ycombinator.com/item?id=42906600
  - jkrejcha 2y ago
    Yeah, this does make the "read pointer from user input" case (which is actually sometimes useful) a bit weird however but it seems pretty obvious that ptr-to-int should probably be exposing at the very least
    - dataflow 2y ago
      > Yeah, this does make the "read pointer from user input" case (which is actually sometimes useful) a bit weird I think it works out quite reasonably and elegantly, actually. If you can prove that an address wasn't leaked -- then you can assume the program behavior is independent of any pointer read from user input, and thus optimize as if the pointer wasn't read from user input. Otherwise, you assume the address was leaked, and thus must act as if the target might overlap said address. > however but it seems pretty obvious that ptr-to-int should probably be exposing at the very least I don't think that's necessary, but it's certainly a valid way to write a compiler. (I say this because I don't think (void)(uintptr_t)ptr; should be considered exposing, for example.)

Veserv 2y ago

In the original code, it stores through q. In the optimized example: *(char*)iq = 10 -> *(char*)(uintptr_t)(p + 1) = 10 After that optimization pass, there is no store to q. C assumes that you can not store to a different object without doing out-of-bounds pointer arithmetic and that out-of-bounds pointer arithmetic is illegal, therefore it assumes that q is not stored during that store. The problem is that the optimizer replaced a plain store through q with a illegal out-of-bounds pointer arithmetic store (because it was sneakily done in non-pointer land). That causes the "safety" checking (that can check less because of that invariant) to be insufficient. The problem is not leaking q, it is blindly replacing a legal construct with an "illegal" construct. The specific problem here being the pointer cast which turned a integer into a pointer. You have no clue where that points to without analyzing the value of that integer. As such, the assumption should be: "can store anywhere, all loads everywhere in the program are suspect" when that occurs. You can then utilize pointer provenance to prove that "no, we do know where this can point to, the optimization/caching party is back on". Leaking did not occur because they saved the address of q. "Leaking" occurred because they cast a integer to a pointer which can "leak" a pointer to literally anything.

dataflow 2y ago
> Leaking did not occur because they saved the address of q. "Leaking" occurred because they cast a integer to a pointer which can "leak" a pointer to literally anything. No - please see the following comment, I respond to this same comment there: https://news.ycombinator.com/item?id=42906600 https://news.ycombinator.com/item?id=42906600
- Veserv 2y ago
  I agree that you could choose semantics such that as soon as you take the address of a object that any store anywhere could alias it, so it is no longer legal to ever cache the value unless you prove the store does not overlap. But, the key thing here is that if the programmer wrote: *(p+1) = 10; print(q[0]); It is entirely reasonable and legal for the compiler to optimize that to: *(p+1) = 10; print(0); Because the abstract model says that stores to one object can not alias another object. You, as the programmer, are required to not author out-of-bounds stores and a good compiler could detect illegal constructs. However, in this case, the optimizer transformed a legal, well-formed construct into a illegal construct and then optimized as if it was always a illegal construct. Focusing on directly preventing such transforms and why such transforms should be illegal (pointing out the legal -> illegal thing they enable) minimizes the changes needed to the model.