Software QA FYI - SQAFYI

Testing with Axioms in C++ 2011

By: Anya Helene Bagge, Valentin David, Magne Haveraaen

Abstract Unit testing is an important part of modern software development, where individual code units are tested in isolation. Such tests are typically case-based, checking a likely error scenario or an error that has previously been identified and fixed. Coming up with good test cases is challenging, particularly when testing generic code, and focusing on individual tests can distract from creating tests that cover the full functionality. Concepts provide a generic way of describing code interfaces for generic code. Together with axioms, program behaviour can be specified algebraically in a formal or semi-formal way.

In this paper we show how concepts and axioms can be expressed in standard C++ 2011, and explore how to generate generic unit tests, by treating the axioms as code to be evaluated with test data. We also show a generic way to generate test data for axiom-based testing in C++ 2011.

Keywords Algebraic Specification; Axiom-Based Testing; Axioms; C++;
C++0x; C++11; Concepts; Generative Programming; Mouldable Programming;

Test Generation; Unit Testing
1 Introduction
Modern software engineering practises encourage the use of unit testing to increase software reliability. Test-driven development (TDD) [Bec02] dictates that software should be extended by writing tests for a new feature first, before implementing the feature. The tests provide a specification of the behaviour of the new feature, and provide an easy way to check the implementation throughout development and refactoring.

Less extreme methods call for tests for all program units, and for regression tests to be written to ward off the reappearance of known bugs. Such methods may be practised rigorously, or in an ad hoc manner. Common to all is that they rely on the programmer to invent good test cases that cover both likely and unlikely errors. The programmer must also be careful that the tests exercise the full expected feature set, or the implementation will seem OK when all it does is implement the bare minimum to pass the tests.

1.1 Testing with Concepts and Axioms
We suggest writing tests based on axioms that formally specify expected behaviour, rather than relying on ad hoc test cases. We integrate axioms with concepts that describe code interfaces basically, the types and operations that a program module supports. Axiom-based testing provides reusable tests for implementations of concepts. Also, by stating the requirements of generic code in terms of concepts, we know what behaviour we must test for in arguments given to generic code. Testing an implementation consists of stating (and checking) that it conforms to the interface of the given concept, then generating suitable test data, and finally evaluating the axioms for the generated test data values using the implementation. If any of the axioms evaluate to false, the implementation does not satisfy the concept specification which may mean that the implementation is buggy, or that the specification is wrong; if the results are to be reliable, the axiom must correctly express the desired feature.

1.2 Concepts in C++ 2011 Concepts were proposed for inclusion in the C++111 standard as a modularisation feature for generic programming. Concepts were designed to solve the problem of incomprehensible error messages from deep inside C++ template code, providing a sort of bounded polymorphism to the otherwise duck typed (at compile time) template system, similar to how type classes work in Haskell [HHPW96]. The proposal also allowed for axioms in concepts, opening the way to axiom-based optimisation [TJ07, BH09] and testing [BDH09]. However, concepts were dropped [Str09] from the draft standard [B+11b] before finalisation.
Since the proposed C++ standard no longer provides for concepts and axioms, our approach has changed since our original implementation of axiom-based testing for C++ [BDH09]. We now provide a library, Catsfoot, which adds alternative concept support to C++11 as well as support for generating axiom tests, all using template meta-programming. While we previously had to rely on an external tool to support test generation, with limited C++ support, this is no longer necessary. Our contributions in this article include:
 a technique and library for testing with concepts and axioms in C++11,
 a library for using concepts in C++11, and
 a generic test data generation library to be used with axiom-based testing.

Our Catsfoot concept library supports most of the features of the previous C++0x draft [GSSW08] (with the exception of archetypes), though in this paper we will focus mainly on using it for axiom-based testing, leaving the rest for a future paper. Further information on the concept library, as well as the full source code released under the GNU LGPL license, is available at http://catsfoot.sourceforge.
net/ [Dav11].
We have tested all code examples in this paper with GCC 4.5.2 and 4.6.0 (with the exception of one example, which does not run on current compiler releases). The file containing the examples can be obtained from the website.

Full article...

Other Resource

... to read more articles, visit

Testing with Axioms in C++ 2011