6 ms·

This is crazy. I remember thinking when I first heard about stack and heap growing towards each other: uh-oh. But the problem was so blindingly obvious that I j

by e12e 9y ago

This is crazy. I remember thinking when I first heard about stack and heap growing towards each other: uh-oh. But the problem was so blindingly obvious that I just assumed any system written for anything beyond co-operative multitasking had a fix - because if not there was obviously no actual memory safety...

tptacek 9y ago
What would the fix be? The fact that you can point the stack pointer at arbitrary memory and the CPU will treat that memory as the stack is a feature, and an important one, of the ISA. The real issue here is that writing programs in memory-unsafe languages is inherently difficult and risky, and fewer programs should be written that way.
- geofft 9y ago
  I'd hesitate to pin the blame on "memory-unsafe languages", because Rust is currently vulnerable to the same attack: https://github.com/rust-lang/rust/issues/16012 https://github.com/rust-lang/rust/issues/16012 It looks like the fix is going to involve adding some code to LLVM to probe each stack page when you make a large stack allocation, but once that happens, it's straightforward for clang to implement -fstack-check for C and C++ programs, too. This is a weird emergent problem from the fact that stack and heap memory are part of the same address space and that the stack is designed to implicitly grow as needed. It's not clear that it's a language or compiler's fault for relying on the stack doing that, nor that it's the platform or kernel's fault for making that approach possible. I'm not totally sure how you would design a language so that you don't have this problem. I guess you could forbid a function from using more than some small amount of stack, and make sure your stack guard area is at least that big, but that seems like an unfortunate restriction. Maybe something like the Stackless Python approach, where all variables are heap-allocated, would work? Also, all that said, note that Windows gets this right: MSVC inserts calls to _chkstk() to do stack probing. I believe this entire class of vulnerability doesn't exist on Windows, and probably some people at MS who spend their entire lives in memory-unsafe languages are feeling very smug today.
  - pcwalton 9y ago
    I'm working on it in Rust right now. Hopefully should have a patch up today.
    - kibwen 9y ago
      No way. If so: be still, my heart. Been waiting for LLVM support for this for ages.
    - pcwalton 9y ago
      Patches ready. Waiting on reviews. https://reviews.llvm.org/D34386 https://reviews.llvm.org/D34386 https://reviews.llvm.org/D34387 https://reviews.llvm.org/D34387
- clarry 9y ago
  You're really barking at the wrong tree here. The user of the memory-unsafe language isn't at fault here for doing things the implementation will utilize stack for. The language specification -- the contract between him and the implementation, never stated or implied that he is responsible for making sure that these objects on stack aren't accessed in larger than page sized increments. The word "stack" never appears in the C specification. At a source level, these programs may as well be 100% bug free. This is nothing more than a quirk of implementation. And one that affects all languages that use the stack (and by which I mean the stack, not some heap-allocated structure the language provides stack-like operations on). Memory safety doesn't really enter the picture.
- e12e 9y ago
  The design might be fundamentally broken, but if so you're saying that even with an mmu, we can only have co-operative multitasking. That's not the promise of a multi-user/multi-prosess system. If "all programs are safe", we could just use the Amiga OS kernel and no longer need an mmu, or a similar design. [ed: apparently windows NT takes steps to avoid this according to a sibling comment. Not clear, but I assume it implies a performance hit for certain heavy stack usage?]
  - clarry 9y ago
    There would be a performance hit, but that is likely to be insignificant. Apparently the stack check code touches every stack page. If performance were a concern (and I don't really think it is), it should be possible to reduce the impact by assuming a sufficiently large stack guard that the majority of functions with fixed size stack frames could never leap over. Then these functions wouldn't need any runtime checks. The only checking you'd have to do is on code that uses VLAs, alloca, or such, along with the few outlier functions that use ridiculously large fixed size buffers. I don't see why you should need to touch every page.
  - geofft 9y ago
    I don't entirely follow what you're saying in your first sentence, but I'm going to try to respond to what I think you're saying. If I'm off base please let me know! 1. Memory-safe languages are about making sure that the programmer's intended behavior matches the actual behavior, that is, eliminating a class of bugs related to memory unsafety. They are a security scheme insofar as these bugs are security bugs, but they're not an interprocess security scheme. In particular, you can write a memory-safe debugger that goes and makes arbitrary modifications to other processes the OS gives it access to. You can even write a memory-safe program in Rust that goes and edits /proc/self/mem. But in these cases, the programmer is intending to mess with process memory directly, so the language isn't obligated to stop the programmer. It is obligated to stop the programmer from, say, overflowing a string and overwriting the return address. 2. It is certainly possible to design a memory-safe language that is usable for interprocess memory protection. Microsoft had a research OS called Singularity that did exactly this: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/osr2007_rethinkingsoftwarestack.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... But it's another step on top of memory safety. 3. Preemptive multitasking and protected memory aren't inherently related (although, yes, in the market, most cooperatively multitasked OSes lacked memory protection, and most OSes with memory protections were preemptively multitasked). You can have a preemptively multitasked system with no MMU at all; you just need to respond to timer interrupts and switch tasks.

by e12e 9y ago

tptacek 9y ago

What would the fix be? The fact that you can point the stack pointer at arbitrary memory and the CPU will treat that memory as the stack is a feature, and an important one, of the ISA. The real issue here is that writing programs in memory-unsafe languages is inherently difficult and risky, and fewer programs should be written that way.

geofft 9y ago
I'd hesitate to pin the blame on "memory-unsafe languages", because Rust is currently vulnerable to the same attack: https://github.com/rust-lang/rust/issues/16012 https://github.com/rust-lang/rust/issues/16012 It looks like the fix is going to involve adding some code to LLVM to probe each stack page when you make a large stack allocation, but once that happens, it's straightforward for clang to implement -fstack-check for C and C++ programs, too. This is a weird emergent problem from the fact that stack and heap memory are part of the same address space and that the stack is designed to implicitly grow as needed. It's not clear that it's a language or compiler's fault for relying on the stack doing that, nor that it's the platform or kernel's fault for making that approach possible. I'm not totally sure how you would design a language so that you don't have this problem. I guess you could forbid a function from using more than some small amount of stack, and make sure your stack guard area is at least that big, but that seems like an unfortunate restriction. Maybe something like the Stackless Python approach, where all variables are heap-allocated, would work? Also, all that said, note that Windows gets this right: MSVC inserts calls to _chkstk() to do stack probing. I believe this entire class of vulnerability doesn't exist on Windows, and probably some people at MS who spend their entire lives in memory-unsafe languages are feeling very smug today.
- pcwalton 9y ago
  I'm working on it in Rust right now. Hopefully should have a patch up today.
  - kibwen 9y ago
    No way. If so: be still, my heart. Been waiting for LLVM support for this for ages.
  - pcwalton 9y ago
    Patches ready. Waiting on reviews. https://reviews.llvm.org/D34386 https://reviews.llvm.org/D34386 https://reviews.llvm.org/D34387 https://reviews.llvm.org/D34387
clarry 9y ago
You're really barking at the wrong tree here. The user of the memory-unsafe language isn't at fault here for doing things the implementation will utilize stack for. The language specification -- the contract between him and the implementation, never stated or implied that he is responsible for making sure that these objects on stack aren't accessed in larger than page sized increments. The word "stack" never appears in the C specification. At a source level, these programs may as well be 100% bug free. This is nothing more than a quirk of implementation. And one that affects all languages that use the stack (and by which I mean the stack, not some heap-allocated structure the language provides stack-like operations on). Memory safety doesn't really enter the picture.
e12e 9y ago
The design might be fundamentally broken, but if so you're saying that even with an mmu, we can only have co-operative multitasking. That's not the promise of a multi-user/multi-prosess system. If "all programs are safe", we could just use the Amiga OS kernel and no longer need an mmu, or a similar design. [ed: apparently windows NT takes steps to avoid this according to a sibling comment. Not clear, but I assume it implies a performance hit for certain heavy stack usage?]
- clarry 9y ago
  There would be a performance hit, but that is likely to be insignificant. Apparently the stack check code touches every stack page. If performance were a concern (and I don't really think it is), it should be possible to reduce the impact by assuming a sufficiently large stack guard that the majority of functions with fixed size stack frames could never leap over. Then these functions wouldn't need any runtime checks. The only checking you'd have to do is on code that uses VLAs, alloca, or such, along with the few outlier functions that use ridiculously large fixed size buffers. I don't see why you should need to touch every page.
- geofft 9y ago
  I don't entirely follow what you're saying in your first sentence, but I'm going to try to respond to what I think you're saying. If I'm off base please let me know! 1. Memory-safe languages are about making sure that the programmer's intended behavior matches the actual behavior, that is, eliminating a class of bugs related to memory unsafety. They are a security scheme insofar as these bugs are security bugs, but they're not an interprocess security scheme. In particular, you can write a memory-safe debugger that goes and makes arbitrary modifications to other processes the OS gives it access to. You can even write a memory-safe program in Rust that goes and edits /proc/self/mem. But in these cases, the programmer is intending to mess with process memory directly, so the language isn't obligated to stop the programmer. It is obligated to stop the programmer from, say, overflowing a string and overwriting the return address. 2. It is certainly possible to design a memory-safe language that is usable for interprocess memory protection. Microsoft had a research OS called Singularity that did exactly this: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/osr2007_rethinkingsoftwarestack.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... But it's another step on top of memory safety. 3. Preemptive multitasking and protected memory aren't inherently related (although, yes, in the market, most cooperatively multitasked OSes lacked memory protection, and most OSes with memory protections were preemptively multitasked). You can have a preemptively multitasked system with no MMU at all; you just need to respond to timer interrupts and switch tasks.