Testing from Structured Algebraic Specifications: The Oracle Problem

摘要

Work in the area of specification-based testing has pointed out that testing can be effectively used to verify programs against formal specifications. The aim is to derive test information from formal specifications so that testing can be rigorously applied whenever full formal verification is not cost-effective. However, there are still several obstacles to be overcome in order to establish testing as a standard in formal frameworks. Accurate interpretation of test results is an extremely critical one. ududThis thesis is concerned with testing programs against structured algebraic specifications where axioms are expressed in first-order logic with equations, the usual connectives and quantifiers. The main issue investigated is the so-called oracle problem, that is, whether a decision procedure can be defined for interpreting the results of tests according to a formal specification. In this context, testing consists in checking whether specification axioms are satisfied by programs. Consequently, tests exercise operations referred to by the axioms and oracles evaluate the axioms according to the results produced by the tests. ududThe oracle problem for flat (unstructured) specifications often reduces to the problem of comparing two values of a non-observable sort, namely the equality problem, and also how to deal with quantifiers which may demand infinite test sets. Equality on non-observable sorts is interpreted up to behavioural equivalence with observational equivalence as an important special case. However, a procedure for implementing such a behavioural equality may be hard to define or even impossible. In this thesis, a solution to the oracle problem for flat specifications is presented which tackles the equality problem by using a pair of approximate equalities, one finer than behavioural equality and one coarser, and taking the syntactic position of quantifiers in formulae into account. ududAdditionally, when structured specifications are considered, the oracle problem can be harder. The reason is that specifications may be composed of parts over different signatures, and the structure must be taken into account in order to interpret test results according to specification axioms. Also, an implementation of hidden (non-exported) symbols may be required in order to check axioms which refer to them. Two solutions to the oracle problem for structured specifications are presented in this thesis based on a compositional and a non-compositional style of testing, namely structured testing and flat testing respectively. Structured testing handles the oracle problem more effectively than flat testing and under fewer assumptions. ududFurthermore, testing from structured specifications may require an approach which lies in between flat and structured testing. Therefore, based on normalisation of ordinary specifications, three normal forms are presented for defining a more practical and combined approach to testing and also coping more effectively with the oracle problem. The use of normal forms gives rise to a style of testing called semi-structured testing where some parts of the specification are replaced by normal forms and the result is checked using structured testing. Testing from normal forms can be very convenient whenever the original specification is too complex or oracles cannot be defined from it.