[Valgrind-users] memcheck reliability and usefulness

[John R. <jr...@Bi...>]

Nicholas Nethercote wrote:
> On Mon, 5 Jan 2004, John Reiser wrote:
> 
> 
>>>As with all free software, you get out what you put in.
>>
>>I put in test cases, I get out bugs -- enough to demonstrate that memcheck
>>has a ways to go before I should rely on it to check non-test code.
> 
> 
> Memcheck produces false positives and false negatives.  This will always
> be the case, because the method it uses isn't sound or complete,

This is a major change in stance.  Originally, and for a few years, valgrind
claimed that it would complain if and only if an uninitialized bit affected
control flow or I/O.  Of course, the claim _never_ was correct:
     ld-linux.so.2 before LD_PRELOAD takes effect
     scalar args to syscalls
     floating point arithmetic
     MMX (even AND and OR !)
     bitwise "convolution" operations (multiplication, division, remainder)
but at least there was the pretense, and therefore some hope, that
"complain as late as possible [just before disaster]" could be relied on
in most cases.  Now even the pretense is gone.

> and the
> implementation will always have imperfections.  (And I agree that the bugs
> you mention, particular the lack of checking on scalar syscall arguments,
> should be looked at.)
> 
> However, I don't see why one shouldn't use Memcheck on non-test code:
> 
>   - If it produces false positives, as long as the number is small enough
>     that they don't become a distraction -- and I think experience shows
>     that this is true for Memcheck -- one can check them, determine their
>     falsehood, and suppress them.
> 
>   - As for producing false negatives, the only problem I can see with this
>     is if someone assumes that when their programs passes Memcheck without
>     errors, that it is totally bug-free with respect to memory errors.  I
>     don't imagine this is common, and it is not the case with you John --
>     you are clearly aware of Memcheck's shortcomings.
> 
> I can understand why you might not trust a compiler that you knew had
> certain bugs -- because you are relying on blemish-free output.  But
> Memcheck is a different sort of program, where the output doesn't have to
> be blemish-free for it to still be useful.  So I don't understand why
> relying on it would be a bad thing.  Perhaps you could elaborate further?

The test case fanout.c shows that memcheck does not understand reconvergent
fanout: "cancelling" of uninitialized-ness.  The result of any boolean AND
(x & ~x) is guaranteed to be 0, regardless of which bits are initialized
or not, yet memcheck complains from within printf().  The example further
underscores the severity of not checking scalar args to syscalls: by memcheck's
logic the return value of main() is undefined, yet memcheck does not complain
there!  Even if not checking the argument to sys_exit(), everyone knows that
there _is_ an implicit read of the return value from main(); memcheck
ought to pay attention.

-----fanout.c
int g(int a, int *p)
{
         return *p & ~a;
}

int f(int *p)
{
         return g(*p, p);
}

main()
{
         int x;  /* deliberately uninitialized */
         printf("%d\n", !!f(&x));
         return !!f(&x);
}
/* Curious quirk: memcheck (valgrind-2.1.0) complains 5 times
    as written, but 7 times when both "!!" are removed.
    The values produced by the code (and their "heritage") are the same!
*/
-----end fanout.c


So, memcheck now admits that its method is neither sound nor complete.
Memcheck complains "as late as possible" for uninit bits in "easy"
operations, "as soon as possible" [maybe: integer mul/div/rem are
murky] for uninit bits in "hard" operations, and "never" for
scalar args to syscalls.  There is no option to get "eager" mode
all the time (complain "as soon as possible": on any fetch from memory),
which in many cases is the information needed for the easiest debugging
and fixing.

How, then, should the programmer interpret the output from memcheck?
Supposedly any complaint should indicate an actual bug.  But if
reconvergent fanout or integer "convolution" is involved, then all bets
are off, and the noise level from memcheck is quite high.  Unfortunately
such operations are quite common in pattern matching and recognition
algorithms, and pattern processing is widespread: cryptanalysis, remote
sensing, image analysis, radar, sonar, vision, robotics, ...; including
stroke recognition for mouse input to a GUI.

Even when a complaint accurately determines that a bug exists, it can
quite difficult to locate and correct if it is associated with a
chain of "easy" operations, and therefore the complaint is as late
as possible.  "Eager mode" should be available for all operations,
not just floating point or other "hard" operations.

More troubling are the omitted complaints (false negatives).
These include scalar args to syscalls and the internal hacks that
suppress complaints automatically in an attempt to reduce noise
from strlen (etc.) without checking that the code is a reaonsable
impostor for strlen.

All in all, that's too much hassle for me.  Memcheck goes to the bottom
of my toolbox.  I can check and correct more code sooner, and have more
confidence the results, using Insure++, or Purify on SPARC/Solaris.

--