Create an account

Subscribe to LWN

LWN.net Weekly Edition for May 16, 2013

A look at the PyPy 2.0 release

PostgreSQL 9.3 beta: Federated databases and more

LWN.net Weekly Edition for May 9, 2013

(Nearly) full tickless operation in 3.10

Weekly edition	Kernel	Security	Distributions	Contact Us	Search
Archives	Calendar	Subscribe	Write for LWN	LWN.net FAQ	Sponsors

How might we eliminate undefined behaviour?

How might we eliminate undefined behaviour?

Posted Jul 20, 2009 1:41 UTC (Mon) by mikov (subscriber, #33179)
In reply to: How might we eliminate undefined behaviour? by xoddam
Parent article: Linux 2.6.30 exploit posted

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.

(Log in to post comments)

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.

Copyright © 2013, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds