7 ms·

Your sentence to missing a word. Nonetheless, I agree. Eventually one cannot continue putting blame solely on the proximal cause. It's too bad that given the

Your sentence to missing a word. Nonetheless, I agree. Eventually one cannot continue putting blame solely on the proximal cause. It's too bad that given the number of extensions to x86 there have been, that it still doesn't have anything like native array bounds checking. Even something as simple as "any writes inside the stack outside my stack frame and all reads inside the stack and after my stack frame should assert" (on an opt-in until the next return) would do wonders towards preventing some of these sorts of errors, although not all.

comex 12y ago
Have you heard of MPX? http://en.m.wikipedia.org/wiki/Intel_MPX http://en.m.wikipedia.org/wiki/Intel_MPX
- TheLoneWolfling 12y ago
  Yes I have, but MPX is primarily for a different use case. Also, MPX has performance issues. See [1]. Also, it has false positives (!). Not a good thing. [1]https://code.google.com/p/address-sanitizer/wiki/IntelMemoryProtectionExtensions https://code.google.com/p/address-sanitizer/wiki/IntelMemory...
  - comex 12y ago
    Hmm... according to that page, the false positives and performance issues seem to largely derive from using the cache structure to store bounds externally. But if you manage the bounds explicitly as part of your data structures, and use BNDMOV/BNDMK rather than BND{ST,LD}X, it should be reasonably fast. What else could Intel do?
    - TheLoneWolfling 12y ago
      Have a read of the linked page again. A large chunk of the performance issues are because in many cases you can't just "use BNDMOV/BNDMK rather than BND{ST,LD}X". There are a number of data structures where managing bounds explicitly has... issues. Namely, you end up with a lot of overhead. And the entire purpose of hardware support is to prevent the overhead. Something like, as I said, an opt-in assert when you read past the end of your stack frame, or write before or after your stack frame, doesn't have the overhead. It doesn't prevent a lot of things - about the only thing it prevents is stack smashing - but it's better than nothing and doesn't have the overhead.
      - comex 12y ago
        That will only work for direct writes to array variables on the stack, or pointers which can be proved to live on the current stack frame, but those are quite rare; e.g. in the vulnerability mentioned in the post, it's sprintf doing the overflowing write into its parent stack frame, but sprintf could be called with any pointer. If, say, you narrow the trapping region to some unused region of the stack frame to try to avoid this, you can get slightly better protection than a stack canary, but not much better. And most overflow vulnerabilities in modern software seem to be on the heap anyway.* (Which is not to say primitives based on fine-grained tagged memory couldn't do some interesting things; OpenRISC has some form of this, but I haven't looked into it in detail.) I don't see content on the linked page corresponding to data structures where managing bounds explicitly is difficult, other than the bnd_variable_size bit, which is described as rare. *corrected to state that I'm only considering overflows, not, e.g., use-after-frees, which aren't related to bounds checks
userbinator 12y ago
It's too bad that given the number of extensions to x86 there have been, that it still doesn't have anything like native array bounds checking It's called the BOUND instruction, and has been there since the 80186/188: http://en.wikipedia.org/wiki/X86_instruction_listings#Added_with_80186.2F80188 http://en.wikipedia.org/wiki/X86_instruction_listings#Added_... Ironically, AMD removed it in AMD64 and Intel followed them, but it's still there in 32-bit mode.
- stassats 12y ago
  Because individual instructions doing the same thing are faster. Though it's especially slow because it's microcoded and is left just for backwards compatibility and not trying to be fast. So modern CPUs are good at reordering, predicting branches, etc., for simple instructions and no extra silicon needs to be wasted to duplicate that. And encoding space is limited as well.
  - userbinator 12y ago
    If individual instructions are faster, that means the instruction decoder isn't as good as it should be. BOUND wasn't fast because it didn't get any use, and it didn't get any use because people thought it was slow... but now that the usefulness of this instruction is apparent, it seems to me that they should make the decoder issue the necessary uops and make it at least as fast as the (bigger, more cache-wasting) sequence of simpler instructions. Instructions like MOVS and STOS used to be slower than the equivalent series of simple instructions, but now they're much faster. Even the more obscure and far less useful BCD arithmetic instructions have been made on-par with a longer series of equivalent instructions[1] so not doing the same for the much more useful BOUND is... unusual. The amount of silicon needed to implement MPX (which includes several new instructions) seems far more than it'd take to make a BOUND decode faster. [1] https://news.ycombinator.com/item?id=8477585 https://news.ycombinator.com/item?id=8477585
    - dfox 12y ago
      BOUND didn't get much of an use because it is useful only for bounds checking of the "dump core if outside" kind.
simonster 12y ago
On 32-bit x86, you could use segment registers to get bounds checking with overhead only at setup and not at use, effectively making bounds checks free in hot loops (http://www.blackhat.com/presentations/bh-usa-05/BH_US_05-Chiueh.pdf http://www.blackhat.com/presentations/bh-usa-05/BH_US_05-Chi...). I believe that SpiderMonkey uses this trick. Doesn't work on x86-64 though.
asveikau 12y ago
I feel like this suggestion is a little misplaced. To use a scheme like this you must ultimately tell the hardware what the bounds are, and that layer is going to be error prone in the same ways as what it replaces. From this vantage point I can say the abstraction that already exists for this is the page table. The MMU knows what regions are mapped and it will generate a fault for an out of bounds access. But within mapped regions the array bounds are all fiction. As they should be in the eyes of the hardware. That is for higher level layers to worry about. I feel like the c-haters don't get that some layer of the system must work this way. By all means build your higher level stuff on top. But things like virtual memory and allocators are well understood, frankly when it gets to that level there is little reason for it to give a damn that a[] has an element count of 5. At some point something must chop up larger blocks into smaller ones, and create new bounds from nothing.
- zurn 12y ago
  This would require using zillions of VM areas for all your language level objects, and aligning them on page boundaries. It's really not going to work. Have a look at SoftBound and HardBound for some of the current thinking in this area that scales to object level granularity.
  - asveikau 12y ago
    I think you misunderstand me. I am advocating the status quo, not for more granular pages. Anyway from what I have seen some high level languages are actually using the MMU for some things. For example, a null check at every access would be kind of lame, from what I have seen high level language runtimes just let it fault on the zero page and handle it by raising exceptions. (I am 100% sure CLR does this, I believe JVM does too.)

comex 12y ago

Have you heard of MPX? http://en.m.wikipedia.org/wiki/Intel_MPX http://en.m.wikipedia.org/wiki/Intel_MPX

TheLoneWolfling 12y ago
Yes I have, but MPX is primarily for a different use case. Also, MPX has performance issues. See [1]. Also, it has false positives (!). Not a good thing. [1]https://code.google.com/p/address-sanitizer/wiki/IntelMemoryProtectionExtensions https://code.google.com/p/address-sanitizer/wiki/IntelMemory...
- comex 12y ago
  Hmm... according to that page, the false positives and performance issues seem to largely derive from using the cache structure to store bounds externally. But if you manage the bounds explicitly as part of your data structures, and use BNDMOV/BNDMK rather than BND{ST,LD}X, it should be reasonably fast. What else could Intel do?
  - TheLoneWolfling 12y ago
    Have a read of the linked page again. A large chunk of the performance issues are because in many cases you can't just "use BNDMOV/BNDMK rather than BND{ST,LD}X". There are a number of data structures where managing bounds explicitly has... issues. Namely, you end up with a lot of overhead. And the entire purpose of hardware support is to prevent the overhead. Something like, as I said, an opt-in assert when you read past the end of your stack frame, or write before or after your stack frame, doesn't have the overhead. It doesn't prevent a lot of things - about the only thing it prevents is stack smashing - but it's better than nothing and doesn't have the overhead.
    - comex 12y ago
      That will only work for direct writes to array variables on the stack, or pointers which can be proved to live on the current stack frame, but those are quite rare; e.g. in the vulnerability mentioned in the post, it's sprintf doing the overflowing write into its parent stack frame, but sprintf could be called with any pointer. If, say, you narrow the trapping region to some unused region of the stack frame to try to avoid this, you can get slightly better protection than a stack canary, but not much better. And most overflow vulnerabilities in modern software seem to be on the heap anyway.* (Which is not to say primitives based on fine-grained tagged memory couldn't do some interesting things; OpenRISC has some form of this, but I haven't looked into it in detail.) I don't see content on the linked page corresponding to data structures where managing bounds explicitly is difficult, other than the bnd_variable_size bit, which is described as rare. *corrected to state that I'm only considering overflows, not, e.g., use-after-frees, which aren't related to bounds checks

userbinator 12y ago

It's too bad that given the number of extensions to x86 there have been, that it still doesn't have anything like native array bounds checking It's called the BOUND instruction, and has been there since the 80186/188: http://en.wikipedia.org/wiki/X86_instruction_listings#Added_with_80186.2F80188 http://en.wikipedia.org/wiki/X86_instruction_listings#Added_... Ironically, AMD removed it in AMD64 and Intel followed them, but it's still there in 32-bit mode.

stassats 12y ago
Because individual instructions doing the same thing are faster. Though it's especially slow because it's microcoded and is left just for backwards compatibility and not trying to be fast. So modern CPUs are good at reordering, predicting branches, etc., for simple instructions and no extra silicon needs to be wasted to duplicate that. And encoding space is limited as well.
- userbinator 12y ago
  If individual instructions are faster, that means the instruction decoder isn't as good as it should be. BOUND wasn't fast because it didn't get any use, and it didn't get any use because people thought it was slow... but now that the usefulness of this instruction is apparent, it seems to me that they should make the decoder issue the necessary uops and make it at least as fast as the (bigger, more cache-wasting) sequence of simpler instructions. Instructions like MOVS and STOS used to be slower than the equivalent series of simple instructions, but now they're much faster. Even the more obscure and far less useful BCD arithmetic instructions have been made on-par with a longer series of equivalent instructions[1] so not doing the same for the much more useful BOUND is... unusual. The amount of silicon needed to implement MPX (which includes several new instructions) seems far more than it'd take to make a BOUND decode faster. [1] https://news.ycombinator.com/item?id=8477585 https://news.ycombinator.com/item?id=8477585
  - dfox 12y ago
    BOUND didn't get much of an use because it is useful only for bounds checking of the "dump core if outside" kind.

simonster 12y ago

On 32-bit x86, you could use segment registers to get bounds checking with overhead only at setup and not at use, effectively making bounds checks free in hot loops (http://www.blackhat.com/presentations/bh-usa-05/BH_US_05-Chiueh.pdf http://www.blackhat.com/presentations/bh-usa-05/BH_US_05-Chi...). I believe that SpiderMonkey uses this trick. Doesn't work on x86-64 though.

asveikau 12y ago

I feel like this suggestion is a little misplaced. To use a scheme like this you must ultimately tell the hardware what the bounds are, and that layer is going to be error prone in the same ways as what it replaces. From this vantage point I can say the abstraction that already exists for this is the page table. The MMU knows what regions are mapped and it will generate a fault for an out of bounds access. But within mapped regions the array bounds are all fiction. As they should be in the eyes of the hardware. That is for higher level layers to worry about. I feel like the c-haters don't get that some layer of the system must work this way. By all means build your higher level stuff on top. But things like virtual memory and allocators are well understood, frankly when it gets to that level there is little reason for it to give a damn that a[] has an element count of 5. At some point something must chop up larger blocks into smaller ones, and create new bounds from nothing.

zurn 12y ago
This would require using zillions of VM areas for all your language level objects, and aligning them on page boundaries. It's really not going to work. Have a look at SoftBound and HardBound for some of the current thinking in this area that scales to object level granularity.
- asveikau 12y ago
  I think you misunderstand me. I am advocating the status quo, not for more granular pages. Anyway from what I have seen some high level languages are actually using the MMU for some things. For example, a null check at every access would be kind of lame, from what I have seen high level language runtimes just let it fault on the zero page and handle it by raising exceptions. (I am 100% sure CLR does this, I believe JVM does too.)