UB-2017. Part 1

We often hear that some people argue that problems arising from indefinite behavior (UB) in C and C ++ are mainly solved by the wide distribution of dynamic validation tools such as ASan, UBSan, MSan and TSan. We will show the obvious here: in spite of 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 consider the situation in detail.
')


Valgrind and most sanitizers are designed for debugging: they generate friendly diagnostic messages related to cases of unspecified 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 stream of UB to a state of the world in which a significant number of important programs are mostly free of UB in their most common configurations and use cases. .

The problem with dynamic debugging tools is that they do nothing to help us deal with the worst cases of UB: about which we don’t know how they will work when testing, but someone else can figure out how UB will manifest itself 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 affecting big programs. One way to circumvent the testing problem is to use static UB detection tools. They are constantly being improved, but a confident and accurate static analysis is not necessarily easier to do than to achieve a good test coverage. Of course, these two techniques are aimed at solving one problem, identifying possible ways to execute a program, but from different sides. This problem has always been very complex, and perhaps always will be. Much has been written about finding UB through static analysis, in this article we will focus on dynamic tools. Another way to solve the problem of testing is to use the “soften” UB tools: they turn unspecified behavior into that defined using C and C ++, effectively achieving some of the advantages of using safe programming languages. The difficulties in designing tools that “soften” UB are as follows:

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

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

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

Objective 2: Each case of UB must either be documented or diagnosed by the compiler as a fatal error, or have an optional mitigation mechanism that satisfies the previous requirements. It is more difficult. We believe that this can be achieved on many platforms. Kernels of operating systems and other code for which performance is critical, needs the use of other technologies, such as formal methods. In the remainder of this article, we consider 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 it is possible that the value of N will reach 75.

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

Valgrind works from executable code, cannot insert red zones between stack variables, since 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 address of the call to the stack on the fly. As a result, Valgrind has limited support in detecting errors with the manipulation of objects on the stack. ASan runs at compile time and inserts red areas around stack variables. Stacked 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 performed by ASan and Valgrind relate only to the placement of objects in memory, and the placement of objects with verification enabled is different from the placement of objects without the use of verification tools.

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 a mitigation mechanism for unsafe memory operations, including ASLR, stack canaries, protected allocators, and NX bits.







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

A serious disadvantage of ASan as a means of softening UB is shown here:

$ cat asan-defeat.c #include <stdio.h> #include <stdlib.h> #include <string.h> 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 another offset in order to spoil the desired region of memory. (Thanks to Yuri Gribov for prompting to use the -fno-common flag in ASan.)

In order to mitigate this variant of indefinite behavior, a real check of overflow should be made, rather than a simple check that every memory access takes place in a valid region. Memory safety is the gold standard here. Although there are many academic works on memory security, and some demonstrate approaches with acceptable 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 these kinds of errors are very good. It is possible to significantly mitigate this type of UB, but in order to completely eliminate it, you will need complete type and memory security.

Security Temporary Memory Object Violation (Temporal Memory Safety Violations)

Description: The security breach of temporary memory objects is any use of a memory location after the expiration of its lifetime. This includes the addressing of automatic variables outside the life region of these variables, the use after release, the use of a dangling pointer for reading or writing, a double release, which can be very dangerous in practice, because free () modifies the metadata that usually belongs to the block being released. If a block is already released, writing to this data can damage data used for other purposes, and, in principle, can have the same effect as any other invalid record.

Debugging: ASan is designed to detect “use after release” bugs, which often lead to reproducible, erroneous behavior. He makes such a check by placing the released blocks in quarantine, preventing their immediate reuse. For some programs and input data, this can increase memory consumption and reduce 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 have survived the scope of these variables. The idea is to turn automatic variables into blocks allocated in dynamic memory, which the compiler automatically allocates when the execution enters the block, and releases (while quarantined) when the execution leaves the block. This option is turned off 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 with -O2. ASan can detect a problem in a program without optimization, but only if the option detect_stack_use_after_return is set, and only if it has not been compiled with optimization.

 $ cat temporal.c #include <stdio.h> 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 has been removed by the optimizer, and thus is safe, since the remote code from UB cannot have consequences. But this is not the case! A program is meaningless anyway, but a non-optimized program works deterministically, as if the variable x was declared static, while an optimized program in which ASan did not find anything suspicious, does not behave deterministically and reveals an internal state that is not intended to 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 anti-overflow of integers, but there can be overflow in both directions. Overflow of signed integers is UB, including INT_MIN / -1, INT_MIN% -1, minus INT_MIN, negative number shifts, left-shift numbers with one after the sign bit, and (sometimes), left-shift numbers with a one in the sign bit.
The division by zero and the shift by an amount greater than the digit capacity of the number is UB, both for 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 source level, it is very reliable. There are some oddities related to compile-time computations, for example, some program can catch an exception if it is compiled as C ++ 11, and not catch when compiling in C11, we think that this corresponds to the standards, but did not go into details. GCC has its own version of UBSan, but it cannot be trusted 100%, there the constants collapse before the passage of this tool is performed.

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

Conclusion: Integer UB is not very difficult to catch, UBSan, that's all you need to do. The problem is that mitigating integer UB leads to redundancy. For example, while SPEC CPU 2006 runs at 30% slower. There are a lot of places to improve, and eliminate overflow checks where it cannot be damaged, and make other checks less disturbing for the loop optimizer. Someone with sufficient resources must do this.

Strict Aliasing Violations

Description: The “strict aliasing" rules in 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 one object. This allows you to perform fine optimizations, but there is a risk of breaking programs with a more flexible look at things (and this, according to rough estimates, is 100% of large programs in C and C ++). For a more detailed review, see section 1-3 of this article (to be published in the next section. comment. trans. ).

Debugging: The current status of debugging tools for “strict aliasing” violations is weak. Compilers issue 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 type conversion through a pointer to void, but catches invalid conversion of pointers, which are also this type of UB. thanks to the C standard and how C compilers interpret what they can do when optimizing TBAA (type-based alias analysis), libcrunch is neither reliable (it doesn’t catch some violations that occur during program execution), nor is it complete (it warns conversion of pointers if it looks suspicious, but does not violate the standard).

Softening: It's simple: pass a flag to the compiler (-fno-strict-aliasing), and it disables the optimization based on strict aliasing. 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 this class of optimizations.

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

Alignment Violations

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

Debugging: UBSan can detect alignment problems.

Mitigation: Unknown

Conclusion: use UBSan

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

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

Debugging: no tools

Mitigation: No, apart from avoiding too much optimizing compilers.

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

Data Races

Description: data contests occur when more than one stream is available to a memory location, and at least one of them is writeable and access is not synchronized by locking mechanisms. 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 multi-threaded code).


Description: TSan is an excellent detector for dynamic memory races. 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 thing is that their response depends on the number of cores, the flow planner algorithm, what is still running on the test machine, the phases of the moon, etc.

Mitigation: do not create streams

Conclusion: There is a good idea for this particular UB: if you don’t like blocking objects, then don’t use parallel code, use atomic actions instead.

Unsequenced Modifications

Description: In C, the “point of sequence” limits how sooner or later an expression with a side effect, such as x ++, will have an effect. C ++ has a different, but more or less equivalent, formulation of this rule. In both languages, modifications with violation of 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 <stdio.h> 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, however, it is almost trivial to determine the order in which side effects will occur. The Java language is an example of how this is done. We had a difficult period when we believed that such a restriction would prevent any modern optimizing compiler. If the standardization committee believes whole-heartedly that this is not the case, the compiler developers will have to follow the rules. Ideally, all major compilers should do the same in such cases.

Conclusion: With some practice, it is not very difficult to notice a potential violation of the cue-following sequence points. We have to worry about seeing very complex expressions with side effects. This happens in the Legacy code, but look, it still works, so maybe this is not a problem. In fact, this problem should be fixed in the compilers.

Non-UB, referring to violations of sequence points is an “indefinite sequence” (indeterminately sequenced) in which operators can be executed in the order specified by the compiler. An example is the order of calling two functions when 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 quite insane situations.

To be continued.