4 ms·

Hi! I'm a former compiler engineer who specialized on undefined behaviour. Would you like warnings on: * int f(int x, int y) { return x + y; } * int get

Hi! I'm a former compiler engineer who specialized on undefined behaviour. Would you like warnings on: * int f(int x, int y) { return x + y; } * int get_x_coord(Point *p) { return p->x; } * void compute_and_cache(const char *key) { *get_cache_bucket_for(key) = compute_value_for(key); } I'm curious, what would you do with a warning on every load or store through a pointer? On the flip side, I can offer -fsanitize=undefined which will catch when you do many things that have UB at runtime. It does not change the ABI which means that there are some bugs it can't catch, but deploying it is easier since you do not need to recompile all your libraries with it (like your C++ standard library and C library, in particular). You can use this to help you build unit tests that send intentionally overflowing values into your functions and show that they do not overflow. It turns untestable problem (since you cannot check for UB after it happens) into a problem you can write deterministic tests for.

wrs 3y ago
The problem isn’t overflow, the problem is the backwards logic of the compiler assuming there will never be any execution that leads to overflow, so the code that overflows just vanishes completely. In other words, bool overflowed = (x+1)<x; should be meaningful. It may or may not do what you want on any given architecture, but it shouldn’t just be assumed false.
- dzaima 3y ago
  How about if the x+1 was from an inlined function? a macro? perhaps even just a variable defined 10 lines up? In a 7-character sequence it may seem pretty obvious that it's probably intended to mean something, but when joining together multiple independent things doing redundant operations it's much less trivial. int game_logic(int prev_score, int bonus) { if (bonus < 0) { // check for bad argument return -1; } int new_score = prev_score + bonus; // ... if (new_score < prev_score) { // sanity check abort(); } return new_score; } // in the above the abort path can (and is) already optimized out, but an invocation of game_logic(x,1) becomes exactly x+1<x
- zzo38computer 3y ago
  I think the -fwrapv switch in GCC allows this to work properly. I don't actually know about this specific case, but -fwrapv makes signed and unsigned arithmetic to wrap around so that only the appropriate number of low bits are kept. (I commonly use -fwrapv when writing programs in C.)
  - deleted 3y ago
    [deleted]
- nlewycky 3y ago
  bool overflowed = (x+1)<x; I was convinced that some warning, probably -Wtautological-compare, already handled this and I plugged it into godbolt to see which one, but got no warnings with either gcc or clang. Frankly, I'm stunned and even a bit annoyed. Clearly this code deserves a warning, unless there's some good reason I'm just blind to right now. Nevertheless, I don't know what to do about the suggestion "it may or may not do what you want on any given architecture, but it shouldn’t just be assumed false." The compiler needs to know what it can and can't do. The common advice of "just do what the CPU does" doesn't work, we need to know what to do when cross-compiling, when constant folding, and we need to know which instructions are valid to select. If I selected PADDSW for this add (a saturating addition operation) but then later when you use x+1 I select a non-saturating addition, would you be happy with that? Probably not. The compiler needs actual rules to follow. I don't know how to apply the suggestion about warnings when we end up deleting dead code. The compiler deletes dead code all the time, consider a case like "vector<t> v; v.push_back(a); v.push_back(b);", each push_back begins with an if-statement on whether reallocation is required, and that becomes constant with inlining. Tracking "this code became dead because", well, because which situations exactly?
  - mjevans 3y ago
    If code is dead or unreached, and therefore deleted / no instructions emitted; clearly THAT is of a level a warning should cover, if not an error.
    - nlewycky 3y ago
      Dead code happens all the time. Adjusting the example in my comment you're replying to: vector<t> v; v.push_back(a); v.push_back(b); v.push_back(c); v.push_back(d); Let's suppose the definition of our vector here looks something like this: template <typename T> struct vector<t> { size_t len = 0; size_t storage_len = 0; T *storage = nullptr; void push_back(T t) { if (len + 1 > storage_len) { storage_len = storage_len ? storage_len * 2 : 1; storage = realloc(storage, storage_len); } storage[len] = t; ++len; } }; So here's what happens. vector<t> v; v.push_back(a); v.push_back(b); v.push_back(c); v.push_back(d); becomes len = 0; storage_len = 0; storage = nullptr; if (len + 1 > storage_len) { storage_len = storage_len ? storage_len * 2 : 1; storage = realloc(storage, storage_len); } storage[len] = a; ++len; if (len + 1 > storage_len) { storage_len = storage_len ? storage_len * 2 : 1; storage = realloc(storage, storage_len); } storage[len] = b; ++len; if (len + 1 > storage_len) { storage_len = storage_len ? storage_len * 2 : 1; storage = realloc(storage, storage_len); } storage[len] = c; ++len; if (len + 1 > storage_len) { storage_len = storage_len ? storage_len * 2 : 1; storage = realloc(storage, storage_len); } storage[len] = d; ++len; becomes len = 0; storage_len = 0; storage = nullptr; if (0 + 1 > 0) { storage_len = 1; storage = realloc(storage, 1); } storage[0] = a; len = 1; if (1 + 1 > 1) { storage_len = 2; storage = realloc(storage, 2); } storage[1] = b; len = 2; if (2 + 1 > 2) { storage_len = 4; storage = realloc(storage, 4); } storage[2] = c; len = 3; if (3 + 1 > 4) { storage_len = 8; storage = realloc(storage, 8); } storage[3] = d; len = 4; In that last one, you can see that the if-expression is false and the body becomes dead code. If I understand the rule you're proposing, you want to get a warning or error for that?
mjevans 3y ago
Different levels of warnings might be useful. -Wub # Warn _anytime_ there is detected potential undefined behavior, irrespective of if there is an associated optimization. -Wubelim # Warn any time code is eliminated as a result of undefined behavior / assumptions. -Wub... # Any other classes of UB optimizations that change the program as (incorrectly) written. Again, the goal is to provide feedback that improves the program and possibly educates / reminds the programmer about how their meanings might be misunderstood.
- nlewycky 3y ago
  > -Wub # Warn _anytime_ there is detected potential undefined behavior, irrespective of if there is an associated optimization. Can I ask you, have you tried any existing tools? Coverity static analysis, Klocwork, PVS-Studio, clang static analysis, tis-interpreter, Frama-C? What did you think of those? If not, why not (how important is the problem to you)? My understanding of these tools is that they start by marking every spot potential UB could happen -- every add is potentially overflowing, every pointer dereference is potentially null or freed or whatnot, and then they use solvers to prove that the UB does not occur, and print out the rest. The benefit they have is that they can examine more than one file at a time (the compiler may only look at one .c file at a time) and they have permission to take much longer than compiling. > -Wubelim # Warn any time code is eliminated as a result of undefined behavior / assumptions. This doesn't happen, the compiler doesn't detect your UB and use that to delete your code. Consider this: int x = 4; int y; int *p = &y - sizeof(int); *p = 7; printf("%d", x); The compiler sees 'x' mentioned in two places, once where it's defined, and once where it's used (picture the compiler building up a graph of places a values is set (definitions) and places the value is used, the use-def graph) and replaces the print with "printf("%d", 4);", then since 'x' is dead it can be deleted entirely. The rest of the code with 'y' and 'p' executes exactly in the way the programmer wrote it, we keep 'y' on the stack, and make 'p' a pointer out of bounds by computing the address that is 4 below 'y' and writing sizeof(int) bytes representing the value 7 there. We don't really go out of our way to detect UB. Another way to think about it is that the assumptions we make about your program being free of UB are completely indistinguishable from all the rest of the correct and working code. "int x = 4;" should declare a new variable, named x, with an int's worth of memory, initialized to the value 4. That is precisely as true to the compiler as any UB-performing, code. When you write "p->xcoord" you are telling the compiler that 'p' is a valid pointer to an object of its type at this moment, and it believes you. Trust the programmer, and all that. > -Wub... # Any other classes of UB optimizations that change the program as (incorrectly) written. "UB optimizations" isn't a thing. It just isn't. The optimizations never change the program, at least, not unless the compiler is buggy. The compiler's job is to find some assembly which meets the specification we call the program. With the optimizer enabled, we spend more time so that we can select assembly that minimizes a cost model we have for the execution time on the underlying machine (or sometimes file size). > Again, the goal is to provide feedback that improves the program and possibly educates / reminds the programmer about how their meanings might be misunderstood. FWIW we agree on the goal. The model for warnings in clang at least has been to look at the code as it is typed, and focus on errors that programmers make. We have all kinds of complex rules for warnings, like "if (3 < 4)" issues a warning (-Wtautological-compare) but "if (MAX_THREADS < MAX_CORES)" with #define MAX_THREADS 3 and #define MAX_CORES 4 doesn't. We've put a ton of effort into getting this sort of thing right, and that includes warnings that code will always produce UB when run, even if it was expanded through macros or templates. It's not an exhaustive system, the warnings work was guided by actual bugs we've encountered in real systems. There might be another way to do this. The C++ constexpr feature has the compiler evaluate some functions at compile time and detect any UB they encounter as they run. The clang implementation of this can also handle working with values that are not known at compile time, and working with dynamic allocations. One could try to run every function with the constexpr evaluator and see whether it does a better job at producing good warnings, then remove the redundant warnings (made by pattern matching on the AST) and see if the result is fast enough to use as part of regular compilation.
int_19h 3y ago
I wouldn't like warnings for these things. I'd like them all to trap in a well-defined (but non-recoverable) way if UB actually gets triggered. And I'd like this to be the default behavior, even in release builds. Safety should never be opt-in.
- nlewycky 3y ago
  I can offer you -fsanitize=undefined -fsanitize-trap=undefined, which you'd need to put in your configuration for release builds, presumably you have other flags in your build system (like -O2) already. It's possible that a program terminating based on attacker influenced values could be used as a channel to leak confidential data to the attacker, so I'd suggest that developers decide whether to use this on a case-by-case basis. (Maybe it should default to on, but we'd need user education so people who are building sensitive systems know they need to turn it off.)

wrs 3y ago

The problem isn’t overflow, the problem is the backwards logic of the compiler assuming there will never be any execution that leads to overflow, so the code that overflows just vanishes completely. In other words, bool overflowed = (x+1)<x; should be meaningful. It may or may not do what you want on any given architecture, but it shouldn’t just be assumed false.

dzaima 3y ago
How about if the x+1 was from an inlined function? a macro? perhaps even just a variable defined 10 lines up? In a 7-character sequence it may seem pretty obvious that it's probably intended to mean something, but when joining together multiple independent things doing redundant operations it's much less trivial. int game_logic(int prev_score, int bonus) { if (bonus < 0) { // check for bad argument return -1; } int new_score = prev_score + bonus; // ... if (new_score < prev_score) { // sanity check abort(); } return new_score; } // in the above the abort path can (and is) already optimized out, but an invocation of game_logic(x,1) becomes exactly x+1<x
zzo38computer 3y ago
I think the -fwrapv switch in GCC allows this to work properly. I don't actually know about this specific case, but -fwrapv makes signed and unsigned arithmetic to wrap around so that only the appropriate number of low bits are kept. (I commonly use -fwrapv when writing programs in C.)
- deleted 3y ago
  [deleted]
nlewycky 3y ago
bool overflowed = (x+1)<x; I was convinced that some warning, probably -Wtautological-compare, already handled this and I plugged it into godbolt to see which one, but got no warnings with either gcc or clang. Frankly, I'm stunned and even a bit annoyed. Clearly this code deserves a warning, unless there's some good reason I'm just blind to right now. Nevertheless, I don't know what to do about the suggestion "it may or may not do what you want on any given architecture, but it shouldn’t just be assumed false." The compiler needs to know what it can and can't do. The common advice of "just do what the CPU does" doesn't work, we need to know what to do when cross-compiling, when constant folding, and we need to know which instructions are valid to select. If I selected PADDSW for this add (a saturating addition operation) but then later when you use x+1 I select a non-saturating addition, would you be happy with that? Probably not. The compiler needs actual rules to follow. I don't know how to apply the suggestion about warnings when we end up deleting dead code. The compiler deletes dead code all the time, consider a case like "vector<t> v; v.push_back(a); v.push_back(b);", each push_back begins with an if-statement on whether reallocation is required, and that becomes constant with inlining. Tracking "this code became dead because", well, because which situations exactly?
- mjevans 3y ago
  If code is dead or unreached, and therefore deleted / no instructions emitted; clearly THAT is of a level a warning should cover, if not an error.
  - nlewycky 3y ago
    Dead code happens all the time. Adjusting the example in my comment you're replying to: vector<t> v; v.push_back(a); v.push_back(b); v.push_back(c); v.push_back(d); Let's suppose the definition of our vector here looks something like this: template <typename T> struct vector<t> { size_t len = 0; size_t storage_len = 0; T *storage = nullptr; void push_back(T t) { if (len + 1 > storage_len) { storage_len = storage_len ? storage_len * 2 : 1; storage = realloc(storage, storage_len); } storage[len] = t; ++len; } }; So here's what happens. vector<t> v; v.push_back(a); v.push_back(b); v.push_back(c); v.push_back(d); becomes len = 0; storage_len = 0; storage = nullptr; if (len + 1 > storage_len) { storage_len = storage_len ? storage_len * 2 : 1; storage = realloc(storage, storage_len); } storage[len] = a; ++len; if (len + 1 > storage_len) { storage_len = storage_len ? storage_len * 2 : 1; storage = realloc(storage, storage_len); } storage[len] = b; ++len; if (len + 1 > storage_len) { storage_len = storage_len ? storage_len * 2 : 1; storage = realloc(storage, storage_len); } storage[len] = c; ++len; if (len + 1 > storage_len) { storage_len = storage_len ? storage_len * 2 : 1; storage = realloc(storage, storage_len); } storage[len] = d; ++len; becomes len = 0; storage_len = 0; storage = nullptr; if (0 + 1 > 0) { storage_len = 1; storage = realloc(storage, 1); } storage[0] = a; len = 1; if (1 + 1 > 1) { storage_len = 2; storage = realloc(storage, 2); } storage[1] = b; len = 2; if (2 + 1 > 2) { storage_len = 4; storage = realloc(storage, 4); } storage[2] = c; len = 3; if (3 + 1 > 4) { storage_len = 8; storage = realloc(storage, 8); } storage[3] = d; len = 4; In that last one, you can see that the if-expression is false and the body becomes dead code. If I understand the rule you're proposing, you want to get a warning or error for that?

mjevans 3y ago

Different levels of warnings might be useful. -Wub # Warn _anytime_ there is detected potential undefined behavior, irrespective of if there is an associated optimization. -Wubelim # Warn any time code is eliminated as a result of undefined behavior / assumptions. -Wub... # Any other classes of UB optimizations that change the program as (incorrectly) written. Again, the goal is to provide feedback that improves the program and possibly educates / reminds the programmer about how their meanings might be misunderstood.

nlewycky 3y ago
> -Wub # Warn _anytime_ there is detected potential undefined behavior, irrespective of if there is an associated optimization. Can I ask you, have you tried any existing tools? Coverity static analysis, Klocwork, PVS-Studio, clang static analysis, tis-interpreter, Frama-C? What did you think of those? If not, why not (how important is the problem to you)? My understanding of these tools is that they start by marking every spot potential UB could happen -- every add is potentially overflowing, every pointer dereference is potentially null or freed or whatnot, and then they use solvers to prove that the UB does not occur, and print out the rest. The benefit they have is that they can examine more than one file at a time (the compiler may only look at one .c file at a time) and they have permission to take much longer than compiling. > -Wubelim # Warn any time code is eliminated as a result of undefined behavior / assumptions. This doesn't happen, the compiler doesn't detect your UB and use that to delete your code. Consider this: int x = 4; int y; int *p = &y - sizeof(int); *p = 7; printf("%d", x); The compiler sees 'x' mentioned in two places, once where it's defined, and once where it's used (picture the compiler building up a graph of places a values is set (definitions) and places the value is used, the use-def graph) and replaces the print with "printf("%d", 4);", then since 'x' is dead it can be deleted entirely. The rest of the code with 'y' and 'p' executes exactly in the way the programmer wrote it, we keep 'y' on the stack, and make 'p' a pointer out of bounds by computing the address that is 4 below 'y' and writing sizeof(int) bytes representing the value 7 there. We don't really go out of our way to detect UB. Another way to think about it is that the assumptions we make about your program being free of UB are completely indistinguishable from all the rest of the correct and working code. "int x = 4;" should declare a new variable, named x, with an int's worth of memory, initialized to the value 4. That is precisely as true to the compiler as any UB-performing, code. When you write "p->xcoord" you are telling the compiler that 'p' is a valid pointer to an object of its type at this moment, and it believes you. Trust the programmer, and all that. > -Wub... # Any other classes of UB optimizations that change the program as (incorrectly) written. "UB optimizations" isn't a thing. It just isn't. The optimizations never change the program, at least, not unless the compiler is buggy. The compiler's job is to find some assembly which meets the specification we call the program. With the optimizer enabled, we spend more time so that we can select assembly that minimizes a cost model we have for the execution time on the underlying machine (or sometimes file size). > Again, the goal is to provide feedback that improves the program and possibly educates / reminds the programmer about how their meanings might be misunderstood. FWIW we agree on the goal. The model for warnings in clang at least has been to look at the code as it is typed, and focus on errors that programmers make. We have all kinds of complex rules for warnings, like "if (3 < 4)" issues a warning (-Wtautological-compare) but "if (MAX_THREADS < MAX_CORES)" with #define MAX_THREADS 3 and #define MAX_CORES 4 doesn't. We've put a ton of effort into getting this sort of thing right, and that includes warnings that code will always produce UB when run, even if it was expanded through macros or templates. It's not an exhaustive system, the warnings work was guided by actual bugs we've encountered in real systems. There might be another way to do this. The C++ constexpr feature has the compiler evaluate some functions at compile time and detect any UB they encounter as they run. The clang implementation of this can also handle working with values that are not known at compile time, and working with dynamic allocations. One could try to run every function with the constexpr evaluator and see whether it does a better job at producing good warnings, then remove the redundant warnings (made by pattern matching on the AST) and see if the result is fast enough to use as part of regular compilation.

int_19h 3y ago

I wouldn't like warnings for these things. I'd like them all to trap in a well-defined (but non-recoverable) way if UB actually gets triggered. And I'd like this to be the default behavior, even in release builds. Safety should never be opt-in.

nlewycky 3y ago
I can offer you -fsanitize=undefined -fsanitize-trap=undefined, which you'd need to put in your configuration for release builds, presumably you have other flags in your build system (like -O2) already. It's possible that a program terminating based on attacker influenced values could be used as a channel to leak confidential data to the attacker, so I'd suggest that developers decide whether to use this on a case-by-case basis. (Maybe it should default to on, but we'd need user education so people who are building sensitive systems know they need to turn it off.)