Seed Model Synthesis for Testing Model-Based Mutation Operators

Abstract

In software engineering, mutation consists in injecting small changes in artefacts – like models, programs, or data – for purposes like (mutation) testing, test data generation, and all sorts of search-based methods. These activities normally require the definition of sets of mutation operators, which are often built ad-hoc because there is currently poor support for their development and testing.

To improve this situation, in previous work we proposed a model-based approach to create and execute mutation operators. Our proposal represents the artefacts to be mutated as models and provides a domain-specific language called Wodel to define the mutation operators. However, testing the operators is cumbersome, since it requires the manual creation of input seed models. To facilitate this testing process, we propose a method – based on model finding – for the automated synthesis of test models that exercise the defined mutation operators. We provide tool support for our proposal, and illustrate its usage by defining mutation operators for BPMN.

1 Introduction

Mutation consists in the selective introduction of modifications into sets of seed artefacts, like models, programs or data. Mutation is at the core of many techniques in software engineering, like mutation testing (where programs are mutated with faults to evaluate the quality of a test suite)  [5, 14], test data generation (like in mutation-based fuzzing, which introduces small changes to existing test inputs)  [26], and search-based software engineering (which applies metaheuristic search techniques to software engineering problems, where candidate solutions are combined and mutated)  [15]. Mutation has also been applied for other purposes, like the automatic generation of exercises and quizzes  [9] or testing distributed applications in simulated environments  [3].

Mutation-based methods require the creation of mutation operators able to change the target artefacts in pertinent ways. For example, for mutation testing, operators need to emulate common faults made by competent developers. Such operators are typically defined over the abstract syntax tree of the program, which makes them difficult to test since the input data of the operators are programs. Moreover, operators are often defined ad-hoc using general programming languages not designed for mutating artefacts, like Java  [19] or C  [18], which is costly and error-prone.

To improve this situation, we propose an approach to facilitate the creation and testing of mutation operators. It is model-based to enable its application to heterogeneous artefacts (programs, models, data). This means that the artefacts to mutate are represented as models conforming to a meta-model, for which we rely on injection (artefact-to-model) and extraction (model-to-artefact) transformations. Our solution includes a domain-specific language (DSL) called Wodel   [8, 9] specially tailored to design mutation operators applicable over models. To help in the validation of the designed operators, we offer facilities for synthesizing models over which the operators can be tested. Such models are ensured to provide full statement coverage of the mutation program.

Our method is supported by the Wodel tool  [10]. While the DSL Wodel was introduced in  [8, 9], in this paper we focus on the facility for seed model synthesis, based on constraint solving and model finding  [20].

The rest of this paper is organized as follows. Section 2 introduces a running example in the area of process modelling. Then, Section 3 describes the Wodel DSL. Section 4 explains our methods to synthesize models for testing mutation operators, and Sect. 5 describes our current tool support. Finally, Sect. 6 reviews related work, and Sect. 7 concludes the paper.

2 Running Example: Mutation for Process Models

A number of research works have applied mutation to workflow languages for different purposes, like evaluating the quality of test cases (as in  [7] for WS-BPEL), optimising process models (as in  [16] for BPMN), or for process mining using a genetic approach (as in  [6] for process trees or  [22] for Petri nets). As an illustration, in this paper, we are defining a set of mutation operators for the Business Process Model and Notation (BPMN)¹.

Figure 1 shows part of a simplified BPMN meta-model taken from an editor built by a third-party². A process defines a set of FlowObjects, which can be either Activities (i.e., a work to be done), Events (to denote that something happens, such as the start or end of the process), or Gateways (to fork or merge several paths). Depending on the kind of gateway, the execution of its outgoing paths can be in parallel (AND), inclusive (OR, one or more paths are executed), or exclusive (XOR, only a path is executed). The OCL invariant inv2 ensures that gateways always have input and output paths. Finally, flow objects can be connected through ConnectingObjects to specify the execution flow (Sequence), send messages (Message), or associate artefacts to flow objects (Association). The OCL invariant inv1 ensures that start events have no input flows, end events have no output flows, and flow objects are not connected to themselves. To better illustrate model synthesis in Sect. 4, we have restricted processes to have between 1 and 10 elements, as cardinality of reference BusinessProcess.elements indicates.

Fig. 1.

Simplified BPMN meta-model.

Figure 2 shows a simple BPMN model in concrete syntax. It describes the process to satisfy someone who is hungry. The process starts when a person becomes hungry. The first activity is to buy food, followed by cooking the food. Then, when the meal is ready, the person eats it, and this concludes the process.

Fig. 2.

An example BPMN model (using the standard concrete syntax).

In the next section, we introduce our DSL Wodel for model mutation, and use it to define a set of mutation operators for BPMN.

3 Wodel: A Domain Specific Language for Model Mutation

Wodel   [8, 9] is a DSL for the specification of mutation operators. It is domain-independent, and so it can be applied to arbitrary languages, or to other kinds of artefacts like data. For this purpose, it relies on the provision of a domain meta-model specifying the structure of the artefacts to be mutated. The execution of a Wodel program yields a set of mutant models obtained by applying the specified operators to a set of given seed models, using different policies. For traceability, a registry with the mutations used to generate each mutant is also produced. Wodel ensures that the created mutant models conform to the domain meta-model and satisfy its OCL invariants.

Wodel provides mutation primitives to select, modify, create, delete, clone and retype objects; and to create, modify and delete references. Its mutation engine has built-in functionalities to ease the definition of mutation operators; for example, new objects are automatically added to a suitable container reference, and mandatory attributes and references without an explicit value are automatically initialized. Its editing environment  [10] features code completion, type checking, and generation of stand-alone Java code from Wodel programs (cf. Sect. 5). The tool can be extended with post-processing applications. Two examples are the framework for the automated generation of exercises presented in  [9], and the mutation testing development framework introduced in  [11].

Listing 1 shows a simple Wodel program for defining a mutation operator for BPMN. Line 1 specifies the strategy for mutant synthesis: generating either a maximum number of mutants, or all possible ones by using the keyword exhaustive. Line 2 states the output folder to store the mutants, and the input folder with the seed models. Line 3 configures the meta-model in use (we use the on in Fig. 2). The remainder of the program defines the mutation operators.

In this example, the operator ev2ac retypes an event of any kind into an activity (lines 7–9). This operator uses a single mutation primitive, but in general, operators can use any number of mutation statements. For instance, Table 2 in the appendix contains other more complex operators for BPMN, both proposed in the literature  [21] and created by us. Mutation primitives can be scheduled to be applied a random number of times within a given interval. If they do not define an interval (as in the example), they are applied just once.

Figure 3 shows an application of the mutation operator in Listing 1 to the BPMN model of Fig. 2. In the resulting mutant, the IntermediateEv ‘meal ready’ is replaced by an equally named Activity, and the incoming/outgoing references are preserved by the operator.

Fig. 3.

Application of the mutation operator in Listing 1 to a BPMN model.

4 Seed Model Synthesis Using Model Finding

As any other software, mutation programs need be tested to detect possible errors, so that they can be fixed. In the case of Wodel, this implies the creation of test models upon which the mutation programs can be executed. However, creating test models manually is tedious and error-prone, and it is difficult to ensure a full coverage of the program.

Therefore, to ease the testing of Wodel programs and operators, we propose a method based on model finding  [17] to automatically produce seed models over which all instructions of the given Wodel program are applicable (if such models exist in the given search scope).

Figure 4 outlines the seed model synthesis process. It relies on model search, a technique which applies constraint resolution over models  [17]. In particular, the synthesizer enriches the description of the domain meta-model and its invariants with additional OCL constraints derived from the Wodel program. These constraints express the requirements that a seed model must fulfil to allow the application of each mutation operator included in the program. Next, the enriched meta-model is loaded into a model finder  [20], which performs a bounded search of instances of the meta-model satisfying the OCL constraints. If a model is found, then it ensures full statement coverage of the Wodel program when executed with the model.

Fig. 4.

Process for automated model synthesis.

Table 1. Templates to generate OCL constraints from mutation primitives.

Table 1 shows the templates used to generate the OCL constraints for each mutation primitive, as well as illustrative examples. For instance, the OCL template for the object deletion primitive demands the existence of an object with the specified type and feature values, and included in a container reference that would not violate its lower cardinality bound if the object deletion takes place. The table shows as an example the deletion of an Activity: the derived OCL constraint checks that there exists some Activity, and the BusinessProcesses to which it belongs contain other elements apart from the Activity (i.e., the size of reference BusinessProcess.elements is bigger than 1, and deleting the Activity would still satisfy the reference cardinality).

Other OCL templates deal with object creation (which requires the existence of a suitable container reference with enough space for the object), object cloning (which in addition requires the existence of a candidate object to be cloned), object retyping (which requires conditions equivalent to those for deleting and creating objects for every container or regular reference that is not source- or target-compatible with the new type), reference modification (which requires the existence of an object of the target class), reference creation (which in addition requires a reference with space to add the object of the target class), and reference deletion (which requires that the reference fulfils its lower cardinality after taking one of its objects out).

For readability reasons, Table 1 shows the template associated to one occurrence of a mutation primitive. However, a program may apply the same primitive with the same parameters more than once. This may occur because the primitive is repeated, or because it defines an interval of applications bigger than one. Hence, in the general case, we count how many times a same instruction appears (i.e., is to be executed), and generate a slightly more complex constraint where each such occurrence is represented as a variable. For instance, if the mutation create Activity has to occur twice, we generate the constraint shown in Listing 2 (cf. Table 1).

Overall, the model synthesis process starts with the domain meta-model and its invariants. The meta-model is added an auxiliary mandatory class named Dummy. Then, the process uses the templates of Table 1 to generate the OCL constraints for each mutation operator in the provided Wodel program. These constraints are added as invariants of the Dummy class. Finally, the model finder is invoked with this enriched meta-model as input.

As an example, Listing 3 shows the OCL constraint generated from the program in Listing 1. As the retype operation considers three types, and or with three cases is generated.

Figure 5 shows a seed model returned by the model finder for the previous constraint. It satisfies the constraint of Listing 3, and those of the original meta-model.

Fig. 5.

Generated seed model.

Please note that seed models satisfying the synthesized constraints enable the application of all statements in the Wodel program. However, they do not guarantee that, after applying the program, the resulting mutant satisfies the existing invariants of the domain meta-model. This would require from techniques for advancing constraints to model operations  [4], which is left for future work.

5 Tool Support

The Wodel development environment is available as an Eclipse plugin at http://miso.es/tools/Wodel.html, together with examples and videos. The implementation is based on EMF  [24], and expects the meta-models of the artefacts to be mutated to be specified using Ecore.

Figure 6 shows the Wodel IDE. The IDE features a textual editor (label 1 in the figure) to create Wodel programs. The editor is built with Xtext and supports features like code completion. Label 2 in the figure shows the explorer with a typical Wodel organization. The src folder contains Wodel programs with the defined mutation operators. These operators are compiled into Java programs, and stored in the src-gen folder. The generated Java programs can be executed within the IDE to produce mutants from the seed models, which are saved in the out folder.

Fig. 6.

Wodel IDE and seed model synthesizer.

To support the contributions presented in this paper, we have extended the Wodel environment to support the synthesis of seed models for testing mutation programs. The seed model synthesis for a given program can be configured by means of the wizard marked with label 3 in the figure. This wizard allows setting the maximum number of seed models to be generated, the mutation operators used in the seed model generation process (either all operators in the program or a subset), additional model requirements expressed by OCL, and optionally, an EMF model to be used as seed of the model search. Moreover, a preference page allows customizing the minimum and maximum number of objects and references that the produced seed models should have. The search of seed models is performed using the Use Validator model finder  [20]. The generated seed models are converted from the USE format to EMF, and stored in the model folder (see the explorer view). The generated models can be used to test the designed operators, and can be visualized using, e.g., the EMF tree editor, or dedicated graphical editors, such as the one with label 4 in the figure.

6 Related Work

Next, we review works related to the main elements of our approach: languages tailored to define or synthesize mutation operators, and model synthesis from requirements.

DSLs for Mutation Operators, and Operator Synthesis. Some model-based mutation approaches use general-purpose model transformation languages to define mutation operators. In  [12], the authors present an MDE approach to define mutation testing tools, where programs are represented as models, and operators are encoded in QVT-o. Mutation operators have also been defined using Henshin in  [2], and ATL in  [25]. Instead, Wodel is a DSL targeted to define mutation operators, giving support for specific mutation actions (e.g., retyping, cloning), the automatic initialization of object features and containers, and the configuration of the number of mutants to generate. Works like  [25] miss such policies and only produce one mutant per input model.

Major  [19] is a mutation testing tool for Java that includes a scripting language to perform small customizations in mutation operators. For example, it allows configuring the replacement lists of mutation operators like Arithmetic Operator Replacement (AOR). Instead, Wodel is more expressive as it enables the selection, creation, deletion and retyping of elements. Moreover, Wodel is language-independent, as one can define operators for arbitrary meta-models.

In  [1], the authors propose a set of mutation primitives to define mutation operators for Ecore meta-models. However, it is not a full-fledged DSL, missing essential features like the possibility of selecting elements, and there is no tool support for execution. The approach in  [2] generates operators that guarantee the consistency of the mutated models with the meta-model multiplicity constraints. The operators are encoded as graph transformation rules. In comparison, Wodel considers more advanced primitives, like cloning, modifying the source or target of references, and retyping. Our techniques for model synthesis (for testing) could be a complement to these two approaches.

Model Synthesis. The MDE community has used model finders (like USE  [20] or Alloy  [17]) for activities like model completion, test model generation, or transformation analysis. For example, model finding is used in  [13] to generate test models for transformations based on specifications. For this purpose, the specifications are transformed into OCL. In our case, the novelty yields in the encoding of the semantics of the Wodel program into OCL, ensuring full statement coverage of the program.

Overall, to the best of our knowledge, environments to support the creation and testing of model-based mutation operators are currently lacking. Hence, we have designed Wodel, and its seed model generation capabilities to fill this gap.

7 Conclusions and Future Work

Given the recurrent need to develop sets of mutation operators, we propose a model-based approach to facilitate their definition, testing, and application. This way, we provide a DSL – called Wodel   – for their description, and model synthesis capabilities – based on model finding – for their testing and validation. Our approach is supported by an Eclipse plugin, and we have illustrated the approach in the context of the BPMN language.

We are currently extending the model synthesis process in two ways. First, to generate models where the operators are not applicable but are close to being applicable, so called near misses  [23]. Second, to generate seed models ensuring that the execution of the Wodel program leads to a correct model. For this purpose, we may use techniques to advance OCL constraints as preconditions, based on [4]. We also plan to work on static analysis techniques, e.g., to detect operator conflicts and dependencies. Finally, we are currently working on a methodology supporting the integral engineering of mutation operators.

A BPMN Mutation Operators

Table 2 encodes the BPMN mutation operators proposed in [21] using Wodel.

Table 2. Wodel mutation operators for BPMN.