Mutating Data Structure Specifications for Robustness Testing

Modern software systems are typically networked and reuse existing software components. Assuring that a system correctly validates data received from some untrusted source is of particular importance. In this context, test engineers often employ robustness testing techniques, where negative test cases [1] play a prominent role [2]. 

A particular challenge in robustness testing are pointer parameters, which refer to dynamic data structures such as linked lists or binary trees. Safe programming practices demand that pointer parameters are checked for validity, which includes verifying that they point to a valid instance of the expected data structure. 

While recent work in this context [3] employs mutation testing at test-case level [4], our hypothesis is that applying it at the level of data structure specification will lead to more representative negative test cases and, thus, a smaller test suite. To do so, a data structure's specification, that describe the expected structure, e.g. as a Prolog predicate, is mutated and subsequently used for generating negative test cases that can be applied to the input validation method under test.

This thesis shall
(i) review works on specification mutation, particularly in the context of dynamic data structures, to derive relevant mutation operators,
(ii) devise a script that receives a Prolog predicate characterizing a dynamic data structure as input, applies mutation operators, and then generates negative test cases based on the mutated specifcation, and
(iii) evaluate the generated negative test cases by measuring code coverage of input validation methods for common dynamic data structures.

The ideal student for this thesis topic has a good understanding of graph-based structures and is, preferably, familiar with the Prolog programming language.
Supervisors Kerstin Jacob & Jan H. Boockmann
Suitable for
Literature [1] Myers, G. J.; Sandler, C. & Badgett, T. The art of software testing (3. ed.). Wiley, 2021. url:
[2] Beizer, B. Black-box testing - techniques for functional testing of software and systems. Wiley, 1995.
[3] Jan H. Boockmann, K. J. & Lüttgen, G. Hanus, M. & Prott, K.-O. (Eds.). Towards Robustness Testing of Functions Operating on Dynamic Data Structures. KPS 2021: 21. Kolloquium Programmiersprachen und Grundlagen der Programmierung, 2021, 5-19. url: (last accessed: 20 Jan 2022).
[4] Jia, Y. & Harman, M. An Analysis and Survey of the Development of Mutation Testing. IEEE Trans. Software Eng., 2011, vol. 37, no. 5, pp. 649-678. url:
Zuletzt geändert: Donnerstag, 20. Januar 2022, 16:38