Nonsense. This is trivial stuff. [LWN.net]

How might we eliminate undefined behaviour?

Posted Jul 20, 2009 0:41 UTC (Mon) by xoddam (subscriber, #2322) [Link]

Question for language lawyers:

If the behaviour of a program is undefined, we can't rule out the risk that it is exploitable.

So how might we move towards eliminating undefined behaviour from a given piece of software?

It would be nice if the compiler was able to produce meaningful warnings everywhere that the program might ever do anything undefined.

Of course this is impossible in the general case because the task of static analysis is NP-complete (mostly because the program's inputs are not known to the compiler).

However there is surely a way to produce *many* such meaningful warnings. In particular, it must be possible wherever the compiler is presently able to exploit the undefined-ness of an operation to make an optimisation.

Of course if we were to attempt this immediately we would start with a huge, huge number of false positives due to race conditions and the like which are for the most part not bothersome in practice.

If it were then possible to gradually reduce these warnings by meaningful annotations and the judicious introduction of memory barriers and relevant runtime checking, any progress would then be most reassuring.

How might we eliminate undefined behaviour?

Posted Jul 20, 2009 1:41 UTC (Mon) by mikov (subscriber, #33179) [Link]

A poster in The Register (Steve 105) gave a good example of why a warning in this case, while it does seem desirable at first sight, is probably not a good idea in general:

Surely the reason for the optimisation is (among other things) code like this:
inline char foo(char *p) { if (p == 0) return 0; else return *p; }

char bar(char *p) { *p = 2; return foo(p); }

int main() { char c = 0; return bar(&c); }
If foo gets inlined into bar, the compiler can spot that the null pointer check in the inlined code is unnecessary and remove it. This is a most excellent optimisation (granted, in this example foo and bar do so little work that other optimisations may render it unnecessary).

I think GCC would do good if it reported this a warning iff using the pointer and checking the pointer are in the same original function - that is the optimization didn't appear as a result of other optimizations like global inlining, etc.

That would have caught our case. I am not sure how difficult it would to implement this distinction though - I suspect quite.

How might we eliminate undefined behaviour?

Posted Jul 20, 2009 2:34 UTC (Mon) by xoddam (subscriber, #2322) [Link]

Point taken; there is some subltety involved :-)

But I do think that we can reasonably ask the compiler to distinguish between cases where an optimisation is *demonstrably* safe (ie. the result can be determined at compile time, as in your inlining case) and cases where the optimisation can result in totally different behaviour between naive and optimised object code.

The particular optimisation that resulted in this particular vulnerability does not follow from eager evaluation of known quantities but from an assumption on the part of the compiler that the program is so correct as to never step outside the language specification. Since the spec leaves so much undefined, and programmers are human, and input is untrusted, this assumption is less than completely valid -- and therefore such optimisations merit at the very least a BIG FAT WARNING.

How might we eliminate undefined behaviour?

Posted Jul 20, 2009 3:01 UTC (Mon) by MisterIO (guest, #36192) [Link]

I think you're mixing two different things. 1 is the warning or something similar that could be emitted in a clear bug like the one in the original code(and some static checkers should really find that kind of bug), 2 is the gcc's optimization, that has nothing to do with the bug. Sure, the optimization allows the exploitation of the bug, but the warning about the bug doesn't have anything to do with it and, even without the optimization, the bug is still there so the warning makes sense. I'm not saying that gcc should warn about it at all costs, but it's clearly something that a static checker should be able to do. For example it seems like cppcheck has accepted my suggestion to include it among its checks.

How might we eliminate undefined behaviour?

Posted Jul 20, 2009 9:33 UTC (Mon) by stevenb (guest, #11536) [Link]

Inlining is just one of the problems, but in general "good warnings" and "optimization" don't go well together.

It shouldn't be too hard to warn about this in GCC before inlining in recent GCCs. GCC internals could look like this, for the current trunk (r149803):
* put a new pass after pass_early_warn_uninitialized (which runs before inlining), say pass_null_pointer_check
* look for null-pointer checks in the function
* for every found null-pointer check, see if there is a dereference of the pointer that dominates the check.

Implementing the details is left as an exercise for the reader. This would only warn when optimizing.

The problem is that you could actually need optimizations to get a reliable warning. If you try to warn before doing any optimizations (including inlining) then you wouldn't warn about a snippet like this one:

void bar(char *p) {
char *q = p;
*q = 2;
if (p)
foo(p);
}

because you wouldn't find a dereference of p before inlining, but the compiler will copy propagate p into q to give:

void bar(char *p) {
char *q = p;
*p = 2;
if (p)
foo(p);
}

which would have given you the warning...

It shouldn't be very hard to construct cases where you get missed warnings or false positives depending on what optimizations you do before figuring out what to warn about.

If you warn after optimizing (including inlining perhaps) you may get lots of false positives. But if you warn before optimizations, you may not warn for cases that are obvious by inspection.