llvm dev - Apr 2017 - [RFC] Design of a TBAA sanitizer

On Tue, Apr 11, 2017 at 3:14 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> Hi Kostya,
>
> On April 11, 2017 at 2:39:44 PM, Kostya Serebryany (kcc at google.com)
wrote:
> > > ptr0 = malloc();
> > > free(ptr0);
> > > ptr1 = malloc();
> > >
> > > ptr0 and ptr1 will be NoAlias despite overlapping (there is
actually a
> > > real soundness issue here in LLVM's semantics, but I
don't want to
> > > digress). You can also recreate the pattern with realloc.
> > >
> >
> > In both of your examples there is no place in the program where both
P0
> and
> > P1 are live simultaneously,
> > i.e. no analysis path is expected to query MayAlias(AccessToP0,
> > AccessToP1). No?
>
> I may be misunderstanding what you meant, but I don't see why not.
>
> Say you had (all values are SSA values):
>
> %p0 = malloc()
> store i32 0, i32* %p0  // S0
> free(%p0)
> %p1 = malloc()
> store i32 1, i32* %p1  // S1
>
> and some pass wanted to sink S0 to after S1.  So it starts checking
> "from the bottom", as
>
>   Alias(S0, S1) = NoAlias
>   Alias(S0, malloc()) = NoAlias
>   Alias(S0, free(%p0)) = MayAlias
>
> etc.  The last MayAlias will prevent it from doing the sink, but I
> don't see why it can't ask the Alias(S0, S1) question.
>
Yea, that's a bit trickier.
But we can at least add checks for pairs of pointer accesses that the
analysis claims to be ok to reorder.


>
> > > The same problem exists with constant addresses. LLVM states that
> > > constant locations are noalias with themselves, and you again
have the
> > > "noalias does not imply pointer inequality" problem.
> >
> > That won't even have to be special cased, because if we emit a
check
> > ConstPtr != ConstPtr,
> > such a check will be trivially optimized away.
>
> But won't it be constant folded to trigger the sanitizer crash /
> warning?  That is, since LLVM will state the ConstPtr NoAlias
> ConstPtr, you'll emit the check:
>
> if (overlap(ConstPtr, Sz, ConstPtr, Sz))
>   abort();
>
> which will get constant folded to
>
> if (true) abort();
>
ah, yes, you are right, then this will have to be special-cased.

>
> If you meant that the implementation of overlap will differ based on
> whether the pointers are constant pointers or not, I'm not sure if
> that will work, since the fact that the values whose aliasness (I
> think I invented a new word :P ) you're checking could have been
> arbitrarily obscured (AA could have looked through PHIs and selects
> etc.) which will prevent you from rediscovering that the values were
> constant pointers in some cases.
>
> -- Sanjoy
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170411/bd4c5056/attachment.html>

On April 11, 2017 at 3:28:04 PM, Kostya Serebryany (kcc at google.com)
wrote:
> On Tue, Apr 11, 2017 at 3:14 PM, Sanjoy Das
> wrote:
>
> > Hi Kostya,
> >
> > On April 11, 2017 at 2:39:44 PM, Kostya Serebryany (kcc at google.com)
wrote:
> > > > ptr0 = malloc();
> > > > free(ptr0);
> > > > ptr1 = malloc();
> > > >
> > > > ptr0 and ptr1 will be NoAlias despite overlapping (there is
actually a
> > > > real soundness issue here in LLVM's semantics, but I
don't want to
> > > > digress). You can also recreate the pattern with realloc.
> > > >
> > >
> > > In both of your examples there is no place in the program where
both P0
> > and
> > > P1 are live simultaneously,
> > > i.e. no analysis path is expected to query MayAlias(AccessToP0,
> > > AccessToP1). No?
> >
> > I may be misunderstanding what you meant, but I don't see why not.
> >
> > Say you had (all values are SSA values):
> >
> > %p0 = malloc()
> > store i32 0, i32* %p0 // S0
> > free(%p0)
> > %p1 = malloc()
> > store i32 1, i32* %p1 // S1
> >
> > and some pass wanted to sink S0 to after S1. So it starts checking
> > "from the bottom", as
> >
> > Alias(S0, S1) = NoAlias
> > Alias(S0, malloc()) = NoAlias
> > Alias(S0, free(%p0)) = MayAlias
> >
> > etc. The last MayAlias will prevent it from doing the sink, but I
> > don't see why it can't ask the Alias(S0, S1) question.
> >
>
> Yea, that's a bit trickier.
> But we can at least add checks for pairs of pointer accesses that the
> analysis claims to be ok to reorder.
But that the problem right -- AA told you that S0 and S1 *are* okay to
reorder.  In fact, if your original program would have been:

p0 = malloc()
free(p0)
p1 = malloc()
*p0 = 20  // S0
*p1 = 20  // S1

then S0 and S1 would have been okay to reorder (since the original
program has UB).  But you cannot assert !overlap(p0, p1) in the well
defined program I mentioned earlier.

-- Sanjoy
>
>
>
> >
> > > > The same problem exists with constant addresses. LLVM states
that
> > > > constant locations are noalias with themselves, and you
again have the
> > > > "noalias does not imply pointer inequality"
problem.
> > >
> > > That won't even have to be special cased, because if we emit
a check
> > > ConstPtr != ConstPtr,
> > > such a check will be trivially optimized away.
> >
> > But won't it be constant folded to trigger the sanitizer crash /
> > warning? That is, since LLVM will state the ConstPtr NoAlias
> > ConstPtr, you'll emit the check:
> >
> > if (overlap(ConstPtr, Sz, ConstPtr, Sz))
> > abort();
> >
> > which will get constant folded to
> >
> > if (true) abort();
> >
>
> ah, yes, you are right, then this will have to be special-cased.
>
>
> >
> > If you meant that the implementation of overlap will differ based on
> > whether the pointers are constant pointers or not, I'm not sure if
> > that will work, since the fact that the values whose aliasness (I
> > think I invented a new word :P ) you're checking could have been
> > arbitrarily obscured (AA could have looked through PHIs and selects
> > etc.) which will prevent you from rediscovering that the values were
> > constant pointers in some cases.
> >
> > -- Sanjoy
> >
>

On Tue, Apr 11, 2017 at 3:31 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> On April 11, 2017 at 3:28:04 PM, Kostya Serebryany (kcc at google.com)
wrote:
> > On Tue, Apr 11, 2017 at 3:14 PM, Sanjoy Das
> > wrote:
> >
> > > Hi Kostya,
> > >
> > > On April 11, 2017 at 2:39:44 PM, Kostya Serebryany (kcc at
google.com)
> wrote:
> > > > > ptr0 = malloc();
> > > > > free(ptr0);
> > > > > ptr1 = malloc();
> > > > >
> > > > > ptr0 and ptr1 will be NoAlias despite overlapping
(there is
> actually a
> > > > > real soundness issue here in LLVM's semantics, but
I don't want to
> > > > > digress). You can also recreate the pattern with
realloc.
> > > > >
> > > >
> > > > In both of your examples there is no place in the program
where both
> P0
> > > and
> > > > P1 are live simultaneously,
> > > > i.e. no analysis path is expected to query
MayAlias(AccessToP0,
> > > > AccessToP1). No?
> > >
> > > I may be misunderstanding what you meant, but I don't see why
not.
> > >
> > > Say you had (all values are SSA values):
> > >
> > > %p0 = malloc()
> > > store i32 0, i32* %p0 // S0
> > > free(%p0)
> > > %p1 = malloc()
> > > store i32 1, i32* %p1 // S1
> > >
> > > and some pass wanted to sink S0 to after S1. So it starts
checking
> > > "from the bottom", as
> > >
> > > Alias(S0, S1) = NoAlias
> > > Alias(S0, malloc()) = NoAlias
> > > Alias(S0, free(%p0)) = MayAlias
> > >
> > > etc. The last MayAlias will prevent it from doing the sink, but I
> > > don't see why it can't ask the Alias(S0, S1) question.
> > >
> >
> > Yea, that's a bit trickier.
> > But we can at least add checks for pairs of pointer accesses that the
> > analysis claims to be ok to reorder.
>
> But that the problem right -- AA told you that S0 and S1 *are* okay to
> reorder.  In fact, if your original program would have been:
>
> p0 = malloc()
> free(p0)
> p1 = malloc()
> *p0 = 20  // S0
> *p1 = 20  // S1
>
> then S0 and S1 would have been okay to reorder (since the original
> program has UB).  But you cannot assert !overlap(p0, p1) in the well
> defined program I mentioned earlier.
>
Yea.. tricky...
Well, if we combine this kind of checking with asan your particular problem
is gone (because asan has quarantine for free-d memory and it won't be
reused immediately)


>
> -- Sanjoy
>
> >
> >
> >
> > >
> > > > > The same problem exists with constant addresses. LLVM
states that
> > > > > constant locations are noalias with themselves, and you
again have
> the
> > > > > "noalias does not imply pointer inequality"
problem.
> > > >
> > > > That won't even have to be special cased, because if we
emit a check
> > > > ConstPtr != ConstPtr,
> > > > such a check will be trivially optimized away.
> > >
> > > But won't it be constant folded to trigger the sanitizer
crash /
> > > warning? That is, since LLVM will state the ConstPtr NoAlias
> > > ConstPtr, you'll emit the check:
> > >
> > > if (overlap(ConstPtr, Sz, ConstPtr, Sz))
> > > abort();
> > >
> > > which will get constant folded to
> > >
> > > if (true) abort();
> > >
> >
> > ah, yes, you are right, then this will have to be special-cased.
> >
> >
> > >
> > > If you meant that the implementation of overlap will differ based
on
> > > whether the pointers are constant pointers or not, I'm not
sure if
> > > that will work, since the fact that the values whose aliasness (I
> > > think I invented a new word :P ) you're checking could have
been
> > > arbitrarily obscured (AA could have looked through PHIs and
selects
> > > etc.) which will prevent you from rediscovering that the values
were
> > > constant pointers in some cases.
> > >
> > > -- Sanjoy
> > >
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170411/65df2abd/attachment.html>