Structural performance measure of evolutionary testing applied to worst-case timing of real-time systems

Evolutionary testing is a new testing technique for automatically generating test cases which satisfy a given test criterion. For best or worst-case execution time assessment of real-time systems it can be used to generate test cases which minimize or maximize execution times or possibly violate the timing specification of the system. As a typical search- or optimization technique, evolutionary testing cannot guarantee to find test cases according to the test objective. The only outcome of such a search process is the time found, but there is no information on how close the result comes to the actual minimal or maximal time. Experiments with this testing technique established a relationship between the complexity of a test object and the success of the search process to find optimal or near optimal solutions. This work can be seen as an initial attempt to define a predictive complexity measure which is able to indicate the degree of how successfully an evolutionary search might have performed on a test object. The measure is simple and easy to retrieve as it is based on a program's source code. It is extensible which is important for a further improvement in accuracy. The application of the new measure has shown to be successful for many example test programs but also revealed weaknesses on test objects whose complexity is difficult to capture