The ASTOOT approach to testing object-oriented programs

ABSTRACT

This article describes a new approach to the unit testing of object-oriented programs, a set of tools based on this approach, and two case studies. In this approach, each test case consists of a tuple of sequences of messages, along with tags indicating whether these sequences should put objects of the class under test into equivalent states and/or return objects that are in equivalent states. Tests are executed by sending the sequences to objects of the class under test, then invoking a user-supplied equivalence-checking mechanism. This approach allows for substantial automation of many aspects of testing, including test case generation, test driver generation, test execution, and test checking. Experimental prototypes of tools for test generation and test execution are described. The test generation tool requires the availability of an algebraic specification of the abstract data type being tested, but the test execution tool can be used when no formal specification is available. Using the test execution tools, case studies involving execution of tens of thousands of test cases, with various sequence lengths, parameters, and combinations of operations were performed. The relationships among likelihood of detecting an error and sequence length, range of parameters, and relative frequency of various operations were investigated for priority queue and sorted-list implementations having subtle errors. In each case, long sequences tended to be more likely to detect the error, provided that the range of parameters was sufficiently large and likelihood of detecting an error tended to increase up to a threshold value as the parameter range increased.

REFERENCES

• 1: S. Antoy, Systematic design of algebraic specifications, Proceedings of the 5th international workshop on Software specification and design, p.278-280, April 1989, Pittsburgh, Pennsylvania, United States
• 2: ~ANTOY, S. AND HAMLET, D. 1992. Automatically checking an implementation against its formal ~specification. Tech. Rep. TR 91-1, Rev. 1, Portland State Univ., Portland, Ore.
• 3: ~BARTUSSEK, W. AND PARNAS, n. L. 1986. Using assertions about traces to write abstract ~specifications for software modules. In Software Specification Techniques. Addison-Wesley, ~Reading, Mass., 111-130.
• 4: Gilles Bernot , Marie Claude Gaudel , Bruno Marre, Software testing based on formal specifications: a theory and a tool, Software Engineering Journal, v.6 n.6, p.387-405, Nov. 1991
• 5: ~CHOQUET, N. 1986. Test data generation using a prolog with constraints. In Proceedmgs ofthe ~Workshop on Software Testing. IEEE Computer Society, Washington, D.C., 132-141.
• 6: Roong-Ko Doong, An approach to testing object-oriented programs, Polytechnic University, Brooklyn, NY, 1993
• 7: Roong-Ko Doong , Phyllis G. Frankl, Case studies on testing object-oriented programs, Proceedings of the symposium on Testing, analysis, and verification, p.165-177, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120822]
• 8: J. D. Gannon , R. G. Hamlet , H. D. Mills, Theory of modules, IEEE Transactions on Software Engineering, v.13 n.7, p.820-829, July 1987 [doi>10.1109/TSE.1987.233493]
• 9: John Gannon , Paul McMullin , Richard Hamlet, Data Abstraction, Implementation, Specification, and Testing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.3, p.211-223, July 1981 [doi>10.1145/357139.357140]
• 10: ~GAUDEL, M. AND MARRE, B. 1988. Generation of test data from algebraic specifications. In ~Proceedings of the 2nd Workshop on Software Testing, Verification, and Analysis. IEEE ~Computer Society, Washington, D.C., 138-139.
• 11: ~GOGUEN, J. A. AND WIN}~LER, T. 1988. Introducing OBJ3. Tech. Rep. SRI-CSL-88-9, Computer ~Science Lab., SRI Int., Menlo Park, Calif.
• 12: ~GOGUEN, J. A., THATCHER, J. W., AND WAGNER, E.G. 1978. An initial algebra approach to the ~specification, correctness, and implementation of abstract data types. Current Trends Program. ~Meth. 4, 80-149.
• 13: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 14: ~GUTTAG, J.J. 1980. Notes on type abstraction (version 2). IEEE Trans. Softw. Eng. 6, 1 (Jan.), ~13 23.
• 15: John Guttag, Abstract data types and the development of data structures, Communications of the ACM, v.20 n.6, p.396-404, June 1977 [doi>10.1145/359605.359618]
• 16: ~GUTTAG, J. J. AND HORNING, J.J. 1978. The algebraic specification of abstract data types. Acta ~Inf. 10, 1, 27 52.
• 17: John V. Guttag , Ellis Horowitz , David R. Musser, Abstract data types and software validation, Communications of the ACM, v.21 n.12, p.1048-1064, Dec. 1978 [doi>10.1145/359657.359666]
• 18: Jhon V. Guttag , Ellis Horowitz , David R. Musser, Some extensions to algebraic specifications, Proceedings of an ACM conference on Language design for reliable software, p.63-67, March 28-30, 1977, Raleigh, North Carolina
• 19: D. Hoffman , C. Brealey, Module test case generation, Proceedings of the ACM SIGSOFT '89 third symposium on Software testing, analysis, and verification, p.97-102, December 13-15, 1989, Key West, Florida, United States
• 20: D. Hoffman , Richard Thomas Snodgrass, Trace Specifications: Methodology and Models, IEEE Transactions on Software Engineering, v.14 n.9, p.1243-1252, September 1988 [doi>10.1109/32.6168]
• 21: Daniel M. Hoffman , Paul Strooper, Automated Module Testing in Prolog, IEEE Transactions on Software Engineering, v.17 n.9, p.934-943, September 1991 [doi>10.1109/32.92913]
• 22: Pankaj Jalote, Testing the Completeness of Specifications, IEEE Transactions on Software Engineering, v.15 n.5, p.526-531, May 1989 [doi>10.1109/32.24701]
• 23: ~JALOTE, P. AND CABALLERO, M.G. 1988. Automated testcase generation for data abstraction. In ~Proceedings of COMPSAC 88. IEEE Computer Society, Waghington, D C., 205-210.
• 24: ~KNUTH, D. E. AND BENDIX, P. B. 1970. Simple word problems in universal algebras. In ~Computational Problems in Abstract Algebra. Pergamon Press, Elmsford, N.Y., 263-297.
• 25: ~LISKOV, B. H. AND Z~LLES, S.N. 1975. Specification techniques for data abstractions. IEEE ~Trans. Softw. Eng. 1, i (Mar.), 7-19.
• 26: John McLean, A Formal Method for the Abstract Specification of Software, Journal of the ACM (JACM), v.31 n.3, p.600-627, July 1984 [doi>10.1145/828.829]
• 27: Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 28: ~MUSSER, D.R. 1980. Abstract data type specification in the AFFIRM system. IEEE Trans. ~Softw. Eng. 6, 1 (Jan.), 24-32.
• 29: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 30: ~WEYUKER, E.J. 1982. On testing non-testable programs. Comput. J. 25, 4, 465 470.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Languages
      D.2.5 Testing and Debugging
          Subjects: Symbolic execution
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages
      D.3.3 Language Constructs and Features
          Subjects: Abstract data types

General Terms:
Experimentation, Languages, Reliability

Keywords:
abstract data types, algebraic specification, object-oriented programming, software testing