6 ms·

" Claim that all we need is for some particular "undefined"-catching tool to be widely used. In fact, these tools are full of false positives and false negative

" Claim that all we need is for some particular "undefined"-catching tool to be widely used. In fact, these tools are full of false positives and false negatives; at best they catch a few limited types of "undefined" behavior, not changing the big picture." Question: why can't existing C compilers clearly indicate when they encounter undefined behavior?

pdkl95 11y ago
While it is possible (in theory) to catch some types of undefined behavior, some of it can be very subtle, and it shows up in the C Standard far more often than most people think. https://www.securecoding.cert.org/confluence/display/c/CC.+Undefined+Behavior#CC.UndefinedBehavior-ub_1 https://www.securecoding.cert.org/confluence/display/c/CC.+U...
MereInterest 11y ago
Undefined behavior is primarily something that that has effects, rather than at compile time. For example, taking the value of an uninitialized local variable. int main() { int i; if(some_big_complicated_function()){ i = 0; } printf("%d\n",i); } Is this undefined behavior? The compiler can't be sure, because it can't know whether `some_big_complicated_function()` returns true or not. Therefore, it would need to be a runtime check, rather than a compile time check. But runtime checks are expensive, and so it typically isn't done. It would be entirely allowed by the standard to give such a warning at runtime, but the resulting program would go much, much slower due to all the checks.
- sz4kerto 11y ago
  This would certainly worth a warning (at some warning level) exactly because what you say -- the compiler is not sure that the behavior is fully defined.
  - MereInterest 11y ago
    I wasn't sure whether or not it would print out a warning, so I tested it. With g++ 4.8.4, there is no warning printed, even with `-Wall -Wextra -pedantic`.
- AnimalMuppet 11y ago
  But at compile time you can definitely say "This may be a problem."
- bmm6o 11y ago
  What you say is true, but this case could easily trigger a warning about possible use before assignment. The compiler doesn't have (and can't) to prove that either branch will always be taken at runtime. And there's no benefit to code like this anyway, just write it so it's obviously to be assigned. Your coworkers will thank you.
  - MereInterest 11y ago
    I completely agree. I was, instead, trying to give an example of why a compiler can't just "detect undefined behavior" as the grandparent suggested.
  - bmm6o 11y ago
    And really, the main benefit to not assigning a value in the declaration is to get the compiler to tell you if there is a code path that misses an assignment. int i; if (foo || bar) i = 1; else if (baz) { if (!quux) goto fail; i = 2; } printf("%d", i); // not all code paths assign a value
- pdkl95 11y ago
  That's shoddy programming - it obviously contains an error. As someone who compiles with "-Wall -Wextra -Werror", I believe that this example program shouldn't even be allowed to compile, even though the standard allows it. The variable should really be initialized explicitly, which shouldn't be expensive at runtime. int i = 1; /* or whatever */ Alternately, if the programmer intended to only print when some_big_complicated_function() return true - which is a strong possibility because they only wrote a value to "i" for that case - then the bug is in the position of the printf and possibly the variable definition, if you're using >=C99. #include <stdlib.h> #include <stdio.h> int some_big_complicated_function(void); int main() { if (some_big_complicated_function()) { int i = 0; printf("%d\n", i); } return EXIT_SUCCESS; } > the resulting program would go much, much slower due to all the checks. That depends on a lot. It can be (very) significant if you're talking about the middle of a hot loop; in the given example that runs once per main(), the difference is negligible. For better examples and a discussion of why it can be very hard to issue useful warnings when optimizing around undefined behavior, see LLVM's series of articles that should is mandatory reading for anybody working with C/C++. 1/3 - http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-... 2/3 - http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-... 3/3 - http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
VLM 11y ago
Undefined behavior is the end result of conflicting standards; the usual human response to a pile of confusing standards is making yet another new, soon to be confusing, standard, see XKCD for the graphical interpretation. And that new standard both contains new undefinitions and via its impact against existing standards creates who new waves of new undefinitions.
twoodfin 11y ago
Modern compilers/analyzers can and will report whatever statically detectable UB they can, but most interesting cases are triggered dynamically. e.g.: int data[64]; int foo(int bar) { return data[bar]; } If foo() has external linkage, how does the compiler ensure it's never called with a value <0 or >63? And that's an easy case. clang/llvm can instrument code to detect some forms of UB and trigger a diagnostic at runtime, but these checks can be expensive (and you still have a runtime failure, rather than a compile time detection).
- captainmuon 11y ago
  Well, there is undefined behavior like this, and there is other undefined behavior. In this case, there is a semi-sensible thing the code could do: if you ask for foo(66), return the data at 2*sizeof(int) beyond the end of `data`. If that region of memory is protected, print a message and end the program (so, crash). The other situation is when the compiler assumes there is no UB, and applies some optimizations that break code that otherwise did what you wanted it to do. GCC is notorious for implementing a lot of these optimizations, almost out of spite (because you deserve it if you write faulty code...). Aliasing variables/pointers with a different type, reinterpreting memory as a different type (type punning), certain null checks (e.g. if (this == null)), and so on... All of these can be detected at compile time, and there is a sensible "do-as-I-mean" thing that you can do, or a language-lawer unexpected thing (that of course might allow correct programs to be faster).
riscy 11y ago
I believe in many cases in C, you would need to insert runtime checks (and I believe gcc/clang has a flag for inserting these when statically checking for it is infeasible). One such behavior which is considered undefined is signed integer overflow/underflow. Without this being undefined, some important loop optimizations would not be possible [1]. The blog link below has lots of information about undefined behavior from the perspective of a compiler implementer. [1] http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
JoshTriplett 11y ago
[EDIT: more clearly distinguished between undefined and unspecified behavior.] > Question: why can't existing C compilers clearly indicate when they encounter undefined behavior? Why can't existing programs clearly indicate when they encounter unexpected input? Not every instance of undefined behavior has explicit handling in a compiler; sometimes, undefined behavior occurs as part of the implicit functioning of the compiler implementation. The compiler does not need to consider undefined behavior at all. It doesn't necessarily have an explicit case for "undefined, choose a behavior"; it can simply act as though undefined behavior does not exist, and have the behavior in that case depend on whatever the code written to handle defined behavior happens to do in the undefined case. [EDIT: This example is unspecified behavior, not undefined behavior. The example does still illustrate what I meant by behavior that arises out of the compiler implementation without explicit notice by the compiler.] For instance, if you write f(g(), h()), C doesn't specify whether g or h gets called first. The compiler doesn't explicitly parse that whole expression and internally note "oh, you have unspecified behavior here, I'll silently choose an interpretation and not tell you about it". The compiler just parses the expression and breaks it down into sequential operations, implicitly choosing an interpretation based on its parsing, evaluation, and optimization. The compiler might evaluate g() first because it parses left-to-right, or h() first because it parses right-to-left, or h() first because h() was an inline function and it expands those first... A compiler explicitly designed to flag undefined behaviors would need to have additional logic to notice undefined behaviors; you couldn't just take an existing compiler and find all the places where it explicitly notices undefined behavior and chooses a way to handle it. Existing compilers have started to add warnings for cases where they explicitly exploit undefined behavior for optimization, such as assuming a lack of signed overflow, or assuming that you never dereference a NULL pointer. But retrofitting a compiler to flag cases where it currently just doesn't even consider the undefined behavior would require far more work.
- GFK_of_xmaspast 11y ago
  > For instance, if you write f(g(), h()), C doesn't define whether g or h gets called first. That's unSPECIFIED behavior, not unDEFINED behavior. There's a big difference.
dtparr 11y ago
There's a blog post[0] from Chris Lattner from a few years back that touches on this. The summary is: "People often ask why the compiler doesn't produce warnings when it is taking advantage of undefined behavior to do an optimization, since any such case might actually be a bug in the user code. The challenges with this approach are that it is 1) likely to generate far too many warnings to be useful - because these optimizations kick in all the time when there is no bug, 2) it is really tricky to generate these warnings only when people want them, and 3) we have no good way to express (to the user) how a series of optimizations combined to expose the opportunity being optimized." [0] - http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
- mcguire 11y ago
  "it is really tricky to generate these warnings only when people want them" And we're back to Perlis' lollipop.[1] [1] http://www.cs.yale.edu/homes/perlis-alan/quotes.html#93 http://www.cs.yale.edu/homes/perlis-alan/quotes.html#93

pdkl95 11y ago

While it is possible (in theory) to catch some types of undefined behavior, some of it can be very subtle, and it shows up in the C Standard far more often than most people think. https://www.securecoding.cert.org/confluence/display/c/CC.+Undefined+Behavior#CC.UndefinedBehavior-ub_1 https://www.securecoding.cert.org/confluence/display/c/CC.+U...

MereInterest 11y ago

Undefined behavior is primarily something that that has effects, rather than at compile time. For example, taking the value of an uninitialized local variable. int main() { int i; if(some_big_complicated_function()){ i = 0; } printf("%d\n",i); } Is this undefined behavior? The compiler can't be sure, because it can't know whether `some_big_complicated_function()` returns true or not. Therefore, it would need to be a runtime check, rather than a compile time check. But runtime checks are expensive, and so it typically isn't done. It would be entirely allowed by the standard to give such a warning at runtime, but the resulting program would go much, much slower due to all the checks.

sz4kerto 11y ago
This would certainly worth a warning (at some warning level) exactly because what you say -- the compiler is not sure that the behavior is fully defined.
- MereInterest 11y ago
  I wasn't sure whether or not it would print out a warning, so I tested it. With g++ 4.8.4, there is no warning printed, even with `-Wall -Wextra -pedantic`.
AnimalMuppet 11y ago
But at compile time you can definitely say "This may be a problem."
bmm6o 11y ago
What you say is true, but this case could easily trigger a warning about possible use before assignment. The compiler doesn't have (and can't) to prove that either branch will always be taken at runtime. And there's no benefit to code like this anyway, just write it so it's obviously to be assigned. Your coworkers will thank you.
- MereInterest 11y ago
  I completely agree. I was, instead, trying to give an example of why a compiler can't just "detect undefined behavior" as the grandparent suggested.
- bmm6o 11y ago
  And really, the main benefit to not assigning a value in the declaration is to get the compiler to tell you if there is a code path that misses an assignment. int i; if (foo || bar) i = 1; else if (baz) { if (!quux) goto fail; i = 2; } printf("%d", i); // not all code paths assign a value
pdkl95 11y ago
That's shoddy programming - it obviously contains an error. As someone who compiles with "-Wall -Wextra -Werror", I believe that this example program shouldn't even be allowed to compile, even though the standard allows it. The variable should really be initialized explicitly, which shouldn't be expensive at runtime. int i = 1; /* or whatever */ Alternately, if the programmer intended to only print when some_big_complicated_function() return true - which is a strong possibility because they only wrote a value to "i" for that case - then the bug is in the position of the printf and possibly the variable definition, if you're using >=C99. #include <stdlib.h> #include <stdio.h> int some_big_complicated_function(void); int main() { if (some_big_complicated_function()) { int i = 0; printf("%d\n", i); } return EXIT_SUCCESS; } > the resulting program would go much, much slower due to all the checks. That depends on a lot. It can be (very) significant if you're talking about the middle of a hot loop; in the given example that runs once per main(), the difference is negligible. For better examples and a discussion of why it can be very hard to issue useful warnings when optimizing around undefined behavior, see LLVM's series of articles that should is mandatory reading for anybody working with C/C++. 1/3 - http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-... 2/3 - http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-... 3/3 - http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-...

VLM 11y ago

Undefined behavior is the end result of conflicting standards; the usual human response to a pile of confusing standards is making yet another new, soon to be confusing, standard, see XKCD for the graphical interpretation. And that new standard both contains new undefinitions and via its impact against existing standards creates who new waves of new undefinitions.

twoodfin 11y ago

Modern compilers/analyzers can and will report whatever statically detectable UB they can, but most interesting cases are triggered dynamically. e.g.: int data[64]; int foo(int bar) { return data[bar]; } If foo() has external linkage, how does the compiler ensure it's never called with a value <0 or >63? And that's an easy case. clang/llvm can instrument code to detect some forms of UB and trigger a diagnostic at runtime, but these checks can be expensive (and you still have a runtime failure, rather than a compile time detection).

captainmuon 11y ago
Well, there is undefined behavior like this, and there is other undefined behavior. In this case, there is a semi-sensible thing the code could do: if you ask for foo(66), return the data at 2*sizeof(int) beyond the end of `data`. If that region of memory is protected, print a message and end the program (so, crash). The other situation is when the compiler assumes there is no UB, and applies some optimizations that break code that otherwise did what you wanted it to do. GCC is notorious for implementing a lot of these optimizations, almost out of spite (because you deserve it if you write faulty code...). Aliasing variables/pointers with a different type, reinterpreting memory as a different type (type punning), certain null checks (e.g. if (this == null)), and so on... All of these can be detected at compile time, and there is a sensible "do-as-I-mean" thing that you can do, or a language-lawer unexpected thing (that of course might allow correct programs to be faster).

riscy 11y ago

I believe in many cases in C, you would need to insert runtime checks (and I believe gcc/clang has a flag for inserting these when statically checking for it is infeasible). One such behavior which is considered undefined is signed integer overflow/underflow. Without this being undefined, some important loop optimizations would not be possible [1]. The blog link below has lots of information about undefined behavior from the perspective of a compiler implementer. [1] http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-...

JoshTriplett 11y ago

[EDIT: more clearly distinguished between undefined and unspecified behavior.] > Question: why can't existing C compilers clearly indicate when they encounter undefined behavior? Why can't existing programs clearly indicate when they encounter unexpected input? Not every instance of undefined behavior has explicit handling in a compiler; sometimes, undefined behavior occurs as part of the implicit functioning of the compiler implementation. The compiler does not need to consider undefined behavior at all. It doesn't necessarily have an explicit case for "undefined, choose a behavior"; it can simply act as though undefined behavior does not exist, and have the behavior in that case depend on whatever the code written to handle defined behavior happens to do in the undefined case. [EDIT: This example is unspecified behavior, not undefined behavior. The example does still illustrate what I meant by behavior that arises out of the compiler implementation without explicit notice by the compiler.] For instance, if you write f(g(), h()), C doesn't specify whether g or h gets called first. The compiler doesn't explicitly parse that whole expression and internally note "oh, you have unspecified behavior here, I'll silently choose an interpretation and not tell you about it". The compiler just parses the expression and breaks it down into sequential operations, implicitly choosing an interpretation based on its parsing, evaluation, and optimization. The compiler might evaluate g() first because it parses left-to-right, or h() first because it parses right-to-left, or h() first because h() was an inline function and it expands those first... A compiler explicitly designed to flag undefined behaviors would need to have additional logic to notice undefined behaviors; you couldn't just take an existing compiler and find all the places where it explicitly notices undefined behavior and chooses a way to handle it. Existing compilers have started to add warnings for cases where they explicitly exploit undefined behavior for optimization, such as assuming a lack of signed overflow, or assuming that you never dereference a NULL pointer. But retrofitting a compiler to flag cases where it currently just doesn't even consider the undefined behavior would require far more work.

GFK_of_xmaspast 11y ago
> For instance, if you write f(g(), h()), C doesn't define whether g or h gets called first. That's unSPECIFIED behavior, not unDEFINED behavior. There's a big difference.

dtparr 11y ago

There's a blog post[0] from Chris Lattner from a few years back that touches on this. The summary is: "People often ask why the compiler doesn't produce warnings when it is taking advantage of undefined behavior to do an optimization, since any such case might actually be a bug in the user code. The challenges with this approach are that it is 1) likely to generate far too many warnings to be useful - because these optimizations kick in all the time when there is no bug, 2) it is really tricky to generate these warnings only when people want them, and 3) we have no good way to express (to the user) how a series of optimizations combined to expose the opportunity being optimized." [0] - http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-...

mcguire 11y ago
"it is really tricky to generate these warnings only when people want them" And we're back to Perlis' lollipop.[1] [1] http://www.cs.yale.edu/homes/perlis-alan/quotes.html#93 http://www.cs.yale.edu/homes/perlis-alan/quotes.html#93