Construction of global finite state machine for testing task interactions written in message sequence charts

ABSTRACT

Integration testing of embedded software is difficult because such software tends to be large and complex; it is often structured as a set of tasks whose interaction patterns can be arbitrary and nondeterministic; it is subject to frequent changes while being tested; and testing period must be minimized since the product's life-time is short. In order to conduct integration testing in a cost-effective manner, it is essential that requirements are captured in precise notation and that test cases are automatically generated and executed whenever possible.In this paper, we demonstrate how to generate test cases from a set of Message Sequence Charts (MSCs) by constructing a semantically equivalent global finite state machine (GFSM). Test cases are expressed as a sequence of messages to be exchanged among various system entities. When transforming complex and hierarchical MSCs to a GFSM, state explosion problem is often encountered. When constructing a GFSM, we achieved significant reduction in the number of states and transitions by generating only the feasible sequences. Such reduction was possible because embedded software we used as the case study, digital TV application software, had known and well-defined initial state.We developed a graphical toolset to edit MSCs and automatically generate test cases. Users describe the required functionalities in scenarios, and test cases are automatically generated from the GFSM according to the state and transition coverage criteria. We applied the proposed approach to specify and test a substantial portion of embedded software running on a digital TV and were able to detect an error, previously unknown to the developers, that occurred due to a subtle race condition among tasks.

REFERENCES

• 1: David Harel, Statecharts: A visual formalism for complex systems, Science of Computer Programming, v.8 n.3, p.231-274, June 1, 1987 [doi>10.1016/0167-6423(87)90035-9]
• 2: Recommendation Z.100. Specification and Description Language (SDL'2000). Technical report, ITU-T, Geneva, 2000.
• 3: T. Murata. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 77:541-580, 1989.
• 4: Recommendation Z.120. Message Sequence Chart (MSC'2000). Technical report, ITU-T, Geneva, 2000.
• 5: J. Grabowski. SDL and MSC Based Test Case Generation - An Overall View of the SAMSTAG Method. Technical report, University of Berne, IAM-94-0005, 1994.
• 6: In Sang Chung , Hyeon Soo Kim , Hyun Seop Bae , Yong Rae Kwon , Byung Sun Lee, Testing of Concurrent Programs Based on Message Sequence Charts, Proceedings of the International Symposium on Software Engineering for Parallel and Distributed Systems, p.72, May 17-18, 1999
• 7: Rajeev Alur , Mihalis Yannakakis, Model Checking of Message Sequence Charts, Proceedings of the 10th International Conference on Concurrency Theory, p.114-129, August 24-27, 1999
• 8: C. Bourhfir, R. Dssouli, and E. M. Aboulhamid. Automatic Test Generation for EFSM-based Systems. Technical report, University of Montreal, TR-1043, 1996.
• 9: ATSC T3/S13 Doc. 010. Data Broadcast Specification. Technical report, ATSC, 1999.
• 10: ATSC Doc. A/65. Program and System Information Protocol for Terrestrial Broadcast and Cable. Technical report, ATSC, 1997.

INDEX TERMS

Keywords:
integration testing, message sequence charts, task interaction