Page 43 - SMILESENG

Intl. Summer School on Search- and Machine Learning-based Software Engineering
Generating Complex Metamorphic Relations for Cyber-Physical Systems with Genetic Programming
Jon Ayerdi∗, Valerio Terragni†, Aitor Arrieta∗, Paolo Tonella‡ and Maite Arratibel §
Mondragon Unibertsitatea∗, University of Auckland †, Universita` della Svizzera italiana (USI) ‡, Orona § ∗{jayerdi,aarrieta}@mondragon.edu, †v.terragni@auckland.ac.nz, ‡paolo.tonella@usi.ch, §marratibel@orona-group.com
Abstract—One of the major challenges of testing complex Cyber-Physical Systems (CPS) is determining whether the be- havior of the system on a particular test execution is correct or not, the so called oracle problem. Metamorphic testing is an alternative testing technique which can alleviate this problem by reasoning over relations between the inputs and outputs of multi- ple test executions, which are known as Metamorphic Relations (MRs). However, defining effective MRs is a complicated task which is error-prone and often requires domain-expertise and knowledge about the system under test. In this paper, we present an approach for the automatic generation of MRs based on genetic programming. Our current implementation is specifically tailored for generating MRs for performance testing CPSs, and is based on previous work on the evolutionary generation of program assertions. Furthermore, we propose an extension based on our experience with this approach. We also present the results obtained with an industrial case study in previous iterations of this work, which have been promising thus far.
I. INTRODUCTION
Cyber-Physical Systems (CPSs) are complex heterogeneous systems that integrate physical and software components [1]. The complexity of CPSs and their interactions with their environment makes the definition of test oracles especially challenging for them [2]. This inability to determine whether these system’s behaviour is correct or not is known as the oracle problem [3].
We present an automated approach to mitigate the oracle problem in an industrial case study from ORONA [4], one of the leading elevator companies in Europe. We employ oracles based on metamorphic testing, and we automate the definition of these oracles by using genetic programming and samples of correct and incorrect executions [5]. Based on our experience and previous results, we also describe the future research avenues to improve the approach and make it more applicable.
II. BACKGROUND
Metamorphic Testing aims to detect system failures by defining necessary relations between the inputs and outputs of two or more test executions, the so called Metamorphic Relations (MRs) [6]. Typically, a single source test case ⟨Is , Os ⟩ is executed, and then a follow-up test case ⟨If , Of ⟩ is generated such that Is and If satisfy the input relation.
An example MR derived for multi-elevator installations [7] is that increasing the number of available elevators (E) should reduce the average waiting time of the passengers (AW T ),
since the system will have more resources to meet the trans- portation demands. This MR can be expressed as:
′
where Ef = Es ∪ E′ is the input relation, which defines how the follow-up test inputs relate with the source test inputs, and AW Ts ≥ AW Tf is the output relation, i.e., the assertion that defines whether the system’s behaviour is correct.
III. APPROACH
Manually defining MRs is, unfortunately, a difficult and error-prone task which requires expertise with the system under test. Because of this, we proposed GASSERTMRS [5], a tool for automatically generating MRs by using samples of correct and incorrect system behaviours.
GASSERTMRS is built based on GASSERT [8], a technique to automatically generate or improve assertion oracles. GAS- SERTMRS explores the space of candidate MRs with a co- evolutionary algorithm introduced by GASSERT, which for- mulates the oracle improvement problem as a multi-objective optimization problem with three objectives of descending priorities: (1) minimizing the number of false positives, (2) minimizing the number of false negatives, and (3) minimizing the complexity of the generated MRs. GASSERTMRS evolves two populations of MRs in parallel: One which favors fewer false positives first, and another which favors fewer false negatives first. The remaining objectives are used to break ties, with MR complexity being the lowest priority objective in all cases. Both populations share genetic material by periodically exchanging their best individuals.
GASSERTMRS employs user-defined input transformations, and generates output relations of the following form:
Of [operator]F(Os,Is,If)
where Os and Of are the values for the output variable, [operator] is a relational operator, Is and If are the input variable values, and F is the expression generated by GAS- SERTMRS. We generate MRs following this specific template in order to improve the readability of the generated MRs and greatly reduce the search-space for the algorithm.
The current implementation of GASSERTMRS supports only boolean and numeric variables, constants and operators, which can be limiting. For complex types, the variable can often be decomposed or serialized into boolean and numeric variables. For instance, an elevator passenger call (c) can be
31
Ef = Es ∪ E ⇒ AW Ts ≥ AW Tf