Automated Concolic Testing of Smartphone Apps
Automated Concolic Testing
of Smartphone Apps
Saswat Anand
Stanford Univ
.
Mayur Naik
Georgia Tech
.
Hongseok Yang
Univ. of Oxford
Mary Jean Harrold
Georgia Tech.
Motivation
Motivation
Problems with Smartphone Apps
Automatically generate
test inputs
for
bounded exhaustive testing
of
smartphone apps
Problem
Test Inputs for Apps
•
Whole-program testing
•
Test input is a sequence of events e
1
, e
2
…,
e
n
•
Types of events: a tap on the screen,
change in geo-location, arrival of a SMS
message, etc.
Bounded Exhaustive Testing of Apps
S, the set of all
event sequences*
s.t. each sequence
takes a unique path
*of bounded-length
Set of
covered
branches
Goal: cover
these
1.
Generate individual events
2.
Generate sequences of events
Two subproblems
Generating Individual Events
•
An event is associated with
d
ata
o
X & Y coordinates of a tap event
o
geo-location of a change-in-geo-location event
o
content of an incoming SMS event
o
e
tc.
•
Data determine which program path is taken
Challenge: Generate the “right” data
for events
Example: Music Player App
Play
Pause
Stop
Eject
Rewind
Skip
Example: Music Player App
public void onClick(View target) {if (target == play)
startService(new Intent(ACTION_PLAY));
else if (target == pause)
startService(new Intent(ACTION_PAUSE));
else if (target == skip)
startService(new Intent(ACTION_SKIP));
else if (target == rewind)
startService(new Intent(ACTION_REWIND));
else if (target == stop)
startService(new Intent(ACTION_STOP));
else if (target == eject)
showUrlDialog();
}
tap(136, 351)
Example: Music Player App
public void onClick(View target) {if (target == play)
startService(new Intent(ACTION_PLAY));
else if (target == pause)
startService(new Intent(ACTION_PAUSE));
else if (target == skip)
startService(new Intent(ACTION_SKIP));
else if (target == rewind)
startService(new Intent(ACTION_REWIND));
else if (target == stop)
startService(new Intent(ACTION_STOP));
else if (target == eject)
showUrlDialog();
}
tap(248, 351)
Example: Music Player App
public void onClick(View target) {if (target == play)
startService(new Intent(ACTION_PLAY));
else if (target == pause)
startService(new Intent(ACTION_PAUSE));
else if (target == skip)
startService(new Intent(ACTION_SKIP));
else if (target == rewind)
startService(new Intent(ACTION_REWIND));
else if (target == stop)
startService(new Intent(ACTION_STOP));
else if (target == eject)
showUrlDialog();
}
tap(360, 351)
Example: Music Player App
public void onClick(View target) {if (target == play)
startService(new Intent(ACTION_PLAY));
else if (target == pause)
startService(new Intent(ACTION_PAUSE));
else if (target == skip)
startService(new Intent(ACTION_SKIP));
else if (target == rewind)
startService(new Intent(ACTION_REWIND));
else if (target == stop)
startService(new Intent(ACTION_STOP));
else if (target == eject)
showUrlDialog();
}
tap(24, 351)
Example: Music Player App
public void onClick(View target) {if (target == play)
startService(new Intent(ACTION_PLAY));
else if (target == pause)
startService(new Intent(ACTION_PAUSE));
else if (target == skip)
startService(new Intent(ACTION_SKIP));
else if (target == rewind)
startService(new Intent(ACTION_REWIND));
else if (target == stop)
startService(new Intent(ACTION_STOP));
else if (target == eject)
showUrlDialog();
}
tap(136, 493)
Example: Music Player App
public void onClick(View target) {if (target == play)
startService(new Intent(ACTION_PLAY));
else if (target == pause)
startService(new Intent(ACTION_PAUSE));
else if (target == skip)
startService(new Intent(ACTION_SKIP));
else if (target == rewind)
startService(new Intent(ACTION_REWIND));
else if (target == stop)
startService(new Intent(ACTION_STOP));
else if (target == eject)
showUrlDialog();
}
tap(305, 544)
Existing alternatives
•
Random Testing
o
Cannot perform systematic/exhaustive testing
•
Platform-specific tools (e.g., hierarchy
viewer in Android)
o
Limited to GUI Events
o
Cannot handle third-party GUI widgets
Generating Individual Events
Generating Individual Events
Our solution
Use concolic execution to generate data
associated with events
F
T
F
T
tap(int x, int y){1 if (x>2 && x<4){2 if (y>1 && y<3)
3
W1_clicked();
4 else
5
W2_clicked();
6 }else
7
W3_clicked();
}
Generating Individual Tap Events
1
7
2
3
5
x>2 && x<4
y>1 && y<3
Generating Individual Tap Events
tap(1, 5)
F
T
F
T
1
7
2
3
5
x>2 && x<4
y>1 && y<3
Generating Individual Tap Events
tap(1, 5)
F
1
!
(
x
>
2
&
&
x
<
4
)
W3_clicked()
F
T
F
T
1
7
2
3
5
x>2 && x<4
y>1 && y<3
(
x
>
2
&
&
x
<
4
)
tap(3, 5)
(
x
>
2
&
&
x
<
4
)
Generating Individual Tap Events
tap(1, 5)
T
1
(
x
>
2
&
&
x
<
4
)
F
2
!
(
y
>
1
&
&
y
<
3
)
W2_clicked()
tap(3, 5)
F
T
F
T
1
7
2
3
5
x>2 && x<4
y>1 && y<3
(
x
>
2
&
&
x
<
4
)
(
y
>
1
&
&
y
<
3
)
tap(3, 2)
Generating Individual Tap Events
tap(1, 5)
(
x
>
2
&
&
x
<
4
)
(
y
>
1
&
&
y
<
3
)
tap(3, 5)
tap(3, 2)
T
1
(
x
>
2
&
&
x
<
4
)
T
2
(
y
>
1
&
&
y
<
3
)
W1_clicked()
F
T
F
T
1
7
2
3
5
x>2 && x<4
y>1 && y<3
Example: Music Player App
❖
❖
❖
❖
❖
❖
❖
❖
❖
❖
❖
1.
Generate individual events
2.
Generate sequences of events
Two subproblems
Generating Sequences of Events
Concatenate individual events generated
by concolic execution.
Baseline Algorithm
Set of
covered
branches
S, Set of all event
sequences s.t. each
sequence takes a
unique path
Baseline
algorithm
Goal: cover
these
Number of sequences generated
for Music Player app by baseline algorithm
Baseline Algorithm Suffers from Path Explosion
ACTEve Algorithm
ACTEve:
A
utomated
C
oncolic
T
esting of
Eve
nt-driven programs
ACTEve Algorithm
Set of
covered
branches
R s.t. R ⊆ S
S, Set of all event
sequences s.t. each
sequence takes a
unique path
Baseline
algorithm
ACTEve
algorithm
Goal: cover
these
ACTEve is
relatively sound
Path Subsumption
Maps memory
location to
values
(symbolic or
concrete)
Path
constraint
Program state in concolic execution
Program entry
Path Subsumption
Program entry
Path Subsumption
•
Checking path subsumption is very
expensive in general
o
Constraint implication check
o
Matching memory map
•
But, path subsumption can be checked
cheaply in special cases
o
Read-only events
o
Events whose mutual ordering does not matter
o
etc.
Path Subsumption
Read-only Events
Program
Entry
❖
❖
❖
❖
❖
❖
❖
❖
❖
❖
❖
Read-only Events
Read-only events are represented as
❖
ACTEve System Architecture
Empirical Study
•
Apply ACTEve and baseline algorithms
o
event sequences of length up to 4
o
16
concurrently running emulators
o
time budget of 12 hours
•
Measured three metrics
o
r
unning time
o
n
umber of feasible paths
o
n
umber of satisfiability checks
Empirical Results
Future Work
Widget
Explosion
1.
Concolic execution to generate individual
events
2.
ACTEve: an efficient algorithm for
bounded exhaustive testing of event-
driven programs
o
Requires only a small fraction (5-36%) of time
compared to baseline algorithm
3.
Implementation for Android
Main Contributions
Backup slides
Read-only Events
Program
Entry
Output of Android’s “Hierarchy Viewer” tool
A
S
o
l
u
t
i
o
n
:
U
s
e
P
l
a
t
f
o
r
m
-
s
p
e
c
i
f
i
c
K
n
o
w
l
e
g
e
A
S
o
l
u
t
i
o
n
:
U
s
e
P
l
a
t
f
o
r
m
-
s
p
e
c
i
f
i
c
K
n
o
w
l
e
g
e
void onTouchEvent(MotionEvent e) {int rawX = (int) e.getX();
int rawY = (int) e.getY();
int x = (rawX – MARGIN) / SIZE;
int y = (rawY – MARGIN) / SIZE;
if (x >= 0 && x < 3 && y >= 0 & y < 3)
{int cell = x + 3 * y;
…
}
Output of Android’s “Hierarchy Viewer” tool
Program
Entry
Program
Entry
Covered
branches
Covered
branches
same program location
P
a
t
h
S
u
b
s
u
m
p
t
i
o
n
Program
Entry
Program
Entry
Covered
branches
Covered
branches
same program location
P
a
t
h
S
u
b
s
u
m
p
t
i
o
n
Path constraint
when PAUSE
button is tapped on
Example: Music Player App
This work was done while I was a student at Georgia Tech with professors from Georgia Tech and Univ. of Oxford.
A smartphone has advanced computing capability and connectivity than traditional phones.
The software that runs on smartphones are called Apps.
In this talk, I will present some ideas on testing smartphone apps.
%Those ideas however apply to other types of similar devices like tablets.
This research focuses on automated concolic testing of smartphone apps, addressing problems and solutions related to generating test inputs for exhaustive testing. It explores the challenges of generating individual events and sequences of events in smartphone applications, aiming to enhance testing coverage and effectiveness.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Automated Concolic Testing of Smartphone Apps Saswat Anand Stanford Univ. Mayur Naik Georgia Tech. Hongseok Yang Univ. of Oxford Mary Jean Harrold Georgia Tech.
Motivation Problems with Smartphone Apps
Problem Automatically generate test inputs for bounded exhaustive testing of smartphone apps
Test Inputs for Apps Whole-program testing Test input is a sequence of events e1, e2 , en Types of events: a tap on the screen, change in geo-location, arrival of a SMS message, etc.
Bounded Exhaustive Testing of Apps S, the set of all event sequences* s.t. each sequence takes a unique path Set of covered branches Goal: cover these *of bounded-length
Two subproblems 1. Generate individual events 2. Generate sequences of events
Generating Individual Events An event is associated with data o X & Y coordinates of a tap event o geo-location of a change-in-geo-location event o content of an incoming SMS event o etc. Data determine which program path is taken Challenge: Generate the right data for events
Example: Music Player App Play Pause Rewind Skip Stop Eject
Example: Music Player App public void onClick(View target) { if (target == play) startService(new Intent(ACTION_PLAY)); else if (target == pause) startService(new Intent(ACTION_PAUSE)); else if (target == skip) startService(new Intent(ACTION_SKIP)); else if (target == rewind) startService(new Intent(ACTION_REWIND)); else if (target == stop) startService(new Intent(ACTION_STOP)); else if (target == eject) showUrlDialog(); } tap(136, 351)
Example: Music Player App public void onClick(View target) { if (target == play) startService(new Intent(ACTION_PLAY)); else if (target == pause) startService(new Intent(ACTION_PAUSE)); else if (target == skip) startService(new Intent(ACTION_SKIP)); else if (target == rewind) startService(new Intent(ACTION_REWIND)); else if (target == stop) startService(new Intent(ACTION_STOP)); else if (target == eject) showUrlDialog(); } tap(248, 351)
Example: Music Player App public void onClick(View target) { if (target == play) startService(new Intent(ACTION_PLAY)); else if (target == pause) startService(new Intent(ACTION_PAUSE)); else if (target == skip) startService(new Intent(ACTION_SKIP)); else if (target == rewind) startService(new Intent(ACTION_REWIND)); else if (target == stop) startService(new Intent(ACTION_STOP)); else if (target == eject) showUrlDialog(); } tap(360, 351)
Example: Music Player App public void onClick(View target) { if (target == play) startService(new Intent(ACTION_PLAY)); else if (target == pause) startService(new Intent(ACTION_PAUSE)); else if (target == skip) startService(new Intent(ACTION_SKIP)); else if (target == rewind) startService(new Intent(ACTION_REWIND)); else if (target == stop) startService(new Intent(ACTION_STOP)); else if (target == eject) showUrlDialog(); } tap(24, 351)
Example: Music Player App public void onClick(View target) { if (target == play) startService(new Intent(ACTION_PLAY)); else if (target == pause) startService(new Intent(ACTION_PAUSE)); else if (target == skip) startService(new Intent(ACTION_SKIP)); else if (target == rewind) startService(new Intent(ACTION_REWIND)); else if (target == stop) startService(new Intent(ACTION_STOP)); else if (target == eject) showUrlDialog(); } tap(136, 493)
Example: Music Player App public void onClick(View target) { if (target == play) startService(new Intent(ACTION_PLAY)); else if (target == pause) startService(new Intent(ACTION_PAUSE)); else if (target == skip) startService(new Intent(ACTION_SKIP)); else if (target == rewind) startService(new Intent(ACTION_REWIND)); else if (target == stop) startService(new Intent(ACTION_STOP)); else if (target == eject) showUrlDialog(); } tap(305, 544)
Generating Individual Events Existing alternatives Random Testing oCannot perform systematic/exhaustive testing Platform-specific tools (e.g., hierarchy viewer in Android) oLimited to GUI Events oCannot handle third-party GUI widgets
Generating Individual Events Our solution Use concolic execution to generate data associated with events
Generating Individual Tap Events x>2 && x<4 tap(int x, int y){ 1 if (x>2 && x<4){ 2 if (y>1 && y<3) 3 W1_clicked(); 4 else 5 W2_clicked(); 6 }else 7 W3_clicked(); } 1 F T y>1 && y<3 2 7 T F 3 5
Generating Individual Tap Events x>2 && x<4 1 F T y>1 && y<3 2 7 T F 3 5 tap(1, 5)
Generating Individual Tap Events x>2 && x<4 1 F T y>1 && y<3 2 7 T F 3 5 (x>2 && x<4) tap(1, 5) tap(3, 5) F1 !(x>2 && x<4) W3_clicked()
Generating Individual Tap Events x>2 && x<4 1 F T y>1 && y<3 2 7 T F 3 5 (x>2 && x<4) (y>1 && y<3) (x>2 && x<4) tap(1, 5) tap(3, 5) tap(3, 2) T1 (x>2 && x<4) F2 !(y>1 && y<3) W2_clicked()
Generating Individual Tap Events x>2 && x<4 1 F T y>1 && y<3 2 7 T F 3 5 (x>2 && x<4) (y>1 && y<3) tap(1, 5) tap(3, 5) tap(3, 2) T1 (x>2 && x<4) T2 (y>1 && y<3) W1_clicked()
Two subproblems 1. Generate individual events 2. Generate sequences of events
Generating Sequences of Events Concatenate individual events generated by concolic execution.
Baseline Algorithm S, Set of all event sequences s.t. each sequence takes a unique path Baseline algorithm Set of covered branches Goal: cover these
Baseline Algorithm Suffers from Path Explosion 25000 20000 15000 10000 5000 0 1 2 3 4 Number of sequences generated for Music Player app by baseline algorithm
ACTEve Algorithm ACTEve: Automated Concolic Testing of Event-driven programs
ACTEve Algorithm ACTEve algorithm S, Set of all event sequences s.t. each sequence takes a unique path Baseline algorithm R s.t. R S Set of covered branches Goal: cover these ACTEve is relatively sound
Path Subsumption Program state in concolic execution Maps memory location to values (symbolic or concrete) < ,C > Path constraint
Path Subsumption Note - memory map C path constraint Program entry Path ?1 Path ?2 < 1,?1> < 2,?2> ?1subsumes ?2 1. ?2 ?1 2. ?1= ?2
Path Subsumption Note - memory map C path constraint Program entry Path ?1 Path ?2 < 1,?1> < 2,?2> ?1subsumes ?2 1. ?2 ?1 2. ?1= ?2 any path that is an extension of ?2 - Only generate tests corresponding to paths that are extension of ?1 - Don t generate test corresponding to
Path Subsumption Checking path subsumption is very expensive in general o Constraint implication check o Matching memory map But, path subsumption can be checked cheaply in special cases o Read-only events o Events whose mutual ordering does not matter o etc.
Read-only Events Program Entry event ??is does not write to any memory location. ? corresponds to ?1, ,?? 1 ? is subsumed by q corresponds to ?? Path ? executed for event sequence ?1, ,??
Read-only Events Read-only events are represented as
Empirical Study Apply ACTEve and baseline algorithms o event sequences of length up to 4 o 16 concurrently running emulators o time budget of 12 hours Measured three metrics o running time o number of feasible paths o number of satisfiability checks
Future Work Widget Explosion
Main Contributions 1. Concolic execution to generate individual events 2. ACTEve: an efficient algorithm for bounded exhaustive testing of event- driven programs o Requires only a small fraction (5-36%) of time compared to baseline algorithm 3. Implementation for Android
Read-only Events Program Entry 1. ?1 ? ?1 2. ?1= ?2because ? does not write to any memory location. corresponds to event sequence ?1, ,?? 1 < 1,?1> corresponds to ?? in ?1, ,?? 1,?? < 2,?1 ? > Path ? executed for input event sequence ?1, ,??
A Solution: Use Platform-specific Knowlege Output of Android s Hierarchy Viewer tool
A Solution: Use Platform-specific Knowlege Output of Android s Hierarchy Viewer tool void onTouchEvent(MotionEvent e) { int rawX = (int) e.getX(); int rawY = (int) e.getY(); int x = (rawX MARGIN) / SIZE; int y = (rawY MARGIN) / SIZE; if (x >= 0 && x < 3 && y >= 0 & y < 3) { int cell = x + 3 * y; }
Path Subsumption Program Entry Program Entry same program location Path ?2 Path ?1 {? ?.?. ?2;? is feasible} {? ?.?. ?1;? is feasible} Covered branches Covered branches
Path Subsumption Program Entry Program Entry same program location Path ?2 Path ?1 if we explore all paths {? ?.?. ?2;? is feasible} that extends ?1, then no need to explore any path that extends ?2 because no additional branch coverage will be obtained. {? ?.?. ?1;? is feasible} Covered branches Covered branches
Example: Music Player App Path constraint when PAUSE button is tapped on
