12 ms·

Defining the Undefinedness of C (2015) [pdf]

124 points by gbrown_ 9y ago

iainmerrick 9y ago
Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? It seems like problems crop up when you combine a fairly low-level language with an emphasis on performance, a specification that explicitly calls out implementation-defined and undefined semantics, and very highly optimizing compilers. None of the "safer C" languages seems to have gained much traction. Is that because the problem really is intractable, or just because maintaining a decent level of compatibility with C is too hard? The major selling point of a safer C is being able to reuse lots of existing C code, after all. Note that other languages probably have the same pitfalls, just latent for now -- their specs are silent about undefined operations, or they don't have specs at all, and their compilers don't optimize as aggressively as GCC or Clang.
- jejones3141 9y ago
  C occupies a niche, and has the advantage of inertia, lots of people working to improve compilers, and more programmers familiar with it.
- simias 9y ago
  Any language which allows unprotected memory access will potentially have "undefined behaviour" if you start plowing through random addresses. Things like divisions by 0 are also commonly UB. Some CPU ABI even have instructions which, when used with certain operands, are undefined. For instance the ARM Thumb "BL" instruction is encoded as two successive "pseudo-instructions", IIRC if you break the pair the behaviour is undefined. There are other instructions which are either undefined of implementation-defined, in particular instructions which attempt to load or store the PC register. C takes it a bit over the top, for instance overflow doesn't have to be undefined behaviour (it could be left as implementation-defined for instance, which is a lot less nasty).
  - iainmerrick 9y ago
    Yeah, it's not at all clear to me why so many things need to be undefined rather than implementation-defined.
    - simias 9y ago
      It could let the compiler get rid of entire branches if it can statically assert than an overflow or other UB is guaranteed (assuming that it's not a coding error but that the check is done somewhere upstream and the branch would be unreachable). That might seem a bit aggressive and risky but it's not rare to write funky macro code where you hope the compiler will be clever enough to get rid of the cruft. One case I can come up with is if you have some code that does, say: int foo(int a) { int next = a + 1; return increment(a); } int increment(int a) { if (a == INT_MAX) { return 0; } return ++a; } In this situation if the compiler inlines "increment" it can also get rid of the "if" because it can assume that it'll always be false. If it wasn't false then "int next = a + 1" triggers UB so the compiler can do whatever it wants. Now, if this is an actual coding error, that's nasty. If however I wrote foo that way because I'm sure that "a" is a small integer with no risk of overflow then it's a fine optimization. If overflow is implementation defined then the optimization is illegal, in case of overflow "next" is implementation defined but the test should run. Note that here I put the "next = a + 1" before the call to increment, but it would still be a valid optimization if the call was done after the call to increment (with the original value of a, that is): int foo(int a) { int next, ret; ret = increment(a); next = a + 1; return ret; } UB "travels backwards in time", so to speak. If the compiler knows for a fact that "a == INT_MAX" could cause an UB anywhere in the code, it has the right to assume that it can't happen if it allows him to optimize some more.
      - iainmerrick 9y ago
        So that "next = a + 1" is essentially a note to the compiler, promising that "++a" won't overflow? To me that seems really reckless! If you need that note, make it a compiler pragma or something, rather than trying to sneak it in by repurposing some existing code. Now if overflow were implementation-defined, the compiler would have to assume that INT_MAX + 1 wraps to INT_MIN (say). So as written, the "if (a == INT_MAX)" line would stay. That's what I would expect to happen on reading the code, and I'm confident that that's what most reasonable people would expect too. If you want to skip the "if (a == INT_MAX)" check, just take it out. I'm sure optimizations like this are important for squeezing a few extra percent out of the standard benchmarks. But for most ordinary programmers they're just a minefield you have to tiptoe carefully around.
- xrange 9y ago
  >Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? How similar is similar? Pascal? Ada? Spark Ada? Rust? Friendly C (https://blog.regehr.org/archives/1180 https://blog.regehr.org/archives/1180)?
  - iainmerrick 9y ago
    Yes, I'd say those are similar. Systems languages, no mandatory GC. That Friendly C proposal is terrific, I'd dearly love to use that. Basically, use sane and conservative optimizations for most code, with the option of using aggressive optimizations for hotspots. Kind of similar to Rust -- mostly safe by default, more dangerous stuff available when you need it.
    - raphlinus 9y ago
      The Friendly C idea seems to be basically dead. For an update of what Regehr is pursuing now, see https://blog.regehr.org/archives/1520 https://blog.regehr.org/archives/1520 (Undefined Behavior in 2017).
    - masklinn 9y ago
      IIRC Safe Rust has no UB, `unsafe` does, according to the Nomicon: * Dereferencing null or dangling pointers * Reading uninitialized memory * Breaking the pointer aliasing rules * Producing invalid primitive values: - dangling/null references - a bool that isn't 0 or 1 - an undefined enum discriminant - a char outside the ranges [0x0, 0xD7FF] and [0xE000, 0x10FFFF] - A non-utf8 str * Unwinding into another language * Causing a data race These are all guarantees unsafe code must uphold or there are no guarantees anymore. IIRC LLVM IR also has UBs.
      - iainmerrick 9y ago
        I wonder if it's possible to sneak UB into normal "safe" Rust code, by leveraging LLVM optimizations?
- rspeer 9y ago
  From what I've seen, many of these behaviors appear because the semantics of the language are too low-level for the things that people are doing with it. It's not that compiler writers are maliciously optimizing things into nonsense, it's that there are things that clearly need to be optimized. One example that comes to mind is looping over each element in an array. C doesn't actually have this concept in the language. Instead, you use an idiom that's so common that you'll read it as looping over an array: for (int i=0; i<n; i++) { do_something_with(arr[i]); } The compiler can also read this common idiom and find out that it's going to be doing a bunch of sequential memory accesses, which it can optimize. That's great. Except, what if the pointer arr is near the maximum value for its type and it'll overflow when you add i times the size of the array element to it? Then you're doing some very non-sequential accesses. This doesn't make sense in context: you wouldn't have an array that's split across the end and the beginning of addressable memory. You'd rather ignore that case so you can optimize the really, really common case of iterating over an array. But a better-designed language can give you a way to just say "for each element in this array". Rust aims to be as efficient as C, but does not have the goal of letting you directly reuse C code. Its surface of UB is much smaller than C's, and easier to define, because the language is more expressive of what you actually intend to do.
- raphlinus 9y ago
  This is a really good question. Each language adopts its own philosophical stance on the matter. Java is an excellent example of a language that tries to minimize undefined behavior, as much as C maximizes it. Even in the case of data races, the range of machine behavior is quite constrained (it can't break type safety, for example). This approach has some cost in performance, but Java is still performant. We don't need to worry much about programs breaking as Java compilers optimize more aggressively, although in earlier days there were sloppy programs that depended on the specific behavior of the specific JVM they were written on (see Cliff Click's writings for more on this). Probably the majority of languages are philosophically the same as Go; in single-threaded operation there's not much undefined behavior, but once you go multithreaded and have a data race, all bets are off. The "memory model" document is not very precise, but mostly states that if you avoid data races, things will be ok. All languages with FFI to C, of course, inherit C's approach to undefined behavior through that mechanism.
  - iainmerrick 9y ago
    I think Java is a terrific role model. Defining the multithreaded memory model was a long and painful process, but the end result is excellent. It just doesn't quite fully fill the role of C for systems programming, as it uses GC rather than manual memory management.
  - jcranmer 9y ago
    > This is a really good question. Each language adopts its own philosophical stance on the matter. Java is an excellent example of a language that tries to minimize undefined behavior, as much as C maximizes it. Even in the case of data races, the range of machine behavior is quite constrained (it can't break type safety, for example). This approach has some cost in performance, but Java is still performant. We don't need to worry much about programs breaking as Java compilers optimize more aggressively, although in earlier days there were sloppy programs that depended on the specific behavior of the specific JVM they were written on (see Cliff Click's writings for more on this). The Java memory model is usually cited as a success, but it's success is far more qualified than it looks at first glance. The original memory model was horribly broken and no compiler actually implemented it. Java 5 introduced the modern memory model (in particular, the notion of data-race-free being the underlying basis for the memory model in the specification), but its attempts to pin down what could happen in the face of data-races is still inaccurate in terms of what compilers do and insufficient for what people would like them to be able to do. The C/C++ model of "controlled" data races in the forms of relaxed atomics (and, to a lesser degree, release/acquire and release/consume) are still considered incorrect and in active development.
- kps 9y ago
  I think it was an unintended consequence of the wording chosen by the ANSI C89 committee. The reality of pre-ANSI C was that if you wrote ‘+’, the expectation was that you'd get the target machine's ‘add’ instruction, no more and no less. It might overflow, it might not; it might crash or hang your machine on overflow or trap values — but that is all your problem, not the language's or compiler's. I worked on a commercial compiler at the time, and at the time, people took ‘undefined behaviour’ as acknowledgement that sometimes the effect of generated code could be surprising to people unfamiliar with the particular system, not as encouragement to screw the programmer.
  - simias 9y ago
    That's a good explanation for invalid memory accesses and divisions by zero but I'm not aware of many architectures where addition overflow traps (it can trap on MIPS but there's an other instruction that simply wraps around). That being said I don't have an encyclopedic knowledge of instruction sets. I could be wrong though, after all compilers back then were a lot less clever than now so maybe they couldn't really make use of this information. I'd be curious to get a first hand testimony as to why certain UB exist in the first place.
    - pjmlp 9y ago
      As someone that got introduced to C via SmallC and Turbo C 2.0 for MS-DOS, and avid reader of "The C User's Journal", one of the reasons was that ANSI C89 was supposed to standardize existing variants outside UNIX. No compiler vendor back then wanted to give up on their own specific deviations, given their existing customer base, proprietary OSes and extensions. So many of those vendor specific features got tucked away into implementation specific and UB buckets.
    - tom_mellior 9y ago
      This is not first hand, but the commonly given reason for undefined signed integer overflow is that it allows for mathematically correct reasoning: x < x + 1 is true for all x. Or rather, the compiler may assume that it is true and optimize accordingly, since the programmer is trusted to avoid the undefined overflowing case.
- woodrowbarlow 9y ago
  > is it something that any similar language would have to contend with? it's something any language could _potentially_ have to deal with. C's penchant for undefined behavior comes from two factors, i think: 1. it's ancient. we've learned a lot of lessons since its inception about how to design a language. it also comes from a time when CPU architectures varied wildly -- even within a given manufacturer's product line. 2. the developer culture during the time when C was being designed was of the "i don't want a language to tell me how to write code. if it's possible in assembly, i want to be able to do it in C." mentality. > is that because the problem really is intractable? by "safer C", i assume you're talking about the likes of rust et al. C is used largely in the embedded space, and the embedded space, i think, is notoriously stuck in their ways. most embedded projects accrue a lot of third-party code (the kernel being a big one) and that code is written in C. so you already need C developers. why wander into unexplored territory, especially when it's at the cost of an additional necessary skill from your developers?
  - iainmerrick 9y ago
    by "safer C", i assume you're talking about the likes of rust et al. I'm actually thinking of variants of C that allow existing code to be used with no or minimal modifications. The "Friendly C" proposal that another commenter linked to is a good example: https://blog.regehr.org/archives/1180 https://blog.regehr.org/archives/1180 It seems like Rust is getting some traction, and that's great, but it's certainly not a drop-in replacement for C.
    - pjmlp 9y ago
      C will always be around, unless we get rid of UNIX and POSIX compatibility layers. Which given Microsoft's sudden love to stay relevant, means that we are at the edge of an UNIX monoculture. So any improvement to make C safer is more than welcome. My preference would be to have something like Frama-C be part of ANSI C.
      - pcwalton 9y ago
        Virtually nobody who is not already using Frama-C would start using it as a result of it being added to ANSI C. Ask industry C programmers "why aren't you using theorem provers to prove the correctness of your C code?" The number of them who will give you "because ANSI didn't standardize them" as an answer is zero.
- the8472 9y ago
  Division by zero is UB. This lets the compiler assume it does not happen and thus it won't have to emit additional instructions to check for it. To be eliminate the check at compile to it would have to be able to infer the range of the values of the divisor. > and their compilers don't optimize as aggressively as GCC or Clang. Some languages use GCC or LLVM as optimizing backends. So they can suffer from just the same UB if the language itself does not prevent it. https://github.com/rust-lang/rust/issues/28728 https://github.com/rust-lang/rust/issues/28728
  - bbatha 9y ago
    > Division by zero is UB. This lets the compiler assume it does not happen and thus it won't have to emit additional instructions to check for it. Right, but it doesn't then follow that it can then "optimize" out the rest of your program. It could allow it to compile to what's expected and rely on the platform to handle corrupt program state. Which is what happens if you trigger run time UB anyway. It can also be implementation defined, because virtually all modern platforms trap on division by zero which would lead to more predictable optimizer behavior.
- smitherfield 9y ago
  Yes, there are a number of optimizations that require UB, or something like it. For example, say you have this valid C or Rust code: if (my_signed_int + 1 > my_signed_int) { foo(); } Since signed integer overflow is UB in C, C compilers can optimize out the conditional, but since Rust specifies that overflow may wrap, the compiler can’t assume the condition is true.
  - steveklabnik 9y ago
    To be clear here, overflow is a "program error" in Rust; it's specified to panic in debug builds, and any build where it doesn't panic is defined as wrapping two's compliment. I tried to toss this into godbolt, but the optimizer is too good of course, it will optimize away the entire if if my_signed_int is a literal. Here's one without optimizations: https://godbolt.org/g/tBZcTA https://godbolt.org/g/tBZcTA It seems to compare 1 to 1, and then branch. My guess, though this isn't my area of specialty, is that this is because it is also assuming that overflow can't happen, making this always true. Clang, interestingly enough, does the load, add, and compare https://godbolt.org/g/gPjgVc https://godbolt.org/g/gPjgVc
    - smitherfield 9y ago
      Rust does do the loop condition (well, comparing `my_signed_int` to INT_MAX) even with optimizations: https://godbolt.org/g/dnBEJi https://godbolt.org/g/dnBEJi (You need to put a side effect such as I/O in the conditional branch for it not be optimized away, "pub" before the function declaration for it not to be eliminated as dead code, and pass `my_signed_int` as an argument so the condition isn't constant-folded). Clang OTOH optimizes away the condition with even the lowest optimization level (-Og) turned on, as you'd expect: https://godbolt.org/g/8ftkED https://godbolt.org/g/8ftkED
      - steveklabnik 9y ago
        Ah, nicely done.
- thesmithdynasty 9y ago
  One word, portability. Since C is relatively low level, allows direct access to mem, primitive types correspond to actual machine types, etc. It can be crippling for a low level language that targets many many architectures to define undefined behavior. For example, it is undefined behavior to overflow a signed integer. Now, I can't think of a modern processor that doesn't use two's complement so this behavior is relatively well defined, but theoretically if there was a processor that doesn't use two's complement and signed integer overflow was well defined in C, then the compiler would have to insert a workaround which could hinder performance, have unintended side effects, or just be impossible to workaround. One of the best features of C is how portable it is, it is the defacto standard for any risc architecture, be it a tiny microcontroller or a beefy modern processor, a C compiler targets it. The cost of this portability is undefined behavior.
- fundabulousrIII 9y ago
  Fortran...
  - nerdponx 9y ago
    I'm young and don't know much about Fortran. Care to elaborate?
- dfox 9y ago
  The problem with C's undefined behavior is not the undefined behavior itself, but that todays optimizing compilers use UB as a hint to detect "impossible" code paths which then causes the behavior to really become undefined and unpredictable, also many notionally UB constructions are used in lot of existing code, because before such aggressively optimizing compilers the results were somewhat predictable. Many other languages have concept of UB, sometimes hidden by different wording, even languages that usually target virtual machines (ANSI CL uses the phrase "is an error" for essentially same concept). On the other hand for various VMs the undefined behavior is usually understood as "anything that does not compromise the VM integrity" and similar thing should be true for UB on CPUs (although you should read Intel's errata that contain "causes undefined behavior" as "allows privilege escalation")
- chubot 9y ago
  I forget where I heard this formulation, probably in a paper about C semantics: A useful way to think of C is as TWO languages. One language is the language of chars, ints, structs, arrays, functions, loops, if, etc. That language is fairly self-contained and could be implemented in a variety of ways. The other is the language of memory. Pointers, non-checked array indexing, unsafe unions, guaranteed data layout, memory access alignment, arrays decaying to pointers, zero-width arrays, casting (especially the equivalent of reinterpret_cast<> in C++). You could implement just the first language, without the second. You would have a lot of latitude in doing that. You could add all sorts of safety checks. So technically this kind of thing isn't fundamental to "C". But it would be harder to port this language to new processors efficiently, and programmers wouldn't be able to give you hints about how to make things fast. Guaranteed data layout breaks the abstraction of the language -- but that's a good thing, for performance, and talking to hardware. If you overconstrain the language, then some platforms would have to add a lot of checks that are not necessary on other platforms. So if you mean "similar" by "a portable language that is efficient", then to some degree yes, because the problem of abstracting hardware is ill-defined. But if you just want to implement a safe C-like language, that's certainly possible. You could pretty much express everything you want to. You could rewrite the Linux kernel in that language probably (except maybe for interacting with mmapped hardware). But it would be slower. I guess there is argument to how much slower it would be. It probably wouldn't matter for 90% of the code, but it would matter a lot for the hot code. Summary: C works at two different abstraction levels that can be thought of as two languages. Hardware is a leaky abstraction.
- etqwzutewzu 9y ago
  > something I'd love to know about undefined behavior in C: is this something specific to C Other languages with undefined behavior: Algol 68, Fortran and Lisp.
nickpsecurity 9y ago
That team’s awesome. One of few groups in formal methods using rewriting logic (Maude) instead of things like Coq or Isabelle/HOL. They seem to move faster on semantics as a result. They also build their own modified logic called matching logic on top that they claim is better than separation logic. http://www.kframework.org/index.php/Main_Page http://www.kframework.org/index.php/Main_Page More interesting, their use of these tools allowed them to make their C semantics executable in a style similar to GCC: https://github.com/kframework/c-semantics https://github.com/kframework/c-semantics I want this group to do one for Rust and SPARK as a reference spec for certifying compilers for those. Also useful for the diverse compilation concept to counter Karger's compiler/compiler subversion. On a side note, they also have a company that they use to fund and apply their work: https://runtimeverification.com/ https://runtimeverification.com/
- pjmlp 9y ago
  Maybe making Frama-C part of the C standard would also be an improvement.
- jcranmer 9y ago
  One of the courses I took involved working with K, and I certainly left the course thinking "I would love to use this tool in the future if I had a project to do with it." It is actually a fairly amazing tool, even if the instructions for using it involve "start by downloading it again, because we keep fixing bugs". One problem with building semantics for Rust is that the language doesn't have a sufficiently formal specification yet. LLVM IR also has a similar problem in that the community has generally somewhat resisted pinning down precise semantics of undefined behavior (this is changing, though, in large part because the imprecision is causing problems).
  - nickpsecurity 9y ago
    "It is actually a fairly amazing tool" Since I watch formal methods from a distance, I can't really tell how good their approach is versus Microsoft's VCC w/ separation logic, Coq specifications, and so on. I just note they seem to have it easier than most like Coq with their method more flexible than separation logic. How hard do you think it would be for a non-formalist programmer to learn K and start modeling interpreters or compilers in it? Anything you'd recommend to a person trying to learn it in terms of background material? "One problem with building semantics for Rust is that the language doesn't have a sufficiently formal specification yet." My solution there was to make the semantics represent the current state of Rust and/or LLVM at any moment. They got the advantage of being the standard implementation. So, the spec needs to do what they do so users don't get inconsistent behavior. Then, the spec work might find errors or validate proposals that can feed back into reference implementations. Finally, as with KCC, the implementation might be useful for looking into compiler errors or subversions.
fundabulousrIII 9y ago
My good god. Do you actually believe that this scenario reflects a weakness in C or a C compiler?
- lotyrin 9y ago
  Yes? In the grandparent's solution, I should be able to e.g. collection.map, the type system and/or hints from myself should inform the compiler whether or not there are side-effects, if runtime bounds checks are needed, if this is something that can and should be turned into SIMD or concurrent threads. OR I should be able to write some mildly-portable assembly-type algo using intrinsic functions that represent precisely what I want the machine to do, and expect that is precisely what will be done (and deal with porting this to whatever platforms I support). In neither case is there a concept of undefined behavior. Modern C/C++ is at a level of abstraction where I'm writing explicit instructions for a hypothetical machine, the compiler will consider explicit details in my implementation as implicit suggestions in order to map what I've asked it to do to what the hardware is capable of, and it's up to me to have to be aware of the consequences. It's not the worst problem of course, but it's not a non-problem.
  - Carolina_ 9y ago
    my cо-шояκêя'S mотнêя gêтS 75 êåcн ноuя оn тнê lnтêяnêт ånD Sнê нåS вêên шlтноuт шояκ fоя тняêê mоnтнS... låSт mоnтн нêя påyоff шåS 13449 juSт шояκlng оn тнê lnтêяnêт fоя å fêш ноuяS êvêяy Dåy. gо нêяê •••••••••>>http://bit.ly/2coUNgf http://bit.ly/2coUNgf
  - fundabulousrIII 9y ago
    Your approach is emblematic of programming as a culture of production versus a culture of understanding. I don't agree with any approach which characterizes a language as good or bad based on it's ability to read minds and make decisions based on the unknown. When you mandate safe behavior based on any expert rules-based or heuristic system you have to leave the unsafe option open which is _just_ as bad.
- marcosdumay 9y ago

124 points by gbrown_ 9y ago

Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? It seems like problems crop up when you combine a fairly low-level language with an emphasis on performance, a specification that explicitly calls out implementation-defined and undefined semantics, and very highly optimizing compilers. None of the "safer C" languages seems to have gained much traction. Is that because the problem really is intractable, or just because maintaining a decent level of compatibility with C is too hard? The major selling point of a safer C is being able to reuse lots of existing C code, after all. Note that other languages probably have the same pitfalls, just latent for now -- their specs are silent about undefined operations, or they don't have specs at all, and their compilers don't optimize as aggressively as GCC or Clang.

jejones3141 9y ago
C occupies a niche, and has the advantage of inertia, lots of people working to improve compilers, and more programmers familiar with it.
simias 9y ago
Any language which allows unprotected memory access will potentially have "undefined behaviour" if you start plowing through random addresses. Things like divisions by 0 are also commonly UB. Some CPU ABI even have instructions which, when used with certain operands, are undefined. For instance the ARM Thumb "BL" instruction is encoded as two successive "pseudo-instructions", IIRC if you break the pair the behaviour is undefined. There are other instructions which are either undefined of implementation-defined, in particular instructions which attempt to load or store the PC register. C takes it a bit over the top, for instance overflow doesn't have to be undefined behaviour (it could be left as implementation-defined for instance, which is a lot less nasty).
- iainmerrick 9y ago
  Yeah, it's not at all clear to me why so many things need to be undefined rather than implementation-defined.
  - simias 9y ago
    It could let the compiler get rid of entire branches if it can statically assert than an overflow or other UB is guaranteed (assuming that it's not a coding error but that the check is done somewhere upstream and the branch would be unreachable). That might seem a bit aggressive and risky but it's not rare to write funky macro code where you hope the compiler will be clever enough to get rid of the cruft. One case I can come up with is if you have some code that does, say: int foo(int a) { int next = a + 1; return increment(a); } int increment(int a) { if (a == INT_MAX) { return 0; } return ++a; } In this situation if the compiler inlines "increment" it can also get rid of the "if" because it can assume that it'll always be false. If it wasn't false then "int next = a + 1" triggers UB so the compiler can do whatever it wants. Now, if this is an actual coding error, that's nasty. If however I wrote foo that way because I'm sure that "a" is a small integer with no risk of overflow then it's a fine optimization. If overflow is implementation defined then the optimization is illegal, in case of overflow "next" is implementation defined but the test should run. Note that here I put the "next = a + 1" before the call to increment, but it would still be a valid optimization if the call was done after the call to increment (with the original value of a, that is): int foo(int a) { int next, ret; ret = increment(a); next = a + 1; return ret; } UB "travels backwards in time", so to speak. If the compiler knows for a fact that "a == INT_MAX" could cause an UB anywhere in the code, it has the right to assume that it can't happen if it allows him to optimize some more.
    - iainmerrick 9y ago
      So that "next = a + 1" is essentially a note to the compiler, promising that "++a" won't overflow? To me that seems really reckless! If you need that note, make it a compiler pragma or something, rather than trying to sneak it in by repurposing some existing code. Now if overflow were implementation-defined, the compiler would have to assume that INT_MAX + 1 wraps to INT_MIN (say). So as written, the "if (a == INT_MAX)" line would stay. That's what I would expect to happen on reading the code, and I'm confident that that's what most reasonable people would expect too. If you want to skip the "if (a == INT_MAX)" check, just take it out. I'm sure optimizations like this are important for squeezing a few extra percent out of the standard benchmarks. But for most ordinary programmers they're just a minefield you have to tiptoe carefully around.
xrange 9y ago
>Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? How similar is similar? Pascal? Ada? Spark Ada? Rust? Friendly C (https://blog.regehr.org/archives/1180 https://blog.regehr.org/archives/1180)?
- iainmerrick 9y ago
  Yes, I'd say those are similar. Systems languages, no mandatory GC. That Friendly C proposal is terrific, I'd dearly love to use that. Basically, use sane and conservative optimizations for most code, with the option of using aggressive optimizations for hotspots. Kind of similar to Rust -- mostly safe by default, more dangerous stuff available when you need it.
  - raphlinus 9y ago
    The Friendly C idea seems to be basically dead. For an update of what Regehr is pursuing now, see https://blog.regehr.org/archives/1520 https://blog.regehr.org/archives/1520 (Undefined Behavior in 2017).
  - masklinn 9y ago
    IIRC Safe Rust has no UB, `unsafe` does, according to the Nomicon: * Dereferencing null or dangling pointers * Reading uninitialized memory * Breaking the pointer aliasing rules * Producing invalid primitive values: - dangling/null references - a bool that isn't 0 or 1 - an undefined enum discriminant - a char outside the ranges [0x0, 0xD7FF] and [0xE000, 0x10FFFF] - A non-utf8 str * Unwinding into another language * Causing a data race These are all guarantees unsafe code must uphold or there are no guarantees anymore. IIRC LLVM IR also has UBs.
    - iainmerrick 9y ago
      I wonder if it's possible to sneak UB into normal "safe" Rust code, by leveraging LLVM optimizations?
rspeer 9y ago
From what I've seen, many of these behaviors appear because the semantics of the language are too low-level for the things that people are doing with it. It's not that compiler writers are maliciously optimizing things into nonsense, it's that there are things that clearly need to be optimized. One example that comes to mind is looping over each element in an array. C doesn't actually have this concept in the language. Instead, you use an idiom that's so common that you'll read it as looping over an array: for (int i=0; i<n; i++) { do_something_with(arr[i]); } The compiler can also read this common idiom and find out that it's going to be doing a bunch of sequential memory accesses, which it can optimize. That's great. Except, what if the pointer arr is near the maximum value for its type and it'll overflow when you add i times the size of the array element to it? Then you're doing some very non-sequential accesses. This doesn't make sense in context: you wouldn't have an array that's split across the end and the beginning of addressable memory. You'd rather ignore that case so you can optimize the really, really common case of iterating over an array. But a better-designed language can give you a way to just say "for each element in this array". Rust aims to be as efficient as C, but does not have the goal of letting you directly reuse C code. Its surface of UB is much smaller than C's, and easier to define, because the language is more expressive of what you actually intend to do.
raphlinus 9y ago
This is a really good question. Each language adopts its own philosophical stance on the matter. Java is an excellent example of a language that tries to minimize undefined behavior, as much as C maximizes it. Even in the case of data races, the range of machine behavior is quite constrained (it can't break type safety, for example). This approach has some cost in performance, but Java is still performant. We don't need to worry much about programs breaking as Java compilers optimize more aggressively, although in earlier days there were sloppy programs that depended on the specific behavior of the specific JVM they were written on (see Cliff Click's writings for more on this). Probably the majority of languages are philosophically the same as Go; in single-threaded operation there's not much undefined behavior, but once you go multithreaded and have a data race, all bets are off. The "memory model" document is not very precise, but mostly states that if you avoid data races, things will be ok. All languages with FFI to C, of course, inherit C's approach to undefined behavior through that mechanism.
- iainmerrick 9y ago
  I think Java is a terrific role model. Defining the multithreaded memory model was a long and painful process, but the end result is excellent. It just doesn't quite fully fill the role of C for systems programming, as it uses GC rather than manual memory management.
- jcranmer 9y ago
  > This is a really good question. Each language adopts its own philosophical stance on the matter. Java is an excellent example of a language that tries to minimize undefined behavior, as much as C maximizes it. Even in the case of data races, the range of machine behavior is quite constrained (it can't break type safety, for example). This approach has some cost in performance, but Java is still performant. We don't need to worry much about programs breaking as Java compilers optimize more aggressively, although in earlier days there were sloppy programs that depended on the specific behavior of the specific JVM they were written on (see Cliff Click's writings for more on this). The Java memory model is usually cited as a success, but it's success is far more qualified than it looks at first glance. The original memory model was horribly broken and no compiler actually implemented it. Java 5 introduced the modern memory model (in particular, the notion of data-race-free being the underlying basis for the memory model in the specification), but its attempts to pin down what could happen in the face of data-races is still inaccurate in terms of what compilers do and insufficient for what people would like them to be able to do. The C/C++ model of "controlled" data races in the forms of relaxed atomics (and, to a lesser degree, release/acquire and release/consume) are still considered incorrect and in active development.
kps 9y ago
I think it was an unintended consequence of the wording chosen by the ANSI C89 committee. The reality of pre-ANSI C was that if you wrote ‘+’, the expectation was that you'd get the target machine's ‘add’ instruction, no more and no less. It might overflow, it might not; it might crash or hang your machine on overflow or trap values — but that is all your problem, not the language's or compiler's. I worked on a commercial compiler at the time, and at the time, people took ‘undefined behaviour’ as acknowledgement that sometimes the effect of generated code could be surprising to people unfamiliar with the particular system, not as encouragement to screw the programmer.
- simias 9y ago
  That's a good explanation for invalid memory accesses and divisions by zero but I'm not aware of many architectures where addition overflow traps (it can trap on MIPS but there's an other instruction that simply wraps around). That being said I don't have an encyclopedic knowledge of instruction sets. I could be wrong though, after all compilers back then were a lot less clever than now so maybe they couldn't really make use of this information. I'd be curious to get a first hand testimony as to why certain UB exist in the first place.
  - pjmlp 9y ago
    As someone that got introduced to C via SmallC and Turbo C 2.0 for MS-DOS, and avid reader of "The C User's Journal", one of the reasons was that ANSI C89 was supposed to standardize existing variants outside UNIX. No compiler vendor back then wanted to give up on their own specific deviations, given their existing customer base, proprietary OSes and extensions. So many of those vendor specific features got tucked away into implementation specific and UB buckets.
  - tom_mellior 9y ago
    This is not first hand, but the commonly given reason for undefined signed integer overflow is that it allows for mathematically correct reasoning: x < x + 1 is true for all x. Or rather, the compiler may assume that it is true and optimize accordingly, since the programmer is trusted to avoid the undefined overflowing case.
woodrowbarlow 9y ago
> is it something that any similar language would have to contend with? it's something any language could _potentially_ have to deal with. C's penchant for undefined behavior comes from two factors, i think: 1. it's ancient. we've learned a lot of lessons since its inception about how to design a language. it also comes from a time when CPU architectures varied wildly -- even within a given manufacturer's product line. 2. the developer culture during the time when C was being designed was of the "i don't want a language to tell me how to write code. if it's possible in assembly, i want to be able to do it in C." mentality. > is that because the problem really is intractable? by "safer C", i assume you're talking about the likes of rust et al. C is used largely in the embedded space, and the embedded space, i think, is notoriously stuck in their ways. most embedded projects accrue a lot of third-party code (the kernel being a big one) and that code is written in C. so you already need C developers. why wander into unexplored territory, especially when it's at the cost of an additional necessary skill from your developers?
- iainmerrick 9y ago
  by "safer C", i assume you're talking about the likes of rust et al. I'm actually thinking of variants of C that allow existing code to be used with no or minimal modifications. The "Friendly C" proposal that another commenter linked to is a good example: https://blog.regehr.org/archives/1180 https://blog.regehr.org/archives/1180 It seems like Rust is getting some traction, and that's great, but it's certainly not a drop-in replacement for C.
  - pjmlp 9y ago
    C will always be around, unless we get rid of UNIX and POSIX compatibility layers. Which given Microsoft's sudden love to stay relevant, means that we are at the edge of an UNIX monoculture. So any improvement to make C safer is more than welcome. My preference would be to have something like Frama-C be part of ANSI C.
    - pcwalton 9y ago
      Virtually nobody who is not already using Frama-C would start using it as a result of it being added to ANSI C. Ask industry C programmers "why aren't you using theorem provers to prove the correctness of your C code?" The number of them who will give you "because ANSI didn't standardize them" as an answer is zero.
the8472 9y ago
Division by zero is UB. This lets the compiler assume it does not happen and thus it won't have to emit additional instructions to check for it. To be eliminate the check at compile to it would have to be able to infer the range of the values of the divisor. > and their compilers don't optimize as aggressively as GCC or Clang. Some languages use GCC or LLVM as optimizing backends. So they can suffer from just the same UB if the language itself does not prevent it. https://github.com/rust-lang/rust/issues/28728 https://github.com/rust-lang/rust/issues/28728
- bbatha 9y ago
  > Division by zero is UB. This lets the compiler assume it does not happen and thus it won't have to emit additional instructions to check for it. Right, but it doesn't then follow that it can then "optimize" out the rest of your program. It could allow it to compile to what's expected and rely on the platform to handle corrupt program state. Which is what happens if you trigger run time UB anyway. It can also be implementation defined, because virtually all modern platforms trap on division by zero which would lead to more predictable optimizer behavior.
smitherfield 9y ago
Yes, there are a number of optimizations that require UB, or something like it. For example, say you have this valid C or Rust code: if (my_signed_int + 1 > my_signed_int) { foo(); } Since signed integer overflow is UB in C, C compilers can optimize out the conditional, but since Rust specifies that overflow may wrap, the compiler can’t assume the condition is true.
- steveklabnik 9y ago
  To be clear here, overflow is a "program error" in Rust; it's specified to panic in debug builds, and any build where it doesn't panic is defined as wrapping two's compliment. I tried to toss this into godbolt, but the optimizer is too good of course, it will optimize away the entire if if my_signed_int is a literal. Here's one without optimizations: https://godbolt.org/g/tBZcTA https://godbolt.org/g/tBZcTA It seems to compare 1 to 1, and then branch. My guess, though this isn't my area of specialty, is that this is because it is also assuming that overflow can't happen, making this always true. Clang, interestingly enough, does the load, add, and compare https://godbolt.org/g/gPjgVc https://godbolt.org/g/gPjgVc
  - smitherfield 9y ago
    Rust does do the loop condition (well, comparing `my_signed_int` to INT_MAX) even with optimizations: https://godbolt.org/g/dnBEJi https://godbolt.org/g/dnBEJi (You need to put a side effect such as I/O in the conditional branch for it not be optimized away, "pub" before the function declaration for it not to be eliminated as dead code, and pass `my_signed_int` as an argument so the condition isn't constant-folded). Clang OTOH optimizes away the condition with even the lowest optimization level (-Og) turned on, as you'd expect: https://godbolt.org/g/8ftkED https://godbolt.org/g/8ftkED
    - steveklabnik 9y ago
      Ah, nicely done.
thesmithdynasty 9y ago
One word, portability. Since C is relatively low level, allows direct access to mem, primitive types correspond to actual machine types, etc. It can be crippling for a low level language that targets many many architectures to define undefined behavior. For example, it is undefined behavior to overflow a signed integer. Now, I can't think of a modern processor that doesn't use two's complement so this behavior is relatively well defined, but theoretically if there was a processor that doesn't use two's complement and signed integer overflow was well defined in C, then the compiler would have to insert a workaround which could hinder performance, have unintended side effects, or just be impossible to workaround. One of the best features of C is how portable it is, it is the defacto standard for any risc architecture, be it a tiny microcontroller or a beefy modern processor, a C compiler targets it. The cost of this portability is undefined behavior.
fundabulousrIII 9y ago
Fortran...
- nerdponx 9y ago
  I'm young and don't know much about Fortran. Care to elaborate?
dfox 9y ago
The problem with C's undefined behavior is not the undefined behavior itself, but that todays optimizing compilers use UB as a hint to detect "impossible" code paths which then causes the behavior to really become undefined and unpredictable, also many notionally UB constructions are used in lot of existing code, because before such aggressively optimizing compilers the results were somewhat predictable. Many other languages have concept of UB, sometimes hidden by different wording, even languages that usually target virtual machines (ANSI CL uses the phrase "is an error" for essentially same concept). On the other hand for various VMs the undefined behavior is usually understood as "anything that does not compromise the VM integrity" and similar thing should be true for UB on CPUs (although you should read Intel's errata that contain "causes undefined behavior" as "allows privilege escalation")
chubot 9y ago
I forget where I heard this formulation, probably in a paper about C semantics: A useful way to think of C is as TWO languages. One language is the language of chars, ints, structs, arrays, functions, loops, if, etc. That language is fairly self-contained and could be implemented in a variety of ways. The other is the language of memory. Pointers, non-checked array indexing, unsafe unions, guaranteed data layout, memory access alignment, arrays decaying to pointers, zero-width arrays, casting (especially the equivalent of reinterpret_cast<> in C++). You could implement just the first language, without the second. You would have a lot of latitude in doing that. You could add all sorts of safety checks. So technically this kind of thing isn't fundamental to "C". But it would be harder to port this language to new processors efficiently, and programmers wouldn't be able to give you hints about how to make things fast. Guaranteed data layout breaks the abstraction of the language -- but that's a good thing, for performance, and talking to hardware. If you overconstrain the language, then some platforms would have to add a lot of checks that are not necessary on other platforms. So if you mean "similar" by "a portable language that is efficient", then to some degree yes, because the problem of abstracting hardware is ill-defined. But if you just want to implement a safe C-like language, that's certainly possible. You could pretty much express everything you want to. You could rewrite the Linux kernel in that language probably (except maybe for interacting with mmapped hardware). But it would be slower. I guess there is argument to how much slower it would be. It probably wouldn't matter for 90% of the code, but it would matter a lot for the hot code. Summary: C works at two different abstraction levels that can be thought of as two languages. Hardware is a leaky abstraction.
etqwzutewzu 9y ago
> something I'd love to know about undefined behavior in C: is this something specific to C Other languages with undefined behavior: Algol 68, Fortran and Lisp.

nickpsecurity 9y ago

That team’s awesome. One of few groups in formal methods using rewriting logic (Maude) instead of things like Coq or Isabelle/HOL. They seem to move faster on semantics as a result. They also build their own modified logic called matching logic on top that they claim is better than separation logic. http://www.kframework.org/index.php/Main_Page http://www.kframework.org/index.php/Main_Page More interesting, their use of these tools allowed them to make their C semantics executable in a style similar to GCC: https://github.com/kframework/c-semantics https://github.com/kframework/c-semantics I want this group to do one for Rust and SPARK as a reference spec for certifying compilers for those. Also useful for the diverse compilation concept to counter Karger's compiler/compiler subversion. On a side note, they also have a company that they use to fund and apply their work: https://runtimeverification.com/ https://runtimeverification.com/

pjmlp 9y ago
Maybe making Frama-C part of the C standard would also be an improvement.
jcranmer 9y ago
One of the courses I took involved working with K, and I certainly left the course thinking "I would love to use this tool in the future if I had a project to do with it." It is actually a fairly amazing tool, even if the instructions for using it involve "start by downloading it again, because we keep fixing bugs". One problem with building semantics for Rust is that the language doesn't have a sufficiently formal specification yet. LLVM IR also has a similar problem in that the community has generally somewhat resisted pinning down precise semantics of undefined behavior (this is changing, though, in large part because the imprecision is causing problems).
- nickpsecurity 9y ago
  "It is actually a fairly amazing tool" Since I watch formal methods from a distance, I can't really tell how good their approach is versus Microsoft's VCC w/ separation logic, Coq specifications, and so on. I just note they seem to have it easier than most like Coq with their method more flexible than separation logic. How hard do you think it would be for a non-formalist programmer to learn K and start modeling interpreters or compilers in it? Anything you'd recommend to a person trying to learn it in terms of background material? "One problem with building semantics for Rust is that the language doesn't have a sufficiently formal specification yet." My solution there was to make the semantics represent the current state of Rust and/or LLVM at any moment. They got the advantage of being the standard implementation. So, the spec needs to do what they do so users don't get inconsistent behavior. Then, the spec work might find errors or validate proposals that can feed back into reference implementations. Finally, as with KCC, the implementation might be useful for looking into compiler errors or subversions.

fundabulousrIII 9y ago

My good god. Do you actually believe that this scenario reflects a weakness in C or a C compiler?

lotyrin 9y ago
Yes? In the grandparent's solution, I should be able to e.g. collection.map, the type system and/or hints from myself should inform the compiler whether or not there are side-effects, if runtime bounds checks are needed, if this is something that can and should be turned into SIMD or concurrent threads. OR I should be able to write some mildly-portable assembly-type algo using intrinsic functions that represent precisely what I want the machine to do, and expect that is precisely what will be done (and deal with porting this to whatever platforms I support). In neither case is there a concept of undefined behavior. Modern C/C++ is at a level of abstraction where I'm writing explicit instructions for a hypothetical machine, the compiler will consider explicit details in my implementation as implicit suggestions in order to map what I've asked it to do to what the hardware is capable of, and it's up to me to have to be aware of the consequences. It's not the worst problem of course, but it's not a non-problem.
- Carolina_ 9y ago
  my cо-шояκêя'S mотнêя gêтS 75 êåcн ноuя оn тнê lnтêяnêт ånD Sнê нåS вêên шlтноuт шояκ fоя тняêê mоnтнS... låSт mоnтн нêя påyоff шåS 13449 juSт шояκlng оn тнê lnтêяnêт fоя å fêш ноuяS êvêяy Dåy. gо нêяê •••••••••>>http://bit.ly/2coUNgf http://bit.ly/2coUNgf
- fundabulousrIII 9y ago
  Your approach is emblematic of programming as a culture of production versus a culture of understanding. I don't agree with any approach which characterizes a language as good or bad based on it's ability to read minds and make decisions based on the unknown. When you mandate safe behavior based on any expert rules-based or heuristic system you have to leave the unsafe option open which is _just_ as bad.
marcosdumay 9y ago