Dr.-Ing. Norbert Oster, Akad. ORat - DOTgEAr

imageLocal UnivIS administration, Scientific Staff
Office hour:
    by arrangement, Room 05.158, (Anmeldung bitte per Mail)


Automatic Dataflow-oriented Test Case Generation for Object-oriented Software Systems by Evolutionary Algorithms


Short introduction:

In spite of remarkably improved methods in software development, the increasing complexity of modern software systems still represents a main hindrance towards fault-free software development. Size and budget of today's projects mostly forbid a complete formal verification, which in turn covers only the logical domain of the code but not the real environment, even in cases where verification is feasible. On this account, testing is still considered to be an important means of quality assurance previous to the final release. In order to increase the chances of revealing faults during the testing phase, test cases are selected according to different strategies: for functional testing, inputs are derived from the specified requirements, whilst for structural testing the code has to be executed as exhaustively as possible. In consequence of the complexity of the control structures, the identification of test data allowing to achieve high dataflow coverage is exceedingly time consuming. Checking the correctness of the test results has usually to be carried out by hand and therefore requires a high amount of effort. Therefore, the overall number of test cases is crucial, even if their generation can be performed at low cost, e. g. by means of a random generator.
The aim of the ongoing research project is to automate the generation of adequate sets of dataflow-oriented test cases and to evaluate the adequacy of different techniques with respect to both quality achieved and effort required. In various application areas evolutionary algorithms have revealed as providing suitable search and optimisation strategies. Previous related investigations based on genetic algorithms were restricted to simple control flow criteria (statement and branch coverage), to special purpose programming languages or to language subsets hardly transferable to real projects.

Accomplished Milestones:

  • Dynamic analysis of test execution
    In order to identify the definition/use-pairs actually covered during the execution of a test case, a tool for monitoring the dynamic execution of a program has been developed. It is intended to instrument the test object in such a manner that all relevant dataflow information is logged during each test run. The results were published on the occasion of the international conference PSAM7/ESREL'04.
  • Global optimisation of test sets
    Based on the dynamic assessment of the coverage achieved by a test set, a procedure has been developed aiming at generating an optimal set of test cases using evolutionary algorithms. The fitness function for evaluating each test set depends both on the number of covered dataflow pairs (see dynamic analysis) and on the size of the test set. For this reason the task is considered as a global optimisation problem independent from the control flow structure of the test object. For the actual generation of the test data, different genetic operators were developed to be used in parallel in the context of adaptive evolutionary algorithms. The different options were implemented and evaluated in a parallelized distributed toolset. Details were published by the TAV subgroup of the GI.
  • Static analysis of the test object
    The evaluation of the results determined by the evolutionary algorithm requires the knowledge of both the coverage actually achieved (see dynamic analysis) and the coverage attainable. For this purpose a static analyzer has been developed, which locates the respective definitions and uses of each variable in the data flow graph (and all the DU-paths between those pairs). Together with the results achieved by the dynamic analysis, the static analysis is meant to provide a better stopping criterion for the global optimisation and to support the local optimisation described in the following.
  • Assessing the fault detection capability of the automatically generated test cases
    In addition to the mere evaluation of the relative goodness of a test set in terms of coverage (see static analysis), an estimation of the quality of the automatically generated test cases based on their fault detection capability has been developed as part of this project. For this purpose, a back-to-back-testing approach based on the principles of mutation testing has been implemented, i.e. representative faults are injected into the original program and the behaviour of the modified and original variant is compared when executed with the test cases generated. The ratio of modified programs behaving differently than the original is an indicator of the fault detection capability of the test set. The results of the last two sub tasks were published on the occasion of the international conference SOQUA 2005.
  • Adding support for additional testing strategies
    The developed technique of multi-objective generation and optimisation of test cases can be applied to other testing strategies as well. Choosing coverage criteria, which are orthogonal to the data flow oriented strategies under consideration, is expected to help in detecting additional fault types. As part of a sub-project, an approach to the static analysis of the test object and dynamic analysis of the test execution has been developed and implemented for the condition coverage criteria. In an additional sub-project, support for the structural equivalence class and boundary testing criterion has been implemented, which is expected to provide an additional fault detection in combination with the existing criteria.
  • Extending the approach with automatic test driver generators
    Because the automated generation of test cases requires specialised test drivers, which provide limited suitability for the manual validation of the test results, a two-step automatic generation of test drivers has been implemented as part of a sub-project. This generator first creates parametrizable test drivers, intended to be used during the optimisation of test cases only, and finally translates them to the wide-spread jUnit-syntax, as soon as the generated and optimised test data is available.
  • Experimental evaluation of the tool developed
    The practical applicability of the approach developed has been assessed and evaluated in different experimental setups. Java packages with up to 27 classes (5439 lines of code) were used as test objects. The distributed execution of test cases during the generation and optimisation of the test cases was parallelised on up to 58 networked computers. The results were published on the occasion of the international conference SAFECOMP 2006.

Planned Milestones:

  • Extending the functionality of the automated generation procedure
    In addition to the testing criteria from the family of control and data flow based strategies already supported, the method and the tool implemented will be extended with further testing techniques. On the basis of the procedures and tools developed so far, it has to be evaluated how the investigations mentioned above can be extended and enhanced using domain knowledge in order to support the heuristics (e.g. slicing in hybrid evolutionary algorithms) as well as applying distributed evolutionary systems.
  • Porting the tool to support additional programming languages
    After having successfully implemented the automated generation of test drivers and the generation and optimisation of test data for Java-programs, the industrial applicability of the tool will be achieved by adding support for additional programming languages. Among others, support for the language family of C is intended, which is typically used for embedded systems - especially C++ and C#. Based on the insight gained so far for Java, the tool will be extended by a static and dynamic analysis for C#-programs.
  • Local optimisation of additionally required test cases
    From the localisation of the data flow pairs done so far (see static analysis) additional test paths have to be derived in order to fulfil the testing criterion. The corresponding test cases are to be generated in a local optimisation step using evolutionary algorithms. This requires the definition of a new fitness function based on the graph-theoretic characteristics of the control flow as well as the enhancement of the instrumentation of the test object already implemented (dynamic analysis). Consequently, the automatic generation of test cases is locally directed and enhanced with respect to time effort and data flow coverage achieved.
watermark seal