Reading indeterminate contents might as well be undefined

Pascal Cuoq - 13th Mar 2013

Warning: on a punctiliousness scale ranging from zero to ten, this post is a good nine-and-a-half. There was no tag for that, so I tagged it both “C99” and “C11”. The faithful reader will know what to expect. There is a bit of C90, too.

To summarize, it may appear that according to the letter of modern C standards, it is only dangerous to use uninitialized variables, instead of very dangerous. Nevertheless, this post shows that it does not matter what the standards say: compilers will bite you even when you are arguably right.

Some context in the form of a link

In 2012, Xi Wang wrote a nice blog post showing it is not a good idea to use an uninitialized variable as a source of additional entropy when trying to create a random seed.

“Xoring an uninitialized variable with whatever other source of entropy you already have cannot hurt”, the conventional thinking goes. Conventional thinking is wrong. Your typical modern compiler deletes the code that gathers the original entropy, since it is only going to be xored with an uninitialized variable. Hence the title of Xi Wang's blog post, More Randomness or Less.

In C90 “indeterminate” was simple

In the nineties real men were real men C standards were short and reading indeterminate contents(such as uninitialized variables) was listed in the very definition of “undefined behavior”:

1.6 DEFINITIONS OF TERMS

Unspecified behavior — behavior for a correct program construct and correct data for which the Standard imposes no requirements.

Undefined behavior — behavior upon use of a nonportable or erroneous program construct of erroneous data or of indeterminately-valued objects for which the Standard imposes no requirements.

“Undefined behavior” means the compiler can do what it wants so the behavior noticed by Xi Wang can in no way be held against a C90 compiler.

In 1999 C standards became more complicated

The C99 standard does not directly list “reading indeterminate contents” as undefined behavior. Instead it defines indeterminate contents as “either an unspecified value or a trap representation”. Reading a trap representation causes undefined behavior (6.2.6.1:5). The nuance here is that the type unsigned char is guaranteed not to have any trap representations (and thus can always be used to read indeterminate contents).

Less randomness : the simplified version

“But my compilation platform does not have trap representations for type int either therefore I can use an uninitialized int variable and expect an unspecified value (a much better prospect than undefined behavior)” one may think. This line of reasoning is attractive. It could even explain the behavior shown in Xi Wang's blog post and reproduced in simplified form below:

$ cat i.c
int f(int x)
{
  int u;
  return u ^ x;
}
$ gcc -O2 -std=c99 -S -fomit-frame-pointer i.c
$ cat i.s
…
_f:
Leh_func_begin1:
	ret
…

On this 64-bit platform the argument x passed to f() is in register %edi and the result of f() is expected in register %eax. Thus by executing instruction ret directly function f() is not even giving us back the entropy we provided it. It is instead giving us the current contents of %eax which may not be random at all.

(Giving us back the entropy we passed to it would have been mov %edi %eax followed by ret a longer sequence.)

One may argue that the compiler has only opportunistically chosen the most convenient value for variable u that is x xored with the current contents of %eax so that u xored with x is just the current contents of register %eax. This fits the interpretation of “unspecified value” for C99's definition of “indeterminate contents”. It is a good argument but just wait until you have seen the next example.

The next example

#include <stdio.h>
int main(int c  char **v)
{
  unsigned int j;
  if (c==4)
    j = 1;
  else
    j *= 2;
  printf("j:%u " j);
  printf("c:%d" c);
}

If fewer than three command-line arguments are passed to the program it should display an unspecified even number for j right?

$ gcc -v
Using built-in specs.
Target: x86_64-linux-gnu
…
gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5.1)
$ gcc -O2 t.c
$ ./a.out
j:1 c:1

GCC version 4.4.3 has decided that since the “else” branch was reading from an uninitialized variable j only the “then” branch was worth compiling. This is acceptable if reading uninitialized variable j is undefined behavior but not if it is unspecified behavior. Let us insist:

$ gcc -Wall -O2 -std=c99 t.c
$ ./a.out
j:1 c:1

Although we are requesting the C99 standard to be followed by GCC the program is not printing for variable j the even unspecified value we are entitled to.

(In passing a proper static analyzer would know that if it is going to show variable j as containing 1 it might as well show c as containing 4. Also a proper static analyzer would remind you that your program must in essence only be used with three command-line arguments. The reason compilers do not do this is covered elsewhere)

Between 1999 and 2011 C standards did not get shorter

In 2007 Rich Peterson working at HP was disappointed to find that the “Not a Thing” (NaT) value that registers can have on the Itanium architecture could not be used to implement an uninitialized unsigned char.

One thing led to another and the C11 standard was amended with the phrase “If the lvalue designates an object of automatic storage duration that could have been declared with register storage class (never had its address taken) and that object is uninitialized (not declared with an initializer and no assignment to it has been performed prior to the use) the behavior is undefined.”

That would have been my reaction too if I was paid by the word. Anyway this additional sentence re-introduces undefined behavior where there was none in C99.

In the example above the address of j was never taken so maybe that's GCC's excuse. Let us check:

#include <stdio.h>
int main(int c  char **v)
{
  unsigned int j;
  unsigned int *p = &j;
  if (c==4)
    j = 1;
  else
    j *= 2;
  printf("j:%u " j);
  printf("c:%d" c);
}
$ gcc -O2 t.c
$ ./a.out
j:1 c:1

No GCC is still acting as if j *= 2; was undefined.

Conclusion

I am not saying that this is not a bug in GCC. Perhaps it was fixed in later versions (in fact that version does not accept -std=c11 so it must be rather old). My thesis is that you might as well avoid reading from uninitialized variables as if it was undefined behavior because otherwise compilers will bite you. This statement holds even if what we have witnessed here is a bug in GCC version 4.4.3.

Also if this is a bug in GCC 4.4.3 this is the first time I identify a bug in GCC without the assistance of a random program generator. In other words compiler bugs are rare but they become surprisingly common if you stick to a strict interpretation of a necessarily ambiguous standard. And speaking of Csmith if there is indeed a GCC bug here said bug cannot be detected with Csmith which does not generate programs like mine.

Pascal Cuoq
13th Mar 2013