(B) Mutating Data Structure Specifications for Robustness Testing

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.