llvm dev - Feb 2016 - Possible soundness issue with available_externally (split from "RFC: Add guard intrinsics")

----- Original Message -----
> From: "James Y Knight via llvm-dev" <llvm-dev at
lists.llvm.org>
> To: "Sanjoy Das" <sanjoy at playingwithpointers.com>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Thursday, February 25, 2016 1:41:43 PM
> Subject: Re: [llvm-dev] Possible soundness issue with
> available_externally (split from "RFC: Add guard intrinsics")
> While we're talking about this, I'd just mention again that the
same
> issue arises for *normal* functions too, when linked into a shared
> library:
> int foo() { return 1; }
> int bar() { return foo(); }
> Now, compare:
> clang -fPIC -O1 -S -o - test.c
> gcc -fPIC -O1 -S -o - test.c
> GCC will refuse to inline foo into bar, or use any information about
> foo in compiling bar, because foo is exported in the dynamic symbol
> table, and thus replaceable via symbol interposition.
> Clang assumes that you won't do that, or that you don't care what
> happens if you do. It will happily inline. And, in absense of
> inlining (e.g. if foo is too long to inline), clang will deduce
> function attributes about foo and rely on those in bar -- despite
> that the call goes through the PLT and could in fact be an entirely
> different unrelated implementation (or, for that matter, a
> differently-optimized version of the same implementation).
> Is that *really* okay?
I'm comfortable with saying that symbol interposition falls outside of the
model we have for the targeted system (at least by default), and thus, this is
okay. We also don't model the possibility of someone hex-editing the binary
;)

-Hal 
> On Wed, Feb 24, 2016 at 6:57 PM, Sanjoy Das via llvm-dev <
> llvm-dev at lists.llvm.org > wrote:
> > Hi all,
> 
> > This is something that came up in the "RFC: Add guard intrinsics
to
> 
> > LLVM" thread; and while I'm not exactly blocked on this,
figuring
> > out
> 
> > a path forward here will be helpful in deciding if we can use the
> 
> > available_externally linkage type to expression certain semantic
> 
> > properties guard intrinsics will have.
> 
> > Let's start with an example that shows that we have a problem
> > (direct
> 
> > copy/paste from the guard intrinsics thread). Say we have:
> 
> > ```
> 
> > void foo() available_externally {
> 
> > %t0 = load atomic %ptr
> 
> > %t1 = load atomic %ptr
> 
> > if (%t0 != %t1) print("X");
> 
> > }
> 
> > void main() {
> 
> > foo();
> 
> > print("Y");
> 
> > }
> 
> > ```
> 
> > The possible behaviors of the above program are {print("X"),
> 
> > print("Y")} or {print("Y")}. But if we run opt
then we have
> 
> > ```
> 
> > void foo() available_externally readnone nounwind {
> 
> > ;; After CSE'ing the two loads and folding the condition
> 
> > }
> 
> > void main() {
> 
> > foo();
> 
> > print("Y");
> 
> > }
> 
> > ```
> 
> > and some generic reordering
> 
> > ```
> 
> > void foo() available_externally readnone nounwind {
> 
> > ;; After CSE'ing the two loads and folding the condition
> 
> > }
> 
> > void main() {
> 
> > print("Y");
> 
> > foo(); // legal since we're moving a readnone nounwind function
> > that
> 
> > // was guaranteed to execute (hence can't have UB)
> 
> > }
> 
> > ```
> 
> > If we do not inline @foo(), and instead re-link the call site in
> > @main
> 
> > to some non-optimized copy (or differently optimized copy) of @foo,
> 
> > then it is possible for the program to have the behavior
> > {print("Y");
> 
> > print ("X")}, which was disallowed in the earlier program.
> 
> > In other words, opt refined the semantics of @foo() (i.e. reduced
> > the
> 
> > set of behaviors it may have) in ways that would make later
> 
> > optimizations invalid if we de-refine the implementation of @foo().
> 
> > The above example is clearly fabricated, but such cases can come up
> 
> > even if everything is optimized to the same level. E.g. one of the
> 
> > atomic loads in the unrefined implementation of @foo() could have
> > been
> 
> > hidden behind a function call, whose body existed in only one
> > module.
> 
> > That module would then be able to refine @foo() to `ret void` but
> 
> > other modules won't.
> 
> > The only solution I can think of is to redefine
> > available_externally
> 
> > to mean "the only kind of IPO/IPA you can do over a call to this
> 
> > function is to inline it". Redefining available_externally this
way
> 
> > will also let us soundly use it to represent calls to functions
> > that
> 
> > have guard intrinsics, since a failed guard intrinsic basically
> 
> > replaces the function with a "very de-refined"
implementation (the
> 
> > interpreter).
> 
> > What do you think? I don't think implementing the above above will
> > be
> 
> > very difficult, but needless to say, it will still be a fairly
> 
> > non-trivial semantic change (hence I'm not directly jumping to
> 
> > implementation).
> 
> > -- Sanjoy
> 
> > _______________________________________________
> 
> > LLVM Developers mailing list
> 
> > llvm-dev at lists.llvm.org
> 
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160226/796e1c12/attachment.html>

On Feb 26, 2016 8:50 PM, "Hal Finkel" <hfinkel at anl.gov>
wrote:
> *From: *"James Y Knight via llvm-dev" <llvm-dev at
lists.llvm.org>
> *To: *"Sanjoy Das" <sanjoy at playingwithpointers.com>
> *Cc: *"llvm-dev" <llvm-dev at lists.llvm.org>
> *Sent: *Thursday, February 25, 2016 1:41:43 PM
> *Subject: *Re: [llvm-dev] Possible soundness issue with
> available_externally (split from "RFC: Add guard intrinsics")
>
> While we're talking about this, I'd just mention again that the
same issue
> arises for *normal* functions too, when linked into a shared library:
>    int foo() { return 1; }
>    int bar() { return foo(); }
>
> Now, compare:
>   clang -fPIC -O1 -S -o - test.c
>   gcc -fPIC -O1 -S -o - test.c
>
> GCC will refuse to inline foo into bar, or use any information about foo
> in compiling bar, because foo is exported in the dynamic symbol table, and
> thus replaceable via symbol interposition.
>
> Clang assumes that you won't do that, or that you don't care what
happens
> if you do. It will happily inline. And, in absense of inlining (e.g. if foo
> is too long to inline), clang will deduce function attributes about foo and
> rely on those in bar -- despite that the call goes through the PLT and
> could in fact be an entirely different unrelated implementation (or, for
> that matter, a differently-optimized version of the same implementation).
>
> Is that *really* okay?
>
> I'm comfortable with saying that symbol interposition falls outside of
the
> model we have for the targeted system (at least by default), and thus, this
> is okay. We also don't model the possibility of someone hex-editing the
> binary ;)
>
I'm not really okay with it; the current behavior feels unprincipled.

We have a visibility attribute which can be used to control this: On ELF
systems, "default" visibililty allows interposition (unlike on Darwin)
--
that is, it explicitly ALLOWS for replacing the symbol's definition. The
policy of "You can't replace the definition of the symbol, but it is
globally visible" is exactly what the "protected" visibility mode
is for.

If we want to say that you can't interpose by default on ELF targets, that
would be a choice. Then, we should make the default symbol visibility
"protected" instead of "default". But, continuing to
generate calls through
the PLT -- which is only needed because the symbols might be replaced --
while simultaneously making optimizations that are broken if they actually
ARE replaced, seems kinda bogus.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160229/5b864dae/attachment.html>

----- Original Message -----
> From: "James Y Knight" <jyknight at google.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Sanjoy Das" <sanjoy at playingwithpointers.com>,
"llvm-dev"
> <llvm-dev at lists.llvm.org>
> Sent: Monday, February 29, 2016 9:31:24 AM
> Subject: Re: [llvm-dev] Possible soundness issue with
> available_externally (split from "RFC: Add guard intrinsics")
> On Feb 26, 2016 8:50 PM, "Hal Finkel" < hfinkel at anl.gov
> wrote:
> > > From: "James Y Knight via llvm-dev" < llvm-dev at
lists.llvm.org >
> > 
> 
> > > To: "Sanjoy Das" < sanjoy at playingwithpointers.com
>
> > 
> 
> > > Cc: "llvm-dev" < llvm-dev at lists.llvm.org >
> > 
> 
> > > Sent: Thursday, February 25, 2016 1:41:43 PM
> > 
> 
> > > Subject: Re: [llvm-dev] Possible soundness issue with
> > > available_externally (split from "RFC: Add guard
intrinsics")
> > 
> 
> > > While we're talking about this, I'd just mention again
that the
> > > same
> > > issue arises for *normal* functions too, when linked into a
> > > shared
> > > library:
> > 
> 
> > > int foo() { return 1; }
> > 
> 
> > > int bar() { return foo(); }
> > 
> 
> > > Now, compare:
> > 
> 
> > > clang -fPIC -O1 -S -o - test.c
> > 
> 
> > > gcc -fPIC -O1 -S -o - test.c
> > 
> 
> > > GCC will refuse to inline foo into bar, or use any information
> > > about
> > > foo in compiling bar, because foo is exported in the dynamic
> > > symbol
> > > table, and thus replaceable via symbol interposition.
> > 
> 
> > > Clang assumes that you won't do that, or that you don't
care what
> > > happens if you do. It will happily inline. And, in absense of
> > > inlining (e.g. if foo is too long to inline), clang will deduce
> > > function attributes about foo and rely on those in bar -- despite
> > > that the call goes through the PLT and could in fact be an
> > > entirely
> > > different unrelated implementation (or, for that matter, a
> > > differently-optimized version of the same implementation).
> > 
> 
> > > Is that *really* okay?
> > 
> 
> > I'm comfortable with saying that symbol interposition falls
outside
> > of the model we have for the targeted system (at least by default),
> > and thus, this is okay. We also don't model the possibility of
> > someone hex-editing the binary ;)
> 
> I'm not really okay with it; the current behavior feels unprincipled.
> We have a visibility attribute which can be used to control this: On
> ELF systems, "default" visibililty allows interposition (unlike
on
> Darwin) -- that is, it explicitly ALLOWS for replacing the symbol's
> definition. The policy of "You can't replace the definition of the
> symbol, but it is globally visible" is exactly what the
"protected"
> visibility mode is for.
> If we want to say that you can't interpose by default on ELF targets,
> that would be a choice. Then, we should make the default symbol
> visibility "protected" instead of "default". But,
continuing to
> generate calls through the PLT -- which is only needed because the
> symbols might be replaced -- while simultaneously making
> optimizations that are broken if they actually ARE replaced, seems
> kinda bogus.
This makes sense, and I think you understand my concern here: Most programmers
don't understand these issues, nor do they ever expect to use dynamic
interposition. They do expect, however, that the compiler has good IPA and will
use the information it is provided effectively. I'd be happy to make the
default visibility protected, allowing us to continue optimizing well, and
provide a principled behavior otherwise. Given, as you point out, this is the
default on Darwin, is there experience from Darwin porting, or any other
factors, that would indicate this would be a hardship?

Thanks again, 
Hal 

-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160229/1d1d4f83/attachment.html>