9 ms·

What you get is what you C: Controlling side effects in mainstream C compilers [pdf]

95 points by gbrown_ 9y ago

lisper 9y ago
> For example, divisions by zero are considered UB [undefined behavior], so a compiler can assume the divisor is always non-zero (Chapter 6.5.5). This means code that checks the value of the divisor prior to a division can be removed by a compiler C's "undefined behavior" rules are insanity of the highest order, bordering on professional malpractice. They are the result of the pursuit of speed at the expense of all else. This might have been acceptable in 1973. It should not even be contemplated in 2018.
- Avshalom 9y ago
  not just speed but "portable assembly" if architectures get to decide what to do on ÷0 then by golly so does a C compiler (never mind that those differences make C less portable).
- moefh 9y ago
  I don't disagree, but I feel "code that checks the value of the divisor prior to a division can be removed by a compiler" needs clarification: it's not as insane as it sounds. The example given in the referenced paper[1] for this is: if (arg2 == 0) ereport(/* ... */); PG_RETURN_INT32((int32) arg1 / arg2); The compiler re-ordered the instructions and performed the division before the check, but only because it didn't know "ereport()" couldn't return (so the compiler thought the division would happen either way). If the code had been: if (arg2 != 0) PG_RETURN_INT32((int32) arg1 / arg2); ereport(/* ... */); or something like it, it would have been fine. [1] https://people.csail.mit.edu/nickolai/papers/wang-undef-2012-08-21.pdf https://people.csail.mit.edu/nickolai/papers/wang-undef-2012...
  - radford-neal 9y ago
    I think that's just a compiler bug.
    - moefh 9y ago
      Nah, it's a valid optimization as long as ereport() returns. The compiler doesn't need to follow the order of operations as long as the observed behavior is the same as if the operations were performed in the order in the code. Since the compiler doesn't have any responsibility if division by zero happens, it's fine to do the division before. This is an interesting read: https://blogs.msdn.microsoft.com/oldnewthing/20140627-00/?p=633 https://blogs.msdn.microsoft.com/oldnewthing/20140627-00/?p=...
      - Asooka 9y ago
        It is a compiler bug. The compiler can't reason what the effect of dividing by zero will be, because it's undefined. Therefore, hoisting the division before the if can change the observed behaviour, because the ereport function won't be executed. Ereport may not return, or it may print a debug message, or any other manner of things that are absolutely observable program behaviour. The function should be compiled with whatever division opcode or subroutine the compiler likes, including ones that crash the program, make it loop forever, make your cpu explode, or launch nukes at North Korea, however - it cannot reorder the function call after the division, because if it crashes, the program behaviour changes.
        lisper 9y ago
        > it cannot reorder the function call after the division Actually, it can because one of the things undefined behavior can do is go backwards in time. Undefined behavior anywhere in the program can legally make any part of the program do anything at any time. On top of that, there is no reliable way to tell if your program contains undefined behavior. This is madness.
        nickpsecurity 9y ago
        On that last point, check out Rosu et al's KCC: an executable, formal semantics of C that addresses undefined behavior. https://github.com/kframework/c-semantics/blob/master/README.md https://github.com/kframework/c-semantics/blob/master/README...
- radford-neal 9y ago
  Undefined behaviour can be tricky, but I don't think it is THAT tricky. If a check for a divisor of zero done before a division could be eliminated, programming would become completely impossible. On the other hand, code that does the division first, and AFTER that checks whether the divisor was zero, could fall prey to the dreaded undefined behaviour optimization...
- saagarjha 9y ago
  Please read this: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
  - lisper 9y ago
    OK, what lesson exactly am I supposed to take away from this? Because the last sentence in that post is exactly my point: "... undefined behavior in C is a pretty scary thing if performance is not your only goal."
    - saagarjha 9y ago
      You mentioned this: > C's "undefined behavior" rules are insanity of the highest order, bordering on professional malpractice. They are the result of the pursuit of speed at the expense of all else. C's goal is performance (though not necessarily at the expense of all else). It's the compiler's job to make code that is as fast as possible. The article I linked was an attempt to show that it is very difficult to both have this goal as well as one in which you don't have "insane" undefined behavior. It's not that the C compiler authors are out to get you: "ha ha, lipser used undefined behavior! Let's break his code in the weirdest way"; rather, this seemingly poor behavior is borne out of a desire to have reasonable rules. Allowing the compiler to assume that a run runs ten times or that a pointer doesn't randomly change between statements is important.
      - loup-vaillant 9y ago
        > It's the compiler's job to make code that is as fast as possible. This doesn't used to be the case, or we would have had something more like FORTRAN, with less pointers that alias all over the place. C was build so the programmer could optimise the program. The design of C was pretty hostile to compiler optimisations, to the point that some PL researchers say its wide adoption set us back decades. It's only later that compilers started to really optimise stuff themselves. And they used undefined behaviour to do so. Signed integer overflow UB for instance was used to optimised `for` loops, thus compensating the verbose, hard to optimise original design. > It's not that the C compiler authors are out to get you The end result is the same. "Oh, this code leads to undefined behaviour. Let's pretend it's dead, it will be faster that way". Apply that to reasonable looking, yet incorrect, safety checks (like checking for integer overflow after the fact), and just like that you have a buffer overflow and an arbitrary code execution exploit.
- ychen306 9y ago
  I agree with you. But this quote is badly written by the author -- they should have clarified further. In fact, compilers don't remove check of divisors that prevents div-by-0 precisely for this reason. What the authors mean is someting like this: >if (!msize) msize = 1 / msize; // provoke a signal
- mpweiher 9y ago
  > insanity of the highest order, bordering on professional malpractice. Hear, hear! > might have been acceptable in 1973 The irony being that compilers in, well, 1983-ish did not pull these kinds of stunts.
  - pjmlp 9y ago
    Well, C compilers required some ways to catch up with optimizers in other programming languages with better type information, as Fran Allen complained a few times.
- montrose 9y ago
  Surely there are still applications in 2018 that require speed at the expense of all else. Perhaps not as many, but there are bound to be some.
  - lisper 9y ago
    Like what? Seriously... what do you want to run for which you would be willing to risk data corruption, or a hacker pwning your machine, in exchange for it running faster? Because that's what we're really talking about here.
faragon 9y ago
On x86 CPUs, working with latest compilers in -O3 optimization level is becoming like working with old RISC CPUs without hardware for unaligned load/store: except if you write your code using memcpy/memmove for unaligned load/store, you'll get caught by some crash. E.g. in x86-64 in -O3 GCC emits SIMD instructions that can crash your code if not properly aligned. E.g. the typical cast to 32 or 64 bit that worked in C on x86 processors, is no longer guaranteed to work: uint8_t * p = some_address_not_aligned; uint32_t i = * (uint32_t *)p; In order to be safe previous code should be replaced by: memcpy(&i, p, sizeof(uint32_t)); (the compiler is smart enough for inlining the above memcpy call, so is as fast as the previous case)
- Kenji 9y ago
  E.g. the typical cast to 32 or 64 bit that worked in C on x86 processors, is no longer guaranteed to work: Sorry to disappoint you, but this fragment of code was never guaranteed to work by the C standard, and x86 is a special case where it might work (but is not guaranteed to!). I hope you didn't make such type punning mistakes in the code you've written so far. A memcpy is always necessary to transform 4 bytes in an (unaligned) char array into a 32-bit integer. And yes, it all gets optimised away. At the end of the day, if you do it with memcpy, you end up with literally the same assembly as when you use a type cast, at least on GCC last time I tried. Still, it's good to not cause undefined behaviour.
  - saagarjha 9y ago
    I don't know why this comment was killed: it's correct. The code above violates the C standard, so you're luckily that it even crashes at all rather than doing something even worse like masking to a 4-byte boundary.
  - faragon 9y ago
    "was never guaranteed to work by the C standard" It was, on x86, before of compilers emitting opcodes not supporting unaligned memory accesses, because x86 CPUs guaranteed safe operation on unaligned memory accesses. Don't get me wrong, of course it is a good practice writing code not relying on CPU-specific characteristics. The problem is that there is a ton of software for x86 that becomes not reliable when recompiled with -O3 on x86-64 (with hard to catch situations, e.g. passing tests, but with random crashes depending on the data being handled, etc.).
zokier 9y ago
This is great stuff; if I were ever to write a language this sort of side-effect control is something I would like to include. That being said, I'm bit surprised how much effort developers put into "tricking" C compilers; one would think that writing pieces of (inline) assembly would provide the desired effect while being both easier and more robust. At least it feels like in many cases the developers have some idea on what the desired code is. Maybe there are some subtleties that I am missing?
- krupan 9y ago
  Assembly is not portable.
  - nine_k 9y ago
    Are the tricks portable?
    - quacker 9y ago
      "portable" in the sense that the compiler will produce the proper assembly for the platform - choice of x86, ARM, MIPS, 32/64 bit, etc. Whether the "tricks" behave identically across all platforms depends on the trick, I think.
      - pjmlp 9y ago
        Usually those tricks are not even portable across compilers on the same platform. It suffices a change on compiler version with optimizer improvements, or using another vendor's compiler for the tricks to fall apart. In a gigantic code base, with rotating developers, it becomes a very "fun" thing to debug.
        coldtea 9y ago
        >Usually those tricks are not even portable across compilers on the same platform. That's much less of an issue. If it can work on GCC for example or Clang across platforms, you're OK for tons of platforms, even if you can't change compilers intra-platform.
DC-3 9y ago
Would be interesting to see this applied to Rust. Obviously physical side-effect attacks (timing, EM) are still a concern and LLVM optimisations need to be considered as with the Clang toolchain, but massive swathes of UB are eliminated when compared to C.

95 points by gbrown_ 9y ago

> For example, divisions by zero are considered UB [undefined behavior], so a compiler can assume the divisor is always non-zero (Chapter 6.5.5). This means code that checks the value of the divisor prior to a division can be removed by a compiler C's "undefined behavior" rules are insanity of the highest order, bordering on professional malpractice. They are the result of the pursuit of speed at the expense of all else. This might have been acceptable in 1973. It should not even be contemplated in 2018.

Avshalom 9y ago
not just speed but "portable assembly" if architectures get to decide what to do on ÷0 then by golly so does a C compiler (never mind that those differences make C less portable).
moefh 9y ago
I don't disagree, but I feel "code that checks the value of the divisor prior to a division can be removed by a compiler" needs clarification: it's not as insane as it sounds. The example given in the referenced paper[1] for this is: if (arg2 == 0) ereport(/* ... */); PG_RETURN_INT32((int32) arg1 / arg2); The compiler re-ordered the instructions and performed the division before the check, but only because it didn't know "ereport()" couldn't return (so the compiler thought the division would happen either way). If the code had been: if (arg2 != 0) PG_RETURN_INT32((int32) arg1 / arg2); ereport(/* ... */); or something like it, it would have been fine. [1] https://people.csail.mit.edu/nickolai/papers/wang-undef-2012-08-21.pdf https://people.csail.mit.edu/nickolai/papers/wang-undef-2012...
- radford-neal 9y ago
  I think that's just a compiler bug.
  - moefh 9y ago
    Nah, it's a valid optimization as long as ereport() returns. The compiler doesn't need to follow the order of operations as long as the observed behavior is the same as if the operations were performed in the order in the code. Since the compiler doesn't have any responsibility if division by zero happens, it's fine to do the division before. This is an interesting read: https://blogs.msdn.microsoft.com/oldnewthing/20140627-00/?p=633 https://blogs.msdn.microsoft.com/oldnewthing/20140627-00/?p=...
    - Asooka 9y ago
      It is a compiler bug. The compiler can't reason what the effect of dividing by zero will be, because it's undefined. Therefore, hoisting the division before the if can change the observed behaviour, because the ereport function won't be executed. Ereport may not return, or it may print a debug message, or any other manner of things that are absolutely observable program behaviour. The function should be compiled with whatever division opcode or subroutine the compiler likes, including ones that crash the program, make it loop forever, make your cpu explode, or launch nukes at North Korea, however - it cannot reorder the function call after the division, because if it crashes, the program behaviour changes.
      - lisper 9y ago
        > it cannot reorder the function call after the division Actually, it can because one of the things undefined behavior can do is go backwards in time. Undefined behavior anywhere in the program can legally make any part of the program do anything at any time. On top of that, there is no reliable way to tell if your program contains undefined behavior. This is madness.
        nickpsecurity 9y ago
        On that last point, check out Rosu et al's KCC: an executable, formal semantics of C that addresses undefined behavior. https://github.com/kframework/c-semantics/blob/master/README.md https://github.com/kframework/c-semantics/blob/master/README...
radford-neal 9y ago
Undefined behaviour can be tricky, but I don't think it is THAT tricky. If a check for a divisor of zero done before a division could be eliminated, programming would become completely impossible. On the other hand, code that does the division first, and AFTER that checks whether the divisor was zero, could fall prey to the dreaded undefined behaviour optimization...
saagarjha 9y ago
Please read this: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
- lisper 9y ago
  OK, what lesson exactly am I supposed to take away from this? Because the last sentence in that post is exactly my point: "... undefined behavior in C is a pretty scary thing if performance is not your only goal."
  - saagarjha 9y ago
    You mentioned this: > C's "undefined behavior" rules are insanity of the highest order, bordering on professional malpractice. They are the result of the pursuit of speed at the expense of all else. C's goal is performance (though not necessarily at the expense of all else). It's the compiler's job to make code that is as fast as possible. The article I linked was an attempt to show that it is very difficult to both have this goal as well as one in which you don't have "insane" undefined behavior. It's not that the C compiler authors are out to get you: "ha ha, lipser used undefined behavior! Let's break his code in the weirdest way"; rather, this seemingly poor behavior is borne out of a desire to have reasonable rules. Allowing the compiler to assume that a run runs ten times or that a pointer doesn't randomly change between statements is important.
    - loup-vaillant 9y ago
      > It's the compiler's job to make code that is as fast as possible. This doesn't used to be the case, or we would have had something more like FORTRAN, with less pointers that alias all over the place. C was build so the programmer could optimise the program. The design of C was pretty hostile to compiler optimisations, to the point that some PL researchers say its wide adoption set us back decades. It's only later that compilers started to really optimise stuff themselves. And they used undefined behaviour to do so. Signed integer overflow UB for instance was used to optimised `for` loops, thus compensating the verbose, hard to optimise original design. > It's not that the C compiler authors are out to get you The end result is the same. "Oh, this code leads to undefined behaviour. Let's pretend it's dead, it will be faster that way". Apply that to reasonable looking, yet incorrect, safety checks (like checking for integer overflow after the fact), and just like that you have a buffer overflow and an arbitrary code execution exploit.
ychen306 9y ago
I agree with you. But this quote is badly written by the author -- they should have clarified further. In fact, compilers don't remove check of divisors that prevents div-by-0 precisely for this reason. What the authors mean is someting like this: >if (!msize) msize = 1 / msize; // provoke a signal
mpweiher 9y ago
> insanity of the highest order, bordering on professional malpractice. Hear, hear! > might have been acceptable in 1973 The irony being that compilers in, well, 1983-ish did not pull these kinds of stunts.
- pjmlp 9y ago
  Well, C compilers required some ways to catch up with optimizers in other programming languages with better type information, as Fran Allen complained a few times.
montrose 9y ago
Surely there are still applications in 2018 that require speed at the expense of all else. Perhaps not as many, but there are bound to be some.
- lisper 9y ago
  Like what? Seriously... what do you want to run for which you would be willing to risk data corruption, or a hacker pwning your machine, in exchange for it running faster? Because that's what we're really talking about here.

faragon 9y ago

On x86 CPUs, working with latest compilers in -O3 optimization level is becoming like working with old RISC CPUs without hardware for unaligned load/store: except if you write your code using memcpy/memmove for unaligned load/store, you'll get caught by some crash. E.g. in x86-64 in -O3 GCC emits SIMD instructions that can crash your code if not properly aligned. E.g. the typical cast to 32 or 64 bit that worked in C on x86 processors, is no longer guaranteed to work: uint8_t * p = some_address_not_aligned; uint32_t i = * (uint32_t *)p; In order to be safe previous code should be replaced by: memcpy(&i, p, sizeof(uint32_t)); (the compiler is smart enough for inlining the above memcpy call, so is as fast as the previous case)

Kenji 9y ago
E.g. the typical cast to 32 or 64 bit that worked in C on x86 processors, is no longer guaranteed to work: Sorry to disappoint you, but this fragment of code was never guaranteed to work by the C standard, and x86 is a special case where it might work (but is not guaranteed to!). I hope you didn't make such type punning mistakes in the code you've written so far. A memcpy is always necessary to transform 4 bytes in an (unaligned) char array into a 32-bit integer. And yes, it all gets optimised away. At the end of the day, if you do it with memcpy, you end up with literally the same assembly as when you use a type cast, at least on GCC last time I tried. Still, it's good to not cause undefined behaviour.
- saagarjha 9y ago
  I don't know why this comment was killed: it's correct. The code above violates the C standard, so you're luckily that it even crashes at all rather than doing something even worse like masking to a 4-byte boundary.
- faragon 9y ago
  "was never guaranteed to work by the C standard" It was, on x86, before of compilers emitting opcodes not supporting unaligned memory accesses, because x86 CPUs guaranteed safe operation on unaligned memory accesses. Don't get me wrong, of course it is a good practice writing code not relying on CPU-specific characteristics. The problem is that there is a ton of software for x86 that becomes not reliable when recompiled with -O3 on x86-64 (with hard to catch situations, e.g. passing tests, but with random crashes depending on the data being handled, etc.).

zokier 9y ago

This is great stuff; if I were ever to write a language this sort of side-effect control is something I would like to include. That being said, I'm bit surprised how much effort developers put into "tricking" C compilers; one would think that writing pieces of (inline) assembly would provide the desired effect while being both easier and more robust. At least it feels like in many cases the developers have some idea on what the desired code is. Maybe there are some subtleties that I am missing?

krupan 9y ago
Assembly is not portable.
- nine_k 9y ago
  Are the tricks portable?
  - quacker 9y ago
    "portable" in the sense that the compiler will produce the proper assembly for the platform - choice of x86, ARM, MIPS, 32/64 bit, etc. Whether the "tricks" behave identically across all platforms depends on the trick, I think.
    - pjmlp 9y ago
      Usually those tricks are not even portable across compilers on the same platform. It suffices a change on compiler version with optimizer improvements, or using another vendor's compiler for the tricks to fall apart. In a gigantic code base, with rotating developers, it becomes a very "fun" thing to debug.
      - coldtea 9y ago
        >Usually those tricks are not even portable across compilers on the same platform. That's much less of an issue. If it can work on GCC for example or Clang across platforms, you're OK for tons of platforms, even if you can't change compilers intra-platform.

DC-3 9y ago

Would be interesting to see this applied to Rust. Obviously physical side-effect attacks (timing, EM) are still a concern and LLVM optimisations need to be considered as with the Clang toolchain, but massive swathes of UB are eliminated when compared to C.