Model-Based Metamorphic Testing of Autonomous Robotic Systems

Testing non-stationary systems, particularly autonomous systems, is inherently challenging due to the lack of test oracle. Metamorphic testing was introduced by Chen as a possible conceptual solution to test systems when a test oracle is not available. The behavioral properties of the system under test (SUT) are defined in the course of its state space exploration and specified using generic relations known as metamorphic relations (MRs) between different sets of inputs and their expected outputs. Objective is to develop methods for incremental construction of efficiently (run-time) decidable constraint sets that specifies SUT MR-based on its observable behaviors.

Research field:	Information and communication technology
Supervisors:	Prof. Dr. Jüri Vain Dr. Gert Kanter
Availability:	This position is available.
Offered by:	School of Information Technologies Department of Software Science
Application deadline:	Applications are accepted between June 01, 2022 00:00 and June 30, 2022 23:59 (Europe/Zurich)

Autonomous systems such as self-driving cars, heterogeneous robotic machines in agriculture, smart agents implementing networked sevices and other exhibit complex non-stationary emerging behavior that depends on numerous system external and internal factors. Testing systems has been traditionally made using requirements specification  where test pass/fail is decided based on the satisfaction of (Tretman’s IOCO, RTIOCO etc) conformance relations  between expected and real behavior of the system under test. In model based testing the expected behavior (called test oracle) is specified using some modelling formalism.

Testing non-stationary systems, particularly autonomous systems, is inherently more complicated due to the lack of test oracle. Metamorphic testing was introduced by Chen et al. [1] as a possible conceptual solution to test systems when a test oracle is not available. The behavioral or functional properties of the system are defined in the course of system state space exploration and specified using generic relations known as metamorphic relations (MRs) between different sets of inputs and their expected outputs. Metamorphic testing is performed as a step-by-step process as follows [2]: (i) Postulate an initial hypothesis on metamorphic relations based on known system inputs an observable outputs; (ii) Generate a source test case passing the seed input to the system using a traditional test generation method and execute them; (iii) Generate follow-up test cases by morphing inputs of the source test case and test the validity of earlier formulated metamorphic relations; (iv) Compare the results of source and follow-up test cases against the metamorphic relations to decide the verdict of the tests.

Efficient and theoretically motivated guiding of morphing steps of test inputs and drawing conclusions about the metamorphic relation is still subject of active research though in some special cases the empirical methods have been suggested [3].

Objective

• Develop of methods for incremental construction of efficiently (run-time) decidable constraint sets that specifies SUT metamorphic relation based on its observable behaviors.
• Providing a  metod for generating new test cases for MR refinement based on earlier test runs and known MR.
• Showing under which assumptions the problems stated above are decidable;
• Implementing the feasible methods in the testing framework TestIt [4]
• Validating the feasiblity of the methods based on benchmarks and a real case-study, that is  testing emerging behavior of an agriculture robot swarm (simulation available at Maanmittauslaitos, Finland).

Methods

• Applying machine learning methods to guide the MR hypothesis formation and checking by execution of test cases.
• Proving consistency of the MR constraint sets by applying SAT-solving and model checking.
• Demonstrating methods scalability using benchmark examples and simulated case studies (autonomous swarm of heterogeneous robots for grop monitoring).

 

Novelty

• Up to now, the metamorphic testing has been developed predominantly in purely empirical setting, i.e. metamorphic relations as well as morphing transformations have been described informally and implemented only for specific cases.
• This work aims at generalizing the MT methods by addressing them under constraint learning, programming and solving theoretical framework.
• This  allows providing general decidability results and  define the scope of problems for which the MT is still feasible.
• Extending the current MT tool support by implementing novel theoretical results in the testing tool set TestIt.

 

References

[1] Tsong Y Chen et al. Metamorphic testing: a new approach for generating next test cases. arXiv preprint arXiv:2002.12543, 2020.

[2] Huai Liu et al. A new method for constructing metamorphic relations. In 2012 12th International Conference on Quality Software, pages 59–68. IEEE, 2012.

[3] Sergio Segura et al. A survey on metamorphic testing. IEEE Transactions on software engineering, 42(9):805–824, 2016.

[4] Kanter, G., & Vain, J. (2020). Model-based testing of autonomous robots using TestIt. Journal of Reliable Intelligent Environments, 6, 15-30.

 

Responsibilities and (foreseen) tasks

• Develop of methods for incremental construction of efficiently (run-time) decidable constraint sets that specifies SUT metamorphic relation based on its observable behaviors.
• Providing a  method for generating new test cases for MR refinement based on earlier test runs and known MR.
• Showing under which assumptions the problems stated above are decidable;
• Implementing the feasible methods in the testing framework TestIt
• Validating the feasibility of the methods based on benchmarks and a real case-study, that is  testing emerging behavior of an agriculture robot swarm (simulation available at Maanmittauslaitos, Finland).
• Contribute to the organization of research and workshops where project findings are presented

 

Applicants should fulfil the following requirements:

• a master’s degree in computer science or applied mathematics
• a clear interest in the topic of the position
• excellent command of English
• strong and demonstrable writing and analytical skills
• capacity to work both as an independent researcher and as part of an international team
• capacity and willingness to provide assistance in organizational tasks relevant to the project

 

The following experience is beneficial:

• Knowledge of programming theory and computer science
• Programming skills (C++, Python)
• Experience in robotics or embedded software development
• System modelling (UPPAAL tool)

 

The candidate should submit a research plan for the topic, including the overall research strategy. The candidate can expand on the listed research questions and tasks, and propose theoretical insights to be used.

 

We offer:

• 4-year PhD position in the largest department in one of the largest, most internationalized and leading computer science research centers in Estonia with a large portfolio of ongoing pan-European projects
• The chance to do high-level research in a renowned computer science and AI laboratory in Estonia
• Opportunities for conference visits, research stays and networking with globally leading universities and research  centers in the field of computer science