An incremental approach to structural testing of concurrent software

ABSTRACT

Structural testing of a concurrent program P involves the selection of paths of P according to a structure-based criterion. A common approach is to derive the reachability graph (RG) of P, select a set of paths of P, derive one or more inputs for each selected path, and force deterministic executions of P according to the selected paths and their inputs. The use of RG(P) for test path selection has the state explosion problem, since the number of states of RG(P) is an exponential function of the number of processes in P.In this paper, we present a new incremental approach to structural testing of P. Based on the hierarchy of processes in P, our incremental testing approach is to integrate processes in P in a bottom-to-top manner. When a set S of processes in P at the same level are integrated, we construct a reduced RG for S such that the reduced RG contains all synchronizations involving the processes in S and some of the synchronizations involving processes at lower levels in order to connect synchronizations involving processes in S. Based on the reduced RG for S, we can select test paths to focus on the detection of interface faults involving processes in S. After the selection of paths, RG(S) is further reduced in order to retain only some of the synchronizations involving processes in S that are needed in order to connect synchronizations between S and other processes in P. Our incremental approach alleviates the state explosion problem and offers other advantages.

REFERENCES

• Bie90: Boris Beizer, Software testing techniques (2nd ed.), Van Nostrand Reinhold Co., New York, NY, 1990
• CK93: S. C. Cheung , J. Kramer, Enhancing compositional reachability analysis with context constraints, Proceedings of the 1st ACM SIGSOFT symposium on Foundations of software engineering, p.115-125, December 08-10, 1993, Los Angeles, California, United States
• CK95: S. C. Cheung , J. Kramer, Compositional reachability analysis of finite-state distributed systems with user-specified constraints, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.140-150, October 12-15, 1995, Washington, D.C., United States
• Cle94: R. Cleaveland, J.N. Gada, P.M. Lewis, S.A. Smolka, O. Sokolsky, S. Zhang, "The Concurrency Factory- Practical Tools for Specification, Simulation, Verification and Implementation of Concurrent Systems", In Proceedings o/DIMA CS Workshop on Specification o/Parallel Algorithms, Princeton, N J, 1994.
• CPS93: Rance Cleaveland , Joachim Parrow , Bernhard Steffen, The concurrency workbench: a semantics-based tool for the verification of concurrent systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.1, p.36-72, Jan. 1993 [doi>10.1145/151646.151648]
• CT91: Richard H. Carver , Kuo-Chung Tai, Replay and Testing for Concurrent Programs, IEEE Software, v.8 n.2, p.66-74, March 1991 [doi>10.1109/52.73751]
• CT95: R. H. Carver , K. C. Tai, Test sequence generation from formal specifications of distributed programs, Proceedings of the 15th International Conference on Distributed Computing Systems, p.360, May 30-June 02, 1995
• GS91: Susanne Graf , Bernhard Steffen, Compositional Minimization of Finite State Systems, Proceedings of the 2nd International Workshop on Computer Aided Verification, p.186-196, June 18-21, 1990
• GW93: Patrice Godefroid , Pierre Wolper, Using partial orders for the efficient verification of deadlock freedom and safety properties, Formal Methods in System Design, v.2 n.2, p.149-164, April 1993 [doi>10.1007/BF01383879]
• Hoa85: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• HGP92: Gerard J. Holzmann , Patrice Godefroid , Didier Pirottin, Coverage Preserving Reduction Strategies for Reachability Analysis, Proceedings of the IFIP TC6/WG6.1 Twelth International Symposium on Protocol Specification, Testing and Verification XII, p.349-363, June 22-25, 1992
• KS83: Paris C. Kanellakis , Scott A. Smolka, CCS expressions, finite state processes, and three problems of equivalence, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.228-240, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806724]
• KT95: P.V. Koppol and K.C. Tai, "Conformance Testing of Protocols Specified as Labeled Transition Systems", Proc. oj: 8th Intl. workshop on Protocol Test Systems, pp 143-158, Sept. 1995.
• LM87: T. J. LeBlanc , J. M. Mellor-Crummey, Debugging parallel programs with instant replay, IEEE Transactions on Computers, v.36 n.4, p.471-482, April 1987 [doi>10.1109/TC.1987.1676929]
• LSU89: A. M. Lapone, K. K. Sabnani and M. U. Uyar, "An Algorithmic Procedure for Checking Safety Properties of Communication protocols", iEEE Transactions on Communications, pp 940-948, Sept. 1989.
• Mil89: R. Milner, Communication and concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• PT87: Robert Paige , Robert E. Tarjan, Three partition refinement algorithms, SIAM Journal on Computing, v.16 n.6, p.973-989, December 1, 1987 [doi>10.1137/0216062]
• TC95: Kuo-Chung Tai , Richard H. Carver, A Specification-Based Methology for Testing Concurrent Programs, Proceedings of the 5th European Software Engineering Conference, p.154-172, September 25-28, 1995
• TC95a: Tai, K. C., and Carver, R. H., "Testing of Distributed Programs", Chapter 33 o/ Handbook o/ Parallel and Distributed Computing, McGraw Hill, 1995.
• TCO91: Kuo-Chung Tai , Richard H. Carver , Evelyn E. Obaid, Debugging Concurrent Ada Programs by Deterministic Execution, IEEE Transactions on Software Engineering, v.17 n.1, p.45-63, January 1991 [doi>10.1109/32.67578]
• TK93: K.C. Tai and P.V. Koppol, "Hierarchy-Based Incremental Analysis of Communication Protocols", proc. o/Int. Con/. on Network Protocols, pp 318- 325, 1993.
• TLK92: Richard N. Taylor , David L. Levine , Cheryl D. Kelly, Structural Testing of Concurrent Programs, IEEE Transactions on Software Engineering, v.18 n.3, p.206-215, March 1992 [doi>10.1109/32.126769]
• You95: Michal Young , Richard N. Taylor , David L. Levine , Kari A. Nies , Debra Brodbeck, A concurrency analysis tool suite for Ada programs: rationale, design, and preliminary experience, ACM Transactions on Software Engineering and Methodology (TOSEM), v.4 n.1, p.65-106, Jan. 1995 [doi>10.1145/201055.201080]
• YC92: R.-D. Yang , C.-G. Chung, Path analysis testing of concurrent programs, Information and Software Technology, v.34 n.1, p.43-56, Jan. 1992 [doi>10.1016/0950-5849(92)90093-5]
• YY91: Wei Jen Yeh , Michal Young, Compositional reachability analysis using process algebra, Proceedings of the symposium on Testing, analysis, and verification, p.49-59, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120812]
• YY93: W. J. Yeh and M. Young, "Hierarchical Tracing of Concurrent Programs", Proc. o/3rd Irvine Software Symposium, pp 73-84, April 1993.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Algorithms, Theory