A Method of Test Cases Generation for Real-Time Systems
Ian Ho & Jin-Cherng Lin
Dept. of Computer Science and Engineering
Tatung Institute of Technology
Taipei 10451, Taiwan, R.O.C.
E-mail:
Abstract
Real-time software must satisfy not only functional correctness requirements but also timeliness requirements. A lot of real-time researches were focused on analysis rather than testing recently, [Glass80] observes that real-time testing is still a “lost-world” compared to “civilization” developed in other areas of software, reflecting the little work done in the area.
During the execution of real-time software, sequence of events due to time take place between the concurrent processes. Because of the unpredictable progress of concurrent processes, multiple executions of real-time software with the same test cases may produce different results. This nondeterministic execution behavior always creates problems in software testing.
This paper is concerned with test cases generation for real-time systems. It includes (1) a guideline of how to handle the nondeterministic properties of real-time systems, and (2) how to generate test cases using dual-language based model and path-like testing strategy. It faces the problem of testing concurrent and real-time software and extends the testing activities to the requirement and design phase by using the dual-language approach. This approach can be used to validate both the specifications and implementations. Besides, since the model is in formal form, the test cases can be automatically generated. Therefore the difficulties of generating test cases for testing real-time systems is minimized.
Key Words – dual-language approach, time Petri nets, real-time systems, software testing, temporal logic, test case generation.
1 Introduction
A real-time system is a set of concurrent computations that interact with each other and adhere to some timing constraints. The specification of each of the computations and the interactions is based on logical properties (as in other systems), but itessegments and its logic specifications. Since we start out with the model that is in formal form, the test cases can be automatically generated. The difficulties of generating test cases for testing real-time systems is then minimized.
2 The Proposed Method – Dual-Language Approach
There are a variety of test case design methods evolving for computer software in the past several years. Some of them provide a mechanism that can help to ensure the completeness of tests and provide the highest likelihood of uncovering errors in software. Generally speaking, white box testing of software is predicated on a close examination of procedural detail. Logical paths in the software are tested by offering test cases that exercise specific sets of conditions or segments.
The special characteristics of real-time systems offer major challenges when testing is to be conducted. The time dependent and asynchronous nature of many real-time applications adds a new and potentially difficult element to the testing activities. In [Mandrioli95], they provides the feasibility of real-time system test cases generation by using history checking method in TRIO language (a language based on first-order logic, augmented by temporal operators). [Clarke95] also presents a domain testing based technique for verifying timing constraints of real-time systems, given timing constraints specified as minimum and maximum allowable delays between input/output events. Both of them have described that integrating formal methods and testing is one of the most effective strategies to tackle the temporal properties of the system. Similarly, we believe that if we combine several methodologies and abstract its own merits, the interaction between formal methods and existing testing techniques could be enhanced and errors which not only in logic and function, but also in timing and behavior will be uncovered.
The dual-language approach is a paradigm for developing concurrent and real-time systems where two entities are distinguished: a set of properties one wishes to verify and the system about which these properties are to be verified [Felder94]. By applying the dual-language approach in real-time software design and analysis, a descriptive language (e.g. temporal logic) is used to describe the system properties because of its precise mathematical notations and an operational language (e.g. time Petri nets) is used to support the description of a system in terms of an abstract model that simulates its behavior.
In this paper, our proposed method is implemented based on the dual-language approach for system design and analysis. By checking these formalisms, the new developed testing technique is adopted to generate test cases for real-time system from its timing criteria and logic specifications.
Generally speaking, generating test cases for functional testing is not an easy task, because there are few guidelines given. There is no exception to the real-time system discussed in this article. [Morasca90] had mentioned that a concurrent software repeated runs under the same inputs can yield executions that differ in the order certain activities are carried out. This implies, on the one hand, that different correct results can be produced in response to the same external stimuli, due to the different executions and , on the other hand, it can be the case that when repeatedly executing a software with the same input data, sometimes a failure occurs and other times it does not, depending on the particular execution. Therefore, in the concurrent software we should define a test case as a particular execution, and not just as the input data. It means that for the time Petri nets, a test case is the predicate that selects a particular firing sequence.
Consider the process of a real-time system development under dual-language approach. Our point of view lies in the fact that the temporal logic is a qualified tool to identify the time criteria in formal design. Moreover, the time Petri nets can handle the state transitions of the system accurately. In [Felder94], they have integrated the TRIO and time Petri nets as a dual-language approach to do the system verification, both in the perspective of operational formalism and descriptive formalism, which seems very creative.
Due to the practicality and integrity of this method in concurrent real-time systems implementation and verification, we propose to integrate and extend the concept of path testing under a dual-language approach. We believe that it will not only cover the software characteristics both structurally and functionally, but also it can handle the nondeterministic properties from time perspective to solve some issues of testing real-time systems.
To generate test cases, we first model the system with dual-language approach, and investigate its formalisms. Then we identify the test segments in time Petri nets from a graphic perspective and set up its relationships with graph matrix. Finally, we can find out the cases suitable for software testing. The detailed steps will be addressed in section 4.
3 Overview of Temporal Logic and Time Petri Nets
Real-time software is a software which must meet strict timing demands. Some formalisms have been developed to specify and verify the problems and properties in concurrent real-time systems. During the past decade, temporal logic has been widely used to resolve the execution sequences of programs and was found especially useful in proving properties of concurrent real-time software. Time Petri nets, with which timing requirements on ttessegments and its logic specifications.
Details of each step are described as follows.
4.1 Modeling the System Through Temporal Logic Specifications and Time Petri Nets Model
We start out our approach with modeling the system by the formal way. A time Petri nets P£ is composed of a set of places P, a set of transitions T, an input function I (the preset of transitions), a output function O (the postset of transitions), and related markings g£ along with the added firing time functions Min and Max. Therefore it is a seven-tuple and can be expressed as follows:
P£ = ( P, T, I, O,g£, Min, Max)
P = { P1, P2, … , Pm } ; m is the number of places.
T = { t1, t2, … , tn } ; n is the number of transitions.
I(ti) is the preset of transition ti.
O(ti) is the postset of transition ti.
g£ = { k1, k2, … , km } ; the value of marking for mth place, it could be 0 or 1.
0 Ø¡ Mini Ø¡ Maxi Ø¡ Û¡ the temporal domain for ith transition.
The temporal logic predicate for transition ti can be expressed by the formula shown as;
]¡e¡]¡I(ti)סg£1^¡ 1]¡xסT^¡f¡÷¡
º¡e¡]¡O(ti)סg£1^¡1 ]¡I(ti)סg£0^¡1]¡xÏ¡MiniØ¡TØ¡xÏ¡Maxi^¡f¡^¡
where
x G¡ time stamp for certain event.
T G¡ current value
The time Petri net graph for test segment Si1
Figure-2 Time Petri Net Representation of Test Segment
It is obvious that we can determine all of the test segments in system model without difficulty using the graphic notation of the time Petri nets,. Basically, we can employ the related technology as the way basis path testing does to investigate the nets graph and to obtain all “paths” for it.
4.3 Constructing the Graph Matrix
In this step, a graph matrix will be constructed as a tabular representation of the Petri nets. The graph matrix is a square matrix whose size (i.e., number of rows and columns) is equal to the number of places on the Petri nets. Each row and column corre
i.e., [P] = [P]is 1Ñvec, whi preset/postset of each transition, as correspondent of the net. Actually, the operation (i.e., multiplication) between vectointo sub-accordithlogic prof each (i.eAND, Excl, e). The decomposed sub-mattransiar the ee pathPetri, and will be usseof test cases.
4.5 Applying the Time Variation Method
In time Petri nets, we are most concerned the time uncertainty of each transition. We consider that the “temporal domain” for each transition is exactly the major origin of the system nondeterminism. Then, if we expand the temporal domain of each transition in basic time unit, we may get a more clear insight in each activity.
We name the ex
4.6 Generation of Tetime variation methode transition for each test segCombing degramatricdelayed transitions, the straightforwardly.
5 An Illustrative Example
In this section, we try to use a similar case as in Figure-1 to explain how this method is applied.
In Figure-3, we have a time Petri net model with initial markings on p1 and p3. To simplify our problem, we still need to assume that the transitions in the net will be forced to fire within its upper bound, and the tokens are uniquely generated and co
Where ò¡is the Exclusive OR function. Since transitions t1ò¡t2 , the matrix can be deco
In former matrix, t1 and t3 appear in the same row. It means t1 and t3 share the same place in which the marking will be consumed by either one. We leave t3
It is the result after the execution of the Petri net model. To some extent matrices shown here are equivalent to the basis set of linearly dependent paths for path testing.
Further expan
t2 ÷¡t2(1) , t
t3 ÷¡t3(1)Combining the matrices and related transitions, two sets of test cases are obtained. Test cases for this example are shown as follows:
SET-1 : 1111t1(2) , t1(3) , t1(4) , t1(5)
SET-2 : 1111t2(1) , t2(2) , t2(3) , t3(1) , t3(2)
Where each of the timed transition can be further replaced by related temporal logic formulae.
6 Concluding Remarks
For a real-time system, the introduction of time presents a new collection of complications in software testing which must be resolved. This concern is especially serious since many real-time systems are also mission critical; i.e., failure of the system could result in loss of life or resources. Thus safety-critical systems must be verified in a much more rigorous and thorough way than conventional ones, to remove as many flaws as possible before they are put into operational use.
Testing is a fundamental verification activity, and if applied with other methods such as formal design and verification, it is likely to give a high level degree of confidence in the reliable behavior of the software [Morasca90]. That’s the reason why we proposed to use the dual-language approach as a starting point of the software testing.
This paper is a step towards a general framework for testing concurrent and real-time software., to some extent it is especially suitable for testing the real-time system by using the “instruction level simulator”. This approach can uncover errors not only in logic and function, but also in timing and behavior, and may lead to hierarchical automated real-time software testing method.
References
[Berthomieu91] B. Berthomieu and M. Diaz, “Modeling and Verification of Time Dependent Systems Using Time Petri Nets,” IEEE Trans. Software Eng., vol. 17, no. 3, 1991, pp.259-273.
[Chang94] E. Chang, Z. Manna and A. Pnueli, “Compositional Verification of Real-Time Systems,” Proceedings, 9th Annual IEEE Symposium on Logic in Comp