Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Defining the Undefinedness of C (2015) [pdf]

fsl.cs.illinois.edu

Post reply on HN
Print view View original

31–40 of 91 posts

Re: Defining the Undefinedness of C (2015) [pdf]

#31

Post by bbatha »

the8472 wrote: post #15
iainmerrick wrote: post #2

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…

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 sam…

> 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.

Re: Defining the Undefinedness of C (2015) [pdf]

#32

Post by jcranmer »

bbatha wrote: post #28
kps wrote: post #9

Earlier quoted context omitted.

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 comme…

I've never really understood why this couldn't be slotted in as "implementation defined behavior". `add` has a well defined meaning on every platform just because it differs shouldn't give the compiler license to change the meaning of my program for that platform . It should however platform specific optimizations based on overflow, etc. Could somebody provide me with an example of truly undefinable behavior? (Perhap…

When C was first written, it wasn't necessarily possible on some architectures to get traps to trigger at the exact instruction on some hardware. Thus, any potentially-trapping instruction had to be undefined instead of implementation-defined.

Re: Defining the Undefinedness of C (2015) [pdf]

#33

Post by kibwen »

iainmerrick wrote: post #23
masklinn wrote: post #21

Earlier quoted context omitted.

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 *…

I wonder if it's possible to sneak UB into normal "safe" Rust code, by leveraging LLVM optimizations?

Yes, though those are considered bugs in the Rust compiler. As the goal of Rust is to forbid memory unsafety in safe code, the Rust developers accept the burden of working around LLVM-related UB (which sometimes is quite difficult, see e.g. this longstanding UB bug related to how LLVM translates certain numeric casts: https://github.com/rust-lang/rust/issues/10184 ).

Re: Defining the Undefinedness of C (2015) [pdf]

#34

Post by iainmerrick »

simias wrote: post #24
iainmerrick wrote: post #20

Earlier quoted context omitted.

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_MA…

I wouldn't write code like this on purpose, rather I'd genuinely need "next" for some other computation and the compiler could then use that to infer that I know "a" not to overflow. If I wanted to make it an "annotation" then I'd use "assert(a This is a very simple example of course, but maybe this "increment" code is actually used in many other parts of the codebase where the test actually makes sense. It's not rar…

That code ought to be a compile error. "On this code path, your code assumes ptr is null and not-null at the same time!"

Not all UB can be detected at compile time, but when it can be detected, it should be flagged to the user.

Re: Defining the Undefinedness of C (2015) [pdf]

#35

Post by jcranmer »

raphlinus wrote: post #8
iainmerrick wrote: post #2

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…

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 n…

> 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.

Re: Defining the Undefinedness of C (2015) [pdf]

#36

Post by lotyrin »

fundabulousrIII wrote: post #26

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

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.

Re: Defining the Undefinedness of C (2015) [pdf]

#37

Post by iainmerrick »

littlestymaar wrote: post #25
iainmerrick wrote: post #7

Earlier quoted context omitted.

Yeah, it's not at all clear to me why so many things need to be undefined rather than implementation-defined.

Undefined means : the compiler can omit this case and assume it never happens. Take integer overflow for instance: an implementation-defined behavior means in case of overflow the compiler can either wrap, crash, or have a saturation at max value. Undefined behavior means the compiler can assume it doesn't happen and optimize with this information in mind. For instance, the following code : for(i = 0; i With the unde…

That's a good example, thanks!

Reminds me of the Java binary search bug: https://research.googleblog.com/2006/06/extra-extra-read-all...

I think the correct code here would be something like:

    for (j = i; j
Or something like that. Obviously that's rather awkward, with the risk of a sneaky off-by-one bug. (Edit to add: heh, just noticed I'm assuming max+1 won't overflow!) It would be great to have a C-like language that encourages safer code like that.

Re: Defining the Undefinedness of C (2015) [pdf]

#38

Post by pjmlp »

iainmerrick wrote: post #16
woodrowbarlow wrote: post #10

Earlier quoted context omitted.

> 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 lin…

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 It seems like Rust is getting some traction, and that's great, but it's certainly not a drop-in replacement for C.

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.

Re: Defining the Undefinedness of C (2015) [pdf]

#39

Post by simias »

iainmerrick wrote: post #34
simias wrote: post #24

Earlier quoted context omitted.

I wouldn't write code like this on purpose, rather I'd genuinely need "next" for some other computation and the compiler could then use that to infer that I know "a" not to overflow. If I wanted to make it an "annotation" then I'd use "assert(a This is a very simple example of course, but maybe this "increment" code is actually used in many other parts of the codebase where the test actually makes sense. It's not rar…

That code ought to be a compile error. "On this code path, your code assumes ptr is null and not-null at the same time!" Not all UB can be detected at compile time, but when it can be detected, it should be flagged to the user.

But what if it's the result of some inlining or simply macro expansion? It's a tough call to make.

Re: Defining the Undefinedness of C (2015) [pdf]

#40

Post by pjmlp »

nickpsecurity wrote: post #22

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 More interesting, their use of these tools allowed them to make their C s…

Maybe making Frama-C part of the C standard would also be an improvement.
Post reply on HN