Dissertationsthema Stephan Weißleder
From GRK-Wiki
Contents |
Model-Based Test Case Generation from UML and OCL
Introduction
Testing is the primary means to detect faults in a system under test (SUT), e.g. hardware or software. Modeling languages like the Unified Modeling Language (UML) provide an abstract layer to design tests on a semi-formal foundation. In model-based testing, each test run validates if the SUT corresponds to certain reference models. This is often evaluated via expressions of the Object Constraint Language (OCL). Furthermore, models can also be used to generate test input sequences, to derive the expected behavior of the SUT, or both. This is advantageous compared to conventional test suite generation because the automation increases the efficiency of the test generation process. Commercial tools are available which automatically generate test sets based on models (e.g. Rhapsody ATG, Leirios Test Designer).
In trustworthy systems, testing is an important technique to ensure a certain quality level. The quality of test suites is often measured with coverage criteria (e.g. MC/DC, All-Transitions, Multi-Dimensional). Although there is no proof of their effectiveness, there are many widely approved coverage criteria. Each of them is focused on certain aspects of the specification or the SUT. Whereas most coverage criteria have been defined and investigated in the area of code-based test generation, we focus on coverage of the model. We investigate coverage criteria that, e.g., focus on conditions or partition boundaries of the model. We generate test sets which satisfy such coverage criteria automatically and introduce a prototype that realizes our approach based on UML and OCL.
We argue that the support of model-based testing by existing tools could be improved. For instance, Rhapsody ATG is restricted to the language C++ and the Leirios Test Designer uses OCL but is restricted to a subset of OCL in postconditions. Furthermore, we argue that the automatic derivation of boundary-based coverage criteria could also be improved. For instance, AETG depends on user-defined partition boundaries instead of deriving them from the model. Therefore, the boundary selection is error-prone and there is a high probability that the test effectiveness is low. In contrast to manual selection of input value boundaries, we present an approach to derive them automatically from OCL expressions of UML state machines and UML class diagrams. We statically analyze the interdependence of OCL expressions within the system model and transform the model into a transition tree and investigate the tree's paths. The corresponding test suite is focused on detecting errors that result from differences between constraints in the model and constraints in the system under test.
Test Generation from UML and OCL, Results, Comparison to other Tools
We implemented our approach in an Eclipse-based tool called ParTeG (see http://parteg.sourceforge.net ). This tool checks all paths from the initial state of the UML state machine until a loop of transitions is reached. Every time the tool encounters, e.g., a guard condition, it searches the path backwards to find a postcondition that affects the outcome of this guard condition. The postconditions describe, e.g., the effect of input parameters on attribute values. This allows to create a connection between the values of test input parameters and the control flow within the state machine. The constraints on test input parameters are interpreted as equivalence classes and the concrete values are selected close to the corresponding boundaries.
We compared our prototype implementation to already existing commercial tools. In this context, we used mutation analysis with a subset of the "sufficient mutation operators" (see Offutt). Since our approach is focused on the deduction of test input data partitions, the test suites generated by ParTeG reached a higher number of killed mutants than Rhapsody ATG and Leirios Test Designer.
Furthermore, most existing test generation tools aim at the satisfaction of a fixed set of certain coverage criteria. Since each coverage criterion has its eligibility for a certain application fields and required safety levels, it would be desirable to let the user choose the coverage criterion to satisfy. ParTeG allows the user to choose from a set of coverage criteria. This allows its application in a broader set of environments.
Future Work, Discussion
Our current implementation starts at the initial state of the state machine to derive test cases and builds up a corresponding tree of test traces. This algorithm is reasonable for coverage criteria like All-One-Loop-Paths. For criteria like MC/DC, however, other approaches are necessary. We will add an algorithm that works on the control-flow graph of the state machine using several test goals to derive test cases. Based on the coverage criteria to satisfy, we define certain test goals like a set of transitions for transition coverage or a set of assignments of a condition's attribut values for MC/DC. Following that, we iterate through all test goals and apply our approach of deducing test input values to test generation algorithms like presented by Offutt or Sokenou. Furthermore, the representation in an independent graph structure allows to perform static analysis and the creation of test cases independently of the used input formalism. Given a transformation from another modeling formalism, we can reuse the whole implementation of test generation, e.g., for protocol state machines or activity diagrams.
The emphasis placed on test input boundaries enables ParTeG to combine several coverage criteria like Multi-Dimension and MC/DC. We will also investigate further combinations of coverage criteria with regard to their fault detection ability. To our knowledge, ParTeG is the first tool that generates test cases via equivalence classes for test input parameters generated from UML and OCL.
