A dangling pointer is indeterminate
July 3, 2014
A case of undefined behaviour in C language
This blog post illustrates a lesser-known case of C undefined behavior, that is, using the value of a dangling pointer in a way that most developers consider harmless, such as pointer arithmetics or as operand of a comparison. Anyone who has ever had to debug an erratic C program knows that dangling pointers should not be dereferenced. In truth, according to the C standard, all further uses of the value of a pointer after the lifetime of the pointed object are forbidden. The post provides examples of apparently harmless uses of a dangling pointer, although they are still invalid. One is taken from the current snapshot of ntpd.
A synthetic example
Here is a first example:
#include
#include
#include
#include
int main(int argc, char *argv[]) {
char *p, *q;
uintptr_t pv, qv;
{
char a = 3;
p = &a;
pv = (uintptr_t)p;
}
{
char b = 4;
q = &b;
qv = (uintptr_t)q;
}
printf("Roses are red,\nViolets are blue,\n");
if (p == q)
printf ("This poem is lame,\nIt doesn't even rhyme.\n");
else {
printf("%p is different from %p\n", (void*)p, (void*)q);
printf("%"PRIxPTR" is not the same as %"PRIxPTR"\n", pv, qv);
}
}
What does the above program do? Many would see that it depends whether the compiler allocates the variables a and b at the same address. Without optimization, a and b are likely to be allocated to different stack slots, and the program prints a beautiful poem:
$ clang t.c && ./a.out Roses are red, Violets are blue, 0x7fff53c28bbf is different from 0x7fff53c28bbe 7fff53c28bbf is not the same as 7fff53c28bbe
Even at the minimum level of optimization, another compiler may allocate a and b at the same address, since they are never simultaneously alive:
$ gcc t.c && ./a.out Roses are red, Violets are blue, This poem is lame, It doesn't even rhyme.
Finally, in some cases, one may get the output below:
$ gcc -O2 t.c && ./a.out Roses are red, Violets are blue, 0x7fffb4e003bf is different from 0x7fffb4e003bf 7fffb4e003bf is not the same as 7fffb4e003bf $ gcc -v … gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)
The above result introduces a whole new branch of mathematics : the execution enters the branch where p != q, and then proceeds to display values for p and q that make the condition p == q true. This would make an excellent pitch for a special programming episode of The Twilight Zone.
You may think that p and q being passed to function printf() is the compiler’s excuse for generating an executable that behaves strangely, but in fact this printf() can be commented out, leaving only pv and qv, which are integers computed while the addresses are in-scope, to display strange values. The undefined behavior justifying the above output is indeed only the condition p == q.
An explanation
The clause 6.2.4:2 of the C11 standard defines the lifetime of an object:
The lifetime of an object is the portion of program execution during which storage is guaranteed to be reserved for it. An object exists, has a constant address, and retains its last-stored value throughout its lifetime. If an object is referred to outside of its lifetime, the behavior is undefined. The value of a pointer becomes indeterminate when the object it points to (or just past) reaches the end of its lifetime.
The third sentence of this paragraph is the well-known dangling-pointer-dereference undefined behavior, cause of the weakness CWE-416. The subject of this blog post is the last sentence: the value of dangling pointers itself. It is not only the pointed object but any copy of the value of a freed address that cause undefined behavior if used.
Dangling-pointer undefined behavior in the wild
A concrete instance of this kind of undefined behavior can be found in ntpd 4.2.7p446. At line 4421 of file ntpd/ntp_io.c, the definition of function delete_interface_from_list is:
static void
delete_interface_from_list(endpt *iface)
{
remaddr_t *unlinked;
do {
UNLINK_EXPR_SLIST(unlinked, remoteaddr_list, iface ==
UNLINK_EXPR_SLIST_CURRENT()->ep, link,
remaddr_t);
if (unlinked != NULL) {
DPRINTF(4, ("[...] %s [...] #%d %s [...]\n",
stoa(&unlinked->addr), iface->ifnum,
iface->name));
free(unlinked);
}
} while (unlinked != NULL);
}
In this function, when the pointer unlinked is not null at the if statement, it is freed and, according to the standard, its value becomes indeterminate. The condition of the do while loop is thus an undefined behavior for those iterations.
In order to avoid this undefined behavior, this function could be rewritten by changing the do while loop into an infinite loop (using a while (1) construct) and exiting the loop with a break; statement when the pointer unlinked is known to be null (in the else branch of the conditional).
static void
delete_interface_from_list(endpt *iface)
{
remaddr_t *unlinked;
- do {
+ while (1) {
UNLINK_EXPR_SLIST(unlinked, remoteaddr_list, iface ==
UNLINK_EXPR_SLIST_CURRENT()->ep, link,
remaddr_t);
if (unlinked != NULL) {
DPRINTF(4, ("[...] %s [...] #%d %s [...]\n",
stoa(&unlinked->addr), iface->ifnum,
iface->name));
free(unlinked);
+ } else {
+ break;
}
- } while (unlinked != NULL);
+ }
}Conclusion
The ntpd software package is a venerable program, and if a compiler optimization caused it to misbehave, the fact would likely have been noticed. There are no security consequences to this bug as far as one can tell.
One can blame the compiler for the first example. This debate is not for us to arbitrate, but note that even if GCC’s behavior on the first example was reported as a GCC bug, this would be unlikely to result in a change: the well-meaning answer would be “this is undefined behavior anyway”.
One can also wishfully believe that optimizing compilers such as GCC and Clang will never go as far as miscompiling the second example. Unfortunately, no one can tell how smart tomorrow’s compiler will be. An optimizing compiler can remove randomness from a pseudo-random number generator that uses uninitialized variables, or optimize a useful computation into an infinite loop. Because optimization based on undefined behavior is an exercise in absurdity, there is no telling what the consequences might be if a compiler became smart enough to notice that the function delete_interface_from_list uses a dangling pointer. One nightmare scenario is if the compiler inferred that the condition unlinked != NULL within the do is false for all defined values of unlinked, the only values that matter. Such a fact can be inferred with purely local reasoning, and justifies compiling the condition as “always false”. The consequence of this undefined behavior, if it caused this optimization, would be a resource leak where only the first matching element of the linked list would be removed, instead of all of them. With any secondary consequence that the non-removal of elements after the first one might have too.
This bug turned up during the initial steps of a verification of ntdp with TrustInSoft Analyzer. Of all the bugs that can be found this way, this one is rather in the harmless-interesting quadrant: not every bug needs a blog post just to argue that a bug exists. Other bugs, such as buffer overflows, are boring and dangerous. If pushed to its conclusion, the verification process will allow to be quite sure that neither boring nor interesting bugs remain within the chosen verification perimeter.
Ack
This post was written by Julien Crétin and Pascal Cuoq, and benefitted from insights of John Regehr, Harlan Stenn, Juergen Perlinger (who dug up this related discussion on comp.std.c), Lukas Biton, and Miod Vallat.
An earlier version of this post contained an error in the reasoning about the possible consequences of the undefined behavior in ntpd. Reddit user rabidcow pointed out the error.