[Soot-list] Obtained all aliased variables?

[Richard Xiao]

Hi, Zell:

My code has not been integrated into Soot yet. Just implement what I
sketched in the last post, I believe it only takes you one day work.

Cheers,
Xiao


On Sun, Feb 24, 2013 at 4:01 PM, Zhoulai <zell08v at orange.fr> wrote:

> Hi,
>
> I happen to have the same need as Marc-André. Is there implementation code
> that solves  this problem?
>
> Zell.
>
> On Sat, Feb 23, 2013 at 6:57 AM, Richard Xiao <richardxx at cse.ust.hk>wrote:
>
>> Hi, Marc-Andre:
>>
>> I ever did an in-depth study on alias queries.
>>
>> The easiest and efficient way for your task is using an inversed
>> points-to matrix. Suppose the points-to matrix (rows represent pointers,
>> columns are objects) computed by SPARK is P, the transpose of P (pointed-to
>> matrix) is PT. Therefore, for a querying pointer p, execute:
>>
>> <code>
>>
>> ans = empty
>> foreach o in points-to set of p
>>      ans = ans (union) PT[o]
>>
>> </code>
>>
>> That's to say, just extract all rows of PT that are the objects in the
>> points-to set of p, and union these rows.
>>
>> Although this way does not achieve the lower bound for this problem, in
>> practice, especially for Anderson's points-to result, it is very efficient.
>>
>> One more problem is that, maintaining P and PT is very cost. However,
>> notice that many rows in P are identical (i.e. many identical points-to
>> sets), you can compact P by merging the identical rows. Then, using the
>> compressed matrix P to compute PT. Also for Anderson's analysis, this
>> simple compression is very effective.
>>
>> Hope it helps.
>>
>> Regards,
>> Xiao
>>
>>
>>
>> On Sat, Feb 23, 2013 at 12:09 AM, Marc-Andre Laverdiere-Papineau <
>> marc-andre.laverdiere-papineau at polymtl.ca> wrote:
>>
>>> Hello,
>>>
>>> I would like to find out all the variables that are aliased to a given
>>> variable.
>>>
>>>  From what I can see, this is not the first time ppl ask on the ML, and
>>> the answer has always been to check for the intersection... (e.g
>>> http://www.sable.mcgill.ca/pipermail/soot-list/2012-February/004107.html
>>> )
>>>
>>> So far, I have used the non-empty intersection check of the points-to
>>> set, but that's a bit tedious to do when a program has a lot of
>>> variables that are unrelated.
>>>
>>> Does anyone know how to get all the Local and SootField objects that are
>>> aliased to a given Local/SootField? The only option I can think of is
>>> traversing the PAG - but the API doesn't look very much suited for my
>>> needs. Am I missing some magic visitor class???
>>>
>>> Regards,
>>>
>>> --
>>> Marc-André Laverdière-Papineau
>>> Doctorant - PhD Candidate
>>> _______________________________________________
>>> Soot-list mailing list
>>> Soot-list at sable.mcgill.ca
>>> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>>>
>>
>>
>>
>> --
>> Richard Xiao Xiao
>> PhD Student @ CSE @ Hong Kong University of Science and Technology
>> www.cse.ust.hk/~richardxx
>>
>> _______________________________________________
>> Soot-list mailing list
>> Soot-list at sable.mcgill.ca
>> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>>
>>
>


-- 
Richard Xiao Xiao
PhD Student @ CSE @ Hong Kong University of Science and Technology
www.cse.ust.hk/~richardxx
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20130225/1ed188d1/attachment.html