# Uncertainty-Aware Test Prioritization: Approaches and Empirical Evaluation

Man Zhang, Jiahui Wu, Shaukat Ali and Tao Yue M. Zhang is with Kristiania
University College, Oslo, 999026, Norway.
E-mail<EMAIL_ADDRESS>J. Wu, S. Ali, and T. Yue are with Simula
Research Laboratory, Oslo, 999026, Norway. E-mail: {jiahui, shaukat,
<EMAIL_ADDRESS>
###### Abstract

Complex software systems, e.g., Cyber-Physical Systems (CPSs), interact with
the real world; thus, they often behave unexpectedly in uncertain
environments. Testing such systems is challenging due to limited resources,
time, and complex testing infrastructures setup. Furthermore, the inherent
uncertainties in their operating environment complicate their testing.
Devising uncertainty-aware testing solutions supported with test optimization
techniques (e.g., with search) can be considered as a mandate for tackling
this challenge. This paper proposes an uncertainty-aware and time-aware test
case prioritization approach, named UncerPrio, for optimizing a sequence of
tests to execute with a multi-objective search. To guide the prioritization
with uncertainty, we identify four uncertainty measures (denoted as AUM, PUS,
ANU, and PUU), which characterize uncertainty measurement, uncertainty space,
the number of uncertainties, and uncertainty coverage. Based on these measures
and their combinations, we proposed 10 uncertainty-aware and multi-objective
test case prioritization problems, and each problem was additionally defined
with one cost objective to be minimized (denoted as PET for execution cost)
and one effective measure to be maximized (denoted as PTR for model coverage).
Moreover, considering time constraints for test executions (i.e., time-aware),
we defined 10 time budgets for all the 10 problems for identifying the best
strategy in solving uncertainty-aware test prioritization. In our empirical
study, we employed four well-known Multi-Objective Search Algorithms (MuOSAs):
NSGA-II, MOCell, SPEA2, and CellDE with five use cases from two industrial CPS
subject systems, and used Random Algorithm (RS) as the comparison baseline.
Results show that all the MuOSAs significantly outperformed RS. The strategy
of Prob.6 f(PET,PTR,AUM,ANU) (i.e., the problem with uncertainty measures AUM
and ANU combined) achieved the overall best performance in observing
uncertainty when using 100% time budget.

###### Index Terms:

uncertainty-aware testing, test case prioritization, multi-objective search.

##  1 Introduction

Along with the increase in the number of the deployment of large-scale and
complex software systems such as Cyber-Physical Systems (CPSs), growing
attention has been paid to their dependability when facing uncertainty during
their operations, as such systems often interact with the real world, which
itself is inherently uncertain. Testing has been a primary means to ensure the
dependability of such systems before their deployment [1].

In any non-trivial context, test case prioritization is essential because test
execution is both time-wise and monetary expensive, especially when testing
complex software systems such as CPSs, which often requires the use of test
infrastructures (e.g., simulators, emulators, and even hardware equipment) if
available. Various search-based solutions have been proposed for test case
prioritization in the context of CPS testing [2, 3]. In addition, with the
growing realization of handling inherent uncertainty in CPSs to ensure their
dependability, several uncertainty-wise testing approaches have been proposed
in the literature [4, 5, 6, 7, 8]. Along these lines, in our previous work, we
proposed UncerTest for uncertainty-wise test case generation and minimization
for CPSs. However, we realize that such test case generation methods (e.g.,
[9]) generate many test cases when considering uncertainty, and test cases
must be executed multiple times since a known uncertainty might not always
occur, and an unknown uncertainty might be observed. For instance, our
previous study [9] showed that executing more than 1000 test cases could take
more than one day. Executing them multiple times due to uncertainty easily
becomes infeasible in practice; therefore, in practice, test engineers need a
solution to prioritize such test executions to execute effective (e.g.,
uncertainty-aware in our context) tests earlier to observe more uncertainties
earlier within a limited time budget.

In this paper, we define 10 uncertainty-aware and time-aware test case
prioritization problems by considering uncertainty, time budget, execution
time, and behavior coverage, which are formulated as 10 search problems.
Specifically, the 10 problems are defined based on the following four
uncertainty, one cost, and one effectiveness measure:  (1) uncertainty
measures: AUM: the average uncertainty measure (adopted from Uncertainty
Theory [10]) of the prioritized test cases (to maximize); PUS: the average
percentage of uncertainty space (adopted from Uncertainty Theory [10]) covered
(to maximize); ANU: the average number of modeled uncertainties covered (to
maximize); and PUU: the average number of unique uncertainties covered (to
maximize);  (2) cost measure: PET: the total execution time of prioritized
test cases (to minimize); and  (3) effectiveness measure: PTR: the (state
machine) transition coverage (to maximize).  Each search problem comprises the
cost, effectiveness, and one or two uncertainty measures, which lead to 10
fitness functions to guide search algorithms toward finding optimal solutions.
In addition, for each problem, we conduct experiments with 10 levels of time
budget, which are defined as 10 time constraints.

In our empirical study, we employed four well-known, multi-objective search
algorithms (MuOSAs) (i.e., NSGA-II [11], MOCell [12, 13], SPEA2 [14], and
CellDE [15]) to solve the 10 uncertainty-aware test case prioritization
problems under the 10 time constraints. We evaluated their performance with
Random Search (RS), with five use cases from two industrial CPS subject
systems. Results showed that all the selected MuOSAs performed significantly
better than RS. When comparing the MuOSAs, different algorithms performed best
to solve different prioritization problems for different subject systems.
Therefore, based on the results, we derived recommendations to select MuOSAs
for solving a particular test prioritization problem for a given time budget.
To further investigate the impacts of time budgets and compare performances
achieved by various problems to identify the best strategy, we conducted
analyses on them using a metric named ANOU representing efficiency in
observing uncertainties with prioritized solutions. Results of the analyses
indicate that there exist significant correlations between time budget and
ANOU, but the direction of the correlations (i.e., negative or positive) might
depend on use cases. In this empirical study, we found that four out of the
five use cases demonstrated a positive correlation; thus, 100% time constraint
(denoted as TB100) is recommended by default. Among the 10 uncertainty-wise
problems, the problems containing AUM and ANOU demonstrate better performances
than others. This hints that the two subjective measures might have a high
chance of positively triggering the occurrence of uncertainties during test
execution. In the five use cases, a multi-objectives problem defined with both
AUM and ANU, denoted as Prob.6 f(PET,PTR,AUM,ANU), achieved the overall best
performance.

Contributions. We: 1) proposed an uncertainty-aware and time-aware test
prioritization approach with tool support111https://github.com/man-
zhang/uncertainty-prioritization for optimizing test case execution cost-
effectively for complex software systems (e.g., CPSs) which need to deal with
inherent uncertainty; 2) reformulated uncertainty-aware and time-aware test
prioritization as 10 multi-objective search problems (MuOSP) under 10 time
constraints by considering four uncertainty-aware metrics, one cost measure,
and one effectiveness measure; 3) conducted an empirical study for 10
uncertainty-aware MuOSPs under 10 time constraints using four MuOSAs and RS on
five use cases from two industrial systems; and 4) provided a step-wise guide
to apply UncerPrio.

Paper structure: Section 2 presents the overall context and background.
Section 3 formulates the prioritization problems. Section 4.1.2 describes the
industrial subject systems. Section 4 presents the experiments and results.
The related work is given in Section 5 and Section 6 concludes the paper.

##  2 Background

This section provides the necessary background information on the source and
characterization of test cases to be prioritized. Section 2.1 introduces how
to construct test ready models222Test ready models capture known behaviors and
structure of the system under test (SUT) and are ready for enabling model-
based testing (MBT), e.g., for automated test case generation. with
uncertainty, which are used to automatically generate test cases with
uncertainty with an uncertainty-aware test case generation method (Section
2.2). Generated tests are then used as input by our uncertainty-aware
prioritization. Section 2.3 introduces the uncertainty-wise test verdict for
asserting uncertainty occurrences.

###  2.1 Belief test ready models developed with UncerTum

In our previous work, we have developed an integrated, UML-based modeling
framework (named as UncerTum) [9] for constructing test ready models with
subjective uncertainty 333From a subjective perspective, Zhang et al. [16]
defined uncertainty as ”a state of affairs whereby a BeliefAgent does not have
full confidence in a Belief that it holds”. information explicitly specified,
called belief test ready models (BMs). UncerTum is equipped with specialized
modeling notations, named the UML Uncertainty Profile (UUP), for specifying
uncertainties. As the core of UncerTum, UUP characterizes an uncertainty with
information such as IndeterminacySource (for capturing a source that may lead
to the occurrence of the uncertainty) and quantifies it via Measurement.
UncerTum also defines four sets of UML model libraries: Pattern, Time,
Measure, and Risk libraries.

* An example of test $t_{1}$: I$\rightarrow$T0$\rightarrow$S0$\rightarrow$T1$\rightarrow$S1$\rightarrow$T2$\rightarrow$S2$\rightarrow$T3$\rightarrow$S1$\rightarrow$T2 $\rightarrow$S2$\rightarrow$T2f$\rightarrow$F derived with the BSM; $un_{3}$ links to a known indeterminacy source IndS1 to enable a motion sensor jammer.

Figure 1: A simplified SafeHome example of the belief test ready model with
explicitly captured uncertainty

When modeling with UncerTum, i.e., specifying uncertainty as part of test
ready models (e.g., UML state machines specifying expected system behaviours)
and then forming belief test ready models, uncertainty is a situation whereby
engineers (belief agent) lack of confidence (hence subjective) about a system
behavior of the belief agent’s concern, e.g., whether a specified state occurs
after invoking a specified trigger action. An example of a belief state
machine (BSM) specified with UML state machine is shown in Figure 1, which
models the Monitoring behavior of SafeHome [17, 18] with uncertainty. With
UncerTum, we specify one uncertainty in the BSM based on the source state,
transition event, and target state. For instance, when the SafeHome system is
in state S0.Sensors Initializing (the source state), T1.after 1s (a transition
with time event is triggered), the system might transit to any of the two
potential target states (i.e., F.Final State and S1.Normal) non-
deterministically. To capture such uncertain behaviors, we identify two
uncertainties as $un_{1}(S0,T1,F)$ and $un_{2}(S0,T1,S1)$. In a BSM, we define
uncertainty space, which is the universal set of uncertainties originating
from the same source target triggered by the same event, such as
usp1=$\\{un_{1},un_{2}\\}$. Covering an uncertainty space indicates covering a
kind of uncertainty, and covering any uncertainty in an uncertainty space
means that this uncertainty space is covered, e.g., usp1 is covered if any
$un_{1}$ or $un_{2}$ is covered. In the BSM shown in Figure 1, there exist
eight unique transitions444Note that a unique transition is identified by
considering its source and target states, e.g., T1S0,S1 and T1S0,F are
considered as two unique transitions as their target states are different.
(i.e.,
TR(BM)=$\\{$T0${}^{I,S0},$T1${}^{S0,F},$T1${}^{S0,S1},$T2${}^{S1,S1},$T2${}^{S1,S2},$T3S2,S1,
T2f${}^{S2,F},$T1f${}^{S1,F}\\}$), four unique uncertainties (i.e.,
UU(BM)=$\\{un_{1},un_{2},un_{3},un_{4}\\}$), and two uncertainty spaces (i.e.,
USP(BM)=$\\{usp_{1},usp_{2}\\}$).

###  2.2 Test cases generation with UncerTest

UncerTest [9] is a model-based test case generation approach for testing CPSs
under uncertainty. Specifically, UncerTest takes BMs (Section 2.1) as input
and generates a set of executable test cases with uncertainty sources (i.e.,
indeterminacy sources) seeded in test environments.

####  2.2.1 Uncertainty measurements

Uncertainty can be measured differently. For instance, Probability Theory is
commonly applied to measure uncertainty as a frequency. However, its
application requires a large amount of data collected from a long-run
experiment to make the estimated measurement of uncertainty (i.e.,
probability) “close enough to the long-run frequency”. However, such a large
amount of data is usually unavailable at the startup phase of the test design
in the context of MBT [19]. Therefore, UncerTest opts for Uncertainty Theory
for handling uncertainty measurement when sufficient data does not exist to
estimate the probability. This theory measures uncertainty as a belief degree
from the subjective perspective of belief agents (engineers in our context).

Probability Theory measures uncertainty as probability, while Uncertainty
Theory measures uncertainty as Uncertain Measure Uncertain Measure is
represented as the $\mathcal{M}$ symbol and respects the three axioms below
[10]:

  * •

Normality:
$\mathcal{M}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}{\\{}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Gamma\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}{\\}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}=1$,
($\Gamma$ is the universal set).

  * •

Duality:
$\mathcal{M}\left\\{\Lambda\right\\}+\mathcal{M}\\{{\Lambda}^{c}\\}=1$, where
$\Lambda$ denotes a particular event, whereas ${\Lambda}^{c}$ denotes all the
events in the universal set excluding $\Lambda$.

  * •

Subadditivity:
$\mathcal{M}\\{\bigcup^{\infty}_{i=1}{{\Lambda}_{i}}\\}<\sum^{\infty}_{i=1}{\mathcal{M}\left\\{{\Lambda}_{i}\right\\}}$,
(every countable sequence of events ${\Lambda}_{1},{\Lambda}_{2},\dots$).

Uncertainty Space is defined as triplet ($\Gamma,\mathcal{L},\mathcal{M}$),
where $\Gamma$ is the universal set, $\mathcal{L}$ is a $\sigma$-algebra [20]
over $\Gamma$.

Theorem: Let ($\Gamma_{k},\mathcal{L}_{k},\mathcal{M}_{k}$) be uncertainty
spaces and ${\Lambda}_{k}\in{\mathcal{L}}_{k}$, for $k=1,2,\dots n$. Then
${\Lambda}_{1},{\Lambda}_{2},\dots\Lambda_{n}$ are always independent of each
other if they are from different uncertainty spaces.

As shown in Figure 1, with Probability Theory, uncertainty $un_{2}$ is
calculated with its occurrence frequency. For instance, $un_{2}$ occurs 98% of
the time, hence UM$(un_{2})$= Pr$(un_{2})$=$0.98$. With Uncertainty Theory, we
consider $un_{1}$ and $un_{2}$ from uncertainty space $usp_{1}$, and
$\mathcal{L}=\\{\emptyset,\\{un_{1}\\},\\{un_{2}\\},\\{un_{1},un_{2}\\}\\}$.
The measurement is calculated with belief degree of domain experts (e.g., when
there is insufficient historical data to calculate the frequency), for
instance, UM$(un_{2})=\mathcal{M}\\{un_{2}\\}=0.98$. The uncertainties from
different uncertainty spaces (e.g., $un_{2}$ from $usp_{1}$ and $un_{3}$ from
$usp_{2}$) are independent of each other.

####  2.2.2 Enabling Indeterminacy Sources

In UncerTum’s UUP, IndeterminacySource is for constructing known sources of
uncertainty. We extended it to trigger occurrences of specified uncertainties
during test execution by enabling indeterminacy sources in generated
executable test cases. For instance, it might increase the chance of enabling
the occurrence of uncertainty $un_{3}$(S1, T2, S1) (Figure 1) by employing a
motion sensor jammer (an indeterminacy source IndS1) when introducing an
intrusion (see T2S1,S1). In addition, indeterminacy sources are parts of
assertions for uncertainty occurrences, e.g., checking whether an uncertainty
occurs with enabled indeterminacy sources. More details are provided in
Section 2.3.

####  2.2.3 Generating Uncertainty-aware Test Cases

The need for uncertainty-wise testing emerged as part of our cooperation with
industrial partners, who observed that during the operation of their systems,
they observe uncertain behaviors (e.g., a device showing wrong measurements
for a short period, raising false alarms). As a result, they wanted to test
their system to find uncertainties. To this end, in our previous work, we
proposed UncerTest [9] consisting of two test case generation strategies, All
Simple Belief Paths (ASiBP) and All Specified Length Belief Paths (ASlBP), for
generating test cases based on BMs. The two strategies are distinguished by
whether round trips (i.e., paths containing circles) are allowed from the
practical perspective.

TABLE I: Characterization of test cases being prioritized

Phase |  Attribute |  Definition
---|---|---
Test Case |  TR$(t)$ |  Set of unique transitions covered by test case $t$: TR$(t)=\\{{tr}_{1},{tr}_{2},\dots,{tr}_{ntr_{t}}\\}$, where ${ntr}_{t}$ is the total number of the transitions.
Generation |  Us$(t)$ |  Multiset of uncertainties covered by $t$: Us$(t)=\\{u_{1},u_{2},\dots,u_{nu_{t}}\\}$, where $nu_{t}$ is the total number of the uncertainties.
|  UU$(t)$ |  Set of unique uncertainties covered by $t$: UU$(t)=\\{u_{1},u_{2},\dots,u_{nuu_{t}}\\}$, where ${nuu}_{t}$ is the total number of the uncertainties.
|  USP$(t)$ |  Set of uncertainty spaces covered by $t$: USP$(t)=\\{usp_{1},usp_{2},\dots,usp_{nusp_{t}}\\}$, where ${nusp}_{t}$ is the total number of the uncertainty spaces.
|  UM$(t)$ |  Uncertainty measurement of $t$. For instance, UM$(t)=0.8$ means that (1) with Uncertainty Theory: the modeler has 80% confidence that the execution of test case $t$ will pass; (2) with Probability Theory: the test case $t$ will pass with a probability of 80% based on its execution history [9]. Note that Uncertainty Theory was applied in UncerTest.
Test Case Execution |  ET$(t)$ |  One-time execution time of test case $t$. The average execution time for multiple executions of $t$: $AET(t)=\frac{\sum^{n}_{k=1}{ET^{k}(t)}}{n}$, where $n$ is the times of executions and $ET^{k}(t)$ is the time for the $k$th time execution.

Since BMs inputted to UncerTest contain uncertainty information, each
generated test case naturally has uncertainty characterized by the first five
attributes in Table I. For each test case, the values of the first three
attributes can be easily obtained by counting the number of transitions and
(unique) uncertainties along the test case’s path. An USP groups uncertainties
originating from the same state with the state transition representing its
potential outcomes. USP(t) counts a number of such USP covered in the path of
the test. UM(t) represents its uncertainty measurement derived based on
Uncertainty Theory (Section 2.2.1). For instance, based on the BM shown in
Figure 1, test $t_{1}$ traversing
I$\rightarrow$T0$\rightarrow$S0$\rightarrow$T1$\rightarrow$S1$\rightarrow$T2$\rightarrow$S2$\rightarrow$T3$\rightarrow$S1$\rightarrow$T2$\rightarrow$S2$\rightarrow$T2f$\rightarrow$F
could be derived with the ASlBP strategy, which contains round trips (e.g.,
S1$\rightarrow$T2$\rightarrow$S2$\rightarrow$T3$\rightarrow$S1). Test $t_{1}$
covers five transitions (i.e.,
TR$(t_{1})=\\{$T0${}^{I,S0},$T1${}^{S0,S1},$T2${}^{S1,S2},$T3${}^{S2,S1},$T2f${}^{S2,F}\\}$)
out of the eight, three uncertainties (i.e.,
Us$(t_{1})$=$\\{un_{2},un_{4},un_{4}\\}$), two unique uncertainties (i.e.,
UU$(t_{1})$=$\\{un_{2},un_{4}\\}$) out of the four, and two uncertainty spaces
(i.e., USP$(t_{1})$=$\\{usp_{1},usp_{2}\\}$). By applying Probability Theory,
the measurement is 0.96 (i.e., UM$(t_{1})$=Pr$(t_{1})$= $0.98\times 0.99\times
0.99$ = $0.96$) while the measurement is 0.98 by applying Uncertainty Theory
(i.e., UM$(t_{1})$=$\mathcal{M}\\{t_{1}\\}$=$0.98\wedge 0.99\wedge
0.99$=$0.98$).

UncerTest also converts indeterminacy sources captured along the sequence of
model elements of the BM (e.g., state, transition) as part of a generated
executable test case. UncerTest is equipped with four search-based test case
minimization strategies, which minimize the number of test cases to execute
and maximize the number of uncertainties. The minimization of UncerTest aims
at reducing test cases from tests generated automatically based on specified
preference (e.g., high uncertain measure). However, such a minimization does
not consider the practical constraints of executing all tests even after being
minimized, e.g., time budget. As a result, we observed that it was too costly
to execute even the minimized tests while working with our industrial
partners. Therefore, there was an emergent need to execute those test cases as
soon as possible, which were likely to lead to observing uncertainties. To
cater to such a need, we propose an uncertainty-aware prioritization specific
to handle uncertainty-aware test case execution by considering time-related
execution costs.

###  2.3 Uncertainty-aware Test Verdict

UncerTest also has a set of uncertainty-aware test verdicts for assessing the
occurrence of uncertainties together with the occurrence of indeterminacy
sources (Section 2.2.2). For instance, executing $t_{1}$ as shown in Figure 1,
when the SUT firstly arrives at state S1 (i.e.,
I$\rightarrow$T0$\rightarrow$S0$\rightarrow$T1$\rightarrow$S1), after an
intrusion is introduced to the SUT (i.e., T2), a specified uncertainty (i.e.,
$un_{4}$) is considered as occurred (i.e., KnOcurred) if the state of the SUT
transits to S2 while a specified uncertainty (i.e., $un_{4}$) is considered
not occurred (i.e., KnNotOcurred) if the state of the SUT transits to S1, an
alternative specified uncertainty in its uncertainty space. Note that if the
SUT transits to neither S1 or S2, we consider an unknown uncertainty occurred,
i.e., UkOccurred. The occurrence of indeterminacy sources depends on whether
the uncertainty is associated with an indeterminacy source (e.g., IndS1 for
$un_{3}$) and whether the indeterminacy source is enabled or not when the
uncertainty occurs. Note that the occurrence of an uncertainty might be
nondeterminate, e.g., due to a lack of knowledge of all associated
indeterminacy sources; hence, execution results for the same uncertainty might
be different in multiple executions. Evaluation results are part of test
execution results collected during test execution. UncerTest’s uncertainty-
aware verdicts are:

  * •

KnOccurred-With-InS: a specified uncertainty occurred under the occurrence of
one or more specified indeterminacy sources.

  * •

KnOccurred-Without-InS: a specified uncertainty occurred without having any
specified indeterminacy source occurred.

  * •

KnNotOccurred-With-InS: a specified uncertainty did not occur even though one
or more specified indeterminacy sources occurred.

  * •

KnNotOccurred-WithoutInS: a specified uncertainty did not occur under the non-
occurrence of any specified indeterminacy source.

  * •

KnOccurred-UkInS: a specified uncertainty occurred, and its indeterminacy
source(s) is unspecified (i.e., unknown).

  * •

KnNotOccurred-UkInS: a specified uncertainty did not occur, and its
indeterminacy source is unspecified (i.e., unknown).

  * •

UkOccurred: a specified uncertainty did not occur, and none of the existing
model elements (i.e., states and transitions in the BSM) could match the
occurrence, i.e., an unknown uncertainty occurred.

Compared to traditional test verdicts (e.g., Fail, Pass), uncertainty-aware
verdicts are defined for identifying unknowns [9], i.e., observing an
uncertainty occurrence that is previously unknown or a known uncertainty
occurred with previously unknown indeterminacy sources. Such unknowns might
refer to existing defects. For instance, an uncertainty that the SUT has not
properly handled because its source (i.e., indeterminacy source) was
previously unknown, which might relate to a flaw in the design of the SUT,
e.g., due to a lack of knowledge about the complexity of the system itself and
the complicated environment in operation. Whether to identify an observed
unknown as a defect or not requires determinations from practitioners who
should have the correct mindset of considering that recognizing uncertainties
is essential for reducing the risk of defects. Moreover, it is interesting to
study whether uncertainties relate to existing bugs or not requires further
investigation by practitioners. Consequently, studying such correlations to
guide practitioners in better identifying and locating bugs requires
conducting an entirely new empirical study, which is not the scope of this
paper. We would also like to mention that these uncertainty-aware verdicts are
especially important for CPSs, with some of their behaviors that can only be
known after deployment and in operation.

##  3 Approach

Figure 2 presents an overview of UncerPrio, together with UncerTum and
UncerTest, severing as an integrated platform for testing CPSs under
uncertainties.

First, uncertainties can be captured as part of BMs with UncerTum for
specifying uncertainty-related information, such as potential uncertain
behavior resulting from known indeterminacy sources and uncertainty
measurements (subjectively indicating belief agents’ belief degrees). Then,
UncerTest generates tests and minimizes them with a strategy specified by
users based on their preferences. Generated test cases are embedded with
triggers of related indeterminacy sources and verdicts for observing
uncertainty occurrences. Third, the execution results of such tests allow
UncerPrio to collect objective uncertainty measurements as frequencies of the
occurrence of subjective uncertainties specified in the BMs and unknown
uncertainties (i.e., those previously unspecified in the BMs).

To solve the test optimization problem with MuOSAs, we formulate the
uncertainty-aware test case prioritization problem as search problems (Section
3.1), define the time cost measure (CMF), effectiveness measure (EMF), and
uncertainty measures (UMF) (Section 3.2), and propose the fitness function to
minimize CMF, maximize EMF and maximize UMF (Section 3.3).

  * *

MuOSP: Multi-Objective Search Problem; MuOSA: Multi-Objective Search Algorithm

Figure 2: Overview of UncerPrio

###  3.1 Problem Formulation

Let T = $\\{$ti| 0 $<$ i $\leq$ nt$\\}$ be a set of test cases derived from a
BM with UncerTest (Section 2), which need to be prioritized. As discussed in
Section 2, each test case $t_{i}$ in T is characterized by the six attributes
(Table I). Thus, a prioritized solution within a specific time budget can be
defined as below:

$T_{prio}=\left\\{t^{{}^{\prime}}_{j},tb\right|0<j\leq
mt,\sum^{mt}_{1}ET\left(t^{{}^{\prime}}_{j}\right)\leq tb\times
ET(T)\\}\subseteq T$

where $T_{prio}$ is a subset of T, j is the position index (its order to
execute) of the prioritized test cases, mt is the total number of test cases,
ET(t) is the execution time of test case t, ET(T) is the total execution time
of all the test cases T, and tb refers a time budget defined as the percentage
of the total execution time ET(T). For example, tb = 40% means that the
execution time of the prioritized test cases cannot be more than 40% of the
execution time of all the test cases.

We define PI(j) to measure the impact of position j of test case
${t}^{{}^{\prime}}_{j}$ in $T_{prio}$ based on its cost-effectiveness. The
impact can be calculated as: $PI\left(j\right)=\frac{mt-j+1}{mt},0<j\leq mt$.
The overall idea is to guide the search to prioritize test cases with high
cost-effectiveness in earlier positions to be executed.

The search space of the test case prioritization problem is the set of
permutations of all the test cases from T or a subset of it, as represented
below:

$PS=\left\\{{ps}_{1},ps_{2},ps_{3}\dots ps_{nps}\right\\}$

where ${ps}_{i}$ is one potential solution $T_{prio}$, and $nps$ is the total
number of potential solutions. Each solution ${ps}_{i}$ can be characterized
with the following list of measures:

  * •

CostMeasure $=\left\\{{cm}_{1},{cm}_{2},\dots,{cm}_{ncm}\right\\}$, a set of
cost measures;

  * •

EffectMeasure $=\left\\{{em}_{1},{em}_{2},\dots,{em}_{nem}\right\\}$, a set of
effectiveness measures; and

  * •

UncerMeasure $=\\{{um}_{1},\ {um}_{2},\dots,{um}_{num}\\}$, a set of
uncertainty-aware measures.

Uncertainty-aware Test Case Prioritization Problem: With given time budget tb,
find a set of Pareto optimal solutions
${PS}_{p}=\left\\{{ps}_{k}\mathrel{\left|\vphantom{{ps}_{k}k\geq
1}\right.\kern-1.2pt}k\geq 1\right\\}\subseteq PS\ $that aim at:

$min\left({CMF}_{1}\left(ps\right),\dots,{CMF}_{ncm}\left(ps\right)\right),$
$max\left({EMF}_{1}\left(ps\right),\dots,{EMF}_{nem}\left(ps\right)\right),and$
$max({UMF}_{1}\left(ps\right),\dots,{UMF}_{num}(ps)),$

where 1) $ncm\geq 1$ and ${CMF}_{i}(ps)$ are for calculating values of the
cost measure ${cm}_{i}$ for solution $ps$; 2) $nem\geq 1$ and ${EMF}_{i}(ps)$
are for calculating values of the effectiveness measure ${em}_{i}$ for $ps$;
3) $num\geq 1$ and ${UMF}_{i}(ps)$ are for calculating values of the
uncertainty measure ${um}_{i}$) for $ps$. ${PS}_{p}$ is a set of nondominated
solutions and there does not exist a solution $ps\in PS$ that dominates
${ps}_{k}\in{PS}_{p}$, i.e., $\nexists ps\in PS-{PS}_{p}$ that satisfies 1)
$\forall CMF_{i}\in\\{CMF_{1},...,CMF_{ncm}\\}$,
${CMF}_{i}(ps)\leq{CMF}_{i}({ps}_{k})$, and 2) $\forall
EMF_{i}\in\\{EMF_{1},...,EMF_{nem}\\}$,
${EMF}_{i}(ps)\geq{EMF}_{i}({ps}_{k})$, and 3) $\forall
UMF_{i}\in\\{UMF_{1},...,UMF_{num}\\}$,
${UMF}_{i}(ps)\geq{UMF}_{i}({ps}_{k})$, and 4) $\exists
CMF_{i}\in\\{CMF_{1},...,CMF_{ncm}\\}$, ${CMF}_{i}(ps)<{CMF}_{i}({ps}_{k})$,
or $\exists EMF_{i}\in\\{EMF_{1},...,EMF_{nem}\\}$,
${EMF}_{i}(ps)>{EMF}_{i}({ps}_{k})$, or $\exists
UMF_{i}\in\\{UMF_{1},...,UMF_{num}\\}$, ${UMF}_{i}(ps)>{UMF}_{i}({ps}_{k})$.

###  3.2 Definitions of Measures

We introduce six measures to formulate the uncertainty-aware test
prioritization problem: one cost, one effectiveness and four uncertainty
measures. Note that the value ranges of all the measures are normalized
between 0 and 1.

####  3.2.1 Cost Measure

C1. Percentage of Execution Time (PET) $PET\left(T_{prio}\right)$ measures
time cost spent by tests as a percentage of the total execution time of all
the test cases (i.e., $\frac{ET(t^{{}^{\prime}}_{j})}{ET_{total}}$ for a test
at $j$th position), which can be calculated as:

$PET\left(T_{prio}\right)=\frac{\sum^{mt}_{j=1}ET(t^{{}^{\prime}}_{j})\times
PI(j)}{{ET}_{total}},0<j\leq mt$ (1)

We aim to minimize PET, i.e., PET$\downarrow$, spent by the prioritized test
cases; thus, a smaller value indicates a better result.

####  3.2.2 Effectiveness Measures

E1. Percentage of Transition Coverage (PTR) $PTR\left(T_{prio}\right)$
measures the percentage of the total number of unique transitions covered by
the prioritized test cases. We first define the set of unique transitions
covered by $T^{{}^{\prime}}_{j}$ as:
${TR}^{{}^{\prime}}\left(T^{{}^{\prime}}_{j}\right)=\bigcup^{j}_{k=1}{TR(t^{{}^{\prime}}_{k})}$,
and the size of ${TR}^{{}^{\prime}}\left(T^{{}^{\prime}}_{j}\right)$ as
${ntr}^{{}^{\prime}}_{{T}^{{}^{\prime}}_{j}}$. The relative complement of
${TR}^{{}^{\prime}}\left(T^{{}^{\prime}}_{j-1}\right)$ in
${TR}^{{}^{\prime}}\left(T^{{}^{\prime}}_{j}\right)$ is then defined as:

$\Delta{TR}^{{}^{\prime}}\left(T^{{}^{\prime}}_{j}\right)=\left\\{\begin{array}[]{ll}{TR}^{{}^{\prime}}\left(T^{{}^{\prime}}_{j}\right)\setminus{TR}^{{}^{\prime}}\left(T^{{}^{\prime}}_{j-1}\right),&j>1\\\
{TR}^{{}^{\prime}}\left(T^{{}^{\prime}}_{j}\right),&j=1\end{array}\right.$ (2)

where $\Delta{ntr}^{{}^{\prime}}_{T^{{}^{\prime}}_{j},1}$ is the size of
${\Delta TR}^{{}^{\prime}}\left(T^{{}^{\prime}}_{j}\right)$. Based on these
definitions, we can therefore calculate $PTR\left(T_{prio}\right)$ as:

$PTR\left(T_{prio}\right)=\frac{\sum^{mt}_{j=1}{\Delta
ntr^{{}^{\prime}}_{T^{{}^{\prime}}_{j},1}\times PI(j)}}{ntr},0<j\leq mt$ (3)

where $ntr$ is the total number of transitions covered by BSM used for
deriving the test cases. A higher PTR value indicates, in test execution, to
prioritize tests that include more unique transitions, i.e., covering more SUT
behaviors. Hence, we aim to maximize PTR (denoted as PTR$\uparrow$) covered by
prioritized test cases with a higher value indicating a better result.

####  3.2.3  Uncertainty measures

To consider uncertainty from various aspects in testing, we define four
uncertainty-aware objectives measuring uncertainty from four uncertainty-
related characteristics (see Table I), i.e., the measurement of its occurrence
(i.e., UM), the quantity of uncertainties being tested (i.e., Us), the
coverage of uncertainties (i.e., UU), and the coverage of kinds of
uncertainties (i.e., USP) in the context of MBT.

U1. Average Uncertainty Measure (AUM) $AUM\left(T_{prio}\right)$ measures the
average of uncertainty measurement of tests in the prioritized subset of test
cases:

$AUM\left(T_{prio}\right)=\frac{\sum^{mt}_{j=1}{UM(t^{{}^{\prime}}_{j})}\times
PI(j)}{mt},0<j\leq mt$ (4)

where $mt$ is the total number of test cases in $T_{prio}$ and
$UM(t^{{}^{\prime}}_{j})$ is the uncertainty measurement of
$t^{{}^{\prime}}_{j}$. As Uncertainty Theory used in UncerTest (see Table I),
$UM(t^{{}^{\prime}}_{j})$ measures a modeler’s confidence that the test
$t^{{}^{\prime}}_{j}$ will pass (i.e., the uncertainties in the test will
occur as specified). A higher value indicates, in the test execution, to
prioritize tests that are more likely to pass by including uncertainties with
higher measurements, then we aim to maximize AUM (denoted as AUM$\uparrow$);
thus, a higher value of it indicates a better solution.

U2. Average Normalized Number of Predefined Uncertainties Covered (ANU)
$ANU\left(T_{prio}\right)$ measures the average normalized number of
uncertainties that exist in the prioritized test cases:

$ANU\left(T_{prio}\right)=\frac{\sum^{mt}_{j=1}{nor\left({nu}_{t^{{}^{\prime}}_{j}}\right)\times
PI(j)}}{mt},\ 0<j\leq mt$ (5)

where ${nu}_{t^{{}^{\prime}}_{j}}$ is the number of uncertainties specified in
test case $t^{{}^{\prime}}_{j}$ which can be normalized as
$nor\left(x\right)=\frac{x}{x+1}$, and $mt$ is the total number of test cases
in $T_{prio}$. A higher value indicates, in the test execution, to prioritize
tests including more uncertainties to increase the chance to test the SUT in
the presence of uncertainties, then we aim to maximize ANU covered by the
prioritized test cases (denoted as ANU$\uparrow$); thus, a higher value
indicates a better solution.

U3. Percentage of Unique Predefined Uncertainties Covered (PUU)
$PUU\left(T_{prio}\right)$ measures the percentage of the total number of
unique uncertainties covered by prioritized test cases. We define the set of
unique uncertainties covered by $T^{{}^{\prime}}_{j}$ as:
${UU}^{{}^{\prime}}(T^{{}^{\prime}}_{j})=\bigcup^{j}_{k=1}{UU(t^{{}^{\prime}}_{k})}$,
and its size is ${nuu^{{}^{\prime}}}_{T^{{}^{\prime}}_{j}}$. The relative
complement of $UU^{{}^{\prime}}\left(T^{{}^{\prime}}_{j-1}\right)$ in
$UU^{{}^{\prime}}\left(T^{{}^{\prime}}_{j}\right)$ is then defined as:

$\Delta
UU^{{}^{\prime}}\left(T^{{}^{\prime}}_{j}\right)=\left\\{\begin{array}[]{ll}UU^{{}^{\prime}}\left(T^{{}^{\prime}}_{j}\right){\setminus}UU^{{}^{\prime}}\left(T^{{}^{\prime}}_{j-1}\right),&j>1\\\
UU^{{}^{\prime}}\left(T^{{}^{\prime}}_{j}\right),&0<j\leq 1\end{array}\right.$
(6)

where $\Delta{nuu}^{{}^{\prime}}_{T^{{}^{\prime}}_{j},1}$ is the size of
$\Delta UU^{{}^{\prime}}\left(T^{{}^{\prime}}_{j}\right)$. Based on these
definitions, we can therefore calculate $PUU\left(T_{prio}\right)$ with:

$PUU(T_{prio})=\frac{\sum^{mt}_{j=1}{\Delta{nuu}^{{}^{\prime}}_{T^{{}^{\prime}}_{j,1}}\times
PI(j)}}{nuu},0<j\leq mt$ (7)

where $nuu$ is the total number of uncertainties covered by the BSM. A higher
value indicates, in the test execution, prioritize tests that cover more
unique uncertainties, then we aim to maximize PUU covered by the prioritized
test cases (denoted as PUU$\uparrow$); thus, a higher value indicates a better
solution.

U4. Percentage of Uncertainty Space Covered (PUS) $PUS(t^{{}^{\prime}}_{j})$
is the percentage of the total set of uncertainty spaces of the BSM covered by
test case $t^{{}^{\prime}}_{j}$, which can be calculated as:

$PUS\left(t^{{}^{\prime}}_{j}\right)=\frac{{musp}_{t^{{}^{\prime}}_{j}}}{nusp}\times
100\%$ (8)

where $musp$ is the number of predefined uncertainty spaces covered by test
case $t^{{}^{\prime}}_{j}$ and $nusp$ is the total number of predefined
uncertainty spaces in the BSM. $PUS\left(T_{prio}\right)$ measures the
percentage of uncertainty spaces covered by the prioritized test cases, which
can be calculated as:

$PUS\left(T_{prio}\right)=\frac{\sum^{mt}_{j=1}{PUS(t^{{}^{\prime}}_{j})}\times
PI(j)}{mt},0<j\leq mt$ (9)

where $mt$ is the total number of test cases in $T_{prio}$. PUS is a measure
defined based on Uncertainty Space in Uncertainty Theory (Section 2). A higher
value indicates, in the test execution, prioritize tests covering more diverse
kinds of uncertainties (i.e., more unique uncertainty spaces), then we aim to
maximize PUS achieved by the prioritized test cases (PUS$\uparrow$); thus a
higher value indicates a better solution.

###  3.3 Fitness Functions

We reformulate the test prioritization problems as multi-objective search
problems, and each is considered a strategy to prioritize uncertainty-aware
tests for test execution. Considering the cost-effectiveness and being
uncertainty-aware (i.e., to trade-off between cost, model coverage, and
uncertainty-aware effectiveness), we define 10 prioritization problems and
formalize them as 10 fitness functions, as shown in Table II, aiming to
identify the best strategy for uncertainty-aware test prioritization. All of
the prioritization problems were formed with the cost measure (PET), the
effectiveness measure (PTR), and one or two uncertainty measures of the four.
The rationale is to consider potential correlations between any two
uncertainty measures and study their effectiveness in solving uncertainty-
aware test prioritization. For instance, Prob.5 f(PET,PTR,AUM,PUS) is to
prioritize test cases combined with two uncertainty measures that take less
time to execute, cover more transitions, have a higher uncertainty measurement
(i.e., a higher confidence that uncertainties will occur as specified), and
cover more kinds of uncertainties (i.e., more uncertainty spaces) in the front
of the test execution sequence.

To be time-aware, we also define 10 time budgets (denoted as TB10…TB100),
formulated as constraints in search, i.e., the execution time of $T_{prio}$
should be within a given time budget, as shown as:

$ET\leq tb\%\times ET_{total},tb=10,20\dots 100$ (10)

where $ET$ is the execution time of $T_{prio}$ and $ET_{total}$ is the total
execution time of all the test cases to prioritize $T$. Time constraints
restrict how many tests can be executed in the prioritized solution
$T_{prio}$.

TABLE II: Prioritization Problems and Fitness Functions

Prob. | Fitness Function | Prob. | Fitness Function
---|---|---|---
1 | f(PET,PTR,AUM) | 6 | f(PET,PTR,AUM,ANU)
2 | f(PET,PTR,PUS) | 7 | f(PET,PTR,AUM,PUU)
3 | f(PET,PTR,ANU) | 8 | f(PET,PTR,PUS,ANU)
4 | f(PET,PTR,PUU) | 9 | f(PET,PTR,PUS,PUU)
5 | f(PET,PTR,AUM, PUS) | 10 | f(PET,PTR,ANU,PUU)

##  4 Evaluation

Section 4.1 presents the experiment design, followed by results, a
recommendation to apply UncerPrio based on the results and threats to validity
in Sections 4.2 and 4.4 .

###  4.1 Experiment Design

The experiment design is summarized in Table III, which shows that our
empirical study has 2500 settings (= 10 × 10 × 5 × 5), formed by considering
the 10 prioritization problems with the 10 time budgets solved by 5 algorithms
(RS and 4 MuOSAs) for 5 use cases of 2 subject systems.

In Section 4.1.1, we present the employed MuOSAs. In Section 4.1.2, we present
the subject systems. In Sections 4.1.3 and 4.1.4, we present the research
questions (RQs) and evaluation metrics, followed by the statistical tests
(Section 4.1.5).

TABLE III: Experiment Design

RQs | Task | Problem |  | Time
---
Budget (TB)
Algorithm | Metric | Statistical Analysis |  | Use Case of
---
the Subject Systems
1 |  Compare each MOSA with RS |  Problems 1-10 (TableII) |  10, 20 30, 40 50, 60 70, 80 90, 100 |  RS (only for RQ1) EA: NSGA-II EA: MOCell EA: SPEA2 HA: CellDE |  HV IGD |  Comparison Analysis: \- Kruskal-Wallis Test \- Mann-Whitney U Test \- Vargha and Delaney Â12 Correlation Analysis: \- Spearman’s Rank Correlation Coefficient Multiple Hypothesis Testing: \- Holm–Bonferroni Method |  AW (AW1, AW1, AW3, AW4) GS (GS1)
2 |  | Compare among
---
MOSA
3 |  | Study impacts of
---
TB for each SUT
Best MuOSA | ANUO
4 |  | Compare problems
---
for each SUT
Best TB | Best MuOSA | ANUO

####  4.1.1 Employed MuOSAs

The employed MuOSAs are NSGA-II [11], MOCell [13], SPEA2 [14], and CellDE
[15], which are implemented in jMetal [21] and have been applied for
addressing various software engineering optimization problems (e.g.,
requirements engineering optimization problems [22, 23], product configuration
[24] and testing [2, 25]). RS is used as the comparison baseline to justify
the use of MuOSAs.

For all of the algorithms, we used their default parameter settings in jMetal,
which are also provided in Table V for reference. The stopping criterion is
the 25000 times fitness evaluations. Considering the inherent randomization of
search algorithms, we run RS and each MuOSA 100 times.

####  4.1.2 Subject Systems

The Empirical study of our prioritization problem is conducted with two
industrial case studies. The first system is GeoSports (GS), which attaches
devices to Bandy555Bandy is a variation of ice hockey often played in Northern
Europe. players for recording measurements (e.g., heartbeat, speed, location)
and deliver them during a game via a receiver station to a runtime monitoring
system used by coaches. To test GS in a lab setting without real players, a
test infrastructure (including hardware and software) was developed to execute
test cases [9]. Executing test cases on this test infrastructure is both time-
wise and monetary expensive; hence, available test suites need to be
optimized.

Another subject system is Automated Warehouse (AW) equipped with various
handling facilities (e.g., cranes, conveyors, sorting systems, picking
systems, rolling tables, lifts, and intermediate storage). A cloud-based
supervision system interacts with these physical units and network equipment.
AW implements several key scenarios such as introducing many pallets to the
warehouse and transferring items with stacker cranes. To test such scenarios,
relevant simulators and emulators have been developed. Further details on the
subject systems can be consulted in [26].

Test cases generated and minimized with UncerTest for GS and AW are used as
the dataset for evaluating UncerPrio, and the description of BMs used for test
generation can be found in [26]. The descriptive statistics of the test cases
collected from the five use cases of the two systems are provided in Table IV.
Column “# of Test Cases” shows the number of test cases to prioritize. For
example, for AW1, the total number of executable test cases to be prioritized
is 420, which requires 7924 seconds to execute.

TABLE IV: Characteristics of Employed Test Case Datasets

Subject System | Use Case | Execution Time (s) | # of Test Cases
---|---|---|---
AW | AW1 | 7924 | 420
AW2 | 15250 | 776
AW3 | 567960 | 857
AW4 | 1655 | 296
GS | GS1 | 118755 | 1799

####  4.1.3 Research Questions

In this empirical study, we aim to answer four RQs:

  * -

RQ1: How do the selected MuOSAs perform, when compared to RS, in terms of
solving the 10 uncertainty-aware test case prioritization problems constrained
with the 10 time budgets?

  * -

RQ2: For each use case and each time budget, which MuOSA is the best in
solving each prioritization problem?

  * -

RQ3: For each use case, how do the time budgets impact MOSAs’ performance in
solving each problem?

  * -

RQ4: For each SUT with a given time budget, which prioritization problem is
most efficient in observing uncertainties?

RQ1 is simply for the sanity check such that the use of MuOSAs can be
justified. RQ2 is defined for comparing the performance of the MuOSAs in
solving the optimization problems. RQ3 is designed to investigate the impact
of the various time budgets on the results. RQ4 is for studying the efficiency
of each test case prioritization problem in terms of observing uncertainties.

####  4.1.4 Evaluation Metrics

To assess the performance of the MuOSAs, we apply Hypervolume (HV) and
Inverted Generational Distance (IGD) indicators to compare the performance of
search algorithms according to the guideline in [27]. HV computes the volume
in the objective space that is covered by a non-dominated set of solutions
(e.g., Pareto front), by considering both convergence and diversity. IGD
measures the distance between the optimal non-dominated set of solutions and
the nearest solutions in the computed non-dominated set of solutions.

Based on the uncertainty-aware test verdict (Section 2.3), for each test, we
define a number of observed uncertainties NOUt as a basic evaluation metric.
Based on NOU, to enable comparison of solutions across the time budgets and
problems, we define Average Number of Observed Uncertainties (ANOU). ANOU
$\left(T_{prio}\right)$ measures the average number of observed uncertainties
by the prioritized test cases, as formally defined below:

$ANOU\left(T_{prio}\right)=\frac{\sum^{mt}_{j=1}{nou_{t^{{}^{\prime}}_{j}}\times
PI(j)}}{mt},0<j\leq mt$ (11)

where ${nou}_{t^{{}^{\prime}}_{j}}$ is the number of uncertainties observed in
executing test case $t^{{}^{\prime}}_{j}$, and $mt$ is the total number of
test cases in $T_{prio}$. This metric is an objective uncertainty measurement
and is used to assess the efficiency of solutions (i.e., prioritized test
cases) achieved by the prioritization problems we defined and the MuOSAs we
employed.

TABLE V: Parameter Settings of the MuOSAs

Parameter |  Settings
---|---
Population Size |  All: 100
Neighborhood |  MOCell and CellDE: 1-hop neighbors (8 surrounding solutions)
Parents Selection |  All: Binary Tournament
Crossover |  All but CellDE: Simulated Binary, CellDE: Differential evolution crossover rate: 0.9
Mutation |  All but CellDE: Polynomial, mutation rate: 1/n
Archive Size |  MOCell and CellDE: 100
Max Generation |  All: 25000
Times of Run |  All: 100

####  4.1.5 Statistical Tests

Table III represents the statistical tests we applied for answering the RQs.
Based on the guidelines in [28, 29], we conduct the comparative analysis with
the Kruskal–Wallis test, Mann-Whitney U test, and the Vargha and Delaney
statistics. Our study compares two or more groups (e.g., algorithms or
problems) with the Kruskal–Wallis test. If comparison results show that at
least one group originates from a different distribution compared to the
others (i.e., $p<$ 0.05), we apply the Mann-Whitney U test to perform pair-
wise comparisons with a significance level of 5%. Besides, we used the Vargha
and Delaney statistics to calculate Â12, a non-parametric effect size measure,
to demonstrate which group of a pair gives better results. To deal with
aggregated error probabilities arising due to multiple comparisons, we further
applied the Holm–Bonferroni method [30] as a post-hoc analysis to control the
family-wise error rate at level $\alpha$ (i.e., 5%).

To assess the performance of the algorithms, we use HV and IGD indicators by
following the guideline in [27]. For HV, a higher value means a better
performance of an algorithm (Section 4.1), while a smaller IGD value indicates
a better performance. With the employed statistical tests, based on the
results of indicators achieved by algorithms A and B on the same
prioritization problem, algorithm A outperforms algorithm B only if Â12 is
greater than 0.5 for HV, and Â12 is less than 0.5 for IGD. The difference is
considered significant if the p-value is less than 0.05. Moreover, to
demonstrate the performance of the algorithm compared to other algorithms on
the different subject systems, for each problem with each time budget, we
calculate a Rank value for each algorithm with Algorithm 1. Note that a higher
Rank value means better performance.

Algorithm 1 Rank Algorithm

1:$algos[\,],len(algos)\geq 2$

2:$algos[\,],rank[\,]$ $//$rank[i] is the rank value of algos[i]

3:$n\leftarrow len(algos)$

4:for $i\leftarrow 1$ to $n-1$ do

5: for $j\leftarrow i+1$ to $n$ do $//$sort algos[]

6: if $better(algos[i],algos[j])$ then

7: $switch(algos,i,j)$

8: end if

9: end for

10:end for

11:$rank[1]\leftarrow 1$

12:for $i\leftarrow 2$ to $n$ do $//$set rank values for algos[]

13: if $better(algos[i],algos[i-1])$ then

14: $rank[i]\leftarrow rank[i-1]+1$

15: else

16: $rank[i]\leftarrow rank[i-1]$

17: end if

18:end for

  * *

Function $better(algo1,algo2)$ compares $algo1$ with $algo2$, which returns
the best algorithm based on these two conditions: 1) for _PET_ , p-value $<$
0.05 and Â12 $<$ 0.5; 2) p-value $<$ 0.05 and Â12 $>$ 0.5.

With rank values, we further define Confidence, which computes the percentage
of a MuOSA being better than the others as:

$Confidence_{j}=\frac{Rank_{j}}{\sum^{n}_{i=1}{Rank_{i}}}\times
100\%,\;0<j\leq n$ (12)

To compare the prioritization problems for RQ4, we defined ANOU (Section 4.1).
The comparison analysis on the problems was the same as performed on the
algorithms, but the metric differed (i.e., ANOU for problems and HV for
algorithms).

To answer RQ3 and RQ4, we employed Spearman’s rank correlation coefficient
[31] to examine whether there is a correlation between two variables (e.g.,
time budgets and ANOU) for each problem in RQ3). We report the correlation
coefficient ($\rho$) and significance of correlation ($p$-value) with a
significance level of 5%. $p$-value determines whether two variables are
monotonically related, i.e., a monotonic relationship between the time budgets
and ANOU can be identified only if $p$-value is less than 0.05. Coefficient
($\rho$) represents the direction and strength of the correlation with its
value between -1 and +1. When a monotonic relationship exists, $\rho>0$ means
a positive correlation between time budget and ANOU, i.e., ANOU tends to
increase as the time budget increases, while $\rho<0$ suggests that ANOU tends
to decrease as time budget increases. Based on the guideline from [32],
$|\rho|>0.9$ could be considered as a very strong correlation between two
variables, and $|\rho|<0.1$ indicates the correlation is negligible.

###  4.2 Experiment Results

In this section, we analyze the experimental results to answer all RQs
(Sections 4.2.1 \- 4.2.4). Note that detailed statistical results can be found
in our online repository1.

####  4.2.1 Answers for RQ1

To answer RQ1, we conducted comparisons of the four selected algorithms with
RS for solving the 10 search problems (see Table II) on the 5 use cases from
the 2 subject systems (i.e., the 4 selected use cases for AW and 1 use case
for GS), using the 10 time budgets regarding HV and IGD. Thus, we have 2000
(i.e., 4 $\times$ 10 $\times$ 5 $\times$ 10) combinations of comparisons. The
Mann-Whitney U test, the Holm–Bonferroni method, and the Vargha and Delaney
statistics were employed to compare each MuOSA with RS, and the results of HV
and IGD for each comparison between each MuOSA and RS under each time
constraint can be found in the online repository1.

To summarize the results, in 97.45% (1949/2000) of the cases regarding HV and
81.4% (1628/2000) of the cases regarding IGD, the selected MuOSAs
significantly outperformed RS since all Â12 values were greater than 0.5 and
p-values were less than 0.05. In 0.45% (9/2000) of the cases in terms of HV
and 18.6% (372/2000) in terms of IGD, we observed no significant differences
between the RS and the selected MuOSAs since p-values were greater than 0.05.
Regarding the cases that RS outperformed MuOSAs, in terms of HV, we found 2.1%
(42/2000) of the cases, which are only observed in AW4 (18 cases out of 400)
and GS1 (24 cases out of 400) when using SPEA2. Regarding IGD, there are no
downside cases, i.e., 0% (0/2000).

RQ1: The prioritization problems are complex, hence warranting the use of
MuOSAs to solve them since for 97.9% with HV and 100% with IGD of the time
MuOSAs either significantly outperformed RS (97.45% with HV and 81.4% with
IGD) or there were no significant differences observed (0.45% with HV and
18.6% with IGD).

####  4.2.2 Answers for RQ2

With RQ2, we aim to find the best MOSA among MuOSAs for each prioritization
problem with each time budge, with the Kruskal-Wallis Test, Mann-Whitney U
Test, Vargha and Delaney statistics, and Holm–Bonferroni method. Detailed
comparison results of the 10 prioritization problems on the five use cases in
the 10 time budgets with HV and IGD can be found in our online repository1.

Table VI shows the overall best MuOSA for each problem for each time budget
based on the best algorithms of all the use cases. The table is summarized by
following two steps. First, for each use case, we select algorithms that
performed the best regarding HV and/or IGD for each problem under each time
budget. If one of the selected algorithms achieved the best regarding both HV
and IGD, we opt for it as the best. For instance, for Prob.1 f(PET,PTR,AUM)
within TB10 on AW1, both NSGA-II and SPEA2 achieve the best HV, and only SPEA2
achieves the best IGD, then SPEA2 is recognized as the best for solving Prob.1
f(PET,PTR,AUM) within TB10 on AW1. If there exist distinct best algorithms in
terms of HV and IGD, we then follow the guideline in [27] to employ the
recommended indicator for deciding the best. For instance, for Prob.6
f(PET,PTR,AUM,ANU) within TB40 on AW2, MoCell achieves the best HV and SPEA2
achieves the best IGD. As IGD is the recommended indicator in the pair
comparison of MoCell and SPEA2 according to the guideline, we then identify
SPEA2 as the best algorithm for solving Prob.6 f(PET,PTR,AUM,ANU) within TB40
on AW2.

Second, based on the summary of the best algorithm for each problem within
each time budget on each use case, we select the algorithm that achieves the
highest number of best results among the use cases as the best one. For
instance, SPEA2 is selected as the best algorithm for solving Prob.1
f(PET,PTR,AUM) within TB10 as SPEA2 is recognized as the best on AW2, AW3, AW4
and GS1 in solving Prob.1 f(PET,PTR,AUM) within TB10.

TABLE VI: Summary of the best MuOSA(s) for each Problem with each time budget
\- RQ2. Green–MOCell; Blue–SPEA2; Yellow–Multiple MuOSAs.

|  | Time Budgets
---|---|---
|  |  TB10 |  TB20 |  TB30 |  TB40 |  TB50 |  TB60 |  TB70 |  TB80 |  TB90 |  TB100
Problems |  Prob. 1 |  S |  S |  S |  S |  S |  S |  S |  S |  S |  S
Prob. 2 |  S |  S |  S |  S |  S |  S |  S |  S |  S |  S
Prob. 3 |  M/S |  S |  S |  S |  S |  S |  S |  S |  S |  S
Prob. 4 |  S |  S |  S |  S |  S |  S |  S |  S |  S |  S
Prob. 5 |  S |  S |  S |  S |  S |  S |  S |  S |  S |  S
Prob. 6 |  M |  M |  M |  S |  M/S |  M/S |  S |  S |  S |  S
Prob. 7 |  S |  S |  S |  S |  S |  S |  S |  S |  S |  S
Prob. 8 |  M/S |  M/S |  S |  S |  S |  S |  S |  S |  S |  S
Prob. 9 |  S |  S |  S |  S |  S |  S |  S |  S |  S |  S
Prob. 10 |  S |  N/M |  S |  S |  S |  S |  S |  S |  S |  S

  * *

Note that N: NSGA-II, M: MOCell, and S: SPEA2

Based on Table VI, SPEA2 achieves the best results in 96 out of 100
configurations, i.e., 10 problems under 10 time constraints. However, users
might have their own preferences and available time budget to execute tests.
We provide this recommendation table (Table VI) for the users to select an
algorithm for a particular test prioritization problem for a particular time
budget. For example, if one has a particular interest in solving Prob.9
f(PET,PTR,PUS,PUU), i.e., minimizing PET and maximizing PTR, PUS, and PUU with
any time budget (10% to 100%), we recommend using SPEA2 since it consistently
performed the best for all the use cases and for all the time budgets.

RQ2: We recommend SPEA2 as it achieved the best performance in 96 out of 100
configurations . However, as users could have their own interests and
available budget to perform test execution, a recommendation table is derived
to guide the algorithm selection for a specific problem within an available
time budget.

####  4.2.3 Answers for RQ3

RQ3 studies the impacts of various time budgets for each problem with the best
algorithm obtained in RQ2. We conducted a correlation analysis on ANOU
achieved with various time budgets (i.e., TB10 – TB100) using the Spearman
Correlation Coefficient. Results (i.e., $\rho$ and $p$-value) are reported in
Table VII.

TABLE VII: Results of the Spearman Correlation Coefficient between various
time budgets and ANOU with the best MuOSA(s) for each problem on all case
studies \- RQ3

Problem | AW1 | AW2 | AW3 | AW4 | GS1
---|---|---|---|---|---
Prob.1 f(PET,PTR,AUM) | 0.58 | 0.93 | -0.25 | 0.99 | 0.96
Prob.2 f(PET,PTR,PUS) | 0.96 | 0.94 | -0.12 | 0.99 | 0.99
Prob.3 f(PET,PTR,ANU) | 0.96 | 0.98 | -0.95 | 0.04 | -0.06
Prob.4 f(PET,PTR,PUU) | 0.96 | 0.94 | -0.18 | 0.99 | 0.98
Prob.5 f(PET,PTR,AUM,PUS) | 0.41 | 0.89 | -0.21 | 0.99 | 0.96
Prob.6 f(PET,PTR,AUM,ANU) | 0.26 | 0.45 | -0.52 | -0.01 | -0.06
Prob.7 f(PET,PTR,AUM,PUU) | 0.50 | 0.89 | -0.20 | 0.99 | 0.95
Prob.8 f(PET,PTR,PUS,ANU) | 0.96 | 0.97 | -0.96 | 0.07 | 0.00
Prob.9 f(PET,PTR,PUS,PUU) | 0.96 | 0.94 | -0.09 | 0.99 | 0.98
Prob.10 f(PET,PTR,ANU,PUU) | 0.96 | 0.98 | -0.95 | 0.03 | -0.08

  * *

Note that an underlined value means that the correlation is not statistically
significant (i.e., $p$-value > 0.05; otherwise, significant (i.e., $p$-value
$<$ 0.05).

Based on the results in Table VII, for all of the 10 problems on the four use
cases, except for Prob.8 f(PET,PTR,PUS,ANU) on GS1, a monotonic relationship
exists between time budgets and ANOU (i.e., $p$-value $<$ 0.05). Regarding the
overall tendency, for AW1 and AW2, the monotonic relationship is positive
(i.e., $\rho$ $>$ 0), meaning that as the time budget increases, ANOU observed
by executing tests as the sequence prioritized by UncerPrio tends to increase.
For AW4 and GS1, the monotonic relationship between is positive in most
problems, except for Prob.3 f(PET,PTR,ANU) on GS1, Prob.6 f(PET,PTR,AUM,ANU)
on AW4 and GS1, and Prob.10 f(PET,PTR,ANU,PUU) on GS1. However, the
correlation coefficient of negative cases is negligible, i.e., $|\rho|<$ 0.1.
Results obtained in AW3 are different from the other four use cases, for all
of the problems, the monotonic relationship between time budgets and ANOU is
negative, i.e., $\rho$ $<$ 0\. It indicates that as the time budget increases,
the ANOU tends to decrease with the prioritized sequence to execute the tests.

To identify the TB strategy, Table VIII demonstrates the best TB, which
achieves the best ANOU for each problem on each use case. The results showed
that the TB100 strategy performed best with all problems on AW1 and AW2. For
AW4 and GS1, except for four problems that contain ANU, the TB100 strategy
achieved the best in the other six problems. For AW3, the low time budget
(i.e., TB10, TB20, and TB30) obtained the best results among all of the
problems. The results of the best TB strategy are consistent with the results
of the overall tendency for each use case (Table VII), i.e., the positive
coefficient results in the greater TB as the best while the negative
coefficient results in the lower TB as the best.

TABLE VIII:  Summary of the best TB strategy for each problem on each use case
\- RQ3

Problem | AW1 | AW2 | AW3 | AW4 | GS1
---|---|---|---|---|---
Prob.1 f(PET,PTR,AUM) | TB100 | TB100 | TB20 | TB100 | TB100
Prob.2 f(PET,PTR,PUS) | TB100 | TB100 | TB10 | TB100 | TB100
Prob.3 f(PET,PTR,ANU) | TB100 | TB100 | TB10 | TB80 | TB20
Prob.4 f(PET,PTR,PUU) | TB100 | TB100 | TB10 | TB100 | TB100
Prob.5 f(PET,PTR,AUM,PUS) | TB100 | TB100 | TB20 | TB100 | TB100
Prob.6 f(PET,PTR,AUM,ANU) | TB100 | TB100 | TB30 | TB60 | TB50
Prob.7 f(PET,PTR,AUM,PUU) | TB100 | TB100 | TB20 | TB100 | TB100
Prob.8 f(PET,PTR,PUS,ANU) | TB100 | TB100 | TB10 | TB90 | TB80
Prob.9 f(PET,PTR,PUS,PUU) | TB100 | TB100 | TB10 | TB100 | TB100
Prob.10 f(PET,PTR,ANU,PUU) | TB100 | TB100 | TB10 | TB60 | TB40

Based on the above results, the performance of TB strategies varies from use
case to use case and from problem to problem. To further investigate
performance with various TB, for each use case, we reported a scatter plot of
execution time spent by each test case along with its observed uncertainties
(i.e., NOU) as shown in Figure 3, and detailed statistics (i.e., average,
maximum, minimum and standard deviation) of execution time as shown in Table
IX. In this table, we also report the average time (seconds) to observe an
actual occurrence of uncertainty, i.e., Avg(ET/NOU). Based on the results,
compared to other use cases, we found that test cases in AW3 spent more time,
and differences among test cases are greater. The time cost to observe an
uncertainty in AW3 (i.e., 117.40 seconds on average) is also much more than in
other use cases. Thus, with an increase in time budget, the efficiency metric
ANOU would probably decrease. This may explain the negative correlation result
between time budget and ANOU in AW3, while a positive correlation exists in
other use cases in most cases.

Figure 3: A scatter plot of execution time ($x$ axis in seconds) of each test
case versus a number of uncertainties observed per test case (i.e., NOU in $y$
axis) for each use case \- RQ3 TABLE IX: Descriptive statistics of the
execution times (in seconds) of test cases to prioritize for each use case,
and the average time (in seconds) needed to observe an uncertainty (i.e.,
Avg(ET/NOU)) \- RQ3

Use Case | Avg | Max | Min | $\bm{\sigma}$ | Avg(ET/NOU)
---|---|---|---|---|---
_AW1_ | 18.87 | 300.01 | 4.82 | 42.60 | 9.44
_AW2_ | 19.65 | 300.00 | 10.25 | 37.01 | 11.20
_AW3_ | 662.73 | 1200.02 | 373.05 | 165.87 | 117.40
_AW4_ | 5.59 | 6.66 | 1.78 | 1.26 | 0.58
_GS1_ | 66.01 | 99.70 | 10.30 | 14.66 | 23.50

Based on results of correlation analysis (Table VII) and best TB (Table VIII),
in AW4 and GS1, the problems which contain ANU achieved different best TB
strategies than other problems. The ANU objective is derived from a number of
subjective uncertainties (i.e., NU) of test cases based on their prioritized
sequence. To analyze NU with ANOU in various use cases, we reported a scatter
plot of NU specified in each test case versus its observed uncertainties
(i.e., NOU) as shown in Figure 4, and performed a Spearman Correlation
analysis on NU and NOU of test cases for each use case (Table X). With the
results, we found that in AW3, AW4 and GS1, a greater NU trends to observe
more NOU, while such a correlation is not significant in AW1 and AW2. Thus, in
AW3, AW4 and GS1, the problems with ANU objective would result in a higher
chance to prioritize tests that are capable of observing more uncertainties in
the front positions of the execution sequence. For AW4 and GS1, since there
does not exist much difference in execution time (see $\sigma$ in Table IX),
test cases in the front positions of the sequence would probably achieve
higher ANOU than ones in the rear positions. Thus, this might explain that the
less time budget (i.e., less than TB100) achieves the best ANOU for the
problems that contain ANU in AW4 and GS1. In Table X, we also report the
average time to target a specified subjective uncertainty, i.e., Avg (ET/NU).
For all of the use cases, the actual time spent to observe an uncertainty is
longer than expected, i.e., Avg(ET/NOU) $>$ Avg (ET/NU). Thus, if test cases
of a use case take time to target a subjective uncertainty, such as more than
1 minute in AW3, it would probably take more time to observe an uncertainty.
Therefore, for use cases that take more time to target a subjective
uncertainty (i.e., Avg(ET/NU) $>$ 60s) as the efficiency would probably
decrease over time, we would recommend less time budget as the TB strategy,
i.e., TB10/TB20/TB30.

Figure 4: A scatter plot of a number of subjective uncertainties (i.e., $x$
axis is NU) of each test case versus a number of uncertainties observed per
the test case (i.e., $y$ axis is NOU) for each use case \- RQ3 TABLE X:
Results of the Spearman Correlation Coefficient between NU and NOU of test
cases for each use case \- RQ3

Use Case | $\bm{\rho}$ |  $\bm{p}$-value | Avg(ET/NU)
---|---|---|---
_AW1_ | 0.02 | 0.67 | 2.51
_AW2_ | 0.03 | 0.45 | 3.18
_AW3_ | 0.44 |  $<$0.01 | 69.75
_AW4_ | 0.86 |  $<$0.01 | 0.43
_GS1_ | 0.39 |  $<$0.01 | 8.54

  * *

Note that an underlined value means that the correlation is not statistically
significant (i.e., $p$-value > 0.05); otherwise significant.

Based on the above analyses, we found that TB100 achieved the best in most
cases. For cases that spend more execution time and have fewer subjective
uncertainties, we would recommend fewer TB strategies (such as AW3). If test
cases in a use case spend less time, the best TB strategy would highly depend
on use cases and problems such as AW1 $vs.$ AW4, we cannot conclude a clear
recommendation currently. However, if the time budget is not a practical
constraint, we recommend TB100.

RQ3: Significant correlations between time budget and ANOU are observed in all
five use cases, but the direction and strength are use case by use case. TB100
(i.e., executing all tests) is recommended when the time budget is not a
practical constraint; otherwise, we recommend strategies requiring smaller TB
(i.e., TB10/TB20/TB30), especially for cases with few uncertainties specified.

####  4.2.4 Answers for RQ4

RQ4 studies efficiency among 10 uncertainty-aware test case prioritization
problems. The efficiency of each problem is measured with ANOU achieved by the
best MuOSA using TB100 (selected in RQ3). Detailed configurations for each
problem on each use case can be found in the online repository1.

(a) AW1

(b) AW2

(c) AW3

(d) AW4

(e) GS1

Figure 5: Average ANOU ($y$ axis) achieved with the best MuOSAs reported at
every 10% used time budget ($x$ axis) with the TB100 strategy for all of the
10 prioritization problems on each use case \- RQ4

To compare the problems, we conducted comparative analyses and reported
results of Rank (see Algorithm 1) and Confidence (see Equation 12) in Tables
XI and XII respectively. More detailed results of the Kruskal-Wallis Test,
Mann-Whitney U Test, Vargha and Delaney effect size, and Holm–Bonferroni
method can be found in our online repository1. Regarding the results of Rank
and Confidence, we found that Prob.6 f(PET,PTR,AUM,ANU) performed the best
(i.e., the highest rank value) in four out of the five use cases (i.e., except
AW3) and performed the third best (inferior to Prob 3, 8 and 10) in AW3. In
addition, Prob.6 f(PET,PTR,AUM,ANU) achieved the overall best performance
among the five use cases with Rank and Confidence metrics (see All in Tables
XI and XII).

TABLE XI: Rank results of each problem on each use case with ANOU \- RQ4. Note
that a greater value means a better performance, and the grey cells are the
best.

UC |  Problem
---|---
1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10
AW1 |  8 |  1 |  4 |  1 |  7 |  10 |  9 |  5 |  1 |  6
AW2 |  4 |  1 |  7 |  1 |  6 |  10 |  4 |  8 |  1 |  8
AW3 |  5 |  2 |  9 |  1 |  4 |  7 |  5 |  8 |  2 |  9
AW4 |  4 |  2 |  8 |  3 |  4 |  10 |  4 |  7 |  1 |  9
GS1 |  5 |  2 |  7 |  1 |  4 |  10 |  5 |  8 |  3 |  9
All |  26 |  8 |  35 |  7 |  25 |  47 |  27 |  36 |  8 |  41

TABLE XII: Confidence results of each problem on each use case with ANOU \-
RQ4. Grey cells highlight the best.

UC |  Problem
---|---
1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10
AW1 |  15% |  2% |  8% |  2% |  13% |  19% |  17% |  10% |  2% |  12%
AW2 |  8% |  2% |  14% |  2% |  12% |  20% |  8% |  16% |  2% |  16%
AW3 |  10% |  4% |  17% |  2% |  8% |  13% |  10% |  15% |  4% |  17%
AW4 |  8% |  4% |  15% |  6% |  8% |  19% |  8% |  13% |  2% |  17%
GS1 |  9% |  4% |  13% |  2% |  7% |  19% |  9% |  15% |  6% |  17%
All |  10% |  3% |  13% |  3% |  10% |  18% |  10% |  14% |  3% |  16%

In order to provide more details on the performance of the 10 problems, Figure
5 plots the average ANOU over time spent by executing tests with the sequence
prioritized by each problem, and the results are reported at every 10% time
budget under the TB100 strategy. In terms of average ANOU, prioritized
solutions achieved by Prob.6 f(PET,PTR,AUM,ANU) outperformed solutions by
other problems throughout the entire execution in four out of the five use
cases except for AW3. Regarding AW3, a group of problems, i.e., Prob.3, 6, 8,
and 10 achieved the best, and the differences among them are modest. Thus,
Prob.6 f(PET,PTR,AUM,ANU) can be recognized as the best among all five use
cases.

To investigate subjective uncertainty objectives defined in the problems
responding to ANOU, for each use case, we conducted Spearman’s rank
correlation coefficient for each subjective measure for a test (i.e., UM, NU,
NUU, and USP) with a number of observed uncertainties by the test (i.e., NOU).
In addition, we analyzed the correlation coefficient between each pair of
subjective measures to study uncertainty properties in the tests being
prioritized. Results are shown in Table XIII. Regarding NU, NUU, and USP
responding to NOU (i.e., NOU $\sim$NU, NOU $\sim$NUU, and NOU $\sim$USP),
there does not exist a significant correlation between the three measures and
NOU in AW1 and AW2, and a positive correlation is observed in AW3, AW4 and
GS1. In terms of the significant correlations, comparing with NUU and USP, NU
obtained a higher positive strength (see $\rho$) signifying that a greater NU
has a higher chance to lead to a higher ANOU. In addition, with the
correlation results of NU, NUU, and USP, we found that they are all positively
correlated (see NU $\sim$NUU, NU $\sim$USP, and NUU $\sim$USP). Thus, there
might be a lack of interactions between any pair of the three measures.
Moreover, since NU (referring to ANU) might be superior to NUU (referring to
PUU) and USP (referring to PUS), this might explain that the problems
containing ANU are consistently better than the problems containingPUU or PUS
in all use cases. Another piece of evidence is that the four problems
containing ANU are consistently the best in four out of five use cases (except
for AW1).

In terms of UM, there does not exist a clear correlation between UM and NOU as
(1) in AW1–4, $p$-value is greater than 0.05, and (2) in GS1, $p$-value is
less than 0.05 but $\rho$ is low (i.e., 0.11). Regarding the correlation of UM
with NU, NUU, and USP, results are consistent for the three measures, i.e.,
$p$-value is less than 0.05 and $\rho$ is negative in all of the use cases. It
indicates that, for tests being prioritized, a test with more subjective
uncertainties (i.e., a greater NU) or more unique subjective uncertainties
(i.e., a greater NUU) or covering more uncertainty spaces (i.e., a greater
USP) tends to have a lower uncertainty measure (i.e., UM). UM for a test is
calculated based on a minimum value of UM of all uncertainties it contains,
then a test with more (unique) uncertainties or covering more uncertainty
space would result in a higher chance to include an uncertainty with a lower
UM. This might be a reason for the negative correlation of UM with NU, NUU and
USP. As the correlation results, UM and NOU are not significantly correlated,
but with the results of problems that contain AUM, we found that the best four
in AW1 are the problems that contain AUM. This might be due to a non-
significant correlation between NU and NOU in AW1, and comparing NU and UM in
this use case, UM might better guide to observing the uncertainties. However,
combining NU with UM, they could interact with each other, e.g., if tests have
the same NU, UM might be possible to distinguish the tests that have a greater
UM in the front positions. Such prioritized tests might result in better
performance, as Prob.6 f(PET,PTR,AUM,ANU) achieved the overall best.

RQ4: An uncertainty-aware prioritization problem with maximizing AUM and
maximizing ANU (i.e., Prob.6 f(PET,PTR,AUM,ANU)) achieved the overall best
performance in terms of efficiency in observing uncertainties.

TABLE XIII: Results of the Spearman Correlation Coefficient for each pairs of
NOU, UM, NU, NUU, and USP of test cases for each use case \- RQ4

Use Case | NOU $\bm{\sim}$UM | NOU $\bm{\sim}$NU | NOU $\bm{\sim}$NUU | NOU $\bm{\sim}$USP
---|---|---|---|---
$\bm{\rho}$ |  $\bm{p}$-value | $\bm{\rho}$ |  $\bm{p}$-value | $\bm{\rho}$ |  $\bm{p}$-value | $\bm{\rho}$ |  $\bm{p}$-value
_AW1_ | 0.02 | 0.74 | 0.02 | 0.67 | -0.07 | 0.15 | -0.09 | 0.06
_AW2_ | -0.01 | 0.70 | 0.03 | 0.45 | -0.07 | 0.04 | -0.03 | 0.46
_AW3_ | 0.06 | 0.10 | 0.44 |  $<$0.01 | 0.25 |  $<$0.01 | 0.17 |  $<$0.01
_AW4_ | -0.05 | 0.41 | 0.86 |  $<$0.01 | 0.57 |  $<$0.01 | 0.58 |  $<$0.01
_GS1_ | 0.11 |  $<$0.01 | 0.39 |  $<$0.01 | 0.28 |  $<$0.01 | 0.19 |  $<$0.01
| UM $\bm{\sim}$NU | UM $\bm{\sim}$NUU | UM $\bm{\sim}$USP |
_AW1_ | -0.12 | 0.01 | -0.16 |  $<$0.01 | -0.13 |  $<$0.01 |  |
_AW2_ | -0.16 |  $<$0.01 | -0.29 |  $<$0.01 | -0.16 |  $<$0.01 |  |
_AW3_ | -0.28 |  $<$0.01 | -0.43 |  $<$0.01 | -0.20 |  $<$0.01 |  |
_AW4_ | -0.13 | 0.02 | -0.35 |  $<$0.01 | -0.29 |  $<$0.01 |  |
_GS1_ | -0.25 |  $<$0.01 | -0.53 |  $<$0.01 | -0.12 |  $<$0.01 |  |
| NU $\bm{\sim}$NUU | NU $\bm{\sim}$USP | NUU $\bm{\sim}$USP |
_AW1_ | 0.36 |  $<$0.01 | 0.30 |  $<$0.01 | 0.80 |  $<$0.01 |  |
_AW2_ | 0.37 |  $<$0.01 | 0.22 |  $<$0.01 | 0.77 |  $<$0.01 |  |
_AW3_ | 0.40 |  $<$0.01 | 0.24 |  $<$0.01 | 0.77 |  $<$0.01 |  |
_AW4_ | 0.57 |  $<$0.01 | 0.58 |  $<$0.01 | 1.00 |  $<$0.01 |  |
_GS1_ | 0.47 |  $<$0.01 | 0.27 |  $<$0.01 | 0.28 |  $<$0.01 |  |

###  4.3 Applying UncerPrio

UncerPrio is designed to optimize the test execution process specific to SUTs
facing uncertainty (e.g., unpredictable operating environment). As shown in
Figure 6, first, applying UncerPrio requires a set of executable tests with
sufficient information for calculating the four uncertainty measures (A1).
Note that UncerPrio was implemented as a series of uncertainty-wise solutions
including an uncertainty modeling approach (UncerTum) and an automated test
generation approach (UncerTest), as shown in Figure 2. However, UncerPrio can
be independent of them as long as tests have sufficient information as O1
(e.g., a demo example with JSON provided in our
repository666https://github.com/man-zhang/uncertainty-
prioritization/blob/main/example/foo.json).

Users of UncerPrio can select an applicable strategy, in the sense that
required information is available for calculating required uncertainty
measures, to prioritize tests (A2) based on preferences, though UncerPrio’s
default strategy is Prob.6 f(PET,PTR,AUM,ANU), as it achieves the overall best
performance in observing uncertainties in our experiment. Considering the
available time budget and repetition times of test executions, a user can
decide on a time constraint (A3). UncerPrio’s default time budget is TB100,
which is set based on our experimental results. If there is a lack of
knowledge about the SUT and its operating environment, we recommend executing
tests multiple times to gain (objective) knowledge based on execution results.
However, we do not have a concrete recommendation on the number of
repetitions, as an empirical study involving industry practitioners is needed
in the future to derive such information. With the specified strategy and time
constraint, we recommend an MuOSA by referring to Table VI (A4). However, a
user can specify one to use if needed.

We implemented UncerPrio as an open-source prototype tool, which is online
available1. The tool can be used (A5) via a command line as its user interface
and is accompanied by documentation and an example demonstrating how to use
it. Guided by solutions produced by the tool (O2), users can conduct test
execution on their test execution infrastructures (A6) and obtain test
execution results (O3). To ease the introduction of indeterminacy sources and
conveniently observe their occurrences, we recommend making the test
infrastructure controllable (e.g., manipulating the test environment) and
accessible (e.g., retrieving statuses of the test environment). For instance,
in our experiment, for testing GS1, an available test infrastructure
facilitates accessing statuses of the SUT in real time, such as where a device
is located. We set up signal shielding at a certain position to simulate a
challenging situation whereby the SUT might not be able to receive signals as
usual, i.e., introducing an indeterminacy source if the SUT moves to the
position where the shielding is located.

Regarding execution results (O3), since we used UncerTest to generate tests,
which already contain necessary assertions to evaluate the occurrence of
uncertainties and indeterminacy sources (see Section 2.3). To be independent
of UncerTest, users can define their own specifications to observe such
occurrences and generate test results after test execution accordingly. Based
on the objective information contained in the test results, information of
tests can be updated (A7). For instance, newly observed uncertainties that are
previously unknown before test execution can be added, and measurements of
uncertainty occurrences (e.g., calculating the frequency) can be updated. This
requires integrating subjective measurements (e.g., belief degree with
Uncertainty Theory in BMs) and objective measurements (e.g., frequency with
Probability Theory from the test results). In the future, we plan to
investigate different theories and methods for integrating subjective and
objective measurements, such as computing a weighted average of the frequency-
based probability and belief degree and using Bayesian approaches to update
belief degrees with frequency data.

Once the first round of execution ends, based on the remaining time budget,
users can further decide whether to: 1) execute the tests with the current
prioritization solution again, 2) generate a new solution with the updated
information of tests, or 3) terminate the test execution process.

* Test execution environment should be controllable/accessible in order to enable/evaluate indeterminacy sources.

Figure 6: Step-wise guideline of applying UncerPrio

###  4.4 Threats to Validity

Internal validity is related to the parameter settings of the selected MuOSAs,
i.e., NSGA-II, MOCell, SPEA2, and CellDE. We chose default settings [29, 12]
for these algorithms and parameter tuning may further improve their
performance. However, we follow the commonly used guidelines to choose these
default values [29, 33].

The key threat to external validity is the generalization of the results. We
used five different use cases from two different CPS subject systems for the
10 test prioritization problems for 10 different time budgets. No doubt,
further experiments with more subject systems can be performed to generalize
the results further.

The key threat to conclusion validity is about the randomness of solutions
produced by MuOSAs [34]. We dealt with this threat by repeating the
experiments 100 times [34] according to guidelines from [29]. To draw
conclusions, results were analyzed with statistical methods, such as Vargha
and Delaney statistics to calculate the effect size, Mann-Whitney U test to
determine the significance of results [35], Spearman’s rank correlation
coefficient to explore correlations of variables, and the Holm–Bonferroni
method as the posthoc analysis to control the family-wise error rate due to
multiple comparisons .

The key threat to construct validity is about the use of measures to compare
MuOSAs [34]. To avoid incomparability of the measures, we used the same
stopping criterion (25000 fitness evaluations [34]) for all algorithms to
avoid any potential bias in results. Furthermore, we use the same quality
indicators, i.e., HV and IGD to compare all MuOSAs.

##  5 Related Work

Test case prioritization orders test cases for execution in terms of their
‘importance’, which can be measured with various testing-related objectives,
such as coverage criteria (e.g., branch coverage on code) and fault detection.
In [18], Zhang et al. sorted all the candidate test cases considering not-yet-
covered code units in the previous iteration to select partial test cases for
prioritization with a greedy strategy in the context of regression testing. Lu
et al. [36] implemented a coverage-based test case prioritization approach
with ant colony optimization to maximize the statement coverage on source
code. In addition, due to the increasing use of MBT, model-related coverage
objectives are also used for test case prioritization (e.g., [37, 38, 39]).
For instance, Hierons et al. [38] applied the grid-based evolution strategy
that included several objectives, including an objective related to pairwise
coverage of features (i.e., model elements), to produce test suites and
prioritize tests in the context of MBT for software product lines. In this
paper, the main inputs for generating test cases are test models (i.e., UML
state machines), which describe expected system behaviors against which the
system shall be tested. To maximize the model coverage (i.e., the coverage of
a state machine), all the 10 proposed problems are defined withPTR (i.e.,
percentage of transition coverage with position impact) objective–maximizing
the percentage of the total number of unique transitions covered by the
prioritized test cases. To cover more uncertainties, we also defined PUU and
PUS to ensure that systems are tested with high coverage of known
uncertainties. Such coverage of uncertainties is the novelty of our work.

Another important objective is fault detection in prioritization, whose value,
e.g., can be derived based on historical test results. In [40, 41, 42], the
fault detection capability was defined as the rate of successful executions
(i.e., executions that found faults) based on the test case execution history.
Parejo et al. [39] introduced another objective, number of faults, calculated
based on fault reports of a previous version of the software under test. To
adapt this aspect for our aim (i.e., accelerating observations of
uncertainties), we defined ANOU (i.e., average normalized number of observed
uncertainties with the position impact), indicating that a solution with a
higher value of ANOU can observe more uncertainties as earlier as possible.
However, these data are not always available since existing approaches do not
typically consider such uncertainty concerns. Therefore, we used UM for a test
case and further defined another objective, AUM (i.e., average uncertainty
measure with the position impact), relying on the knowledge and expertise of
domain experts from the subjective perspective. A higher value of UM reflects
a higher belief degree of observing the occurrence of uncertainties included
in the test case. Next, a higher value of AUM might lead to a higher chance of
observing uncertainties with prioritized tests.

As the time budget for executing test cases is always limited, execution time
is one widely used objective [43, 44, 42]. For instance, Wang et al. [2]
defined a cost measure referring to the total execution time for enhancing
test case prioritization in an industrial setting. In [5], Shin et al.
proposed to schedule the test execution order considering the time budget for
CPS acceptance testing. Arrieta et al. [42] considered execution time, fault
detection, requirements coverage, etc. to solve a search-based test case
prioritization problem in the context of testing CPS product lines. Similarly,
we also take the execution time into account for all the 10 uncertainty-aware
problems and define 10 time budgets for the experiment.

Regarding uncertainty, Zhang et al. [45] implemented a search-based
uncertainty-wise approach for requirements prioritization involving the
uncertainty in cost overrun, i.e., cost overrun probability. The approach
utilized Monte Carlo Simulation to estimate the probability of cost overrun
with requirements implementation cost modeled by the triangular distribution.
In [5], uncertainty was considered a factor that impacts execution time and
the risk of hardware damage. With such consideration, execution time and risk
were expressed with probability functions as parts of objectives for
optimizing acceptance test cases. As demonstrated in the paper, a probability
function for execution time can be obtained with the Monte Carlo process, and
risk is specified by the related engineer as a single value. Our work aims to
prioritize test cases for execution by considering uncertainty. Uncertainty-
related information is initially constructed in test models by domain experts
(e.g., software testing engineers) from a subjective perspective. With such
subjective uncertainty, we defined four objectives, i.e., AUM, ANU, PUU and
PUS for prioritizing test cases from various uncertainty perspectives (e.g.,
uncertainty measurement, uncertainty coverage). In addition, with our previous
work (i.e., UncerTest), we managed to generate executable test cases based on
such models and evaluate occurrences of the unknown uncertainty (not specified
in the models) and known uncertainties (specified in the models) with test
execution. Thus, objective uncertainty information can be collected
accumulatively with test execution. We further defined ANOU (referring to the
number of observed uncertainties) for prioritizing test cases concerning
objective uncertainties.

In our previous work, we developed an uncertainty-aware test case generation
and minimization solution, named UncerTest, as we discussed in Section 2.
Built on UncerTest, we formulated the uncertainty-aware test case optimization
problem and developed a solution accordingly, as presented in this paper.
Further, we empirically evaluated the impacts of various mutation and
crossover operators for solving the UncerTest minimization problems with
selected MuOSA. There exist several existing works for uncertainty-aware
testing of CPSs [4, 5, 6, 7, 8] since testing CPSs under uncertainties and
also discovering uncertain behaviors are critical to ensure their
dependability. However, uncertainty-aware test prioritization has not been
studied in the literature. UncerPrio is the first solution that addresses the
problem.

##  6 Conclusion and Future Work

In this paper, we proposed a multi-objective uncertainty-aware and time-aware
test case prioritization approach, named UncerPrio, for Cyber-Physical Systems
(CPSs). UncerPrio considers four dedicated subjective uncertainty-related
objectives, transition coverage, and execution time. Such multi-objective
problems are then solved with the four commonly used MuOSAs (i.e., NSGA-II,
MOCell, SPEA2, and CellDE) under 10 time constraints. We evaluated the
selected MuOSAs by comparing with Random Search (RS) using five use cases from
two industrial CPSs of varying complexity. The results showed that all the
MuOSAs significantly outperformed RS. To investigate the best strategy to
prioritize tests in observing uncertainties efficiently, we analyzed the four
MuOSAs, the 10 time budgets, and the 10 uncertainty-aware prioritization
problems, and observed that the overall best performance was achieved by a
problem with combined AUM and ANU uncertainty-aware objectives (i.e., Prob.6
f(PET,PTR,AUM,ANU)) using 100% time budget (i.e., TB100), and a recommended
MuOSA for the problem with the TB100 strategy is SPEA2.

In this study, we studied the correlations between two uncertainty measures.
In the future, we plan to investigate correlations of more uncertainty
measures by defining many objective optimization problems via dedicated
empirical studies. We also plan to conduct more case studies to generalize our
findings further. Last but not least, we plan to study correlations between
uncertainties and bugs and use such correlations to guide practitioners in
better identifying and locating bugs.

## Acknowledgments

This work is supported by the Co-tester project (No. 314544), funded by the
Research Council of Norway. This work was also supported by the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation program (grant agreement No 864972).

## References

  * [1] R. Patton, _Software testing_. Pearson Education India, 2006.
  * [2] S. Wang, S. Ali, T. Yue, Ø. Bakkeli, and M. Liaaen, “Enhancing test case prioritization in an industrial setting with resource awareness and multi-objective search,” in _Proceedings of the 38th International Conference on Software Engineering Companion_ , 2016, pp. 182–191.
  * [3] R. Pietrantuono and S. Russo, “Search-based optimization for the testing resource allocation problem: Research trends and opportunities,” in _2018 IEEE/ACM 11th International Workshop on Search-Based Software Testing (SBST)_ , 2018, pp. 6–12.
  * [4] C. Wang, F. Pastore, and L. Briand, “Oracles for testing software timeliness with uncertainty,” _ACM Transactions on Software Engineering and Methodology (TOSEM)_ , vol. 28, no. 1, pp. 1–30, 2018.
  * [5] S. Y. Shin, S. Nejati, M. Sabetzadeh, L. C. Briand, and F. Zimmer, “Test case prioritization for acceptance testing of cyber physical systems: a multi-objective search-based approach,” in _Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis_ , 2018, pp. 49–60.
  * [6] C. Menghi, S. Nejati, K. Gaaloul, and L. C. Briand, “Generating automated and online test oracles for simulink models with continuous and uncertain behaviors,” in _Proceedings of the 2019 27th acm joint meeting on european software engineering conference and symposium on the foundations of software engineering_ , 2019, pp. 27–38.
  * [7] S. Y. Shin, K. Chaouch, S. Nejati, M. Sabetzadeh, L. C. Briand, and F. Zimmer, “Uncertainty-aware specification and analysis for hardware-in-the-loop testing of cyber-physical systems,” _Journal of Systems and Software_ , vol. 171, p. 110813, 2021.
  * [8] M. Camilli, A. Gargantini, P. Scandurra, and C. Trubiani, “Uncertainty-aware exploration in model-based testing,” in _2021 14th IEEE Conference on Software Testing, Verification and Validation (ICST)_. IEEE, 2021, pp. 71–81.
  * [9] M. Zhang, S. Ali, and T. Yue, “Uncertainty-wise test case generation and minimization for cyber-physical systems,” _Journal of Systems and Software_ , vol. 153, pp. 1–21, 2019.
  * [10] B. Liu, “Uncertainty theory,” in _Uncertainty theory_. Springer, 2007, pp. 205–234.
  * [11] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: Nsga-ii,” _IEEE transactions on evolutionary computation_ , vol. 6, no. 2, pp. 182–197, 2002.
  * [12] A. J. Nebro, J. J. Durillo, F. Luna, B. Dorronsoro, and E. Alba, “Design issues in a multiobjective cellular genetic algorithm,” in _International Conference on Evolutionary Multi-Criterion Optimization_. Springer, 2007, pp. 126–140.
  * [13] ——, “Mocell: A cellular genetic algorithm for multiobjective optimization,” _International Journal of Intelligent Systems_ , vol. 24, no. 7, pp. 726–746, 2009.
  * [14] E. Zitzler, M. Laumanns, and L. Thiele, “Spea2: Improving the strength pareto evolutionary algorithm,” _TIK-report_ , vol. 103, 2001.
  * [15] J. J. Durillo, A. J. Nebro, F. Luna, and E. Alba, “Solving three-objective optimization problems using a new hybrid cellular genetic algorithm,” in _International Conference on Parallel Problem Solving from Nature_. Springer, 2008, pp. 661–670.
  * [16] M. Zhang, B. Selic, S. Ali, T. Yue, O. Okariz, and R. Norgren, “Understanding uncertainty in cyber-physical systems: a conceptual model,” in _Modelling Foundations and Applications: 12th European Conference, ECMFA 2016, Held as Part of STAF 2016, Vienna, Austria, July 6-7, 2016, Proceedings 12_. Springer, 2016, pp. 247–264.
  * [17] M. Zhang, S. Ali, T. Yue, R. Norgren, and O. Okariz, “Uncertainty-wise cyber-physical system test modeling,” _Software & Systems Modeling_, vol. 18, no. 2, pp. 1379–1418, 2019.
  * [18] Q. Zhang, C. Fang, W. Sun, S. Yu, Y. Xu, and Y. Liu, “Test case prioritization using partial attention,” _Journal of Systems and Software_ , vol. 192, p. 111419, 2022.
  * [19] B. Liu, “Why is there a need for uncertainty theory,” _Journal of Uncertain Systems_ , vol. 6, no. 1, pp. 3–10, 2012.
  * [20] R. Walter, “Real and complex analysis,” 1987.
  * [21] A. J. Nebro and J. J. Durillo, “jmetal,” http://jmetal.sourceforge.net/, 2016.
  * [22] Y. Li, T. Yue, S. Ali, and L. Zhang, “Zen-reqoptimizer: a search-based approach for requirements assignment optimization,” _Empirical Software Engineering_ , vol. 22, no. 1, pp. 175–234, 2017.
  * [23] T. Yue and S. Ali, “Applying search algorithms for optimizing stakeholders familiarity and balancing workload in requirements assignment,” in _Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation_ , 2014, pp. 1295–1302.
  * [24] H. Lu, T. Yue, S. Ali, and L. Zhang, “Nonconformity resolving recommendations for product line configuration,” in _2016 IEEE International Conference on Software Testing, Verification and Validation (ICST)_. IEEE, 2016, pp. 57–68.
  * [25] S. Wang, D. Buchmann, S. Ali, A. Gotlieb, D. Pradhan, and M. Liaaen, “Multi-objective test prioritization in software product line testing: an industrial case study,” in _Proceedings of the 18th International Software Product Line Conference-Volume 1_ , 2014, pp. 32–41.
  * [26] U-Test, “Use cases - industrial case studies,” http://www.u-test.eu/use-cases/, 2017.
  * [27] S. Ali, P. Arcaini, D. Pradhan, S. A. Safdar, and T. Yue, “Quality indicators in search-based software engineering: An empirical evaluation,” _ACM Transactions on Software Engineering and Methodology (TOSEM)_ , vol. 29, no. 2, pp. 1–29, 2020.
  * [28] Y. Dodge, _The concise encyclopedia of statistics_. Springer Science & Business Media, 2008.
  * [29] A. Arcuri and L. Briand, “A practical guide for using statistical tests to assess randomized algorithms in software engineering,” in _2011 33rd International Conference on Software Engineering (ICSE)_. IEEE, 2011, pp. 1–10.
  * [30] S. Holm, “A simple sequentially rejective multiple test procedure,” _Scandinavian journal of statistics_ , pp. 65–70, 1979.
  * [31] C. Spearman, “The proof and measurement of association between two things,” _The American journal of psychology_ , vol. 100, no. 3/4, pp. 441–471, 1987.
  * [32] P. Schober, C. Boer, and L. A. Schwarte, “Correlation coefficients: appropriate use and interpretation,” _Anesthesia & Analgesia_, vol. 126, no. 5, pp. 1763–1768, 2018.
  * [33] D. J. Sheskin, _Handbook of parametric and nonparametric statistical procedures_. Chapman and Hall/CRC, 2003.
  * [34] S. Wang, S. Ali, and A. Gotlieb, “Minimizing test suites in software product lines using weight-based genetic algorithms,” in _Proceedings of the 15th annual conference on Genetic and evolutionary computation_ , 2013, pp. 1493–1500.
  * [35] T. Yue, L. C. Briand, and Y. Labiche, “Facilitating the transition from use case models to analysis models: Approach and experiments,” _ACM Transactions on Software Engineering and Methodology (TOSEM)_ , vol. 22, no. 1, pp. 1–38, 2013.
  * [36] C. Lu, J. Zhong, Y. Xue, L. Feng, and J. Zhang, “Ant colony system with sorting-based local search for coverage-based test case prioritization,” _IEEE Transactions on Reliability_ , vol. 69, no. 3, pp. 1004–1020, 2019.
  * [37] D. Marijan, M. Liaaen, A. Gotlieb, S. Sen, and C. Ieva, “Titan: Test suite optimization for highly configurable software,” in _2017 IEEE International Conference on Software Testing, Verification and Validation (ICST)_. IEEE, 2017, pp. 524–531.
  * [38] R. M. Hierons, M. Li, X. Liu, J. A. Parejo, S. Segura, and X. Yao, “Many-objective test suite generation for software product lines,” _ACM Transactions on Software Engineering and Methodology (TOSEM)_ , vol. 29, no. 1, pp. 1–46, 2020.
  * [39] J. A. Parejo, A. B. Sánchez, S. Segura, A. Ruiz-Cortés, R. E. Lopez-Herrejon, and A. Egyed, “Multi-objective test case prioritization in highly configurable systems: A case study,” _Journal of Systems and Software_ , vol. 122, pp. 287–310, 2016.
  * [40] S. Wang, S. Ali, and A. Gotlieb, “Cost-effective test suite minimization in product lines using search techniques,” _Journal of Systems and Software_ , vol. 103, pp. 370–391, 2015.
  * [41] S. Wang, S. Ali, T. Yue, Y. Li, and M. Liaaen, “A practical guide to select quality indicators for assessing pareto-based search algorithms in search-based software engineering,” in _Proceedings of the 38th International Conference on Software Engineering_ , 2016, pp. 631–642.
  * [42] A. Arrieta, S. Wang, G. Sagardui, and L. Etxeberria, “Search-based test case prioritization for simulation-based testing of cyber-physical system product lines,” _Journal of Systems and Software_ , vol. 149, pp. 1–34, 2019.
  * [43] ——, “Test case prioritization of configurable cyber-physical systems with weight-based search algorithms,” in _Proceedings of the Genetic and Evolutionary Computation Conference 2016_ , 2016, pp. 1053–1060.
  * [44] A. Arrieta, S. Wang, U. Markiegi, G. Sagardui, and L. Etxeberria, “Employing multi-objective search to enhance reactive test case generation and prioritization for testing industrial cyber-physical systems,” _IEEE Transactions on Industrial Informatics_ , vol. 14, no. 3, pp. 1055–1066, 2017.
  * [45] H. Zhang, M. Zhang, T. Yue, S. Ali, and Y. Li, “Uncertainty-wise requirements prioritization with search,” _ACM Transactions on Software Engineering and Methodology (TOSEM)_ , vol. 30, no. 1, pp. 1–54, 2020.