<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Aug 2, 2016 at 5:57 PM, Fee via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi John Criswell,<br>
<br>
Thank you for your helpful answer.<br>
<br>
I think CFL Alias Analysis is not the right way to go because it seems<br>
to avoid building whole points-to sets to be more efficient (correct me<br>
if i am wrong). </blockquote><div><br></div><div>It does not build points-to sets, but does answer all the aliasing queries you can normally ask of LLVM.</div><div>It will answer all of those queries as well as any other anderson's impl will.</div><div><br></div><div>Nothing in LLVM asks or answers "what is the set of things this pointer points-to". </div><div> </div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">So, it would trade compile-time performance for<br>
runtime-security, which is bad.<br></blockquote><div><br></div><div>This is not correct, in the sense that CFL-Anders will give precisely the same answers any other andersen's impl will give about aliasing.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
DSA from poolalloc seems promising, I need to check it.<br>
<br>
 Do you think that an implementation of Andersen's pointer analysis<br>
(like <a href="https://github.com/grievejia/andersen" rel="noreferrer" target="_blank">https://github.com/grievejia/andersen</a>) would work?<br></blockquote><div>That one ignores the effect of certain instructions.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
It seems to be not field-sensitive. Do you have any clue how hard it is<br>
to make an existing analysis field-sensitive?<br></blockquote><div><br></div><div>For LLVM, it requires changes to both the type of constraints one handles, constraint building, constraint optimization, and constraint solving.</div><div><br></div><div>It is non-trivial unless you are very familiar with andersens and it's various implementation techniques.</div><div><br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Regards<br>
—Fredi<br>
<div class="HOEnZb"><div class="h5"><br>
<br>
On 08/01/2016 09:58 PM, John Criswell wrote:<br>
> On 7/31/16 11:48 AM, Fee via llvm-dev wrote:<br>
>> Dear all,<br>
>><br>
>> I want to implement a pass that provides some kind of data flow<br>
>> integrity similar to Write Integrity Testing<br>
>> (<a href="https://www.doc.ic.ac.uk/~cristic/papers/wit-sp-ieee-08.pdf" rel="noreferrer" target="_blank">https://www.doc.ic.ac.uk/~cristic/papers/wit-sp-ieee-08.pdf</a>).<br>
><br>
><br>
>><br>
>> This approach statically determines for each memory write the<br>
>> (conservative, overapproximated) points-to set of locations that can be<br>
>> written by the instruction. Further, it instruments the memory write<br>
>> instruction to prevent a write to a location not in the points-to set.<br>
><br>
> Correct.  I would also point out that their use of Anderson's analysis<br>
> is (most likely) unnecessary.  Because they unify points-to sets<br>
> before instrumenting, they are modifying the end-result of the<br>
> inclusion-based analysis to be what unification-based points-to<br>
> analysis would have computed.  It is not clear to me that anything can<br>
> be gained by using inclusion-based analysis over unification-based<br>
> analysis.<br>
><br>
>><br>
>> How can I get the points-to set, including locations from<br>
>> stack/heap/static variables?<br>
>> How do I approach this problem in general?<br>
><br>
> To the best of my knowledge, the existing LLVM alias analysis passes<br>
> only provide a mod/ref and aliasing query interface.  I don't believe<br>
> they provide a shape graph or points-to sets that can be easily used.<br>
> You might want to check CFL-AA to see what it provides, but I have<br>
> personally never used it.<br>
><br>
> You could use DSA located in the poolalloc project which provides a<br>
> shape graph.  The original SAFECode essentially did what WIT does<br>
> (except that it also protected memory reads and used a very different<br>
> run-time check mechanism, plus it could optimize away provably<br>
> type-safe checks).  SAFECode used DSA's shape graphs to segregate the<br>
> heap, find points-to sets, and learn memory object type information.<br>
> However, in its current shape, you'd need to run DSA prior to most<br>
> LLVM optimizations to get good field sensitivity. Otherwise, DSA will<br>
> lose field sensitivity and provide poor precision in its results.<br>
><br>
> As I need something similar for my research work, my research group<br>
> will be working on either improving or replacing DSA.  However, it'll<br>
> be awhile, so if you need something now, either CFL-AA or DSA will be<br>
> your best bet.<br>
><br>
>> I am new to LLVM.<br>
><br>
> Welcome to the club.<br>
><br>
> Regards,<br>
><br>
> John Criswell<br>
><br>
>><br>
>> Thank you!<br>
>><br>
>> Regards,<br>
>> – Fredi<br>
>><br>
>> _______________________________________________<br>
>> LLVM Developers mailing list<br>
>> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
>> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
><br>
><br>
<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</div></div></blockquote></div><br></div></div>