TL;DR

This post shows that modern optimizing C compilers assume that the source code they are compiling respects memory alignment constraints, even if the target architecture imposes no such restriction. This can lead to compiled programs not behaving as the programmer intended.

C: The Language Formerly Known as Portable Assembly

Some people will tell you that C is a portable assembly language, in which each line of source code is individually translated into one or a few assembly instructions. In this worldview, the C compiler does not do anything very smart, rather it only handles for you the mapping of subexpressions to the registers and instructions of various incompatible target ISAs. This worldview is no longer accurate, for reasons discussed in this blog post and in previous posts in the same vein, but it used to be true several decades ago. See for instance this answer by StackOverflow’s Jerry Coffin, which ascribes the notion of “C as a portable assembly language” to the first edition of the book “The C Programming Language” by Brian Kernighan and Dennis Ritchie, the creator of C himself. This early history of C as portable assembly language is also visible in this post to comp.std.c in 1990 retracing the problem that the volatile qualifier solved and its introduction by the ANSI standardization committee in the 1989 C standard.

The shift of the C language from “portable assembly” to “high-level programming language without the safety of high-level programming languages” should be kept in mind when writing C code from scratch in 2020, or when maintaining legacy C code.

Misaligned Memory Accesses

The x86-64 and AArch64 architectures are popular at the moment, and their respective 32-bit predecessors are still widely used; the POWER architecture is getting old, but the Power architecture continues to receive updates; RISC-V is popular in some circles, and so on. The C language is old enough to remember a time when the popular architectures were different, and unlike the popular architectures of today, did not all allow misaligned accesses. Alpha and SPARC are two examples of once-popular instruction sets in which misaligned memory accesses were forbidden (a processor exception would happen if such an access were attempted).

The C standards, having to accommodate both target architectures where misaligned accesses worked and target architectures where these violently interrupted the program, applied their universal solution: they classified misaligned access as an undefined behavior. This allowed both executions to continue normally with the results that you would expect if you had been writing x86-64 assembly, or for the execution to stop abruptly, which you would expect if you had been writing SPARC assembly. This in turn led to the appearance of C programs that, consciously or not, were only written for architectures that allow misaligned memory accesses. In fact, if you ask early owners of Alpha or SPARC computers, there were many of these. For users of these architectures, the problem was that C programs, written to access memory in misaligned ways, worked as intended on the numerous processors that allowed this, but crashed when compiled and run on their computers. This is now a forgotten problem, but a well-documented one nevertheless. It is covered for instance in the blog post On misaligned memory accesses(2006).

Something funny happened to Pavel Zemtsov in 2016. He was writing C++ code that involved misaligned memory accesses, as one tends to do without even noticing when one is targeting x86-64, when he suddenly realized that he was using an architecture that forbade misaligned accesses after all! GCC automatically vectorized the loop he was writing, and in doing so, assumed that all uint32_t accesses were to addresses that were aligned to 32-bit boundaries. The summary of that blog post, A bug story: data alignment on x86, is that GCC used vector instructions recently added to the x86-64 ISA that had alignment requirements. The humor came from the fact that the source code looked very ordinary: nothing suggested the use of modern vector instructions; the source did not call intrinsics or anything like that. But making sophisticated transformations is what modern, optimizing C compilers do.

A Clever GCC Optimization

The present blog post brings bad, and as far as I know, previously undocumented news. Even if you really are targeting an instruction set without any memory access instruction that requires alignment, GCC still applies some sophisticated optimizations that assume aligned pointers. Consider the following function:

int h(int *p, int *q){
  *p = 1;
  *q = 1;
  return *p;
}

GCC optimizes this function to make it always return 1:

h:
        movl    $1, (%rdi)
        movl    $1, (%rsi)
        movl    $1, %eax
        ret

GCC generates code for a function h that always return 1: that’s the movl $1, %eax part of the assembly listing, in which the value 1 is hard-coded. In this function, GCC reasons that if p and q are the same, then the second assignment writes 1 to *p, and if they are distinct, when what is read in *p is exactly what was written at the first assignment, that is, 1. It seems that either way, the function can only return 1. The reasoning is sound if p and q both are aligned to an address multiple of sizeof(int), but it is wrong if either pointer is misaligned, as in the calling context below:

void f(void) {
  char *t = malloc(1 + sizeof(int));
  if (!t) abort();
  int *fp = (int*)t;
  int *fq = (int*)(t+1);
  int r = h(fp, fq);
  assert(r == *fp);
  ...
}

Strictly speaking, the function f invokes Undefined Behavior when it computes fq. The result t of the call to malloc is guaranteed to be aligned for int, but t+1 is not aligned for int. A very old computer that uses non-uniform pointer representations could crash on the conversion to int* of t+1. The words “if the resulting pointer is not correctly aligned for the referenced type, the behavior is undefined” in the C11 standard make the conversion Undefined Behavior.

The programmer, knowing that the program is to be executed on the little-endian x86-64 architecture, that has uniform pointer representation and handles misaligned accesses, might expect r to be set to 257 and the assertion to be true. Instead, r is set to 1, but *fp still evaluates to 257, so that the assertion is evaluated as false at runtime.

Note that this discussion is not about strict aliasing. The description of strict-aliasing rules in the C standard is rather vague, and it could be interpreted as meaning that you are not allowed to use the second byte of an int to read the first byte of an int. However, if using the compilation option -fno-strict-aliasing, you tell GCC to use a forgiving memory model without strict aliasing restrictions, it still optimizes functionh

How to express misaligned memory accesses

If you are writing C code in 2020 that would benefit from reading four bytes at once even if these may not be aligned to a multiple-of-4 address, and if this C code is intended to be compiled with a modern C compiler, you should use memcpy. On target architectures that allow misaligned memory accesses, a modern C compiler can easily translate the memcpy from a temporary int variable into the single assembly instruction that you would have written if you were directly writing in assembly. As a bonus, the same code will function on architectures that do not allow misaligned memory accesses; on these, the compiler will automatically generate either a longer sequence of instructions or an actual call to memcpy.

For instance, if the function h is intended to accept a misaligned pointer q, it can be changed as follows:

int h(int *p, int *q){
  *p = 1;
  int one = 1;
  memcpy(q, &one, sizeof *q);
  return *p;
}

Note: if you take this route, you might want to go the extra mile and avoid building misaligned pointers altogether, which as we said earlier, is Undefined Behavior in itself. The above example leaves the argument qas a pointer to int in order to focus on the important change with respect to the original, but if the second argument can be misaligned, it would be better to declare it as a pointer to char, so as not to force the construction of a misaligned pointer to int when the function is called.

When targeting x86-64, GCC produces the code we intended but did not get with the original function h:

h:
        movl    $1, (%rdi)
        movl    $1, (%rsi)
        movl    (%rdi), %eax
        ret

This assembly code reads back the contents pointed to by the first argument (%rdi) in order to return it (in %eax) because the compiler is aware that accessing memory through the second argument (%rsi) may have changed it. The call tomemcpy in the source code is free: it is not translated to a function call, and not even to a single unnecessary instruction.

By contrast, when generating assembly code for an architecture for which the direct memory access would not produce the intended result, such as armv5, GCC, having no shorter and more expedient version, keeps the call tomemcpy. The armv5 ISA is a bit quirky, as RISC ISAs tend to be, so that on a processor implementing it, the misaligned memory access may not crash, but in any case, it would not produce the same result as the call to memcpy, hence GCC not replacing the latter by the former. This shows that GCC, while translating the statement *q = 1;, is assuming the int access to be aligned when it chooses to translate it to the single “store” instruction str r3, [r1].

Does a lot of existing C code do this?

It is difficult to tell how much existing code does this. The optimization described in this post is only implemented in GCC, and it is focused enough that you wouldn’t expect it to be applied very often(just wait until C code is increasingly compiled with Link-Time Optimizations, though). At a time when the popular ISAs mostly provide the expected behavior on misaligned accesses, the crime of misaligned memory accesses is seldom reported, but this is only by lack of witnesses.

One data point is the fast compression library LZO, which contains the following lines, intended to do the right thing on each of several possible target platforms:

#if (LZO_ARCH_ALPHA)
#  define LZO_OPT_AVOID_UINT_INDEX          1
#elif (LZO_ARCH_AMD64)
#  define LZO_OPT_AVOID_INT_INDEX           1
#  define LZO_OPT_AVOID_UINT_INDEX          1
#  ifndef LZO_OPT_UNALIGNED16
#  define LZO_OPT_UNALIGNED16               1
#  endif
#  ifndef LZO_OPT_UNALIGNED32
#  define LZO_OPT_UNALIGNED32               1
#  endif
#  ifndef LZO_OPT_UNALIGNED64
#  define LZO_OPT_UNALIGNED64               1
#  endif
#elif (LZO_ARCH_ARM)
#  if defined(__ARM_FEATURE_UNALIGNED)
#   if ((__ARM_FEATURE_UNALIGNED)+0)
#    ifndef LZO_OPT_UNALIGNED16
#    define LZO_OPT_UNALIGNED16             1
#    endif
#    ifndef LZO_OPT_UNALIGNED32
#    define LZO_OPT_UNALIGNED32             1
#    endif
#   endif
#  elif 1 && (LZO_ARCH_ARM_THUMB2)
 
...
 
#if (LZO_OPT_UNALIGNED32)
LZO_COMPILE_TIME_ASSERT_HEADER(sizeof(*(lzo_memops_TU4p)0)==4)
#define LZO_MEMOPS_COPY4(dd,ss) \
    * (lzo_memops_TU4p) (lzo_memops_TU0p) (dd) = * (const lzo_memops_TU4p) (const lzo_memops_TU0p) (ss)
#elif defined(lzo_memops_tcheck__)
#define LZO_MEMOPS_COPY4(dd,ss) \
    LZO_BLOCK_BEGIN if (lzo_memops_tcheck__(lzo_memops_TU4,4,1)) { \
        * (lzo_memops_TU4p) (lzo_memops_TU0p) (dd) = * (const lzo_memops_TU4p) (const lzo_memops_TU0p) (ss); \
    } else { LZO_MEMOPS_MOVE4(dd,ss); } LZO_BLOCK_END
#else
#define LZO_MEMOPS_COPY4(dd,ss) LZO_MEMOPS_MOVE4(dd,ss)
#endif

You will have noticed that the code wants to perform misaligned accesses, but is written to detect at compile-time platforms where misaligned accesses would fail, and in these cases, to avoid them.

This issue pointed out in Pavel Zemtsov’s 2016 post and in the present one is that the above #ifdef nest, when it picks the simple uint32_t lvalue access for the x86-64 target architecture (since x86-64 processors allow these memory accesses), exposes the code to be mistranslated by the compiler, for loop vectorization purposes or for optimization purposes.

Conclusion

This blog post is an extended version of a ticket I opened on GCC’s Bugzilla, where I suggested as a new feature a commandline option to make GCC not assume that memory accesses are aligned. The reaction of the GCC developers confirms that this behavior is here to stay. Clang developers, if you asked them, would reserve the right to make Clang behave in the same way, especially now that GCC has breached the topic. The conclusion is that as a modern C developer, you should always avoid misaligned memory accesses, and use memcpy to or from a temporary variable instead. Thememcpy call will be free as long as the code is compiled with an optimizing compiler for a platform that allows misaligned memory accesses.

Acknowledgments

The following people have contributed context information in this post, participated in a discussion that lead to the discovery being written up, improved the wording of some sentences, or had their joke stolen in this post: hikari, Alexander Monakov, David Monniaux, Markus F.X.J. Oberhumer, John Regehr, Miod Vallat, Ashley Zupkus.

Rich Felker, maintainer of the musl libc, recently tweeted to ask:

Anyone want to guess what gcc generates for a==b?0:a-b ? Any ideas why?

The answer to the first question is that when a and b are two pointers to char, GCC generates a sequence of several instructions, including a “conditional move” instruction, for the source-level construct a==b?0:a-b:

movq    %rdi, %rax
movl    $0, %edx
subq    %rsi, %rax
cmpq    %rsi, %rdi
cmove   %rdx, %rax

Of these five instructions, just the first and the third would be sufficient to produce the same result. On the architecture targeted by GCC here, applying the SUB instruction to two pointers that satisfy a==b can only produce a result of zero. In the case where a is a pointer one-past to some object and b a pointer to the beginning of another object, the standard allows a==b to be true or false, but in this case the source-level construct a-b is undefined, and any value computed by SUB is a valid result too.

One way to make GCC generate only the first and the third instructions would be to write a-b. Unfortunately, the C standard leaves this expression undefined when a and b are both null pointers, whereas a==b is defined (and is true). If GCC documented that it allows a null pointer to be subtracted from another (and that the result is 0), this would be a safe alternative when targeting GCC. As far as I know, however, GCC does not document this behavior. Since GCC does not document it and the C standard leaves it undefined, GCC could implement a new optimization tomorrow that improves its SPECint score by 0.5% while breaking programs relying on this expression.

The situation is similar to that of implementing rotate in C in 2013. Shifting an uint32_t by 32-n is undefined if n can be 0, but, at the time, Clang would only optimize to the efficient ROL instruction the pattern (x << n) | (x >> (32-n)) , to the exclusion of n ? (x << n) | (x >> (32-n)) : x or (x << n) | (x >> (-n%31)). Sometimes, in the transition from C-as-it-was-written-in-1990 to modern C, the compiler forces developers to write code circumlocutions to protect themselves from UB-based optimizations, and then punishes them for the circumlocutions.

Writing a sound static analyzer for C implies, first and foremost, formalizing the language that the analyzer will allow programs to use. “Just using the standard as reference” is illusory: in several places, the C standard is ambiguous, or even self-contradictory, enough that what matters is the consensual interpretation that compiler authors have arrived to. Sometimes the situation may be too obscure to even have been discussed. A question I asked myself in 2011 is somewhat related to Rich’s: when a is a null pointer and b is a valid pointer, a < b is left undefined by the standard but compilers currently produce code that makes this expression evaluate to 1, and existing code relies on this. Then, we chose to warn for pointer comparisons and to allow the subtraction of null pointers. Maybe the latter allowance is a decision that should be revisited now, since there exists at least one person in the world, Rich, who cares about this case.

Mandatory “no sane compiler would optimize this” post-scriptum

LLVM assuming that since x << n appears in the source code, n cannot be greater than 32 has already caused unintended behavior.

In order to break programs that rely on a-b when both a and b are null pointers, a compiler would only need to propagate the information that a and b aren't null pointers from any pointer subtraction involving them. This is as easy as assuming that a pointer is not null if it was passed to memcpy, even if that was with a size that was not known to be nonzero, and GCC already does this.

How can essential operators be better prepared to face upcoming cybersecurity challenges, whether they are located within the EU or elsewhere in the world?

The European Commission and the High Representative have proposed concrete measures to ensure safety and security of essential operators, betting on cooperation across member states and across EU structures.

These concrete measures can be found in this cybersecurity factsheet that shows how European citizens and businesses rely on digital services & technologies. It also highlights the rise of cyber incidents and attacks, but also underlines that awareness and knowledge of cybersecurity issues is still insufficient. The factsheet sums-up The Commission and High Representative’s different proposals to reinforce the EU’s resilience to cyber-attacks.

European Commission President, Jean-Claude Juncker could not have said it better “Cyber-attacks can be more dangerous to the stability of democracies than guns and tanks (…) Cyber-attacks know no borders and no one is immune.”

80% of European companies have experienced at least one cybersecurity incident last year (2015), according to PwC 2016 global state of information security survey. This is the biggest increase in Cyber-attacks in a decade.

In a context where attackers have unprecedented opportunities, means and scale of operations, exposed software must be hardened using the strongest techniques. TrustInSoft uses formal methods to ensure the total absence of vulnerabilities in legacy software, developed in simpler times and used in the infrastructures of essential operators.

My interest was piqued by a question on the questions-and-answers site Quora (the irritating one that tries to get you to register by limiting the number of answers you can view in a month otherwise; no, now you’re thinking of Medium; I mean the one that was doing this from the beginning). The question was about the differences between the B method and Frama-C. The existing answer at the time was making some good points, but I thought the phrase “First you are supposed to write or find some C source codes” in the existing answer was backwards. So I wrote my own answer there.

Working on improving and applying TIS Interpreter, with funding from the CII, we ended up implementing support for program-defined variadic functions. Recently, while applying TIS Interpreter to the musl standard C library implementation, we found one slight violation of the C standard in the way musl defined functions of the printf family. This post describes program-defined variadic functions and the ways they can be misused, and argues that they are worth supporting in TIS Interpreter.

What are variadic functions and why should we care?

Variadic functions, found in several programming languages, accept a variable number of arguments. As an example, we can imagine a little variadic function add(arg1, arg2, …, argn) that takes some numbers as arguments, and computes their sum, arg1 + arg2 + … + argn, whatever the number of passed arguments actually is.

In C, variadic functions are not that popular, and a seasoned C programmer, anticipating what this is going to entail, would probably avoid specifying and implementing such an add function. Nevertheless, in some cases, the possibility of going beyond functions with fixed number and type of arguments is convenient. When, in the 1990s, C was still considered and used as a high-level language, variadic functions were a reasonable solution in situations where the flexibility they provided made a difference with more cumbersome alternatives. An especially good example of such a situation is for input and output formatting using format strings. Because of that, even though a contemporary C programmers would usually avoid defining new variadic functions, many are present in existing C software, notably in legacy code.

The printf function in C

Let us take a closer look at C’s ubiquitous printf function. Its declaration is a part of the stdio.h standard library header file and it looks like as follows:

int printf(const char * restrict format, ...);

The declaration states that the printf function takes:

• one mandatory argument called format of type const char * (the qualifier restrict declares that the pointer does not alias any memory location that the function will otherwise access and can be ignored for this discussion),
• and the subsequent ellipsis (i.e. ...) means that any number of additional arguments may follow.

The mandatory argument format here is the format string itself. The expected type of the remaining arguments is not established statically on the declaration level, but depends dynamically on the contents of this first argument. In the case of printf, this argument is a format string, and it is the conversion specifiers (the special patterns introduced with the % character) present in this format string that define the types and the number of arguments to be printed on the standard output. The conversion specifier %d expects an int argument and displays it in decimal style, the conversion specifier %c expects a char argument and displays it as an ASCII character, and so on; the list is long. The characters in the format string that are not conversion specifiers simply pass through unchanged.

A simple use of printf could be:

char c = 'X';
int i = 42;
printf("The %c is %d.", c, i);

This code snippet prints “The X is 42.” to the standard output when executed.

In a different context, the same printf function might be passed a double argument and a void* argument. Although this lax type handling has some advantages in the case of formatting functions (the same printf function can be used to print strings, floating-point values, pointers and integers), major dangers come with it. The main advantage is the flexibility that it offers: without it the whole printf function family could not exist in this form, and producing formatted outputs in C would be much more tedious. The danger is that this mechanism may give rise to a whole lot of significant type-safety related problems. If we follow section 7.21.6.1 of the ISO C11 standard dedicated to the fprintf function (of whom printf is a specialised version), we discover that both failure to provide enough arguments and a mismatch in a provided argument’s type cause Undefined Behavior. CWE-134: Use of Externally-Controlled Format String shows that the security risks involved, information leak and—through the %n formatter—foreign code execution, are real and should be taken seriously.

Home-brew variadic functions in C

The printf function is only the most ubiquitous example of a C function that takes a variable number of arguments. The C standard library not only contains several other variadic functions, but also provides the tools necessary for the programmer to define their own variadic functions. The ingredients are available in the stdarg.h header file.

Declaring, calling, and defining variadic functions

We have already seen with printf how to declare a variadic function. After providing a number of mandatory arguments, together with their types, we simply add an ellipsis (i.e. ...) after the last argument, which means additional arguments may follow:

int add(int n, ...);

We also know how to call such functions, as they are in fact called almost exactly like the normal ones. The fixed mandatory arguments are simply followed by the additional variable ones. Therefore the number of passed arguments can differ between different call sites of the same function:

int foo = add(3, 23, 12, 7);
int bar = add(2, 23, 19);

Defining variadic functions is a bit more complicated. The function’s mandatory arguments are accessed just the usual way, but a special mechanism is needed in order to access the variable ones. The stdarg.h header provides four variadic macros: va_start, va_arg, va_end, and va_copy, as well as the type va_list, which together make it possible to cycle through the additional arguments that have been passed to a variadic function:

• The type va_list holds the necessary information needed by the variadic macros. The traditional name of a variable of this type is ap, for argument pointer.
  Intuitively, we can imagine that an object of this type contains a pointer to the next variadic argument (or a list of remaining variadic arguments). Of course, as the interface is abstract, the actual implementation of this type is not known to the library user. The C standard only describes how it will behave if used correctly.
• The macro va_start(va_list ap, parmN) initializes the va_list object ap.
  Intuitively, after invoking va_start the ap object points to the first variadic argument passed to the function.
  (Note: The parmN parameter here must be the same as the name of the last non-variadic argument in the function definition, that is, the argument just before the .... The necessity of passing this parameter hints at the low-level details of the implementation.)
• The macro invocation va_arg(va_list ap, type) has the type and the value of the next variadic argument. Also, each invocation of va_arg on ap modifies ap so that subsequent arguments are returned in sequence. The type provided to the va_arg macro should match the actual type of the next argument.
  Intuitively, va_arg returns the argument that ap points to and makes ap point to the next one.
• Finally, the macro va_end(va_list ap) deinitializes the ap object. Each va_list object should be deinitialized before the function returns.
• For simplicity’s sake we will ignore the va_copy macro here, as it is not necessary for the examples in this post.

There is no built-in way (such as an additional variadic macro) to know from the inside of a variadic function how many arguments and of which types have been passed to it. The only way is to provide this information explicitly and consistently at each call site, and to retrieve it inside the variadic function. The usual approach is to encode it using the function’s mandatory arguments, exactly like in the case of printf‘s format string.

A full example

In order to see how this all works, let us implement the closest approximation that can be achieved in C of the add function that sums a variable number of arguments:

int add(int n, ...) {
  va_list ap;
  va_start(ap, n);
  int sum = 0;
  for (; n > 0; n--) {
    int next_arg = va_arg(ap, int);
    sum += next_arg;
  }
  va_end(ap);
  return sum;
}

The internal workings of function add are pretty straightforward:

1. The beginning:
   • First we declare a va_list object ap and we intialize it using the va_start macro. Now, intuitively, ap points to the first variadic argument of add.
   • Also, we initialize the sum variable to zero.
2. The middle:
   • n times we consume the next variadic argument, using the va_arg(ap, int) macro. Note that we expect each of the variadic arguments to be of type int and we expect their number to be equal at least n.
   • We add the subsequent arguments’ values to the variable sum.
3. The end:
   • We deinitialize the ap variable using the va_end macro.
   • We return the sum variable’s value, which is now (obviously) equal to the sum of the n variadic arguments.

Now, in order to perform a correct call to add we must at least make sure that:

• the number of variadic arguments that we pass to the function is not smaller than the value of the argument n passed in the same call (it is all right if more arguments are passed than consumed),
• and that all these n arguments are of type int.

Examples of some correct calls would be:

add(3, 23, 12, 7); /* == 42 */
add(1, 42); /* == 42 */
add(3, 23, 12, 7, 'x', 13.0, "hello"); /* == 42 */
add(0); /* == 0 */
add(-42); /* == 0 */

Variadic macros and the C standard

Now, please notice the inconspicuous at least, in “we must at least make sure that”, which found its way to the previous paragraph. Well, these are by far not the only conditions necessary to call the add function correctly. In fact the section of the C11 standard concerning variadic functions and variadic macros is complex and it provides numerous ways to introduce Undefined Behavior into programs that use the stdarg.h library header.

The C11 standard section 7.16, entitled Variable arguments <stdarg.h>, defines the semantics of the four variadic macros, as well as the va_list type, and thus decides how home-brew functions with variable arguments behave, and when they may misbehave. There are many constraints concerning correct usage of these macros, some pretty straightforward and direct, some subtle. Violating most of these constraints seems completely innocuous in practice for all common compilation platforms, while breaking others causes visible problems on some or all common compilation platforms.

Correct sequence of variadic macros invocations

Several constraints concerning the variadic macros are concerned with the order in which these macros are supposed to be invoked on a va_list object. The allowed order is strictly defined by the standard. The following rules paraphrase, in a simplified and more casual way, what the standard says on this subject (note that we omit, again, the va_copy macro):

• Each va_list object ap begins its life uninitialized.
• If ap is not initialized it may be initialized using the va_start macro.
• Once ap has been initialized, va_arg macro may be invoked on it at most number of times equal to the number of variadic arguments which were passed to the function.
• If a va_list variable has been initialized, it must be deinitialized in the same function before the function returns, using the va_end macro.
• This sequence can be repeated any number of times: after deinitializing ap with va_end we can initialize it again with va_start, and iterate on all the variadic arguments again (from the beginning) with va_arg, and then deinitialize it again with va_end.
• If any other sequence of events happens, the behavior is undefined.

This ends up to be a simple pattern, which resembles a finite state machine that validates how va_start, va_arg, and va_end (invoked on a given va_list variable) are allowed to be interwoven in a single function. Such machine for a 3 variadic arguments passed in the call would look like this:

Consuming too many variadic arguments

The interesting aspect of these rules is how the impact of violating each of them is differently visible in practice. For example, if we try to consume more variadic arguments than are available in the given call we will run into trouble quite quickly. Of course what happens exactly is compiler and platform dependent, but in most cases the implementation of the underlying Undefined Behavior will result in reading some random data from memory. Let us see a simple program that simulates such a situation:

/* FILE not_enough_args.c */

#include "stdarg.h"
#include "stdio.h"

int f(int fst, ...) {
  va_list ap;
  va_start(ap, fst);
  int x = va_arg(ap, int);
  printf("%d\n", x);
  va_end(ap);
  return x;
}

int main() {
  f(11);
  return 0;
}

In this program, the function f tries to consume one int variadic argument and in the call no argument is passed at all. On my machine compiling it with gcc and then executing ten times prints following values, which seem pretty random indeed:

1691332760
-262231160
1531375144
-1205239608
133570616
985826840
-1260096984
1604313000
-883866920
-473417640
-121339624

The unpleasant case of va_end macro

What may be more disturbing, disobeying many of the the other mentioned constraints concerning the sequence of variadic macro invocations will usually have no visible effect during both the program’s compilation and its execution. In particular, all the rules which involve the va_end macro appear to be optional in practice. The va_end macro is translated by most compilers on most architectures to a do-nothing operation (a fact recognised directly in the C standard rationale, section 7.15.1.3 : The va_end macro). As this macro is supposed to perform a clean-up after initializing and using the va_list object, and in most stdarg.h implementations there is simply nothing to clean up, thus the macro is actually not needed at all and may be just ignored. You might ask, why was it included in the standard in the first place? Following the C rationale again: those implementations that need it probably need it badly is the explanation.

The variadic arguments’ types

There are also several constraints which concern the types of the variadic arguments. Basically, the type provided when invoking the va_arg(ap, type) macro should be compatible with the actual type of the next variadic argument (with several well-defined exceptions, see the C11 standard section 7.16.1.1p2 for details). The danger related with the underlying Undefined Behavior is quite serious in this case, and definitely of the harmless-looking, but waiting to stab you in the back one day kind. As the size of C types may vary depending on compiler, the compilation options, and the platform, it is not hard to imagine situations when a given program works perfectly well on one configuration, where the two theoretically incompatible types happen to align well (and they happen to be passed through the function call exactly in the same way), and it fails miserably on another configuration, where exactly the same two types in the same circumstances do not behave the same anymore, and thus the variadic argument is recovered incorrectly, and suddenly there we have a nice shiny bug…

Let us look at a simplistic example that showcases the problem. In the following code we call the variadic function f passing two arguments, both of type long and value 42, and then we attempt to consume one variadic argument of size long long:

/* FILE type_mismatch.c */

#include "stdarg.h"
#include "stdio.h"

void f(int hello, ...) {
  va_list ap;
  va_start(ap, hello);
  long long b = va_arg(ap, long long);
  printf("%lld\n", b);
  va_end(ap);
}

int main(void) {
  f(0, (long) 42, (long) 42);
  return 0;
}

On my machine when I compile this source code with gcc using two different target options I get different results upon execution:

• Option -m64 selects 64-bit x86-64 build. In this case the first variadic argument’s value 42 of type long is read correctly, as the sizes of the types long and long long seem to match: the program prints 42.
• Option -m32 selects 32-bit i386 build. In this case the argument is read incorrectly: the program prints 180388626474 which is definitely not the value we expected.

This example is simplistic indeed, but it shows exactly the disturbing property that we were just talking about: on one configuration it works perfectly fine, and on another it does not. Of course here it is pretty evident that the two concerned types will not always match and that something might go wrong. However, if this kind of mismatch is well hidden in a much larger program which has many execution paths and #define directives all around the place, the existence of a potential problem will not be so obvious anymore. Furthermore, no amount of testing on a 64-bit i386 build will ever throw any doubt at the Works on My Machine certificate that we might have given this piece of code. But compiling and running on a 32-bit system tells a different story.

Support of variadic functions in TIS Interpreter

In TIS Interpreter we have recently implemented support for variadic functions written using the variadic macros from stdarg.h. TIS Interpreter, developed thanks to the funding of the CII and available as Open-Source, is an abstract interpretation tool for C programs, capable of finding and identifying a very large set of Undefined Behaviors and C standard violations. Now, with its newly gained proficiency in this particular domain, it can also discover problems concerning variable argument handling, like the ones mentioned above.

Let us see how TIS Interpreter handles the examples that we have introduced so far:

• • Interpreting the example where too many variadic arguments consumed produces the following warning:

not_enough_args.c:7:[value] warning: va_arg macro called when all the variadic arguments have been already used up; assert enough arguments

• • When we interpret the example where variadic argument types are not really matching we get:

type_mismatch.c:7:[value] warning: the actual type of the next variadic argument (long) does not match the type provided to the va_arg macro (long long); assert the type of each variadic arguments provided to a function matches the type given to the corresponding call to the va_arg macro

• • And as of the example that we did not explicitly state, with a va_end macro invocation removed from an otherwise correct program:

missing_va_end.c:13:[value] warning: local variable ap of type va_list in function add has been initialized using va_start or va_copy macro and has not been deinitialized by a matching va_end macro; assert va_list variable ap has been uninitialized using the va_end macro

All these warnings are extracted from the output of TIS Interpreter when we execute it directly on the code that we have seen here, simply like that:

$ tis-interpreter not_enough_args.c

The case of musl

Recently the support for variadic functions deemed itself very useful, as we were running musl code through TIS Interpreter. The musl library is an example of a perfect target for TIS Interpreter: it is an important and widely used Open Source component written in C, and it aims “to be correct in the sense of standards-conformance and safety”.

musl is a libc: an implementation of the standard library functionality described in the ISO C and POSIX standards. musl‘s main objectives are to be lightweight, fast, simple, free, and, as we have already emphasised, correct. It is a key component of the Alpine Linux, a security-oriented, small, simple, resource-efficient Linux distribution, very well adapted to use in software containers. The features of Alpine Linux make it a frequent choice for using in Docker containers, rumours say that it is even considered as the default platform option in the official Docker image library. And, as Docker is an extremely popular (the world’s leading according to its website) software container platform, musl happens thus to be a pretty widely deployed libc version. Hence our interest in it.

What did we find?

As musl is high-quality software written with standard-conformance in mind (POSIX standard for the interface it provides, C standard for its assumptions with respect to the compiler), we did not expect to find many issues to report. And effectively we have only managed to encounter minor transgressions of the C standard. One of these, which ultimately has been deemed important enough to be corrected, was present in the implementation of the printf and scanf variadic functions. In musl the implementation of these library functions is in fact based on the variadic macros from stdarg.h.

The issue was related to the type and value of the argument passed to the va_arg macro. Consider the program:

char dest[100];
int x = sprintf(dest, "%lld\n", -1LL);

These two lines are correct C. The type of the -1LL argument matches the format specifier %lld. Still, TIS Interpreter emits a warning when using this snippet to drive the sprintf implementation that was in musl at the time.

src/stdio/vfprintf.c:141: warning: although the type provided to the va_arg macro (unsigned long long) and the actual type of the next variadic argument (long long) are corresponding unsigned - signed variants of the same integer type, the actual value of the argument (signed) is negative thus it cannot be represented in the provided (unsigned) type

This warning refers to the Undefined Behavior that we have already come across earlier, described in C11 standard section 7.16.1.1:2:

(…) if type is not compatible with the type of the actual next argument (as promoted according to the default argument promotions), the behavior is undefined, except for the following cases:

• one type is a signed integer type, the other type is the corresponding unsigned integer type, and the value is representable in both types;
• one type is pointer to void and the other is a pointer to a character type.

So what happens here exactly? The next variadic argument at this point of the execution is the -1LL constant, which is a negative value of long long type. Deep inside the sprintf implementation, the va_arg macro expects at this moment is an argument of unsigned long long type. Though these two types are not compatible, we fall into one of two exception cases: one type is a signed integer type, the other type is the corresponding unsigned integer type. But this use of a type with a different signedness is only valid if the argument’s value exists in both the signed and the unsigned type, which is not the case for -1. Consuming -1LL with va_arg(…, unsigned long long) is undefined. And that is exactly what TIS Interpreter is warning about here.

A short investigation led to the va_arg invocation that consumed this variadic argument. It was the one at line 141 of the vprintf.c file, effectively expecting unsigned long long:

break; case ULLONG: arg->i = va_arg(*ap, unsigned long long);

The cause behind the issue is optimization in the vprintf.c file. Two symbols, LONG_IS_INT and ODD_TYPES, are defined conditionally and then employed, using #ifdef directives, to fiddle with the enum type related with handling the conversion specifiers and with the switch cases which select the correct va_arg invocation in the function pop_arg. Let us see exactly how the ODD_TYPES makes us get to the switch case with the unsigned long long type:

First, the symbol ODD_TYPES is defined or not, depending on the representation of certain types on the platform:

#if SIZE_MAX != ULONG_MAX || UINTMAX_MAX != ULLONG_MAX
#define ODD_TYPES
#endif

Then ODD_TYPES decides if LLONG is an actual enumeration tag or just a synonym for the ULLONG tag:

enum {
  /* ... */
  PTR, INT, UINT, ULLONG,
  /* ... */
#ifdef ODD_TYPES
  LLONG, SIZET, IMAX, UMAX, PDIFF, UIPTR,
#else
#define LLONG ULLONG
/* other #define directives here... */
#endif
  /* ... */
};

Finally, inside the pop_arg function’s switch statement the case corresponding to LLONG is conditionally avoided (as LLONG is in this situation just an alias for ULLONG, that would be de facto second ULLONG case in the switch):

switch (type) {
  /* ... */
  break; case ULLONG: arg->i = va_arg(*ap, unsigned long long);
  /* ... */
#ifdef ODD_TYPES
  break; case LLONG: arg->i = va_arg(*ap, long long);
  /* ... */
#endif

So what purpose did these type-related shenanigans serve? This optimization can shave off a few bytes from the compiled code by unifying certain execution paths: if these different types have the same underlying representation, they can be both treated in the same way. Unfortunately, as we have just seen, this optimization also introduces Undefined Behavior. After (see the discussion on the musl mailing list), a cleanup patch has been applied by Rich Felker, the primary author of musl, in this commit.

Conclusion

In an ideal world, this kind of optimization would not need to exist at the C level in the first place. If the compiler recognised what was going on in this situation, i.e. that two or more execution paths are equivalent on a given architecture, these two switch cases could be merged at compile-time. Then the programmer could just stick to the C standard, express their intentions, and get an executable as small as when applying the hack discussed above.

Luckily, in these particular circumstances, the efficiency impact of removing altogether this dubious optimization was negligible, so the choice was easy to make. In other cases though, if the difference in efficiency was more substantial, it might be less clear if sticking to the C standard is worth the price.

As a side-effect, this lead to a short discussion about compilers producing efficient code from the type-safe and correct version that musl now uses exclusively. It is a pleasant convergence that a problem uncovered in musl with TIS Interpreter revealed an instance of a compilation challenge which was being worked on at the same time.

Acknowledgments: Shafik Yaghmour provided comments on an early version of this post, and it was edited by Pascal Cuoq. Joakim Sindholt provided the cleanup patch that was merged into the musl tree by Rich Felker.

The libksba library, used by GnuPG, provides functions for parsing X.509 cryptographic certificates. I was testing libksba with TIS Interpreter a little over a year ago. One of the bugs I found then illustrates a point I would like to make now.

The bug

Consider this function, as it was present in libksba two years ago:

const char *
ksba_cert_get_digest_algo (ksba_cert_t cert)
{
  gpg_error_t err;
  AsnNode n;
  char *algo;
  size_t nread;

  if (!cert)
    return NULL;  /* Ooops (can't set cert->last_error :-().  */

  if (!cert->initialized)
    {
       cert->last_error = gpg_error (GPG_ERR_NO_DATA);
       return NULL;
    }

  if (cert->cache.digest_algo)
    return cert->cache.digest_algo;

  n = _ksba_asn_find_node (cert->root, "Certificate.signatureAlgorithm");
  if (!n || n->off == -1)
    err = gpg_error (GPG_ERR_UNKNOWN_ALGORITHM);
  else
    err = _ksba_parse_algorithm_identifier (cert->image + n->off,
                                            n->nhdr + n->len, &nread, &algo);
  if (err)
    cert->last_error = err;
  else
    cert->cache.digest_algo = algo;

  return algo;
}

The source code above contains the bug. The bug can almost be found by inspection of the function, inferring contents of types and behavior of callees from the way they are used. I have only removed commented-out code from the original. If you think that you have identified the bug I found one year ago, but that it may depend how the function ksba_cert_get_digest_algo is used, you may be on the right track. Here is how ksba_cert_get_digest_algo is invoked in tests/cert-basic.c:

  oid = ksba_cert_get_digest_algo (cert);
  s = get_oid_desc (oid);
  printf ("  hash algo.: %s%s%s%s\n",
          oid?oid:"(null)", s?" (":"",s?s:"",s?")":"");

If on the other hand, even with this clue, you are still finding the entire function ksba_cert_get_digest_algo too tedious to review, here is a synthetic view that makes that bug stand out:

const char *
ksba_cert_get_digest_algo (ksba_cert_t cert)
{
  …
  char *algo;
  …
  n = _ksba_asn_find_node (cert->root, "Certificate.signatureAlgorithm");
  if (!n || n->off == -1)
    err = gpg_error (GPG_ERR_UNKNOWN_ALGORITHM);
  else
    err = _ksba_parse_algorithm_identifier (cert->image + n->off,
                                            n->nhdr + n->len, &nread, &algo);
  if (err)
    cert->last_error = err;
  else
    cert->cache.digest_algo = algo;

  return algo;
}

The bug is that the automatic variable algo remains uninitialized until _ksba_asn_find_node is called. When that function succeeds, &algo is passed as argument of the function _ksba_parse_algorithm_identifier (without looking at it, we can assume that that function does initialize algo in all cases). The fact remains that when _ksba_asn_find_node fails because of the condition !n || n->off == -1 being true, the variable algo remains uninitialized until its “value” is returned as the result of the function.

The anecdote

The funny thing about this bug is that it is very easy to produce inputs for. I was using afl, an efficient and easy-to-use fuzzer, to generate testcases. This bug was the second one I found, right after I set up afl and TIS Interpreter to work together on libksba. It turned up just after afl generated an input that demonstrated a crash caused by an unrelated first bug. Whenever the target software crashes, afl generates a README.txt file to invite the user to report their success to afl’s author. This is smart timing: when using a fuzzer to find bugs, producing an input that causes a direct crash is one of the best possible outcomes. afl’s README file is thus a subtle declaration of victory: you only see it when afl has done a good job.

The README, a pure ASCII file intended for human consumption, of all inputs pretending to be X.509 certificates, also happens to trigger the uninitialized-variable-use bug described in the first part of this post. Let they who would not have used the shell command for i in findings_dir/crashes/* ; do run_in_tis_interpreter.sh $i ; done throw the first stone.

No great coincidence happened here, neither was the README.txt file generated designed to look fiendishly similar to a X.509 certificate. Any brute-force purely random fuzzer would have instantly produced a file that triggered the bug shown. In good time, afl would have found one too—and, importantly, it would have recognized that such an input caused a different execution path than less obviously incorrect certificates to be followed inside libksba’s cert-basic test program, and would have set it apart for later inspection.

Epilog

The crash initially found by afl was fixed in a timely manner by Werner Koch in commit a7eed17, and the uninitialized-variable-use bug described in this post was fixed in commit 3f74c2c.

I never formally reported any of afl’s numerous findings to afl’s author, despite the instructions in the input file. Well, this post can be my report: all the bugs reported by me in libksba in 2016 were found using afl and TIS Interpreter together. This post is but an example to illustrate how well these two tools work together.

afl had been used on libksba before (for instance this 2014 vulnerability is listed as having been found using afl). But although the uninitialized-variable-use bug is very shallow and can be evidenced by throwing any README file at cert-basic, the bug was probably missed because it did not cause a crash. Barring weird optimizations, when executing a binary not instrumented to detect the use of uninitialized variables, the variable’s value is what happened to be on the stack. The stack is full of valid addresses: addresses of variables and buffers that have previously served, but also addressed of call sites to return to. Reading from any of these addresses, it is likely that a zero will be found before the end of the page (code contains plenty of null bytes because of how constants in instructions are typically encoded, and data contains plenty of null bytes too, of course). This means that running cert-basic directly does not reveal, via a crash, that something wrong happened. All that happens is that instructions or (possibly secret) data is printed as if it were a string. Since there are no a priori expectations for what cert-basic should print when passed an invalid file, this is difficult to notice.

One solution, of course, is to have used MemorySanitizer (MSan for short) to compile libksba’s cert-basic. One might speculate that the bug was not found earlier because MSan’s instrumentation is incompatible with ASan’s, and that users of afl, if they use a sanitizer at all, use ASan in order to find the most dangerous memory bugs.

TIS Interpreter takes more time to run a test program than it takes to compile and execute this test program with MSan or ASan instrumentation, but TIS Interpreter finds all the problems that these two sanitizers find, and more.

afl can produce minimal test suites that exert all the different execution paths it was able to identify in the target programs. This feature enables TIS Interpreter to be used harmoniously together with it.

If the only way to use the two together was to run TIS Interpreter on every input that afl generated and discarded, then the collaboration between the two tools would be fruitless. The interesting inputs would be lost in a sea of uninteresting ones and TIS Interpreter’s comparatively slow speed would make it seem like it is not finding anything. But since afl can produce minimal test suites, covering a lot of different behaviors of a typical parser with a few hundred testcases, these few hundred testcases should definitely be run in the best detector of undefined behavior that exists, even if that detector uses up a few seconds per testcase. And, for C programs, the best detector of undefined behavior in terms of detected undefined behaviors is arguably TIS Interpreter.