Finding and preventing run-time error handling mistakes

ABSTRACT

It is difficult to write programs that behave correctly in the presence of run-time errors. Existing programming language features often provide poor support for executing clean-up code and for restoring invariants in such exceptional situations. We present a dataflow analysis for finding a certain class of error-handling mistakes: those that arise from a failure to release resources or to clean up properly along all paths. Many real-world programs violate such resource safety policies because of incorrect error 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 800 error handling mistakes almost 4 million lines of Java code. The analysis is unsound and produces false positives, but a few simple filtering rules suffice to remove them in practice. The remaining mistakes were manually verified. These mistakes cause sockets, files and database handles to be leaked along some paths. We present a characterization of the most common causes of those errors and discuss the limitations of exception handling, finalizers and destructors in addressing them. Based on those errors, we propose a programming language feature that keeps track of obligations at run time and ensures that they are discharged. Finally, we present case studies to demonstrate that this feature is natural, efficient, and can improve reliability; for example, retrofitting a 34kLOC program with it resulted in a 0.5% code size decrease, a surprising 17% speed increase (from correctly deallocating resources in the presence of exceptions), and more consistent behavior.

REFERENCES

• 1: Advisor. Beware: 10 common web application security risks. Technical Report Doc 11756, Security Advisor Portal, Jan. 2003.
• 2: 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]
• 3: Glenn Ammons , Rastislav Bodík , James R. Larus, Mining specifications, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.4-16, January 16-18, 2002, Portland, Oregon
• 4: Philip Baldwin , Sanjeev Kohli , Edward A. Lee , Xiaojun Liu , Yang Zhao, Modeling of sensor nets in Ptolemy II, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984675]
• 5: 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
• 6: 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]
• 7: A. Brown and D. Patterson. Undo for operators: Building an undoable e-mail store. In USENIX Annual Technical Conference, 2003.
• 8: 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
• 9: 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]
• 10: T. Cargill. Exception handling: a false sense of security. C++ Report, 6(9), 1994.
• 11: 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
• 12: F. Cristian. Exception handling. Technical Report RJ5724, IBM Research, 1987.
• 13: Manuvir Das , Sorin Lerner , Mark Seigle, ESP: path-sensitive program verification in polynomial time, ACM SIGPLAN Notices, v.37 n.5, May 2002
• 14: 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
• 15: 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
• 16: B. Demsky and M. C. Rinard. Automatic data structure repair for self-healing systems. In ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2003.
• 17: Christophe Dony, A fully object-oriented exception handling system: rationale and smalltalk implementation, Advances in exception handling techniques, Springer-Verlag New York, Inc., New York, NY, 2001
• 18: D. Engler, B. Chelf, A. Chou, and S. Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In Symposium on Operating Systems Design and Implementation, 2000.
• 19: Dawson Engler , David Yu Chen , Seth Hallem , Andy Chou , Benjamin Chelf, Bugs as deviant behavior: a general approach to inferring errors in systems code, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 20: 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
• 21: 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
• 22: 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
• 23: 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]
• 24: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 25: J. Gray. The transaction concept: virtues and limitations. In International Conference on Very Large Data Bases, pages 144--154. Cannes, France, Sept. 1981.
• 26: Claus Hagen , Gustavo Alonso, Flexible Exception Handling in the OPERA Process Support System, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.526, May 26-29, 1998
• 27: 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]
• 28: Sudheendra Hangal , Monica S. Lam, Tracking down software bugs using automatic anomaly detection, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581377]
• 29: 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]
• 30: 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
• 31: Roy Levin, Program structures for exceptional condition handling., 1977
• 32: 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]
• 33: 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
• 34: D. E. Lowell, S. Chandra, and P. M. Chen. Exploring failure transparency and the limits of generic recovery. In USENIX Symposium on Operating Systems Design and Implementation, Oct. 2000.
• 35: D. E. Lowell and P. M. Chen. Discount checking: transparent, low-overhead recovery for general applications. Technical Report CSE-TR-410-99, University of Michigan, Nov. 1998.
• 36: R. Miller and A. Tripathi. Issues with exception handling in object-oriented systems. In Object-Oriented Programming, 11th European Conference (ECOOP), pages 85--103, 1997.
• 37: 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]
• 38: Martin P. Robillard , Gail C. Murphy, Regaining Control of Exception Handling, University of British Columbia, Vancouver, BC, Canada, 1999
• 39: 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
• 40: 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
• 41: SourceForge.net. About SourceForge.net (document A1). http://sourceforge.net. Technical report, 2003.
• 42: Sun Microsystems. Java pet store 1.1.2 blueprint application. http://java.sun.com/blueprints/code/. Technical report, 2001.
• 43: 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]
• 44: 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]
• 45: Shaula Yemini , Daniel M. Berry, A modular verifiable exception handling mechanism, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.214-243, April 1985 [doi>10.1145/3318.3320]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Experimentation, Languages, Measurement, Reliability, Verification

Keywords:
dataflow, destructors, exceptions, finalizers, try-finally