Technology

The MoMuT family of tools belongs to the so-called black-box testing tools as it derives test cases from models of the system under test (SUT) and does not rely on, e.g., the source code of the SUT. In difference to most other test case generation tools, MoMuT’s main focus is on fault-based testing: the tools generate test cases that are guaranteed to detect models that contain certain user-selectable, seeded faults. Research has shown that this methodology is powerful and subsumes other coverage criteria, like condition coverage (see [1]). In MoMuT’s case these faulty models are called mutants, hence the test case generation strategy is known as “Mutation-driven Test Case Generation” or “Model-based Mutation Testing”.

Key Benefits of MoMuT’s Approach

  1. Automated Test Design With Guaranteed Defect Coverage
  2. Test Suite Analysis
  3. Test Suite Extension
  4. Model-based Fault Localization

Automated Test Design With Guaranteed Defect Coverage

 In the following we give a quick introduction to fault-based test case generation as implemented in MoMuT.

Mutation Based Test-Case Generation - Principle

Mutation driven test case generation – Principle

The figure to the left shows the principle idea MoMuT is following when creating test cases with the mutation strategy. First, an engineer creates a test model. In case of MoMuT::UML this is a UML model of the input/output behavior of the SUT to be tested.  Second, in order to generate test cases, MoMuT will apply mutation operators to the model and derive a number of mutated (“faulty”) models. Third, MoMuT takes the original and one mutated model at a time and searches for a discriminating sequence of inputs/outputs (controllables/observables) that will reveal a difference in behavior between the original and the faulty model. Once such a sequence is found, it is turned into a test case in a final step. Notice that the different MoMuT tools will use much more optimized workflows in reality. Most of the algorithms used by MoMuT have been published in scientific conferences and can be found in the related proceedings (see publications).

Although the basic idea of mutation-based test case generation is quite simple, there is some additional detail to observe. Most importantly we want to mention that MoMuT is looking for a difference in the observable behavior of the mutant and the original when creating test cases (see [2]). Some difference in the internal state alone is not good enough in the black-box testing setting. MoMuT also produces positive tests, which means that the fail verdict is implicit: whenever there is some observation from the system under test that is not foreseen by the test case, then the test fails. If the model is non-deterministic and the selected test case generation back end supports the generation of adaptive test cases, the tests might not be linear sequences but graphs. Apart from the normal verdicts “pass” and “fail”, MoMuT also knows about “inconclusive”, which means that the observed behavior is correct but the test goal (getting to the mutation) could not be reached. Finally, we want to say that the mutation-based approach lends itself very nicely to the completion of existing test suites: given a set of existing tests MoMuT will run a kill-check on the model mutants and generate new test cases for the surviving ones.

Test Suite Analysis

The fault-based approach also lets MoMuT readily analyse existing test suites to determine the fault coverage. The result of this analysis usually is a set of mutants that the existing tests do not detect and a mapping of existing tests to mutants they detect. Graphically this can be represented like in the following image, where each column represents one mutant and each row a test case (each pixel represents a test). Each of the black columns in the image stands for one mutant that the existing test cases could not detect.

killcheck

Graphical result of the mutation analysis of two test suites. Color codes are as follows: Red … Mutant Detected By Test, Green … Mutant Detected By Other Test, Black … Mutant Not Detected, Blue … Mutant Not Responding/Stuck in Loop

Besides detecting which mutants survived, the result of this analysis can also be used to prioritize the runs of test-cases within a test-suite. For example, a minimal set of test cases detecting all mutants can be identified and run before any other test.

Test Suite Extension

Given the result of MoMuT’s analysis of an existing test suite, MoMuT can be used in the next step to try and generate additional test cases that will detect the previously undetected mutants.

Model-based Fault Localization

Given a SUT and a long test case that is failing, model-based fault localization may help in debugging as it can (1) look for mutants that show the same faulty behavior, and (2) generate shorter test cases that try to trigger the same fault. For a more detailed account of this process, we refer the interested reader to [3].

References

[1] J. A. Offutt and J. M. Voas, “Subsumption of condition coverage techniques by mutation testing,” Dept. of Information and Software Systems Eng., George Mason Univ. 1996.
[Bibtex]
@TECHREPORT{Offutt96Subsumption,
author = {A. Jefferson Offutt and Jeffrey M. Voas},
title = {Subsumption of condition coverage techniques by mutation testing},
institution = {Dept. of Information and Software Systems Eng., George Mason Univ.},
year = {1996}
}
[2] J. Tretmans, “Test generation with inputs, outputs and repetitive quiescence,” Software – concepts and tools, vol. 17, iss. 3, pp. 103-120, 1996.
[Bibtex]
@article{Tretmans96Ioco,
author = {Jan Tretmans},
title = {Test Generation with Inputs, Outputs and Repetitive Quiescence},
journal = {Software - Concepts and Tools},
year = {1996},
volume = {17},
pages = {103-120},
number = {3}
}
[3] [doi] B. K. Aichernig, K. Hörmaier, and F. Lorber, “Debugging with timed automata mutations,” in Computer safety, reliability, and security, A. Bondavalli and F. Di Giandomenico, Eds., Springer International Publishing, 2014, vol. 8666, pp. 49-64.
[Bibtex]
@incollection{Aichernig14Debugging,
year={2014},
isbn={978-3-319-10505-5},
booktitle={Computer Safety, Reliability, and Security},
volume={8666},
series={Lecture Notes in Computer Science},
editor={Bondavalli, Andrea and Di Giandomenico, Felicita},
doi={10.1007/978-3-319-10506-2_4},
title={Debugging with Timed Automata Mutations},
url={http://dx.doi.org/10.1007/978-3-319-10506-2_4},
publisher={Springer International Publishing},
keywords={Timed automata; debugging; model-based mutation debugging; mutation testing; model-based testing; language inclusion; mutation operators},
author={Aichernig, Bernhard K. and H{\"o}rmaier, Klaus and Lorber, Florian},
pages={49-64},
language={English}
}