Naouel Moha
email: moha@irisa.fr

Sagar Sen
email: ssen@irisa.fr

Cyril Faucher
email: cfaucher@irisa.fr

Olivier Barais
email: barais@irisa.fr

Jean-Marc Jézéquel
email: jezequel@irisa.fr

Evaluation of Kermeta for Solving Graph-based Problems

Keywords:

Kermeta is a meta-language for specifying the structure and behavior of graphs of interconnected objects called models. In this paper, we show that Kermeta is relatively suitable for solving three graph-based problems. First, Kermeta allows the specification of generic model transformations such as refactorings that we apply to different metamodels including Ecore, Java, and Uml. Second, we demonstrate the extensibility of Kermeta to the formal language Alloy using an inter-language model transformation. Kermeta uses Alloy to generate recommendations for completing partially specified models. Third, we show that the Kermeta compiler achieves better execution time and memory performance compared to similar graph-based approaches using a common case study. The three solutions proposed for those graph-based problems and their evaluation with Kermeta according to the criteria of genericity, extensibility, and performance are the main contribution of the paper. Another contribution is the comparison of these solutions with those proposed by other graph-based tools.

Introduction

Model-Driven Engineering (MDE) is a software development methodology focusing on models as first-class entities. Models are sets of objects which types are defined in metamodels. They can also be seen as graphs of objects interconnected by relationships. MDE aims to improve productivity of developers by maximizing compatibility between systems and platforms and simplifying the process of design.

Kermeta has been developed as a core language for an MDE platform. It is an executable metamodelling language implemented on top of the Eclipse Modeling Framework (EMF) within the Eclipse development environment.

In this paper, we present Kermeta as a suitable language for solving graph-based problems. We focus on three case studies proposed in the GraBats'08 tool contest 1 that involve specific graph-based problems.

The first case study consists of applying three well known refactorings [START_REF] Fowler | Refactoring -Improving the Design of Existing Code[END_REF] (Encapsulate Field, Move Method, and Pull Up Method) on models of Java programs. In this paper, we present a generalised approach to model refactoring that is applicable not only to Java programs but other metamodels such as Ecore and Uml. We specify the generic refactorings for various metamodels using the notion of model typing [START_REF] Steel | On model typing[END_REF], which is an extension of object typing in the model-oriented context.

The second case study (conference scheduling) highlights the extensibility of Kermeta to external languages, such as the formal specification language Alloy. We present an inter-language model transformation from Kermeta to Alloy to complete partial models. In the context of the case study, we use Alloy to generate different valid schedules for an unscheduled conference.

The third case study is an AntWorld simulation demonstrating Kermeta performance with regard to execution time and memory usage. The Kermeta to Java / EMF compiler provides a version of the Kermeta simulation achieving better performance compared to similar approaches based on Eclipse and eventually EMF.

Our contributions are threefold: [START_REF] Anastasakis | UML2Alloy: A challenging model transformation[END_REF] approaches to solve graph-based problems involving these case studies, [START_REF] Biermann | Antworld simulation case study modeled by emf transformation[END_REF] experiments to evaluate Kermeta in terms of genericity, extensibility, and performance using these case studies, (3) and a comparison of our approaches with those proposed by other graph-based tools. This article is organized as follows. Section 2 introduces Kermeta and highlights some of its features including the notion of model typing. Sections 3, 4, and 5 develop each of the three criteria that characterise Kermeta based on the three case studies. Section 6 surveys related work. Section 7 concludes and presents future work.

Kermeta

Description

Kermeta is a language for specifying metamodels, models, and model transformations that are compliant to the Meta Object Facility (MOF) standard [START_REF] Omg | MOF 2.0 Core Specification[END_REF]. The objectoriented meta-language MOF supports the definition of metamodels in terms of object-oriented structures (packages, classes, properties, and operations). It also provides model-specific constructions such as containments and associations between classes. Kermeta extends the MOF with an imperative action language for specifying constraints and operational semantics for metamodels [START_REF] Muller | Weaving executability into object-oriented meta-languages[END_REF]. Kermeta is built on top of EMF within the Eclipse development environment. The action language of Kermeta provides mechanisms for dynamic binding, reflection, and exception handling. It also includes classical control structures such as blocks, conditionals, and loops. Figure 1 shows the Kermeta graphical interface within Eclipse. It includes three views: a graphical representation of the current metamodel, a Kermeta code that applies transformations on the metamodel, and a tree representation of concepts of one of the two first views depending on the current view.

In the next paragraphs, we describe two key features of the Kermeta language essential for the comprehension of the paper: its ability of extension and the notion of model typing.

Extension of Kermeta

The first key feature of Kermeta is its ability to extend an existing metamodel with constraints, new structural elements (meta-classes, classes, properties, and operations), and functionalities defined with other languages using the aspect keyword. This keyword permits the composition of corresponding code within the underlying metamodel as it was a native element of it. This feature offers more flexibility to developers by enabling them to easily manipulate and reuse existing metamodels. The static composition operator "require" allows defining these various aspects in separate units and integrating them automatically into the metamodel. The composition is performed statically and the composed metamodel is type-checked to ensure the safe integration of all units. This mechanism can be compared to the open class paradigm [START_REF] Clifton | MultiJava: Modular open classes and symmetric multiple dispatch for java[END_REF]. Open classes in Kermeta are used to organize "cross-cutting" concerns separately from their metamodel, a key feature of aspect-oriented programming [START_REF] Kiczales | Aspect-Oriented Programming[END_REF]. Thanks to this composition operator, Kermeta remains a kernel platform and safely integrates all concerns around a metamodel.

Kermeta offers expressions very similar to Object Constraint Language (OCL) expressions [START_REF] Omg | The Object Constraint Language Specification 2[END_REF]. In particular, Kermeta includes lexical closures similar to OCL iterators on collections such as each, collect, select, or detect. Moreover, Kermeta also allows the direct importation and evaluation of OCL constraints. Pre-conditions and post-conditions can be defined for operations and invariants on classes.

Kermeta and its framework remain dedicated to model processing but provide an easy integration with other languages. Kermeta also allows importing Java classes to use services such as file input/output or network communications, which are not available in the Kermeta framework. It is also very useful, for instance, to make models communicate with existing Java applications. An other example of integration is the extension to Alloy [START_REF] Jackson | Software Abstractions: Logic, Language, and Analysis[END_REF] as presented in Section 4.

Model Typing

The second key feature of Kermeta is the notion of model typing [START_REF] Steel | On model typing[END_REF]. It consists of an extension of object-oriented typing in a model-oriented context: a model transformation expects some properties in its input model, like a given reference and multiplicity between a class A and a class B; if the instances of A in the input model have no such reference, this model cannot be processed by the transformation. A model typing is a strategy for using models that are subtypes or variants of a required model in place of it. Model typing permits the detection of type errors early in the design process of model transformation. Moreover, it allows more flexible reuse of model transformations across various metamodels, while preserving type safety [START_REF] Steel | On model typing[END_REF]. Type safety is guaranteed by type conformance, a criterion of substitutability.

The notion of model type conformance (or substitutability) has been adapted and extended to model types based on Bruce's notion of type groups and type group matching [START_REF] Bruce | Semanticsdriven language design: Statically type-safe virtual types in object-oriented languages[END_REF]. The matching relation, denoted <#, between two model types defines a function of the set of object types they contain according to the following definition adapted from [START_REF] Steel | On model typing[END_REF]:

Model type M' matches another M (denoted M' <# M ) iff for each object type C in M, there is one and only one corresponding object type C' in M' such that every property and operation in M.C also occurs in M'.C' with exactly the same signature as in M.C.

A limitation of the model typing is the name-dependent structural conformance. Indeed, only the matching of variants of model types that have respective objects interconnected in the same structural manner and with identical properties and operation names is possible. To reduce this limitation, we added two mechanisms to the model typing: the renaming of properties/operations and the possibility to match with other objects belonging to the same inheritance hierarchy. The renaming consists in specifying a new name for a property or an operation in a specific metamodel to allow the matching. The second mechanism consists in extending the matching to parents and children of the current object if this one does not match.

The following sections describe the three use cases on which Kermeta is applied, using a common presentation pattern: 1) we describe the problem that we propose to solve; 2) we present the use case which embeds this problem; 3) we illustrate our approach using a case study; 4) we present some experiments and results; 5) we provide a comparison with other graph-based tools2 ; 6) we end with a discussion.

Genericity

In this section, we present generic model transformations in Kermeta based on the notion of model typing. More precisely, we specify generic refactorings for different metamodels.

Problem Description

Refactoring has been intensively investigated in the graph and model transformation community over the last few years [START_REF] Mens | A survey of software refactoring[END_REF]. However, to the best of our knowledge, there exists no approach to specify metamodel independent generic transformations. In current approaches, the specification of refactorings are highly dependent on the metamodel. Our goal is to specify generic model transformations, such as refactorings, that can be reusable on different metamodels. For instance, a refactoring such as Pull Up Method (i.e., moving methods to the superclass if these methods have same signatures on subclasses) could be generic across any language supporting the objectoriented notion of inheritance (Uml, Ecore, Java).

Case Study: Refactoring

The refactoring case study of the GraBats'08 tool contest [START_REF] Hoffman | A case study for program refactoring[END_REF] consists of applying three well known refactorings (Encapsulate Field, Move Method, and Pull Up Method) on models of Java programs. We generalise this case study to the problem of specifying generic refactorings for various metamodels (Ecore, Uml).

In next section, we illustrate our approach by taking the Encapsulate Field refactoring as example. We recall that the Encapsulate Field refactoring consists of making a public field private and providing accessors [START_REF] Fowler | Refactoring -Improving the Design of Existing Code[END_REF].

Approach: Specification of Generic Refactorings

Figure 2 illustrates the four steps of our approach for the specification of generic refactorings. The first step consists in specifying a generic metamodel GenericMT 3 , which is a super-type of all metamodels. Then, in the second step, we specify a refactoring in Kermeta using GenericMT as the source metamodel. In the third step, the target metamodels such as Uml or Java are adapted to match with the metamodel GenericMT. The target metamodels are then subtypes of GenericMT. In the last step, the refactoring can then be concretely applied to all models of all target metamodels.

Step 1: Specification of Generic Metamodel

Our approach consists first of specifying a lightweight metamodel that contains the minimum required classes for specifying refactorings. The generic metamodel, called GenericMT, given in Figure 3 has been designed to specify refactorings. GenericMT consists of concepts such as classes, properties, operations, and parameters common to all metamodels. We use the letter 'g' as a prefix in the name of each element of the metamodel to denote the fact that they actually play the role of formal generic parameters. The elements contained within the metamodel GenericMT are minimum and sufficient for the specification of the three refactorings. However, since concepts related to the body of methods are not specified in the Ecore and Uml metamodels, we omit these concepts in our generic metamodel in order to specify a consistent common metamodel for all three metamodels.

Step 2: Specification of Generic Refactorings

In the second step, we specify refactorings based on the generic metamodel. Listing 1 gives a Kermeta code excerpt of the refactoring Encapsulate Field based on the metamodel GenericMT. This code checks (using preconditions) if for the specified field a getter accessor does not exists or if it exists, it is static. In the body of the operation encapsulateField, it creates a getter accessor if it did not exist yet. This code gives an insight into the specification of refactorings in Kermeta. The interested reader can refer to the Kermeta syntax in [11].

Step 3: Adaptation with Target Metamodels

The third step consists of adapting the target metamodels to the generic metamodel GenericMT using the mechanism of aspects in Kermeta. The adaptation consists in weaving in the target metamodel properties and operations that match with those of the generic metamodel. For each operation, we specify the body of the method. For each property, we specify how to set and get it by defining getter and setter accessors. This step is necessary because the model typing fails to match metamodels that are structurally too different from the one required by the transformation. Thus, the adaptation modifies the structure of the target metamodel with additional elements, enabling the match of model typing.

During the matching process, we match with the target metamodel not only one class of the generic metamodel but a set of classes. Thus, the model type conformance is hard to obtain if it is not possible to distinguish classes of the generic metamodel that have same name attributes. We introduced a "non-matching" strategy by adding a discriminant attribute such as isAnAttribute in GAttribute to distinguish this class from GOperation.

Listings 2 and 3 show the adaptation of the return type of an operation for the Java and Uml target metamodels. The adaptation for Java is quite straightforward and consists of assignments. The adaptation for Uml requires in the setter to look for a parameter with ParameterDirectionKind.return as a value of the attribute direction.

package j a v a p r o g r a m ; r e q u i r e " p l a t f o r m : / r e s o u r c e / o r g . k e r m e t a . r e f a c t o r i n g / m etam odel / J av aProgram . e c o r e " a s p e c t c l a s s O p e r a t i o n { p r op e r t y gReturnT y pe : j a v a p r o g r a m : : C l a s s g e t t e r i s do r e s u l t ?= s e l f . t y p e end s e t t e r i s do s e l f . t y p e := v a l u e end } Listing 2. Kermeta Code for Java Adaptation.

package uml ; r e q u i r e " h t t p : / /www. e c l i p s e . o r g / uml2 / 2 .

Step 4: Application of Refactoring

The last step of our approach consists of applying the refactoring on the target metamodel as illustrated in Listing 3 for the Uml metamodel. We can notice that the class Refactor takes as argument the metamodel Uml, which thanks to the adaptation of Listing 3 is a subtype of the expected super-type GenericMT as specified in Listing 1. The models to refactor are loaded and saved after refactoring in XMI files.

package r e f a c t o r ; r e q u i r e " h t t p : / /www. e c l i p s e . o r g / uml2 / 2 .

Experiments and Results

We specified and applied three refactorings suggested in the GraBats'08 tool contest (Encapsulate Field, Move Method, and Pull Up Method) on three different metamodels (Uml, Ecore, and Java Program). The metamodels structurally differ. For example, the Uml metamodel has a hierarchical structure whereas the Java metamodel has a flat structure (i.e., has no containers).

Comparison with Other Tools

None of the tools that participate to the contest offer the possibility to specify generic refactorings. However, they focus on other criteria. Tools such as Fujaba [7], Progres [START_REF] Weinell | Using PROGRES for graph-based program refactoring[END_REF], and VMTS [START_REF]Visual Modeling and Transformation System (VMTS)[END_REF] focus on the user interaction criterion. For example, VMTS provides a source code like presentation and control flow diagrams for rewriting rules. In Kermeta, it is also possible to visualize models and metamodels using the Ecore Diagram Editor available in the Eclipse Ecore Tools plugin or graphical editors generated with GMF (Graphical Modeling Framework) plugin. Jdt2Mdr [START_REF] Muliawan | Refactoring using JDT2MDR[END_REF], Progres [START_REF] Weinell | Using PROGRES for graph-based program refactoring[END_REF], and Fujaba [7] focus on the expressiveness and extensibility criteria. Jdt2Mdr transforms Uml models of controlled graph transformations into executable Java code. Progres provides imperative control structures such as conditional branches and iterations. Such control structures enhance expressiveness in specifying graph transformation rules.

Discussion

Writing adaptations can be more or less difficult depending on the developers' knowledge of the target metamodel. However, after adaptation, the developers can reuse all model transformations written for the generic metamodel. Conversely, if we write a transformation for the generic metamodel, we can apply it on all target metamodels.

Model evolution can be supported: indeed, if a metamodel evolves but still matches with the generic metamodel, the transformations are still valid for all models of the new metamodel.

Not only transformation but generic MDE tools can be develop which are independent of the metamodelling language. In future work, we intend to investigate generic analyses to compute metrics and detect patterns and anti-patterns or inconsistencies in different metamodels.

Extensibility

Model transformations can extend Kermeta to external languages and model-oriented tools with functionality not readily available in Kermeta. In the following subsections, we demonstrate extensibility of Kermeta by presenting a transformation from metamodels in Kermeta to declarative specifications in the formal language Alloy [9].

Problem Description

We define a partial model as a graph of objects that is either inconsistent with the structure of its metamodel or does not satisfy some invariants on its metamodel. The problem we address is the automatic transformation of a partial model into a complete model. The complete model is a modification of the partial model such that it becomes consistent with its metamodel and invariants. We can automate the process of completing a partial model using a constraint satisfaction language (CSL) equipped with a solver. We name this process automatic model completion. We want to extend Kermeta with this capability. The extension transformation must bridge the gap in expressiveness between Kermeta metamodels + invariants and the target CSL. This is an issue because most CSLs have concise grammars and welldefined declarative semantics as opposed to domain-specific Kermeta metamodels. Further, we must transform low-level solutions back from constraint solvers to domainspecific complete models conforming to a Kermeta metamodel.

Case Study: Conference Scheduling

This case study describes a modelling domain for scheduling papers in different sessions of a conference. We structure the concepts of the conference scheduling problem domain in the metamodel M M cs shown in Figure 4. The metamodel M M cs consists of a conference with sessions. Each session contains papers for presentation and a session chair. Every paper has a presenter. All papers in the conference must be assigned to time slots while respecting invariants I cs such as:

1. No simultaneous papers are presented by the same person; 2. No presenter is chairing another session at the same time; 3. Nobody chairs two sessions simultaneously.

A partial model containing objects of classes in M M cs is shown in Figure 5. In the partial model, we do not assign papers to time slots rendering the invariants I cs unsatisfied.

Approach: Partial Model Completion

We outline our approach for automatic model completion in Figure 6. Our approach consists of the four following steps:

Step 1: The model transformation Kermeta2Alloy: (a) Transforms a source Kermeta metamodel M M s to an Alloy model A s . It transforms M M s classes, their Step 2: We insert Alloy facts for invariants I s to the metamodel M M s . These invariants may initially be specified in OCL. At the moment, we manually transform natural language or OCL constraints to Alloy facts representing these invariants. In future, we intend to integrate an automatic transformation of a subset of OCL to Alloy facts into Kermeta2Alloy. Example:

In the conference scheduling case study, one of the invariants states that a person cannot give simultaneous presentations. We encode both the OCL version and its Alloy fact in Listing 8. We do not present all the case study constraints in OCL or in natural language due to space limitations. Step 3: We invoke the Alloy API to transform the Alloy source model A s to boolean conjunction normal form (CNF). We solve the CNF formula using an off-theshelf satisfiability (SAT) solver such as ZChaff [START_REF] Mahajan | Zchaff2004: An efficient SAT solver[END_REF] or MiniSAT [START_REF] Een | MiniSat a SAT solver with conflict-clause minimization[END_REF] to obtain solution(s) (if they exist). These solutions are dumped as Alloy XML files. Example: We present the results of executing the run statement of Listing 7 in Section 4.4.

Step 4: We transform an Alloy XML file representing a solution to a complete model c s using the transformation Alloy2Model. This complete model c s conforms to the metamodel M M s . Example: In this transformation low-level relational mappings between atoms are transformed to a conference model conforming to M M cs .

Experiments and Results

We name the Alloy model we obtain for conference scheduling A cs . We solve A cs to obtain a complete model c cs with a valid conference schedule. We execute a run command to solve the predicate ConferenceModel in A cs . The result of our experiment is an XMI file or a set of XMI files or complete conference model(s) with valid schedule(s). One of the complete models c cs in comprehensible visual syntax is shown in Figure 7. We have not specified a concrete visual syntax for the conference scheduling language and the XMI to concrete syntax transformation is manual. Nevertheless, one can use the Eclipse Graphical Modelling Framework (GMF) to specify a concrete syntax for any language. The red dotted arrows from papers to slots illustrate the scheduling solution.

Comparison with other Tools

The AGG-EMT [START_REF]The Attributed Graph Grammar (AGG) System[END_REF] tool performs scheduling using triple graph grammars (TGG). In their approach, a paper is assigned a time slot using TGG rules such that negative application conditions (NACs) are not violated. The termination of the transformation process determines if we can schedule the conference. The AGG solution is specific to the scheduling problem while our approach is generic and applicable to any Kermeta metamodel transformable to Alloy. However, the domain specific TGG rules can make the scheduling process itself more efficient than SAT solving.

Discussion

Our approach is generic and valid for any metamodel and not just for the conference scheduling case study. We present this approach in the context of automatic model completion but we have applied this approach earlier for model completion in model editors [START_REF] Sen | Domain-specific model editors with model completion[END_REF], and for test model generation [START_REF] Sen | On combining mullti-formalism knowledge to select test models for model transformaion testing[END_REF]. There have been other contributions to transform high-level languages to Alloy such as the prototype tool UML2Alloy [START_REF] Anastasakis | UML2Alloy: A challenging model transformation[END_REF].

Kermeta supports import/export to industry standards for metamodel and metadata specification such as EMF and XSD allowing widespread application of transformations written in Kermeta. For instance, the transformation to Alloy for any metamodel makes them amenable to formal analysis, automatic model synthesis, and counter-example generation.

Performance

Problem Description

In this section, we implement in Kermeta the AntWorld simulation and evaluate Kermeta performance with regard to execution time and memory usage. We also compare and discuss these performance results to those obtained with similar approaches based on Eclipse and eventually EMF. Performance and scalability issues are often seen as a challenge to promote model-driven tools to industry. Indeed, although model-driven applications might offer high-level design abstractions and reduce development time and efforts, they might also experience scalability problem with respect to performance.

Case Study: AntWorld

The AntWorld simulation is a case study designed as a benchmark for the comparison of graph-based tools [START_REF] Zündorf | [END_REF]. It aims to run tools on a scalable application to evaluate their performance in terms of execution time and memory usage.

The case study simulates an ant colony searching for food around the area of the ant hill located in the center of a grid. If an ant finds food, it drops pheromones in its way back home. An ant that brings food into the ant hill leads to the creation of new ants. If an ant searching for food hits a pheromone, the ant follows the pheromone path to the food. The simulation is divided in rounds and every ant moves during a round.

Figure 8 gives the Ecore metamodel of the AntWorld simulation. The class Ant represents an ant and contains an attribute mode to determine whether the ant is searching for food or moving back to the center. The class Map represents the grid of nodes corresponding to the area of food search. A map contains a set of nodes represented by the class GridNode. Among the grid nodes, there are two special types of nodes AxisNode and CenterNode. The AxisNode is a node on an axis. The CenterNode corresponds to the node in the center of the grid. CenterNode inherits from AxisNode because it is at the intersection of the two axes. A GridNode is located in a given level and might be at the border of the map. It also contains a number of food parts and a number of pheromones.

Approach

Until recently, Kermeta applications were executed only in an interpreted mode. To get better performance, we have developed a Kermeta to Java/EMF compiler that allows developers to deploy Kermeta applications as Java

Implementation

We implement the AntWorld simulation in Kermeta and in particular, the local search. The transformation rules of the AntWorld simulation are written as operations, which are sets of expressions that specify the expected behavior. The operations are added to the Ecore metamodel of AntWorld by using the aspect-oriented modeling facilities of Kermeta. Listing 9 describes the operation antEat weaved into the class GridNode. This operation describes the behavior of an ant that arrives at a node containing food. The ant takes a piece of food and drops 1024 parts of pheromones. This listing shows also a reference weaved into the class Map to add a cache of nodes with pheromones for improving the performance during the update of the number of pheromones on a node.

Experiments and Results

We computed the execution time and memory usage of the AntWorld simulation written in Kermeta and executed in a compiled mode. These experiments were performed on a laptop with an Intel Core 2 CPU T2600, 2.16GHz, and 2Go for RAM under Windows XP. We also computed these performance tests using the version of Kermeta on the virtual desktop infrastructure (VDI) submitted for the tool contest to have a fair comparison with other VDIs submitted for the tool contest.

The table 1 presents the performance results for every 25 rounds. It gives the number of grid levels, ants, and nodes with pheromone. It also provides the elapsed time between every 25 rounds, the cumulative elapsed time, and the consuming memory. The elapsed time are given both on local and the VDI.

The memory usage of the Kermeta runtime context is constant during the execution and independent of the algorithm. The memory usage excludes the memory consumed for the runtime context (estimated at 5246 kB). It increases progressively with the number of rounds.

Comparison with other Tools

We compare the performance results of Kermeta with other tools partipating in the contest. The VMTS tool [START_REF] Meszaros | GraBaTs[END_REF] is the fastest tool among all tools participating to the tool contest because it seems to be hard coded using C++. VMTS is 53.7 times faster than Kermeta at 500 rounds. We compare Kermeta with other tools based on Eclipse or EMF like Viatra2 [START_REF]Department of measurement and information systems[END_REF] and EMF Transformation [START_REF] Biermann | Antworld simulation case study modeled by emf transformation[END_REF]. We execute the simulation using the VDIs to have a fair comparison. Figure 9 illustrates the results obtained with Kermeta, Viatra2, VMTS and EMF Transformation. We observe that Kermeta is 4.9 times faster than Viatra2 at 500 rounds. As regards EMF Transformation, results given during the GraBats'08 Workshop shows that Kermeta is 65 times faster at 100 rounds. A regression analysis reveals that all the curves are polynomial. Figure 10 shows a comparison between Kermeta and VMTS in terms of memory usage. Kermeta seems to be the best solution with 10,353 kB at 500 rounds compared to VMTS with 31,404 kB (that is, a factor of 3) and 90,156 kB (results only provided at 250 and 500 rounds) for GrGen [START_REF] Buchwald | net solution of the AntWorld case for the GraBaTs 2008 contest[END_REF] (a factor of 8.7). Viatra2 consumes 145,000 kB at 350 rounds (results directly provided by Viatra2) in comparison with 4,601 kB in Kermeta (a factor of 31,5). Both the Kermeta and VMTS curves are polynomial.

Discussion

Viatra2 is not compiled, but interpreted. The use of a compiled version is very significant in Kermeta and especially in the case of the AntWorld simulation. The compiled version is 50 times faster than the interpreted one.

The measures could have been influenced by external elements. Indeed, we notice that running programs or network connections can reduce from 10% to 20% the time executions. Therefore, we compute our performance measures by disconnecting all network connections and closing all programs except Kermeta. However, parasite programs may still have influenced the measures.

Related Work

Several approaches can be adopted for writing model transformations. Developers can use general purpose languages such as Java, C#, and C++ or dedicated rulebased languages such as ATL [START_REF] Jouault | ATL: A model transformation tool[END_REF] and the OMG QVT standard [START_REF] Omg | MOF 2.0 Query/View/Transformation Specification[END_REF]. These dedicated languages mix imperative and declarative constructs. Another category of approaches include pattern-based transformation tools such as Agg [START_REF]The Attributed Graph Grammar (AGG) System[END_REF], VMTS [START_REF]Visual Modeling and Transformation System (VMTS)[END_REF], Viatra2 [START_REF]Department of measurement and information systems[END_REF], and Progres [START_REF] Weinell | Using PROGRES for graph-based program refactoring[END_REF]. These approaches present advantages and drawbacks. Developers who use general purpose languages benefit from well-known languages such as Java/EMF and dedicated and mature development environments such as the JDT under Eclipse. However, these languages are not always suitable to specify transformations because developers need to manage different constructs such as tree traversals and object instantiations. This implies a bad separation of concerns and therefore, decreases the reuse and maintainability of transformations.

In rule-based languages, simple transformations are easy to write because they are based on a one-to-one mapping that specify how to map concepts from one metamodel to another. Moreover, the declarative nature of such languages allows developers to benefit from a good expressive power without managing the rule dependencies themselves. This expressive power occurs also in pattern-based transformation tools. These languages generally support built-in static analysis capabilities such as critical pair analysis and sequential dependency analysis, which help to detect inconsistencies and implicit dependencies in transformations [START_REF] Mens | Analysing Refactoring Dependencies using Graph Transformation[END_REF]. However, the specification of complex transformations using a declarative style can be complicated because there is no clear mapping among the concepts.

Kermeta is a domain specific language for metamodelling. It leverages object-oriented languages (Java, C#, C++, . . . ), class diagrams, and design-by-contract to make metamodelling easy for the seasoned object-oriented programmers. Compared to Java, Kermeta provides modeloriented and aspect-oriented capabilities: OCL-like lexical closures, native support of open-classes, model typing feature, and the ability to load and save EMF models. EMFScript [START_REF] Tombelle | Dynamic and generic manipulation of models: From introspection to scripting[END_REF] and Epsilon [START_REF] Kolovos | The Epsilon Transformation Language[END_REF] share some common features with Kermeta such as OCL-like lexical closures and imperative style of programming for manipulating models. Kermeta as a model-transformation engine raises also several drawbacks. Compared to a general purpose language, the developer has to learn a new language and the environment is not as mature as an Eclipse JDT. Compared to a rule-based language, its imperative nature forces the developer to manage lots of concerns (tree traversal algorithms, object instantiations, . . . ). However, the imperative style offers more control for manipulating transformations. Finally, even if Kermeta provides a support for model transformation testing and a type checker, it does not provide any static analyzer that helps designers to detect inconsistencies in transformations. However, Kermeta still appears as a very good trade-off between general purpose and rulebased languages as well as efficient for large scale MDE applications.

Conclusion

In this paper, we have evaluated Kermeta, an executable metamodelling language for describing the structure of metamodels and their behavior, on three graph-based problems. As a result, Kermeta serves as a general purpose metamodelling language that helps in solving modeland graph-based problems. The three cases studies highlighted respectively the genericity, extensibility, and performance of the Kermeta language. They demonstrated that Kermeta allows the specification of generic refactorings, the partial model completion, and the efficient execution of resource consuming algorithms. Future work includes increasing the repository of refactorings on other metamodels, automatically transforming a subset of OCL to Alloy, optimizing the source code generated for improving the performance, and evaluating Kermeta with other criteria.

Fig. 1 .

 1 Fig. 1. Kermeta Graphical Interface

4 NaouelFig. 2 .Fig. 3 .

 423 Fig. 2. Approach for the Specification of Generic Refactorings

package r e f

  a c t o r ; c l a s s R e f a c t o r <MT : GenericMT > { op e r a t ion e n c a p s u l a t e F i e l d ( f i e l d : MT : : G A t t r i b u t e , f i e l d C l a s s : MT : : GC l as s , g e t t e r N a m e : S t r i n g , s e t t e r N a m e : S t r i n g ) : Void // P r e c o n d i t i o n s pre g e t t e r I s S t a t i c N o t E x i s t i s do i f f i e l d C l a s s . g O p e r a t i o n . e x i s t s { op | op . gName == g e t t e r N a m e } then f i e l d C l a s s . g O p e r a t i o n . d e t e c t { op | op . gName == g e t t e r N a m e } . g I s S t a t i c == f i e l d . g I s S t a t i c e l s e t r u e end end // Method body i s do // Manage t h e g e t t e r i f not f i e l d C l a s s . g O p e r a t i o n . e x i s t s { op | op . gName == g e t t e r N a m e } then // No g e t t e r , s o we must add i t var op : MT : : GO perati on i n i t MT : : GO perati on . new op . gName := g e t t e r N a m e f i e l d C l a s s . g O p e r a t i o n . add ( op ) op . gReturnT y pe := f i e l d . gType end // Manage t h e s e t t e r and t h e v i s i b i l i t y . . . end } Listing 1. Kermeta Code for the Encapsulate Field Refactoring.

  1 . 0 /UML" c l a s s Main { op e r a t ion main ( ) : Void i s do var r e f a c t o r : r e f a c t o r : : R e f a c t o r <uml : : UmlMT > i n i t r e f a c t o r : : R e f a c t o r <uml : : UmlMT>.new var n a m e F i e l d : uml : : P r o p e r t y var f i e l d C l a s s : uml : : C l a s s r e f a c t o r . e n c a p s u l a t e F i e l d ( nam eFi el d , f i e l d C l a s s , " getName " , " setName " ) end } Listing 4. Kermeta Code for Applying the Encapsulate Field Refactoring on the Uml metamodel.

Fig. 4 .

 4 Fig. 4. Conference Scheduling Metamodel M Mcs

Fig. 5 .Fig. 6 .

 56 Fig. 5. A Partial Model pcs Without Slot Assignment

s i gListing 5 .Listing 6 .

 56 Paper { p a p e r I D : lon e I n t , s e s s i o n : one S e s s i o n , p r e s e n t e r : one P e r s o n , s l o t : one T i m e S l o t } f a c t P a p e r c o n t a i n e r s { a l l o : Paper | o i n S e s s i o n . p a p e r s } f a c t S e s s i o n p a p e r s P a p e r s e s s i o n o p p o s i t e { a l l o1 : S e s s i o n , o2 : Paper | o2 i n o1 . p a p e r s i m p l i e s o1 i n o2 . s e s s i o n } Alloy Model for Conference Scheduling (b) Transforms a source partial model p s to Alloy predicates and appends them to A s . Example: The partial model in Figure 5 is transformed to the predicate Conf erenceM odel, partially presented in Listing 6. The predicate states the number of objects in the partial model. Following this, it states values for properties that we extract from the partial model. We assign values for all properties available in the partial model including sessions, papers, presenters, and time slots. What remains unassigned in the predicate are the properties for Paper.slot. pred C o n f e r e n c e M o d e l { / * Number o f o b j e c t s o f e a c h s i g n a t u r e i n P a r t i a l Model * / #C o n f e r e n c e =1 and #S e s s i o n =3 and #Paper =9 and #P e r s o n =8 and #T i m e S l o t=6 and / * E x i s t s some o b j e c t o f a s i g n a t u r e w i t h p r o p e r t i e s o f v a l u e s i n t h e p a r t i a l m odel * / some s 1 : S e s s i o n , s 2 : S e s s i o n , s 3 : S e s s i o n | s 1 . s e s s i o n I D = 10 and s 2 . s e s s i o n I D= 20 and s 3 . s e s s i o n I D =30 and . . . / * S i m i l a r e x p r e s s i o n s t h a t d e f i n e o t h e r o b j e c t s i n p a r t i a l m odel * / } Alloy Predicate for pcs (c) Inserts a run command to solve p s in A s . The run command states the scopes for the different objects we expect in the complete model and for integers between -2 7 to 2 7 . It obtains these scopes from the partial model. Example: In the case study we use integers to specify identities for sessions, papers, and people. We create the Alloy run command in Listing 7 and insert it into A cs . The run command solves the predicate ConferenceModel. run C o n f e r e n c e M o d e l f o r 1 C o n f e r e n c e , 6 T i m e S l o t , 9 Paper , 3 S e s s i o n , 8 P e r s o n , 7 i n t Listing 7. Alloy Run Command to Complete Partial Model

/Listing 8 .

 8 /No S i m u l a t e n o u s Paper P r e s e n t a t i o n s by a P e r s o n //OCL V e r s i o n con t e xt P e r s o n in v n o S i m u l t a n e o u s P r e s e n t a t i o n s : s e l f . p r e s e n t s . f o r A l l { p1 , p2 | p1 != p2 i m p l i e s p1 . s l o t != p2 . s l o t } // T r a n s f o r m e d A l l o y F a c t f a c t n o S i m u l t a n e o u s P r e s e n t a t i o n s { a l l p : P e r s o n | a l l p a p e r 1 : p . p r e s e n t s , p a p e r 2 : p . p r e s e n t s | p a p e r 1 != p a p e r 2 i m p l i e s p a p e r 1 . s l o t != p a p e r 2 . s l o t } OCL Invariant to Alloy Fact

Fig. 7 .

 7 Fig. 7. A Complete Model ccs

Fig. 8 .

 8 Fig. 8. AntWorld Metamodel / EMF and thus, execute Kermeta applications in a compiled mode. The Kermeta compiler first transforms a Kermeta model into an Ecore model and then generates an Eclipse plugin in Java/EMF source code. The resulting Java source code may be used both in Eclipse application or in Java application (standalone). The Java compiled version of an Kermeta application typically runs faster than in interpreted mode.

  package a n t w o r l d ; r e q u i r e k e r m e t a r e q u i r e " p l a t f o r m : / r e s o u r c e / AntWorld/ AntWorld . e c o r e " u sin g a n t w o r l d a s p e c t c l a s s Map { r e f e r e n c e g r i d O f P h e r s : bag Gri dN ode [ 0 . . * ] } a s p e c t c l a s s Gri dN ode { op e r a t ion a n t E a t ( map : Map ) i s do s e l f . f o o d := s e l f . f o o d -1 s e l f . p h e r := s e l f . p h e r + 1 0 2 4 // The c u r r e n t node i s added t o t h e c a c h e // when i t i s i n i t i a l i z e d , i . e . s e l f . p h e r == 1 0 2 4 i f s e l f . p h e r == 1 0 2 4 then map . g r i d O f P h e r s . add ( s e l f ) end end } Listing 9. Implementation by Aspect of the Reference gridOfPhers on the Class Map and the Operation antEat on the Class Ant.

Fig. 9 .Fig. 10 .

 910 Fig. 9. Execution Time of Kermeta (VDI), Viatra2 (VDI), VMTS and EMF Transformation

  Listing 3. Kermeta Code for Uml Adaptation.

	1 . 0 /UML"
	a s p e c t c l a s s O p e r a t i o n {
	p r op e r t y gReturnT y pe : uml : : C l a s s
	g e t t e r i s do
	r e s u l t ?= s e l f . t y p e
	end
	s e t t e r i s do
	var r e t : uml : : P a r a m e t e r
	r e t := s e l f . ow nedParam eter . d e t e c t {p |
	p . d i r e c t i o n == P a r a m e t e r D i r e c t i o n K i n d . r e t u r n }
	i f r e t == v o i d then
	r e t := P a r a m e t e r . new
	s e l f . ow nedParam eter . add ( r e t )
	end
	r e t . t y p e := v a l u e
	end
	}

Table 1 .

 1 Performance Test Results

	Number of	Number of	Number of	Number of Nodes	Elapsed Time (ms)	Cumulative Time (ms)	Memory
	Rounds	Grid Levels	Ants	with Pheromone	Local	VDI	Local	VDI	(kB)
	25	8	20	19	47	157	47	157	30
	50	8	182	21	125	226	172	383	40
	75	14	693	65	515	841	687	1224	131
	100	18	1775	142	1313	1785	2000	3009	254
	125	22	3070	277	2437	3283	4437	6292	403
	150	26	4767	452	3969	5293	8406	11585	594
	175	34	6415	653	5766	7728	14172	19313	907
	200	40	8488	982	7562	10148	21734	29461	1241
	225	48	10468	1248	9594	12936	31328	42397	1666
	250	56	12598	1617	11875	15946	43203	58343	2187
	275	64	14654	1882	14078	18794	57281	77137	2706
	300	72	16873	2261	16141	21476	73422	98613	3323
	325	79	19122	2593	18578	24610	92000	123223	3934
	350	86	21444	2907	21093	27505	113093	150728	4601
	375	96	23972	3235	24032	31054	137125	181782	5504
	400	103	26108	3657	26656	33835	163781	215617	6294
	425	111	28753	4041	29187	35581	192968	251198	7213
	450	119	30986	4462	32188	37737	225156	288935	8110
	475	129	33571	4939	35281	40444	260437	329379	9444
	500	135	35911	5435	37781	43319	298218	372698	10353

The GraBats'08 tool contest was held during the 4 th International Workshop on Graph-Based

Tools 2008.

These tools participate to the tool contest organised for the STTT Special Section on Graph-based Tool Comparison.

Acknowledgements. We are grateful to Vincent Mahé and Didier Vojtisek for their valuable comments on this paper and their contribution on the implementation of the Kermeta workbench as well as on the solutions of the case studies.


Romain Delamare
email: romain.delamare@irisa.fr

Benoit Baudry
email: benoit.baudry@irisa.fr

Sudipto Ghosh
email: ghosh@cs.colostate.edu

Yves Le Traon
email: yves.letraon@telecom-bretagne.eu

A Test-Driven Approach to Developing Pointcut Descriptors in AspectJ

Keywords: Aspect-oriented programming, joinpoints, pointcut descriptors, mutation analysis, testdriven development, testing tool

Aspect-oriented programming (AOP) languages introduce new constructs that can lead to new types of faults, which must be targeted by testing techniques. In particular, AOP languages such as AspectJ use a pointcut descriptor (PCD) that provides a convenient way to declaratively specify a set of joinpoints in the program where the aspect should be woven. However, a major difficulty when testing that the PCD matches the intended set of joinpoints is the lack of precise specification for this set other than the PCD itself.

In this paper, we propose a test-driven approach for the development and validation of the PCD. We developed a tool, AdviceTracer, which enriches the JUnit API with new types of assertions that can be used to specify the expected joinpoints. In order to validate our approach, we also developed a mutation tool that systematically injects faults into PCDs. Using these two tools, we perform experiments to validate that our approach can be applied for specifying expected joinpoints and for detecting faults in the PCD.

Introduction

With the emergence of the aspect-oriented programming (AOP) paradigm, the testing community must adapt existing testing techniques or develop new ones for systems developed using this paradigm. When implementing a program with aspects, the core concerns are implemented in a base program and the cross-cutting concerns are implemented in aspects. An aspect is composed of two main parts: [START_REF] Anbalagan | Efficient mutant generation for mutation testing of pointcuts in aspect-oriented programs[END_REF] an advice that implements the behavior of the cross-cutting concern, and (2) the pointcut descriptor (PCD) that designates a set of joinpoints in the base program where the advice should be woven.

A number of researchers have studied the new types of faults that can be introduced by AOP and should, thus, be targeted by testing techniques. These works identify new faults that can occur in the interactions between the base program and the aspect, in the advice, or in the PCD. This last category of faults is specific to aspect-oriented languages since they introduce new constructs to define the PCD. As observed by Ferrari et al. [START_REF] Ferrari | Mutation testing for aspect-oriented programs[END_REF], the PCD is the place that is the most fault-prone in an aspect.

The consequence of an incorrect PCD is that the advice is woven in unexpected places or is not woven where it is expected. This is known as the fragile pointcut problem in AOP [START_REF] Koppen | Pcdiff: Attacking the fragile pointcut problem[END_REF][START_REF] Störzer | Using pointcut delta analysis to support evolution of aspect-oriented software[END_REF]. In turn, this introduces faults in the program resulting from aspect weaving. Moreover, when aspect-oriented programs evolve, there is a well-known risk that the PCD may match unintended joinpoints. This is known as the evolution paradox issue in AOP [START_REF] Tourwe | On the existence of the aosd-evolution paradox[END_REF].

A major challenge to detecting faults in the PCD is that a PCD is an abstract declaration of a set of joinpoints and there is no other specification of the set of joinpoints that it should match. To cope with this lack of specification, we propose a test-driven approach to developing the PCDs, where the tests can be used to validate that the joinpoints matched by the PCD are the intended ones. The approach requires the creation of test cases that specify the intended and unintended join-points. These test cases should not pass before aspect weaving and should pass after weaving if the correct set of joinpoints is matched by the PCD.

In order to write these test cases, we need to build an oracle that checks that an advice is woven at a particular point in the program. Currently, using AspectJ and JUnit, we can only build oracles that check whether an advice has executed correctly at a specific place in the base program. This is not satisfactory for us because, if such a test case fails, it is not possible to determine if this happened because the advice was not woven (the fault we are looking for) or because the advice does not behave as expected. In order to have more precise oracles for our test-driven approach, we implemented a tool called AdviceTracer that can be used with JUnit. AdviceTracer can determine at runtime which advice (defined in a particular aspect) is executed and at which place in the base program. This information can then be used to build oracles that specifically target the presence or absence of an advice, and do not just check if the advice executes correctly.

We also developed a mutation tool, called AjMutator, that systematically injects faults into the PCD and checks if a set of test cases is able to detect these faults. The faults are based on the model proposed by Ferrari et al. [START_REF] Ferrari | Mutation testing for aspect-oriented programs[END_REF]. We performed experiments to evaluate the effectiveness of the test cases written using AdviceTracer in terms of their ability to detect faults introduced by AjMutator in the PCD. We used Tetris and an auction application as examples. Tetris has three aspects and the auction system has two. For each of these systems, we developed test cases that specify the intended joinpoints and generated mutants for the PCDs in the aspects. We observed that the test cases are able to detect different types of faults. We also measured the effort required to create the test cases that detected these faults.

Section 2 discusses the main issues encountered when testing a PCD. Section 3 presents the Advice-Tracer tool and Section 4 presents the AjMutator tool. Section 5 describes our case studies. Section 6 discusses related research. We present our conclusions in Section 7.

Testing Pointcut Descriptors

When testing a PCD, we look for four kinds of faults, as defined by Lemos et al. [START_REF] Lemos | Testing aspect-oriented programming pointcut descriptors[END_REF]. Figure 1 illustrates them using a set abstraction. The lined set corresponds to the intended joinpoints and the grey set corresponds to the joinpoints actually matched by the PCD. An fault in the PCD can produce (1) both unintended and neglected joinpoints, (2) only neglected joinpoints, or (3) only unintended joinpoints. A PCD with a type In order to detect these faults we need an alternate way to specify the set of intended joinpoints. In this paper, we propose a test-driven approach for PCD development. In test-driven approaches, the test cases are the specification of the program [START_REF] Beck | Test Driven Development: By Example[END_REF]. Thus, in our approach the test cases specify the set of joinpoints that are expected to be matched by the PCD.

Our solution provides a specification of the PCD. Now, it is possible to check for inconsistencies between the PCD and this specification. A difference between the sets of intended and matched joinpoints reveals a fault. Another advantage of a test-driven approach is that it provides test suites for regression testing in the early stages of development. Thus, it becomes possible to check that no unexpected changes were introduced both during the development and the evolution of the program.

A key issue for such a test-driven approach is the lack of support for oracles that precisely specify the presence or absence of a joinpoint. In the current state of AspectJ, to test that a joinpoint was matched by the PCD at a specific place of the system, a test case needs to check that the behavior implemented by the joinpoint executes correctly at this place.

For example, let us consider the aspect in Listing 1. The expression pointcut deleteLines(): execution ( * AspectTetris.deleteLines())

is a PCD that will match all the executions of all deleteLines() methods, irrespective of their return type. The advice declared in the body of the expression, after() : deleteLines() {...} is woven after each joinpoint matched by the PCD. Suppose that we need to write a test case that specifies that the advice is expected to be woven each time deleteLines() of the AspectTetris class is executed. Using JUnit, one would write a test case such as Listing 1. An aspect example extracted from the Tetris system testdL() shown in Listing 2. However, testdL() is not precise enough to specify a joinpoint. The first problem is that if this test case fails, it is not possible to conclude that the failure is caused by a fault in the PCD:

• If += is replaced by = in the advice of aspect
Counter, testdL() will fail, but not because of a fault in the PCD.

• If * is replaced by int in the PCD, testdL() will fail again, this time because of a fault in the PCD.

The second problem is that testdL() will not detect all the faults in the PCD. For example, in Listing 1, if the PCD is replaced by execution( * AspectTetris. * ()), testdL() will pass even though there is a fault in the PCD. This fault is of type 3 as defined in Figure 1, which means that the expected joinpoints are matched, but the PCD also matches unintended joinpoints. To detect that fault, we need to write test cases that specify that no advice should be woven in some places of the code. However, this is not possible to do with test cases such as testdL(). These test cases do not explicitly mention the presence or absence of an advice; they just implicitly assume the presence of an advice. Not allowing explicit mention of an advice is a limitation of JUnit-based unit testing.

In order to experiment with a test-driven approach for PCD validation and overcome the limitations of JUnit, we developed a tool called AdviceTracer. This tool enables us to define an oracle for test cases that explicitly specify the presence or absence of an advice at a specific place in the program.

AdviceTracer

The AdviceTracer tool [START_REF] Delamare | Advicetracer[END_REF] allows a programmer to write test cases that focus on checking whether or not a joinpoint has been matched by the PCD. More precisely, AdviceTracer is used to specify an oracle that expects the presence or absence of an advice at a particular point in the base program. Test cases can specify the PCD without executing the behavior of the advice.

Illustrative example

Listings 3, 4 and 5 illustrate the use of Advice-Tracer. Listing 3 shows a Java class C with two methods m1 and m2; m2 calls m1. Listing 4 shows an Aspect A, in which an annotation has been added in order to name the advice, A1. The advice is woven before the executions of m1 which are in the control flow of m2.

Listing 5 shows two test cases that specify the set of expected joinpoints. In a textual form the specification of the expected joinpoints can be expressed as "the advice A1 should be executed only before the executions of m1 in the control flow of m2". This means that we must specify that the advice A1 is expected when m2 calls m1, and also that it should not be executed when m1 is executed outside the control flow of m2. In a testdriven approach, we need two test cases to specify this.

• test1() specifies that no advices should be executed (line 8) when only m1 is called (line 7). Thus, the test case will pass only if weaving an aspect (here aspect A) does not introduce the exe-

Listing 5. A JUnit test class illustrating how to use AdviceTracer

cution of an advice when executing m1. The test case will fail if a joinpoint of m1 is matched by the advice (unintended joinpoint).

• test2() calls m2 and then specifies (at lines [START_REF] Ye | Tool support for understanding and diagnosing pointcut expressions[END_REF][20] that advice A1 should be executed from a joinpoint at line 2 of C, within m1. So if the test case passes, we know that the advice was executed within the context of execution of m1.

If the PCD of Listing 4 is replaced by execution (void C.m1()), then test1() fails because the advice is executed in this test scenario. If the pointcut is replaced by execution(void C.m2()), then test2() fails although the advice is executed because it is woven within m2 instead of m1.

This example also illustrates how AdviceTracer can handle dynamic PCDs. The PCD of Listing 4 is dynamic: it matches the execution of m1 in the control flow of m2. This kind of PCD can only be resolved at runtime. To specify this PCD we first execute m1 outside the control flow of m2 and check that the advice was not executed (test1 of Listing 5), and then we execute m1 in the control flow of m2 and check that the advice was executed at the correct joinpoint (test2 of Listing 5).

AdviceTracer makes it possible to specify the expected joinpoints in order to check that there are no neglected joinpoints. In such an approach, there must be test cases that specify every place in the base program that should be matched by each PCD.

As shown in test1, it is also possible to write test cases that specify unintended joinpoints. In Section 5.3, we present a strategy to reduce the effort required to write test cases.

Primitive methods of AdviceTracer

The above two test cases illustrate how the primitive methods of AdviceTracer are used. These primitives are of three distinct types: those that start or stop AdviceTracer, those that configure the traced advices, and those that define assertions to specify the oracle.

Starting AdviceTracer.

To start tracing, AdviceTracer must be set on by calling the static method setAdviceTracerOn(). It should be called before calling a method where an advice is expected (or not expected) to be woven. The static method setAdviceTracerOff() stops tracing. Between setAdviceTracerOn() and setAdviceTracerOff(), AdviceTracer stores information about which advices (identified by their name) were executed and where they were executed.

3.2.2.

Restricting the traced advices. Using Advice-Tracer each test can specify the advices to be traced. If a test case does not specify any advice, then all the advices are traced. On lines 5 and 15 of Listing 5, the method addTracedAdvice is called. It adds the advice as a parameter to the collection of traced advices. Another method, setTracedAdvices, specifies a collection of advices to be traced. In listing 5, test1 specifies the absence of the advice A1 and test2 specifies the presence of the advice A1.

The test cases test1 and test2 are said to be modular because they specify a set of joinpoints where a specific advice must or must not be woven. A test case is not modular when it is not specific to a particular advice; it passes as long as an advice is woven (or no advice is woven) instead of passing when a specific advice is woven (or when a specific advice is not woven). Restricting the traced advices improves the modularity of the test cases.

The benefit of modular test cases is that they are less affected by removal or addition of advices in the aspects. They are only affected by changes made in the PCDs of the advices they trace. For instance, if a new advice is woven within C.m1, then the test cases of Listing 5 will still pass because they only consider advice A1.

If the PCD changes, the test case needs to be updated. If the base program changes, we may also need to add more test cases.

Implementation of AdviceTracer

AdviceTracer provides an API consisting of the primitive methods described above and contains an aspect, implemented using AspectJ. The advice in this aspect retrieves the name of the advice that is being traced and the location of the joinpoint that triggered the advice execution. This information is stored in a TraceElement object, which is a pair of strings, one for the advice (e.g., A1) and one for the joinpoint (e.g., C.m1:2). The string for the advice is its name, specified with the @AdviceName annotation. The string for the joinpoint is built with the qualified name of the method and the line number where it is located (separated by the ':' character).

The advice is woven before each joinpoint matched by all the aspects under test (i.e.

before each execution of an advice).

The PCD in the Ad-viceTracer aspect is "adviceexecution()&& ! within(AdviceTracer)". This PCD matches the execution of all the tested advices and not Advice-Tracer's own advice.

All the TraceElement objects are stored in a list that can be retrieved in each test case by calling a static method (getExecutedAdvices). This list is reset each time AdviceTracer is set on, and thus it only contains the TraceElement objects corresponding to the advice execution that were traced be-

Mutation Tool

To validate AdviceTracer, we implemented a mutation tool for PCDs in AspectJ, called AjMutator. This tool is able to automatically insert faults in PCDs to change the set of matched joinpoints. AjMutator inserts seven different types of faults based on seven mutation operators, all defined by Ferrari et al. [START_REF] Ferrari | Mutation testing for aspect-oriented programs[END_REF]. Figure 2 shows the mutation process using AjMutator. AjMutator takes a PCD as input and successively applies different operators to the PCD. Each operator can produce several mutants from a single PCD. In order to run the mutation analysis, these mutant PCDs are then inserted into the aspect to replace the original PCD. One mutant aspect is generated for each mutant PCD.

PCCE
Figure 3 shows the mutation analysis process. First, the mutant is compiled. If the compilation fails, then the mutant is discarded. For example, the PCLO operator can generate mutants that do not compile. For instance, in the NewBlocks aspect of the tetris example, the following PCD is used:

pointcut getBlock(int type) : call (int[][] Blocks.

getBlock(int)) && args(type);

The expression args(type) specifies that the argument of the method is bound to the parameter of the pointcut (type). Replacing the conjunction by a disjunction results in an inconsistent binding and is reported as an error by the AspectJ compiler. The second step of the process checks for equivalent mutants and removes them from the set of mutants to kill. A mutant PCD, p', is equivalent to the initial PCD, p, with respect to the base program, BP, if p' matches exactly the same set of joinpoints as p in BP. The AspectJ compiler, AJDT, provides the API to obtain information on the set of joinpoints matched by p and p'. Then, by comparing these two sets, it is possible to determine if the PCDs are equivalent. Thus, in our case, the detection of equivalent mutants can be automated.

After the set of valid mutants is selected, the test cases are executed with the mutant aspect in the third step of the process. If at least one test case fails, then the mutant is considered "killed", otherwise it is "alive". Thus, unlike classical mutation analysis, a mutant is killed not based on the difference between the behavior of the initial and the mutant program. Instead, we use the oracle of the test cases to kill the mutants. This difference is because of the different goals for mutation analysis. Mutation analysis is generally used to validate the quality of test data, for which the oracle might not be available. In our case, mutation analysis serves a different purpose: it aims at validating the quality of the oracle in test cases that specify intended joinpoints.

Evaluation

We evaluated our approach on two AspectJ systems. For each one we wrote test cases for specifying the different PCDs defined in the aspects. Then we used our mutation tool to insert faults in the PCDs and we checked whether the test cases written with Advice-Tracer can detect the introduced faults.

The auction example is an implementation of an online auction system where users can buy or sell items. This system was developed by the Triskell research group at IRISA. The Reserve aspect allows the user to add an optional and secret reserve price. If the reserve price is not reached at the end of the auction, then the sale is canceled. The AltBid aspect modifies the way that the price is calculated using the second highest bid.

The tetris example is an implementation of the classic video game that was developed by Gustav Ev- ertsson [START_REF] Evertsson | Tetris in AspectJ[END_REF]. The NewBlocks aspect adds new kinds of blocks to the game. The Counters aspect counts the deleted lines and prints them on the game layout. The Levels aspect adds a level system to the game: each time a certain number of lines are deleted, the level is increased and the blocks fall faster. Table 1 shows relevant metrics of the two systems. The auction example has 41 classes and 177 methods, and 16 test cases were written to specify the PCDs (5 test cases to specify the intended joinpoints and 11 to specify the unintended joinpoints). The tetris example has 11 classes and 28 methods, and 41 test cases were written to specify the PCDs (14 test cases to specify the intended joinpoints and 27 to specify the unintended joinpoints).

Results for Mutation Analysis

The operators described in 4 were used to generate mutants. 359 number of mutants were produced, out of which 75 were non-compilable. Out of the remaining 284 mutants, 57 were non-equivalents mutants.

The PWIW operator produced the most mutants (224), but 214 of them are equivalent (only 10 nonequivalent mutants). In most cases, the wildcard introduced by the operator does not allow the selec-tion of more joinpoints. For instance, if call( void AspectTetris.deleteLines()) is replaced by call(void * .deleteLines()), the mutant is equivalent as there is no other class than AspectTetris which has a method called deleteLines that takes no parameter.

Table 2 shows the results of our evaluation. For each aspect, it shows the number of mutants, the number of non-equivalent mutants, and the number of mutants killed.

In the Auction system, 31 mutants were produced for the Reserve aspect, and 10 of them are nonequivalent. 64 mutants were produced for the AltBid aspect, with 13 non-equivalent mutants. All the nonequivalent mutants were killed by the test cases.

Int Tetris, 72 mutants were produced for the New-Blocks aspect, with 7 non-equivalent mutants. 51 mutants were produced for the Counters aspect, with 15 non-equivalent mutants. For the Levels aspect, 66 mutants were produced, and 12 of them were nonequivalents. All the non-equivalent mutants were killed by the test cases.

These results show that test cases written using Ad-viceTracer are actually able to detect faults in the PCD, and thus such test cases can specify PCDs in a testdriven approach.

Table 3 shows the results of the mutation analysis with only the test cases for the intended joinpoints. The results for Tetris are the same as in Table 2, which means that the test cases for the intended joinpoints can kill all the mutants of Tetris. For the Reserve aspect, 92.3% of the mutants are killed, and for the AltBid, 80% of the mutants are killed.

The 3 mutants that are not killed were generated by the PWIW operator. This operator only produces mutants with unintended joinpoints, so usually mutants generated by this operator cannot be detected by test cases for intended joinpoints.

These results allow one to find a tradeoff between the testing effort and the level of confidence in the PCD. Writing only the test cases for intended joinpoints is usually a limited effort and this can guarantee that the PCD matches at least these joinpoints. Of course, to validate that the PCD matches only those joinpoints, it is necessary to write more test cases. In section 5.3 we discuss a strategy to reduce the cost of generation of these test cases.

Evaluation of the AdviceTracer Framework

In section 2 we explained why JUnit was not well adapted for a test-driven development of PCDs. Here, we discuss how AdviceTracer is actually better suited for the development of test cases that specify expected joinpoints.

Consider the aspect Counter shown in Listing 1. With AdviceTracer, we can specify the expected set of joinpoints with testdL1() and testdL2() shown in Listing 6. These test cases capture the intent of the specification more precisely than testdL() of Listing 2.

AdviceTracer can make precise oracles that specifically target the PCDs. There are three points that make test cases made with AdviceTracer more precise than regular JUnit test cases:

• Test cases written with AdviceTracer do not fail because of a fault in the advice. If, on line 10 of Listing 1, += is replaced by =, testdL1 and testdL2 pass but testdL does not.

• Test cases written with AdviceTracer make fault localization easier. If testdL1 fails, we know there is a fault in the PCD that produced a neglected joinpoint. If testdL2 fails, we know there is a fault in the PCD that produced an unintended joinpoint. If testdL fails, we only know that there is a fault, most likely localized in the PCD or in the advice.

• Test cases written with AdviceTracer are more modular. The success of testdL1 and testdL2 only depends on one PCD, changes made on other aspects do not affect them. New aspect, or changes within the advice A1 could change the result of testdL, even if the PCD is unchanged.

Strategy for specifying the unintended joinpoints

Unit test cases are well suited for the specification of intended joinpoints since they target single methods and intended joinpoints are defined at the level of a single method. However, unit test cases might not be as well adapted for the specification of unintended joinpoints. In that case, it is necessary to write unit test cases for each method where no joinpoint is expected. This can require a large number of unit test cases since for most PCDs, the number of intended joinpoints is small.

We need a strategy for specifying the unintended joinpoints that can save time and drastically reduce the number of required test cases. Our strategy is to use system test cases for specifying unintended joinpoints. These test cases cover a greater part of the program, thereby reaching a larger number of unintended joinpoints with less effort. However, system test cases might also cover intended joinpoints. In that case, the oracle needs to check that every executed advice corresponds to an intended joinpoint, otherwise the test case fails. This kind of test cases actually only specify unintended joinpoints. If there are neglected joinpoints and no unintended joinpoints, these test cases will pass. However, if advices are executed at unintended joinpoints by these test cases, then they fail.

This strategy reduce the cost of writing test cases for the unintended joinpoints. It allowed us to write only a few test cases specifying unintended joinpoints, 11 for Auction and 24 for Tetris.

Related work

Ye et al. [START_REF] Ye | Tool support for understanding and diagnosing pointcut expressions[END_REF] tackle the issue of correctness of a PCD. They propose tools to assist developers in diagnosing faults and fixing PCDs. First, according to a PCD, they compute a set of joinpoints that are almost matched by this PCD. This means they compute the set of joinpoints that would be matched if the PCD was slightly different. That way, a developer who analyzes these joinpoints can check whether he/she expected one of these joinpoints to be matched. If this is the case, then the PCD must be fixed. For this step, Ye et al. also propose a tool that can explain why a joinpoint is not matched by the PCD.

The solution proposed by Ye et al. to tackle the problem of faulty PCDs is thus different from our approach. Instead of specifying the set of expected joinpoints a priori, they provide assistance for manual inspection by the developer. The benefit of their approach is that it does not require additional work from the developer. In case the aspects evolve, with this approach the developer has to manually check all the PCDs to be sure that there are no regressions. With our approach the developer can run all the test cases again. If a new advice is added, new test cases must be added to check its PCD. If existing PCDs are modified, the test cases for that PCD must be changed. All the other test cases remain unchanged.

There exist several works related to mutation analysis in the context of AOP. McEachen et al. [START_REF] Mceachen | Distributing classes with woven concerns: an exploration of potential fault scenarios[END_REF] and Baekken et al. [START_REF] Baekken | A candidate fault model for AspectJ pointcuts[END_REF] propose several fault models. These works analyze aspect-oriented languages and identify AOP-specific faults that can occur. In particular, Baekken et al. focus on different categories of faults that can occur in PCDs. Anbalagan et al. [START_REF] Anbalagan | Efficient mutant generation for mutation testing of pointcuts in aspect-oriented programs[END_REF] also propose mutation analysis of the PCD. Like Ye et al., they also associate a notion of similarity with the initial PCD to select a subset of the mutants and limit the cost of mutation analysis. Ferrari et al. [START_REF] Ferrari | Mutation testing for aspect-oriented programs[END_REF] analyze the different faults models previously proposed for AOP and study how they map on to different languages for aspect-oriented programming.

Another work related to our approach is proposed by Sakurai et al. [START_REF] Sakurai | Test-based pointcuts for robust and fine-grained join point specification[END_REF], who propose to describe pointcuts in unit test cases. Although this approach at first glance appears to be similar to our work, it is actually different. They propose a new language for pointcut description based on unit test cases. Here the test cases are not meant to validate a pointcut described as a regular expression. Instead, they are meant to replace the regular expression. This should allow PCDs to be more robust with respect to evolution. However, these PCDs can still be erroneous and the authors do not tackle the issue of the correctness of their PCDs.

Other work on testing aspect-oriented programs focus on other aspects of the testing activity. In particular, some works have focused on unit testing in AOP and regression testing when the base program or aspects evolve.

Xu et al. [START_REF] Xu | Regression test selection for As-pectJ software[END_REF] tackle the issue of regression test selection for AOP. They extended a technique for Java introduced by Harrold et al. [START_REF] Harrold | Regression test selection for java software[END_REF] to take aspects into account. Based on the comparison of the control-flow graphs for test cases on the program before and after evolution, they identify the subset of test cases that must be executed for regression testing.

Xie et al. [START_REF] Xie | A framework and tool supports for generating test inputs of AspectJ programs[END_REF] focus on the automatic generation of test data for aspect-oriented programs. Their framework, called Aspectra, focuses on the validation of the behavior implemented in the advice. This tool leverages existing tools for automatic generation of test data for Java programs. A major issue of automatic test data generation is that the number of generated data can be large. To tackle this issue, Xie et al. [START_REF] Xie | Detecting redundant unit tests for AspectJ programs[END_REF] introduced a framework for detecting redundant unit tests in AspectJ programs. The proposed framework removes the test cases that do not exercise a new behavior.

Xu et al. [START_REF] Xu | State-based incremental testing of aspect-oriented programs[END_REF] propose a model-based testing approach for AOP. The behaviors of the base program and the advices are modeled with statecharts. The authors merge these statecharts and generate test data to cover the paths in the composed statechart that correspond to interactions between the base program and the advice.

Lopes et al. [START_REF] Lopes | Unit testing aspectual behavior[END_REF] focus on unit-testing the advices. Their approach relies on JAML (Java Aspect Markup Language), an aspect language for Java where the advices are implemented in regular Java classes and the PCDs are described in XML. This allows advices to be called as regular methods, and thus to be unit-tested. They also provide JamlUnit, a JUnit extension to test JAML advices.

Conclusions and Future Work

Pointcut descriptors in aspects are critical because they specify the locations where a cross-cutting concern should be woven in a program. However, as pointed out by several papers on AOP testing, these pointcut descriptors are fault-prone and should, thus, be tested. In this paper we identified two major issues related to testing PCDs: the lack of specification for intended joinpoints and the limitations of JUnit for explicitly asserting the presence or absence of an advice at a specific point in the program.

We proposed a test-driven approach for the development of PCDs. This approach allows us to tackle the issue of lack of specification; in our approach the test cases become the specification of the intended joinpoints. We also developed a tool called AdviceTracer that provides an API to testers so that they can define oracles that explicitly specify an expected joinpoint or the expected absence of a joinpoint.

AdviceTracer collects trace information that can also be used to debug aspect-oriented programs. Another possible way to use AdviceTracer is to assess change impact through dynamic analysis during the evolution of base program and the aspects.

A second contribution of this work is the development of mutation tool for PCDs. Based on mutation operators defined in other works, AjMutator automatically generates mutants for a PCD. We used this tool to validate that the test cases developed using Advice-Tracer can actually detect faults in PCDs. While experimenting with our test-driven approach, we observed that unit test cases are indeed able to specify the intended joinpoints and that these test cases can detect faults in the PCDs. Moreover, we observed that unit test cases that specify unintended joinpoints also detect faults in PCDs, but this requires a large number of unit test cases. The experiments also allowed us to validate that AdviceTracer is better suited to a test-driven development of PCDs than plain JUnit.

In the future, we will investigate the ability of Ad-viceTracer to detect other types of faults that could not be injected in the systems studied here. We also want to study how such a test-driven approach for PCDs can help detect faults when the base code evolves. Another point that could be explored is a way to adapt existing test cases, in particular system tests, in order to reduce the effort required to specify unintended joinpoints.

Figure 1 .

 1 Figure 1. The four types of PCD faults

Figure 3 .

 3 Figure 3. The mutant evaluation process

PWIW:

  Pointcut weakening by inserting wildcards into the PCD. The PWIW operator replaces an identifier in the PCD by a wildcard ('*'). It weakens the PCD (i.e., it becomes more general) and only produces unintended joinpoints -type (3) fault of Figure 1.

Listing 2. A JUnit test class for the Counter aspect

	1 public class TestCounter {
	2	@Test
	3	public void testdL() {
	4	AspectTetris tetris = new
		AspectTetris();
	5	tetris.startTetris();
	6	tetris.deleteLines();
	7	assertEquals(tetris.totalLines,1);
	8	}
	9 }
	1 public class C {
	2	public void m1() { ... }
	3	public void m2() {
	4	...
	5	m1();
	6	}
	7 }

Listing 3. A Java class example

  : Pointcut changing by switching execution/ call PCDs. The PCCE operator replaces a call PCD by an execution PCD or vice versa. It changes the context where the advice is woven (with a call PCD, the advice is woven where the method is called, with an execution PCD, the advice is woven in the method). It produces both neglected and unintended joinpoints -type (1) fault.PCGS : Pointcut changing by switching get/ setPCDs: The PCGS operator replaces a set PCD by a get PCD or vice versa. It produces both neglected and unintended joinpoints.

	PCLO : Pointcut changing by changing logical opera-
	tors. This operator replaces a conjunction ('&&')
	by a disjunction ('||') or the contrary. It produces
	type (3) and type (2) faults, respectively.
	PCTT : Pointcut changing by switching this/
	target PCDs. The PCTT operator replaces a
	this PCD by a target PCD. It produces type
	(1) faults.
	POEC : Pointcut weakening or strengthening by
	changing exception throwing clauses. The POEC
	operator adds, removes or changes the throwing
	clauses in the PCDs that specify a method. It pro-
	duces neglected and/or unintended joinpoints.

POPL : Pointcut weakening or strengthening by changing parameter lists. The POPL operator adds, removes or changes the parameters in the PCDs that specify a method or a constructor. It produces neglected and/or unintended joinpoints.

Table 1 . Metrics for Auction and Tetris

 1

				# Test Cases
	System # Class # Method	(Intended/
				Unintended)
	Auction	41	177	16 (5/11)
	Tetris	11	28	41 (14/27)

Table 2 . Mutation scores for PCDs in Tetris and

 2

	Auction
	Mutants Non-Eq Killed	%
		Auction
		Reserve
	31	10	10	100%
		AltBid
	64	13	13	100%
		Tetris
		NewBlocks
	72	7	7	100%
		Counters
	51	15	15	100%
		Levels
	66	12	12	100%

Table 3 . Results for Auction with only the test cases for the intended joinpoints

 3

	Mutants Non-Eq Killed	%
		Reserve
	64	13	12	92.3%
		AltBid
	31	10	8	80%

A JUnit test class for the Counter aspect

	1 public class TestCounter2 {
	2	@Test
	3	public void testdL1() {
	4	AspectTetris tetris =
	5	new AspectTetris();
	6	tetris.startTetris();
	7	addTracedAdvice("deleteLines");
	8	setAdviceTracerOn();
	9	tetris.deleteLines();
	10	setAdviceTracerOff();
	11	assertAdviceExecutionsEquals(1);
	12	assertExecutedAdviceAtJoinpoint(
	13	"deleteLines",
	14	"AspectTetris.deleteLines:23");
	15	}
	16
	17	@Test
	18	public void testdL2() {
	19	AspectTetris tetris =
	20	new AspectTetris();
	21	tetris.startTetris();
	22	addTracedAdvice("deleteLines");
	23	setAdviceTracerOn();
	24	tetris.gameOver();
	25	setAdviceTracerOff();
	26	assertAdviceExecutionsEquals(0);
	27	}
	28 }
	Listing 6.