Multithreaded Points-to Analysis for WALA
Andrew Johnson and Stephen Chong
Harvard University
!
Workshop on WALA
13 June 2015
1
Points-to Analysis
•
Foundational static analysis for imperative
languages
•
Over-approximates the memory locations a pointer
expression may refer to at runtime
•
Our focus is on points-to analysis for object
oriented languages
2
Architecture
Code
Multithreaded
Point-to Analysis
WALA front-end!
• Parse Java code
• Translate to SSA IR
Points-to analysis!
• Compute points-to graph
• Compute call graph
3
Architecture
Code
Multithreaded
Point-to Analysis
WALA front-end!
• Parse Java code
• Translate to SSA IR
Points-to analysis!
• Compute points-to graph
• Compute call graph
3
WALA back-end!
• Use points-to results
• Perform other analyses
Abstract Objects
4
Abstract Objects
•
Finite abstraction for the potentially unbounded
number of objects allocated during program
execution
4
Abstract Objects
•
Finite abstraction for the potentially unbounded
number of objects allocated during program
execution
•
Abstract objects represent zero or more concrete
objects
4
Abstract Objects
•
Finite abstraction for the potentially unbounded
number of objects allocated during program
execution
•
Abstract objects represent zero or more concrete
objects
•
One abstract object per allocation site
4
Abstract Objects
•
Finite abstraction for the potentially unbounded
number of objects allocated during program
execution
•
Abstract objects represent zero or more concrete
objects
•
One abstract object per allocation site
•
One abstract object per type
4
Context Sensitivity*
5
*Sharir and Pnueli 1978
Context Sensitivity*
•
Contexts are used to separate different calls to the
same method based on their “context”
5
*Sharir and Pnueli 1978
Context Sensitivity*
•
Contexts are used to separate different calls to the
same method based on their “context”
•
Call-site sensitivity [Emami et al. 1994]
5
*Sharir and Pnueli 1978
Context Sensitivity*
•
Contexts are used to separate different calls to the
same method based on their “context”
•
Call-site sensitivity [Emami et al. 1994]
•
Object Sensitivity [Milanova et al. 2005]
5
*Sharir and Pnueli 1978
Context Sensitivity*
•
•
Contexts are used to separate different calls to the
same method based on their “context”
•
Call-site sensitivity [Emami et al. 1994]
•
Object Sensitivity [Milanova et al. 2005]
Abstract objects can also have contexts: e.g.,
inherit the context from the abstract object’s
allocation site
5
*Sharir and Pnueli 1978
Programmable Context
Sensitivity
6
Programmable Context
Sensitivity
•
Introduced by Smaragdakis et. al. [2011] and extended by Kastrinis
and Smaragdakis [2013]
6
Programmable Context
Sensitivity
•
Introduced by Smaragdakis et. al. [2011] and extended by Kastrinis
and Smaragdakis [2013]
Merge(abstractObj, callSite, context) = newContext
6
Programmable Context
Sensitivity
•
Introduced by Smaragdakis et. al. [2011] and extended by Kastrinis
and Smaragdakis [2013]
Merge(abstractObj, callSite, context) = newContext
MergeStatic(callSite, context) = newContext
6
Programmable Context
Sensitivity
•
Introduced by Smaragdakis et. al. [2011] and extended by Kastrinis
and Smaragdakis [2013]
Merge(abstractObj, callSite, context) = newContext
MergeStatic(callSite, context) = newContext
Record(allocSite, context) = newAbstractObj
6
Programmable Context
Sensitivity
•
Introduced by Smaragdakis et. al. [2011] and extended by Kastrinis
and Smaragdakis [2013]
Merge(abstractObj, callSite, context) = newContext
MergeStatic(callSite, context) = newContext
Record(allocSite, context) = newAbstractObj
•
Allows for easy implementation of new kinds of context sensitivity
(e.g., more sensitivity for certain classes or the cross-product of
existing context sensitivities)
6
Programmable Context
Sensitivity
•
Introduced by Smaragdakis et. al. [2011] and extended by Kastrinis
and Smaragdakis [2013]
Merge(abstractObj, callSite, context) = newContext
MergeStatic(callSite, context) = newContext
Record(allocSite, context) = newAbstractObj
•
Allows for easy implementation of new kinds of context sensitivity
(e.g., more sensitivity for certain classes or the cross-product of
existing context sensitivities)
•
In WALA this is split across ContextSelector and
InstanceKeyFactory, but the idea is the same
6
5JNF T
Performance:
DaCapo Benchmarks*
ǀǂƽ
ǀƽƽ
ƿǂƽ
ƿƽƽ
ƾǂƽ
ƾƽƽ
ǂƽ
ƽ
16 core Amazon EC2 node with 60GB of RAM and Intel Xeon E5-2680 v2 (Ivy Bridge) processors
8"-"
ljǎ UISFBET
YB
E
MBO
QN
DI
BS
TF
MV
Y
EF
JO
MV
O
IP
U
KZ
EC
RM
IT
Q
GP
F
QT
MJ
FD
U
BS
DI
U
PB
CM
UMS
BO
•
3.6 to 6.2 times speedup over WALA with 16 threads (~5
times speedup overall) using WALA’s
ReceiverTypeContextSelector and default allocation behavior
•
More work = more speedup
7
*Blackburn et al. 2006
5JNF T
Performance:
DaCapo Benchmarks*
ǀǂƽ
ǀƽƽ
ƿǂƽ
ƿƽƽ
ƾǂƽ
ƾƽƽ
ǂƽ
ƽ
16 core Amazon EC2 node with 60GB of RAM and Intel Xeon E5-2680 v2 (Ivy Bridge) processors
8"-"
ljǎ UISFBET
YB
E
MBO
QN
DI
BS
TF
MV
Y
EF
JO
MV
O
IP
U
KZ
EC
RM
IT
Q
GP
F
QT
MJ
FD
U
BS
DI
U
PB
CM
UMS
BO
•
3.6 to 6.2 times speedup over WALA with 16 threads (~5
times speedup overall) using WALA’s
ReceiverTypeContextSelector and default allocation behavior
•
More work = more speedup
7
*Blackburn et al. 2006
Scalability:
Type-Sensitive Analysis*
ƾ,ǂƾƽ.ǁ
ƿǂ.ƽ
ǀƿ.ƿ
ǀǀ.ƽ
ǀǁ.ƿ
džǂǀ.ǃ
ǀƿ.ǂ
ǀǂ.Dž
DŽDŽ.ǁ
ƾǂǂ.ǂ
džǃ.ǃ
ƾ.ƿ
ƾ
ƽ.Dž
ƽ.ǃ
ƽ.ǁ
ƽ.ƿ
ƽ
ǀǁ.ǂ
3FMBUJWF 5JNF
16 core Amazon EC2 node with 60GB of RAM and Intel Xeon E5-2680 v2 (Ivy Bridge) processors
ĉSFBET
lj
NJ
nj
ǐ
ljǎ
M
UB
UP
MBO
YB
E
QN I
D
BS
TF
MV Y
EF
JO
MV
PO
UI
KZ
EC
RM
IT
Q
GP
TF
MJQ
FD
U
BS
DI
U
PB
CM
UMS
BO
•
More work means better scalability (8.2x speed up over
single threaded for a type-sensitive analysis)
•
13.5x speedup for jython (over 15 minutes to 70 seconds)
8
*Smaragdakis et al. 2011
Scalability:
Type-Sensitive Analysis*
ƾ,ǂƾƽ.ǁ
ƿǂ.ƽ
ǀƿ.ƿ
ǀǀ.ƽ
ǀǁ.ƿ
džǂǀ.ǃ
ǀƿ.ǂ
ǀǂ.Dž
DŽDŽ.ǁ
ƾǂǂ.ǂ
džǃ.ǃ
ƾ.ƿ
ƾ
ƽ.Dž
ƽ.ǃ
ƽ.ǁ
ƽ.ƿ
ƽ
ǀǁ.ǂ
3FMBUJWF 5JNF
16 core Amazon EC2 node with 60GB of RAM and Intel Xeon E5-2680 v2 (Ivy Bridge) processors
ĉSFBET
lj
NJ
nj
ǐ
ljǎ
M
UB
UP
MBO
YB
E
QN I
D
BS
TF
MV Y
EF
JO
MV
PO
UI
KZ
EC
RM
IT
Q
GP
TF
MJQ
FD
U
BS
DI
U
PB
CM
UMS
BO
•
More work means better scalability (8.2x speed up over
single threaded for a type-sensitive analysis)
•
13.5x speedup for jython (over 15 minutes to 70 seconds)
8
*Smaragdakis et al. 2011
Implementation
•
Mostly lock-free multithreaded implementation
•
Direct representation of the points-to graph
•
Map from variables and object-fields to sets of abstract
objects
•
Use IntMap and IntSet to reduce memory and improve
performance
9
Andersen-style Analysis*
10
*Andersen 1994
Andersen-style Analysis*
Points-to Statement!
(in context c)
Subset constraints
10
*Andersen 1994
Andersen-style Analysis*
Points-to Statement!
(in context c)
Subset constraints
to = new O
10
*Andersen 1994
Andersen-style Analysis*
Points-to Statement!
(in context c)
to = new O
Subset constraints
Pts(to, c) ⊇ {ao}
ao = Record(allocSite, c)
10
*Andersen 1994
Andersen-style Analysis*
Points-to Statement!
(in context c)
to = new O
Subset constraints
Pts(to, c) ⊇ {ao}
ao = Record(allocSite, c)
to = from
10
*Andersen 1994
Andersen-style Analysis*
Points-to Statement!
(in context c)
to = new O
to = from
Subset constraints
Pts(to, c) ⊇ {ao}
ao = Record(allocSite, c)
Pts(to, c) ⊇ Pts(from, c)
10
*Andersen 1994
Andersen-style Analysis*
Points-to Statement!
(in context c)
to = new O
to = from
Subset constraints
Pts(to, c) ⊇ {ao}
ao = Record(allocSite, c)
Pts(to, c) ⊇ Pts(from, c)
to = o.f
10
*Andersen 1994
Andersen-style Analysis*
Points-to Statement!
(in context c)
to = new O
to = from
to = o.f
Subset constraints
Pts(to, c) ⊇ {ao}
ao = Record(allocSite, c)
Pts(to, c) ⊇ Pts(from, c)
∀ ao ∈ Pts(o, c).Pts(to, c) ⊇ FldPts(ao, f)
10
*Andersen 1994
Andersen-style Analysis*
Points-to Statement!
(in context c)
to = new O
to = from
to = o.f
Subset constraints
Pts(to, c) ⊇ {ao}
ao = Record(allocSite, c)
Pts(to, c) ⊇ Pts(from, c)
∀ ao ∈ Pts(o, c).Pts(to, c) ⊇ FldPts(ao, f)
o.f = from
10
*Andersen 1994
Andersen-style Analysis*
Points-to Statement!
(in context c)
to = new O
to = from
to = o.f
o.f = from
Subset constraints
Pts(to, c) ⊇ {ao}
ao = Record(allocSite, c)
Pts(to, c) ⊇ Pts(from, c)
∀ ao ∈ Pts(o, c).Pts(to, c) ⊇ FldPts(ao, f)
∀ ao ∈ Pts(o, c). FldPts(ao, f) ⊇ Pts(from, c)
10
*Andersen 1994
Andersen-style Analysis*
Points-to Statement!
(in context c)
to = new O
to = from
to = o.f
o.f = from
Subset constraints
Pts(to, c) ⊇ {ao}
ao = Record(allocSite, c)
Pts(to, c) ⊇ Pts(from, c)
∀ ao ∈ Pts(o, c).Pts(to, c) ⊇ FldPts(ao, f)
∀ ao ∈ Pts(o, c). FldPts(ao, f) ⊇ Pts(from, c)
10
*Andersen 1994
Andersen-style Analysis*
Points-to Statement!
(in context c)
to = new O
to = from
to = o.f
o.f = from
Subset constraints
Pts(to, c) ⊇ {ao}
ao = Record(allocSite, c)
Pts(to, c) ⊇ Pts(from, c)
∀ ao ∈ Pts(o, c).Pts(to, c) ⊇ FldPts(ao, f)
∀ ao ∈ Pts(o, c). FldPts(ao, f) ⊇ Pts(from, c)
10
*Andersen 1994
Andersen-style Analysis*
Points-to Statement!
(in context c)
to = new O
to = from
to = o.f
o.f = from
Subset constraints
Pts(to, c) ⊇ {ao}
ao = Record(allocSite, c)
Pts(to, c) ⊇ Pts(from, c)
∀ ao ∈ Pts(o, c).Pts(to, c) ⊇ FldPts(ao, f)
∀ ao ∈ Pts(o, c). FldPts(ao, f) ⊇ Pts(from, c)
…
10
*Andersen 1994
Andersen-style Analysis*
Points-to Statement!
(in context c)
to = new O
to = from
to = o.f
o.f = from
Subset constraints
Pts(to, c) ⊇ {ao}
ao = Record(allocSite, c)
Pts(to, c) ⊇ Pts(from, c)
∀ ao ∈ Pts(o, c).Pts(to, c) ⊇ FldPts(ao, f)
∀ ao ∈ Pts(o, c). FldPts(ao, f) ⊇ Pts(from, c)
…
Points-to statements are managed by a work stealing workqueue algorithm (using Java’s fork/join framework)
10
*Andersen 1994
Difference Propagation*
x=y
Pts(x, c) ⊇ Pts(y, c)
11
*e.g., Pearce et al. 2004
Difference Propagation*
x=y
Pts(x, c) ⊇ Pts(y, c)
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
11
*e.g., Pearce et al. 2004
Difference Propagation*
x=y
Pts(x, c) ⊇ Pts(y, c)
o,c
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y,c
ao1,f
x,c
11
*e.g., Pearce et al. 2004
Difference Propagation*
x=y
Pts(x, c) ⊇ Pts(y, c)
o,c
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
Object field
y,c
ao1,f
x,c
11
*e.g., Pearce et al. 2004
Difference Propagation*
x=y
Pts(x, c) ⊇ Pts(y, c)
o,c
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
Object field
y,c
ao1,f
x,c
Reference
variable
replica
11
*e.g., Pearce et al. 2004
Difference Propagation*
x=y
Pts(x, c) ⊇ Pts(y, c)
o,c
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
Object field
y,c
ao1,f
x,c
Reference
variable
replica
Abstract
object
11
*e.g., Pearce et al. 2004
Difference Propagation
x=y
Pts(x, c) ⊇ Pts(y, c)
o,c
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y,c
ao1,f
x,c
12
ao1
Difference Propagation
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y,c
ao1,f
x,c
y,c
⊆
x,c
⊆
ao1,f
12
ao1
Difference Propagation
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y,c
ao1,f
x,c
y,c
⊆
x,c
⊆
ao1,f
12
ao1
Difference Propagation
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y,c
ao1,f
x,c
y,c
⊆
x,c
⊆
ao1,f
12
ao1
Difference Propagation
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y,c
ao1,f
x,c
y,c
⊆
x,c
⊆
ao1,f
12
ao1
Difference Propagation
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y,c
ao1,f
x,c
y,c
⊆
x,c
⊆
ao2
ao1,f
13
Difference Propagation
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y,c
ao1,f
x,c
y,c
⊆
x,c
⊆
ao2
ao1,f
13
Difference Propagation
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y,c
ao1,f
x,c
y,c
⊆
x,c
⊆
ao2
ao1,f
ao2,f
13
Difference Propagation
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y,c
ao1,f
x,c
y,c
⊆
x,c
⊆
⊆ a
ao2
ao1,f
o2 ,
ao2,f
f
13
Lazy Cycle Collapsing*
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y = o.f
∀ ao ∈ Pts(o, c).Pts(y, c) ⊇ FldPts(ao, f)
y,c
ao1,f
x,c
y,c
⊆
x,c
⊆
ao2
ao1,f
14
*e.g., Pearce et al. 2004
Lazy Cycle Collapsing*
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y = o.f
∀ ao ∈ Pts(o, c).Pts(y, c) ⊇ FldPts(ao, f)
y,c
ao1,f
x,c
y,c
⊆
x,c
⊆
ao1,f
⊆
ao2
y,c
14
*e.g., Pearce et al. 2004
Lazy Cycle Collapsing*
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y = o.f
∀ ao ∈ Pts(o, c).Pts(y, c) ⊇ FldPts(ao, f)
y,c
ao1,f
x,c
y,c
⊆
x,c
⊆
ao1,f
⊆
ao2
y,c
14
*e.g., Pearce et al. 2004
Lazy Cycle Collapsing*
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y = o.f
∀ ao ∈ Pts(o, c).Pts(y, c) ⊇ FldPts(ao, f)
y,c
ao1,f
x,c
y,c
⊆
x,c
⊆
ao1,f
⊆
ao2
y,c
14
*e.g., Pearce et al. 2004
Lazy Cycle Collapsing*
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y = o.f
∀ ao ∈ Pts(o, c).Pts(y, c) ⊇ FldPts(ao, f)
y,c
ao1,f
x,c
y,c
⊆
x,c
⊆
ao1,f
⊆
ao2
y,c
14
*e.g., Pearce et al. 2004
Lazy Cycle Collapsing*
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y = o.f
∀ ao ∈ Pts(o, c).Pts(y, c) ⊇ FldPts(ao, f)
y,c
ao1,f
x,c
y,c
⊆
x,c
⊆
ao1,f
⊆
ao2
y,c
14
*e.g., Pearce et al. 2004
Lazy Cycle Collapsing
x=y
o,c
Pts(x, c) ⊇ Pts(y, c)
ao1
o.f = x
∀ ao ∈ Pts(o, c).FldPts(ao, f) ⊇ Pts(x, c)
y = o.f
∀ ao ∈ Pts(o, c).Pts(y, c) ⊇ FldPts(ao, f)
y,c
⊆
x,c
⊆
ao1,f
⊆
rep
ao2
y,c
15
Analysis Options
•
Selectable context sensitivity
•
Single abstract object for particular types
•
java.lang.String, exceptions, primitive wrapper classes,
etc.
•
Reflection (forthcoming)
•
Signatures for native (or library) methods
•
Written in Java or
•
Using WALA’s XML format (forthcoming)
16
Points-to Analysis Related Work
Popular points-to analyses for Java
•
WALA [http://wala.sf.net]
•
Soot [Vallée-Rai et al. 1999] (SPARK [Lhoták and Hendren 2003]
and PADDLE [Lhoták 2006])
•
Doop [Bravenboer and Smaragdakis 2009]
Multi-threaded points-to analysis
•
Graph rewriting algorithms (e.g., [Méndez-Lojo et al. 2010])
•
Replication-based approach [Putta and Nasre 2012]
•
Coarse-grained parallelism for object-oriented languages
[Edvinsson et al. 2011]
21
Summary
17
Summary
•
First multi-threaded implementation of a contextsensitive points-to analysis for an object-oriented
language
17
Summary
•
First multi-threaded implementation of a contextsensitive points-to analysis for an object-oriented
language
•
First multi-threaded points-to analysis to have
programmable context sensitivity à la Kastrinis and
Smaragdakis 2013
17
Summary
•
First multi-threaded implementation of a contextsensitive points-to analysis for an object-oriented
language
•
First multi-threaded points-to analysis to have
programmable context sensitivity à la Kastrinis and
Smaragdakis 2013
•
Significantly improves performance and scales well
17
Summary
•
First multi-threaded implementation of a contextsensitive points-to analysis for an object-oriented
language
•
First multi-threaded points-to analysis to have
programmable context sensitivity à la Kastrinis and
Smaragdakis 2013
•
Significantly improves performance and scales well
•
Coming to WALA soon!
17
Shameless Plug
Exploring and Enforcing Security Guarantees
via Program Dependence Graphs!
!
Tuesday at 14:25 (2:25pm)
PLDI Main BLUE
18