Using adaptive distinguishing sequences in checking sequence constructions

ABSTRACT

A number of methods have been published to construct checking sequences for testing from Finite State Machine-based specifications. Many of these methods require the existence of a preset distinguishing sequence in the model. In this paper, we show that usually an adaptive distinguishing sequence is sufficient for these methods to work. This result is significant because adaptive distinguishing sequences are strictly more common and up to exponentially shorter than preset ones.

REFERENCES

• 1: Gill, A. Introduction to the Theory of Finite-State Machines, McGraw-Hill, NewYork, 1962.
• 2: Hennie, F. C. Fault detecting experiments for sequential circuits. Proc. 5th. Symp. Switching Circuit Theory and Logical Design, Princeton, N.J., 1964, 95--110.
• 3: D. Lee , M. Yannakakis, Testing Finite-State Machines: State Identification and Verification, IEEE Transactions on Computers, v.43 n.3, p.306-320, March 1994 [doi>10.1109/12.272431]
• 4: T. S. Chow, Testing Software Design Modeled by Finite-State Machines, IEEE Transactions on Software Engineering, v.4 n.3, p.178-187, May 1978 [doi>10.1109/TSE.1978.231496]
• 5: Susumu Fujiwara , Gregor von Bochmann , Ferhat Khendek , Mokhtar Amalou , Abderrazak Ghedamsi, Test Selection Based on Finite State Models, IEEE Transactions on Software Engineering, v.17 n.6, p.591-603, June 1991 [doi>10.1109/32.87284]
• 6: Krishan Sabnani , Anton Dahbura, A protocol test generation procedure, Computer Networks and ISDN Systems, v.15 n.4, p.285-297, Sept. 1988 [doi>10.1016/0169-7552(88)90064-5]
• 7: Dahbura, A. T., Sabnani K. K., Uyar, M. U. Formal methods for generating protocol conformance test sequences. Proceedings of the IEEE, 78 (1990), 1317--1325.
• 8: Lee, D., Yannakakis, M. Principles and methods of testing finite state machines -- a survey. Proceedings of the IEEE, 84, 8 (1996), 1089--1123.
• 9: Hasan Ural , Xiaolin Wu , Fan Zhang, On Minimizing the Lengths of Checking Sequences, IEEE Transactions on Computers, v.46 n.1, p.93-99, January 1997 [doi>10.1109/12.559807]
• 10: Robert M. Hierons , Hasan Ural, Reduced Length Checking Sequences, IEEE Transactions on Computers, v.51 n.9, p.1111-1117, September 2002
• 11: Chen, J., Hierons, R. M., Ural, H., Yenigun, H. Eliminating redundant tests in checking sequences. In Proc. of IFIP TestCom'05, Montreal, Quebec, 2005, 146--158.
• 12: Tekle, K. T., Ural, H., Yalcin, C. M., Yenigun, H. Generalizing redundancy elimination in checking sequences. Proc. of ISCIS'05, Istanbul, Turkey, 2005, 915--926.
• 13: Rob M. Hierons , Hasan Ural, Optimizing the Length of Checking Sequences, IEEE Transactions on Computers, v.55 n.5, p.618-629, May 2006 [doi>10.1109/TC.2006.80]
• 14: G. Gonenc, A Method for the Design of Fault Detection Experiments, IEEE Transactions on Computers, v.19 n.6, p.551-558, June 1970 [doi>10.1109/T-C.1970.222975]
• 15: Sokolovskii, M. N. Diagnostic experiments with automata. Kibernetika, 6 (1971), 44--49.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

General Terms:
Reliability, Theory, Verification

Keywords:
adaptive distinguishing sequences, checking sequence construction, finite state machines, model-based testing, preset distinguishing sequences