Undefined Behavior and Fermat’s Last Theorem

In accordance with the C and C++ standards, if the program leads to an integer overflow or any other “undefined behavior” (UB), the result of the program performance can be anything: it can post obscenities to Twitter or format your disk…

Unfortunately, “Easter eggs” that would make the program do something out of the ordinary in case of UB, have not been noticed since the GCC 1.17 that invoked NetHack, when the code contained unknown #pragma. Usually, the undefined behavior result is much more boring: the compiler just optimizes the code for cases when UB does not take place, without giving the slightest importance to the situation when it does take place, as the standard allows to do anything in that case!

To illustrate how UB in the standard allows the compiler to perform non-obvious optimizations, Raymond Chen provides the following sample code:

int table[4];
bool exists_in_table(int v)
{
    for (int i = 0; i <= 4; i++) {
        if (table[i] == v) return true;
    }
    return false;
}

There is a off-by-one mistake in a loop condition, as we used <= instead of <. As a result, exists_in_table() should either return true at one of the first four iterations, or it will read table[4], which is UB. In this case, exists_in_table() can do anything, including returning a true! In full accordance with the standard, the compiler can optimize the code to:

int table[4];
bool exists_in_table(int v)
{
    return true;
}

Such optimizations often catch programmers off guard. John Regehr provides the following selection of examples when undefined behavior led to significant consequences:

• 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 compiler can run the code inside if (p) {… } and also inside if (!p) {… } when p is not initialized. link
• A division instruction (that potentially crashes the process) can be moved in front of code that has externally visible side effects. link. For example, this code:

int a;
void bar (void)
{
  setlinebuf(stdout);
  printf ("hello!\n");
}
void foo3 (unsigned y, unsigned z)
{
  bar();
  a = y%z;
}
int main (void)
{
  foo3(1,0);
  return 0;
}

will have time to print the message before SIGFPE, if compiled without optimizations, and it will crash right away in case we enable optimization. The program “knows in advance” that it is destined to crash with SIGFPE, and does not even bother printing the message. Chen provides a similar example, but with SIGSEGV.

In 2012, Regehr announced a contest for the craziest consequence of undefined behavior. One of the winners took advantage of the fact that the usage of a pointer after being passed to realloc(), is undefined behavior. His program prints different values for the same pointer:

#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 -O realloc.c; ./a.out

1 2

To my mind, the programs of other contest winners are more boring and partially overlap with the mentioned examples.

But nothing can compare with Regehr’s example: the disprove of Fermat’s Last Theorem by the compiler.

He says that he had to write an infinite loop for some embedded software, so that the optimizing compiler could not remove the entire code that follows the loop. Modern compilers are clever enough to detect “idioms” like while (1) { } or for (;;) { }. They understand that the code following such loop is unreachable and, therefore, there is no need to compile it. For instance, compilers will “shorten” the following function

void foo (void)
  {
    for (;;) { }
    open_pod_bay_doors();
  }

to a single instruction:

foo:
    L2: jmp L2

Clang is even smarter, it can detect (and remove) even the following masked infinite loops:

unsigned int i = 0;
  do {
    i+=2;
  } while (0==(i&1));

As in the previous example, the compiler is able to prove that the loop termination is not possible, and, therefore, it can be replaced by a single jmp instruction.

Regehr decided that compilers are unlikely to prove Fermat’s Last Theorem during compilation.

int fermat (void)
{
  const int MAX = 1000;
  int a=1,b=1,c=1;
  while (1) {
    if (((a*a*a) == ((b*b*b)+(c*c*c)))) return 1;
    a++;
    if (a>MAX) {
      a=1;
      b++;
    }
    if (b>MAX) {
      b=1;
      c++;
    }      
    if (c>MAX) {
      c=1;
    }
  }
  return 0;
}
#include 
int main (void)
{
  if (fermat()) {
    printf ("Fermat's Last Theorem has been disproved.\n");
  } else {
    printf ("Fermat's Last Theorem has not been disproved.\n");
  }
  return 0;
}

regehr@john-home:~$ icc fermat2.c -o fermat2
regehr@john-home:~$ ./fermat2
Fermat's Last Theorem has been disproved.
regehr@john-home:~$ suncc -O fermat2.c -o fermat2
"fermat2.c", line 20: warning: statement not reached
regehr@john-home:~$ ./fermat2
Fermat's Last Theorem has been disproved.

How come? The loop will terminate by return 1. Has the compiler managed to prove that Fermat’s Last Theorem is false?!

So, what a,b,c values has it found?

Regehr added printing of the found values before return 1. That’s when the compiler admitted its weakness and compiled and infinite loop. (Of course, nothing was printed).

Despite the fact that this program does not contain any arithmetic overflows (multiplier factors vary in the range from 1 to 1000, the sum of their cubes does not exceed 2³¹), the C++ standard defines an infinite loop as an undefined action, without changing the external state. That’s why C++ compilers are entitled to consider similar loops as finite.

The compiler can easily see that the only way out of the while(1) loop is the return 1; statement, while the return 0; statement at the end of fermat() cannot be reached. Therefore, it optimizes this function to

int fermat (void)
{
  return 1;
}

In other words, the only possibility to write an infinite loop that could not be removed by the compiler is to add a modification of the external state to the loop body. The easiest (and the most standard) way to do this is to change the variable declared as volatile.