UB-2017. Part 1

We often hear that some people claim that problems arising from Undefined Behavior (UB) in C and C ++ are mainly resolved through widespread use of dynamic verification tools such as ASan, UBSan, MSan, and TSan. We will show the obvious here: despite the fact that in recent years there have been many excellent improvements in these tools, the problems of UB are far from being resolved, and we will consider the situation in detail.



Valgrind and most sanitizers are designed for debugging: they generate friendly diagnostic messages related to cases of undefined behavior that occurred during testing. Such tools are extremely useful and help us evolve from a state of the world in which almost every non-trivial C and C ++ program runs as a continuous UB flow to a state of the world in which a significant number of important programs are mostly UB free in their most common configurations and use cases .

The problem with dynamic debugging tools is that they don’t do anything to help us deal with the worst cases of UB: we don’t know how they work during testing, but someone else can figure out how UB will appear in the release and use it as a vulnerability. The problem boils down to quality testing, which is difficult. Tools like afl-fuzz are good, but they hardly even started to touch large programs. One way to get around the testing problem is to use static UB detection tools. They are constantly being improved, but confident and accurate static analysis is not necessarily easier to do than to achieve good test coverage. Of course, these two techniques are aimed at solving one problem, identification of possible ways to execute the program, but from different angles. This problem has always been very complex, and perhaps always will be. A lot has been written about finding UB through static analysis, in this article we will focus on dynamic tools. Another way to solve the testing problem is to use UB “mitigation” tools: they turn undefined behavior into defined behavior when using C and C ++, effectively achieving some of the benefits of using safe programming languages. The difficulties in designing tools that mitigate UB are as follows: Another way to solve the testing problem is to use UB “mitigation” tools: they turn undefined behavior into defined behavior when using C and C ++, effectively achieving some of the benefits of using safe programming languages. The difficulties in designing tools that mitigate UB are as follows: Another way to solve the testing problem is to use UB “mitigation” tools: they turn undefined behavior into defined behavior when using C and C ++, effectively achieving some of the benefits of using safe programming languages. The difficulties in designing tools that mitigate UB are as follows:

- do not break the code in corner cases
- have low overhead costs
- do not add additional vulnerabilities, for example, requiring linking with an unchecked runtime library
- make it difficult to attack
- combine with each other (in contrast, some debugging tools, such as ASan and TSan, are not compatible, and require two test case runs for a project that needs both tools).

Before looking at individual cases of UB, let's define our goals. They apply to any C and C ++ compiler.

Goal 1:each case of UB (yes, there are about 200 of them, we will give a complete list at the end) must either be documented as having a certain behavior, or be diagnosed by the compiler as a fatal error, or, as a last resort, have a sanitizer that detects UB in runtime. This should not cause controversy, it’s like the minimum requirement for development in C and C ++ in the modern world, where network packets and compiler optimizations can be used by attackers.

Goal 2:each UB case must be either documented, or diagnosed by the compiler as a fatal error, or have an optional “mitigation” mechanism that satisfies the previous requirements. This is harder. We believe that this can be achieved on many platforms. The kernels of operating systems and other code for which speed is critical, needs to use other technologies, such as formal methods. In the remainder of this article, we will examine the current situation for various classes of indefinite behavior.

Let's start with the big UB class.

Spatial Memory Safety Violations

Description: Access outside the repository and even creating such pointers is UB in C and C ++. In 1988, the Morris worm hinted at what awaits us in the next N years. As we know, N> = 29, and perhaps the value of N will reach 75.

Debugging: Valgrind and ASan are great debugging tools. In many cases, ASan is better because it contributes less overhead. Both tools represent addresses as 32- or 64-bit values, and reserve the forbidden red zone around valid blocks. This is a reliable approach, it allows you to seamlessly work with ordinary binary libraries that use this tool, and also supports regular code that has operations for converting pointers to integers.

Valgrind works from executable code, cannot insert red zones between stack variables, because the placement of objects on the stack is already encoded in the offset values ​​in the instructions accessing the stack, and it is impossible to change the addresses of accessing the stack “on the fly”. As a result, Valgrind has limited support in detecting errors with manipulating objects on the stack. ASan runs at compile time and inserts red zones around stack variables. Stack variables are small and numerous, and address space and locality considerations prevent the use of very large red zones. With default settings, the addresses of two adjacent local integer variables x and y will be separated by sixteen bytes. In other words, the verifications produced by ASan and Valgrind relate only to the placement of objects in memory,

Some disadvantage of ASan and Valgrind is that they can skip UB if some code has been removed by the optimizer and cannot be run, as in the example.

Mitigation : We have long had an mitigation mechanism for unsafe memory operations, including ASLR, "stack canaries", "protected allocators", and NX bits.







Later production-grade CFI (control flow integrity control) became available. Another interesting recent development is pointer identification in ARMv8.3. This article provides an overview of UB mitigations related to memory security.

ASan's serious flaw as a means of mitigating UB is shown here:

$ cat asan-defeat.c
#include 
#include 
#include 
char a[128];
char b[128];
int main(int argc, char *argv[]) {
  strcpy(a + atoi(argv[1]), "owned.");
  printf("%s\n", b);
  return 0;
}
$ clang-4.0 -O asan-defeat.c
$ ./a.out 128
owned.
$ clang-4.0 -O -fsanitize=address -fno-common asan-defeat.c
$ ./a.out 160
owned.
$ 

In other words, ASan will simply force the attacker to calculate a different offset in order to spoil the desired region of memory. (Thanks to Yuri Gribov for prompting us to use the -fno-common flag in ASan.)

In order to mitigate this variant of undefined behavior, a real check of going abroad should be performed, and not a simple check that every access to memory occurs in a valid region. Memory security is the gold standard here. Although there are many academic works on memory security, and some demonstrate approaches with reasonable overhead and good compatibility with existing software, they are not widely used. Checked Cis is a very cool project in this area.

Conclusion:Debugging tools for errors of this kind are very good. It is possible to substantially mitigate this type of UB, but in order to completely eliminate it, you will need complete type and memory security.

Temporal Memory Safety Violations

Description: Violation of the security of temporary memory objects is any use of a memory location after the expiration of its lifetime. This includes addressing automatic variables outside the scope of these variables, using after freeing, using a dangling pointer to read or write, double freeing, which can be very dangerous in practice, because free () changes the metadata that usually belongs to the block being freed. If a block has already been freed, writing to this data can damage data used for other purposes, and, in principle, can have the same consequences as any other invalid record.

Debugging:ASan is designed to detect use-after-release bugs that often lead to difficult to reproduce, erroneous behavior. He does this by quarantining the freed blocks, preventing their immediate reuse. For some programs and inputs, this can increase memory consumption and decrease locality. The user can configure the quarantine size to find a compromise between false positives and resource utilization.

ASan can also detect the addresses of automatic variables that survive the scope of these variables. The idea is to turn automatic variables into blocks allocated in dynamic memory, which the compiler automatically allocates when execution enters a block and releases it (while quarantining it) when the execution leaves the block. This option is disabled by default, because it wants the program even more voracious in terms of memory.

The violation of the security of temporary memory objects in the program below causes a difference in behavior during default optimization and -O2. ASan can detect a problem in the program without optimization, but only if the detect_stack_use_after_return option is set, and only if it has not been compiled with optimization.

$ cat temporal.c
#include 
int *G;
int f(void) {
  int l = 1;
  int res = *G;
  G = &l;
  return res;
}
int main(void) {
  int x = 2;
  G = &x;
  f();
  printf("%d\n", f());
}
$ clang -Wall -fsanitize=address temporal.c
$ ./a.out 
1
$ ASAN_OPTIONS=detect_stack_use_after_return=1 ./a.out 
=================================================================
==5425==ERROR: AddressSanitizer: stack-use-after-return ...
READ of size 4 at 0x0001035b6060 thread T0
^C
$ clang -Wall -fsanitize=address -O2 temporal.c
$ ./a.out 
32767
$ ASAN_OPTIONS=detect_stack_use_after_return=1 ./a.out 
32767
$ clang -v
Apple LLVM version 8.0.0 (clang-800.0.42.1)
...

In some other examples, the sanitizer cannot detect a UB that was deleted by the optimizer, and thus is safe, since a remote code with UB cannot have consequences. But this is not the case! A program is meaningless in any case, but an unoptimized program works deterministically, as if the variable x were declared static, while an optimized program in which ASan did not find anything suspicious behaves deterministically and reveals an internal state that is not intended to be could see:

$ clang -Wall -O2 temporal.c
$ ./a.out 
1620344886
$ ./a.out 
1734516790
$ ./a.out 
1777709110

Mitigation: As discussed above, ASan is not designed to protect against vulnerabilities, but various protected allocators are available and use the same quarantine strategy to close the “use after release” vulnerability.

Conclusion: Use ASan (along with “ASAN_OPTIONS = detect_stack_use_after_return = 1” for testing in small cases). At different levels of optimization errors can be caught that will not be caught at other levels.

Integer Overflow

Description: there is no overflow of integers, but there can be overflow in both directions. Overflow of signed integers, this is UB, this includes INT_MIN / -1, INT_MIN% -1, minus INT_MIN, negative number shifts, left shift of the number with the unit after the sign bit, and also (sometimes), left shift of the number with the unit in the sign bit.
Division by zero and a shift by an amount greater than the digit capacity of the number is UB, for both signed and unsigned numbers. Also see: Understanding Integer Overflow in C / C ++

Debugging:UBSan is a very good tool for finding UB related to integers. Since UBSan works at the source level, it is very reliable. There are some oddities regarding compile-time calculations, for example, some program may catch an exception if it is compiled as C ++ 11, and not catch it when compiling in C11, we think that it complies with the standards, but did not go into details. GCC has its own version of UBSan, but it cannot be 100% trusted, there the constants are collapsed before this tool passes.

Mitigation:UBSan in “trapping mode” (when UB is caught, the process stops without diagnostic output) can be used to mitigate UB. It is effective and does not add vulnerabilities. In part, Android uses UBSan to mitigate this type of UB. Although overflowing integers is basically a logical mistake, in C and C ++ such errors are especially dangerous because they can lead to memory security violations. In languages ​​with secure access to memory, they are much less dangerous.

Conclusion:Integer UB is not very difficult to catch, UBSan, that's all you need for this. The problem is that softening the integer UB results in redundancy. For example, SPEC CPU 2006 runs 30% slower. There are many places for improvement, and eliminating overflow checks where it cannot damage, and making the rest of the checks less disturbing for the loop optimizer. Someone with sufficient resources should do this.

Strict aliasing violations

Description: The strict aliasing rules in the C and C ++ standards allow the compiler to allow the compiler to assume that if two pointers refer to different types, they do not point to the same object. This allows for excellent optimizations, but there is a risk of breaking programs with a more flexible look at things (and this is, according to rough estimates, 100% of large C and C ++ programs). For a more detailed review, see section 1-3 of this article (which will be published in the next part. comment translation ).

Debugging:The current state of debugging tools for strict aliasing violations is weak. Compilers give warnings in some simple cases, but these warnings are very unreliable. libcrunch warns that the pointer is converted to a "pointer to something" type, although it actually points to something else. This allows you to perform type conversions through a pointer to void, but catches invalid pointer conversions, which are also this type of UB. thanks to the C standard and how C compilers interpret what they can do with TBAA (type-based alias analysis) optimization, libcrunch is neither reliable (it does not catch some violations that occur during program execution) nor complete (it warns about converting pointers if it looks suspicious but doesn't violate the standard).

Mitigation: This is simple: pass the flag (-fno-strict-aliasing) to the compiler and it disables strict aliasing-based optimization. As a result, the compiler relies on the good old memory model, where more or less arbitrary conversions between pointer types can be performed, and the resulting code behaves as expected. Of the Big Three, only GCC and LLVM are subject to such UB, MSVC does not implement such a class of optimizations.

Conclusion: Code sensitive to this UB needs to be checked carefully: it is always suspicious and dangerous to convert pointers to something other than char *. As an alternative, you can simply turn off TBAA optimization using the flag, and making sure that no one will compile code without using this flag.

Alignment Violations

Description: RISC processors tend to deny memory access at unaligned addresses. On the other hand, C and C ++ programs, using unbalanced access, have UB, regardless of the target architecture. Historically, we looked at this through our fingers, at first because x86 / x64 supports unbalanced access, and secondly, because compilers have not yet used this UB for optimizations. But even in this case, there is a wonderful article explaining how the compiler can break code with non-aligned access on x64. The code in the article violates strict aliasing, in addition to misalignment, and crashes (tested on GCC 7.1.0 in OS X), despite the -fno-strict-aliasing flag.

Debugging: UBSan can detect misalignment.

Mitigation:unknown

Conclusion: use UBSan

Loops that do not perform I / O and do not end (Loops that Neither Perform I / O nor Terminate)

Description: Loops in C or C ++ code that do not perform I / O and do not complete are undefined and can be arbitrarily terminated by the compiler. See this article and this note .

Debugging: no tools

Softening: No, except avoiding overly optimizing compilers.

Conclusion: This UB is not a practical problem (even if it’s unpleasant for any of us).

Data Races

Description: Data contests occur when a piece of memory is accessible to more than one thread, and to at least one of them to write, and access is not synchronized by mechanisms such as locks. Data contests lead to UB in modern versions of C and C ++ (they do not make sense in older versions, since these standards did not describe multithreaded code).


Description: TSan is an excellent detector of dynamic memory contests. There are other similar tools, such as the Helgrind plugin for Valgrind, but we have not used them recently. The use of dynamic competition detectors is complicated by the fact that the competition is very difficult to make work, and the worst part is that their operation depends on the number of cores, the flow scheduler algorithm, what is still running on the test machine, moon phases, etc.

Mitigation: do not create threads

Conclusion: There is a good idea for this particular UB: if you do not like locking objects, then do not use code that is executed in parallel, use atomic actions instead.

Unsequenced Modifications

Description: In C, a “follow point” limits how sooner or later an expression with a side effect, such as x ++, takes effect. C ++ has a different, but more or less equivalent wording of this rule. In both languages, modifications with violation of the sequence points lead to UB.

Debugging: some compilers generate a warning when there are obvious violations of the rules for following:

$ cat unsequenced2.c
int a;
int foo(void) {
  return a++ - a++;
}
$ clang -c unsequenced2.c
unsequenced2.c:4:11: warning: multiple unsequenced modifications to 'a' [-Wunsequenced]
  return a++ - a++;
          ^     ~~
1 warning generated.
$ gcc-7 -c unsequenced2.c -Wall
unsequenced2.c: In function 'foo':
unsequenced2.c:4:11: warning: operation on 'a' may be undefined [-Wsequence-point]
   return a++ - a++;
          ~^~

However, a small indirect violation does not cause warnings:

$ cat unsequenced.c
#include 
int main(void) {
  int z = 0, *p = &z;
  *p += z++;
  printf("%d\n", z);
  return 0;
}
$ gcc-4.8 -Wall unsequenced.c ; ./a.out
0
$ gcc-7 -Wall unsequenced.c ; ./a.out
1
$ clang -Wall unsequenced.c ; ./a.out
1

Mitigation: Unknown, but it is almost trivial to determine the order in which side effects will be performed. The Java language is an example of how this is done. We had a difficult period when we believed that such a restriction would hinder any modern optimizing compiler. If the standardization committee believes wholeheartedly that this is not so, compiler developers will have to follow the rules. Ideally, all major compilers should do the same in such cases.

Conclusion:With some practice, it’s not very difficult to notice a potential violation of the sequence points during coding. We have to worry about seeing very complex expressions with side effects. It happens in legacy code, but look, it still works, which means that maybe this is not a problem. In fact, this problem should be fixed in compilers.

Non-UB related to violation of sequence points is an “indeterminately sequenced” in which statements can be executed in the order specified by the compiler. An example is the order in which two functions are called in calculating f (a (), b ()). This order must be defined too. From left to right, for example. There will be no loss of speed, if you do not consider completely crazy situations.

To be continued.