Comment by vyodaiken | Hacker News Reader

Comment by vyodaiken | Hacker News Reader

Parent Full thread

>The standard doesn’t describe transformations; it describes behaviors

That is not remotely true - as you can see by looking up the example I reference.

>For C, that’s not something we can realistically do in every case. There’s no way to reasonably constrain the set of allowed behaviors after a program does some crazy pointer operation like * (int *) rand() = rand(), because any implementation of those constraints would more or less require an expensive run-time check at every pointer access.

That's such a weird response. There is nothing in the proposal that requires run-time checks. The proposal simply limits the ability of the compiler/translator to make counter-factual assumptions or otherwise violate the C semantics.

>What you could meaningfully ask is for particular situations (like negative shifts) to be considered unspecified or implementation-defined rather than undefined.

I don't want to do that: I want to clarify the meaning of "undefined behavior" to curtail its use as a license to do arbitrary code transformations. One implementation may trap on a negative shift, one may generate negative shift instructions that the architecture treats as no-ops or whatever they do, one might do sufficient static analysis to detect negative shifts and generate an error message - but the compiler is not free to assume that the shift operator has a negative value.

I'm not trying to remove undefined behavior from C. I am trying to correct a mistaken analysis of what undefined behavior should mean. C is intended to allow for non-portable operations, for example. These are "undefined" in the standard because they depend on the implementation, not because the C language should be specified so as to allow compilers to introduce hidden booby traps or counter-factual assumptions into the implementation

You should read the post you are replying to again, as it is well written and precise.

Basically, the intent of the proposal is understandable but it does not make sense as written.

The spec does not explain how to compile C code, it gives you a set of rules so that you could in theory take some piece of C source and a full execution trace and verify whether that trace was a conforming execution for that C code.

You take the example of the negative shift again, and it is addressed in the post you respond to : it's a perfectly fine proposal to demote negative shifts from UB to something less permissive to the compiler.

However, if you do so, of course, you have to frame what behaviors are accepted for a program doing such a negative shifts, just as you did in your post !

So let's say : arbitrary (but consistent) values are fine, termination is fine. That's great because it means we can still compile a shift to a CPU shift and there's no UB anymore. Ok.

Same goes for signed overflow.

However this is a case by case process, and you will absolutely not be able to ascribe meaning this way to many forms of UB. For example, as the GP said, storing through an invalid pointer.

If you want to compile a pointer store to a store instruction without runtime checks, then possible observable behavior include : other variable changing values, function call not returning to their calling context, and even of course running a full ROP chain exploit !

It's no surprise that in that case the specs says that the set of allowed observable behaviors is anything.

> It's no surprise that in that case the specs says that the set of allowed observable behaviors is anything.

And yet UB is frequently described as this scary monster that will eat your hard drive.

Sure there are more UBs in C than there would need to be if the standard restricted more on contemporary hardware. I think it still allows ones' complement representation for example? But I guess it shouldn't be so bad as long as compilers do not exploit the freedom to do anything that comes from UB, more than they need to on a particular architecture?

Compilers do not "exploit the freedom to do anything that comes from UB", they just assume that the program does not have UB. This might or might not lead the compiler to behave as if it was doing anything it wants, but it's not screwing the programmer on purpose.

As for "UB is frequently described as this scary monster that will eat your hard drive", setting aside that UB could be exploited by an attacker, it's not hard to imagine, for instance, a recursive file deletion routine that is affected by UB misbehaving and erasing more than it should.

Let me take a shift operation as an example. On architectures where it's no problem to "overshift" (e.g. the operation always results in 0), the compiler could be just fine and leave shifts alone. Maybe a 0 is exactly what the user wanted!

Or, the compiler could assume that the programmer made sure that overshifting never happens, since it's UB. Based on that assumption, it could make more aggressive (and possibly totally insignificant) optimizations by inferring other assumptions that don't align with the programmer's idea anymore.

I never encountered such a sitation myself, but there are stories like that on the internet, where for example the Linux kernel was broken.

Another scenario, the user might always do an operation that sometimes results in a random value (which is UB), but in the end only use the resulting value if it was not UB. The compiler instead could assume the operation can never happen in the first place. Again, there is a misalignment here in how the compiler reasoned and how the programmer reasoned (closer to the actual hardware).

So, the difficult problem is probably defining the UB configurations as narrowly as possible. It might be a good idea to specify UB per architecture in some cases, but then it would lead to a lot of complexity. In any case a guideline for compilers should be to minimize surprises, which means not applying many optimizations around UB. That's easier said than done I guess.

> As for "UB is frequently described as this scary monster that will eat your hard drive", setting aside that UB could be exploited by an attacker, it's not hard to imagine, for instance, a recursive file deletion routine that is affected by UB misbehaving and erasing more than it should.

I'd figure it's much more likely to happen as a result of a logic error introduced by the programmer, without any UB involved.

There's also this infamous example of UB: https://kristerw.blogspot.com/2017/09/why-undefined-behavior... (explanation: https://blog.tchatzigiannakis.com/undefined-behavior-can-lit...)

Thanks, that's interesting. And still, it's artificially constructed, so concerning the point I made (actual logic bugs are more likely) I think it stands.

IMHO this is clearly a compiler bug. Yes, it's technically allowed to do this because calling a NULL function pointer is UB, but nobody wants such an optimization (which is my first point from earlier). If the compiler makes such a decision based on UB, shouldn't it be able to at least issue a warning?

Furthermore, why should this be optimized in the first place? If the user decides to make a function pointer instead of a hard-wired inlineable call, he is aware of the performance implications (which are negligible in 99.9% of the cases). Where function call efficiency matters, nobody ever used a function pointer.

Shouldn't the compiler architecture be able to avoid making this optimization, simply by avoiding propagating the UB? It should simply not say "Calling NULL can never happen". This way it would never make optimizations that make the situation even worse. I think this would even be less optimization code!

Instead, when the UB happens, the programmer should get what he deserves (which is, well, calling NULL, and most likely resulting in a segfault, which is the right thing).

On the other hand, if the compiler can infer the value of a function pointer based on propagation of values alone, I'm fine with hard-coding the address, even though it's probably not worth the effort anyway.

That's a "devirtualization" optimization. Suppose you have a C++ class with a virtual method (or something similar coded in C), which only has a single concrete implementation. Clearly, every place which calls that virtual method through any pointer to that class can only be calling that single concrete implementation, so the compiler can call the function directly instead of through the function pointer, perhaps even inlining the called function.

Yes, that EraseAll example is silly, but how can the optimizer distinguish it from non-silly examples? Perhaps there are other alternative functions which also set that same function pointer, but they were all hidden by some #ifdef; in that case, devirtualizing when there's only one option left will be a performance win, and can expose other optimization opportunities.

> devirtualization

Hmm, shouldn't it be possible to do that in some other way? After all, a virtual function is something different than a function pointer (the vtable holding a function pointer is only an implementation detail, isn't it?).

Anyway, I'd rather not have that optimization. When we don't want to pay a small performance hit, we shouldn't make a virtual function in the first place. It's good to see how advanced optimization tricks can combine in dangerous ways with complicated language features!

> distinguish it from non-silly examples?

Yes, probably not possible. There is a real risk, but non-silly examples are less likely than constructed ones.

> all hidden by some #ifdef

If you do it with the preprocessor, there is no need for function pointers in the first place. Just make a #define instead of a variable.

Thanks again for the example, very interesting!

Argument like yours seem to rely on an incorrect understanding of the design of C. Languages like Java encapsulate program execution in a runtime that, in theory, can catch and manage all sorts of programmer errors that C does not catch. That's ok. If the programmer references past the end of an array, the compiler may catch and object, it may simply compile the instructions and let the program step on its own data structures or encounter a memory fault or even a protection violation if the architecture provides some type protection. And it's bizarre to see this warning about ROP exploit, when current "optimization" based on UB is a source of ROP exploit vulnerability. One cannot reliably put protections in code against bad pointers if upstream errors are grounds for deleting the guards.

Undefined behavior doesn’t exist to ease portability per se, it exists to handle meaningless yet syntactically valid constructs.

Shifting by a negative number is meaningless and is indicative of programming error. Instead of specifying that an implementation should check and handle these programming errors, which implies runtime costs, we use undefined behavior and leave the responsibility to the programmer.

The reason many compilers assume a positive shift after a shift operation executes is because otherwise the entire program would be undefined. You’re effectively asking for undefined programs to have defined behavior. The equivalent would be asking the compiler to correct your typos and it can’t do that. As they say: garbage in, garbage out. The compiler isn’t the one booby trapping you, you’re booby trapping yourself.

I think GP is right that what you want is more definition but it has to be in specific cases because otherwise the runtime costs would be too high. In your negative shift example, the definition would be “shifting by a negative number results in garbage output,” but note that that would burden implementations where negative shifts trap.

> it exists to handle meaningless yet syntactically valid constructs.

Maybe more like "handle bad situations that cannot be precluded at compile time". And since C has "no runtime", so can't do much "handling" at run time, it gets UB instead.

It doesn’t need to be unable to be precluded at compile-time to be UB. The expression “1 << -3” can be precluded at compile-time, yet it compiles just fine: instead it invokes UB.

Doing something at runtime is a different concept from having a runtime.

In any case, C, in fact, often does have a runtime. What do you think executes main()?

Yes, 1<<-3 can be detected as UB at compile time when doing constant propagation. But that wasn't my point (you could declare this expression invalid, no need for UB). I was pointing out that UB is not about "meaningless yet syntactically valid constructs" (if there is such a thing at all; I won't argue). UB in general manifests at run time. So I was only proposing a reformulation.

> In any case, C, in fact, often does have a runtime. What do you think executes main()?

Sure, that's why I said it has "no runtime" (in quotes). I'm not trying to split hairs here.

But your formulation isn’t right because it’s not about the UB code being detectable at compile-time or run-time, it’s about describing how the UB code should behave regardless of when it can be analyzed.

In the context of real numbers sqrt(-1) is syntactically valid yet meaningless code. In other contexts, 1 << -3 is too. Also log(-1). Perfectly valid syntax but has no meaning.

The intent of scare-quotes tends to be ambiguous so I avoid them in discussion. http://frivolousquotationmarks.tumblr.com

You're right, they're often ambiguous, but often I don't know how to say it tersely in a different way. My assumption was that in that context the statement [C has "no runtime"] had clear meaning, but maybe I was wrong. The point was to make it obvious that I don't want that be taken too literally, and that I don't want to start a hair splitting discussion whether C has a runtime or not. Apparently it didn't accomplish that goal.

As to the formulation of UB, it's not about code ("syntactically valid constructs") but about manifestation. And manifestation is a run time thing. 1<<-3 "is" UB, yes. And that can be detected at compile time through constant propagation. But that's not why we need UB. We could just forbid 1<<-3, so there was no need for UB in the first place.

UB is really about values not known at compile time. The expression 1<<x might manifest in UB at run time, depending on the value of x. Since x in general is not known well enough to decide whether it will ever be negative, the question "will this expression ever manifest in UB at run time?" is in general undecidable, so the best answer is "possibly". That does not imply that it's always a bad idea to use the expression 1<<x, and it does not make the construct meaningless. (Really I don't think the construct itself has a meaning, but as I said I won't argue here).

And that's why I think the formulation "handle meaningless yet syntactically valid constructs" is misleading. It's not about the construct (i.e., syntactic construction). It's about run time values that lead to UB, and that are totally independent from the construct itself. They might come from a wrong function invocation, or from malicious user input. It is the programmer's duty to make sure, by whatever means, that UB never manifests.

Maybe that's just what you were trying to say, but I think it's important to be clear that it's not about the syntactic constructs.

I’m not saying that 1<<x is generally meaningless. I’m saying that whenever the shift operand is negative, it’s meaningless. Just like log(x) isn’t generally meaningless, it’s only meaningless when the argument is not positive.

Syntactic constructs in general should and do have meaning. The meaning isn’t inherent, but nothing has inherent meaning. log(x) has no inherent meaning, but when x is positive we have decided that it means that it evaluates to the value to which you would raise 10 to get x.

Bad run-time values only cause UB in the context of improper usage in syntactic constructs. They aren’t independent of syntactic constructs: both syntactic constructs and values dictate behavior.

You’re right that UB only manifests itself at run-time. And you’re right that we wouldn’t need to use UB for constructs that only manifest their behavior at compile-time. Indeed, there exists syntactically valid yet meaningless C++ template substitutions that don’t result in UB, they result in compilation errors.

Reply on news.ycombinator.com