EuroSTAR‘98 Testing Temporal Correctness of Real-Time Systems — A New Approach Using Genetic Algorithms and Cluster Analysis —

Testing is one of the most complex and time-consuming activities within the development of embedded systems. Usually, embedded systems have to fulfil real-time requirements, and correct system functionality depends on both their logical correctness and their temporal correctness. An investigation of existing testing approaches shows a lack of support for testing temporal system behavior. For this reason, existing test procedures must be supplemented by new methods that concentrate on determining whether or not the system violates its specified timing constraints. In most cases, a violation occurs because outputs are produced too early, or their computation takes too long. The tester must therefore find the input situations with the longest or shortest execution times, in order to check whether they produce a temporal error. It is virtually impossible to find such inputs by analyzing and testing the temporal behavior of complex systems manually. However, if the search for such inputs is interpreted as a problem of optimization, genetic algorithms can be used to automatically find the inputs with the longest or shortest execution times. The automatic search for accurate test data by means of genetic algorithms is called evolutionary testing. Evolutionary testing is an iterative testing procedure based on the use of genetic algorithms, whic