Generating Predicate Callback Summaries for the Android Framework

Generating Predicate Callback Summaries
for the Android Framework
Danilo Dominguez Perez and Wei Le
{danilo0,weile}@iastate.edu
May 22, 2017
Departament of Computer Science
Iowa State University
1

Outline
1 Motivation
2 Contributions: Predicate Callback Summaries
3 Lithium Framework
Identify Callback Nodes
Compute Predicate Nodes
Compute Update Nodes
Generate Summary Graphs
4 Using Predicate Callback Summaries
5 Experimental Results
6 Conclusions
2

Outline
1 Motivation
3 Lithium Framework
6 Conclusions
3

Motivation
• Callback methods used extensively across Android API
• API calls can execute different sequences of callbacks
depending on the context
• Can be confusing for developers
• Tools need order of callback methods for interprocedural
analysis or test input generation
4

Control Flow Analysis for Android: Related Work
• Lifecycle of Components
• FlowDroid [PLDI 2014] and IccTA [ICSE 2015]
• No-sleep Bug Detection Tool [MobiSys 2012]
• GUI Models
• MobiGUITAR (Black-box) [IEEE Software 2014]
• GATOR (Grey-box) [ICSE 2015]
• Fixed point permutation of callback methods
• Liang et al. [SPSM 2013]
• API Method Summaries
• EdgeMiner [NDSS 2015]
6

Outline
1 Motivation
3 Lithium Framework
6 Conclusions
7

Contributions: Predicate Callback Summaries
• Designed a summary representation for library methods,
called Predicate Callback Summaries (PCSs)
• all potential orders of callback methods called from an API
method
• conditions that determine the execution of such callback
methods
• Designed algorithm and tool to automatically generate
such summaries
• Provided an evaluation on algorithms and tool
8

Examples of Predicate Callback Summaries
Entry
g.thread == false
onCreate onStartCommand
startService Summary
onStartCommand
g.started = true
Exit
Entry
onUnbind
unbindService Summary
Exit
g.started != true
onDestroy
g.started = false
T F
T
F
1
2
5
6
7
1
2
3
4
5
6
• PCSs have three
types of nodes:
• Callback nodes
• Predicate nodes
• Update nodes
• Edges preserve the
original control ﬂow in
API methods
9

Outline
1 Motivation
3 Lithium Framework
6 Conclusions
10

Outline
1 Motivation
3 Lithium Framework
6 Conclusions
12

1. Identify Callback Nodes
Scan the framework code to identify callback call sites using
pre-computed signatures of potential callback methods
api m2 m3
callback node
13

1. Identify Callback Nodes
Using backward traversal on the call graph we generate a call chain from the
API method to the callback call site {api → m2 → m3 → callback}
api m2 m3
callback node
14

Outline
1 Motivation
3 Lithium Framework
6 Conclusions
15

2. Compute Predicate Nodes
We identify all the conditional branch statements the decide whether the call-
back is executed or not
api m2 m3
16

Summarizing Predicate Nodes
In the example, the variable creatingLoader is solved to: (calling object,
LoaderManager, mCreatingLoader)
Simple Version of LoaderManager class
class LoaderManager {
Loader<D> initLoader(int id, Bundle args,
LoaderManager.LoaderCallbacks<D> c) {
LoaderManager r0 = this;
boolean creatingLoader = r0.mCreatingLoader
if ( creatingLoader == true ) {
throw new IllegalStateException("...");
}
LoaderInfo info = mLoaders.get(id);
if (info == null) {
creatingLoader = true;
c.onCreateLoader();
}
}
}
17

Outline
1 Motivation
3 Lithium Framework
6 Conclusions
18

3. Compute Update Nodes
• To identify update nodes we ﬁnd all the statements that modify variables
that can be used in predicate nodes
• The left operand of the statement on green is solved to (calling object,
LoaderManager, mCreatingLoader)
Simple Version of LoaderManager class
class LoaderManager {
Loader<D> initLoader(int id, Bundle args,
LoaderManager.LoaderCallbacks<D> c) {
LoaderManager r0 = this;
boolean creatingLoader = r0.mCreatingLoader
if (creatingLoader == true) {
throw new IllegalStateException("...");
}
LoaderInfo info = mLoaders.get(id);
if (info == null) {
creatingLoader = true ;
c.onCreateLoader();
}
}
}
19

Outline
1 Motivation
3 Lithium Framework
6 Conclusions
20

4. Generate Summary Graph
• After we marked predicate, update and callback nodes
identiﬁed on the ICFG for each API method found
• We traverse the ICFG for API methods to obtain the
summary graph
21

api m2 m3Summary Graph
22

23

24

15
25

15
26

Outline
1 Motivation
3 Lithium Framework
6 Conclusions
27

Using Predicate Callback Summaries
• Built ICFGs for all entry points (top level functions) for a
given app
• Traversed the ICFG of each entry point and connect call
sites of API methods to their respective PCS
• Then analyzed the PCSs to connect callback nodes to
entry nodes of the ICFG of callback methods
• Generated graphs we called inter-callback ICFGs
28

Using Predicate Callback Summaries
ConnectBot Bug
class MyActivity
extends Activity {
void onStop() {
super.onStop();
this.unbindService(connection);
}
}
class MyService
extends Service {
boolean onUnbind(Intent i) {
...
}
void onDestroy() {
if (wifilock != null &&
wifilock.isHeld())
wifilock.release();
}
}
Entry
unbindService
(connection)
onStop
Exit
super.onStop()
Entry
onUnbind
Exit
return true
Entry
onDestroy
Exit
if (wifilock ...)
2
1
3
4
1
2
3
4
wifilock.release()
3
2
1
returns to onStop
from
unbindService
Entry
unbindService Summary
Exit
g.started != true
g.started = false
T
F
1
3
4
6
29

Outline
1 Motivation
3 Lithium Framework
6 Conclusions
30

Implementation and Experimental Setup
• Computed PCSs for 500 frequently invoked Android APIs
found in 930 apps from Google Play Market and F-droid
• Lithium uses Soot to build ICFGs of Android API methods
• Spark for pointer analysis and call graph construction
• Used 2 heuristics to reduce false positives:
• constraint the size of call chains
• constraint the number of possible callers when generating
call chains
31

Experimental Results: PCSs Are Compact
The results show that while the size of ICFG can reach up
to 208 k, the maximum size of the PCSs is 20772 nodes
– reduction of 99% on average
32

Experimental Results: Accuracy of PCSs
• Generate ground truth for 310 API methods with size of
ICFGs ≤ 1000
• precision of the tool is 97%
• recall of 85%
• For the rest we verify a sample of 300 callback nodes
reported
• The precision of the sample was 61%
• Most of the imprecisions were introduced by the call graph
generated for each API method.
33

Experimental Results: Efﬁciency of Computing PCSs
Time in Ascending Order
0 100 200 300 400 500
050010002000
Method
Time(s)
Time vs Size of Summary
0 5000 10000 15000 20000
050010002000
Size of Summary Graph
Time(s)
34

Experimental Results: Client Analysis
• Built Inter-callback ICFGs for 14 apps
• Average time of 0.3 seconds per app
• Found infeasible paths in 2 apps using predicate and
update nodes using Bodik’s infeasible path detection [FSE
1997]
• Callback sequences from inter-callback ICFGs are present
in 96 out of 97 dynamic traces
35

Outline
1 Motivation
3 Lithium Framework
6 Conclusions
36

Conclusions
• Speciﬁcation for summarizing control ﬂow of callbacks from
library methods
• Computed PCSs with high accuracy for large libraries
• PCSs are compact with 99% reduction over ICFGs
• PCSs allow a precise and fast client analysis on apps
• Future work includes integration of Inter-callback ICFGs
with GUI models
37

Compactness of PCSs
Size of ICFGs versus Size of PCSs
ICFG PCS Callbacks P-Node U-Node
min 2 0 0 0 0
avg 58604 330 55 154 120
max 208683 20772 5820 14794 3807

Experimental Results: Usefulness of PCSs
Construct Apps’ inter-callback ICFGs Using PCSs
App Callbacks API Calls
inter-callback ICFGs
Longest Path Time (s)
min ave max
com.blippex.app 21 4 1 1 2 2 0.2
net.sourceforge.andsys 22 12 1 6 15 9 0.1
com.darknessmap 25 11 1 2 5 4 0.1
de.onyxbits.remotekeyboard 41 29 1 2 4 5 0.2
com.example.android.contactslist 44 11 1 8 23 5 0.2
info.staticfree.SuperGenPass 50 20 2 4 7 5 0.0
com.markuspage.android.atimetracker 65 56 2 4 7 5 0.2
aarddict.android 66 28 1 3 10 13 0.3
de.ub0r.android.websms 73 89 0 3 8 6 0.3
com.google.zxing.client.android 83 14 1 5 34 84 0.2
a2dp.Vol 173 121 1 4 15 15 0.6
org.connectbot 176 108 1 6 27 43 1.1
org.openintents.ﬁlemanager 180 38 1 6 23 44 0.6
com.evancharlton.mileage 241 80 1 2 6 5 0.4

Experimental Results: Usefulness of PCSs
Compare Dynamic Traces and Static Paths
App
Traces Paths
covered-c total covered-p infeasible in traces not in traces
com.blippex 94% 12 12 0 77.8% 22.2%
net.sourceforge.andsys 81% 6 6 0 47% 53%
com.darknessmap 64% 6 6 0 63% 37%
com.example.android.contactslist 80% 6 6 12.5% 67.5% 20%
de.onyxbits.remotekeyboard 66% 6 6 0 56.2% 43.8%
info.staticfree.SuperGenPass 64% 6 6 20.8% 58.4% 20.8%
com.markuspage.android.atimetracker 47% 6 6 0 41% 59%
aarddict.android 65% 6 6 0 3% 97%
de.ub0r.android.websms 43% 6 6 0 21.5 78.5%
com.google.zxing.client.android 57% 6 0 0 0.3% 99.7%
org.openintents.ﬁlemanager 35% 10 10 0 4.2% 95.8%%
org.connectbot 41% 6 6 0 2% 98%
a2dp.Vol 47% 10 9 0 0.4% 99.6%
com.evancharlton.mileage 40% 6 6 0 33.8% 66.2%

Generating Predicate Callback Summaries for the Android Framework

Recommended

More Related Content

What's hot (20)

Similar to Generating Predicate Callback Summaries for the Android Framework (20)

More from MobileSoft (20)

Recently uploaded (20)

Generating Predicate Callback Summaries for the Android Framework