Coverage and Games in Model-Based Testing

Petra van den Bos

Promotor: prof.dr. F.W. Vaandrager (RU)
Co-promotor: G.J. Tretmans (RU)
Radboud University
Date: 8 October 2020
Thesis: PDF


It is challenging to construct large and complex software programs. One little mistake in a million lines of code can cause a major defect. Such defects can be detected by testing the software. Because testing is a lot of work, it is important to automate testing as much as possible. Model-based testing is a technique that only requires having a model of the behaviour of the software. An algorithm then extracts the tests from the model, which can subsequently be executed automatically.

A major challenge of model-based testing is to come up with an algorithm that generates the most powerful and versatile tests on the one hand, and minimizes the time needed for executing the tests on the other hand. This thesis investigates several algorithms that generate tests for all parts of the model. The model used in this thesis is a labeled transition system. Such a model allows describing programs that can receive input actions and produce output actions.

This thesis consist of the following contributions:

– Chapter 2 defines the concept of n-complete tests for labeled transition systems. After executing such a set of tests, either the tested program does not contain any bugs for sure, or the program is larger than the size indicated by the number n. The latter is the case, if the true behaviour of the program – if this was known – can only be modeled with a labeled transition system that has more than n states. By making n larger, the program is allowed to be larger and it is more certain that the program does not contain bugs, but also more tests need to be executed.

– Chapter 3 focuses on decreasing the size of the last part of an n-complete test from Chapter 2. The first part of the test makes sure the program is in some state. We assume that we cannot directly observe this state. The last part of an n-complete test therefore checks whether the correct state has been reached by providing input actions and receiving output actions from the program. This chapter provides an algorithm to use as few actions as possible for achieving this. Experiments on five case studies show that indeed few actions are needed with respect to the size of the model.

– Chapter 4 provides an algorithm for generating tests from labeled transitions systems with data elements or values. A value is for example a message accompanying an input or output action. Because there are many values possible, they cannot all be tried in a test. The algorithm of this chapter therefore chooses one value for every action occurring in the model. We apply the algorithm on a case study of a network protocol. Although a program is not completely tested with this approach, we show that most bugs in the network protocol are found.

– Chapter 5 views the test execution as a game between the tester and the program being tested, where the tester has the task to find a bug, while the program tries to prevent this. A translation is given between several concepts from model-based testing and game theory. A move of the tester is providing an input action to the program, and a move of the program is producing an output action. Furthermore, a strategy of the tester corresponds to a test. This chapter connects the worlds of game theory and model-based testing, such that concepts and algorithms from one world can be used in the other world.

– Chapter 6 searches for the easiest way to bring a program in a certain state: this is the first part of an n-complete test from Chapter 2. This is done by analysing a joker game. During test execution, the tester usually is not in full control of the program he is testing: the program may produce an output action, while the tester could have wanted to first provide the program an input action, or would have liked receiving another output action, for reaching the desired state. In a joker game, the tester can play a joker to accomplish the desired action. A strategy that uses the minimum number of jokers can subsequently be translated to a test. In such a test, the number of times the program can hinder the tester is minimized, such that test execution often will be successful.