Memcheck Reloaded: dealing with compiler-generated branches on undefined values (Julian Seward) [FOSDEM 2020]


The valgrind memcheck tool not only checks if the memory you read and write is in a correct place, but it also checks if branches don’t depend on undefined (uninitialized) data. The latter turns out to be difficult to do, due to compiler optimisations.

Memcheck wants to have a low false-positive rate. Back in 2005 this was no problem, but starting in 2015 the aggressive optimisations in clang 3+ and gcc 5+ started to create problems.

Memcheck tracks the entire state of the processor with a shadow state. This way, the definedness of memory locations and registers is kept track of, at the bit level. Only on a branch or load-store address the undefinedness is treated as an error. When an operation is done with undefined values, the definedness is propagated, depending on the operation. E.g. AND with 0 is defined 0, while AND with 1 is undefined. The definedness is not tracked exactly for all operations, instead cheap approximations are used - these usually work because humans (and compiler writers) have a hard time reasoning about undefinedness. There are three levels of accuracy that could be used: exact (very expensive), somewhat inexact (all bits above the undefined bit become undefined on addition and multiplication). Inexact tracking is only used for values that end up being used as addresses (valgrind does some local code analysis to find these).

Unfortunately, current compilers generate some code that depend on undefined values. For example:

int result;
bool ok = compute_something(&result);
if (ok && result == 42) { ... }

The compiler may swap the order of the comparison and the ok check, so in case the ok is false, the comparison (which leads to a branch) is executed even though result is undefined. The compiler is allowed to do this, because the comparison has no side effects. In the end, regardless of the value of result, you end up in the false branch anyway. But memcheck will give an error for this. That’s because memcheck can’t see across basic blocks, while compilers do look across basic blocks now.

The first idea was to look at the entire control flow and verify that you will end up in the same branch regardless of the undefined value. But that would be waaaaaay too complex.

Julian didn’t see a solution for a long time, but then after a year he realized that this problem is exactly the same as the definedness tracking of AND. The problem is basically that you don’t see that it’s an AND, because the AND is expressed as a conditional branch instead of an AND instruction. If we can recover the AND from the instructions, we can keep on using the original definedness analysis.

So we can merge basic blocks and treat them as AND. This does require however to be able to also mark anything that is done in between as conditional.

To implement this, Julian didn’t want to do it per-architecture. All architectures have a different representation of a branch. So the branches are first translated to IR and then parttern matching is applied to it to see if it is one of these hidden ANDs.

This will slow down the JIT, but it turns out not to be that much. It’s mostly the backend (that inserts instrumentation) that is expensive. The frontend is not dominant.

This feature will go into valgrind 3.16, enabled by default for x86, arm and powerpc. s390 and MIPS are currently crashing. It manages to eliminate all false positives of this kind from firefox (Julian works for Mozilla).

Answering a question from the audience: are there other false positives that need to be tackled? The only remaining annoying false positives are from system calls (i.e. the struct you give as an argument and that will be filled in by the system call). These will not be tackled.