8 ms·
Undefined Behavior in 2017
- jpfr 9y agoI wonder why he mentions this TIS interpreter but not the development of complete semantics for C and specifically the k framework (https://github.com/kframework/c-semantics https://github.com/kframework/c-semantics). Afaik, kcc is also really good at finding undefined behavior. Regehr even wrote about it in the past (https://blog.regehr.org/archives/523 https://blog.regehr.org/archives/523).
- tom_mellior 9y agoAFAIR from the last presentation on the K framework I attended (a year ago), the publicly available version of their C interpreter is incomplete: It only runs programs that don't need the standard library. That's pretty great for many things! But it's not a turnkey solution for analyzing real applications. For that they had a proprietary commercial version. (Again, this is from memory, and it may have changed.) Another reason to mention TIS-interpreter specially is that Pascal Cuoq (the co-author of this blog post) is one of its developers, and his livelihood depends on it being used.
- ellisonch 9y agoOriginal developer of the C semantics in K here! I just wanted to add a pedantic clarification (since pedantry is what semantics is all about). The semantics of the language itself is more or less complete. On top of that, a sizable portion of the standard library is given semantics directly (e.g, malloc, setjmp, stdargs, I/O including input/output to FILEs, much of printf, etc. are all formalized in the semantics). There's even basic C11 thread support. All of this runs and can be reasoned about formally. I tried to give direct semantics to the things that couldn't be (easily) written in C, because much of the standard library CAN be written in C and so it isn't so critical that it's formalized. To round out the library you can provide provide C implementations of any missing library functions at compile time (we provide some by default), and it will KCC those just like any other code. The resulting system is pretty good at catching undefined behavior, but it is super slow. I'm not involved with the commercial version, but they offer a trade off: don't do any semantic checking inside standard library calls in exchange for faster execution times. My understanding is that instead of chugging through the semantics of printf for every bottle of beer on the wall, they just call out to a native of printf. This makes things a lot faster, but it's possible you won't catch as many problems. In general, the commercial version is trying to make using the semantics practical instead of "academically slow", which was all I managed :) Any questions welcome.
- tom_mellior 9y agoThanks for the clarification! That's kind of what I remembered, but you explained it much better.
- pjmlp 9y agoThe main message from my point of view: > Be knowledgeable about what’s actually in the C and C++ standards since these are what compiler writers are going by. Avoid repeating tired maxims like “C is a portable assembly language” and “trust the programmer.” > Unfortunately, C and C++ are mostly taught the old way, as if programming in them isn’t like walking in a minefield. Nor have the books about C and C++ caught up with the current reality. These things must change.
- userbinator 9y agoI think it's the compilers that have perverted the language to such an extent that it's become ridiculously difficult to understand, and so it's the compilers that must change back to being less obtuse and adversarial. The C standard even suggests, when defining undefined behaviour, that one of the possible options is "behaving during translation or program execution in a documented manner characteristic of the environment". If signed int arithmetic on the hardware wraps around upon overflow, then take that into account when optimising and don't assume it can't overflow. This is how C programmers want the language to work; compiler writers and standards be damned. I've written plenty of Asm and also looked at as much if not more compiler output; and while the latter sometimes pleasingly surprises me, it's usually pretty evident that it was not generated by an intelligent entity. (And countless times, I've obtained size and/or speed savings by replacing the latter with what I would otherwise write.) My general impression is that there aren't enough highly-skilled Asm programmers working on compiler development --- there are many reasons I can think of for that, but one of the things I've always wished to exist is a simple, straightforward C compiler with "understandable" output and optimisation that creates results closer to what a human Asm programmer might write; with the associated optimisation advantages and predictability. This means not assuming anything just because the standard says so, but taking a more holistic (for lack of a better word) approach to compilation and optimisation. A long-time favourite post on this: http://blog.metaobject.com/2014/04/cc-osmartass.html http://blog.metaobject.com/2014/04/cc-osmartass.html
- clarry 9y ago> If signed int arithmetic on the hardware wraps around upon overflow, then take that into account when optimising and don't assume it can't overflow. This is how C programmers want the language to work; Don't speak for all of us. Some of us may take the language for what it is, instead of assuming it to be a "high level portable assembler" which it is not, but which a particular implementation of it may be, thanks to the standard leaving much up to the implementation. It is this same leeway that (thankfully) allows smart optimizing compilers that can generate performant code for programs that are not omgwtf-optimized at the source level. And it is this same leeway that allows very simplistic, naive implementations that do not go out of their way to perform crazy analysis to try and warn you about some corner case of undesirable behavior your code might hit. You're right that it is the compilers can and need to change to accommodate different types of users. But I don't think every compiler should just go back to being a 1991 compiler; not every compiler needs to accommodate every user.
- chrisdew 9y agoHow many of these 200+ undefined behaviours exist in more modern low-level languages, such as Rust and D?
- jupp0r 9y agoNone exist in (safe) Rust.
- adrianN 9y agoSometimes you hit undefined behavior in LLVM when compiling safe Rust, but that is considered a bug in the compiler. https://github.com/rust-lang/rust/issues/10184 https://github.com/rust-lang/rust/issues/10184
- saghm 9y agoBy the same logic, you could do something in C that isn't considered undefined behavior but acts in an undefined way when compiled with Clang
- justinpombrio 9y agoIn Rust it's pretty limited. Here is the full list, from the Rustonomicron: 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 Note that all of these are inside of unsafe blocks. Besides unsafe blocks, Rust has no undefined behavior, and the compiler will prevent you from doing any of these things. https://doc.rust-lang.org/nomicon/meet-safe-and-unsafe.html https://doc.rust-lang.org/nomicon/meet-safe-and-unsafe.html
- hornetblack 9y agoAn important point: if you provide a safe wrapper around some unsafe code it's up to the programmer to ensure the above is true.
- wereHamster 9y agoWhy don't compilers have an option to reject UB with an compiler error? Surely the compiler must know when it comes across a piece of source code whose semantic is undefined.
- adrianN 9y agoSome UB depends on the input (out of bounds access is a popular example). Some UB is created during optimization passes, for example by inlining. It's hard to produce useful error messages.
- chrisdew 9y agoSome undefined behaviours relate to runtime values. !iirc! signed 2+2 is safe but signed SIGNED_INT_MAX + 1 is not.
- Peaker 9y agoBut it is easy to give it a defined behavior on a particular architecture. For example, on x86-64, it can be defined to overflow just like unsigned does. The compiler can emit errors about the code if it is compiled to a different architecture where the same defined behavior is too expensive to implement.
- scatters 9y agoHow would that help? The behavior would be defined, but it still wouldn't be what you /want/.
- Peaker 9y agoDefined good behavior > defined bad behavior > undefined behavior. This article is about attacking the last category. Unsigned overflow is far less of a problem than signed overflow because it is defined. It is very cheap to make signed overflow defined. It is more expensive to detect it and fail at runtime.
- petergeoghegan 9y ago
- nikanj 9y agoI wish there was a GCC switch that made the optimizer go "This is clearly undefined behaviour. I'll stop this compile right here", as opposed to "This is clearly undefined behaviour. Sweet jackpot, it means I can do whatever the heck I want. Drop those NULL checks below, I've got the golden UDB ticket now"
- dom0 9y agoThe optimizer doesn't work that way. It assumes the code does not do UB and then removes branches that can never be taken if the code executes no UB. That's different from "This is UB, and now I do ...".
- cousin_it 9y agoI think we deserve a compiler warning whenever a source line of code (not a line generated by the preprocessor) gets removed due to UB exploitation. All such cases are worth the programmer's attention, because they are either useless lines or bugs.
- quantdev 9y agoIt's more complicated than this, unfortunately. Imagine an int variable x and two expressions f(x) and g(x) of x. Now imagine an if statement with condition f(x) < g(x). Precisely because incrementing the largest int is undefined behavior, the compiler may be able to simplify the if condition because, for example, it can assume x+1 > x is always true. So it's not necessary for the line to be useless or wrong for undefined behavior rules to trigger compiler optimizations.
- deleted 9y ago[deleted]
- caf 9y agoYou must also account for the case where the source line removed was only useless because of the specific context it had been inlined to by an earlier stage of the optimiser.
- the8472 9y ago> Loops that Neither Perform I/O nor Terminate > Summary: This UB is probably not a problem in practice (even if it is moderately displeasing to some of us). Since LLVM is mostly based around C/C++ semantics this actually turned out to be a problem for rust, because rust can encode diverging functions in its type system and assume certain code sections to be unreachable. If the compiler then optimizes out code and the unreachable (thus not-compiled) section is reached things explode. https://github.com/rust-lang/rust/issues/28728 https://github.com/rust-lang/rust/issues/28728
- userbinator 9y agoI think that's a great example of how optimisers have gone off the deep end: no reasonable human programmer would think "I can't figure out if this loop terminates, so let's just leave it out", but that appears to be the default behaviour in this case --- when what should happen when the optimiser "gives up" is that it should just translate the code verbatim.
- deleted 9y ago[deleted]
- adrianN 9y agoBut the optimizer doesn't give up in this case. It successfully figures out that the loop has no side effect except heating up your processor and eliminates it.
- iainmerrick 9y agoWhat's the advantage of eliminating the loop? If the compiler is able to do that analysis, why not flag the endless spin loop as a compilation error?
- kazagistar 9y agoLoop is inside a function, that can have no side effect conditionally. Function is used in multiple places and inlined. With inlined context, compiler can eliminate loop sometimes.
- deleted 9y ago[deleted]
- Cryptoholic 9y agoMitigation: Stop using languages that let you run roughshod over memory like C and C++ do.