Route: Roads Not Taken in UI Testing

Algorithm 1 describes how Base Path Construction component executes the original test \(t\) to obtain its execution path \(p\) as the base path. As defined in Section 2, \(p\) is a 5-tuple of \(v_s\) (start state), \(v_f\) (end state), \(V_p\) (base states), \(E_p\) (edges), and \(V_o\) (oracle states). The algorithm first initializes \(E\) and \(V_o\) as an empty set and then launches the AUT. Next, it dumps the current screen of the AUT to obtain the initial state before test execution as the start state and uses it to initialize base states and the variable for previous state (lines 3–6). A dumped screen of an Android app is a widget hierarchy tree in XML format, in which non-leaf nodes are layout widgets and leaf nodes are actionable or visible widgets, such as buttons and text views. We uniquely identify a GUI state by computing a hash value over the widget hierarchy tree.

Route models GUI states by considering all the widgets and node attributes. In other words, we do not abstract away node attributes or values of text boxes, and any change in tree structure or node attribute value leads to a different state. This granularity is required, because sometimes the difference between an oracle state and its previous state is subtle, such as a change of the checked or text attribute of a node. To decrease the likelihood of dynamic content such as timestamps or ads that introduces inaccuracy in Route, we leverage virtualization when we need to revisit base states, i.e., the GUI states in the base path.

Before executing the test, a snapshot of the start state is taken (line 7). We leverage virtualization to save the visited states and later restore and explore them in App Exploration (detailed in the next subsection). In other words, the AUT is installed and executed on a virtual machine (VM) such as Android Virtual Device [20] or VirtualBox VM [39], such that the runtime program state of the AUT, including the underlying OS and emulated hardware, can be stored in a snapshot and fully resumed later. This helps improve the accuracy and performance of GUI state exploration. In prior work [5, 22, 33, 34, 45], a GUI state is resumed by restarting the AUT and replaying the recorded event sequence. However, a shortcoming of this restart-and-replay approach is that the background services and dynamic contents such as timestamps or ads may change after restarting the AUT and the GUI state cannot be reached again. Virtualization addresses this issue. Moreover, the exploration of the AUT can be accelerated, because the snapshots can be restored and processed in parallel with multiple VMs. The practice of using virtualization and snapshots is also adopted by prior work in Android testing [15].

Algorithm 1 executes the original test \(t\) after the initialization steps (line 8). For each \(event \in t\), if the event is not an assertion, then it first executes the event and then obtains \(curState\), the current GUI state after execution (lines 9–12). We subsequently update the base path in terms of the base states \(V_p\) and edges \(E_p\) and take a snapshot of this new state (lines 13–16). However, if the event is an assertion,¹ then it means some checks are performed on the previous state, and we hence update the oracle states \(V_o\) with \(prevState\) (lines 17 and 18). Finally, after the execution of \(t\), the end state is updated and the base path \(p\) is returned as input to the next phase of App Exploration (lines 21–23).

With the base path \(p\) from the original test, App Exploration component performs k-step lookahead on each base node to obtain \(G\), an explored state transition graph of the AUT, as described in Algorithm 2. In particular, the algorithm explores if there are paths with length not greater than \(k\) from a base state \(v\) to another base state. This base-path-directed exploration restricts the possible paths that can be constructed from the graph later, such that the generated tests will not deviate too much from the base path.

Algorithm 2 first initializes \(G\), the graph to be returned, with the states and edges in the base path (line 1). Next, for each base state \(v\in V_p\), it performs initialization steps in lines 3–9. It creates a first-in-first-out \(queue\) to store the event sequences that need to be executed for exploration (line 3). To initialize the queue, it retrieves all actionable widgets from \(v\) (line 4), creates an action event, such as click, for each of them, and enqueues the generated event sequences in \(queue\) (lines 5–9). For example, the solid nodes and edges in Figure 2 depict the initial \(G\) for the test in Listing 1. Moreover, for \(v\) equal to state 2 of Figure 2, \(queue\) is initialized with three single events, which when executed result in exploration of states 3, 5, and 8.

For each event sequence \(events \in queue\), Algorithm 2 first restores the GUI state \(v\) and executes the events sequentially (lines 11–16). The executed events, as well as the encountered GUI states, are also recorded as \(subPath\), a sub-path starting from \(v\) (lines 17–21). Next, if \(curState\), then the GUI state reached after the execution is a base state, and it updates \(G\) with the traversed \(subPath\) (lines 24 and 25). Otherwise, if the length of \(events\) is smaller than the threshold \(k\), then it means we can continue exploring forward from \(v\). To that end, we retrieve all actionable widgets for \(curState\) and create \(newEvents\), a new event sequence by appending an appropriate action event such as click to each of the retrieved widgets (lines 26–29). \(newEvents\) is then enqueued in \(queue\) for further exploration (line 30). For example, for \(k=2\) and \(v\) equal to state 2 in Figure 2, subpaths \((2\rightarrow 3)\) and \((2\rightarrow 5\rightarrow 4)\) will be added to \(G\), since states 3 and 4 belong to \(V_p\). Note that some paths (explored states in Figure 2) are not added to \(G,\) because they do not visit any base states or they exceed the lookahead threshold, e.g., given \(k=3\), the path \((1\rightarrow 8\rightarrow 9\rightarrow 11\rightarrow 4)\) is not explored. After all event sequences in \(queue\) are consumed for all base states \(v\), the algorithm stops and returns \(G\) (line 35). We describe Test Generation in detail in the next section.

With the explored state transition graph of the AUT, the number of candidate paths may grow exponentially and become too many to verify. As a result, Test Generation component prioritizes the candidate execution paths by their difference from the base path (line 10 in Algorithm 3). In other words, we compute a distance score between the base path \(p\) and each candidate path \(p^{\prime }\) with the pathDiff function in Algorithm 4. The paths with the highest distance scores are executed and verified first.

We would like to select the candidate paths that are most different from the base path, as they are more likely to exercise a feature in a different way than the existing test. To that end, we consider the difference between a candidate path and the base path at both the path level and the state level. By path level, we mean how different the two paths are in terms of their length and visited states. At the state level, we further look into the new states in the candidate path and determine the extent they are different from their preceding states.

Algorithm 4 first gets the list of states visited by \(p\) and \(p^{\prime }\) as \(L\) and \(L^ {\prime }\), respectively (lines 2 and 3). It then computes a coarse-grained score (\(d_1\)) about how different \(L\) and \(L^{\prime }\) are in terms of their edit distance (line 4). Here, we treat \(L\) and \(L^{\prime }\) as two strings and the contained state identifiers (hash values) as characters and compute their Levenshtein distance [28], i.e., the number of required edits, inserts, or deletions that converts \(L\) to \(L^{\prime }\). Next, it traverses each state \(v^{\prime }_i \in L^{\prime }\) sequentially. If \(v^{\prime }_i\) is not a base state (i.e., \(v^{\prime }_i \notin L\)), then we compute a fine-grained score to determine how different \(v^{\prime }_i\) and \(v^{\prime }_{i-1}\) (its previous state) are in terms of the edit distance between their XML representations, i.e., XML tree edit distance (line 8). This helps us estimate if the change from \(v^{\prime }_{i-1}\) to \(v^{\prime }_i\) is significant or merely incidental (such as a checkbox is selected). Finally, \(d_1\) and the averaged fine-grained score (\(d_2\)) are normalized into \([0,1]\) and a weighted sum of them is returned (line 13, with \(\alpha =0.5\) in our implementation).

Subject tests. We collected a set of feature-based UI tests from prior work in mobile app testing [12, 42, 43]. We avoided including multiple apps from the same category (e.g., two or more shopping list apps) to ensure our dataset is diverse.²In the dataset from Reference [43], most of the subject apps came with only two or three tests. We hence expanded the original test suites to have at least six test cases for each app. Moreover, we added appropriate assertions to the tests from Reference [42] that had no assertion. The tests with oracles unsupported by our current implementation of Route, such as assertions for Intent (the message object used in Android), were also excluded. Finally, we examined the subject tests to ensure each of them is written for exactly one feature. Table 1 shows the 73 subject tests in our study, including the test names, app names, and the contained GUI events and assertions. With the exception of Writeily Pro and Money Tracker, all of the other subject apps are popular (i.e., 100K+ to 50M+ installs on Google Play).

Implementation. We implemented Route in Python for UI tests written using Appium [2], an open-source and cross-platform testing framework. Existing usage-based tests for the subject apps are written with Appiums’ Python client. The generated tests are stored in JSON format and executed by our test runner. When collecting actionable widgets from current screen (line 4 and line 27 in Algorithm 2), we considered all leaf nodes in the XML representation if the clickable attribute is true. Moreover, the current implementation only supports action click in the App Exploration component, i.e., line 7 and line 29 in Algorithm 2. We do not support system events such as pressing back or home button. Furthermore, Route does not generate text input other than the values used in the original tests.

In terms of the lookahead step in the App Exploration component, i.e., \(k\) in Algorithm 2, we conducted a pilot study to check the quality of the generated tests with different \(k\) and determined \(k=3\) to achieve a good balance between the execution time (the larger the value of \(k\), the larger the search space) and the ability to find tests that cover the same feature as in the original test but in a different way. Regarding the number of generated tests in the Test Generation component, i.e., \(n\) in Algorithm 3, we configured \(n=3,\) because in our experiments, we found that a value higher than 3 results in diminishing returns in terms of the fault detection effectiveness of generated tests and a value substantially lower than 3 sacrifices the ability to detect many defects. We evaluate and discuss how variable \(n\) influences the fault detection effectiveness of the augmented test suites as part of RQ4 in Section 5.5.

Finally, in our experiments, we used VirtualBox VM [39] with Android-x86 7.1 OS [1] installed. The experiments were conducted on a Windows laptop with 2.8 GHz Intel Core i7 CPU and 32 GB RAM. Our experimental data is publicly available [3].

We executed Route to generate 219 new tests (with \(n=3\)) from the 73 original tests in Table 1. During the execution, App Exploration was the most time-consuming phase. On average, it took five hours to finish the exploration for an original test (with a median of 4.4 hours and a standard deviation of 3.8 hours). This is as expected, because the GUI states of the AUT (i.e., snapshots of VM) were repeatedly restored and restarted in this phase. Nevertheless, this phase can be accelerated several times by performing the exploration in parallel with multiple emulators.

To investigate whether Route is able to generate quality tests that verify the same features as the original tests, we manually examined the behavior of the 219 generated tests and categorized them into four groups.

In the deviated tests generated by Route, the oracles in the original tests were satisfied without performing the desired functionality. We inspected all of the deviated tests to understand the reasons behind their generation, as summarized in Table 3. As shown in Table 3, most of the deviated tests resulted from imprecise oracles. A factor contributing to imprecise oracles is duplicate widget ID. For example, in TestDelete for OwnCloud, an existence check of the TextView with ID empty_list_view is performed after deleting a file. However, this widget ID is used in multiple Activities (FileDisplayActivity and UploadListActivity), which resulted in a test that does not perform deletion but with a passed oracle. Using a unique widget ID may prevent such a situation.

Another example of imprecise oracles is TestPageSearch for WordPress, shown in Figure 9. In this test, an oracle verifies a post titled “sour candy” to confirm the search feature works. Nevertheless, the oracle can be satisfied by directly navigating to the post list screen without a search. The same case happened when Route tried to augment TestSearch for Shopping List and Writeily Pro. To avoid this situation, test engineers may provide oracles that more precisely describe the expected program state of the AUT. For example, in addition to specific text about search results such as post title, the test can further check the screen title or Activity name to ensure that the correct screen is displayed.

Another reason for generation of deviated tests is replaced action. For instance, in TestDeleteNote for Writeily Pro, the test first deletes a note and then checks if the TextView with ID empty_hint (hint text for empty folder) appears. However, the existence check can also be satisfied by moving the note elsewhere. To address this situation, we can allow the user of Route to annotate core test steps (e.g., clicking the delete button) in the original tests. Such annotated events are then guaranteed to be included in Test Generation to ensure the generated tests are feature-based.

Although deviated tests are not as useful as other types of generated tests in augmentation of a test suite, they can be insightful for developers to improve the quality of assertions in original tests, e.g., the fact that an assertion passes on multiple screens can potentially indicate a problem with the original test.

To investigate whether the generated tests are advantageous in terms of fault detection effectiveness (FDE), we created mutants for the apps under test with MutApk [17], an open-source mutation testing tool for APK files. It supports 35 mutation operators designed for Android apps [30] and performs the mutation on intermediate representations of the code. We created the mutants with MutApk’s default strategy, in which both the mutation operators and locations of mutated code were picked randomly. The number of mutants created for each app is shown in Table 4.

The percentages of mutants killed by the original test suite and the augmented test suite are shown in Table 1. Note that we generated three more tests for each original test, so the size of augmented test sets is four (one original plus three generated). Table 1 shows that the fault detection effectiveness of the augmented test sets improved on 73% (\(53/73\)) of the subject tests and by up to 39% (in the case of TestCreateNote for Writeily Pro). The mean, median, and standard deviation of the FDE for the original test suites were 4.5%, 3%, and 4.9%, respectively. However, the mean, median, and standard deviation of the FDE for the augmented test suites were 13.3%, 12%, and 8.4%, respectively. In total, the augmented tests were able to kill 38% (\(138/365\)) of the mutants, while the original tests were only able to kill 17% (\(61/365\)) of them. Another perspective from each app regarding the improved fault detection effectiveness is reported in Table 4. Both perspectives indicate that the generated tests are not redundant. They covered additional parts of the AUT that the original tests missed. In other words, Route is capable of augmenting test suites to detect latent faults.

To further understand the types of faults that Route can help identify, we have listed the mutation operators used in our experiment in Table 5. Out of 21 mutation types created with the help of MutApk [17], the original test suites were able to cover 13 of them. However, the test suites augmented by Route outperformed the original suites in terms of both the types of mutants covered and the number of mutants killed. The augmented suites exclusively covered six more mutant types: InvalidKeyIntentPutExtra, InvalidSQLQuery, LengthyGUIListener, NullValueIntentPutExtra, ViewComponentNotVisible, and WrongMainActivity . Furthermore, the number of mutants killed by the augmented suites was significantly (over three times) more than the original suites for the following mutant types: ClosingNullCursor, DifferentActivityIntentDefinition, LengthyGUICreation, NullMethodCallArgument, and WrongStringResource .

Note that the behaviors manifested by the mutants were not necessarily app crashes. For instance, Figure 10 illustrates an alternative way found by Route to create a list in the To Do List app, which is through adding tasks in batch. Here, the mutant created with operator WrongStringResource was exclusively killed by a test generated by Route . The mutation operator modified a menu option that was clicked in one of the tests generated by Route, resulting in the test to fail when executed on the mutant app. Figure 11 depicts another example of a non-crashing failure due to a mutant created with the DifferentActivityIntentDefinition operator. In this case, Route generated a test to add a subject in the School Planner app through adding a Grade, which resulted in exclusively killing the mutant. These examples demonstrate that Route was able to generate additional tests that exposed non-crashing failures.

As mentioned previously, the number of tests generated by Route can be configured by setting the variable \(n\). While expanding the test suites may improve their fault detection effectiveness (FDE), it introduces additional costs in terms of test execution and maintenance. We analyzed how the size of augmented test suites influence the FDE in our experiments and listed the results in Table 6. The results indicate that when we grew the test suites linearly, the improvement was sub-linear in terms of both the FDE and the types of covered mutation operators (CMOs). For example, when we expanded the test suites by 2 fold (from 73 tests to 146 tests, by setting \(n=1\)), the FDE improved by a factor of 1.84 (\(112/61\)). Moreover, in the case that the size of test suites was increased by 4 fold (by setting \(n=3\)), the FDE improved by a factor of 2.26 (\(138/61\)). Finally, increasing \(n\) from 2 to 3 did not improve the number of covered mutant types. We depict the normalized growth of FDE and CMOs along with the suite size in Figure 12. From this experiment, we conclude configuring Route with a value for \(n\) higher than 3 is likely to result in diminishing returns. Developers may choose to set \(n\) in between 1 and 3, depending on their desire to balance between test suite size and FDE.

The major external threat to validity of our results is the generalization to other subject test cases and apps. To mitigate this threat, we constructed our dataset by including different categories of apps. Another external threat to validity is using mutants in place of real faults in the experiments. Nevertheless, prior empirical study [26, 40] indicates a statistically significant correlation between mutant detection and real fault detection. Moreover, we reported the mutation operators covered by both the original and augmented test suites to provide more insights regarding what types of real bugsRoute may be good at revealing. The main internal threat to validity of the proposed approach is the possible mistakes involved in our implementation and experiments. WhenRoute identifies GUI states, dynamic content such as timestamps or ads may introduce inaccuracy, i.e., the XML layout is slightly changed but should be considered as the same screen. We leveraged virtualization to mitigate this issue and did not observe any instance of inaccuracies caused by dynamic content in our experimental results. That said, to prevent such potential inaccuracy caused by dynamic content, one can adopt more sophisticated state abstraction models such as the ones used in prior work [10, 21, 47] to determine which screens are equivalent. Moreover, we manually inspected all of our results to increase our confidence in their correctness. The experimental data is also publicly available for external inspection.

Test augmentation techniques [6, 11, 13, 18, 23, 27, 35, 41, 44, 46, 49, 50] create new tests from existing ones to achieve a given engineering goal, such as improving coverage according to a criterion. Pezze et al. [41] proposed to leverage existing unit tests to construct more complex tests that focus on class interactions to reveal more faults. Yoo and Harman [49] introduced a search-based technique that can generate additional test data from existing test data to improve the input space coverage. Harder et al. [23] presented a test augmentation technique based on operational abstraction, which is a formal specification of program’s runtime behavior that can be dynamically mined. A test suite can be augmented by adding test cases until the operational abstraction stops changing. Tillmann and Schulte [46] proposed to use symbolic execution and constraint solving to help increase code coverage by finding relevant variations of existing unit tests. Similarly, Bloem et al. [13] used symbolic execution and model checking techniques to alter path conditions of existing tests and generate new tests that enter uncovered features of the program. Starting from concrete unit tests, Fraser and Zeller [18] presented an approach to generate parameterized unit tests containing symbolic pre- and post-conditions to achieve higher code coverage. To improve the mutation score of an existing test suite, Baudry et al. [11] introduced a genetic algorithm to guide the search for test cases that kill more mutants. Focusing on the context of regression testing, the work by Santelices et al. [44] adopted dependency analysis and symbolic execution to synthesize new tests with respect to the code changes not covered by existing tests. Another work considering test-suite augmentation for code changes by Kim et al. [27] leverages different test generation algorithms dynamically, since different algorithms have different strengths. Finally, Zhang and Elbaum [50] developed a solution to amplify a test suite for finding bugs in exception handling code.

Route is different from the prior work because it is for GUI tests, while all of the above augmentation techniques are for unit tests. Furthermore, Route aims to generate tests that verify the same functionality as the original tests, which is not the focus of prior work. Finally, unlike Route, none of the above-mentioned techniques target Android apps.

Our work is more related to Thor, proposed by Adamsen et al. [6]. Thor takes existing UI tests for Android apps and injects neutral event sequences to see if the original assertions still pass. Neutral event sequences are a series of operations that are not expected to affect the outcome of the injected test cases, such as rotating the phone or turning the screen off and on. Unlike Route, Thor is not able to find alternative tests for verifying the same functionality, because its goal is to simply expose the AUT to adverse conditions. In other words, Thor cannot generate the types of tests discussed in Section 5.2 in which the same functionality of the AUT is examined with different controllers, input data, or control flows.

Another work related to ours is Testilizer for web applications, proposed by Fard et al. [35]. Testilizer first infers a state flow graph from an existing web test, dynamically explores the graph, and then generates new tests from the updated graph. The goal of Testilizer is to explore new states and apply new and generic assertions learned from existing ones. In other words, the augmentation by Testilizer is not feature-based. It is also not applicable to Android apps.

App crawling based on GUI hierarchy information. Many automated test generation techniques [5, 7, 8, 14, 15, 22, 32, 33, 34, 36, 38, 45, 48] leverage GUI hierarchy information of the AUT and apply different exploration strategies to create and execute GUI events to improve code coverage. For example, given an Android app, CrashScope [38] explores the app by dispatching randomly generated events, which can be system events or GUI events extracted from the GUI hierarchy. While we also leverage GUI hierarchy information for test generation, what distinguishes Route from prior work, including CrashScope, is that our exploration strategy is directed by existing test suites to achieve feature-based augmentation. Note that Route is not another record-and-replay tool, such as Reference [24], because our goal is not to faithfully replay existing tests, but to diverge from them in a manner that allows us to meaningfully examine the same features.

Systematic testing. To perform systematic testing of Android apps, prior work [8, 9, 19, 25, 37] used techniques such as targeted event sequence generation and symbolic execution. Tanzirul and Neamtiu proposed A3E [9], an app crawler that aims to increase app coverage (Activity and method coverage) by prioritizing events that lead to undiscovered states in the app. Mirzaei et al. [37] and Anand et al. [8] introduced concolic testing in Android to automatically explore obscured parts of an app by finding proper events and contextual settings. Jensen et al. [25] introduced a two-phase technique (generating event-handler summaries and concolic testing) that produce backward event sequences from a target line of code to the entry point of the app. Xiang et al. [19] tried to address the environmental challenges of symbolic execution in the presence of various Android SDKs and libraries by deducing a representation of libraries on-the-fly.

Similarly, Route tries to find an event sequence to reach a specific part of the app. However, unlike the above tools, our goal is not to increase the code coverage by reaching unexplored parts of an app. In contrast, we try to find a new path covering the already visited states in existing test cases through different sequence of events. In addition, previous tools primarily focus on achieving certain objectives at the source-code level (i.e., to reach specific lines of code), while Route focuses on covering the same behavior and feature as the original test (i.e., to find a path that covers the terminal and oracle GUI states). Finally, it is worth noting that symbolic execution can be used as a complementary approach together with Route to find proper input values to increase the exploration performance.