Towards Optimization-Safe Systems: Analyzing the Impact of Undefined Behavior | Hacker News Reader

Towards Optimization-Safe Systems: Analyzing the Impact of Undefined Behavior

pdos.csail.mit.edu

50 pointsColinWright47 comments

Open articleView on HN

More info: https://css.csail.mit.edu/stack

Code: https://github.com/xiw/stack

Simple solution: remove the undefined behaviour from your codebase.

Better solution, don't use languages that allow undefined behaviour.

Do you mean Haskell? because its compiler is very advanced and does complex optimizations.

I didn't have a particular language in mind. Though Haskell is certainly a fine choice.

It's semantically well-defined, though. The compiler will never change the value of your result, it will only discover more efficient ways to compute it.

Haskell allows plenty of undefined behaviour! unsafePerformIO, unsafeCoerce, the FFI, even something as simple as unchecked arithmetic can cause it.

why? languages like ruby etc dont even have universally defined behaviour - there is no spec etc, just a reference implementation.

Are you arguing that that is a good thing?

Ruby has a standard, http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_...

Easy talking, name one?

Is it hard? I thought that most languages had fully defined behavior, and that C was an exception to this. In case you want specific examples to poke holes in, let's say Java, C#, and Ada.

Once you add multithreading into the mix, there's plenty of undefined behavior in almost any language. In particular, compiler optimizations can cause surprising effects in programs without sufficient synchronization.

In the Java memory model you still get memory-safety in the presence of race conditions, but other than that the program behavior is pretty much undefined. It's better than undefined behavior in C, but not by much.

That's an interesting point, I hadn't thought about multithreading. Is it truly undefined in the nasal demons sense, or is it just that the behavior is hard to predict in advance?

I assume everyone reading a discussion about undefined behavior knows what nasal demons are, but just in case someone doesn't: in illustrating just what "undefined behavior" means in C, it has been suggested that it would be perfectly legal for a compiler, upon encountering such, to cause demons to fly out of the programmer's nose. The point being that it's not just a matter of producing an unexpected value or something of that nature, but a completely unexpected behavior. As a real-world example, early versions of gcc would, upon encountering a #pragma (whose behavior is undefined) would start a game of nethack.

It's hard because yes it's true that Java and C# have fully defined behaviour (at least to my knowledge, and when you assume that the garbage collection is optimal) the operations of the VM's themselves are written in C. So you are still dependant on that the programmers of your VM are in control of the undefined behaviour of C.

I know that sounds a bit like a cop out, but it lays the finger on the pain point of modern computing, that whatever we do, we are still so heavily reliant on C for everything low level.

How would we come close? I'd say name a language whose JIT directly outputs (x86) assembly, and whose runtime is written in a runtime free version that is output by that same JIT.

The only language I know of that can do that atm is Rust.

Rust, of course, uses LLVM, which is written in C++.

Yes, but it emits x86 assembly, and can emit code that runs without a runtime.

It would be interesting to find out if it generates any undefined constructs. My betting is it does.

You can use defensive C that checks for undefined behavior whenever it could possibly occur to implement the runtime of an undefined-free language.

And with intelligent coding you could probably get those checks to be very minimal.

Java

... and now you have two problems :-)

SML is the quintessential example. Haskell is pretty good about it, too.

Though this paper focuses on undefined behavior, defined behavior doesn't really make things any better when the programmer makes the wrong assumptions. Look at the first snippet; here the programmer assumed pointer arithmetic behaves like arithmetic in a register where overflow results in wrapping. This might be a reasonable assumption, but this isn't what the spec says. Now you could argue that this should be the defined behavior (and perhaps I would agree), because this is what many programmers will expect.

But sooner or later you'll come across a programmer who isn't aware of wrapping and wrongly assumes the value can only grow when a positive integer is added to it. So you could define a language which silently does bignums and all is well, except now you have to deal with memory allocation (this can be a major issue on memory-constrained platforms) during integer arithmetic, and the way bignum computations affect the program's performance & timing (crypto side channel attacks anyone?). So the next programmer again has to know the pitfalls of the Defined behavior and Do The Right Thing, just as he must do now with Undefined Behavior (i.e. rearrange bounds checking and pointer arithmetic so that it'll never point beyond one past the last element of an array; and so that your signed integers never overflow).

The second snippet (pointer dereference before NULL check) is perhaps more subtle, and again I might agree that the language would be safer if it didn't allow the removal of the NULL check that would keep this incorrect code from doing further harm. However, no matter what your proposed defined behavior for NULL/invalid pointer dereferencing is (what would it be? I have no idea), there would likely be cases where the programmer makes the wrong assumption and his program relying on that Defined behavior is still incorrect and potentially insecure.

Simply defining undefined behavior just doesn't fix incorrect code. You still have to remove the broken (undefined or not) code from the codebase...

EDIT: If you meant to suggest languages whose compiler will abort if it finds code that might result in undefined behavior, well, that's much harder. UB in C is predominantly a run-time issue, so you'd be making a really smart static analyzer to detect at compile time whether your code can actually hit UB. Did someone solve the halting problem? Alternatively you can make a language where integers never overflow. Then we get to what I said about bignums and surprise-allocation and such.. Haskell just isn't for everything.

You can define a null pointer access as what it actually does on the typical architecture, touching the memory at address 0. Obviously this won't magically fix unintentional NULL use, but it will let the kernel-mode dereference-before-check work fine.

It's not simple to find the undefined behavior in C. (As evidenced by the OP being about a tool to help. I've read that clang may be better than gcc at this.)

For the sort of code that was best written in C, a few decades ago, it was often reasonable engineering to depend on technically undefined behavior. Then over the decades the compilers made increasingly-subtle transformations without getting much better at telling you where they might have tripped you up (again, maybe except for clang which I haven't tried yet).

Easier said than done. There are better tools for finding undefined behaviour these days but they are pretty recent and far from perfect.

For a taste of how common undefined behaviour is, even in important code bases, (and why everybody should be using tools to test for it) see this post: http://blog.regehr.org/archives/1054 "Integer Undefined Behaviors in Open Source Crypto Libraries"

Also the follow up about how difficult C sometimes makes it to avoid undefined behaviour without a performance penalty: http://blog.regehr.org/archives/1063 "Safe, Efficient, and Portable Rotate in C/C++"

gcc 4.9 has a new UndefinedBehaviorSanitizer, -fsanitize=undefined - http://gcc.gnu.org/gcc-4.9/changes.html

Perhaps this will help find these coding mistakes? (unfortunately, it seems to be a runtime checker and not a compile-time warning)

As others have pointed out, statically determining whether a program will invoke undefined behaviour is undecidable.

Ah, but it doesn't have to be exact to be useful. Spotting common cases and minimising false positives would be great, even if there was no guarantee of catching everything.

That's like saying the halting problem is undecidable. Just because we can't make a general-case solution doesn't mean there isn't progress to be made.

Undefined behaviour is a dynamic property, not language constructs. It's akin to saying "remove run-time errors from your programs".

Only a specific class of error. And you can do that. It's hard, but you can do it.

C is deceivingly simple, I wonder how many people know about strict aliasing rules for example. To verify a C-program you should really 1. Do static analysis, preferable using many different tools, 2. Test on different optimization levels, 3. Test on different compilers.

I posted this a while ago https://news.ycombinator.com/item?id=6230503

It still intrigues me that this happens, I do wonder if it is limited to languages like C or if it could conceivably happen in anything with an advanced runtime (think the porter stemmer bug that broke java7 on release)

Maybe we can introduce this to jit-spraying ? (http://dsecrg.com/files/pub/pdf/HITB%20-%20JIT-Spray%20Attac...)

Seems to be a problem of language-lawyers coding compiler optimizations. Stop doing that. See also "Doctor, it hurst when I move my arm this way".

Given the reasons that people use C, what do you think makes for a better sales pitch -- "our compiler produces the fastest code" or "our compiler produces the safest code"? This is simply the compiler market optimizing for what it's customers want.

Well the existence of CompCert seems to indicate that there is at least some demand for a compiler with a greater emphasis on correctness than speed. It doesn't fix the issue of undefined behaviour of course since that is part of the language standard itself.

http://compcert.inria.fr/compcert-C.html

CompCert is a research project. Its unqualified existence does not prove that any demand exist for anything. You might as well say that there is some demand for aspect-oriented programming because so much research is being done on the topic (substitute the topic of your choice if my having picked this one offends you).

It so happens that this particular research project found a few industrial users eager to try it out and study the feasibility of deploying it, but it wasn't necessary for the research project to exist.

Not at all. The problem is that there are useful, effective optimizations allowed by the language spec which also have unexpected consequences on subtly incorrect code.

Take an oversized shift, for example. The result is undefined, and for good reason. This allows an expression like x << y to be translated directly to a single machine instruction on just about every architecture. If there was a defined result for oversized shifts, then many architectures' instructions would not match it, forcing the compiler to generate inefficient code on those architectures.

For every example of a weird optimization causing problems, you can find an example of that same optimization making code go much faster.

You could say that compilers should value correctness over speed, and I would agree with you, but: all of these optimizations are correct. These are C compilers, and they compile C programs just fine. Where they have trouble is on programs that aren't actually valid C, but are just close. You can argue that they are being technically correct in a bad way, but then if you abandon the standard and decide that you should "correctly" compile a certain class of invalid programs, how do you decide what "correct" means?

Ordinarily, unsigned left shift silently shifts bits off the end.

  0xffffffff <<  0 is 0xffffffff
  0xffffffff <<  1 is 0xfffffffe
  ..
  0xffffffff << 30 is 0xc0000000
  0xffffffff << 31 is 0x80000000

It is defined to ignore overflow. Therefore, I claim that there's enough consistency here that we can extend the pattern to this:

  0xffffffff << 32 is 0x00000000

I claim this really is the mathematically correct answer. It's consistent with the most obvious pattern, and there are no other relevant patterns.

C has chosen to call this undefined behavior instead of returning the correct answer here, and I call that choosing optimization over correctness.

That may be a useful left shift operator, but it's just not C's left shift operator. You can argue the spec is poor, but you cannot argue that the compiler writers are incorrect.

Are you so sure that all architectures that implement a left shift operator work the same way? For example, if you shift left by 'x' they might shift left by 'x modulo 32'

With C, you could still use the shift instruction on that architecture. With your 'correct answer', the compiler would have to output instructions to check the value of x prior to the shift.

Besides which, shifting is just one specific case. C has an easily understandable and documented behavior: overflow is undefined, no matter how you achieve it. We don't have to go into horrific detail about what happens when you overflow with adds, multiplys, shifts and so on.

On some architectures it's the way he wants it (always zero on overflow), on some it's the way you suggest (shift is mod 32), and on some it just generates junk.

Bitshifting is an operation that people generally expect to be extremely fast. Adding a check on every single operation generated by a C compiler just to guarantee identical results upon overflow probably would not go over well.

The Watcom C/C++ compiler used to have a neat shift optimization bug.

If you shifted one way a few bits then shifted back a few bits (As you would in calculating addresses for graphics operations), the optimizer would think you were undoing the operation and do nothing. or interestingly shift n-m bits.

You had to do some dummy operation in between for the code to actually execute. This was true at least up to Watcom 11.

People writing compiler optimizations are necessarily language lawyers. Their job is to make the code run as fast as possible given the semantics of the language.

In a way, the problem is that C dates too much from a time before language lawyers. I can't think of a modern language that is as underspecified as C, because we know better now. If were to be written again today, it would be much better specified (see: Go). I don't even mean this as a criticism of anybody in particular, it was a different time.

"Fixing" C would be creating a new dialect, unfortunately. (Personally, I just consider C a last resort, and I've found that works pretty well.)

The problem is deciding what kind of optimizations are 'resonable'. In one context, assuming x+1 is greater than x will avoid some wasteful code in your loops. In another context, it could destroy your program's logic. If you restrict yourself to guaranteed-safe optimizations, you miss out on most of the potential gains.

Reply on news.ycombinator.com