llvm dev - Dec 2016 - How to ask MustAlias queries from DSA results

Hello, everyone!


I'm writing an automatic memory leak fixing tool recently. For my task,
I'm using the DSA (Data Structure Analysis) for alias analysis. In my task,
when I detect a memory leak, I need to find a pointer (in C)
'must-alias' with the corresponding resource.


In DSA, I think if two Value* point to the same DSNode, they
'may-alias'. If two Value* point to different DSNode, they
'not-alias'. However, is it possible to know whether two Value*
'must-alias'?


I checked the AliasAnalysis interface before it was removed from DSA, the
interface never returns MustAlias results. I guess it may not be possible to get
'MustAlias' results from DSA. Will it be possible to modify the DSA code
so that every heap DSNode tracks all possible malloc() calls it comes from?


Thanks for your help.


Best regards, Zhixuan Yang
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161217/8fe26204/attachment.html>

On 12/16/16 9:53 PM, 杨至轩(Zhixuan Yang) via llvm-dev
wrote:
> Hello, everyone!
>
> I'm writing an automatic memory leak fixing tool recently. For my 
> task, I'm using the DSA (Data Structure Analysis) for alias analysis. 
> In my task, when I detect a memory leak, I need to find a pointer (in 
> C) 'must-alias' with the corresponding resource.
If I understand correctly, if you find memory leak, you want to find the 
corresponding call(s) to malloc() that allocated the memory object, 
correct?  Can you more completely explain what you are trying to accomplish?
>
> In DSA, I think if two Value* point to the same DSNode, they 
> 'may-alias'. If two Value* point to different DSNode, they 
> 'not-alias'. However, is it possible to know whether two Value* 
> 'must-alias'?
No.  DSA does not track must-alias information.
>
> I checked the AliasAnalysis interface before it was removed from DSA, 
> the interface never returns MustAlias results. I guess it may not be 
> possible to get 'MustAlias' results from DSA. Will it be possible
to
> modify the DSA code so that every heap DSNode tracks all possible 
> malloc() calls it comes from?
Interesting question.  You could add a "Must-Alias" flag that is 
originally set on a DSNode.  Whenever two DSNodes are merged due to a 
"may-alias" relationship, you could flip the "Must-Alias"
flag off.

However, DSA is a unification-based analysis, so I would think that the 
accuracy of a must-alias feature would be pretty weak.  Also, DSA loses 
precision as it performs more inter-procedural analysis (the local 
analysis will be the most precise but will have many Incomplete DSNodes; 
the Bottom-Up and Top-Down propagate information up and down the call 
graph but will cause further DSNode merging).

It may be that you will need a more accurate points-to analysis 
algorithm for your work.

Regards,

John Criswell
>
> Thanks for your help.
>
> Best regards, Zhixuan Yang
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161217/f890eeaa/attachment.html>

Dear Josh,
> If I understand correctly, if you find memory leak, you want to find the
corresponding call(s) to malloc() that allocated the memory object, correct? 
Can you more completely explain what you are trying to accomplish?

Thanks for your reply. In my task, I use data flow analysis to locate a program
point where a malloc must be leaked (by must leaked, I mean (a) it must be
allocated, (b) must not be free()d and (c) never used in the future). And I want
to fix this leak by finding a pointer must point to that malloc(). So I want to
perform a must-alias query.

>However, DSA is a unification-based analysis, so I would think that the
accuracy of a must-alias feature would be pretty weak.  Also, DSA loses
precision as it performs more inter-procedural analysis (the local analysi>s
will be the most precise but will have many Incomplete DSNodes; the Bottom-Up
and Top-Down propagate information up and down the call graph but will cause
further DSNode merging).

Thanks for your clarification. I agree with you. Even if we implemented a
MustAlias interface in DSA, it will be too weak.


>It may be that you will need a more accurate points-to analysis algorithm
for your work.

In fact, my task can be solved in a simpler (while less elegant) way. If I want
to find pointers must-alias with a malloc() call, I can create a new variable
storing the result returned by the malloc() when it is called.


Thanks for your help.


Best regards, Zhixuan Yang
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161218/dc8ad692/attachment.html>