Testing CPS with Design Assumptions-Based Metamorphic Relations and Genetic Programming

Cyber-Physical Systems (CPSs) software is used to enforce desired behaviours
on physical systems. To test the interaction between the CPS software and the
system's physics, engineers provide traces of desired physical states and
observe traces of the actual physical states. CPS requirements describe how
closely the actual physical traces should track the desired traces. These
requirements are typically defined for specific, simple input traces such as
step or ramp sequences, and thus are not applicable to arbitrary inputs. This
limits the availability of oracles for CPSs. Our recent work proposes an
approach to testing CPS using control-theoretical design assumptions instead of
requirements. This approach circumvents the oracle problem by leveraging the
control-theoretical guarantees that are provided when the design assumptions
are satisfied. To address the test case generation and oracle problems,
researchers have proposed metamorphic testing, which is based on the study of
relations across tests, i.e., metamorphic relations (MRs). In this work, we
define MRs based on the design assumptions and explore combinations of these
MRs using genetic programming to generate CPS test cases. This enables the
generation of CPS input traces with potentially arbitrary shapes, together with
associated expected output traces. We use the deviation from the expected
output traces to guide the generation of input traces that falsify the MRs. Our
experiment results show that the MR-falsification provides engineers with new
information, helping them identify passed and failed test cases. Furthermore,
we show that the generation of traces that falsify the MRs is a non-trivial
problem, which is successfully addressed by our genetic search.