Test Case Minimization for Real-Time Systems Using Timed Bound Traces

Real-Time systems (RTS for short) are those systems whose behavior is time dependent. Reliability and safety are of paramount importance in designing and building RTS because a failure of an RTS puts the public and/or the environment at risk. For the purpose of effective error reporting and testing, this paper considers the trace inclusion problem for RTS: given a path

ρ

(resp.

ρ

′

) of length

n

of a timed automaton

A

(resp.

B

), find whether the set of timed traces of

ρ

of length

n

are included in the set of timed traces of

ρ

′

of length

n

such that

A

is known but not

B

. We assume that the traces of

ρ

′

are only defined by a decision procedure.

The proposed solution is based on the identification of a set of timed bound traces. The latter gives a finite representation of the trace space of a path. The number of these timed bounds varies between 1 and 2 × (

n

+1). The trace inclusion problem is then reduced to the inclusion of timed bound traces. The paper shows also how these results can be used to reduce the number of test cases for an RTS.