  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, complex
testing infrastructure setup, and the inherent uncertainties in their operating
environment. Devising uncertainty-aware testing solutions supported with test
optimization techniques 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: uncertainty measurement
(AUM), uncertainty space (PUS), the number of uncertainties (ANU), and
uncertainty coverage (PUU). 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
(execution cost, PET) to be minimized and one effective measure (model
coverage, PTR) to be maximized. 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.
