Simulation-based Metamorphic Testing of Cyber-Physical Systems

Abstract

Cyber-Physical Systems (CPSs) are heterogeneous systems in which software components and physical processes interact with each other. These systems have strict requirements that are difficult to verify, resulting in very costly verification processes which often lack automation. As CPSs and their requirements become more complex, development practices that still rely on manual intervention struggle to scale up. As such, there is a need to identify the fundamental problems that currently prevent the automation of those processes, and find solutions to them. One such problem is the inability to accurately define the expected behaviour of the systems for their verification, namely, the test oracle problem. Due to factors such as ambiguous requirements or non-determinism, testing activities for CPSs often involve human oracles, since automated oracles cannot be implemented without defining specific properties to verify. Metamorphic Testing (MT) is an alternative verification approach which can be used to define test oracles. Instead of focusing on a single system execution, MT defines properties that compare the behaviours from two or more system executions with known relationships between their inputs and outputs, the so-called Metamorphic Relations (MRs). This thesis aims to advance the current practice on testing CPSs by proposing methods that alleviate the test oracle problem by using MT. First, we present a general CPS DevOps architecture which will enable the automation of all the development tasks, focusing on the verification components where the MT techniques will be implemented. Second, we propose methods for identifying MRs for CPSs. On the one hand, we propose a pattern for performance-based MRs, which can be used to instantiate MRs for specific CPSs more easily. On the other hand, we implement a fully-automated approach for generating MRs for a given system based on samples of correct and incorrect system behaviours. We implement two prototypes of this technique. The first prototype enables automatic performance MR generation for CPSs, given user-provided test execution pairs. The second prototype demonstrates the full automation of a generic whole MR generation process. Finally, we propose an optimization approach for MT, metamorphic test selection. The goal of this approach is to maximize the cost-effectiveness of MT by reducing the number of tests that need to be executed, which is important due to the high cost of executing CPSs.

Sistema ziber-fisikoak (CPSak) software-osagaiek eta prozesu fisikoek elkarri eragiten dioten sistemak dira. Sistema hauek balidatzeko zailak diren propietateak izan ohi dituzte, eta ondorioz sarritan automatizaziorik ez duten balidazio prozesuak izaten dituzte. CPSak eta heuren propietateak konplexuagoak bihurtzen diren heinean, interbentzio manualetan oinarritzen diren praktikek eskalatzeko harazoak izaten dituzte. Hori dela eta, prozesu horien automatizazioa eragozten duten oinarrizko arazoak identifikatu beharra dago, eta horiei irtenbideak bilatu. Arazo horietako bat sistemaren balidaziorako espero den portaera zehaztasunez definitzeko ezintasuna da, hau da, orakuluaren arazoa. Baldintza anbiguoak eta ez-determinismoa bezalako faktoreak direla eta, CPSetarako balidazioek askotan orakulu manualak izaten dituzte, orakulu automatizatuak ezin baitira inplementatu balidatzeko propietate zehatzik gabe. Metamorphic Testing (MT) orakuluak definitzeko erabil daitekeen balidazio teknika alternatibo bat da. Sistemaren exekuzio bakarra erabili beharrean, MTek bi exekuzio edo gehiagoren portaerak alderatzen dituzten propietateak definitzen ditu, haien sarrera eta irteeren arteko erlazio ezagunak dituztenak, erlazio metamorfikoak (MRs) deiturikoak. Tesi honen helburua CPSak balidatzeko egungo jardunbideak hobetzea da, MT teknika erabiliz orakuluaren arazoari irtenbidea hematen dioten metodoak proposatuz. Lehenik eta behin, sistemaren garapena automatizatzea ahalbidetuko duen CPS DevOps arkitektura orokor bat aurkezten dugu, MT teknikak implementatuko dituzten balidazio osagaietan zentratuz. Bigarrenik, CPSetarako MRak identifikatzeko metodoak proposatzen ditugu. Alde batetik, errendimendu metriketan oinarritutako MRetarako txantiloi bat proposatzen dugu, CPSetarako MRak errazago instantziatzeko erabil daitekeena. Bestalde, sistema baterako MRak sortzeko teknika automatizatu bat proposatzen dugu, sistemaren jokabide zuzen eta okerren laginetan oinarrituta. Teknika honen bi prototipo inplementatzen ditugu. Lehenengo prototipoak errendimendu metriketan oinarritutako MRen sorkuntza ahalbidetzen du CPSetarako, erabiltzaileek emandako test bikoteak erabiliz. Bigarren prototipoak MRak sortzeko prozesuaren automatizazio osoa demostratzen du. Azkenik, MTrako optimizazio bat proposatzen dugu, test metamorfikoen selekzioa. Teknika honen helburua exekutatu behar diren test kopurua murriztuz MTen eraginkortasuna handitzea da, eta hori garrantzitsua da CPSak exekutatzeko kostu handia dela eta.

Los sistemas cyber-físicos (CPSs) son sistemas heterogéneos en los que componentes de software y procesos físicos interactuan entre ellos. Estos sistemas tienen requisitos estrictos que son difíciles de verificar, lo que resulta en costosos procesos de verificación que no suelen estar automatizados. A medida que los CPSs y sus requisitos se vuelven más complejos, las prácticas del proceso de desarrollo que dependen de la intervención manual escalan cada vez peor. Debido a esto, hay una necesidad de identificar los problemas fundamentales que bloquean la automatización de estos procesos, así como de encontrar soluciones a estos problemas. Uno de estos problemas es la dificultad de definir el comportamiento esperado de los sistemas durante su verificación, lo que se conoce como el problema del oráculo. Debido a factores como los requisitos ambíguos o el no determinismo de los sistemas, las actividades de testeo para CPSs suelen involucrar oráculos humanos, puesto que la implementación de oráculos de testeo automatizados requiere la definición de propiedades específicas a verificar. Metamorphic Testing (MT) es una técnica de verificación alternativa que permite definir oráculos de testeo. El lugar de centrarse en ejecuciones individuales del sistema, MT permite definir propiedades basadas en múltiples ejecuciones con relaciones específicas entre las entradas y salidas del sistema, las llamadas relaciones metamórficas (MRs). Esta tesis tiene como objetivo avanzar en la práctica actual del testeo de sistemas cyber-físicos mediante la propuesta de métodos para aliviar el problema del oráculo de testeo mediante el uso de MT. En primer lugar, presentamos una arquitectura DevOps para CPSs que permitirá automatizar todas las tareas de desarrollo del sistema, centrandonos en los componentes de verificación en los que se integrarán las técnicas de MT. En segundo lugar, proponemos métodos para identificar MRs en CPSs. Por una parte, proponemos un patrón general para MRs basadas en métricas de rendimiento, el cual puede ayudar a instanciar MRs para CPSs concretos de forma más fácil. Por otra parte, implementamos una técnica completamente automática para generar MRs para cualquier sistema a partir de ejecuciones que demuestren su comportamiento correcto e incorrecto. Desarrollamos dos prototipos de esta técnica. El primer prototipo es capaz de generar MRs basadas en métricas de rendimiento de forma automática a partir de parejas de ejecuciones del sistema proporcionadas por los usuarios. El segundo prototipo demuestra la automatización completa del proceso de generación de MRs genéricas. Finalmente, proponemos una técnica de optimización para MT que consiste en la selección de testeos metamórficos. La finalidad de esta técnica es maximizar la eficiencia de MT mediante la reducción del número de testeos que tienen que ser ejecutados, lo cual es muy relevante dado el alto coste de ejecutar CPSs.