Verallgemeinertes Rahmenwerk zur constraintbasierten Testdatenerzeugung aus Programmflussgraphen

We present a new constraint-based method for generating test data for code-based unit testing. The method allows for the first time to combine strategies of path search on control flow graphs, and introduces new strategies. Annotations on the control flow graph describe the instructions inside the graph nodes and are automatically derived from the code. The path through the unit-under-test is composed recursively from partial paths, independent of the actual order of execution of the path. Performance is increased using structural information from the graphs to avoid selection of infeasible paths. We establish formal operational semantics of annotated control flow graphs. An easy-to-use formal notation for structural test criteria is presented, supporting all classical coverage criteria for unit test and allowing further extensions towards more specific test criteria. Structural information from the control flow graph is used for prediction of control- and data-flow to avoid selection of infeasible paths. We provide a framework of path construction and constraint propagation rules, including recursive path decomposition, forward- and backward-stepping, program state and control flow prediction, which can be combined arbitrarily to a strategy matching the test goal. Test data is selected randomly from the constrained search space. Statistical analysis on possible bias of the method is performed and strategies for bias compensation are proposed. Finally, results from a prototypical implementation for an imperative subset of Java using CHR and Prolog are presented. Several path construction strategies are assessed for their performance, concluding that none of them is optimal, but some of them have clear advantages over others depending on the program-under-test and the test criteria. Experience on CHR practice gained from the implementation is also discussed