Brussels / 3 & 4 February 2018


Valgrind's Memcheck tool vs Optimising Compilers

Keeping the false positive rate under control

The ongoing work to improve the accuracy of definedness tracking in the face of newer more aggressively optimizing compilers.

Valgrind's Memcheck tool reports various kinds of errors. One of the most important ones are those where an if-conditions or a memory address uses undefined data. To do this, it tracks the definedness of every bit in the process, and "follows" any undefinedness through arithmetic operations (Add, Sub, Mul, Or, Xor, etc).

This tracking is expensive and so Memcheck makes compromises, trading off exactness for speed. That has worked well for many years. However, as compilers become more aggressive, this works less and less well. In particular, Memcheck now often reports false errors in optimised code from GCC 6, Clang 4, and later versions. This is a problem because one of Memcheck's main strengths is the accuracy of its analyses.

In this talk I'll present my ongoing work to improve accuracy of definedness tracking. I'll mostly talk about various examples involving integer addition and comparisons, and will avoid gory details of Memcheck's internals. I'll also show two problems to which I have no solution.

The talk should be accessible to anyone with some familiarity of basic integer arithmetic (add, sub, and/or/xor, etc) and is curious about how undefinedness "flows" through these operations. If you like maths and proving simple theorems, you might enjoy this talk too -- and we'd like to talk to you!


Julian Seward