Computer Science
Computer Science-2021.gz:143349
Computer Science
20be2dc731652a1f2191a12a6be4e1cdd24503da
CAT: Change-focused Android GUI Testing

Android Apps are frequently updated, every couple of weeks, to keep up with changing user, hardware and business demands. Correctness of App updates is checked through extensive testing. Recent research has proposed tools for automated GUI event generation in Android Apps. These techniques, however, are not efficient at checking App updates as the generated GUI events do not prioritise updates, and instead explore other App behaviours. We address this need in this paper with CAT (Change-focused Android GUI Testing). For App updates, at the source code or GUI level, CAT performs change impact analysis to identify GUI elements affected by the update. CAT then generates length-3 GUI event sequences to interact with these GUI elements. Our empirical evaluations using 21 publicly available open source Android Apps demonstrated that CAT is able to automatically identify GUI elements affected by App updates, generate and execute length-3 GUI event sequences focusing on change-affected GUI elements. Comparison with two popular GUI event generation tools, DroidBot and DroidMate, revealed that CAT was more effective at interacting with the change-affected GUI elements. Finally, CAT was able to detect previously unknown change-related bugs in two Apps.


I. INTRODUCTION
Close to 3 million Apps are available on the Google Play store for Android users. These Apps are frequently updated, typically every week or two, to keep up with changing user, hardware and business demands. To ensure security and correctness, updates in Apps need to be tested thoroughly to ensure changes and existing functionality work as expected.
Several different testing techniques have been proposed in the literature for testing mobile Apps [1]- [10]. Majority of existing work focuses on testing only one version of a mobile App. For updates in Apps, existing test generation work is not effective since it is not focused on updates and may not even exercise them. There is existing body of work on regression test selection [8], [11]- [15] -from an existing suite of tests, regression test selection chooses a subset of tests that exercises updates in an App. QADdroid [11] is the only tool in literature that considers changes and their impact at the GUI level when selecting regression tests. Regression test selection techniques only select tests from an existing test suite, they do not generate new tests that exercise changes. None of the existing techniques support GUI test generation targeting updates in Android Apps.
In this paper, we propose a novel approach for generating GUI events targeting App updates. We support updates to source code and the graphical user interface (GUI). We design and implement a framework named CAT (Changed-focused Android GUI Testing) that first gathers GUI elements impacted by the update (referred to as target GUI elements) and then generates GUI events (or test inputs) to exercise these GUI elements. For updates in the source code, CAT's first step of gathering affected GUI elements entails analysing and tracing impact of changes in source code to target GUI elements. To do this, CAT builds a map relating source code functions to GUI elements and associated Android Activities from the App package file (APK). For updates at the GUI level, CAT gathers all the target GUI elements affected by the update and identifies the Activities associated with them. For the next step of GUI event generation, CAT customises an existing model-based android testing tool, DroidBot [16], to prioritise event generation for target elements. Additionally, CAT generates length-3 event sequences, rather than single events, to interact with the target element. Using event sequences allows for more rigorous testing, exercising the target GUI element in different contexts (sequence of events leading to it).
We evaluate usefulness and effectiveness of CAT in testing App updates with a dataset of 21 open-source Android Apps from the F-Droid App market. We compare performance of CAT against two state of the art model-based GUI testing tools for Android, DroidBot (DB) and DroidMate (DM) [2], [16]. For each App, we generate 1000 input GUI events with all three tools.
CAT was able to trace updates to target GUI elements and generate length-3 event sequences interacting with them in all 21 Apps. We found CAT interacted with the target GUI elements more frequently than DB and DM -69 interactions on average for CAT versus 5 for DB and 3 for DM. We found events generated by CAT interact with the target GUI elements sooner than other tools owing to CAT's prioritisation of target elements in event generation. Finally, CAT was able to reveal previously undetected bugs in two Apps in the dataset -World Weather and BeeCount. DM did not reveal bugs in any Apps, while DB revealed a bug in the World Weather App but not BeeCount. We find the combination of target element priority in event generation along with rigorous target element interaction with length-3 event sequences makes CAT an effective test generation tool for App updates.

II. MOTIVATION
In this section, we highlight the need for changed-focused test input generation with a motivating example -an activelymaintained Android App, Amaze File Manager 1 , with more than 3,000 stars on GitHub. Amaze File Manager is used for Android filesystem management. In addition to basic file operations such as copy and paste, it also supports compression, encryption and cloud service synchronisation. We use the latest version, 3.4.3, of Amaze File Manager in this paper. Commit history for the project revealed that the ZipService.java source file was updated in the latest version. This file contains the implementation for the file compression functionality.
Changes in ZipService.java affect dependent files, Pro-cessViewerFragment.java and MainActivityHelper.java. These two Java files are linked to the compress option in the main menu, according to the layout file menu/contextual.xml used by the MainActivity toolbar. Thus, the target GUI element affected by the update is the compress option. We checked this by clicking the compress option, and found it exercised the changed code in ZipService.java. Figure 1 illustrates the sequence of input events to interact with the target GUI element-compress option: long clicking one item in the file list, clicking the menu icon, and then clicking the compress option. The compress option is included in the toolbar layout of the main Activity and this layout only appears after long clicking a file or folder.
When we run existing test input generation tools such as DM [2] and DB [16] on this App, they explore the GUI model without prioritising interactions with the Compress option. 1 https://github.com/TeamAmaze/AmazeFileManager As a result, these tools may not even exercise the target GUI elements. We monitored events generated by DB as an example, and found it entered the final view in Figure 1 after 59 GUI events. It takes a further 442 GUI events to click the compress option (as it explores the Add ShortCut option in the menu first) which finally triggers the updated implementation in ZipService.java.
The uncertainity observed with existing testing tools in exercising target GUI elements raises the need for a GUI test generation tool that prioritises interactions with these GUI elements. We address this need with CAT.

III. BACKGROUND
Before we discuss our approach in detail, we briefly introduce basic concepts in Android App development and testing.

A. Android Apps
Android Apps run on top of a stack with three main software layers -the Android application framework, the Android Runtime and the Android-customised Linux kernel. The Android application framework provides high-level services via its API in Java classes so that Android Apps do not need to interact with the operating system directly.
The second layer, the Android runtime provides a Dalvik Virtual Machine which is a kind of Java Virtual Machine but specially designed and optimized for Android. A new Android runtime, ART (Android Run-time) is included in recent releases of Android with improved performance and will eventually replace the Dalvik Virtual Machine in the future.
The customised Linux kernel is the last and bottom layer. This layer plays the role of operating system which provides drivers of hardware such as camera, sensors, the screen and physical keys. Low-level memory and network management is also handled by this layer. On top of the Linux kernel, there is a set of libraries programmed in native code including the browser kernel, video and audio decoding, graphics and internet securities.
Android Apps are commonly programmed using Java or Kotlin that are compiled to Java bytecode. Native code can also be included to boost performance. Java bytecode is translated to Dalvik bytecode and stored in a machine executable file in .dex format. Android SDK tools bundle Dalvik bytecode, native code (whenever present) along with any data and resource files into an APK, an Android package, which is an archive file with a .apk extension. The APK file is all that is needed to install the App on Android devices.
To build the APK file, an Android project uses the following components: (i) source class files containing source code implementing classes and functions for the App, (ii) layout-XML files which defines the GUI layout of all the Activities, and (iii) Android manifest which appears in the App root folder as AndroidManifest.xml and describes essential information about the App -package name of the App (used to locate the source code), lists of components  Figure 2 shows the project layout of the Amaze File Manager App in the official IDE, Android Studio [17]. The layout contains the mandatory An-droidManifest.xml file, class files in the java folder and layout, multimedia as well as other resource files in the res folder. In the rest of this section, we describe terms and concepts in Android App development used in the rest of this paper.
An Activity implements a window or screen in the App containing various GUI elements, such as buttons and text areas. Developers can control the behaviour of each Activity by implementing appropriate callbacks for each life-cycle phase (i.e., created, paused, resumed, and destroyed). Activities are first declared in the AndroidManifest.xml file and implemented as Java classes in the source code folder.
GUI elements (also referred to as Views or Widgets) are the basic building blocks for user interactions, such as textboxes, buttons and containers of other GUI elements. Views can be associated to Activities either in the source code or defined in the XML layout files. An Activity uses a GUI registration function, setContentView(), whose parameter is the identify of a layout file to include Views defined in that layout. For instance, the menu as shown in Figure 1 is a fragment Activity and its menu items are text Views. These Views are defined in the main menu layout XML file and this file is referenced in the menu fragment Activity by calling the setContentView() function.
Views are responsible for event handling. Input events may be button clicks, edit text, touch, etc. To respond to an event of a particular type, the View (or GUI element) must register an appropriate event listener and implement the corresponding callback method (called by the Android Framework when the View is triggered by user interaction). For example, if a button is to respond to a click event it must register to View.onClickListener event listener and implement the corresponding onClick() callback method. When a button click event is detected, the Android framework will call the onClick() method of that particular View.
An event sequence is an ordered set of input events. The term state in this paper refers to GUI state which is a collection of GUI information about the current screen and all the GUI elements in it. Amaze file manager App shown in Figure 1 has three different states although it remains in the same Activity. We refer to changed-affected GUI elements as target GUI elements, Activities containing a target GUI element as target Activities and states containing a target GUI element as target states.
As Android Apps are event-driven, inputs are normally in the form of events. Writing or recording input events manually can be arduous and time-consuming [18]. Automated input event generation to test Android Apps is an active area of research. A summary of existing research in Android testing is presented in the next section.

IV. RELATED WORK
CAT is the first Android GUI testing work focusing on App updates. In this Section, we summarise existing work on Android GUI test generation, split into random and model driven testing. We also discuss related research in regression test selection that selects tests based on App updates. a) Android GUI test generation: Random Testing. Android Monkey [19] is a popular random testing tool that examines the GUI and randomly selects events to be exercised in the current state until the number of exercised events exceeds the limit set by user. DynoDroid [20] uses heuristics to select input events rather than being fully random. However, DynoDroid has not been maintained for years and only supports Android version 2.3.5 (Android 10 is current version). Wetzlmaier et al. [21] amplify existing test inputs by injecting random test inputs. This technique gives the user more control than Monkey. None of the existing random testing tools focus on App updates.
Model-based Android Testing. DroidBot (DB) [16] and DroidMate (DM) [2], [22] focus on generating test inputs based on GUI models. DB queries the GUI model of the subject App, computes and executes possible events in this model. DM guides test generation on-the-fly using the GUI model. DB provides an easy to use interface for App exploration. CAT leverages this feature in DB for depth-first App exploration from the start Activity.
b) Regression test selection: Several studies have examined selection of regression tests based on App updates and their impact. Focus of CAT is different -test generation for change affected elements. None of the regression test selection work perform test generation. Nevertheless, both CAT and regression test selection techniques rely on change affected elements identified using change impact analysis. We summarise change impact analysis in Android regression test selection below.
Redroid [13], [15] and ReTestDroid [12] are regression test selection techniques that compare Java source files from original and updated App versions to identify changes and compute change impact at the source code level. Regression tests that exercise change impacted code are selected by the tools. ReTestDroid handles more Java features than Redroid, such as fragments, native code and asynchronous tasks. Both tools perform change impact analysis at the source code level, not considering GUI elements. CAT performs change impact at the source code and GUI level.
QADroid [11] and ATOM [14] also perform test selection for regression versions of Apps. QADroid analyses impact of App updates on code and GUI elements. QADroid, like CAT, builds call graphs based on FlowDroid [23] and links events to function calls using event-function bindings defined in source code. QADroid does not support change impact analysis for dynamic GUI elements, as it does not support Java reflection. ATOM [14] builds an event-flow graph for each App version, whose nodes are Activities and edges capturing events causing Activity transitions. It then computes a delta graph using event-flow graphs of the updated and original App versions. Only events existing in the delta graph is selected for regression testing.

V. OUR APPROACH
We present CAT -Change-focused Android GUI Testing -framework that provides, 1. Change impact analysis and 2. Test input generation for change impacted GUI elements in Android Apps. Our framework is publicly available at https://github.com/CATAndroidTesting/CAT.
The workflow of CAT is presented in Figure 3. The input files to CAT are an APK file and a user-provided change-set for the new version of the App in a JSON file. The JSON file lists the signatures of changed classes and functions in the source code. Output is a set of GUI event sequences to exercise the changes and change impact in the App. Steps in CAT's workflow are as follows, 1. Input Preprocessing. The APK file is preprocessed by our customised version of FlowDroid [23] and Soot [24] to produce a list of layouts in the App, Androidmanifest.XML file, and a call graph representing calling relations between functions in the Java code.

GUI Element and Function Mapping. CAT then traces
GUI elements to the underlying listener functions in the source code. Using this tracing information and the call graph from Step 1, CAT generates a combined graph for tracing between source code functions and GUI elements. 3. Change Impact Analysis. For functions in the source code that are marked as changed, CAT analyses impact of the changes at the GUI level by tracing paths from the changed functions to GUI elements in the combined graph, generated by Step 2. The list of GUI elements generated from this tracing represents the target GUI elements affected by the App update.

Test Input Generation. For target GUI elements from
Step 3, CAT generates test inputs as GUI event sequences that interact with them at least once. 5. Test Execution. We execute GUI event sequences generated by CAT on a test execution engine that is a customised version of DB [16]. We discuss details of the design and implementation of these working phases of CAT in the rest of this section.

A. Step 1: Input Preprocessing
We use FlowDroid [23] along with Soot [24] to preprocess APK files to generate the following -(1) a list of layout files, (2) AndroidManifest.XML file, and (3) a call graph whose nodes are functions in the source code and edges represent calling relations.
Customisation: In its current form, FlowDroid does not expose layout files embedded within other layout files and consequently the GUI elements defined in them. CAT relies on mapping all GUI elements to Activities and functions in the source code for subsequent steps that analyse change impact and generate GUI event sequences. We, therefore, augment FlowDroid with a data collector that allows us to gather information on embedded layout files.

B. Step 2: GUI Element and Function Mapping
In this step, we build a mapping from functions in Java code to GUI elements and Activities using the artifacts generated by FlowDroid in Step 1. This mapping will be useful in determining the GUI events that will help exercise the changed functions in Java code. The mapping is built in two stages -(1) Mapping functions in Java to GUI elements, and (2) Mapping GUI elements to the Activity class.
For the first stage, we initially take the call graph produced by FlowDroid and extract the underlying undirected graph from it that captures function dependencies. We refer to this undirected call graph as function graph. Next, we identify listeners in the function graph that get triggered when there is an interaction with a corresponding item in the GUI. We then expand the function graph with additional nodes for GUI elements and edges between listener nodes and the GUI element nodes they register an event for. Output of the first stage is the expanded function graph that contains functions and GUI elements as nodes with undirected edges representing calling relationships.
In the second stage, we start by extracting all Activities from AndroidManifest.xml. For each Activity, we track the setContentView() method that is used to render the associated layout at the start. We also track the inflate() method, if present, that is used to change the layout after the Activity starts. We use these methods to map each Activity to the Layout it is associated with. The Layout file lists all the GUI elements that will appear to the user for that Activity. We use the GUI element listing in the Layout file along with the Activity -Layout mapping to build an association between GUI elements and the Activity they reside in.
The information from the first and second stages can be merged using GUI elements as the key values connecting both. Merged information allows us to trace functions in Java to GUI elements that can trigger them and further to Activities where the user can interact with these GUI elements. We refer to this merged information as combined GUI-function map Figure 4 shows the utility of the combined GUI-function map, built from the Amaze file manager example, to trace from a changed function in the source code to a GUI element and then to an Activity that the GUI elelment is contained in. Dependencies between functions are gathered from the function graph.
Dynamic GUI elements are commonly used in Android development with Java reflection. A dynamic GUI element can be referred to in the source code with a symbol whose

Step 2. GUI Element and Function Mapping
Step 3. Change Impact Analysis Step 4b. Test Input Generation

DroidBot
Step 5. Test Execution Fig. 3: Workflow of the CAT framework. value is resolved at runtime. To support change impact involving dynamic GUI elements, we annotate these locations so we know to explore them at runtime. When the changed Activity is reached, we record which GUI element leads to this Activity. It is worth noting that existing static change impact analysis tools, such as QADroid [11], cannot precisely handle these dynamic features.

C. Step 3: Change Impact Analysis
This step starts from the JSON file with signatures of changed functions (package-Name.className.functionName(parameterList)) identified by the developer. We then perform a depth-first traversal of the combined GUI function map starting from the changed functions. We are only interested in visited nodes that are GUI elements for test input generation in the next step. Transitive closure of all such visited nodes gives the set of target GUI elements. Events that interact with the target GUI elements are capable of executing the changed function in the source code. As shown in Figure 4, interacting with the widget with the id compress in the MainFragment Activity can trigger the changed function compressFiles() through a chain of internal function calls. Output of this step is the set of target GUI elements.

D. Step 4: Test Input Generation
Test input generation with CAT is built on top of DB [16]. CAT uses DB's depth first exploration from the start Activity to examine different states, checking if the target state (screen with target GUI element) is entered. Once DB enters the target state, CAT takes over event generation, prioritising interactions with target GUI elements in this state. For increased rigor, CAT generates length 3 event sequences, rather than a single event, to interact with the target GUI element. These steps in input generation are discussed below. a) Check for the target state: CAT assumes control of input event generation from DB upon first entry into target state. In order to notify CAT, we monitor the states entered by DB, checking if each new state contains a target GUI element identified in Step 3.
b) Prioritise target element interaction: Once we determine that DB has entered the target state, CAT assumes control and generates input events directed at the target GUI element. In the Amaze file manager App in Figure 1, once DB enters the target state containing the compress widget target element, CAT is in control and generates event sequences to interact with the compress widget. The original DB, in place of CAT, would not prioritise interaction with the target element and would instead treat all GUI elements in the target state as equally interesting.
c) Generating length-3 event sequences: For thorough testing of the target element, it would be desirable to interact with it in different contexts, where a context is defined by the sequence of events leading to it. To balance rigor and  [25] use Length-3 event sequences in their GUI testing work. Inspired by this, CAT generates length-3 event sequences for interacting with the target element. CAT is the first Android testing tool to consider permutation of events leading to a GUI element interaction.
We illustrate length-3 event sequences generated by CAT for the New Project screen in the BeeCount App, shown in Figure 5. Change impact analysis in Step 3 marks the SAVE PROJECT as the target GUI element impacted by changes. CAT builds length-3 event sequences that click the SAVE PROJECT option at least once in the sequence. Example sequence generated by CAT is click ADD COUNT -REMOVE COUNT -SAVE PROJECT. Sequences like this enable checking the behaviour of SAVE PROJECT using different combinations of prior events.
It is worth noting that some generated events can cause the app to leave the target state. When this happens, CAT gives control back to DB which may generate a lot of events exploring states unrelated to updates. To minimise time wasted on other screens, event sequences used to reach every state is recorded by DB and CAT uses these recorded sequences to re-enter the target state.

E. Step 5: Test Execution
Event sequences generated by CAT are executed on the Android Emulator. For some event sequences, execution of an event may leave the target state, as mentioned earlier. The remaining events in the sequence can only be executed when the App goes back to the target state. To enable this, CAT gives unique IDs to events and event sequences and marks the execution status of each sequence. When a sequence has remaining events to be performed but the emulator leaves the target state, the paused events are added to a queue. CAT passes control back to DB to use the recorded steps to go back to target state. When DB returns to the target state, control is passed back to CAT to execute events in the queue, if the queue is non-empty, or other generated event sequences.

VI. EXPERIMENT
We evaluate the feasibility and effectiveness of CAT in generating GUI events that exercise target GUI elements. We use 21 Android applications from the F-Droid App market 2 that has a catalogue of free and open source Android applications. We investigate the following research requestions: Q1. Change Impact Analysis: Is CAT able to perform change impact analysis from changed functions in code to GUI elements?
To answer this question, we use CAT to first build the combined GUI-function map that contains both the function graph and GUI-function mapping for all Apps in our dataset. We then traverse the combined map from the changed functions to GUI level to identify target elements. We manually verify if the GUI elements identified are correct and complete by going through the source code for each subject App. Q2. Test generation for changes: Can CAT generate GUI events to exercise target GUI elements faster and more rigorously than popular testing tools -DroidBot (DB), DroidMate-2 (DM)?
For each subject Android application, we run CAT, DB, DM to generate 1000 tests, where each test is a GUI event. We compare how quickly the tools start interacting with the target GUI element. We measure rigor in exercising target GUI elements as number of generated events that interact with the target elements. Q3. Bug Finding: Is CAT able to detect previously undetected bugs in our App dataset? In this question, we assess if CAT is able to identify previously undetected bugs in our dataset of 21 Android Apps. We compare CAT against DB and DM in this assessment. Selected Tools. We select popular model-based test input generation tools DB and DM for our comparison since these were reported in the literature as being easy-to-use and providing high function code coverage. Monkey, a popular random testing tool, is not used in our comparison as it only reports screen coordinates of GUI interactions, not providing details of the interacted GUI element. Mapping the coordinate information to target GUI elements is not trivial, making comparison with our tool difficult.
Subject Apps. We collect subject Apps from the F-Droid App market with released APK files and well maintained commit information. Apps available on F-Droid are open source allowing us to perform change impact analysis. Table I

VII. RESULTS
We generated 1000 GUI events with DB, DM and CAT for each of the subject Apps presented in Section VI. We assess effectiveness of CAT in performing change impact analysis and compare DB, DM and CAT with respect to their effectiveness in exercising target GUI elements. We also report bugs revealed by CAT as a result of the changes. We present our results in the context of the questions in Section VI.

A. Q1. Change Impact Analysis
CAT is able to analyse impact of changes to GUI elements automatically for all 21 subject Apps. Change impact analysis could determine target GUI elements affected for 18 of the 21 Apps, statically. Remaining 3 Apps, (Tricky Tripper, Suntimes and Hibi), allocate dynamic GUI elements which required CAT to perform runtime analysis to determine the target GUI elements (described in Section V-C). CAT is able to complete change impact analysis for all the subject Apps within 30 seconds. Changes in our dataset of Android Apps took different forms. We briefly discuss change impact analysis performed by CAT for these different change types. 1. New GUI element added. This is the most straight forward scenario as the information on affected GUI elements is readily available. CAT locates the new GUI element in the layout XML file, marks the GUI element as target element. It then locates the Activity associated with the layout of the target GUI element, and marks it as target Activity. This scenario appears in 4 subject Apps i.e. Simple Draw, World Scribe, Fate Sheets and Nani. 2. Modification to existing Activity. The target GUI element in this case is the one that is able to enter the modified Activity. GUI elements implemented to render another Activity may be statically or dynamically allocated. 10 Apps in our dataset had this type of change, with 7 of them implementing static GUI elements to render the modified Activity, and the remaining 3 (Tricky Tripper, Suntimes and Hibi) with dynamically allocated GUI elements. CAT traces changes in the Activity source code to static target GUI elements for 7 Apps. Dynamic target elements in the other 3 Apps are identified during depth-first App exploration. 3. Changes to Java functions. Starting from each changed function, CAT traverses the combined GUI-function map to retrieve the GUI element(s) and associated state and Activity impacted by the change. There were 7 Apps in our dataset with changes to functions and CAT was able to retrieve change affected GUI elements for all 7 Apps.

B. Q2. Test Generation for Changes
We assess and compare effectiveness of the tools in exercising the target GUI elements with respect to (1) how quickly they start interaction, and (2) number of target GUI element interactions. To account for non-determinism in the Android environment, we ran each tool 10 times for each App, generating 1000 GUI events each time. Numbers reported in this section are averaged over the 10 runs. a) Number of events to first target element interaction: Figure 6 shows the average number of events each tool used before it first interacted with the target GUI element for all 21 Apps. Smaller number of events is better, as it indicates the tool starts interacting with the target element faster. Failure labels on bars indicate the associated tool did not interact with any target GUI element for that App in all 1000 GUI events.
CAT is the fastest to start interacting with the target element, only needing 83 events, on average, versus 286 for DB and 258 for DM. For 18 of the 21 Apps in Figure 6, CAT needs fewer events than DB or DM to start target element interaction.  This is because when target state is entered, CAT prioritises interaction with target elements unlike the other two tools. On average, DM uses 159 events to enter the target state and a further 99 elements to interact with the target GUI element. In contrast, depth-first exploration used by DB and CAT enables them to reach deeper screens faster. We remind the reader that CAT diverges from DB only after reaching the target state. Both tools use 81 events, on average, to reach target state. DB uses an additional 205 events to start interacting with the target element. On the other hand, CAT only needs 2 additional events to start target element interaction.
DM outperforms DB and CAT on two Apps: BeeCount (App #3) and Trick Tripper (App #20). For BeeCount, shown in Figure 5, the target GUI element is the Save button in the New Project Activity. Entering this Activity requires clicking the New Project button in the start screen. DM clicks this button earlier than DB and CAT (they click on a different button to first go into Settings, perform further events and then return to click the New Project Button). Similarly, For Trick Tripper, the target state containing the target GUI element can be entered after the first screen. DM clicks the button leading to the target state right away while DB and CAT explore many other events and Activities before entering the target state.
For Simple File Manager (App #8), all 3 tools failed to interact with the target GUI element within 1000 events. Target GUI element for this App is a button for creating shortcuts. The state containing this button is not reached by all 3 tools as they all get stuck on a screen for creating passwords, shown in Figure 8. To be able to leave this state, the tools had to provide input events that were exactly the same for initial and confirmation password, which none were able to do in 1000 tries. To avoid getting stuck in such non-target states, CAT provides the developer with an interface to specify an event sequence that leads it directly to the target state. When such a sequence is provided, CAT is able to interact with the target GUI element 90 times with the first interaction happening after 17 events.  Figure 7 gives the frequency of interactions with the target GUI element. We find, in general, DM and DB generate few events to exercise target elements. DM performs 3 target element interactions on average for each App, and DB performs 5 interactions. CAT, on the other hand, performs 69 target element interactions that explore different event orders in length-3 sequences. CAT clearly provides a more rigorous event generation for exercising target GUI elements, outperforming DB and DM on all 21 Apps (as seen in Figure 7). c) Coverage of change affected Java code: We measured cverage of change impacted Java functions as fraction of change impacted Java functions invoked by the input events. Change impact analysis in CAT also gives the set of functions in the code impacted by App updates. For Apps in our dataset, we found input events that interacted with the target GUI element invoked all the change impacted functions in code, achieving 100% coverage. This was true for all 3 tools. Results for change affected function coverage is shown in Table II.

C. Q3. Bug Findings
CAT uncovered changed-related bugs in 2 of the 21 Apps -World Weather and BeeCount. DM did not reveal bugs in any of the Apps, while DB revealed a bug in the World Weather App but not BeeCount. Both Apps have changes at source code level and change-impacted GUI elements are revealed and tested by CAT.
Latest version of World Weather changes the function to query weather information using a public API. CAT identifies the button for changing API key in the Settings Activity as the target GUI element. CAT's first interaction with the target GUI element results in a crash and the App stops execution. Both DB and CAT are able to crash the App by clicking the button for changing API key. However, once the App is restarted, DB does not produce additional events to interact with this target element as it proceeds to interacting with other unvisited elements. CAT, on the other hand, continues to generate and execute events related to this button as it prioritises target element interaction. Interestingly, clicking this button only crashes the first time, further clicks do not result in crashes. This information about first-time only crash is useful for debugging and can only be provided by CAT as it interacts with the target element multiple times. The crash was reported to the App developer and is awaiting a fix at the time of writing this paper.
BeeCount App version in our dataset updates the listener function for Save button in the New Project Activity. CAT identifies the New Project Activity as the target state and the Save button as the target GUI element. The following event sequence generated by CAT -Edit text, Click Menu, Click Save -reveals a bug in the App. Clicking the Menu button after editing text in the New Project Activity loses the edited text. As a result, clicking the Save button does not perform the expected action of saving the edited text. The App is expected to save the text when leaving the New Project Activity so that when the user later returns to this Activity the previously entered text is retained. This bug in the BeeCount App is not revealed by DM and DB. Both DM and DB interact with the target Save button. However, they are unable to generate the event sequence that triggers this bug -Clicking Menu button after editing text, followed by clicking Save. Order of events is important for triggering this bug. CAT's focus on Length 3 event sequences interacting with the target element allows it to trigger bugs that are sensitive to event orders.

D. Threats to Validity
A potential threat to internal validity is bugs in CAT's implementation. To mitigate this threat, we conducted careful code reviews and extensive testing. Further, the implementations are publicly available for other researchers and potential users to check the validity of our results.
A potential threat to the external validity is related to the fact that the set of Android Apps we have considered in this study may not be an accurate representation of the App under test. We attempt to reduce the selection bias by using a dataset of 21 apps from different categories with a variety of Android features.
A threat to construct validity is caused by restricting the number of GUI events generated by all 3 tools to 1000. Restriction to 1000 input events is used by DM and DB in their default settings and we used the same for CAT. We don't believe changing the number of input events will affect the validity of our results as all 3 tools will be uniformly affected. A final threat to validity is the limited number of tools used in comparison. We used DB and DM as they are popular, wellmaintained and easy to use. Including other GUI testing tools in the comparison will strengthen the validity of our results.

VIII. CONCLUSION
We presented the CAT framework for GUI test input generation targeting Android App updates. CAT supports change impact analysis to identify GUI elements affected by updates. It then generates length-3 GUI event sequences for interacting with the target GUI elements.
We empirically evaluated CAT's performance by comparing it to DB and DM over 21 open-source Android Apps. We made the following observations in our experiment. 1) CAT is able to trace changes made at the source code level to affected GUI elements automatically. 2) For target states containing target GUI elements, CAT is able to generate length-3 event sequences. 3) CAT interacts with target GUI elements sooner than DB and DM, CAT requires 83 events, on average, versus 286 for DB and 258 for DM. 4) CAT interacts with the target GUI element more frequently than DB and DM -average of 69 interactions for CAT, 5 for DB and 3 for DM. 5) Change-related bugs are revealed by CAT in two Apps.
Order of input events was crucial in revealing the bug on one of these Apps. Only CAT was able to reveal this event order sensitive bug owing to the length 3 event sequences used to interact with the target element.
In sum, the CAT framework is a novel, automated and effective tool that will help Android developers to test new versions of their Apps focusing on updates. In the future, we plan to optimise CAT's exploration strategy so that target states are entered sooner and the number of events used in other states is reduced.