memcheck & reporting uninitialized reads

Hi, 

Memcheck reports uninitialized reads (UMRs) only when the reads cause side effects (e.g. cmp, syscall, etc). 

This cases the implementation to be complex and slow, especially if we need to have --track-origins=yes. 

Other tools choose to report UMRs on any first access, including move. 

This is much simpler and faster, but leads to numerous false positives (e.g. when copying structures with padding bytes). 

I wonder if these two approaches where discussed and compared somewhere in literature.

Any link? 

Thanks, 

--kcc 

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

On Tuesday 10 November 2009, Konstantin Serebryany wrote:
> Hi,
>
> Memcheck reports uninitialized reads (UMRs) only when the reads cause side
> effects (e.g. cmp, syscall, etc).

Yes.  So it's not really reporting reads of uninitialised memory;
rather it's reporting dangerous uses of uninitialised values.

> This cases the implementation to be complex and slow, especially if we need
> to have --track-origins=yes.
>
> Other tools choose to report UMRs on any first access, including move.
> This is much simpler and faster, but leads to numerous false positives
> (e.g. when copying structures with padding bytes).
>
> I wonder if these two approaches where discussed and compared somewhere in
> literature.

I don't know of any.  I too would be interested to read more about it.
Personally I don't believe it's possible to have an (essentially) zero
false positive rate without using an approach like Memcheck's.  But I
would love to be proved wrong on this, since I too don't like Memcheck's
complexity and overhead.

J

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

[Nicholas Nethercote]

On Tue, Nov 10, 2009 at 7:46 PM, Konstantin Serebryany
<konstantin.s.serebryany@...> wrote:

> Hi,
> Memcheck reports uninitialized reads (UMRs) only when the reads cause side
> effects (e.g. cmp, syscall, etc).
> This cases the implementation to be complex and slow, especially if we need
> to have --track-origins=yes.
> Other tools choose to report UMRs on any first access, including move.
> This is much simpler and faster, but leads to numerous false positives (e.g.
> when copying structures with padding bytes).
> I wonder if these two approaches where discussed and compared somewhere in
> literature.

Only one I can think of is our Usenix 2005 paper, which is on the
Valgrind website.  It doesn't go into much more detail about the
trade-offs than what you've written above.

Nick

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

> Other tools choose to report UMRs on any first access, including move.
> This is much simpler and faster, but leads to numerous false positives
> (e.g. when copying structures with padding bytes).

There are programming ecosystems in which that is not a "false positive."
It is an actual demerit with a real monetary cost.  Some software creators
must purchase product liability insurance.  Some insurance companies
offer a discount if the code passes tests which show that no uninitialized
bits ever are fetched from memory.  Any hole in a structure is avoided,
documented, and/or filled deliberately.

"Complain immediately upon fetch" sometimes dramatically shortens the
search for the cause of a mysterious UMR.  The feature "--track-origins=yes"
can be viewed as an intermediate strategy between delayed versus
immediate complaints.

--

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers

[Nicholas Nethercote]

On Tue, Nov 10, 2009 at 11:40 PM, Julian Seward <jseward@...> wrote:

> On Tuesday 10 November 2009, Konstantin Serebryany wrote:
>> Hi,
>>
>> Memcheck reports uninitialized reads (UMRs) only when the reads cause side
>> effects (e.g. cmp, syscall, etc).
>
> Yes.  So it's not really reporting reads of uninitialised memory;
> rather it's reporting dangerous uses of uninitialised values.
>
>> This cases the implementation to be complex and slow, especially if we need
>> to have --track-origins=yes.
>>
>> Other tools choose to report UMRs on any first access, including move.
>> This is much simpler and faster, but leads to numerous false positives
>> (e.g. when copying structures with padding bytes).
>>
>> I wonder if these two approaches where discussed and compared somewhere in
>> literature.
>
> I don't know of any.  I too would be interested to read more about it.
> Personally I don't believe it's possible to have an (essentially) zero
> false positive rate without using an approach like Memcheck's.  But I
> would love to be proved wrong on this, since I too don't like Memcheck's
> complexity and overhead.

It all gets quite tricky when you think about it carefully.  Using
Andreas Zeller's terminology, a "bug" is a chain of three things:

- A "defect" is erroneous source code;
- An "infection" is erroneous program state, caused by executing
erroneous source code;
- A "failure" is erroneous program behaviour, caused by erroneous program state.

Sometimes chains are aborted, eg. an infection may be overwritten
without causing a problem.

Debugging is all about working back from failures to defects.  Tools
like Valgrind help with that by automatically giving you a point
somewhere along the chain closer to the defect.  The closer the
better.

For UMRs the defect is usually that some code is missing, ie. there's
a forgotten initialiser.  The infection is that a variable has a
probably-wrong value.  (It may not actually be wrong, eg. you may get
lucky (unlucky?) and have it initialise to the desired value, esp. if
that value is zero.)  We use the term "undefined" but that really just
means "probably wrong".

Once you have a "probably wrong" value in a C/C++ program, just about
anything can happen because you have so much ability to screw up
things via memory accesses.

There are trade-offs with different approaches for identifying UMRs.
The more aggressive you are in identifying suspicious points along the
infection chain, the closer you'll be to the actual defect, but the
more likely you are to reporting a false positive.  Valgrind waits
until the undefined value is used in a way that has a high chance of
causing an immediate failure.

--track-origins=yes is useful because it gives you the location where
the undefined value was allocated in memory, which is often the same
place that the missing initialiser was supposed to be, ie. where the
defect is.

All this assumes that copying undefined values is ok.  It almost
always is, so Valgrind allows it;  John Reiser mentions an unusual
counter-example.  Tools have to make assumptions, sometimes they'll be
wrong.

There may be better approaches than Valgrind's.  If you want to find
one, I strongly recommend you think about it in terms of
defects/infections/failures, it'll clarify your thinking greatly.

Nick

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@...
https://lists.sourceforge.net/lists/listinfo/valgrind-developers