[Soot-list] Obtained all aliased variables?

[Richard Xiao]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20130223/cb336b41/attachment.html