Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper presents a new compile-time analysis that enables a testing methodology for white-box coverage testing of error recovery code (i.e., exception handlers) in Java web services using compiler-directed fault injection. The analysis allows compiler-generated instrumentation to guide the fault injection and to record the recovery code exercised. (An injected fault is experienced as a Java exception.) The analysis (i) identifies the exception-flow 'def-uses' to be tested in this manner, (ii) determines the kind of fault to be requested at a program point, and (iii) finds appropriate locations for code instrumentation. The analysis incorporates refinements that establish sufficient context sensitivity to ensure relatively precise def-use links and to eliminate some spurious def-uses due to demonstrably infeasible control flow. A runtime test harness calculates test coverage of these links using an exception def-catch metric. Experiments with the methodology demonstrate the utility of the increased precision in obtaining good test coverage on a set of moderately-sized Java web services benchmarks.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: J. Arlat , A. Costes , Y. Crouzet , J. C. Laprie , D. Powell, Fault Injection and Dependability Evaluation of Fault-Tolerant Systems, IEEE Transactions on Computers, v.42 n.8, p.913-923, August 1993 [doi>10.1109/12.238482]
• 3: Ken Arnold , James Gosling, The Java programming language (2nd ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1998
• 4: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
• 5: Robert V. Binder, Testing object-oriented systems: models, patterns, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 6: Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Refining data flow information using infeasible paths, Proceedings of the 6th European conference held jointly with the 5th ACM SIGSOFT international symposium on Foundations of software engineering, p.361-377, September 22-25, 1997, Zurich, Switzerland
• 7: Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Relevant context inference, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-146, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292554]
• 8: Jong-Deok Choi , David Grove , Michael Hind , Vivek Sarkar, Efficient and precise modeling of exceptions for the analysis of Java programs, Proceedings of the 1999 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.21-31, September 06-06, 1999, Toulouse, France
• 9: Michał Cierniak , Guei-Yuan Lueh , James M. Stichnoth, Practicing JUDO: Java under dynamic optimizations, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.13-26, June 18-21, 2000, Vancouver, British Columbia, Canada
• 10: Michel Cukier , Ramesh Chandra , David Henke , Jessica Pistole , William H. Sanders, Fault Injection Based on a Partial View of the Global State of a Distributed System, Proceedings of the 18th IEEE Symposium on Reliable Distributed Systems, p.168, October 18-21, 1999
• 11: David Grove , Greg DeFouw , Jeffrey Dean , Craig Chambers, Call graph construction in object-oriented languages, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.108-124, October 05-09, 1997, Atlanta, Georgia, United States
• 12: S. Dawson, F. Jahanian, and T. Mitton. ORCHESTRA: A Fault Injection Environment for Distributed Systems. In Proc. 26th Int. Symp. on Fault Tolerant Computing(FTCS-26), pages 404--414, Sendai, Japan, June 1996.
• 13: Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
• 14: P. G. Frankl , E. J. Weyuker, An Applicable Family of Data Flow Testing Criteria, IEEE Transactions on Software Engineering, v.14 n.10, p.1483-1498, October 1988 [doi>10.1109/32.6194]
• 15: C. Fu, R. P. Martin, K. Nagaraja, T. D. Nguyen, B. G. Ryder, and D. Wonnacott. Compiler-directed program-fault coverage for highly available Java internet services. In Proceedings of the International Conference on Dependable Systems and Networks (DSN 2003), June 2003.
• 16: David Grove , Craig Chambers, A framework for call graph construction algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.6, p.685-746, November 2001 [doi>10.1145/506315.506316]
• 17: R. G. Hamlet. Testing programs with the aid of a compiler. IEEE Transactions on Software Engineering, 3(4):279--290, July 1977.
• 18: DOCTOR: an integrated software fault injection environment for distributed real-time systems, Proceedings of the International Computer Performance and Dependability Symposium on Computer Performance and Dependability Symposium, p.204, April 24-26, 1995
• 19: Nevin Heintze, Set-based analysis of ML programs, Proceedings of the 1994 ACM conference on LISP and functional programming, p.306-317, June 27-29, 1994, Orlando, Florida, United States
• 20: Jang-Wu Jo , Byeong-Mo Chang , Kwangkeun Yi , Kwang-Moo Choe, An uncaught exception analysis for Java, Journal of Systems and Software, v.72 n.1, p.59-69, June 2004 [doi>10.1016/S0164-1212(03)00057-8]
• 21: G. A. Kanawati, N. A. Kanawati, and J. A. Abraham. FERRARI: A Tool for the Validation of System Dependability Properties. In Proc. 22nd Int. Symp. on Fault Tolerant Computing(FTCS-22), pages 336--344, Boston, Massachusetts, 1992. IEEE Computer Society Press.
• 22: S. Lee, B.-S. Yang, S. Kim, S. Park, S.-M. Moon, K. Ebcioglu, and E. Altman. Efficient Java exception handling in just-in-time compilation.
• 23: O. Lhoták and L. Hendren. Scaling Java points-to analysis using Spark. LNCS 2622, pages 153--169, 2003.
• 24: X. Li, R. P. Martin, K. Nagaraja, T. D. Nguyen, and B. Zhang. Mendosus: A SAN-Based Fault-Injection Test-Bed for the Construction of Highly Available Network Services. In Proceedings of the 1st Workshop on Novel Uses of System Area Networks (SAN-1), Cambridge, MA, Jan. 2002.
• 25: T. J. Marlowe , B. G. Ryder, Properties of data flow frameworks: a unified model, Acta Informatica, v.28 n.2, p.121-163, Dec. 1990 [doi>10.1007/BF01237234]
• 26: Ana Lubenova Milanova , Barbara Gershon Ryder, Precise and practical flow analysis of object-oriented software, 2003
• 27: Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to and side-effect analyses for Java, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 28: The Muffin world wide web filtering system. See http://muffin.doit.org/.
• 29: Glenford J. Myers, Art of Software Testing, John Wiley & Sons, Inc., New York, NY, 1979
• 30: Robert Weeks O'Callahan , Jeannette Wing , Daniel Jackson, Generalized aliasing as a basis for program analysis tools, 2001
• 31: Takeshi Ogasawara , Hideaki Komatsu , Toshio Nakatani, A study of exception handling and its dynamic optimization in Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.83-95, October 14-18, 2001, Tampa Bay, FL, USA
• 32: M. J. Radwin. The java network file system. See http://www.radwin.org/michael/projects/jnfs/.
• 33: Sandra Rapps , Elaine J. Weyuker, Selecting software test data using data flow information, IEEE Transactions on Software Engineering, v.11 n.4, p.367-375, April 1985 [doi>10.1109/TSE.1985.232226]
• 34: Martin P. Robillard , Gail C. Murphy, Static analysis to support the evolution of exception structure in object-oriented systems, ACM Transactions on Software Engineering and Methodology (TOSEM), v.12 n.2, p.191-221, April 2003 [doi>10.1145/941566.941569]
• 35: Atanas Rountev , Ana Milanova , Barbara G. Ryder, Points-to analysis for Java using annotated constraints, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.43-55, October 14-18, 2001, Tampa Bay, FL, USA
• 36: B. G. Ryder. Dimensions of precision in reference analysis of object-oriented programming languages. In Proceedings of the Twelveth International Conference on Compiler Construction, pages 126--137, April 2003. invited paper.
• 37: M. Sable. Soot: a java optimization framework. See http://www.sable.mcgill.ca/soot/.
• 38: Michael L. Scott, Programming language pragmatics, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 39: Z. Segall, D. Vrsalovic, D. Siewiorek, D. Yaskin, J. Kownacki, J. Barton, D. Rancey, A. Robinson, and T. Lin. FIAT -- Fault Injection based Automated Testing environment. In Proc. 18th Int. Symp. on Fault-Tolerant Computing (FTCS-18), pages 102--107, Tokyo, Japan, 1988. IEEE Computer Society Press.
• 40: M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. In S. Muchnick and N. Jones, editors, Program Flow Analysis: Theory and Applications, pages 189--234. 1981.
• 41: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 42: Saurabh Sinha , Mary Jean Harrold, Criteria for Testing Exception-Handling Constructs in Java Programs, Proceedings of the IEEE International Conference on Software Maintenance, p.265, August 30-September 03, 1999
• 43: Saurabh Sinha , Mary Jean Harrold, Analysis and Testing of Programs with Exception Handling Constructs, IEEE Transactions on Software Engineering, v.26 n.9, p.849-871, September 2000 [doi>10.1109/32.877846]
• 44: S. Sinha, A. Orso, and M. J. Harrold. Automated support for development, maintenance, and testing in the presence of implicit control flow. Technical Report GIT-CC-03-48, College of Computing, Georgia Institute of Technology, September 2003.
• 45: A. L. Souter and L. L. Pollock. Type infeasible call chains. In Proceedings of the IEEE International Workshop on Source Code Analysis and Manipulation, 2001.
• 46: A. L. Souter and L. L. Pollock. Characterization and automatic identification of type infeasible call chains. Information and Software Technology, 44(13):721--732, October 2002.
• 47: Specbench.org. Java client/server benchmarks.
• 48: Matt Welsh , David Culler , Eric Brewer, SEDA: an architecture for well-conditioned, scalable internet services, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Error handling and recovery; Testing tools (e.g., data generators, coverage testing)
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Reliability

Keywords:
def-use testing, exceptions, java, test coverage metrics