Skip to content

Contest: Craziest Compiler Output due to Undefined Behavior

[UPDATE: Winners are here.]

The C and C++ standards fail to assign a meaning to a program that overflows a signed integer or performs any of the 190+ other kinds of undefined behavior. In principle, a conforming compiler can turn such a program into a binary that posts lewd messages to Twitter and then formats your disk. In practice, of course, we don’t expect such baroque consequences. Rather, the compiler is just going to do its job, which is to generate efficient code for all executions that don’t have undefined behavior. Disregarding Easter eggs such as the old version of GCC that would exec nethack, the compiler isn’t going to go out of its way to make undefined executions behave badly. It just doesn’t care about them. The problem is that as optimizers have gotten more clever, the consequences of undefined behavior have become a bit more strange. For example:

  • Using uninitialized data as an extra source of randomness caused a compiler to delete an entire seed computation. link
  • A compiler can evaluate (x+1)>x to both 0 and 1 in the same program, compiled at the same optimization level, for the same value of xlink
  • An infinite loop such as a counterexample search (where no counterexample exists) can be terminated by the compiler, permitting, for example, Fermat’s Last Theorem to be “disproved.” link
  • An undefined shift operation caused a compiler to delete an important safety check in Google’s Native Client. link
  • A reference to a possibly-null pointer in the Linux kernel caused the compiler to remove a subsequent null check, creating an exploitable vulnerability. link
  • A division instruction (that potentially crashes the process) can be moved in front of code that has externally visible side effects. link
  • A compiler can run the code inside if (p) { ... } and also inside if (!p) { ... } when p is not initialized. link

I will send a small but nice prize to the person who posts a comment describing the most interesting, surprising, or just plain crazy object code emitted by a compiler as a consequence of undefined behavior. Preference will be given to entries that:

  • Are posted before or on July 18 2012.
  • Describe interesting object code as opposed to describing a secondary consequence of that object code. A secondary consequence would be something like an ROP attack, launching a missile, or whatever.
  • Describe object code legitimately generated by a production-quality C or C++ compiler. In other words, I’m not interested in compiler bugs or in your own hand-crafted C compiler that emails Santa Claus when someone divides by zero.
  • Can be reproduced—so please, if possible, include compiler version, compiler options, a pointer to the code, etc.

If you readers can come to a consensus about the winner, I will go along with it. Otherwise, I’ll choose the winner. An example of an entry that would probably win (assuming that it could be reproduced) is “At -O2, LLVM 2.6 turns the attached C++ code into object code THAT ACTUALLY MAKES DEMONS FLY OUT OF MY NOSE.”

Here’s a similar discussion on Stack Overflow. However, people there are mostly talking about secondary consequences rather than interesting object code.

UPDATE: WordPress’s comment system likes to mangle C code, beware. I don’t know of an easy fix.

{ 35 } Comments

  1. bcs | July 12, 2012 at 8:48 am | Permalink

    Trivial but illustrative, this program:

    int main() { short i; for(i=0; i >= 0; i++); return 0; }

    “runs faster” (i.e. terminates at all) without optimizations then with.

  2. regehr | July 12, 2012 at 9:15 am | Permalink

    bcs, your function is actually an extremely tricky one.

    First there is this issue:

    http://blog.regehr.org/archives/482

    The short version of the story is that there is not exactly total agreement among compiler implementors about whether i++ is undefined when i is SHRT_MAX. My reading of the standard is that it is not undefined behavior.

    Second, compilers tend to terminate infinite loops that are free of side effects.

    So it’s very hard to know exactly what is going on when we compile this…

  3. Octoploid | July 12, 2012 at 9:49 am | Permalink

    Here is a simple one I came across yesterday:

    % cat te.c
    int main ()
    {
    int x = 1;
    while (x)
    x <<= 1;
    return x;
    }

    % gcc -O2 te.c –save-temps

    % cat te.s
    .file "te.c"
    .section .text.startup,"ax",@progbits
    .p2align 4,,15
    .globl main
    .type main, @function
    main:
    .LFB0:
    .cfi_startproc
    .p2align 4,,10
    .p2align 3
    .L2:
    jmp .L2
    .cfi_endproc
    .LFE0:
    .size main, .-main
    .ident "GCC: (GNU) 4.8.0 20120709 (experimental)"
    .section .note.GNU-stack,"",@progbits

    gcc-4.8 is the only compiler that produces an endless loop. All others (icc, clang, gcc<=4.7) exit normally with 0.

  4. amonakov | July 12, 2012 at 10:35 am | Permalink

    GCC-4.8 at -O2 compiles the following implementation of prefix sum computation into endless loop, turning code that accesses one element beyond array boundary into code that is virtually guaranteed to crash (which may considered to be a good effect of surprising [ab]use of undefined behaviour rules!). Loop exit test is eliminated since presence of a[i] access before exit test implies that ‘i < N' must be true.

    enum {N=32};
    int a[N], pfx[N];
    void prefix_sum()
    {
    int i, accum;
    for (i=0, accum=a[0]; i < N; i++, accum+=a[i])
    pfx[i] = accum;
    }

  5. regehr | July 12, 2012 at 10:55 am | Permalink

    Octoploid, that is a nice one. This may be the first example I’ve seen of a compiler aggressively exploiting the rule against left-shifting a 1 into or past the sign bit.

  6. regehr | July 12, 2012 at 11:03 am | Permalink

    amonakov, nice! It’s impressive that GCC notices this.

  7. amonakov | July 12, 2012 at 11:09 am | Permalink

    Regarding comment #5, there was a very similar “incident” in 2006 when standard configure check for mktime/time_t stopped working properly, because GCC produced an infinite loop for a loop like: for (int j = 1; j; j *= 2). See http://lists.gnu.org/archive/html/bug-gnulib/2006-12/msg00084.html and an interesting response from Ian Lance Taylor: http://lists.gnu.org/archive/html/bug-gnulib/2006-12/msg00151.html

  8. Pascal Cuoq | July 12, 2012 at 11:33 am | Permalink

    Here is my entry:

    http://lwn.net/Articles/278137/

    Short summary: programmers use undefined behavior (pointer overflow). Because of UB, the generated instruction (unsigned comparison) may not do what programmers intended. Programmers “fix” the problem by keeping the UB and adding another comparison to check if wraparound occurred. Compiler removes the additional comparison.

  9. Nick Lewycky | July 12, 2012 at 5:32 pm | Permalink

    Using clang from trunk (r160143):

    #include
    #include
    int main() {
    int *p = (int*)malloc(sizeof(int));
    int *q = (int*)realloc(p, sizeof(int));
    *p = 1;
    *q = 2;
    if (p == q) {
    printf(“%d %d\n”, *p, *q);
    }
    }

    $ clang evil.cc -o evil -O2; ./evil
    1 2

    Just because the pointers contain the same value does not mean they’re the same pointer; realloc ended the lifetime of the memory pointed to by ‘p’ and constructed a new pointer and returned that. Thus, the compiler concludes that ‘p’ and ‘q’ can’t alias each other.

  10. regehr | July 12, 2012 at 11:03 pm | Permalink

    Pascal and Nick, these are cool. It’s going to be hard to choose the best one.

  11. Eitan Adler | July 12, 2012 at 11:03 pm | Permalink

    In early versions of gcc the compiler would execute nethack or towers of hanoi when it encountered unknown pragmas.

    (okay, so this is implementation defined and not undefined but can it please still count?)

  12. Alireza Saberi | July 12, 2012 at 11:32 pm | Permalink

    Nick, realloc documentation emphasis that “The function MAY move the memory block to a new location, in which case the new location is returned.”. But it seems clang -O2 believes realloc “always” move the memory block to a new location thus ‘q’ and ‘q’ cannot alias each other.

  13. regehr | July 12, 2012 at 11:56 pm | Permalink

    Alireza, your observation (that the allocated block might not be moved) is correct. Even so, Clang is operating correctly here. Basically you have to read the fine print in the C standard which says that in effect, the block is released and then reallocated, but maybe at the same spot. Evil indeed.

  14. Pascal Cuoq | July 13, 2012 at 5:45 am | Permalink

    Actually, the example in comment 9 reminds me of a blog post I started to write pointing out that while realloc() sometimes is an efficient way to enlarge a block, if you have made many copies of the pointer, the standard gives you no way to know whether the block has moved. The realloc() call makes the old pointer indeterminate, and illegal to compare to the new pointer. You have to update all copies.

    realloc()’s modelization in Frama-C’s value-analysis-cum-C-interpreter warns about the p==q comparison in that example.
    I thought the comparison was idiomatic, and that that warning was an unfortunate false positive, so thanks Nick for pointing out to me that the warning is justified and not a false positive after all.

    (I still think it is idiomatic. I expect many codes use it, but it may not be too harmful in practice always to do the treatment intended for the case the block moved).

  15. regehr | July 13, 2012 at 8:39 am | Permalink

    Hi Eitan, I don’t think the GCC thing really counts since it’s more of a joke and it happens at compile time, so code generation isn’t involved.

  16. Chris | July 13, 2012 at 10:23 am | Permalink

    Nick, I fail to see how how that kind of behavior is unexpected. Every beginning C programmer knows that realloc doesn’t necessarily return the same pointer that you gave it, so it’s unsurprising that assigning a value to a location in memory that is not allocated doesn’t assign that value to another location which is allocated.

  17. ogoffart | July 13, 2012 at 11:27 am | Permalink

    The problem was in Qt as QList, QVector and co. Tried to emulate the C99 flexible array which does not exist in C++ with an array of size 1.
    Then, gcc would assume the variables used to index the array are always 0.

    http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43247
    https://bugreports.qt-project.org/browse/QTBUG-19199

    This is a variant of #5

  18. Anonymous | July 13, 2012 at 12:01 pm | Permalink

    Chris, you may want to re-read that code.

  19. Anonymous | July 13, 2012 at 1:39 pm | Permalink

    “Just because the pointers contain the same value does not mean they’re the same pointer” — I am very confused at reading this. How can two pointers containing the same differ…?

  20. Nick Lewycky | July 13, 2012 at 3:49 pm | Permalink

    Pascal, given that I’m writing in C++ the line “if (p == q)” is the one statement in that muck which actually has defined behaviour: “Two pointers of the same type compare equal if and only if they are both null, both point to the same function, or both represent the same address.” C++11 [expr.eq].

    In C99 the comparison rule is different, but it’s actually governed by “The value of a pointer becomes indeterminate when the object it points to reaches the end of its lifetime.” in 6.2.4/2, so the comparison could be true or false!

    Chris, note that it checks that p == q. Surely p == q implies that *p == *q right? Surprise!

    Anonymous, that’s exactly the lesson. A pointer is more than the memory address you would see if you inspected it in a debugger. See the fine print in your copy of the C standard for details.

  21. regehr | July 13, 2012 at 3:58 pm | Permalink

    So far I’m tempted to think that Nick’s entry is winning. Not only has it generated the most discussion, but it also is the only one that I found surprising. Opinions?

  22. regehr | July 13, 2012 at 4:01 pm | Permalink

    The ones from comments 3 and 4 are also excellent.

  23. David Harris | July 13, 2012 at 4:25 pm | Permalink

    Nick’s example seems to be the only one which involves libraries, as opposed to the C language itself. If malloc () and realloc () were user functions, the compiler could never know that p had reached the end of its lifetime.

    What if the user implements their own malloc and realloc (this is commonly done) — how would this affect undefined behavior?

  24. Mans | July 13, 2012 at 4:29 pm | Permalink

    I wrote a bit about a particular undefined behaviour a while back: http://hardwarebug.org/2011/10/18/pointer-peril/

    Summary: comparing addresses of distinct objects is undefined, as is indexing outside array bounds, and gcc knows it.

  25. Mans | July 13, 2012 at 4:31 pm | Permalink

    David, malloc() and realloc() are part of the C language. If you implement them with semantics different from the specified, you get undefined behaviour.

  26. Jeff Walden | July 13, 2012 at 11:34 pm | Permalink

    I’d vote for Nick’s entry as best so far, as well.

  27. Pascal Cuoq | July 14, 2012 at 11:51 am | Permalink

    Nick, I did not mean to say that == produces an undefined behavior in your program.

    I said meant that the first undefined behavior was in p==q, which I still think it is (first use of p after it has become indeterminate).

    “indeterminate” in the C99 standard does *not* mean that “the comparison could be true or false”, it means that accessing p for the comparison is *undefined behavior*. The same vocabulary is used for uninitialized locals (that clearly produce, on access, undefined behavior and not unspecified results; see http://markshroyer.com/2012/06/c-both-true-and-false/ ).

  28. Daniel Trebbien | July 15, 2012 at 7:03 am | Permalink

    I am somewhat confused by the aliasing comments for Nick’s example. Didn’t Clang just assume that p and q were aliases on account of the fact that the allocation sizes are the same, and so elide the check if (p == q)?

    Nick Lewycky, can you post the assembly, OS version, and libc version?

  29. regehr | July 15, 2012 at 8:40 am | Permalink

    Daniel, I can reproduce Nick’s result using Clang 160161 (from a day or two ago) on Linux (Ubuntu 12.04) on x86-64.

    I don’t know what libc version but I doubt that it matters– the issue here is Clang’s model of the C library, not the actual library code.

    Why would same allocation size permit Clang to elide the aliasing check?

  30. Pascal Cuoq | July 16, 2012 at 1:15 am | Permalink

    Daniel, I think you have it backwards.

    It is not that the compiler assumes that p==q evaluates to 1. No, that condition is compiled to actual code, whereas *p and *q as arguments of printf() are constant-folded into what should be their values if p and q did not alias (which according the compiler they can’t do in a defined way).

  31. Daniel Trebbien | July 16, 2012 at 5:42 am | Permalink

    regehr: The statement “same allocation size” implies “the pointers are aliases” is, of course, not true. I was just guessing as to what might be going on.

    I see the same thing on my Mac (Apple clang version 3.1 (tags/Apple/clang-318.0.61) (based on LLVM 3.1svn)
    Target: x86_64-apple-darwin11.4.0). Trimmed to the important part, the assembly it outputs is:

    movl $4, %edi
    callq _malloc
    movq %rax, %rbx
    movq %rbx, %rdi
    movl $4, %esi
    callq _realloc
    movl $1, (%rbx)
    movl $2, (%rax)
    cmpq %rax, %rbx
    jne LBB0_2
    ## BB#1:
    leaq L_.str(%rip), %rdi
    movl $1, %esi
    movl $2, %edx
    xorb %al, %al
    callq _printf
    LBB0_2:

    http://pastebin.com/SK12sxuT

    Indeed, Pascal, arguments *p and *q were replaced with 1, 2 in the call to printf(). Now I get it! Thank you.

    My vote is for Pascal’s example because I think that it is more likely to be encountered in real-world code.

  32. Jeff Epler | July 17, 2012 at 8:03 am | Permalink

    I like Nick’s program in comment 6; but the discussion about whether the comparison (p==q) is undefined behavior is interesting too. It seems like it is, which means that code of the form

    T *q = p; p = realloc(p, new_sz);
    if(p != q) { remap pointers internal to p; }

    is likewise invoking undefined behavior; an optimizing compiler might choose to make the ‘if’ condition always false, and never execute the body of the if statement (or even include it in object code). No, I’m not aware of any compiler that actually does this.

  33. regehr | July 17, 2012 at 9:49 am | Permalink

    Jeff, good point. It would be really easy to write code like this.

    There are also some other interesting issues having to do with realloc, such as whether it remembers that the original allocation was aligned or initialized.

  34. Cetin Sert | July 18, 2012 at 4:57 pm | Permalink

    Nick’s example tested on codepad including stdlib.h prints “1 2″ and without including stdlib.h prints “2 2″.

    codepad – with stdlib.h
    http://codepad.org/X0PLLkvj

    codepad – without stdlib.h
    http://codepad.org/88pmxnFA

    ideone prints “2 2″ in both cases. Don’t know which compilers they are using though.

  35. Mans | July 20, 2012 at 4:49 am | Permalink

    codepad uses gcc 4.1.2 or something that disguises itself as such very well.