# E2E Web Test Dependency Detection using NLP

Matteo Biagiola  Fondazione Bruno KesslerTrentoItaly<EMAIL_ADDRESS>,  Andrea
Stocco  0000-0001-8956-3894 Università della Svizzera
ItalianaLuganoSwitzerland<EMAIL_ADDRESS>,  Ali Mesbah  University of
British Columbia2332 Main MallVancouver, BCCanadaV6T 1Z4<EMAIL_ADDRESS>,
Filippo Ricca  Università degli Studi di GenovaGenovaItaly
<EMAIL_ADDRESS>and  Paolo Tonella  Università della Svizzera
ItalianaLuganoSwitzerland<EMAIL_ADDRESS>
(2019)

###### Abstract.

E2E web test suites are prone to test dependencies due to the heterogeneous
multi-tiered nature of modern web apps, which makes it difficult for
developers to create isolated program states for each test case. In this
paper, we present the first approach for detecting and validating test
dependencies present in E2E web test suites. Our approach employs string
analysis to extract an approximated set of dependencies from the test code. It
then filters potential false dependencies through natural language processing
of test names. Finally, it validates all dependencies, and uses a novel
recovery algorithm to ensure no true dependencies are missed in the final test
dependency graph. Our approach is implemented in a tool called TEDD and
evaluated on the test suites of six open-source web apps. Our results show
that TEDD can correctly detect and validate test dependencies up to 72% faster
than the baseline with the original test ordering in which the graph contains
all possible dependencies. The test dependency graphs produced by TEDD enable
test execution parallelization, with a speed-up factor of up to 7$\times$.

††journalyear: 2019††copyright: none††conference: Technical Report; 2019; FBK,
Trento, Italy

##  1\. Introduction

Ideally, all tests in a test suite should be independent. However, in
practice, developers create tests that are dependent on each other
(Gyori:2015:RTD:2771783.2771793, ; Zhang:2014:ERT:2610384.2610404, ; pradet, ;
Bell:2015:EDD:2786805.2786823, ; Kappler:2016:FBT:2950290.2983974, ). Test
dependency can be informally defined as follows. Let $T=\langle
t_{1},t_{2},\ldots,t_{n}\rangle$ be a test suite, where each $t_{i}$ is a test
case, whose index $i$ defines an order relation between test cases that
corresponds to the original execution order given by testers. When tests
within $T$ are executed in the original order, all tests execute correctly. If
the original execution ordering is altered, e.g., by executing $t_{2}$ before
$t_{1}$, and the execution of $t_{2}$ fails, we can say that $t_{2}$ depends
on $t_{1}$ for its execution, and that a manifest test dependency exists
(Zhang:2014:ERT:2610384.2610404, ; pradet, ).

Test dependencies inhibit the use of test optimization techniques such as test
parallelization (Bell:virtual, ), test prioritization
(Rothermel:2001:PTC:505464.505468, ), test selection
(Gligoric:2015:PRT:2771783.2771784, ) and test minimization
(Vahabzadeh:ICSE18, ), which all require having independent test cases.
Furthermore, test dependencies can mask program faults and lead to undesirable
misleading side-effects, such as tests that pass when they should fail, tests
that fail when they should pass (Zhang:2014:ERT:2610384.2610404, ; LamZE2015,
), or significant test execution overheads (Bell:2015:EDD:2786805.2786823, ;
Kappler:2016:FBT:2950290.2983974, ).

Web developers frequently use end-to-end (E2E) test automation tools, which
verify the correct functioning of the application in given test scenarios by
means of automated test scripts. Such scripts automate the manual operations
that the end user would perform on the web application’s graphical user
interface (GUI), such as delivering events with clicks, or filling in forms
(STVR:STVR121, ; Fewster, ; 7381848, ). Unlike traditional unit tests, E2E
tests focus on whole business-oriented scenarios, such as logging into the web
application, adding items to a shopping cart, and checking out. Such test
scenarios go through all tiers and involve all services required to make the
whole application work. Thus, in web testing, it can be difficult to enforce
isolation, as web tests might use the application state which is promptly
available from previous test case executions (i.e., a polluted state
(Gyori:2015:RTD:2771783.2771793, )). This creates potential test dependencies
due to read-after-write operations performed on persistent data such as
database records or Document Object Model (DOM) fragments that are written by
a test $t_{i}$ and later accessed by a successive test $t_{j}$ (where $j>i$).

Automated detection of all test dependencies in any given test suite is NP-
complete (Zhang:2014:ERT:2610384.2610404, ). As such, researchers have
proposed techniques and heuristics that help developers detect an
approximation of such dependencies in a timely manner
(Gyori:2015:RTD:2771783.2771793, ; Zhang:2014:ERT:2610384.2610404, ; pradet, ;
Bell:2015:EDD:2786805.2786823, ; Kappler:2016:FBT:2950290.2983974, ). In this
work, we focus on automatically detecting test dependencies in E2E web tests.
Existing tools such as DTDetector (Zhang:2014:ERT:2610384.2610404, ),
ElectricTest (Bell:2015:EDD:2786805.2786823, ) or PRADET (pradet, ) are not
applicable because they are based on the extraction of read/write operations
affecting shared data (e.g., static fields) of Java objects. Instead, web
applications are prone to dependencies due to the persistent data managed on
the server-side and the implicit shared data structure on the client-side
represented by the DOM. Such dependencies are spread across multiple
tiers/services of the web application architecture and are highly dynamic in
nature. Hence, existing techniques based on static code analysis are not
directly applicable. The web test dependency problem demands for novel
approaches that leverage the information available in the web test code and on
the client side.

In this paper, we propose a novel test dependency detection technique for E2E
web test cases based on _string analysis_ and _natural language processing_
(NLP). Our approach is implemented in a tool called TEDD (Test Dependency
Detector), which supports efficient and conservative detection and validation
of test dependencies in an E2E test suite using only client-side information,
which makes it independent of the server-side technology.

TEDD extracts an initial approximated dependency graph (TDG). Then, it filters
potentially false dependencies in order to speed up the validation process.
Afterwards, it validates each dependency by dynamic analysis and it recovers
any manifest dependency that is potentially missing in the initial and/or
filtered graph.

The output of TEDD is a validated TDG, which ensures that any test execution
schedule that respects its dependencies will not result in any test failure.
In our empirical study on six web test suites, TEDD produced the final TDGs
72% faster than a baseline approach that validates all possible dependencies
(57%, on average). Also, the test suites parallelized by TEDD according to the
dependencies in the final TDGs achieved a speedup up to 7$\times$ (2$\times$
on average).

Our paper makes the following contributions:

  * •

The first test dependency detection approach for web tests. Our approach
introduces string analysis (SA) to extract an approximated set of test
dependencies, and NLP/SA to filter potential false dependencies.

  * •

An algorithm to automatically retrieve all missing dependencies from any given
web test dependency graph.

  * •

An implementation of our algorithm in a tool named TEDD.

  * •

An empirical evaluation of TEDD on a benchmark of six open-source web test
suites, comprising 196 test cases.

##  2\. Background and Motivation

Ideally, running the tests in a test suite in any order should produce the
same outcome (pradet, ). This means tests should deterministically pass or
fail independently from the order in which they are executed. A test
dynamically alters the state of the program under test in order to assert its
expected behaviour. In practice, some tests fail to undo their effects on the
program’s state after their execution, which can pollute any shared state
(Gyori:2015:RTD:2771783.2771793, ) in tests executed subsequently.

In the web domain, testers perform end-to-end (E2E) testing of their
applications (Berner, ; Fewster, ) by creating test cases using test
automation tools such as Selenium WebDriver (selenium, ). Such tests consist
of (1) actions that simulate an end-user’s interactions with the application,
and (2) assertions on information retrieved from the web page to verify the
expected behaviour. Unlike unit testing, in which tests target specific class
methods, web tests simulate E2E user scenarios, and therefore the program
state that persists across test case executions might be left polluted,
causing test failures if tests are reordered.

Motivating Example. Table 1 lists six E2E Selenium WebDriver tests for the
Claroline web application (WCRE, ), one of the subject test suites used in our
evaluation.

Table 1. Test cases for Claroline, numbered according to their test execution order (WCRE, ). Test | Name | Description
---|---|---
$t_{1}$ | addUserTest | The admin creates a new user account.
$t_{2}$ | searchUserTest | The admin searches for the newly created user.
$t_{3}$ | loginUserTest | The newly created user logs in to the application.
$t_{4}$ | addCourseTest | The admin creates a new course.
$t_{5}$ | searchCourseTest | The admin searches for the newly created course.
$t_{6}$ | enrolUserTest | The user enrols herself in the course.

Figure 1 shows dependencies between tests $t_{1}$ and $t_{2}$. The test case
addUserTest logs in to the application with the administrator credentials
(lines 3–5), it navigates to the create user page (lines 6–7), it creates a
new user account having username user001 by filling in and submitting the
appropriate form (lines 8–12), and it finally verifies that a message is
correctly displayed (line 13).

The execution of addUserTest pollutes the state of the web application, which
is used by the subsequent test searchUserTest to search for the same user
user001 created by addUserTest (line 22). Thus, the shared input data user001
might reveal a potential dependency between the tests (see highlighted inputs
in Figure 1).

To make these two tests independent and avoid polluted program states, a
tester, for instance, should (1) delete the user user001 created in
addUserTest, to clean the polluted program state, and (2) re-create the same
user (or a different one) in searchUserTest.

In practice, however, testers re-use states created by preceding tests to
avoid test redundancy, higher test maintenance cost and increased test
execution time (2016-Leotta-Advances, ). In doing so, they also enforce pre-
defined test execution orders, which in turn inhibit utilizing test
optimization techniques such as test prioritization
(Rothermel:2001:PTC:505464.505468, ).

⬇

1@Test

2public void addUserTest() {

3 driver.findElement(By.id("login")).sendKeys("admin");

4 driver.findElement(By.id("password")).sendKeys("admin");

5 driver.findElement(By.xpath("//button")).click();

6 driver.findElement(By.linkText("Platform administration")).click();

7 driver.findElement(By.linkText("Create user")).click();

8 driver.findElement(By.id("lastname")).sendKeys("Name001" );

9 driver.findElement(By.id("firstname")).sendKeys("Firstname001" );

10 driver.findElement(By.id("username")).sendKeys("user001" );

11 driver.findElement(By.id("password")).sendKeys("password001");

12 driver.findElement(By.id("password_conf")).sendKeys("password001");

13 assertEquals("The new user has been created",
driver.findElement(By.xpath("//*[@id='claroBody']")).getText());

14 driver.findElement(By.id("logout")).click();

15}

16@Test

17public void searchUserTest() {

18 driver.findElement(By.id("login")).sendKeys("admin");

19 driver.findElement(By.id("password")).sendKeys("admin");

20 driver.findElement(By.xpath("//button")).click();

21 driver.findElement(By.linkText("Platform administration")).click();

22 driver.findElement(By.id("search_user")).sendKeys("user001" );

23 driver.findElement(By.cssSelector("input[type='submit']")).click();

24 assertEquals("Name001" ,driver.findElement(By.id("L0")).getText());

25 assertEquals("Firstname001"
,driver.findElement(By.xpath("//td[3]")).getText());

26 driver.findElement(By.id("logout")).click();

27}

Figure 1. Two dependent E2E web tests for the Claroline web application.
Potential dependencies due to shared input data are highlighted. Figure 2. The
test dependency graph for the test suite of Table 1. Solid edges represent
manifest dependencies, namely, dependencies that result in a different test
result if they are not respected. Figure 3. Our overall approach for web test
dependency detection, validation and recovery.

Test Dependency Graph. The dependencies occurring between tests can be
represented in a test dependency graph ($TDG$) (pradet, ). $TDG$ is a directed
acyclic graph in which nodes represent test cases and edges represent
dependencies. $TDG$ contains an edge from a test $t_{2}$ to a test $t_{1}$ if
$t_{2}$ depends on $t_{1}$ for its execution (notationally, $t_{2}\rightarrow
t_{1}$).

Figure 2 illustrates the actual test dependency graph ($TDG$) for the test
suite of Table 1. For example, $TDG$ contains an edge from searchCourseTest to
addCourseTest because searchCourseTest requires the execution of addCourseTest
to produce the expected result (in other words, addCourseTest must be executed
before searchCourseTest in order for it to succeed). Multiple test
dependencies can also occur. For instance, enrolUserTest depends on both
addUserTest and addCourseTest for its correct execution.

In order to be useful, $TDG$ should contain all manifest dependencies, i.e.,
dependencies that do cause tests to fail if violated, while retaining the
minimum number (or none) of false dependencies.

One possible application of a $TDG$ that contains only manifest dependencies
is test suite parallelization. For instance, if we traverse the graph of
Figure 2 and extract the subgraphs reachable from each node with zero in-
degree (in our example, there is only addUserTest), we can identify subsets of
tests that can be be executed in parallel with the others. In our example,
four parallel test suites are possible: { $\langle t_{1},t_{2}\rangle$,
$\langle t_{1},t_{3}\rangle$, $\langle t_{1},t_{4},t_{6}\rangle$, $\langle
t_{4},t_{5}\rangle$ }.

##  3\. Approach

The goal of our approach is to automatically detect the occurrence of
dependencies among web tests. Detecting dependencies in E2E web tests is
particularly challenging due to the stack of programming languages and
technologies involved in the construction of modern web applications, e.g.,
HTML, CSS, JavaScript on the client side; PHP, Java or JavaScript on the
server-side, and back-end layers through Restful APIs or databases.

Our insight is that by analyzing the input data used in test cases
(highlighted in Figure 1), we can obtain clues about potential test
dependencies caused by shared polluted states. For example, the input string
user001 used at line 10 in addUserTest is a write operation of persistent
data. The same input string is used at line 22 in searchUserTest as a read
operation of persistent data. We conjecture that such _read-after-write_
connections on persistent data could indicate potential test dependencies.
Given this insight, our approach focuses on read-after-write relationships on
persistent data, defined as follows.

###### Definition 1 (Persistent Read-After-Write (PRAW) Dependency).

Two test cases $t_{1}$ and $t_{2}$ executed in this order in the original test
suite are subject to a PRAW dependency if $t_{1}$ performs an operation that
writes some information $S_{i}$ into the persistent state of the web
application and $t_{2}$ performs an operation that reads $S_{i}$ from the
persistent state of the web application.

Examples of the write operations in $t_{1}$ include creating, updating or
deleting a record in a database, or creating a DOM element on the webpage.
Examples of read operations in $t_{2}$ are reading the same record from the
database, or accessing the newly created DOM element on the webpage.

Figure 3 illustrates our overall approach, which requires a web test suite as
input, along with a predefined test execution order. Overall, our approach ❶
computes an initial approximated test dependency graph, ❷ filters out
potential false dependencies, ❸ dynamically validates all dependencies in the
graph while recovering any missing dependencies, and, finally, ❹ handles
missing dependencies affecting independent nodes possibly resulting from the
previous validation step.

Next, we describe each step of our approach.

###  3.1. Dependency Graph Extraction

In the first step, from the input test suite, our approach computes an initial
test dependency graph representing an approximated set of candidate
dependencies. This can be conducted in different ways, as described below.

####  3.1.1. Original Order Graph Extraction

A baseline approach consists of connecting all pairwise combinations of tests
according to the original order. This results in a directed graph in which
every pair of distinct nodes is connected by a unique pair of edges, so as to
establish a dependency relation between each test and all the others that are
executed before it. If $n$ is the number of test cases in the test suite, the
graph contains $\frac{n(n-1)}{2}$ edges (e.g., dependencies).

Since the time to validate a dependency graph increases with the number of
dependencies in the graph, heuristics can be used to reduce the size of the
graph by removing edges that are less likely to be manifest dependencies. To
that end, we propose an approach that leverages a fast static string analysis
of the input data present in the tests, to construct a smaller initial test
dependency graph.

####  3.1.2. Sub-Use String Analysis Graph Extraction

Algorithm 1 describes our dependency graph extraction based on sub-use-chain
relations. A sub-use relation consists of a submission (sub) of input data $i$
and all the following uses that submitted value $i$.

1

2

Input : $T_{o}$: test suite in its original order $o$, $\mathcal{I}$: set of
input-submitting actions

Output : $TDG$: test dependency graph with candidate dependencies to be
validated

3

4$TDG$ $\leftarrow$ $\emptyset$

$T_{a}$ $\leftarrow$ $T_{o}$

$\triangleright$ tests to analyze

5

6foreach  _$t$ in $T_{o}$_ do

$\mathcal{S}\leftarrow$ getInputValues($t$, $\mathcal{I}$)

$\triangleright$ $\mathcal{S}$ is the set of input values submitted by $t$

7 $T_{a}$ $\leftarrow$ $T_{a}-\\{t\\}$

8 foreach  _$t_{f}$ in $T_{a}$_ do

$\mathcal{U}$ $\leftarrow$ findUsedValues($t_{f}$) $\cap\ \mathcal{W}$

$\triangleright$ $\mathcal{U}$ is the set of input values used by $t_{f}$

9 if  _ $\mathcal{U}$ $\neq\emptyset$_ then

depToAdd $\leftarrow$ $(t_{f}\xrightarrow[]{\mathcal{U}}t)$

$\triangleright$ candidate manifest dependency

10 $TDG\leftarrow TDG\cup\\{$ depToAdd $\\}$

11 end if

12

13 end foreach

14

15 end foreach

Algorithm 1 Sub-use string analysis graph extraction

Starting from the first test case according to the original test suite order,
Algorithm 1 first retrieves the set $\mathcal{S}$ of input values submitted by
the test, like values inserted into input fields by input-submitting actions
such as the sendKeys methods (line 4).

Second, the algorithm considers each test case $t_{f}$ following $t$ and
searches for any input value in the set $\mathcal{S}$, which is used in any
statement of the current test case $t_{f}$ (line 7), and adds them to the set
of used values $\mathcal{U}$. If at least one string value is found (i.e., a
sub-use chain), a candidate PRAW dependency between $t$ and $t_{f}$ is created
by adding the edge $t_{f}\rightarrow t$, labelled with each retrieved string
value (line 9), to the test dependency graph (line 10).

The internal loop of Algorithm 1 (lines 6–12) searches for the input values
indistinctly in any test action because in web tests there is no clear
distinction between read and write statements. For instance, in Figure 1, the
sendKeys action at line 10 is used to write persistent information into the
application (e.g., in a database). However, the same sendKeys action, at line
22, identifies an action with a read connotation, because the string value
user001 is used to search for a specific persistent information in the web
application.

Let us consider the source code of the two test cases in Figure 1, namely
addUserTest and searchUserTest. From the first test addUserTest, the algorithm
extracts the set $\mathcal{S}=\\{$admin, Name001, Firstname001, user001,
password001$\\}$ because sendKeys is the only input-submitting action. Then,
the string values in $\mathcal{S}$ are looked up in the subsequent test
searchUserTest, producing the set of used values $\mathcal{U}=\\{$admin,
Name001, Firstname001, user001$\\}$. Being $\mathcal{U}$ not empty, the
algorithm creates a candidate test dependency between searchUserTest and
addUserTest.

###  3.2. Filtering

The second step of our approach applies a filtering process to remove
potential false PRAW dependencies. The filtering is performed to speed up the
subsequent validation step, which requires in-browser test execution, and
therefore can be computationally expensive for graphs with numerous candidate
test dependencies. Finding an effective filtering technique is, however,
challenging. A loose filter might remove a few false dependencies, whereas a
strict filter might mistakenly remove manifest dependencies, which would need
to be recovered at a later stage.

In this work, we propose two novel test dependency filtering techniques based
on (1) dependency-free values, and (2) Natural Language Processing (NLP).

####  3.2.1. Dependency-free String Value Filtering

We analyze the frequency of string input values used in the test suite to
filter potential false PRAW dependencies.

Let us consider the test dependency graph depicted in Figure 4, obtained by
applying our sub-use string analysis graph extraction (Section 3.1.2) to the
motivating example test suite (Section 2).

Figure 4. Dependency-free string-based PRAW filtering. Solid black edges
represent manifest dependencies whereas dashed red edges represent false
dependencies.

The set of dependencies { $t_{5}\rightarrow t_{2}$, $t_{5}\rightarrow t_{1}$,
$t_{4}\rightarrow t_{1}$ } represents instances of false candidate PRAW
dependencies. The edges between these test cases are only due to the same
login input data used by the tests—i.e., admin—a default user created during
the installation, for which no test case must be executed to create it.

Existing techniques (Zhang:2014:ERT:2610384.2610404, ; pradet, ) refer to such
cases as dependency-free values, i.e., if the test dependency graph includes
dependencies that are shared across multiple (or all) test cases, these
likely-false dependencies could be filtered out.

However, in principle, these assumptions might not hold in all cases, as
occurrence frequency alone is not conclusive for safe filtering. Our
dependency-free string value filtering computes a ranked list of frequently
occurring strings and asks the developer to either confirm or discard them (if
a string value occurs in all test cases, the corresponding dependency is
automatically filtered).

In our example of Figure 4, our approach computes the frequencies of all
strings, presents it to the the tester, who, for instance, may decide to
filter the dependencies due to the admin string, hence removing
$t_{5}\rightarrow t_{2}$, $t_{5}\rightarrow t_{1}$, $t_{4}\rightarrow t_{2}$.

####  3.2.2. NLP-based Filtering

Developers often use descriptive patterns for test case names, which summarize
the operations performed by each test. Giving a descriptive name to a test
case has several advantages such as enhanced readability (i.e., it becomes
easier to understand what behaviour is being tested) and debugging (i.e., when
a test case fails, it is easier to identify the broken functionality). For
instance, Google recommends test naming conventions (google-junit-test-names,
; google-scenario-test-names, ) in which unit tests need to be named with the
method being tested (a verb or a verb phrase, e.g., pop) and the application
state in which the specific method is tested (e.g., EmptyStack). For
behaviour-based tests such as E2E tests (google-scenario-test-names, ), the
guidelines propose a naming convention that includes the test scenario (e.g.,
invalidLogin) and the expected outcome (e.g., lockOutUser).

Therefore, our second filtering mechanism consists of using Natural Language
Processing (NLP) to analyze test case names and classify them into two
classes, namely, _read_ or _write_. Then, based on such classification, non-
PRAW dependencies, such as a “read” test being dependent on another “read”
test, are discarded from the test dependency graph.

Our approach uses a Part-Of-Speech tagger (POS) to classify each token (i.e.,
word) in a tokenized test name as noun, verb, adjective, or adverb. In
particular, our approach uses the verb from the test case name as the part of
speech that conveys the nature of the test operation, and uses it to classify
each test into read or write classes. Our approach relies on two groups of
standardized R/W verbs, namely CRUD operations—Create, Read, Update and
Delete) (crud, )—in which the Read operation is pre-classified as read whereas
the other three are pre-classified as write.

Our approach uses POS to extract the first verb from each test name and then
computes the semantic similarity (wordnet-similarity, ) (specifically, the WUP
metrics (wup, )) between the extracted verb and each verb in the pre-
classified read/write groups. The similarity score quantifies how much two
concepts are alike, based on information contained in the is–a hierarchy of
WordNet (wordnet, ). After computing all similarity scores, our approach
classifies the extracted verb to the group having the maximum similarity
score. In case of ties (e.g., the verb has the same similarity score for both
the read and write classes), or in case no verbs are found, our approach does
not perform any assignment and the dependency is not filtered. Our
classification of read/write verbs achieved a precision of 80% and a recall of
94% on our experimental subjects.

In this work, we propose and evaluate three NLP configurations.

Verb only (NLP Verb). Our first NLP filtering configuration considers only the
verb of the test case name. Given a dependency $t_{y}\rightarrow t_{x}$, our
approach extracts the verb from both $t_{y}$ and $t_{x}$, and classifies them
either as read or write. Then, it filters (1) the read-after-read (RaR)
dependencies, in which both $t_{y}$ and $t_{x}$ have verbs classified as read,
and (2) the write-after-read (WaR) dependencies, where $t_{y}$ has a write-
classified verb whereas $t_{x}$ has a read-classified verb. All other types of
dependencies, such as read-after-write (RaW) and WaW (write operations in web
applications often also involve reading existing data), are retained.

The dependency searchCourseTest $\rightarrow$ searchUserTest (Figure 4) is
filtered because it is classified as RaR, with search being the read-
classified verb. Conversely, the edge searchUserTest $\rightarrow$ addUserTest
is retained since it is classified as RaW, being search and add the read/write
verbs, respectively. The word Test is considered a stop word and removed
before the NLP analysis starts.

Verb and direct object (NLP Dobj). The second configuration considers the
direct object the verb refers to. Given a set of test cases, our approach uses
a dependency parser to analyze the grammatical structure of a sentence,
extract the direct object from each test name, and construct a set of
“dobject” dependencies.

RaR and WaR dependencies are filtered as described in the previous NLP Verb
case. Differently, RaW and WaW dependencies are filtered only if the direct
objects of two verbs appearing in two tests $t_{y}$ and $t_{x}$ are different.
The intuition is that the two tests may perform actions on different
persistent entities of the web application, if the involved direct objects in
the test names are different. For example, in Figure 4, the RaW dependency
searchCourseTest $\rightarrow$ addUserTest is filtered because the two
involved direct objects, Course and User, are different.

Verb and nouns (NLP NOUN). Our third configuration takes into account all
entities of type noun contained in the test names. When the test name includes
multiple, different entities, analyzing only the direct object may not be
enough to make a safe choice. For instance, in our subject Claroline, the
analysis of the direct object would erroneously filter the manifest dependency
addCourseEventTest $\rightarrow$ addCourseTest, because it is a WaW and the
two direct objects Event and Course are different. However, there is an
implicit relation between the direct object Event and the Course object it
refers to. Thus, the dependency with addCourseTest should be retained.

Again, RaR and WaR dependencies are filtered as described in the NLP Verb
case. Here, RaW and WaW dependencies are filtered only if the two tests
involved in a dependency have no noun in common. As such, the manifest
dependency addCourseEventTest $\rightarrow$ addCourseTest would not be
filtered in this configuration, because of the shared name Course.

###  3.3. Dependency Validation and Recovery

Given a test dependency graph $TDG$, the overall dynamic dependency validation
procedure works according to the iterative process proposed by Gambi et al.
(pradet, ). The approach executes the tests according to the original order to
store the expected outcome. Next, it selects a target dependency according to
a source-first strategy in which tests that are executed later in the original
test suite are selected first (i.e., $t_{3}\rightarrow t_{2}$ would be
selected before $t_{2}\rightarrow t_{1}$).

To validate the target dependency, tests are executed out of order, i.e., a
test schedule in which the target dependency is inverted is computed and
executed. If the result of the test execution differs from the expected
outcome, the target dependency is marked as manifest, because the failure was
due to the inversion. Otherwise, the target dependency is removed from $TDG$.
The process iterates until all dependencies are either removed or marked as
manifest.

The dynamic validation procedure described above works correctly under the
assumption that the initial TDG contains all manifest dependencies (as the
original order graph Section 3.1.1). In our approach, the filtering techniques
applied in the previous step may be not conservative. Therefore, differently
from existing techniques (pradet, ), our approach features a dynamic
dependency recovery mechanism that retrieves all _missing_ dependencies. To
the best of our knowledge, this is the first dependency validation algorithm
that also includes dynamic dependency recovery.

1

2

Input : $T_{o}$: test suite in its original order $o$

$TDG$: test dependency graph

targetDep: dependency selected for validation

expResults: results of executing $T_{o}$

execResults: results of a test schedule in which targetDep is inverted

Output : $TDG$: updated test dependency graph with missing dependencies
recovered

Require : expResults $\neq$ execResults, i.e., targetDep is manifest

3

4schedule $\leftarrow$ computeTestScheduleWithNoInversion($TDG$, targetDep)

5 execResults $\leftarrow$ executeTestSchedule(schedule)

6 failedTest $\leftarrow$ getFirstFailedTest(expResults, execResults)

7 if  _failedTest $\neq$ null_ then

8

9 /* Failure due to a missing dependency; get all tests before failedTest. */

10 depCandidates $\leftarrow$ getDepCandidates$(T_{o}$, schedule$)$

11 foreach  _depCandidate $\in$ depCandidates_ do

12 depToAdd $\leftarrow$ $\langle$ failedTest $\rightarrow$ depCandidate
$\rangle$

13 $TDG\leftarrow TDG\cup\\{\textit{depToAdd}\\}$

14 end foreach

15

16 end if

Algorithm 2 Recovery algorithm

Recovering Missing Dependencies. Algorithm 2 takes a partially-validated
$TDG$. For each failing test schedule in which a target dependency is
inverted, it checks whether the failure is due to a missing dependency in the
dependency graph.

More specifically, Algorithm 2 takes the target dependency and computes a
schedule in which the target dependency is not inverted (line 1). If the
execution of such schedule complies with the expected outcome, our approach
considers the test failure due to the dependency inversion and marks the
dependency as a manifest. On the contrary, if one or more tests fail also in
the schedule without inversion (line 4), our approach assumes that one or more
dependencies are missing and need to be recovered.

To do so, the algorithm takes the first failing test and retrieves the
preceding test cases that were not executed in the schedule (line 6). Those
tests are all candidate manifest dependencies for the failed test. The
algorithm connects the failed test case with each such preceding test and adds
those dependencies to the graph (lines 8–9). The graph obtained this way
contains all newly added candidate manifest dependencies that still need to be
validated.

Figure 5. Recovery of missing dependencies. (A) $t_{4}\rightarrow t_{3}$ is
selected, $t_{4}$ fails because $t_{4}\rightarrow t_{2}$ is missing. (B)
recovery procedure adds candidate dependencies. (C) dependency validation. (D)
final $TDG$.

Let us take as example Figure 5.A, in which $t_{4}$ has a missing manifest
dependency on $t_{2}$, and $t_{3}$ does not modify the application state.
According to the source-first strategy, the validation selects the dependency
$t_{4}\rightarrow t_{3}$ . The schedule computed for such dependencies is
$\langle t_{4}\rangle$, in which $t_{4}$ fails because $t_{2}$ is not
executed. Then, our algorithm starts retrieving the missing dependency by
computing a schedule in which $t_{4}\rightarrow t_{3}$ is not inverted,
$\langle t_{3},t_{4}\rangle$, in which $t_{4}$ fails again for the same
reason. The recovery procedure concludes that there is at least one missing
dependency, and connects $t_{4}$ with both $t_{1}$ and $t_{2}$ (Figure 5.B),
i.e., the only candidate manifest dependencies.

In Figure 5.C the dependency $t_{4}\rightarrow t_{3}$ is selected again. This
time, the computed schedule is $\langle t_{1},t_{2},t_{4}\rangle$, in which
none of the tests fail. Therefore, the dependency is marked as false and
removed. The next selected dependency is $t_{4}\rightarrow t_{2}$, for which
the schedule $\langle t_{1},t_{4}\rangle$ is computed. The test $t_{4}$ fails
because $t_{2}$ is not executed. To check if the failure is due to a missing
dependency, our algorithm computes the test schedule $\langle
t_{1},t_{2},t_{4}\rangle$, in which none of the tests fail. Our algorithm
concludes that $t_{4}\rightarrow t_{2}$ is a manifest dependency and recovers
it. The validation iterates over the other dependencies in the same way and
outputs the final $TDG$ (Figure 5.D), where the initially missing dependency
has been recovered.

###  3.4. Disconnected Dependency Recovery

The previous validation step ❸ can produce disconnected components in the
$TDG$. Missing dependencies involving tests in disconnected components require
a separate treatment. Two cases can occur (1) tests with no outgoing edges
(zero out-degree),111First test $t_{1}$ excluded and (2) isolated tests, i.e.,
tests having neither incoming nor outgoing edges (zero in- and out-degree).

The former case occurs when a false dependency, removed during the validation,
shadows a missing dependency. In such cases, disconnected components of $TDG$,
including potentially missing dependencies, are created as a result of the
validation.

Figure 6.A illustrates an example: the manifest dependency $t_{4}\rightarrow
t_{1}$ is missing in the initial dependency graph. Let us suppose that $t_{3}$
does not change the state of the application when executed, and therefore, its
execution does not influence the execution of any other successive test in the
original order. The algorithm selects first the dependency $t_{4}\rightarrow
t_{3}$, it produces the schedule $\langle t_{4}\rangle$, in which the test
fails since $t_{1}$ is not executed. Our approach checks if the failure is due
to a missing dependency. When the dependency is not inverted, the computed
schedule is $\langle t_{1}$, $t_{3}$, $t_{4}\rangle$, in which none of the
tests fail. Hence, our algorithm concludes that $t_{4}\rightarrow t_{3}$ is a
manifest dependency and no dependency recovery takes place. In the next step,
the algorithm validates the dependency $t_{3}\rightarrow t_{1}$, which is
removed because $t_{3}$ can execute successfully without $t_{1}$. The
dependency graph produced by dependency validation algorithm is illustrated in
Figure 6.B. In the isolated subgraph $t_{4}\rightarrow t_{3}$ the schedule
$\langle t_{3}$,$t_{4}\rangle$ results in a failure of $t_{4}$. Indeed, the
dependency $t_{4}\rightarrow t_{1}$ was not captured by the recovery algorithm
because the false dependency $t_{3}\rightarrow t_{1}$ shadowed the absence of
the manifest dependency $t_{4}\rightarrow t_{1}$.

Figure 6.A also illustrates how our approach handles isolated tests. In this
example, $t_{2}$ is an isolated node. Let us suppose that $t_{2}$ has a
manifest dependency on $t_{1}$ ($t_{2}\rightarrow t_{1}$), which is missing in
the initial $TDG$ because it is either not captured, or because it is wrongly
filtered out in the second step of our approach. Therefore, the validation
step would produce the $TDG$ shown in Figure 6.B, in which there is no chance
to check whether $t_{2}$ executes successfully in isolation. In fact, $t_{2}$
is not part of any test schedule that can be generated from $TDG$, regardless
of any possible dependency inversion. For this reason, a further recovery step
is required once the validation is completed.

Figure 6. Disconnected dependency recovery. (A) dependencies are validated;
$t_{3}\rightarrow t_{1}$ shadows the missing dependency $t_{4}\rightarrow
t_{1}$. (B) $t_{4}$ and $t_{2}$ fail because of missing dependencies. (C)
recovery procedure adds candidate dependencies. (D) dependencies are
validated. (E) final $TDG$.

1

2

Input : $T_{o}$: test suite in its original order $o$

$TDG$: test dependency graph

Output : $TDG$: updated test dependency graph with missing dependencies
recovered

3

4expResults $\leftarrow$ executeTestSuite($T_{o}$)

5 /* Get isolated nodes and nodes with no outgoing edges. */

6 disconnectedTests $\leftarrow$ getDisconnectedTests($TDG$)

7 foreach  _disconnectedTest in disconnectedTests_ do

8 execResults $\leftarrow$ executeTestInIsolation(disconnectedTest)

9 failedTest $\leftarrow$ getFailedTest(expResults, execResults)

10 if  _failedTest $\neq$ null_ then

11 $TDG$ $\leftarrow$ connectWithPrecedingTests(failedTest, $TDG$, $T_{o}$)

12 else if  _isNotIsolated(disconnectedTest)_ then

13 /* Out-degree = 0; in-degree $>$ 0\. */

14 schedules $\leftarrow$ computeSchedules(disconnectedTest, $TDG$)

15 foreach  _schedule $\in$ schedules_ do

16 execResults $\leftarrow$ exec(schedule)

17 failedTest $\leftarrow$ getFailedTest(expResults, execResults)

18 if  _failedTest $\neq$ null_ then

19 $TDG$ $\leftarrow$ connectWithPrecedingTests(failedTest,$TDG$, $T_{o}$)

20 end if

21

22 end foreach

23

24 end if

25

26 end foreach

27

Algorithm 3 Disconnected dependency recovery algorithm

Algorithm 3 handles the recovery of missing dependencies within disconnected
components. The algorithm retrieves all isolated nodes and zero out-degree
nodes (line 3) and executes each of them in isolation (line 5). For each
failing test, the algorithm connects it with all preceding tests according to
the initial test suite order (line 8). Otherwise, if a test is not isolated
and executes successfully (line 9), the algorithm takes all schedules that
contain that test and execute them (lines $12$–$18$). If a test in those
schedules fails, the algorithm connects it with all the preceding ones (line
16).

Finally, for each dependency found and added to $TDG$ during the disconnected
dependency recovery step, the dependency validation procedure must be re-
executed.

Given the graph in Figure 6.B, Algorithm 3 executes $t_{2}$ in isolation,
which fails, thus the dependency $t_{2}\rightarrow t_{1}$ is added. Moreover,
in Figure 6.B, there is only one schedule that involves $t_{3}$, namely
$\langle t_{3}$,$t_{4}\rangle$. In this schedule $t_{4}$ fails, hence our
approach adds the dependencies $t_{4}\rightarrow t_{2}$ and $t_{4}\rightarrow
t_{1}$ (Figure 6.C). Next, the added dependencies are validated (Figure 6.D),
and the final graph is produced, where all initially missing manifest
dependencies have been successfully recovered (Figure 6.E).

To conclude, our validation and recovery algorithms makes sure that (1) newly
added dependencies are themselves validated, (2) false dependencies are
removed in the final $TDG$. Indeed, a node in the final $TDG$ can be either
(i) connected (i.e., in-degree $>0$ and out-degree $>0$), (ii) without
outgoing edges (i.e., in-degree $>0$ and out-degree $=0$) or (iii) isolated
(i.e., in-degree $=$ out-degree $=0$).

###  3.5. Implementation

We implemented our approach in a tool called TEDD (Test Dependency Detector).
The tool is written in Java, and supports Selenium WebDriver web test suites
written in Java. However, our overall approach is general because it can be
applied to test suites developed using other programming languages or web
testing frameworks. TEDD expects as input the path to a test suite and
performs the string analysis by parsing the source code of the tests by using
Spoon (version $6.0.0$) (spoon, ). Our NLP module adopts algorithms available
in the open-source library CoreNLP (version $3.9.2$) (core-nlp, ). The output
of TEDD is a list of manifest dependencies extracted from the final validated
TDG.

##  4\. Empirical Evaluation

We consider the following research questions:

RQ1 (effectiveness): How effective is TEDD at filtering false dependencies
without missing dependencies to be recovered?

RQ2 (performance): What is the overhead of running TEDD? What is the runtime
saving achieved by TEDD with respect to validating complete test dependency
graphs?

RQ3 (parallel test execution): What is the execution time speed-up of the test
suites parallelized from the test dependency graphs computed by TEDD?

###  4.1. Subject Systems

We selected six open-source web applications used in previous web testing
research, for which Selenium test suites are available (WCRE, ). Table 2 lists
our subject systems, including their names, version, size in terms of lines of
code, number of test cases, and the total number of lines of test code. We use
cloc (cloc, ) to count lines of code. During our experiments we used the
original execution order of each test suite, as specified by the developers.

Table 2. Subject systems and their test suites | Web App | Test Suites
---|---|---
| Version | LOC | # | LOC (Avg/Tot)
Claroline | 1.11.10 | 352,537 | 40 | 46/1,822
AddressBook | 8.0.0 | 16,298 | 27 | 49/1,325
PPMA | 0.6.0 | 575,976 | 23 | 54/1,232
Collabtive | 3.1 | 264,642 | 40 | 48/1,935
MRBS | 1.4.9 | 34,486 | 22 | 51/1,114
MantisBT | 1.1.8 | 141,607 | 41 | 43/1,748
Total |  | 866,995 | 196 | 47/9,176

[b]

Table 3. Effectiveness (RQ1), Performance (RQ2) and Parallelization (RQ3)
average results across all subject test suites.

| Effectiveness | Performance | Parallelization
---|---|---|---
|  |  |  |  | Manifest Deps. |  |  | Validation |  |  |  | Speed-up (%)
|  Extracted |  Filtered |  To Validate |  False |  Validated |  Recovered |  Recovered (Disc.) |  Total PRAW |  Extraction |  Filtering |  Val. and Recovery |  Recovery (Disc.) |  Total |  Saving (%) |  Schedules (#) |  Worst-case |  Average
Baseline (Original Order) | 536 | - | 536 | 504 | 32 | 0 | 0 | 32 | 0.00$\dagger$ | - | 424.7$\ast$ | - | 424.70 | - | 30 | 2.2$\times$ | 7.1$\times$
String Analysis | 494 | 393 | 101 | 69 | 21 | 10 | 1 | 32 | 0.10 | 0.00 | 162.02 | 5.21 | 167.33 | 61% | 30 | 2.4$\times$ | 7.1$\times$
NLP-Verb (Original Order) | 535 | 119 | 416 | 384 | 32 | 0 | 0 | 32 | 0.00$\dagger$ | 0.04 | 307.20 | 1.27 | 308.51 | 27% | 30 | 2.2$\times$ | 7.1$\times$
NLP-Verb (String Analysis) | 494 | 113 | 381 | 348 | 32 | 1 | 0 | 33 | 0.09 | 0.04 | 281.10 | 1.28 | 282.50 | 33% | 30 | 2.2$\times$ | 7.1$\times$
NLP-Dobj (Original Order) | 536 | 362 | 174 | 140 | 27 | 6 | 1 | 34 | 0.00$\dagger$ | 0.24 | 134.90 | 3.46 | 138.60 | 67% | 29 | 2.1$\times$ | 6.7$\times$
NLP-Dobj (String Analysis) | 494 | 343 | 151 | 117 | 27 | 5 | 2 | 34 | 0.09 | 0.23 | 129.20 | 9.10 | 138.62 | 67% | 29 | 2.1$\times$ | 6.7$\times$
NLP-Noun (Original Order) | 536 | 364 | 172 | 140 | 28 | 3 | 1 | 32 | 0.00$\dagger$ | 0.05 | 123.30 | 2.52 | 125.87 | 70% | 29 | 2.1$\times$ | 6.7$\times$
NLP-Noun (String Analysis) | 494 | 351 | 143 | 110 | 28 | 4 | 1 | 33 | 0.08 | 0.04 | 116.10 | 4.08 | 120.30 | 72% | 29 | 2.1$\times$ | 6.8$\times$

  * $\ast$

only validation, no within-recovery.

  * $\dagger$

execution time $<$ 0.01 minutes (0.6 seconds).

###  4.2. Procedure and Metrics

####  4.2.1. Procedure

We manually fixed any flakiness of the test cases of the subject test suites
by adding delays where appropriate and we executed each test suite 30 times to
ensure that identical outcomes are obtained across all executions.

To form a baseline for comparison, we applied dependency validation to the
dependency graph obtained from the original order of each test suite (Section
3.1.1).

For each test suite, we ran different configurations of TEDD, by combining
each admissible combination of graph extraction and filtering technique. The
first evaluated configuration is String Analysis (SA), in which the dependency
graph is obtained through sub-use chain extraction (Section 3.1.2) and
filtered from the dependency-free values (Section 3.2.1). Then, we evaluated
three configurations in which we applied the three proposed NLP filters (NLP-
Verb, NLP-Dobj, NLP-Noun) both to the graph from the original order as well as
to the graph obtained with SA.

Finally, given the validated dependency graph obtained in each configuration,
we generated all possible test schedules that respect the test dependencies,
and we executed them sequentially.

####  4.2.2. Metrics

To assess effectiveness (RQ1), for each configuration we measured the number
of false dependencies removed by TEDD as well as the number of manifest
dependencies that are missing and need to be recovered. The number of false
dependencies is obtained by subtracting the number of manifest dependencies
retrieved at the end of the recovery step from the total number of
dependencies in the initial graph.

We evaluated performance (RQ2) by comparing the execution time (in minutes) of
each configuration of TEDD with respect to the baseline approach.

Concerning parallelization (RQ3), we measured the speed-up factor of the
parallelizable test suites with respect to the original test suite running
time. We considered two speed-up scenarios. (1) average case, in which we
measured the ratio between the original test suite running time and the
average running time of the parallelizable test suites, and (2) worst case, in
which we measured the speed-up ratio between the original test suite running
time and the parallelizable test suite having the highest runtime.

###  4.3. Results

Effectiveness (RQ1). For each configuration of TEDD, Table 3 (Effectiveness)
shows the number of extracted dependencies starting from the initial test
suite (Figure 3, step ❶) and the number of filtered dependencies (Figure 3,
step ❷). It also reports information about the validation and recovery steps,
specifically the number of false dependencies detected, the number of
dependencies recovered and those recovered from the disconnected components.
The final number (Column 8) shows the number of dependencies in the final
$TDG$s, all of which are manifest PRAW dependencies.

Across all apps, the baseline approach validated on average 536 dependencies,
of which 504 were deemed as false, and 32 as manifest. The most conservative
among TEDD’s configurations is NLP-Verb (Original Order), which validated
overall 416 dependencies, of which 384 were false (24% less than the baseline)
and detecting 32 manifest dependencies without filtering/recovering any. The
least conservative configuration of TEDD is NLP-Noun (String Analysis) which
retained only 143 dependencies on average from the initial graphs, of which
110 were detected as false, five dependencies had to be recovered, leading to
the final number of 33 manifest dependencies. Overall, the number of missing
dependencies due to filtering and recovered in steps ❸ ❹ is very low (1% of
the initial number of dependencies).

TEDD does not ensure having minimal test dependency graphs. Therefore, the
number of manifest dependencies retrieved by each configurations is slightly
different, between 32 and 34 (Column Total PRAW). However, these differences
do not affect the executability of the schedules that respect the dependencies
(see results for RQ3).

Figure 7. Pareto front

Figure 7 shows the Pareto front plotting the ratio between false and missing
dependencies, for each configuration. Each point represents the average
$\langle$missing, false$\rangle$ values across all subjects, normalized over
the respective maximum values. This essentially shows the tradeoff between the
false dependencies remaining after the filtering step and the missing
dependencies to be recovered.

From the analysis of the Pareto front, we can see that the non-dominated
configurations are those based on NLP-Verb, NLP-Noun and String Analysis (SA).
The baseline approach (Baseline) has the highest number of false dependencies
(536 on average) and no missing dependencies. On the contrary, SA filters many
dependencies (393 on average) but has the highest number of missing/recovered
dependencies (11 on average). Interestingly, NLP-Verb (Original Order) does
not miss any manifest dependency but has more false dependencies compared to
the other NLP-based configurations. Configurations NLP-Dobj (both SA and
Original Order) and NLP-Noun (both SA and Original Order) are comparable
regarding the number of false dependencies remaining after filtering. However,
NLP-Noun (SA and Original Order) needs to recover substantially less manifest
dependencies. Indeed, NLP-Noun dominates NLP-Dobj, while both NLP-Noun (SA and
Original Order) configurations are on the non-dominated front, being both
optimally placed in the lower-left quadrant of the Pareto plot.

Performance (RQ2). Table 3 (Performance) reports the average runtime, in
minutes, of each step of TEDD across all configurations. The most expensive
step of TEDD is validation, especially for what concerns validating the
connected part of the graph (Column 12), whereas dependency graph extraction
and filtering (Columns 10 and 11) have negligible costs (under one minute on
average in all cases). The cost of disconnected components recovery (Column
13) is generally low, ranging from nearly one minute for NLP-Verb to maximum
nine minutes for NLP-Dobj (3.8 minutes on average).

The slowest configuration of TEDD is NLP-Verb (Original Order) which is 27%
faster on average (almost 2 hours less) than the baseline approach. The
fastest configuration of TEDD is NLP-Noun (SA) which is 72% faster on average
(5 hours less) than the baseline approach. This result confirms the Pareto
front analysis, showing that NPL-Noun (SA) is the most effective configuration
of TEDD.

The table reports also the percentage decrease of each configuration with
respect to the baseline, which took approximately 425 minutes on average
($\approx$7 hours). Overall, all SA- or NLP-based configurations of TEDD are
significantly faster.

Parallel Test Execution (RQ3). Column 15 (schedules) reports the average
number of test schedules obtained from the final $TDG$s. Isolated nodes in the
dependency graphs are counted as (single-test) schedules. Columns 16 and 17
report the relative speed-up of the parallelizable test suites considering the
longest test execution schedule (worst-case) and the average case.

First, in our experiments, no test failures occurred in any of the
parallelizable test suite produced by any configuration of TEDD. Essentially,
this testifies that the dependency validation and recovery algorithm does not
miss any manifest dependency.

Overall, all techniques achieve similar speed-up scores, around 2$\times$ in
the worst case and 7$\times$ on average. This is expected since the final TDGs
are similar across configurations (see total number of manifest dependencies
in Table 3). However, results differ across applications. Table 4 presents the
results for the NLP-Noun (SA) configuration. Column runtime original reports
the execution time of the original test suite in seconds. Collabtive has the
slowest test suite (almost 5 minutes) whereas Addressbook has the fastest (40
seconds). The highest speed-up in the worst-case occurs for Claroline, where
the longest test execution schedule test suite is 2.7$\times$ faster. MantisBT
exhibits the highest speed-up in the average case (12.3$\times$), but the
lowest speed-up in the worst-case (1.4$\times$) due to a single slow-executing
schedule (133 s) with respect to the average runtime (15 s). The lowest speed-
up in the average case occurs for MRBS, but it remains still high
(4.2$\times$).

[b]

Table 4. Parallelization results for NLP-Noun (SA)

|  |  | Worst-case | Average
---|---|---|---|---
|  runtime original |  schedules (#) |  runtime |  speed-up (%) |  runtime |  speed-up (%)
Claroline | 75.1 | 36 | 29.0 | 2.7$\times$ | 9.4 | 8.3$\times$
Addressbook | 40.2 | 24 | 20.1 | 2.0$\times$ | 8.8 | 4.5$\times$
PPMA | 51.7 | 22 | 21.1 | 2.4$\times$ | 8.9 | 5.8$\times$
Collabtive | 297.7 | 37 | 133.1 | 2.3$\times$ | 53.2 | 5.7$\times$
MRBS | 56.9 | 20 | 28.7 | 2.0$\times$ | 13.8 | 4.2$\times$
MantisBT | 184.5 | 37 | 133.8 | 1.4$\times$ | 15.1 | 12.3$\times$
Total | 706.1 | 176 | 365.9 | 2.1$\times$* | 109.2 | 6.9$\times$*

  * *

average

##  5\. Discussion

Automation and Effectiveness. Our results confirm that (1) E2E web tests
entail test dependencies, (2) such dependencies can be identified by
considering PRAW connections between test cases, and (3) TEDD can successfully
detect all PRAW test dependencies necessary for independent test case
execution. All proposed filtering techniques proved both very fast and
effective at reducing the size of the initial graph, without filtering many
manifest dependencies.

Performance and Overhead. All configurations of TEDD achieve substantial
improvements with respect to validating the graph extracted from the original
ordering, whose validation cost is quadratic on the number of test cases. This
means that every time a new test case is added to a test suite containing $n$
test cases, such graph requires that $n$ more dependencies are validated.
Moreover, despite the computational cost of NLP processing, the dependency
graph extraction and filtering steps exhibit negligible costs (less than a
minute over all test suites) compared to the validation time.

Relation to Test Optimization Techniques. TEDD can be used by test engineers
to detect PRAW-like dependencies in E2E web test cases. The validated
dependency graph produced by TEDD can be used as input for devising novel test
optimization and regression testing techniques in the web domain.

For instance, test prioritization and test minimization can be formulated as
constrained optimization problems, in which dependencies by TEDD play the role
of constraints that can be addressed using SMT solvers (z3, ) or search-based
heuristics (sbse, ). Test selection can benefit from the $TDG$s produced by
TEDD to identify which test cases are required by modification-traversing test
cases (Rothermel:1997:SER:248233.248262, ; 536955, ; STVR197, ).

In this work, we studied an application to test parallelization as a proxy to
assess the correctness of the $TDG$s produced by TEDD. Specifically, we
applied dependency-aware graph traversal to retrieve all potential parallel
test suites, and measured the runtime speed-up with respect to the initial
test suites.

Test Smells. Our test dependency graph can also be utilized for other test
analysis activities such as detecting poorly designed tests (i.e., test smells
(van2001refactoring, )), or detecting obsolete tests.

For instance, the test case checkEntryTagsRemoved of PPMA executes after
addEntryTags and removeEntryTags tests. By analyzing the $TDG$ produced by
TEDD for this test suite, we noticed that checkEntryTagsRemoved executes
properly also when no tags have been created yet (i.e., checkEntryTagsRemoved
is isolated in the $TDG$). This means that the test checkEntryTagsRemoved is
obsolete because subsumed by the previous removeEntryTags test. Therefore, it
can be safely removed with no impact on the functional coverage or assertion
coverage of the test suite.

Test Suite Evolution. During software evolution, if new test cases are added
to the test suite, dependencies are added to the previously validated $TDG$
through new dependency extraction and filtering. Validation and recovery must
be carried out on the entire new $TDG$. However, this analysis is expected to
be faster than the first initial one, given that the validated $TDG$ we are
adding dependencies to contains only manifest dependencies.

Limitations. TEDD depends on the information available in the test source
code, used to identify potential test dependencies. As such, the effectiveness
of our NLP-based filtering may be undermined if test case names are not
descriptive, as in the case of many automatically generated test suites (e.g.,
test1, test2). In such cases, testers can rely on the string analysis
configuration of TEDD (SA), which also proved effective in our study. Second,
our tool does not provide information about the root cause of the
dependencies, i.e., what part of the program state is polluted by which test.
Lastly, TEDD does not support the analysis of flaky test suites.

Threats to Validity. Using a limited number of test suites in our evaluation
poses an external validity threat. Although more subject test suites are
needed to fully assess the generalizability of our results, we have chosen six
subject apps used in previous web testing research, pertaining to different
domains, for which test suites were developed by a human web tester.

Threats to internal validity come from confounding factors of our experiments,
such as test flakiness. To cope with possible flakiness of the test cases, we
manually fixed any flaky test by adding delays where appropriate and we ran
each test suite 30 times to ensure having identical results on all executions.

##  6\. Related Work

Test Dependency Detection. Different techniques have been proposed recently to
detect dependencies in unit tests, none of which focuses on web tests. Zhang
et al. (Zhang:2014:ERT:2610384.2610404, ) developed DTDetector, which detects
manifest dependencies in JUnit tests with a dependency-aware $k$-bounded
algorithm. They showed that a small value for $k$ (e.g., $k=1$ and $k=2$)
finds most realistic dependent tests. Poldet (Gyori:2015:RTD:2771783.2771793,
) retrieves tests that pollute the shared state of a Java application (i.e.,
heap or filesystem), and provides ways to inspect such polluted states, e.g.,
access path through the heap that leads to the modified value, or the name of
the file that was modified. The tool VMVM (Bell:virtual, ) uses test
virtualization to isolate unit tests of a JUnit suite, by resetting the static
state of the application to its default before each test execution. Our tool
TEDD, differently from the previous works, targets the web domain by focusing
on dependencies due to read-after-write operations performed on persistent
data. ElectricTest (Bell:2015:EDD:2786805.2786823, ) utilizes dynamic data-
flow analysis to identify all conflicting write and read operations over
static Java objects. On the contrary, in E2E web tests, the semantics of read
and write operations is implicit and mediated by multiple layers of
indirection such as client-side DOM, server-side application state, database
entries, and remote service calls. TEDD leverages heuristics based on sub-use-
chain relations and NLP to discover potential test dependencies without the
need for complex data-flow analysis.

Pradet (pradet, ) detects test dependencies in Java unit tests focusing on
manifest dependencies that can be traced back to data dependencies. TEDD
adopts a similar approach as Pradet to validate the test dependencies, i.e.,
validating a single dependency at a time by inverting the dependency and
linearizing the graph.

The main differences between Pradet and our approach are (1) the capability of
TEDD to handle incomplete dependency graphs; Pradet makes the assumption that
the initial dependency graph contains all manifest dependencies computed
through static analysis of all (read/write) accesses to global Java variables.
Due to this assumption, (2) Pradet only removes false dependencies and it does
not recover any missing dependencies. TEDD, on the other hand, features a
novel recovery algorithm to detect and validate all potentially missing
manifest dependencies, which makes it suitable for web E2E test suites, in
which applying thorough data-flow analysis is neither feasible nor
straightforward, due to the heterogeneity of technologies and languages used
in modern web applications. Lastly, (3) TEDD introduces novel extraction and
filtering heuristics, which extend the applicability of Pradet beyond
read/write operations performed on static fields of Java classes.

##  7\. Conclusions and Future Work

In this paper, we proposed a novel test dependency technique for E2E web test
cases implemented in a tool called TEDD. We used TEDD for detecting test
dependencies in six web test suites. Thanks to an effective combination of
novel string analysis and NLP, TEDD achieves an optimal trade off between
false dependencies to be removed and missing dependencies to be recovered.
Moreover, TEDD detected the final set of manifest test dependencies on average
57% faster than the baseline approach. The resulting test dependency graph
supports parallelization of the tests, with a speed-up factor of up to
7$\times$. In our future work, we plan to apply NLP on the DOM and on page
object-based test suites (mf-po, ), as well as to devise ways to produce a
minimal $TDG$, i.e., a $TDG$ having the minimum number of dependencies. We
also intend to run TEDD on more subject web test suites and to extend it to
support mobile test suites.

## References

  * (1) Bell, J., and Kaiser, G. Unit test virtualization with vmvm.  In Proceedings of the 36th International Conference on Software Engineering (2014), ICSE 2014, ACM, pp. 550–561.
  * (2) Bell, J., Kaiser, G., Melski, E., and Dattatreya, M. Efficient dependency detection for safe java test acceleration.  In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering (New York, NY, USA, 2015), ESEC/FSE 2015, ACM, pp. 770–781.
  * (3) Berner, S., Weber, R., and Keller, R. K. Observations and lessons learned from automated testing.  In Proceedings of 27th International Conference on Software Engineering (2005), ICSE 2005, IEEE Computer Society, pp. 571–579.
  * (4) Binder, R. V. Testing object-oriented software: a survey.  Software Testing, Verification and Reliability 6, 3-4 (1996), 125–252.
  * (5) Counts blank lines, comment lines, and physical lines of source code in many programming languages.  https://github.com/AlDanial/cloc, 2018.
  * (6) Stanford corenlp – natural language software.  https://stanfordnlp.github.io/CoreNLP/, 2019.
  * (7) Create, read, update and delete.  https://en.wikipedia.org/wiki/Create,_read,_update_and_delete, 2019\.
  * (8) De Moura, L., and Bjørner, N. Z3: An efficient smt solver.  In International conference on Tools and Algorithms for the Construction and Analysis of Systems (2008), Springer, pp. 337–340.
  * (9) Fewster, M., and Graham, D. Software Test Automation: Effective Use of Test Execution Tools.  Addison-Wesley Longman Publishing Co., Inc., 1999.
  * (10) Fowler, M. Page Object.  http://martinfowler.com/bliki/PageObject.html, September 2013.
  * (11) Gambi, A., Bell, J., and Zeller, A. Practical test dependency detection.  In Proceedings of the 2018 IEEE Conference on Software Testing, Validation and Verification (April 2018), pp. 1–11.
  * (12) Gao, Z., Fang, C., and Memon, A. M. Pushing the limits on automation in gui regression testing.  In Proceedings of IEEE 26th International Symposium on Software Reliability Engineering (Nov 2015), ISSRE ’15, pp. 565–575.
  * (13) Gligoric, M., Eloussi, L., and Marinov, D. Practical regression test selection with dynamic file dependencies.  In Proceedings of the 2015 International Symposium on Software Testing and Analysis (New York, NY, USA, 2015), ISSTA 2015, ACM, pp. 211–222.
  * (14) Google java style guide. naming convention for junit tests.  https://google.github.io/styleguide/javaguide.html#s5.2.3-method-names, 2019\.
  * (15) Testing on the toilet: Writing descriptive test names.  https://testing.googleblog.com/2014/10/testing-on-toilet-writing-descriptive.html, 2014\.
  * (16) Gyori, A., Shi, A., Hariri, F., and Marinov, D. Reliable testing: Detecting state-polluting tests to prevent test dependency.  In Proceedings of the 2015 International Symposium on Software Testing and Analysis (New York, NY, USA, 2015), ISSTA 2015, ACM, pp. 223–233.
  * (17) Harman, M., and Jones, B. F. Search-based software engineering.  Information and software Technology 43, 14 (2001), 833–839.
  * (18) Kappler, S. Finding and breaking test dependencies to speed up test execution.  In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering (New York, NY, USA, 2016), FSE 2016, ACM, pp. 1136–1138.
  * (19) Lam, W., Zhang, S., and Ernst, M. D. When tests collide: Evaluating and coping with the impact of test dependence.  Tech. Rep. UW-CSE-15-03-01, University of Washington Department of Computer Science and Engineering, Seattle, WA, USA, Mar. 2015.
  * (20) Leotta, M., Clerissi, D., Ricca, F., and Tonella, P. Capture-replay vs. programmable web testing: An empirical assessment during test case evolution.  In Proceedings of 20th Working Conference on Reverse Engineering (2013), WCRE ’13, IEEE Computer Society, pp. 272–281.
  * (21) Leotta, M., Clerissi, D., Ricca, F., and Tonella, P. Approaches and tools for automated end-to-end web testing.  Advances in Computers 101 (2016), 193–237.
  * (22) Miller, G. A. Wordnet: a lexical database for english.  Communications of the ACM 38, 11 (1995), 39–41.
  * (23) Pawlak, R., Monperrus, M., Petitprez, N., Noguera, C., and Seinturier, L. Spoon: A library for implementing analyses and transformations of java source code.  Software: Practice and Experience 46 (2015), 1155–1179.
  * (24) Pedersen, T., Patwardhan, S., and Michelizzi, J. Wordnet:: Similarity: measuring the relatedness of concepts.  In Demonstration papers at HLT-NAACL 2004 (2004), Association for Computational Linguistics, pp. 38–41.
  * (25) Rothermel, G., and Harrold, M. J. Analyzing regression test selection techniques.  IEEE Transactions on Software Engineering 22, 8 (Aug 1996), 529–551.
  * (26) Rothermel, G., and Harrold, M. J. A safe, efficient regression test selection technique.  ACM Trans. Softw. Eng. Methodol. 6, 2 (Apr. 1997), 173–210.
  * (27) Rothermel, G., Harrold, M. J., and Dedhia, J. Regression test selection for C++ software.  Software Testing, Verification and Reliability 10, 2 (2000), 77–109.
  * (28) Rothermel, G., Untch, R. J., and Chu, C. Prioritizing test cases for regression testing.  IEEE Trans. Softw. Eng. 27, 10 (Oct. 2001), 929–948.
  * (29) SeleniumHQ web browser automation.  http://www.seleniumhq.org/, 2018.  Accessed: 2017-08-01.
  * (30) Vahabzadeh, A., Stocco, A., and Mesbah, A. Fine-grained test minimization.  In Proceedings of the 40th International Conference on Software Engineering (2018), ICSE ’18, ACM, pp. 210–221.
  * (31) van Deursen, A., Moonen, L., Bergh, A. v. d., and Kok, G. Refactoring test code.  In Extreme Programming Perspectives. Addison-Wesley, 2002, pp. 141–152.
  * (32) Wu, Z., and Palmer, M. Verbs semantics and lexical selection.  In Proceedings of the 32nd annual meeting on Association for Computational Linguistics (1994), Association for Computational Linguistics, pp. 133–138.
  * (33) Zhang, S., Jalali, D., Wuttke, J., Muslu, K., Lam, W., Ernst, M. D., and Notkin, D. Empirically revisiting the test independence assumption.  In Proceedings of the 2014 International Symposium on Software Testing and Analysis (New York, NY, USA, 2014), ISSTA 2014, ACM, pp. 385–396.