Test Case Generation for Programming Language Metamodels

Abstract

for Software Language Engineering 2010 Doctoral Symposium

-

One of the central themes in software language engineering is the speci cation of programming languages, and domain-speci c languages, using a metamodel. This metamodel provides a greater degree of abstraction than a context-free grammar, since it can ignore syntactic details. However, its main bene t is in providing for the speci cation of the abstract syntax graph of a language, and this can then be used for the construction or generation of language processing tools.

One problem associated with the use of programming language metamodels, and metamodels in general, is determining whether or not they are correct. Of course, one approach is to forward engineer code and test this, but it should also be possible to test the metamodel directly. In this context, the question addressed by our research is: given a programming language metamodel, how can we generate an appropriate test suite to show that it is valid?

Being able to generate such a test suite would have two main bene ts. First, examining the automatically-generated test cases would help to develop the modeller's understanding of the metamodel, and help to increase con dence in its validity. Second, since the metamodel speci es a programming language, the generated test cases should be valid programs from that language, and these can be used as test inputs for tools that process the language.

Related work

Testing a programming language speci cations, at least at the syntactic level, has a long history, dating back at least to the work of Purdom on generating test cases from grammars [ 1 ]. However, a naive application of Purdom's approach to a programming language grammar produces programs that may not be syntactically correct (since the grammar may under-specify), and is certainly unlikely to produce semantically valid (let alone meaningful) programs [ 2 ]. ? This work is supported by a John & Pat Hume Scholarship from NUI Maynooth.

Incorporating at least a language's static semantics into test suite generation must go beyond simple context-free grammars. One possible approach is to use attribute grammars, and to seek to exploit the attribute equations to constrain or even direct the generation of test cases [ 3, 4 ]. Despite this research, it is still not a trivial task to directly extend this work to a metamodelling environment that uses, for example, OCL-like constraints for describing the static semantics.

It is possible to borrow some ideas from software modelling, and there is a great deal of existing research dealing with model-based testing strategies [ 5, 6 ]. However, much of this work focuses on the behavioural elements of software models (such as state machines), rather than the structural aspects which might be more relevant to metamodelling.

In the context of testing structural models, two tools strike us as being particularly noteworthy: { USE (a UML-Based Speci cation Environment) which allows the user to specify a UML (Uni ed Modeling Language) class diagram with OCL constraints [ 7 ]. From these we can manually generate corresponding object diagrams, and the USE environment will check that these are valid instances, satisfying the relevant class invariants. { Alloy which has its own logical speci cation language, corresponding roughly to the elements found in a class diagram, and automatically generates object diagrams that correspond to this speci cation [ 8 ]. One of the useful aspects of the Alloy tool is that it is designed to work with a number of di erent SAT solvers in order to test constraints and generate counter-examples.

As part of an earlier project, we have previously exploited the close relationship between the Alloy notation and UML class diagrams to generate instances of a metamodel for software metrics [ 9 ]. One of the drawbacks of this earlier approach is that it did not control the strategy used to generate instances. Faced with the impossibility of manually validating several hundred thousand instances, we exploited test-suite reduction techniques to narrow the set of test cases. 3

Proposed Solution

It is clearly ine cient to generate test cases that are not used, and an ideal solution would be to generate an appropriate set of test cases in the rst place. Of course, this immediately raises two questions: what do we mean by an appropriate set of test cases, and how do we generate these test cases?

One way of measuring the adequacy of a set of test cases for a piece of software is to use coverage criteria. Typically, a test suite can be judged in terms of the percentage of statements, decisions, branches etc. in the source code that are executed when the software is run. It seems natural therefore to attempt to seek to assemble a test suite for a metamodel along similar lines, i.e. to form a set of models that cover the features of the metamodel. In terms of programming language metamodels, this would involve creating a set of programs that exercise the features of the language.

Since most metamodels, including programming language metamodels, are described using UML, it is possible to use UML techniques to compute their coverage. Many coverage criteria for the various UML diagrams have been proposed [10{13]. However, we restrict our attention to UML structural diagrams, since metamodels are often presented in the form of UML class diagrams.

Our recent work has focused on coverage criteria for UML class diagrams initially proposed by Andrews et al. [ 14 ], speci cally: { Generalisation coverage which describes how to measure inheritance relationships. { Association-end multiplicity coverage which measures association relationships de ned between classes. { Class attribute coverage which measures the set of representative attribute value combinations in each instance of class.

It is unlikely that these alone will provide su cient granularity to determine the adequacy of a test suite, and previous work has already determined that there is a poor correlation between coverage of syntactic and semantic features [ 15 ]. However, our immediate work has centred on constructing an extensible, modular system that can at least measure these levels of coverage, and which can be used as a basis for further studies. 4

Research Method

Our research can be broken down into three phases: Phase I: calculating coverage measures for programming language metamodels, Phase II: generating valid models that satisfy coverage criteria, Phase III: generating models satisfying criteria not based on coverage.

In our work to date we have constructed a tool-chain which, when given a UML class diagram and a set of UML object diagrams, will calculate the three coverage measures described above [ 16 ]. The tool chain uses the USE tool as a parser and validator for the class and object diagrams, and uses the Eclipse Modeling Framework (EMF) to represent these as instances of the UML metamodel. To represent the output we have built a coverage metamodel in EMF which is essentially an extension of an existing metrics metamodel [ 17 ]. Finally, we have written a transformation to calculate the coverage measures using ATL (ATLAS Transformation Language).

In order to complete the rst phase we intend to extend the coverage measures for class diagrams to deal with the associated OCL constraints. We intend to use (OCL) decision coverage as our initial measure, and to extend our tool chain to implement this coverage.

In the next phase, we hope to generate valid models that satisfy coverage criteria for at least one programming language metamodel. We are currently studying Alloy's approach as a model of exploiting third-party SAT solvers to control model generation.

At the nal phase of our research we hope to expand this approach to other language-based criteria. To do this, we intend to use OCL-based queries across the metamodel to specify the kind of model to be generated. Ideally, this would allow a user to specify the kind of programs that would be generated in the test suite for a given language metamodel.

References

1. Purdom , P.: A sentence generator for testing parsers . BIT 12 ( 3 ) ( 1972 ) 366 { 375

2. Malloy , B.A. , Power , J.F. : An interpretation of Purdom's algorithm for automatic generation of test cases . In: 1st Annual International Conference on Computer and Information Science , Orlando, Florida, USA (October 3-5 2001 )

3. Lammel, R.: Grammar testing . In: Fundamental Approaches to Software Engineering. Volume 2029 of Lecture Notes in Computer Science., Springer Verlag ( 2001 ) 201 { 216

4. Lammel, R., Schulte , W. : Controllable combinatorial coverage in grammar-based testing . In: 18th IFIP TC6/WG6.1 International Conference on Testing of Communicating Systems , New York, NY (May 2006 ) 19 { 38

5. Pilskalnsa , O. , Andrews , A. , Knight , A. , Ghosh , S. , France, R.: Testing UML designs. Information and Software Technology 49 ( 8 ) ( August 2007 ) 892 { 912

6. Utting , M. , Legeard , B., eds.: Practical Model-Based Testing . Elsevier ( 2007 )

7. Gogolla , M. , Buttner, F. , Richters , M.: USE: A UML-based speci cation environment for validating UML and OCL . Sci. Comp. Prog. 69 ( 1-3 ) ( 2007 ) 27 { 34

8. Jackson , D. : Software Abstractions. MIT Press ( 2006 )

9. McQuillan , J.A. , Power , J.F. : A metamodel for the measurement of object-oriented systems: An analysis using Alloy . In: IEEE International Conference on Software Testing Veri cation and Validation , Lillehammer, Norway (April 9-11 2008 ) 288 { 297

10. McQuillan , J. , Power , J.: A survey of UML-based coverage criteria for software testing . Technical Report NUIM-CS-TR-2005-08 , NUI Maynooth ( 2005 )

11. Dinh-Trong , T.T., Ghosh , S. , France, R.B.: A systematic approach to generate inputs to test UML design models . In: 17th International Symposium on Software Reliability Engineering , Raleigh, NC ( 2006 ) 95 { 104

12. Mahdian , A. , Andrews , A.A. , Pilskalns , O. : Regression testing with UML software designs: a survey . J. of Software Maintenance and Evolution: Research and Practice 21 ( 4) (July/August 2009 ) 253 { 286

13. Briand , L. , Labiche , Y. , Lin , Q. : Improving the coverage criteria of UML state machines using data ow analysis . Soft. Test. Verif. & Reliability 20 ( 2010 )

14. Andrews , A. , France, R. , Ghosh , S. , Craig , G.: Test adequacy criteria for UML design models . Soft. Test. Verif. & Reliability 13 ( 2 ) (April/June 2003) 95 { 127

15. Hennessy , M. , Power , J.F. : Analysing the e ectiveness of rule-coverage as a reduction criterion for test suites of grammar-based software . Empirical Software Engineering 13 ( 4 ) ( August 2008 ) 343 { 368

16. Wu , H. , Monahan , R. , Power , J.F. : Using ATL in a tool-chain to calculate coverage data for UML class diagrams . In: 2nd International Workshop on Model Transformation with ATL , Malaga, Spain ( June 2010 )

17. Vepa , E.: ATL transformation example: UML2 to Measure . Available on-line as http://www.eclipse.org/m2m/atl/atlTransformations/# UML22Measure (August 30 2007 )