An Evolutionary Algorithm for the Generation of Timed Test Traces for Embedded Real-Time Systems

Abstract

In safety-critical applications, the real-time behavior is crucial for the correctness of the overall system and must be tested thoroughly. However, the generation of test traces that cover most or all of the desired behavior of a real-time system is a difficult challenge. In this paper, we present an evolutionary algorithm that generates timed test traces, which achieve a given transition coverage. We generate these traces from a timed automata model. Our main contribution is a novel approach to encode timed test traces as individuals of an evolutionary algorithm. The major difficulty in doing so is that test traces for embedded real-time systems have to be very long. To solve this problem, we introduce the notion of blocks, which simplify long traces by cutting them into pieces. With that, we reduce the search space significantly. Furthermore, we have implemented crossover and mutation operators and a fitness function that takes time-dependent behavior implicitly into account. We show the success of our approach by experimental results from an anti-lock braking system.