Specification-Based Test Selection in Formal Conformance Testing

Reference:

Tuomo Pyhälä. Specification-based test selection in formal conformance testing. Research Report A93, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, August 2004.

Abstract:

More complex systems require more efficient quality assurance. Testing is a often used method to achieve this goal. In this work we consider formal conformance testing, which is a field where formally defined conformance between specifications and implementations is studied. In practice this allows the construction of automated testing tools having a solid theoretical foundation and being able to automatically test whether an implementation conforms to its specification.

Test selection refers to the process of trying to select, from a potentially very large set of possible test cases, the tests which most efficiently test the implementation. We consider a set of tests to be efficient, if it tests a large proportion of the implementation behaviou r without containing too much redundancy. The proposed test selection method is based on the assumption that the implementation resembles the specification. Therefore, by this assumption, having tested a large proportion of the specification behavior we have also tested a large proportion of the implementation behavior.

To capture our notion of a large proportion of the specification behavior, we formally define a specification-based coverage framework, including several coverage metrics of different levels of granularity. We refine an existing conformance testing algorithm to include the specification coverage based test selection methods based on the framework. The algorithm and the coverage metrics are tied together by a heuristic aiming to increase the coverage metrics. Finally, we implement a tool incorporating the discussed algorithms and make a number of experiments with the tool.

Keywords:

formal conformance testing, test selection, on-the-fly testing, specification-based coverage

Suggested BibTeX entry:

@techreport{HUT-TCS-A93,
    address = {Espoo, Finland},
    author = {Tuomo Pyh\"al\"a},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {August},
    number = {A93},
    pages = {56},
    title = {Specification-Based Test Selection in Formal Conformance Testing},
    type = {Research Report},
    year = {2004},
}