Timed Wp-method: Testing real-time systems

Real-time systems interact with their environment using time constrained input/output signals. Examples of real-time systems include patient monitoring systems, air traffic control systems, and telecommunication systems. For such systems, a functional misbehavior or a deviation from the specified time constraints may have catastrophic consequences [27]. Therefore, ensuring the correctness of real-time systems becomes necessary. Two different techniques are usually used to cope with the correctness of a software system prior to its deployment, namely, verification and testing. In this paper, we address the issue of testing real-time software systems specified as a Timed Input Output Automaton (TIOA). TIOA is a variant of timed automaton [1], [2], [22], [29]. We introduce the syntax and semantics of TIOA. We present the potential faults that can be encountered in a timed system implementation. We study these different faults based on TIOA model and look at their effects on the execution of the system using the region graph. We present a method for generating timed test cases. This method is based on a state characterization technique and consists of the following three steps: First, we sample the region graph using a suitable granularity, in order to construct a subautomaton easily testable, called Grid Automaton. Then, we transform the Grid Automaton into a Nondeterministic Timed Finite State Machine (NTFSM). Finally, we adapt the Generalized Wp-method [23] to generate timed test cases from NTFSM. We assess the fault coverage of our test cases generation method and prove its ability to detect all the possible faults. Throughout the paper, we use examples to illustrate the various concepts and techniques used in our approach.