In black and white: an integrated approach to class-level testing of object-oriented programs

ABSTRACT

Because of the growing importance of object-oriented programming, a number of testing strategies have been proposed. They are based either on pure black-box or white-box techniques. We propose in this article a methodology to integrate the black- and white-box techniques. The black-box technique is used to select test cases. The white-box technique is mainly applied to determine whether two objects resulting from the program execution of a test care are observationally equivalent. It is also used to select test cases in some situations. We define the concept of a fundamental pair as a pair of equivalent terms that are formed by replacing all the variables on both sides of an axiom by normal forms. We prove that an implementation is consistent with respect to all equivalent terms if and only if it is consistent with respect to all fundamental pairs. In other words, the testing coverage of fundamental pairs is as good as that of all possible term rewritings, and hence we need only concentrate on the testing of fundamental pairs. Our strategy is based on mathematical theorems. According to the strategy, we propose an algorithm for selecting a finite set of fundamental pairs as test cases. Given a pair of equivalent terms as a test case, we should then determine whether the objects that result from executing the implemented program are observationally equivalent. We prove, however, that the observational equivalence of objects cannot be determined using a finite set of observable contexts (which are operation sequences ending with an observer function) derived from any black-box technique. Hence we supplement our approach with a “relevant observable context” technique, which is a heuristic white-box technique to select a relevant finite subset of the set of observable contexts for determining the observational equivalence. The relevant observable contezxts are constructed from a data member relevance graph (DRG), which is an abstraction of the given implementation for a given specificatin. A semiautomatic tool hass been developed to support this technique.

REFERENCES

• 1: 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
• 2: L Bougé , N Choquet , L Fribourg , M C Gaudel, Test sets generation from algebraic specifications using logic programming, Journal of Systems and Software, v.6 n.4, p.343-360, Nov. 1986 [doi>10.1016/0164-1212(86)90004-X]
• 3: Ruth Breu , Michael Breu, Abstract and Concrete Objects - An Algebraic Design Method for Object-Based Systems, Proceedings of the Third International Conference on Methodology and Software Technology: Algebraic Methodology and Software Technology, p.343-348, June 21-25, 1993
• 4: T. Y. Chen , C. K. Low, Dynamic Data Flow Analysis for C++, Proceedings of the Second Asia Pacific Software Engineering Conference, p.22, December 06-09, 1995
• 5: CHEN, T. Y. AND LOW, C. K. 1997. Error detection in C++ through dynamic data flow analysis. Softw. Concepts Tools 18, 1, 1-13.
• 6: CHEN, H. Y. AND TSE, T.H. 1997. Towards a new methodology for object-oriented software testing at the class and cluster levels. Tech. Rep. TR-97-07. Dept. of Computer Science. University of Hong Kong, Hong Kong, China.
• 7: CHEN, H. Y., DENG, Y. T., AND TSE, T.H. 1997. ROCS: An object-oriented software testing system at the class level based on the relevant observable context technique. Tech. Rep. TR-97-08, Dept. of Computer Science. University of Hong Kong, Hong Kong, China.
• 8: CLARKE, L.A. 1976. A system to generate test data and symbolically execute programs. IEEE Trans. Softw. Eng. SE-2, 3, 215-222.
• 9: Edward Ira Cohen, A finite domain-testing strategy for computer program testing., 1978
• 10: P. Dauchy , M.-C. Gaudel , B. Marre, Using algebraic specifications in software testing: a case study on the software of an automatic subway, Journal of Systems and Software, v.21 n.3, p.229-244, June 1993 [doi>10.1016/0164-1212(93)90025-S]
• 11: 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]
• 12: Roong-Ko Doong , Phyllis G. Frankl, The ASTOOT approach to testing object-oriented programs, ACM Transactions on Software Engineering and Methodology (TOSEM), v.3 n.2, p.101-130, April 1994 [doi>10.1145/192218.192221]
• 13: ELSHOFF, J. L. 1975. A numerical profile of commercial PL/I programs. Rep. GMR-1927, Computer Science Dept., General Motors Research Laboratory, Warren, MI.
• 14: ELSHOFF, J.L. 1976. An analysis of some commercial PL/I programs. IEEE Trans. Softw. Eng. SE-2, 208-215.
• 15: FIEDLER, S.P. 1989. Object-oriented unit testing. Hewlett-Packard J. 40, 4, 69-74.
• 16: FRANKL, P.G. 1991. A framework for testing object-oriented programs. Tech. Rep. PUCS- 105-91, Dept. of Electrical Engineering and Computer Science, Polytechnic University, Brooklyn, NY.
• 17: FRANKL, P. G. AND DOONG, R.-K. 1990. Tools for testing object-oriented programs. In Proceedings of 8th Pacific Northwest Conference on Software Quality, 309-324.
• 18: 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]
• 19: 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]
• 20: Joseph A. Goguen , Răzvan Diaconescu, Towards an algebraic semantics for the object paradigm, Selected papers from 9th workshop on Specification of abstract data types : recent trends in data type specification: recent trends in data type specification, p.1-29, October 1994, Caldes de Malavella, Spain
• 21: Joseph A. Goguen , José Meseguer, Unifying functional, object-oriented and relational programming with logical semantics, Research directions in object-oriented programming, MIT Press, Cambridge, MA, 1987
• 22: Mary Jean Harrold , John D. McGregor , Kevin J. Fitzpatrick, Incremental testing of object-oriented class structures, Proceedings of the 14th international conference on Software engineering, p.68-80, May 11-15, 1992, Melbourne, Australia [doi>10.1145/143062.143093]
• 23: KNUTH, D. E. 1971. An empirical study of FORTRAN programs. Softw. Pract. Exper. 1, 105-133.
• 24: KUNG, D., GAO, J., HSIA, P., LIN, J., AND TOYOSHIMA, Y. 1993. Design recovery for software testing of object-oriented programs. In Proceedings of the 1st Working Conference on Reverse Engineering (Baltimore, MD). IEEE Press, Piscataway, NJ, 202-211.
• 25: A Test Strategy for Object-Oriented Programs, Proceedings of the 19th International Computer Software and Applications Conference (COMPSAC'95), p.239, August 09-11, 1995
• 26: JALOTE, P. 1983. Specification and testing of abstract data types. In Proceedings of the 7th Annual International Computer Software and Applications Conference. IEEE Computer Society, New York, NY, 508-511.
• 27: Bingchiang Jeng , Elaine J. Weyuker, A simplified domain-testing strategy, ACM Transactions on Software Engineering and Methodology (TOSEM), v.3 n.3, p.254-270, July 1994 [doi>10.1145/196092.193171]
• 28: MILLER, E.F. 1977. Notes on the philosophy of testing. In Proceedings of the 1st Annual International Computer Software and Applications Conference. IEEE Computer Society, New York, NY.
• 29: L. J. Morell, A Theory of Fault-Based Testing, IEEE Transactions on Software Engineering, v.16 n.8, p.844-857, August 1990 [doi>10.1109/32.57623]
• 30: Allen S. Parrish , Richard B. Borie , David W. Cordes, Automated flow graph-based testing of object-oriented software modules, Journal of Systems and Software, v.23 n.2, p.95-109, Nov. 1993 [doi>10.1016/0164-1212(93)90076-A]
• 31: D. E. Perry , G. E. Kaiser, Adequate testing and object-oriented programming, Journal of Object-Oriented Programming, v.2 n.5, p.13-19, Jan./Feb. 1990
• 32: Herbert Schildt, The craft of C: take-charge programming, Osborne/McGraw-Hill, Berkeley, CA, 1992
• 33: M. D. Smith , D. J. Robson, A framework for testing object-oriented programs, Journal of Object-Oriented Programming, v.5 n.3, p.45-53, June 1992
• 34: TURNER, C. D. 1993. State-based testing and inheritance. Tech. Rep. TR-1/93, Computer Science Division, School of Engineering and Computer Science, University of Durham, Durham, UK.
• 35: TURNER, C. D. AND ROBSON, D.J. 1993. Guidance for the testing of object-oriented programs. Tech. Rep. TR-2/93, Computer Science Division, School of Engineering and Computer Science, University of Durham, Durham, UK.
• 36: TURNER, C. D. AND ROBSON, D.J. 1995. A state-based approach to the testing of class-based programs. Softw. Concepts Tools 16, 3, 106-112.
• 37: TSE, T. H. AND GOGUEN, J.n. 1992. Function and object-oriented design (FOOD). Foundations of Information Systems Specification and Design, Dagstuhl Seminar Rep. No. 35. International Conference and Research Center for Computer Science, Wadern, Germany.
• 38: WHITE, L. J. AND COHEN, E.I. 1980. A domain strategy for computer program testing. IEEE Trans. Softw. Eng. SE-6, 3, 247-257.
• 39: David A. Wolfram , Joseph A. Goguen, A Sheaf Semantics for FOOPS Expressions, Proceedings of the Workshop on Object-Based Concurrent Computing, p.81-98, July 15-16, 1991

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Languages

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages

General Terms:
Algorithms, Languages, Reliability

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