Automated Concolic Testing of Smartphone Apps

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.

• Concolic Testing
• Smartphone Apps
• Test Inputs
• Exhaustive Testing
• Event Sequences

ihedi Follow

Uploaded on Sep 25, 2024 | 0 Views

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.

Presentation Transcript

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.

2. Motivation

3. Motivation Problems with Smartphone Apps

4. Problem Automatically generate test inputs for bounded exhaustive testing of smartphone apps

5. 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.

6. 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

7. Two subproblems 1. Generate individual events 2. Generate sequences of events

8. 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

9. Example: Music Player App Play Pause Rewind Skip Stop Eject

10. 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)

11. 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)

12. 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)

13. 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)

14. 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)

15. 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)

16. 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

17. Generating Individual Events Our solution Use concolic execution to generate data associated with events

18. 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

19. Generating Individual Tap Events x>2 && x<4 1 F T y>1 && y<3 2 7 T F 3 5 tap(1, 5)

20. 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()

21. 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()

22. 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()

23. Example: Music Player App

24. Two subproblems 1. Generate individual events 2. Generate sequences of events

25. Generating Sequences of Events Concatenate individual events generated by concolic execution.

26. 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

27. 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

28. ACTEve Algorithm ACTEve: Automated Concolic Testing of Event-driven programs

29. 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

30. Path Subsumption Program state in concolic execution Maps memory location to values (symbolic or concrete) < ,C > Path constraint

31. 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

32. 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

33. 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.

34. 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, ,??

35. Read-only Events Read-only events are represented as

36. ACTEve System Architecture

37. 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

38. Empirical Results

39. Future Work Widget Explosion

40. 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

41. Backup slides

42. 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, ,??

43. A Solution: Use Platform-specific Knowlege Output of Android s Hierarchy Viewer tool

44. 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; }

45. Path Subsumption Program Entry Program Entry same program location Path ?2 Path ?1 {? ?.?. ?2;? is feasible} {? ?.?. ?1;? is feasible} Covered branches Covered branches

46. 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

47. Example: Music Player App Path constraint when PAUSE button is tapped on