Embedded in Academia

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 x. link
  • 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.

regehr

,

35 responses to “Contest: Craziest Compiler Output due to Undefined Behavior”

  1. 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. 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. 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. 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. 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.

  8. 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. 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.

  11. 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. 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. 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. 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. 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. 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.

  19. “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. 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. 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?

  23. 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?

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

  27. 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. 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. 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. 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. 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. 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. 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.