1、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,Pr
2、oblem,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,*of
3、 bounded-length,Set of covered branches,Goal: cover these,Generate individual events Generate sequences of events,Two subproblems,Generating Individual Events,An event is associated with data X & Y coordinates of a tap event geo-location of a change-in-geo-location event content of an incoming SMS e
4、vent etc. 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)
5、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
6、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 = sto
7、p)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)start
8、Service(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)startServic
9、e(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)sho
10、wUrlDialog(); ,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)startServi
11、ce(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
12、 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 C
13、annot perform systematic/exhaustive testing Platform-specific tools (e.g., hierarchy viewer in Android) Limited to GUI Events Cannot handle third-party GUI widgets,Generating Individual Events,Generating Individual Events,Our solution Use concolic execution to generate data associated with events,F,
14、T,F,T,tap(int x, int y) 1 if (x2 ,Generating Individual Tap Events,1,7,2,3,5,x2 & x4,y1 & y3,Generating Individual Tap Events,tap(1, 5),F,T,F,T,1,7,2,3,5,x2 & x4,y1 & y3,Generating Individual Tap Events,tap(1, 5),F1 !(x2 & x4)W3_clicked(),F,T,F,T,1,7,2,3,5,x2 & x4,y1 & y3,(x2 & x4),tap(3, 5),(x2 & x
15、4),Generating Individual Tap Events,tap(1, 5),T1 (x2 & x1 & y3)W2_clicked(),tap(3, 5),F,T,F,T,1,7,2,3,5,x2 & x4,y1 & y3,(x2 & x1 & y3),tap(3, 2),Generating Individual Tap Events,tap(1, 5),(x2 & x1 & y3),tap(3, 5),tap(3, 2),T1 (x2 & x1 & y3)W1_clicked(),F,T,F,T,1,7,2,3,5,x2 & x4,y1 & y3,Example: Musi
16、c Player App,Generate individual events 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
17、algorithm,Goal: cover these,Number of sequences generated for Music Player app by baseline algorithm,Baseline Algorithm Suffers from Path Explosion,ACTEve Algorithm,ACTEve: Automated Concolic Testing of Event-driven programs,ACTEve Algorithm,Set of covered branches,R s.t. R S,S, Set of all event seq
18、uences 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 1,Path 2, 1 subsumes 2 2 1 1 =
19、2,Path Subsumption,Note - memory map C path constraint,Program entry,Path 1,Path 2, 1 subsumes 2 2 1 1 = 2,Path Subsumption,Note - memory map C path constraint,- Dont generate test corresponding to any path that is an extension of 2 - Only generate tests corresponding to paths that are extension of
20、1,Checking path subsumption is very expensive in general Constraint implication check Matching memory map But, path subsumption can be checked cheaply in special cases Read-only events Events whose mutual ordering does not matter etc.,Path Subsumption,event is does not write to any memory location.,
21、Read-only Events,Program Entry, corresponds to 1 , 1,corresponds to ,Path executed for event sequence 1 , , is subsumed by q,Read-only Events,Read-only events are represented as ,ACTEve System Architecture,Empirical Study,Apply ACTEve and baseline algorithms event sequences of length up to 4 16 conc
22、urrently running emulators time budget of 12 hours Measured three metrics running time number of feasible paths number of satisfiability checks,Empirical Results,Future Work,Widget Explosion,Concolic execution to generate individual events ACTEve: an efficient algorithm for bounded exhaustive testin
23、g of event-driven programs Requires only a small fraction (5-36%) of time compared to baseline algorithm Implementation for Android,Main Contributions,Backup slides, 1 1 1 = 2 because does not write to any memory location.,Read-only Events,Program Entry,corresponds to event sequence 1 , 1,correspond
24、s to in 1 , 1 , ,Path executed for input event sequence 1 , ,Output of Androids “Hierarchy Viewer” tool,A Solution: Use Platform-specific Knowlege,A Solution: Use Platform-specific Knowlege,void onTouchEvent(MotionEvent e) int rawX = (int) e.getX(); int rawY = (int) e.getY(); int x = (rawX MARGIN) /
25、 SIZE; int y = (rawY MARGIN) / SIZE; if (x = 0 ,Output of Androids “Hierarchy Viewer” tool,Program Entry,Path 1, . 1 ; is feasible, . 2 ; is feasible,Path 2,Program Entry,Covered branches,Covered branches,same program location,Path Subsumption,Program Entry,Path 1, . 1 ; is feasible, . 2 ; is feasib
26、le,Path 2,Program Entry,Covered branches,Covered branches,same program location,if we explore all paths that extends 1 , then no need to explore any path that extends 2 because no additional branch coverage will be obtained.,Path Subsumption,Path constraint when PAUSE button is tapped on,Example: Music Player App,
