4 ms·

All of this complexity is one of the key reasons that Wasm does not have an addressable stack (it is fully virtualized in the execution semantics). That moves t

by titzer 3y ago

All of this complexity is one of the key reasons that Wasm does not have an addressable stack (it is fully virtualized in the execution semantics). That moves the management of stack-allocated data structures up a level, but guarantees that the machine has control flow integrity (CFI) built in.

H8crilA 3y ago
Wait, it's not about addressability, but essentially about type confusion - typically data that is not actually a code pointer suddenly gets used as such by `ret`. If you are running on a machine that can push an integer but pop it as something else you're still in trouble. BTW, signed pointers are essentially a type check mechanism, where forging types is hard.
- Joker_vD 3y ago
  The activation records don't have to be stored in one piece: it's entirely possible to have a call stack that stores only return addresses and a data stack that stores frames of local variables (that's how you'd normally program e.g. on 6502). Which is a scenario that x64 arguably supports too, having separate RSP and RBP registers, with RBP-addressing being nice and easy and RSP-relative addressing encoded very cumbersomely.
  - Vogtinator 3y ago
    There's AMD shadow stack and Intel CET which do that as well. For compatibility, the return address is also on the data stack, but verified with the address stack.
    - titzer 3y ago
      CET complicates software virtual machines in several ways, e.g. deoptimization and exception handling. It's the wrong solution to a software problem that should never have arisen and just makes software even more complicated. An unfortunate metastasis of running unsafe code without checks for too long.
  - Findecanor 3y ago
    Clang/LLVM supports such a scheme. It saves other variables that don't need to be dereferenced there too. Many utilities on several BSDs are compiled with it, but are necessarily statically linked. <https://clang.llvm.org/docs/SafeStack.html https://clang.llvm.org/docs/SafeStack.html> It is also the default on Fuchsia, which therefore supports shared libraries. <https://fuchsia.dev/fuchsia-src/concepts/kernel/safestack https://fuchsia.dev/fuchsia-src/concepts/kernel/safestack> The problem with these software-based approaches is that it is security-by-obscurity, which breaks if the address to the safe stack would leak. Like ASLR, it is considered more or less broken on 32-bit systems where it is easier to allocate significant portions of the address space to find where it is not and then do educated guesses. However, there have been a few papers using Intel's MPK or even CET to protect it properly, at some performance cost of course. It was also the model that Itanium used. You got the return address in a register and because register windows were saved to a separate stack, it thus saved the return address there too.
  - johnklos 3y ago
    Funny that you use the term "x64", which is a technically incorrect way to refer to 64 bit x86 / amd64. If anything, "x64" refers to Alpha: 21064, 21164, 21264, 21364.
    - Joker_vD 3y ago
      If the thing is widely being known as "x64", then "x64" is that thing's name. That's what the word "name" means. And if you want to be picking nits, it's actually EM64T or at the very worst, IA-32e. Then again, there are actually two versions of this ISA and Intel is currently calling its version "Intel 64" (and AMD used to call their pre-release version "x86-64", by the way), but definitely not "64-bit x86". Edit: Oh hey, you're the same guy who made that silly argument 11 months ago [0]. Never mind me then. [0] https://news.ycombinator.com/item?id=33097250 https://news.ycombinator.com/item?id=33097250
      - johnklos 3y ago
        This is in a thread that's about various CPUs INCLUDING Alpha. Good job ;)
        kjs3 3y ago
        I sure hope you don't call those boxes full of electronics being discussed 'computers' since that's obviously a technically incorrect way to refer to them[1]. [1] https://en.wikipedia.org/wiki/Computer_(occupation) https://en.wikipedia.org/wiki/Computer_(occupation)
        johnklos 3y ago
        Your pedantry is incorrect. Computers are people who compute and machines that compute. The point is that in a discussion that includes Alpha, "x64" obviously isn't clear. Doubling down with "but everyone does it" isn't a good look.
        Moomoomoo309 3y ago
circuit10 3y ago
It does make implementing a custom garbage collector harder though, maybe they could have come up with a compromise where there’s a way to walk over local variables on the stack but instead they’re building GC into the runtime, which is also a good solution but having both options might have been nice because a custom one can be more flexible and supported by runtimes that don’t have GC
- titzer 3y ago
  We've discussed engine support for stack walking for application-level GC within linear memory, but there hasn't been a clear win (at least in my mind) over just using a shadow stack, which doesn't require walking frames, just scanning a memory segment. Opening up the contents of executing stack frames imposes a ton of constraints on the engine and complexity (e.g. engine now has to maintain mappings, support frame modification, etc), that have implications for basically all execution tiers. It doesn't seem like the right tradeoff to me. I've implemented a shadow stack for Virgil, so I am aware of how much it sucks. But that doesn't suck as bad as coming up with a stack walking protocol and then modifying every Wasm engine in existence to support that.
  - circuit10 3y ago
    Actually yes, it sounded good at first but it makes optimisation and determinism harder for the engines so it's probably better not to have it
Findecanor 3y ago
Code compiled to WASM typically also have a stack in the linear memory for storing the program's data structures and values that would need to be dereferenced, thus without any protection. Only the "local" variables and the operand stack are protected. "Control-Flow Integrity" can have a general sense, or a specific sense. In the general sense, it means that function pointers and return addresses are protected — and WASM protects the raw function pointers. In code compiled to WASM, a function pointer is represented as an integer indexing into a single global list with all functions. The "call_indirect" op checks only that the index is within bounds and that the function type signature of the function you look up matches. In the specific sense, as in the 2005 paper titled "Control-Flow Integrity: Principles, Implementations, and Applications", it refers to the code also enforcing that a right function pointer is used at each indirect call site. Each site has a list of allowed function pointers. WASM does not do this. (Sorry for the long post but I just don't want people to get confused and believe that WASM is safer than it is)

by titzer 3y ago

H8crilA 3y ago

Wait, it's not about addressability, but essentially about type confusion - typically data that is not actually a code pointer suddenly gets used as such by `ret`. If you are running on a machine that can push an integer but pop it as something else you're still in trouble. BTW, signed pointers are essentially a type check mechanism, where forging types is hard.

Joker_vD 3y ago
The activation records don't have to be stored in one piece: it's entirely possible to have a call stack that stores only return addresses and a data stack that stores frames of local variables (that's how you'd normally program e.g. on 6502). Which is a scenario that x64 arguably supports too, having separate RSP and RBP registers, with RBP-addressing being nice and easy and RSP-relative addressing encoded very cumbersomely.
- Vogtinator 3y ago
  There's AMD shadow stack and Intel CET which do that as well. For compatibility, the return address is also on the data stack, but verified with the address stack.
  - titzer 3y ago
    CET complicates software virtual machines in several ways, e.g. deoptimization and exception handling. It's the wrong solution to a software problem that should never have arisen and just makes software even more complicated. An unfortunate metastasis of running unsafe code without checks for too long.
- Findecanor 3y ago
  Clang/LLVM supports such a scheme. It saves other variables that don't need to be dereferenced there too. Many utilities on several BSDs are compiled with it, but are necessarily statically linked. <https://clang.llvm.org/docs/SafeStack.html https://clang.llvm.org/docs/SafeStack.html> It is also the default on Fuchsia, which therefore supports shared libraries. <https://fuchsia.dev/fuchsia-src/concepts/kernel/safestack https://fuchsia.dev/fuchsia-src/concepts/kernel/safestack> The problem with these software-based approaches is that it is security-by-obscurity, which breaks if the address to the safe stack would leak. Like ASLR, it is considered more or less broken on 32-bit systems where it is easier to allocate significant portions of the address space to find where it is not and then do educated guesses. However, there have been a few papers using Intel's MPK or even CET to protect it properly, at some performance cost of course. It was also the model that Itanium used. You got the return address in a register and because register windows were saved to a separate stack, it thus saved the return address there too.
- johnklos 3y ago
  Funny that you use the term "x64", which is a technically incorrect way to refer to 64 bit x86 / amd64. If anything, "x64" refers to Alpha: 21064, 21164, 21264, 21364.
  - Joker_vD 3y ago
    If the thing is widely being known as "x64", then "x64" is that thing's name. That's what the word "name" means. And if you want to be picking nits, it's actually EM64T or at the very worst, IA-32e. Then again, there are actually two versions of this ISA and Intel is currently calling its version "Intel 64" (and AMD used to call their pre-release version "x86-64", by the way), but definitely not "64-bit x86". Edit: Oh hey, you're the same guy who made that silly argument 11 months ago [0]. Never mind me then. [0] https://news.ycombinator.com/item?id=33097250 https://news.ycombinator.com/item?id=33097250
    - johnklos 3y ago
      This is in a thread that's about various CPUs INCLUDING Alpha. Good job ;)
      - kjs3 3y ago
        I sure hope you don't call those boxes full of electronics being discussed 'computers' since that's obviously a technically incorrect way to refer to them[1]. [1] https://en.wikipedia.org/wiki/Computer_(occupation) https://en.wikipedia.org/wiki/Computer_(occupation)
        johnklos 3y ago
        Your pedantry is incorrect. Computers are people who compute and machines that compute. The point is that in a discussion that includes Alpha, "x64" obviously isn't clear. Doubling down with "but everyone does it" isn't a good look.
        Moomoomoo309 3y ago

circuit10 3y ago

It does make implementing a custom garbage collector harder though, maybe they could have come up with a compromise where there’s a way to walk over local variables on the stack but instead they’re building GC into the runtime, which is also a good solution but having both options might have been nice because a custom one can be more flexible and supported by runtimes that don’t have GC

titzer 3y ago
We've discussed engine support for stack walking for application-level GC within linear memory, but there hasn't been a clear win (at least in my mind) over just using a shadow stack, which doesn't require walking frames, just scanning a memory segment. Opening up the contents of executing stack frames imposes a ton of constraints on the engine and complexity (e.g. engine now has to maintain mappings, support frame modification, etc), that have implications for basically all execution tiers. It doesn't seem like the right tradeoff to me. I've implemented a shadow stack for Virgil, so I am aware of how much it sucks. But that doesn't suck as bad as coming up with a stack walking protocol and then modifying every Wasm engine in existence to support that.
- circuit10 3y ago
  Actually yes, it sounded good at first but it makes optimisation and determinism harder for the engines so it's probably better not to have it

Findecanor 3y ago

Code compiled to WASM typically also have a stack in the linear memory for storing the program's data structures and values that would need to be dereferenced, thus without any protection. Only the "local" variables and the operand stack are protected. "Control-Flow Integrity" can have a general sense, or a specific sense. In the general sense, it means that function pointers and return addresses are protected — and WASM protects the raw function pointers. In code compiled to WASM, a function pointer is represented as an integer indexing into a single global list with all functions. The "call_indirect" op checks only that the index is within bounds and that the function type signature of the function you look up matches. In the specific sense, as in the 2005 paper titled "Control-Flow Integrity: Principles, Implementations, and Applications", it refers to the code also enforcing that a right function pointer is used at each indirect call site. Each site has a list of allowed function pointers. WASM does not do this. (Sorry for the long post but I just don't want people to get confused and believe that WASM is safer than it is)