×

The complexity of asynchronous model based testing. (English) Zbl 1251.68118

Summary: In model based testing (MBT), testing is based on a model M that typically is expressed using a state-based language such as an input output transition system (IOTS). Most approaches to MBT assume that communications between the system under test (SUT) and its environment are synchronous. However, many systems interact with their environment through asynchronous channels and the presence of such channels changes the nature of testing.
In this paper we investigate the situation in which the SUT interacts with its environment through asynchronous channels and the problems of producing test cases to reach a state, execute a transition, or to distinguish two states. In addition, we investigate the oracle problem. All four problems are explored for both FIFO and non-FIFO channels.
It is known that the oracle problem can be solved in polynomial time for FIFO channels but we also show that the three test case generation problems can also be solved in polynomial time in the case where the IOTS is observable but the general test generation problems are EXPTIME-hard. For non-FIFO channels we prove that all of the test case generation problems are EXPTIME-hard and the oracle problem in NP-hard, even if we restrict attention to deterministic IOTSs.

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
68M15 Reliability, testing and fault tolerance of networks and computer systems

Software:

AsmL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] AboElFotoh, H.; Abou-Rabia, O.; Ural, H., A test generation algorithm for protocols modeled as non-deterministic FSMs, The Software Engineering Journal, 8, 4, 184-188 (1993)
[2] Aho, A. V.; Dahbura, A. T.; Lee, D.; Uyar, M. U., An optimization technique for protocol conformance test generation based on UIO sequences and Rural Chinese Postman Tours, (Protocol Specification, Testing, and Verification VIII (1988), Elsevier: Elsevier North-Holland, Atlantic City), 75-86
[3] Aho, A. V.; Dahbura, A. T.; Lee, D.; Uyar, M. U., An optimization technique for protocol conformance test generation based on UIO sequences and rural Chinese postman tours, IEEE Transactions on Communications, 39, 11, 1604-1615 (1991)
[4] R. Alur, C. Courcoubetis, M. Yannakakis, Distinguishing tests for nondeterministic and probabilistic machines, in: 27th ACM Symposium on Theory of Computing, 1995, pp. 363-372.; R. Alur, C. Courcoubetis, M. Yannakakis, Distinguishing tests for nondeterministic and probabilistic machines, in: 27th ACM Symposium on Theory of Computing, 1995, pp. 363-372. · Zbl 0978.68522
[5] Barnett, M.; Grieskamp, W.; Nachmanson, L.; Schulte, W.; Tillmann, N.; Veanes, M., Towards a tool environment for model-based testing with AsmL, (Formal Approaches to Testing. Formal Approaches to Testing, Lecture Notes in Computer Science, vol. 2931 (2003), Springer-Verlag: Springer-Verlag Montreal, Canada), 252-266
[6] Bhateja, Puneet; Gastin, Paul; Mukund, Madhavan, A fresh look at testing for asynchronous communication, (Automated Technology for Verification and Analysis, 4th International Symposium. Automated Technology for Verification and Analysis, 4th International Symposium, ATVA 2006. Automated Technology for Verification and Analysis, 4th International Symposium. Automated Technology for Verification and Analysis, 4th International Symposium, ATVA 2006, Lecture Notes in Computer Science, vol. 4218 (2006), Springer), 369-383 · Zbl 1161.68349
[7] Boreale, Michele; Nicola, Rocco De; Pugliese, Rosario, Asynchronous observations of processes, (First International Conference on the Foundations of Software Science and Computation Structure. First International Conference on the Foundations of Software Science and Computation Structure, FoSSaCS 1998. First International Conference on the Foundations of Software Science and Computation Structure. First International Conference on the Foundations of Software Science and Computation Structure, FoSSaCS 1998, Lecture Notes in Computer Science, vol. 1378 (1998), Springer), 95-109 · Zbl 1009.68079
[8] Boreale, Michele; Nicola, Rocco De; Pugliese, Rosario, A theory of may testing for asynchronous languages, (Second International Conference on the Foundations of Software Science and Computation Structure. Second International Conference on the Foundations of Software Science and Computation Structure, FoSSaCS 1999. Second International Conference on the Foundations of Software Science and Computation Structure. Second International Conference on the Foundations of Software Science and Computation Structure, FoSSaCS 1999, Lecture Notes in Computer Science, vol. 1578 (1999), Springer), 165-179 · Zbl 1009.68079
[9] Castellani, Ilaria; Hennessy, Matthew, Testing theories for asynchronous languages, (18th Conference on Foundations of Software Technology and Theoretical Computer Science. 18th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 1998. 18th Conference on Foundations of Software Technology and Theoretical Computer Science. 18th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 1998, Lecture Notes in Computer Science, vol. 1530 (1998), Springer), 90-101
[10] Chen, T. Y.; Tse, T. H.; Zhou, Z., Fault-based testing in the absence of an oracle, (IEEE Annual International Computer Software and Applications Conference. IEEE Annual International Computer Software and Applications Conference, COMPSAC 2001 (2002), IEEE Computer Society Press), 172-178
[11] Chen, T. Y.; Tse, T. H.; Zhou, Z., Fault-based testing in the absence of an oracle, Information and Software Technology, 45, 1, 1-9 (2003)
[12] Chen, Tsong Yueh; Ho, Joshua W. K.; Liu, Huai; Xie, Xiaoyuan, An innovative approach for testing bioinformatics programs using metamorphic testing, BMC Bioinformatics, 10 (2009)
[13] Chow, T. S., Testing software design modelled by finite state machines, IEEE Transactions on Software Engineering, 4, 178-187 (1978) · Zbl 0379.68039
[14] da Silva Simão, Adenilso; Petrenko, Alexandre, Generating asynchronous test cases from test purposes, Information and Software Technology, 53, 1252-1262 (2011)
[15] Farchi, E.; Hartman, A.; Pinter, S., Using a model-based test generator to test for standard conformance, IBM systems journal, 41, 1, 89-110 (2002)
[16] W. Grieskamp, Y. Gurevich, W. Schulte, M. Veanes, Generating finite state machines from abstract state machines, in: Proceedings of the ACM SIGSOFT Symposium on Software Testing and Analysis, 2002, pp. 112-122.; W. Grieskamp, Y. Gurevich, W. Schulte, M. Veanes, Generating finite state machines from abstract state machines, in: Proceedings of the ACM SIGSOFT Symposium on Software Testing and Analysis, 2002, pp. 112-122.
[17] Grieskamp, Wolfgang, Multi-paradigmatic model-based testing, (Formal Approaches to Software Testing and Runtime Verification. Formal Approaches to Software Testing and Runtime Verification, FATES/RV 2006. Formal Approaches to Software Testing and Runtime Verification. Formal Approaches to Software Testing and Runtime Verification, FATES/RV 2006, Lecture Notes in Computer Science, vol. 4262 (2006), Springer), 1-19
[18] Grieskamp, Wolfgang; Kicillof, Nicolas; Stobie, Keith; Braberman, Victor, Model-based quality assurance of protocol documentation: tools and methodology, The Journal of Software Testing, Verification and Reliability, 21, 1, 55-71 (2011)
[19] Haar, Stefan; Jard, Claude; Jourdan, Guy-Vincent, Testing input/output partial order automata, (TestCom/FATES 2007. TestCom/FATES 2007, Lecture Notes in Computer Science, vol. 4581 (2007), Springer), 171-185
[20] Harel, D.; Politi, M., Modeling Reactive Systems with Statecharts: the STATEMATE Approach (1998), McGraw-Hill: McGraw-Hill New York
[21] F.C. Hennie, Fault-detecting experiments for sequential circuits, in: Proceedings of Fifth Annual Symposium on Switching Circuit Theory and Logical Design, Princeton, New Jersey, November 1964, pp. 95-110.; F.C. Hennie, Fault-detecting experiments for sequential circuits, in: Proceedings of Fifth Annual Symposium on Switching Circuit Theory and Logical Design, Princeton, New Jersey, November 1964, pp. 95-110.
[22] Hierons, R. M., Adaptive testing of a deterministic implementation against a nondetermistic finite state machine, The Computer Journal, 41, 5, 349-355 (1998) · Zbl 0921.68032
[23] Hierons, R. M., Testing from a non-deterministic finite state machine using adaptive state counting, IEEE Transactions on Computers, 53, 10, 1330-1342 (2004)
[24] Hierons, Robert M., Applying adaptive test cases to nondeterministic implementations, Information Processing Letters, 98, 2, 56-60 (2006) · Zbl 1187.68162
[25] Hierons, Robert M., Reaching and distinguishing states of distributed systems, SIAM Journal of Computing, 39, 8, 3480-3500 (2010) · Zbl 1209.68299
[26] Hierons, Robert M.; Bogdanov, Kirill; Bowen, Jonathan P.; Cleaveland, Rance; Derrick, John; Dick, Jeremy; Gheorghe, Marian; Harman, Mark; Kapoor, Kalpesh; Krause, Paul; Lüttgen, Gerald; Simons, Anthony J. H.; Vilkomir, Sergiy A.; Woodward, Martin R.; Zedan, Hussein, Using formal specifications to support testing, ACM Computing Surveys, 41, 2 (2009)
[27] Hierons, Robert M.; Ural, Hasan, Optimizing the length of checking sequences, IEEE Transactions on Computers, 55, 5, 618-629 (2006)
[28] Huo, Jiale; Petrenko, Alexandre, On testing partially specified IOTS through lossless queues, (16th IFIP International Conference on the Testing of Communicating Systems. 16th IFIP International Conference on the Testing of Communicating Systems, TestCom 2004. 16th IFIP International Conference on the Testing of Communicating Systems. 16th IFIP International Conference on the Testing of Communicating Systems, TestCom 2004, Lecture Notes in Computer Science, vol. 2978 (2004), Springer), 76-94
[29] Huo, Jiale; Petrenko, Alexandre, Transition covering tests for systems with queues, Software Testing, Verification and Reliability, 19, 1, 55-83 (2009)
[30] Jard, Claude; Jéron, Thierry; Kahlouche, Hakim; Viho, César, Towards automatic distribution of testers for distributed conformance testing, (TC6 WG6.1 Joint International Conference on Formal Description Techniques and Protocol Specification, Testing and Verification. TC6 WG6.1 Joint International Conference on Formal Description Techniques and Protocol Specification, Testing and Verification, FORTE 1998. TC6 WG6.1 Joint International Conference on Formal Description Techniques and Protocol Specification, Testing and Verification. TC6 WG6.1 Joint International Conference on Formal Description Techniques and Protocol Specification, Testing and Verification, FORTE 1998, IFIP Conference Proceedings, vol. 135 (1998), Kluwer), 353-368
[31] Jard, Claude; Jéron, Thierry; Tanguy, Lénaick; Viho, César, Remote testing can be as powerful as local testing, (Joint International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols (FORTE XII) and Protocol Specification, Testing and Verification. Joint International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols (FORTE XII) and Protocol Specification, Testing and Verification, PSTV XIX. Joint International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols (FORTE XII) and Protocol Specification, Testing and Verification. Joint International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols (FORTE XII) and Protocol Specification, Testing and Verification, PSTV XIX, IFIP Conference Proceedings, vol. 156 (1999), Kluwer), 25-40 · Zbl 0952.68009
[32] Lee, D.; Yannakakis, M., Testing finite-state machines: State identification and verification, IEEE Transactions on Computers, 43, 3, 306-320 (1994) · Zbl 1395.68173
[33] Lee, D.; Yannakakis, M., Principles and methods of testing finite-state machines — a survey, Proceedings of the IEEE, 84, 8, 1089-1123 (1996)
[34] Luo, G. L.; Bochmann, G.v.; Petrenko, A., Test selection based on communicating nondeterministic finite-state machines using a generalized Wp-method, IEEE Transactions on Software Engineering, 20, 2, 149-161 (1994)
[35] Jefferson Offutt, A.; Abdurazik, Aynur, Generating tests from UML specifications, (Second International Conference on the The Unified Modeling Language. Second International Conference on the The Unified Modeling Language, UML 1999. Second International Conference on the The Unified Modeling Language. Second International Conference on the The Unified Modeling Language, UML 1999, Lecture Notes in Computer Science, vol. 1723 (1999), Springer), 416-429
[36] Owe, Olaf; Steffen, Martin; Torjusen, Arild B., Model testing asynchronously communicating objects using modulo ac rewriting, Electronic Notes Theoretical Computer Science, 264, 3, 69-84 (2010)
[37] Petrenko, A.; Yevtushenko, N.; Lebedev, A.; Das, A., Nondeterministic state machines in protocol conformance testing, (Proceedings of Protocol Test Systems, VI (C-19) (1994), Elsevier Science: Elsevier Science North-Holland, Pau, France), 363-378
[38] Petrenko, A.; Yevtushenko, N.; Bochmann, G.v., Testing deterministic implementations from nondeterministic FSM specifications, (Testing of Communicating Systems, IFIP TC6 9th International Workshop on Testing of Communicating Systems (1996), Chapman and Hall: Chapman and Hall Darmstadt, Germany), 125-141
[39] Petrenko, Alexandre; Yevtushenko, Nina; Huo, Jiale, Testing transition systems with input and output testers, (15th IFIP International Conference on Testing of Communicating Systems. 15th IFIP International Conference on Testing of Communicating Systems, TestCom 2003. 15th IFIP International Conference on Testing of Communicating Systems. 15th IFIP International Conference on Testing of Communicating Systems, TestCom 2003, Lecture Notes in Computer Science, vol. 2644 (2003), Springer), 129-145 · Zbl 1029.68856
[40] Rabin, M. O.; Scott, D., Finite automata and their decision problems, IBM Journal of Research and Development, 3, 2, 114-125 (1959) · Zbl 0158.25404
[41] Reif, John H., The complexity of two-player games of incomplete information, Journal of Computer and System Sciences, 29, 2, 274-301 (1984) · Zbl 0551.90100
[42] Thomas J. Schaefer, The complexity of satisfiability problems, in: Tenth Annual ACM Symposium on Theory of Computing, STOC, 1978, pp. 216-226.; Thomas J. Schaefer, The complexity of satisfiability problems, in: Tenth Annual ACM Symposium on Theory of Computing, STOC, 1978, pp. 216-226. · Zbl 1282.68143
[43] Tarjan, R. E., Depth-first search and linear graph algorithms, SIAM Journal of Computing, 1, 2 (1972) · Zbl 0251.05107
[44] P. Tripathy, K. Naik, Generation of adaptive test cases from non-deterministic finite state models, in: Proceedings of the 5th International Workshop on Protocol Test Systems, Montreal, September 1992, pp. 309-320.; P. Tripathy, K. Naik, Generation of adaptive test cases from non-deterministic finite state models, in: Proceedings of the 5th International Workshop on Protocol Test Systems, Montreal, September 1992, pp. 309-320.
[45] Verhaard, Louis; Tretmans, Jan; Kars, Pim; Brinksma, Ed, On asynchronous testing, (Proceedings of the IFIP TC6/WG6.1 Fifth International Workshop on Protocol Test Systems. Proceedings of the IFIP TC6/WG6.1 Fifth International Workshop on Protocol Test Systems, Protocol Test Systems V. Proceedings of the IFIP TC6/WG6.1 Fifth International Workshop on Protocol Test Systems. Proceedings of the IFIP TC6/WG6.1 Fifth International Workshop on Protocol Test Systems, Protocol Test Systems V, IFIP Transactions, vol. C-11 (1992), North-Holland), 55-66
[46] von Bochmann, Gregor; Haar, Stefan; Jard, Claude; Jourdan, Guy-Vincent, Testing systems specified as partial order input/output automata, (20th IFIP TC 6/WG 6.1 International Conference on Testing of Software and Communicating Systems. 20th IFIP TC 6/WG 6.1 International Conference on Testing of Software and Communicating Systems, TestCom/FATES. 20th IFIP TC 6/WG 6.1 International Conference on Testing of Software and Communicating Systems. 20th IFIP TC 6/WG 6.1 International Conference on Testing of Software and Communicating Systems, TestCom/FATES, Lecture Notes in Computer Science, vol. 5047 (2008), Springer), 169-183
[47] Weiglhofer, Martin; Wotawa, Franz, Asynchronous input-output conformance testing, (Proceedings of the 33rd Annual IEEE International Computer Software and Applications Conference. Proceedings of the 33rd Annual IEEE International Computer Software and Applications Conference, COMPSAC 2009 (2009), IEEE Computer Society), 154-159 · Zbl 1157.68391
[48] Weyuker, E. J., On testing non-testable programs, The Computer Journal, 25, 4, 465-470 (1982)
[49] Zhang, Fan; Cheung, To-Yat, Optimal transfer trees and distinguishing trees for testing observable nondeterministic finite-state machines, IEEE Transactions on Software Engineering, 29, 1, 1-14 (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.