Transcript Sample Presentation - Ohio State Computer Science and Engineering

Static Analysis of Object References in
RMI-based Java Software
Mariana Sharp
Atanas (Nasko) Rountev
Ohio State University
Reference Analysis for Java


Which objects may variable x refer to?
Builds a points-to graph
x = new A();
x
f
y = new B();
x.f = y;
o1
y
o2
Nasko Rountev - ICSM'05
2
Uses of Reference Information




Clients: SE tools and compilers
Object read-write information
 Side-effect analysis, dependence analysis
Call graph construction
 For interprocedural static analyses
 De-virtualization and inlining
Escape analysis
 Object lifetime for dependence analysis;
synchronization removal; stack allocation
Nasko Rountev - ICSM'05
3
RMI-Based Distributed Java Applications


Java Remote Method Invocation (RMI)
 Object references that cross JVM
boundaries
 Invocations of remote methods
 Parameter passing for entire object graphs
Open questions
 Correct semantic definition of reference
analysis for RMI-based Java applications
 Practical analysis algorithms
Nasko Rountev - ICSM'05
4
Contributions

Theoretical definition of reference analysis for
distributed RMI-based Java applications


Analysis algorithm


Generalizes an algorithm for non-distributed Java
programs
Static analyses for program understanding



Foundation for many other analyses
Inter-component dependencies
Reducing the cost of serialization at RMI calls
Analysis implementation and evaluation
Nasko Rountev - ICSM'05
5
RMI Basics

Code for a set of components C1, C2, …, Cn
 Each Ci executes on a different JVM
 Remote class: implements java.rmi.Remote
 Remote object: instance of a remote class
 Remote reference: pointer to a remote object
 Remote call: x.m( ), x is a remote reference
interface Listener extends java.rmi.Remote
{ void update(Event b); }
class MyListener implements Listener extends …
{ void update(Event b) { … } }
Nasko Rountev - ICSM'05
6
Component “Channel”
interface Channel extends java.rmi.Remote {
void add(Listener c);
void notify(Event d);
}
class MyChannel implements Channel extends … {
private Listener[ ] LST = new Listener[100];
void add(Listener c) { LST[n++] = c; }
void notify(Event d) { … }
static void main() {
Channel e = new MyChannel();
Naming.bind(“foo”,e);
}
…}
Nasko Rountev - ICSM'05
7
Adding a Listener
Component C1
MyChannel
LST
RMI Registry
“foo”
Component C2
f
g
array
c
MyListener
Channel f = (Channel) Naming.lookup(“foo”);
Listener g = new MyListener();
f.add(g);
LST[n++] = c;
Nasko Rountev - ICSM'05
8
Component “Channel”
class Event implements Serializable { …
private Date dt = new Date();
}
interface Listener extends java.rmi.Remote
{ void update(Event b); }
class MyChannel implements Channel extends … {
void notify(Event d) {
for (…) LST[i].update(d);
}
…}
Nasko Rountev - ICSM'05
9
Announcing an Event
Component C1
Component C2
MyChannel
LST
MyListener
b
array
d
Event
Eventcopy dt Datecopy
dt
Date
notify(new Event());
LST[i].update(d);
Nasko Rountev - ICSM'05
10
Theoretical Model




Names for locals and formals: v 1, v 2, v 3, …
 Label with the component id
Names for site s “new X()” – s 1, s 2, s 3, …
Names for de-serialized objects: s k,i
 Exists in the JVM of Ci, but the original
object was created inside the JVM of Ck
Local points-to edges in component Ci
 ( v i , s x )L or ( s1 y , fld, s2 x )L
 x = i or x = k,i ; y = i or y = k,i
Nasko Rountev - ICSM'05
11
Theoretical Model (cont)


Remote points-to edges in component Ci

( v i , s x )R or ( s1 y , fld, s2 x )R

the target object is a remote object
Effects of v1 = v2 in Ci


For ( v2 i , s y )L/R create ( v1 i , s y )L/R
Effects of v1 = v2.fld in Ci

For ( v2 i , s2 y )L and ( s2 y , fld, s1 x )L/R
create ( v1 i , s1 x )L/R
Nasko Rountev - ICSM'05
12
Theoretical Model (cont)




Effects of v.m(w) in Ci for ( v i , s x )R
 Remote call to method m in Cx
Create ( m.this x , s x )L
For ( w i , s2 y )L/R if s2 y is a remote object
 Create ( p x , s2 y )R for formal p
For ( w i , s2 y )L if s2 y is a non-remote
serializable object
 Take the graph of serializable objects
starting at s2 y and create a copy of the
graph in Cx
 Create ( p x , s2 z )L for formal p
Nasko Rountev - ICSM'05
13
Analysis Algorithm

Pointer Assignment Graph [LhotakHendrenCC03]

Nodes are variables and object fields

Edges represent the flow of values

Each node has a local points-to set PtL and a
remote points-to set PtR

v1 = v2 in Ci : edge node(v2 i )node(v1 i )

Represents the subset relationships
PtL(v2 i )  PtL(v1 i ) and
PtR(v2 i )  PtR(v1 i )
Nasko Rountev - ICSM'05
14
Analyses for Program Understanding



Inter-component dependencies between
 a remote call from Ci to Ck
 some statement in Ck
 due to a memory location in Ck
Inter-component dependencies between
 a remote call from Ci to Ck
 a remote call from Cj to Ck
 due to a memory location in Ck
Specialized serialization at remote calls
 Acyclic object graph; unique types
Nasko Rountev - ICSM'05
15
Experimental Study



11 RMI applications
 Between 12 and 125 methods
 Analysis includes ~7000 library methods
Implementation: Soot 2.1 (McGill U.)
 Generalized the points-to analysis in Soot
Analysis running time
 2.8 GHz PC with 1 GB memory
 Time: ~ 5-6 minutes per application
 Special handling of libraries – no replication
 Open issue: pre-computed summary info
Nasko Rountev - ICSM'05
16
Remote Call Sites
Number of remote call sites
Remote calls
Remote references
Serialization
40
35
30
25
20
15
10
5



ss
l
se
or
da
ta
ba
tr
an
sl
at
je
nu
t
jo
dl
n
au
ct
io
ba
nk
el
ch
an
n
tta
sk
rm
fil
es
rv
st
oc
ks
0
Passing of remote references and serialization are common
High precision of the call graph at remote calls
All remote call sites with serialization: used acyclic and
uniquely-typed object graphs
Nasko Rountev - ICSM'05
17
Conclusions and Future Work




Theoretical foundations for reference analysis
Practical algorithm
 Needs more work on handling of the libraries
Initial precision results are promising
Open questions
 Theoretical definitions of other analyses for
RMI software (e.g., for slicing)
 More experimental results


Additional RMI applications
Precision for other analyses (e.g., analysis of
inter-component dependencies)
Nasko Rountev - ICSM'05
18
Questions?
Nasko Rountev - ICSM'05
19