Averroes: Letting go of the library!
Karim Ali
Workshop on WALA - PLDI ‘15
June 13th, 2015
public class HelloWorld {
public static void main(String[] args) {
System.out.println("Hello, World!");
}
}
Karim Ali
Averroes: Letting go of the library!
2
public class HelloWorld {
public static void main(String[] args) {
System.out.println("Hello, World!");
}
}
•
~ 8 seconds
•
~ 600 MB of memory
•
> 900 reachable methods
•
> 1,700 call edges
Karim Ali
Averroes: Letting go of the library!
3
Hello, World!
Karim Ali
Averroes: Letting go of the library!
4
Partial-Program Analysis
Karim Ali
Averroes: Letting go of the library!
5
Partial-Program Analysis
I'd like to ignore library code
ignore non-application program
elements (e.g., system libraries)?
what about callbacks?
this would be unsound
but better than nothing
whole-program analysis always pulls
in the world for completeness.
The problem is that the world is fairly large
I am NOT interested in those
Karim Ali
Averroes: Letting go of the library!
6
Partial-Program Analysis
?
Karim Ali
Averroes: Letting go of the library!
7
Ideal Call Graph
Karim Ali
Averroes: Letting go of the library!
8
Ideal Call Graph
Whole-Program
Call Graph
Karim Ali
Averroes: Letting go of the library!
9
Incomplete
Call Graph
(unsound)
Ideal Call Graph
Whole-Program
Call Graph
Karim Ali
Averroes: Letting go of the library!
10
Incomplete
Call Graph
(unsound)
Ideal Call Graph
Whole-Program
Call Graph
Karim Ali
Averroes: Letting go of the library!
Conservative
Call Graph
(highly imprecise)
11
Conservative Assumptions
Analyzed Code
m(){
...
}
call method
?
c.center = new Point(0,0);
modify field
Karim Ali
create object
Averroes: Letting go of the library!
12
Incomplete
Call Graph
(unsound)
Partial-Program
Call Graph
Ideal Call Graph
Whole-Program
Call Graph
Karim Ali
Averroes: Letting go of the library!
Conservative
Call Graph
(highly imprecise)
13
The Separate Compilation
Assumption
Karim Ali
Averroes: Letting go of the library!
14
The Separate Compilation
Assumption
All of the library classes can be compiled in the
absence of the application classes.
Karim Ali
Averroes: Letting go of the library!
15
Constraints
1. Class Hierarchy
5. Field Access
2. Class Instantiation
6. Array Access
3. Local Variables
7. Static Initialization
4. Method Calls
8. Exception Handling
Karim Ali
Averroes: Letting go of the library!
16
Constraints
1. Class Hierarchy
5. Field Access
2. Class Instantiation
6. Array Access
3. Local Variables
7. Static Initialization
4. Method Calls
8. Exception Handling
Karim Ali
Averroes: Letting go of the library!
17
Library Points-to Set (LPT)
Application
pt(v1) =
o1
o3
pt(v3) =
pt(v2) =
Karim Ali
o1
o4
Library
LPT = o2
o1
o3
o5
o2
o3
Averroes: Letting go of the library!
[Tip & Palsberg
OOPSLA’00]
18
Library Callbacks
Application
class A extends L {
m();
}
class B extends L {
m();
}
Karim Ali
Library
class L { 1
m();
}
calls
LPT =
2
A
C
class C {
m();
}
Averroes: Letting go of the library!
19
[K. Ali and O. Lhoták, ECOOP ’13]
Karim Ali
Averroes: Letting go of the library!
20
JAR
SCA
JAR
Karim Ali
Placeholder
Library
Averroes: Letting go of the library!
21
SCA
Application
Placeholder
Library
REF
averroes.Library
REF
REF
Karim Ali
Averroes: Letting go of the library!
22
averroes.Library
Karim Ali
Averroes: Letting go of the library!
23
public class averroes.Library {
public static Object libraryPointsTo;
public static void doItAll() {
// Class instantiation
// Library callbacks
// Field writes
// Array element writes
// Exception Handling
}
}
Karim Ali
Averroes: Letting go of the library!
24
Evaluated for SOOT and DOOP
✓
300x smaller library!
✓
Up to 15x faster analysis
✓
Up to 8x less memory
✓
Precise
✓
Sound
Karim Ali
Averroes: Letting go of the library!
25
Implementation Tweaks
Karim Ali
Averroes: Letting go of the library!
26
Class Loaders in WALA
ClassLoaderReference.Primordial
ClassLoaderReference.Extension
ClassLoaderReference.Application
Karim Ali
Averroes: Letting go of the library!
27
Problem 1: App.methods()
public class Library {
ClassLoaderReference.Primordial
public static void doItAll() {
// Class instantiation
A a = new A();
ClassLoaderReference.Extension
// Library callbacks
a.foo();
ClassLoaderReference.Application
}
}
Karim Ali
Averroes: Letting go of the library!
28
Problem 1: App.methods()
public class Library {
ClassLoaderReference.Primordial
public static void doItAll() {
// Class instantiation
A a = new A();
ClassLoaderReference.Extension
// Library callbacks
a.foo();
ClassLoaderReference.Application
}
}
Karim Ali
Averroes: Letting go of the library!
29
Solution 1: App.methods()
public class Library {
ClassLoaderReference.Primordial
public static void doItAll() {
// Class instantiation
A a = new A();
ClassLoaderReference.Extension
// Library callbacks
a.foo();
ClassLoaderReference.Application
}
}
Karim Ali
Averroes: Letting go of the library!
30
Problem 2: doItAll()
public class Library {
ClassLoaderReference.Primordial
public static void doItAll() {
...
}
}
public class PrintStream {
ClassLoaderReference.Extension
public void println(String s) {
...
Library.doItAll();
...
}
ClassLoaderReference.Application
}
Karim Ali
Averroes: Letting go of the library!
31
Solution
Karim Ali
Averroes: Letting go of the library!
32
public class AbstractLibrary {
public static AbstractLibrary instance;
ClassLoaderReference.Primordial
public abstract void doItAll();
}
public class Library extends AbstractLibrary {
static {
AbstractLibrary.instance = new Library();
}
public void doItAll() {
...
A a = new A();
}
ClassLoaderReference.Application
}
public class PrintStream {
public void println(String s) {
...
AbstractLibrary.instance.doItAll();
...
}
}
Karim Ali
Averroes: Letting go of the library!
ClassLoaderReference.Primordial
33
public class AbstractLibrary {
public static AbstractLibrary instance;
ClassLoaderReference.Primordial
public abstract void doItAll();
}
public class Library extends AbstractLibrary {
static {
AbstractLibrary.instance = new Library();
}
public void doItAll() {
...
A a = new A();
}
ClassLoaderReference.Application
}
public class PrintStream {
public void println(String s) {
...
AbstractLibrary.instance.doItAll();
...
}
}
Karim Ali
Averroes: Letting go of the library!
ClassLoaderReference.Primordial
34
public class AbstractLibrary {
public static AbstractLibrary instance;
ClassLoaderReference.Primordial
public abstract void doItAll();
}
public class Library extends AbstractLibrary {
static {
AbstractLibrary.instance = new Library();
}
public void doItAll() {
...
A a = new A();
}
ClassLoaderReference.Application
}
public class PrintStream {
public void println(String s) {
...
AbstractLibrary.instance.doItAll();
...
}
}
Karim Ali
Averroes: Letting go of the library!
ClassLoaderReference.Primordial
35
Evaluation
Karim Ali
Averroes: Letting go of the library!
36
Evaluation
•
What are the performance gains of using the
placeholder library?
•
How precise is Averroes?
•
Does using the placeholder library affect the
soundness of WALA?
Karim Ali
Averroes: Letting go of the library!
37
Library Size
SCA
ON AVG
300x
SMALLER
Original Library
~ 25 MB
Karim Ali
Placeholder Library
~ 80 KB
Averroes: Letting go of the library!
38
Execution Time
ON AVG
2x
30
FASTER
Execution Time (s)
25
20
15
10
5
0
antlr
bloat
chart
WALAAnalysis
Karim Ali
hsqldb
luindex lusearch
WALAOverhead
pmd
xalan compress
WALAAVEAnalysis
Averroes: Letting go of the library!
db
jack
WALAAVEOverhead
javac
jess
raytrace
AVERROES
39
Memory Usage
ON AVG
2x
1.1
1.0
LESS
Memory Usage (GB)
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0
antlr
bloat
chart
hsqldb
luindex lusearch
WALA
Karim Ali
pmd
xalan compress
db
jack
javac
jess
raytrace
WALAAVE
Averroes: Letting go of the library!
40
Precision of Averroes
Karim Ali
Averroes: Letting go of the library!
41
Precision of Averroes
|WALAAVE \ WALA|
|WALA|
ANTLR
BLOAT
CHART
HSQLDB
LUINDEX
LUSEARCH
PMD
ON AVG
8%
XALAN
COMPRESS
DB
JACK
JAVAC
JESS
RAYTRACE
Karim Ali
Averroes: Letting go of the library!
2.06%
19.66%
22.76%
32.56%
4.35%
10.45%
7.78%
33,100.00%
0.00%
7.04%
3.63%
1.21%
8.70%
0.00%
42
Imprecise Library Callbacks
WALAAVE \ WALA
HSQLDB
org.hsqldb.jdbc.*
577 (70%)
Application
Library
Client Code
JDBC
Interface
JDBC
Implementation
Karim Ali
Averroes: Letting go of the library!
43
Sound(i?)ness
Karim Ali
Averroes: Letting go of the library!
44
Unsoundness w.r.t. Dynamic Call Graphs
|DYNAMIC \ WALA|
|DYNAMIC|
ANTLR
BLOAT
CHART
HSQLDB
LUINDEX
LUSEARCH
PMD
XALAN
COMPRESS
DB
JACK
JAVAC
JESS
RAYTRACE
Karim Ali
|DYNAMIC \ WALAAVE|
|DYNAMIC|
6%
4%
1%
1%
3%
99%
Averroes: Letting go of the library!
6%
4%
45
Reasons for Unsoundness
public void notifyListeners(Event event) {
Object[] ls = this.listenerList.getListenerList();
for (int i = ls.length - 2; i >= 0; i -= 2) {
if (ls[i] == Listener.class) {
((Listener)ls[(i + 1)]).changed(event);
}
}
}
Karim Ali
Averroes: Letting go of the library!
46
Correctness Proof
Based on Featherweight Java
Karim Ali
Averroes: Letting go of the library!
47
FJ
…
m
…
m’
Karim Ali
Averroes: Letting go of the library!
48
Karim Ali
FJ
FJAVE
…
…
m
m
…
…
m’
m’
Averroes: Letting go of the library!
49
Evaluation Summary
✓
300x smaller library!
✓
2x faster
✓
2x less memory
✓
Precise
✓
Sound
Karim Ali
Averroes: Letting go of the library!
50
What’s Next?
Karim Ali
Averroes: Letting go of the library!
51
What’s Next?
Application
Analyzing Large Frameworks
Library
SCA
DOOP
Incremental JAR Generation
Better Reflection Support
Automatic Library Detection
SCA
SCALACG
The Past
Karim Ali
Integration with WALA
The Future
Averroes: Letting go of the library!
52
Analyzing Large Frameworks
P
•
•
•
library is much larger than application
event-based systems => many callbacks
modeling application lifecycle is not trivial
G
The Future
Karim Ali
Averroes: Letting go of the library!
53
Better Reflection Support
better support for reflection
P
automatic library detection
incremental JAR generation
G
The Future
Karim Ali
Averroes: Letting go of the library!
54
Integration with WALA
P
WALA
Analysis Scope
WALA Averroes
Analysis Scope
G
The Future
Karim Ali
Averroes: Letting go of the library!
55
Averroes: Letting go of the library!
Karim Ali
Technische Universität Darmstadt
karimali.ca
https://github.com/karimhamdanali/averroes