Exceptional situations and program reliability

ABSTRACT

It is difficult to write programs that behave correctly in the presence of run-time errors. Proper behavior in the face of exceptional situations is important to the reliability of long-running programs. Existing programming language features often provide poor support for executing clean-up code and for restoring invariants.

We present a data-flow analysis for finding a certain class of exception-handling defects: those related to a failure to release resources or to clean up properly along all paths. Many real-world programs violate such resource usage rules because of incorrect exception handling. Our flow-sensitive analysis keeps track of outstanding obligations along program paths and does a precise modeling of control flow in the presence of exceptions. Using it, we have found over 1,300 exception handling defects in over 5 million lines of Java code.

Based on those defects we propose a programming language feature, the compensation stack, that keeps track of obligations at run time and ensures that they are discharged. We present a type system for compensation stacks that tracks collections of obligations. Finally, we present case studies to demonstrate that this feature is natural, efficient, and can improve reliability.

REFERENCES

• 1: Abrial, J.-R., Schuman, S. A., and Meyer, B. 1980. Specification language. In On the Construction of Programs. 343--410.
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: Gustavo Alonso , Claus Hagen , Divyakant Agrawal , Amr El Abbadi , C. Mohan, Enhancing the Fault Tolerance of Workflow Management Systems, IEEE Concurrency, v.8 n.3, p.74-81, July 2000 [doi>10.1109/4434.865896 ]
• 4: Alonso, G., Kamath, M., Agrawal, D., Abbadi, A. E., Gunthor, R., and Mohan, C. 1994. Failure handling in large-scale workflow management systems. Tech. Rep. RJ9913, IBM Almaden Research Center, San Jose, CA. Nov.
• 5: Thomas Ball , Sriram K. Rajamani, Automatically validating temporal safety properties of interfaces, Proceedings of the 8th international SPIN workshop on Model checking of software, p.103-122, May 2001, Toronto, Ontario, Canada
• 6: Ball, T. and Rajamani, S. K. 2001b. SLIC: A specification language for interface checking (of C). Tech. Rep. MSR-TR-2001-21, Microsoft Research.
• 7: Hans-J. Boehm, Destructors, finalizers, and synchronization, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.262-272, January 15-17, 2003, New Orleans, Louisiana, USA
• 8: Anita Borg , Wolfgang Blau , Wolfgang Graetsch , Ferdinand Herrmann , Wolfgang Oberle, Fault tolerance under UNIX, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.1-24, Feb. 1989 [doi>10.1145/58564.58565]
• 9: Aaron B. Brown , David A. Patterson, Undo for operators: building an undoable e-mail store, Proceedings of the annual conference on USENIX Annual Technical Conference, p.1-1, June 09-14, 2003, San Antonio, Texas
• 10: Magiel Bruntink , Arie van Deursen , Tom Tourwé, Discovering faults in idiom-based exception handling, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134320]
• 11: Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304113]
• 12: Campione, M., Walrath, K., and Huml, A. 2000. The Java Tutorial. Addison-Wesley, Reading, MA.
• 13: George Candea , Mauricio Delgado , Michael Chen , Armando Fox, Automatic Failure-Path Inference: A Generic Introspection Technique for Internet Applications, Proceedings of the The Third IEEE Workshop on Internet Applications, p.132, June 23-24, 2003
• 14: Luca Cardelli , Rowan Davies, Service Combinators for Web Computing, IEEE Transactions on Software Engineering, v.25 n.3, p.309-316, May 1999 [doi>10.1109/32.798321 ]
• 15: Cargill, T. 1994. Exception handling: A false sense of security. C++ Report 6, 9.
• 16: Byeong-Mo Chang , Jang-Wu Jo , Kwangkeun Yi , Kwang-Moo Choe, Interprocedural exception analysis for Java, Proceedings of the 2001 ACM symposium on Applied computing, p.620-625, March 2001, Las Vegas, Nevada, United States [doi>10.1145/372202.372786]
• 17: Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Complexity of Points-To Analysis of Java in the Presence of Exceptions, IEEE Transactions on Software Engineering, v.27 n.6, p.481-512, June 2001 [doi>10.1109/32.926173 ]
• 18: Mike Y. Chen , Emre Kiciman , Eugene Fratkin , Armando Fox , Eric Brewer, Pinpoint: Problem Determination in Large, Dynamic Internet Services, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.595-604, June 23-26, 2002
• 19: 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
• 20: F. Cristian, Exception Handling and Software Fault Tolerance, IEEE Transactions on Computers, v.31 n.6, p.531-540, June 1982 [doi>10.1109/TC.1982.1676035]
• 21: Cristian, F. 1987. Exception handling. Tech. Rep. RJ5724, IBM Research.
• 22: Asit Dan , Daniel M. Dias , Thao Nguyen , Marty Sachs , Hidayatullah Shaikh , Richard King , Sastry Duri, The Coyote Project: Framework for Multi-party E-Commerce, Proceedings of the Second European Conference on Research and Advanced Technology for Digital Libraries, p.873-889, September 21-23, 1998
• 23: Manuvir Das , Sorin Lerner , Mark Seigle, ESP: path-sensitive program verification in polynomial time, ACM SIGPLAN Notices, v.37 n.5, May 2002
• 24: Umeshwar Dayal , Meichun Hsu , Rivka Ladin, Organizing long-running activities with triggers and transactions, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.204-214, May 23-26, 1990, Atlantic City, New Jersey, United States
• 25: Robert DeLine , Manuel Fähndrich, Enforcing high-level protocols in low-level software, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.59-69, June 2001, Snowbird, Utah, United States
• 26: Demsky, B. and Rinard, M. C. 2003. Automatic data structure repair for self-healing systems. In Proceedings of the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications. ACM, New York.
• 27: Christophe Dony, A Fully Object-Oriented Exception Handling System: Rationale and Smalltalk Implementation, Advances in Exception Handling Techniques (the book grow out of a ECOOP 2000 workshop), p.18-38, January 2001
• 28: Dawson Engler , Benjamin Chelf , Andy Chou , Seth Hallem, Checking system rules using system-specific, programmer-written compiler extensions, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.1-1, October 22-25, 2000, San Diego, California
• 29: Manuel Fahndrich , Robert DeLine, Adoption and focus: practical linear types for imperative programming, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 30: Stephen Fink , Eran Yahav , Nurit Dor , G. Ramalingam , Emmanuel Geay, Effective typestate verification in the presence of aliasing, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA [doi>10.1145/1146238.1146254]
• 31: Chen Fu , Ana Milanova , Barbara Gershon Ryder , David G. Wonnacott, Robustness Testing of Java Server Applications, IEEE Transactions on Software Engineering, v.31 n.4, p.292-311, April 2005 [doi>10.1109/TSE.2005.51]
• 32: Chen Fu , Barbara G. Ryder , Ana Milanova , David Wonnacott, Testing of java web services for robustness, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA
• 33: Hector Garcia-Molina , Kenneth Salem, Sagas, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.249-259, May 27-29, 1987, San Francisco, California, United States
• 34: David Gay , Alex Aiken, Memory management with explicit regions, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.313-323, June 17-19, 1998, Montreal, Quebec, Canada
• 35: General Services Administration. 1996. Telecommunications: Glossary of Telecommunication terms. Tech. Rep. Federal Standard 1037C, National Communications System Technology & Standards Division. Aug.
• 36: John B. Goodenough, Exception handling: issues and a proposed notation, Communications of the ACM, v.18 n.12, p.683-696, Dec. 1975 [doi>10.1145/361227.361230]
• 37: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 38: Jim Gray, The transaction concept: virtues and limitations (invited paper), Proceedings of the seventh international conference on Very Large Data Bases, p.144-154, September 09-11, 1981, Cannes, France
• 39: Manish Gupta , Jong-Deok Choi , Michael Hind, Optimizing Java Programs in the Presence of Exceptions, Proceedings of the 14th European Conference on Object-Oriented Programming, p.422-446, June 12-16, 2000
• 40: Claus Hagen , Gustavo Alonso, Exception Handling in Workflow Management Systems, IEEE Transactions on Software Engineering, v.26 n.10, p.943-958, October 2000 [doi>10.1109/32.879818 ]
• 41: Matthias Hauswirth , Trishul M. Chilimbi, Low-overhead memory leak detection using adaptive statistical profiling, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 42: Hejlsberg, A., Wilamuth, S., and Golde, P. 2003. The C# Programming Language. Addison-Wesley, Reading, MA.
• 43: Hibernate. 2004. Object/relational mapping and transparent object persistence for Java and SQL databases. In http://www.hibernate.org/.
• 44: John E. Hopcroft , Rajeev Motwani , Rotwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computability, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 45: David Hovemeyer , William Pugh, Finding bugs is easy, Companion to the 19th annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 24-28, 2004, Vancouver, BC, CANADA [doi>10.1145/1028664.1028717]
• 46: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 47: Henry F. Korth , Eliezer Levy , Abraham Silberschatz, A Formal Approach to Recovery by Compensating Transactions, Proceedings of the 16th International Conference on Very Large Data Bases, p.95-106, August 13-16, 1990
• 48: Ben Liblit , Alex Aiken , Alice X. Zheng , Michael I. Jordan, Bug isolation via remote program sampling, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 49: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 50: Barbara Liskov , Robert Scheifler, Guardians and Actions: Linguistic Support for Robust, Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.381-404, July 1983 [doi>10.1145/2166.357215]
• 51: Chengfei Liu , Maria E. Orlowska , Xuemin Lin , Xiaofang Zhou, Improving Backward Recovery in Workflow Systems, Proceedings of the 7th International Conference on Database Systems for Advanced Applications, p.276, April 18-20, 2001
• 52: David E. Lowell , Subhachandra Chandra , Peter M. Chen, Exploring failure transparency and the limits of generic recovery, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.20-20, October 22-25, 2000, San Diego, California
• 53: Lowell, D. E. and Chen, P. M. 1998. Discount checking: transparent, low-overhead recovery for general applications. Tech. Rep. CSE-TR-410-99, University of Michigan. Nov.
• 54: Malayeri, D. and Aldrich, J. 2006. Practical exception specifications. In Advanced Topics in Exception Handling Techniques, C. Dony, J. L. Knudsen, A. B. Romanovsky, and A. Tripathi, Eds. Lecture Notes in Computer Science, vol. 4119. Springer-Verlag, New York. 200--220.
• 55: Miller, R. and Tripathi, A. 1997. Issues with exception handling in object-oriented systems. In Proceedings of the 11th European Conference on Object-Oriented Programming (ECOOP). 85--103.
• 56: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 57: George C. Necula , Scott McPeak , Westley Weimer, CCured: type-safe retrofitting of legacy code, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.128-139, January 16-18, 2002, Portland, Oregon
• 58: Martin Odersky , Philip Wadler, Pizza into Java: translating theory into practice, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.146-159, January 15-17, 1997, Paris, France [doi>10.1145/263699.263715]
• 59: O'Hanley, J. 2005. Always close streams. In http://www.javapractices.com/.
• 60: Perry, E. H., Sanko, M., Wright, B., and Pfaeffle, T. 2002. Oracle9i JDBC developer's guide and reference. Tech. Rep. A96654-01 (Release 2 (9.2)), http://www.oracle.com. Mar.
• 61: Darrell Reimer , Edith Schonberg , Kavitha Srinivas , Harini Srinivasan , Bowen Alpern , Robert D. Johnson , Aaron Kershenbaum , Larry Koved, SABER: smart analysis based error reduction, ACM SIGSOFT Software Engineering Notes, v.29 n.4, July 2004
• 62: Thomas Reps , Susan Horwitz , Mooly Sagiv, Precise interprocedural dataflow analysis via graph reachability, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-61, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199462]
• 63: 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]
• 64: Barbara G. Ryder , Donald Smith , Ulrich Kremer , Michael Gordon , Nirav Shah, A Static Study of Java Exceptions Using JESP, Proceedings of the 9th International Conference on Compiler Construction, p.67-81, March 25-April 02, 2000
• 65: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 66: Frank Schmuck , Jim Wylie, Experience with transactions in QuickSilver, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.239-253, October 13-16, 1991, Pacific Grove, California, United States
• 67: Margo I. Seltzer , Yasuhiro Endo , Christopher Small , Keith A. Smith, Dealing with disaster: surviving misbehaved kernel extensions, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.213-227, October 29-November 01, 1996, Seattle, Washington, United States
• 68: Jonathan S. Shapiro , Jonathan M. Smith , David J. Farber, EROS: a fast capability system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.170-185, December 12-15, 1999, Charleston, South Carolina, United States
• 69: 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
• 70: 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 ]
• 71: Saurabh Sinha , Alessandro Orso , Mary Jean Harrold, Automated Support for Development, Maintenance, and Testing in the Presence of Implicit Control Flow, Proceedings of the 26th International Conference on Software Engineering, p.336-345, May 23-28, 2004
• 72: SourceForge.net. 2003. About SourceForge.net (document A1). http://sourceforge.net. Tech. rep.
• 73: Stallman, R., Pesch, R., and Shebs, S. 2002. Debugging with GDB. Free Software Foundation.
• 74: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 75: Sun Microsystems. 2001. Java pet store 1.1.2 blueprint application. http://java.sun.com/blueprints/code/. Tech. rep.
• 76: Mads Tofte , Jean-Pierre Talpin, Region-based memory management, Information and Computation, v.132 n.2, p.109-176, Feb. 1, 1997 [doi>10.1006/inco.1996.2613 ]
• 77: Giuseppe Valetto , Gail Kaiser, A case study in software adaptation, Proceedings of the first workshop on Self-healing systems, November 18-19, 2002, Charleston, South Carolina [doi>10.1145/582128.582142]
• 78: van der Wal, S. 2002. Creating the C++ auto_ptr<> utility for Symbian OS. Tech. rep., http://www.symbian.com/developer/techlib/. Aug.
• 79: Wagner, D., Foster, J. S., Brewer, E. A., and Aiken, A. 2000. A first step towards automated detection of buffer overrun vulnerabilities. In Proceedings of the Networking and Distributed System Security Symposium 2000 (San Diego, CA).
• 80: Westley Weimer , George C. Necula, Finding and preventing run-time error handling mistakes, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 81: Weimer, W. and Necula, G. C. 2005. Mining temporal specifications for error detection. Lecture Notes in Computer Science, vol. 3440. Springer-Verlag, New York. 461--476.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
      D.2.5 Testing and Debugging
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability

General Terms:
Design, Languages, Reliability, Verification

Keywords:
Error handling, compensating transactions, linear sagas, linear types, resource management