An evaluation of dynamic, optimisation-based worst-case execution time analysis

Evolutionary testing is a relatively new software testing technique based upon the application of evolutionary algorithms. It can be used to generate input situations for procedures automatically which satisfy a given test criterion. In this scope, testing is entirely regarded as a search or optimisation problem with the test criterion as cost function and the program input as parameters which must be optimised according to that cost function. For assessing the worst-case execution time of real-time software dynamically, evolutionary testing can be applied to optimise input parameter combinations with the aim to maximise the execution time of a program. This paper shows the application of evolutionary testing to the automatic generation of maximal execution times for 15 example test programs. The outcome of this optimisation-based timing analysis is compared with random test case generation, and additionally, with the performance of an experienced human tester who attempted to generate test cases manually on the basis of the source codes which maximise execution times. Experiments show a high success rate of evolutionary testing for generating worst-case timing behaviour compared with the outcome of random testing. Random testing can only generate about 85 percent of the execution times found by evolutionary testing. For only 4 out of the 15 test objects, the human tester was found to be more successful than the automatic test case generators. This can be explained by the pathology of these test objects.