What every C programmer should know about Undefined Behavior. Part 2/3

Part 1
Part 2
Part 3

In the first part of our cycle, we discussed what undefined behavior is and how it allows C and C ++ compilers to generate more high-performance applications than “safe” languages. In this post we will discuss what “unsafe” C really is, explaining some completely unexpected effects caused by undefined behavior. In the third part, we will discuss how “friendly” compilers can mitigate some of these effects, even if they are not required to do so.

I like to call it “Why undefined behavior often scares and terrifies C programmers.”
')

Compiler Optimization Interaction Produces Unexpected Results

A modern optimizing compiler contains many optimizations that work in a certain order, sometimes repeated several times, and this order may change as the compiler evolves (that is, when new releases are released).

Also, different compilers have significantly different optimizers. Since the optimizations work as different stages of code conversion, various effects can occur when the preceding stages change the code.

Consider this stupid example (simplified from the real bug example in the Linux kernel) to make it more specific:

void contains_null_check(int *P) { int dead = *P; if (P == 0) return; *P = 4; } 

In this example, the code "explicitly" checks for a null pointer. If the compiler starts the pass of deleting an unreachable code (“Dead Code Elimination”) before passing the deletion of redundant checks for null (“Redundant Null Check Elimination”), then we will see that two code transformations will be performed:

 void contains_null_check_after_DCE(int *P) { //int dead = *P; // deleted by the optimizer. if (P == 0) return; *P = 4; } 

and then:

 void contains_null_check_after_DCE_and_RNCE(int *P) { if (P == 0) // Null check not redundant, and is kept. return; *P = 4; } 

However, the optimizer may be structured differently, and may run the RNCE before the DCE. Then the following two transformations will be performed:

 void contains_null_check_after_RNCE(int *P) { int dead = *P; if (false) // P was dereferenced by this point, so it can't be null return; *P = 4; } 

and then the redundant code is removed:

 void contains_null_check_after_RNCE_and_DCE(int *P) { //int dead = *P; //if (false) // return; *P = 4; } 

For many programmers, removing a null check from a function would be very unexpected (and they will blame the compiler for the bug). However, both options, "contains_null_check_after_DCE_and_RNCE", and "contains_null_check_after_RNCE_and_DCE", are perfectly true optimized form of "contains_null_check" in accordance with the standard, and both optimizations are important for improving the performance of various applications.

Although this is a rather simple and contrived example, such things happen all the time with inline functions. Inline functions open up many possibilities for future optimizations. This means that if the optimizer decides to inline the function, other local optimizations will be made that change the behavior of the code. This is absolutely correct, both from the point of view of the standard, and from the practical point of view, to increase productivity.

Undefined behavior and security should not mix

The family of C-like programming languages ​​is used for a wide range of critical security code, such as kernels, setuid daemons, web browsers, etc. This code works with “hostile” input data and bugs in it can lead to any sort of security problems. One of the best known advantages of C is that it is relatively easy to understand what is happening just by reading the code.

However, indefinite behavior deprives the language of this property. For example, most programmers will assume that “contains_null_check” in the example above performs a null check. Although this example is not so scary (this code can break something, if it is passed null, which is relatively easy to detect when debugging) there are a large number of quite reasonable looking C code fragments that are in fact completely wrong. This issue affects many projects (including the Linux Kernel, OpenSSL, glibc, etc.) and even forced CERT to publish a notification about the GCC vulnerability (although I personally believe that all widely used optimizing C compilers are vulnerable, not just GCC).

Consider an example. Imagine carefully written C code:

 void process_something(int size) { // Catch integer overflow. if (size > size+1) abort(); ... // Error checking from this code elided. char *string = malloc(size+1); read(fd, string, size); string[size] = 0; do_something(string); free(string); } 

This code performs a check to make sure that enough memory is allocated for reading from the file (as you need to add a terminating null), and exits if an integer overflow occurs. However, in this example, the compiler can (according to the standard) remove the check. This means that the compiler can turn the code into this:

 void process_something(int *data, int size) { char *string = malloc(size+1); read(fd, string, size); string[size] = 0; do_something(string); free(string); } 

When compilation occurs on a 64-bit platform, there is a possibility of a bug when “size” equals INT_MAX (perhaps, this is the size of the file on the disk). Let's see how awful it is: when checking the code, nothing is detected, since checking the variable for overflow looks reasonable. When testing the code, there are no problems, unless you specifically test this execution path. It seems the code can be considered safe until someone decides to exploit the vulnerability. This is a very unexpected and rather awful class of bugs. Fortunately, just fix it: just use "size == INT_MAX" or something similar.

It turns out that overflowing the whole is a security issue for many reasons. Even if you use fully qualified integer arithmetic (either using -fwrapv or using unsigned integers), there remains a class of possible bugs related to the overflow of integers. Fortunately, these bugs are noticeable in the code and well known to security auditors.

Debugging optimized code may become pointless.

Some people (for example, low-level embedded-programmers who like to watch the generated machine code) work with constantly enabled optimization. Since the code often has bugs at the beginning of development, these people observe a disproportionate amount of unexpected optimizations that can lead to difficult-to-manage problems during program execution. For example, accidentally skipping “i = 0” in the example “zero_array” in the example from the first article, we allow the compiler to completely remove the loop (turning zero_array into “return;”) because this would be using an uninitialized variable.

Another interesting case may occur when there is a global function pointer. A simplified example looks like this:

 static void (*FP)() = 0; static void impl() { printf("hello\n"); } void set() { FP = impl; } void call() { FP(); } 

which clang optimizes in:

 void set() {} void call() { printf("hello\n"); } 

It can do this because the null pointer call is not defined, which allows us to assume that set () should be called before call (). In this case, the developer forgot to call set (), the program does not fall on null dereferencing, and the code will break if someone else does the debug build.

Such bugs are tracked: if you suspect something suspicious, try building with -O0, and the compiler will most likely not perform optimizations.

"Working" code that uses undefined behavior can break if something changes in the compiler.

We have considered many cases in which code that “seems to be working” suddenly breaks down when a newer version of LLVM is used for compilation, or when an application is ported from GCC to LLVM. Although LLVM itself can have one or two bugs, this most often happens due to the fact that hidden bugs appeared in the application due to the compiler. This can happen in many different cases, here are two examples:

1. An uninitialized variable that previously accepted a zero value by luck, and now is placed in another register that does not contain a zero. This behavior often manifests itself with changes in the allocator registers.

2. An array overflow on the stack overwrites the actual variables instead of the “dead” ones. This happens when the compiler reorders variables on the stack, or more aggressively packs variables with a non-overlapping lifetime into stack space.

An important and frightening thing to discover is that almost any optimization based on unspecified behavior can lead to bugs at any time in the future. Inline functions, loop expansion, and other optimizations will work better, and a significant part of them is done through secondary optimizations, as shown above.

This makes me very sad, in part because the compiler is almost inevitably being blamed, and also because a huge amount of C-code is a time bomb waiting to explode. And it's even worse because ...

There is no reliable way to ensure that a large code base does not contain UB

This is a very bad situation, because in fact there is no reliable way to determine that there is no UB in a large-scale application and that it will not break down in the future. There are many useful tools that can help you find some bugs, but nothing gives you complete confidence that your code will not break in the future. Let's look at some of the options, their strengths and weaknesses.

1. Valgrind is a fantastic tool for finding all kinds of uninitialized variables and other memory bugs. Valgrind is limited by the fact that it is rather slow, and can only search for bugs that already exist in the generated machine code (and cannot find what was removed by the optimizer), and does not know that the source code was written in C (and therefore, it cannot find the bugs of the shift type by an amount larger than the size of the variable or overflow of the signed integer number).

2. Clang has an experimental mode -fcatch-undefined-behavior, which inserts runtime checks to look for violations, such as going beyond the limits of the shift range, some simple errors exceeding the boundaries of arrays, etc. These checks are limited, because they slow down the application, and can not help with the dereference of an arbitrary pointer (and Valgrind can), but can find other important bugs. Clang also fully supports the -ftrapv flag (not to be confused with -fwrapv), with which you can catch bugs in runtime with overflow of signed integers (GCC also has such a flag, but in my experience it is very unreliable and buggy). Here is a little demo -fcatch-undefined-behavior:

 $ cat tc int foo(int i) { int x[2]; x[i] = 12; return x[i]; } int main() { return foo(2); } $ clang tc $ ./a.out $ clang tc -fcatch-undefined-behavior $ ./a.out Illegal instruction 

3. Compiler messages are good for finding some classes of bugs, such as uninitialized variables and simple integer overflows. There are two main limitations: 1) there is no dynamic information about the code execution and 2) the analysis must be very fast, because any analysis increases the compilation time.

4. The Clang static analyzer performs a much more in-depth analysis, trying to find bugs, including using UB, such as null pointer dereferencing.

You can think of it as an enhanced analysis tool compared to compiler warnings, since it does not have time constraints, like ordinary warnings. The main drawback of the static analyzer is that it: 1) does not have dynamic information about the program’s workflow and 2) is not integrated into the normal development process (although its integration with XCode 3.2 and later is fiction).

5. The LLVM “Klee” subproject uses symbolic analysis to “try every possible path” through the code to find bugs in the code and generate a test. This is a great little project that is mainly limited by the fact that it is impractical to run on large applications.

6. Although I have never tried it, the C-Semantics tool from Chucky Ellison and Grigori Rosa is very interesting because it can find some classes of bugs (such as violations of the following points). It is still in the state of a research prototype, but may be useful for finding bugs in (small and limited) programs. I recommend reading John Reger's post to get more information.

So, we have a lot of tools for finding bugs, but there is no good way to prove that there is no UB in the application. Imagine that there are tons of bugs in real-world applications, and that C is used in a wide range of critical applications, and it scares. In our last article, I will look at the various options that the C compiler has in order to handle UB, especially paying attention to Clang.