Testing is increasingly recognised as a crucial part of the software development process and one which is important for almost all forms of software. Unfortunately, testing is also a hard problem, not least because of the difficulty in automating the identification of high quality test data. The TeTra project will be concerned with the problem of automatic generation of test data using evolutionary testing techniques, based upon white box (or structural) test adequacy criteria. In particular the project will focus upon branch and condition-based coverage criteria, which are currently regarded as an industry standard [3] and which are mandatory for many applications, for example avionics [12].
Branch coverage criteria require that a test set contains, for each feasible branch of the program under test, at least one test case which causes execution to traverse the branch. Unfortunately, automatically generating test data which have this property is not generally computable, and so research and development have focused upon techniques which aim to optimise test data with respect to such a criterion. One such optimisation technique which has been of particular recent interest has been Evolutionary testing [6,7,8,9,10,11,14,17,18]. Evolutionary testing uses metaheuristic search based techniques1to find good quality test data. Test data quality is defined by a test adequacy criterion, which underpins the fitness function which drives the search implemented by the genetic algorithm.
For structural criteria, such as those which will be of importance for the TeTra project, a fitness function is typically defined in terms of the program's predicates. It determines the fitness of candidate test data, which in turn, determines the direction taken by the search. The fitness function essentially measures how close a candidate test input drives execution to traversing the desired (target) path. The TeTra project will reformulate program transformation to overcome remaining barriers to wider application of structural evolutionary test data generation. Previously transformation has been applied to many problems including automatic parallelization [13,19], program comprehension [2,16], reverse and re-engineering [15], efficiency improvement [1] and (by the proposers, using slice-based transformations) to testing [4,5]. However, TeTra will be the first to apply transformation to the test data generation problem.