Extending memcheck's validity bit propagation

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Extending memcheck's validity bit propagation

Patrick J. LoPresti-2
Right now, if I have code like this:

  int a; /* invalid value */
  int b = a + 1; /* operation on invalid value */

...memcheck does not produce a warning for the addition. It just taints b as invalid and only generates a warning if I try to use b in a behavior-changing way. This is good, and it is exactly what I want.

However, if instead I have this code:

  int a; /* invalid value */
  int b;
  if (a > 0) /* conditional on invalid value */
    b = a;
  else
    b = 0;

...memcheck produces a warning on the conditional branch. But if you look at what this code actually computes, it is just "b = max(a,0)", which is not so different from "b = a + 1". (That is, b is just some simple function of a.) I want to teach memcheck to treat this second example like the first; that is, just taint b as invalid if a is invalid.

Another example:

  extern unsigned char lookup[256]; // assume this is initialized

  unsigned char x;
  unsigned char y = lookup[x];

Here, I have some 8-bit function implemented using a lookup table. Again, memcheck issues a diagnostic for using x as part of computing an address. But I want to think of y as a simple function of x, and tell memcheck to just let y inherit x's invalidity.

I believe I can cobble together what I want from VALGRIND_GET_VBITS() and VALGRIND_SET_VBITS(). But I have two questions.

1) Is this the right way to do this, or is there some other mechanism more suitable for this purpose?
2) If I do use SET/GET_VBITS(), how can I arrange for --track-origins=yes to work if there is a later use of the uninitialized data?

Thanks.

 - Pat

------------------------------------------------------------------------------
Developer Access Program for Intel Xeon Phi Processors
Access to Intel Xeon Phi processor-based developer platforms.
With one year of Intel Parallel Studio XE.
Training and support from Colfax.
Order your platform today. http://sdm.link/xeonphi
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Extending memcheck's validity bit propagation

John Reiser
>   int a; /* invalid value */
>   int b;
>   if (a > 0) /* conditional on invalid value */
>     b = a;
>   else
>     b = 0;
>
> ...memcheck produces a warning on the conditional branch. But if you look at what this code actually computes, it is just "b = max(a,0)", which is not so different from "b = a + 1". (That is, b is just some simple function of a.) I want to teach memcheck to treat this second example like the first;
> that is, just taint b as invalid if a is invalid.

Teaching VEX about the x86 opcode CMOVG (conditional move if Greater)
might not be so difficult.  Teaching VEX about branch-and-reconverge
control flow involving multiple instructions, probably is harder.

>
> Another example:
>
>   extern unsigned char lookup[256]; // assume this is initialized
>
>   unsigned char x;
>   unsigned char y = lookup[x];
>
> Here, I have some 8-bit function implemented using a lookup table. Again, memcheck issues a diagnostic for using x as part of computing an address. But I want to think of y as a simple function of x, and tell memcheck to just let y inherit x's invalidity.
>

The key here is range analysis on the subscripting operation "lookup[x]".
If the bounds on 'x' propagate, and if 'lookup' has effective bounds,
then probably it is not so hard.

--


------------------------------------------------------------------------------
Developer Access Program for Intel Xeon Phi Processors
Access to Intel Xeon Phi processor-based developer platforms.
With one year of Intel Parallel Studio XE.
Training and support from Colfax.
Order your platform today. http://sdm.link/xeonphi
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Extending memcheck's validity bit propagation

Philippe Waroquiers
In reply to this post by Patrick J. LoPresti-2
On Thu, 2016-11-03 at 15:36 -0700, Patrick J. LoPresti wrote:

> Right now, if I have code like this:
>   int a; /* invalid value */
>   int b = a + 1; /* operation on invalid value */
> ...memcheck does not produce a warning for the addition. It just
> taints b as invalid and only generates a warning if I try to use b in
> a behavior-changing way. This is good, and it is exactly what I want.
>
>
> However, if instead I have this code:
>   int a; /* invalid value */
>   int b;
>   if (a > 0) /* conditional on invalid value */
>     b = a;
>   else
>     b = 0;
> ...memcheck produces a warning on the conditional branch. But if you
> look at what this code actually computes, it is just "b = max(a,0)",
> which is not so different from "b = a + 1". (That is, b is just some
> simple function of a.) I want to teach memcheck to treat this second
> example like the first; that is, just taint b as invalid if a is
> invalid.
I am not sure to understand how you will differentiate the above
    if (a > 0)
      b = a;
    else
      b = 0;

from
    if (a > 0) {
      b = a;
      launch_all_missiles();
    } else
      b = 0;

What we want is an error when the 'outside visible behaviour' of the
program depends on uninit values.
When a jump is processed, how do we know that the jump is jumping
to a location that will have no outside visible effect ?

For sure, we need/must have a valgrind error for the above case,
otherwise we risk a nuclear 3rd world war :).

Or maybe the idea is to do that only for very specific
way to compile
   if (a > 0)
when the then/else branches are only assignment to b ?

This case seems very specialised to me, probably depending
a lot from the compiler and compiler optimisation options.

Is such code creating many false positive ?

Philippe




------------------------------------------------------------------------------
Developer Access Program for Intel Xeon Phi Processors
Access to Intel Xeon Phi processor-based developer platforms.
With one year of Intel Parallel Studio XE.
Training and support from Colfax.
Order your platform today. http://sdm.link/xeonphi
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Extending memcheck's validity bit propagation

John Reiser
> I am not sure to understand how you will differentiate the above
>     if (a > 0)
>       b = a;
>     else
>       b = 0;
>
> from
>     if (a > 0) {
>       b = a;
>       launch_all_missiles();
>     } else
>       b = 0;

Because the first paragraph is equivalent to "b = max(0, a);"
which has relatively simple semantics, but the second paragraph is not.

As I pointed out to the list 2 days ago, if the x86* code is:
        mov $0, r_b
        cmp $0, r_a
        cmovg r_a, r_b  # conditional move if > 0; r_a to r_b
then it is somewhat easy to convince VEX to set state(b) = state(a)
without complaint (when condition code bits indicate > 0.)

If the compiled code uses explicit branching, then probably it's hard.
Quite a few analysis tools (covering either software or hardware!)
have [have had] difficulty with re-convergent fan out.






------------------------------------------------------------------------------
Developer Access Program for Intel Xeon Phi Processors
Access to Intel Xeon Phi processor-based developer platforms.
With one year of Intel Parallel Studio XE.
Training and support from Colfax.
Order your platform today. http://sdm.link/xeonphi
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Extending memcheck's validity bit propagation

Patrick J. LoPresti-2
Thank you, John and Phillippe, for your replies.

First, to John:

Valgrind actually does know that a conditional move is a functional operation and not a conditional branch. So if you can convince your compiler to emit conditional moves, Valgrind will simply "taint" the output instead of emitting a diagnostic. (Actually, my original example is so simple that a modern compiler will see that it invokes undefined behavior, and then the compiler might optimize away the entire program. Of course my real-life case is not so simple; in reality, the undefined value is coming from outside the function.)

Also, even with optimization disabled, or with a compiler that does not emit CMOV instructions, I can get the behavior I want by rewriting like so:

    int a; /* undefined */
    int b = a & (-(a > 0));

It is always possible to rewrite pure functions to avoid branches; anyone who writes vectorized code is probably familiar with this sort of trick. However, the computational overhead can become prohibitive. My second example is the sort of case that would be (very) painful to "fix" in this way.

To both of you:

I do not necessarily want Valgrind to figure all of this out automatically... I am willing to annotate my code with VG_ macros to achieve the effect I want. As I mentioned in the original Email, I believe I can mostly do this with the GET_VBITS() and SET_VBITS() macros. But I fear I will lose the origin tracking, which in my case is extremely useful.

And yes, this is creating a huge number of false positives for me. (My use case is a bit of a long story; I am hoping you will trust me when I say I cannot easily fix this in some other way.) I could add suppression rules, of course, but then I might miss real bugs... I really do want simply to propagate the invalidity bits and only see the warning if the value is later used.

Thank you again for your replies.

 - Pat

------------------------------------------------------------------------------
Developer Access Program for Intel Xeon Phi Processors
Access to Intel Xeon Phi processor-based developer platforms.
With one year of Intel Parallel Studio XE.
Training and support from Colfax.
Order your platform today. http://sdm.link/xeonphi
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Loading...