AbstractEvolutionary testing is a new testing technique based on the application of evolutionary algorithms. It can be used to automatically generate test cases which satisfy a given test criterion. For the best- and worst-case execution time analysis of real-time systems it can be applied to generate test cases which
minimise or maximise the execution time, or violate the timing specification of such a system.
Evolutionary testing regards the testing process entirely as an optimisation problem with the test criterion as the goal for which suitable test cases must be found. As a typical optimisation technique, evolutionary testing cannot guarantee to find test cases which satisfy this test criterion. The only outcome is the time found, but there is no information on how close this time is compared with the actual minimum or maximum time which must be found.
Experiments with the technique have revealed a relationship between the complexity of a test object and the success of the search technique to generate test cases according to best- or worst-case execution times as test target. For very 'simple' test programs, evolutionary testing could easily generate test-cases
according to this target. For more complex programs, the optimisation process exhibited significant difficulties to succeed.
This thesis discusses and defines attributes of programs which correspond to aspects of complexity. These are high nesting, small input domains, high parameter interaction or interdependence, and the size of a program's input. New complexity measures are introduced which attempt to capture these aspects of evolutionary testability. The validation of the measures through a technique which was introduced by Shepperd and Ince, identifies three core measures which can be used to predict evolutionary testability for dynamic timing analysis. These are measures for nesting, small input domains and the input size. These measures can be used to predict the expected outcome of an evolutionary testing process, so that the technique can be applied to programs where the expected outcome of evolutionary testing is likely to be of high quality. Additional measures could not be identified as being valid measures, but they can help to indicate evolutionary testability.
|Date of Award