[Soot-list] How can I tell if the two arrays overlap?

[John Dean]

Marc-Andre,

Your comment below hits the nail on the head: "Java Arrays cannot be
referenced like in C. You cannot do something like &array[12]. So overlap is
a somewhat useless notion." I came to this same conclusion last night.
Previously, I was worried about overlap because I'm borrowing from a 1997
paper by Aart Bik that discusses the need to be concerned about overlapping
arrays used in a loop that are passed in as parameters. The only thing I can
think of is that he was thinking about C and not Java. His prototype tool
was written in C, but it was supposed to be used to analyze Java programs.
I've decided to not worry about overlapping arrays within a loop. If there's
an assignment between one array and another, it shouldn't be a problem for
what I'm doing, since the arrays' indexes won't be offset.

Thanks for confirming my thinking that Java array overlap "is a somewhat
useless notion."

John

-----Original Message-----
From: soot-list-bounces at sable.mcgill.ca
[mailto:soot-list-bounces at sable.mcgill.ca] On Behalf Of Marc-Andre
Laverdiere-Papineau
Sent: Wednesday, August 01, 2012 10:45 AM
To: soot-list at sable.mcgill.ca
Subject: Re: [Soot-list] How can I tell if the two arrays overlap?

Thinking about this, I see the following:

First: do you need to check in-memory overlap, or contents overlap?

My answers below assume the first. For the other, the collection overlap
paper would be your friend.
1- Java Arrays cannot be referenced like in C. You cannot do something like
&array[12]. So overlap is a somewhat useless notion.

2- So you need to check for equality. That can be done at runtime using the
== operator, which checks against the handles AFAIR. That may not work well
if the array is passed between methods.

Statically, I think, constant propagation or SSA form would answer the
question. If the objects are the same based on a definitive analysis
(intersection confluence operator, typically), then you'd have a good
answer.

On 2012-07-29 23:19, John Dean wrote:
> Hi,
>
> If there are two array references with different names for the two 
> arrays, how can I tell if the two arrays overlap (for example, one 
> array is 2-dimensional, and the other array is a row inside the first
array)?
>
> I've searched through the soot api for clues, but I haven't find 
> anything suitable yet. If I was working with Java source code instead 
> of Jimple, I would call arr1.containsAll(arr1), but there's nothing 
> comparable in soot, as far as I can tell. I realize that soot is a 
> static analysis tool, so it won't allow me to find an array element's
value.
>
> I think I know how to retrieve the array references and end up with 
> JArrayRef variables, and I can call JArrayRef's getBase and getIndex 
> methods to get the array variable name and the index, respectively, 
> but I don't know how that helps me.
>
> Maybe if I could somehow get the size of each array and get the 
> starting address of each array, then I suppose I could use that 
> information to tell if the arrays overlapped. That sounds wrong, but maybe
not?
>
> Or maybe I should use each array's retrieved base and then search for 
> definitions of the bases and "chase" the definitions back to see if 
> they intersect. That sounds like a lot of work, and I don't know if 
> it's even possible.
>
> Any advice would be greatly appreciated.
>
> Thanks,
> John
>
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>


--
Marc-André Laverdière-Papineau
Étudiant au doctorat - PhD Student


_______________________________________________
Soot-list mailing list
Soot-list at sable.mcgill.ca
http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list