Rx: treating bugs as allergies---a safe method to survive software failures

ABSTRACT

Many applications demand availability. Unfortunately, software failures greatly reduce system availability. Prior work on surviving software failures suffers from one or more of the following limitations: Required application restructuring, inability to address deterministic software bugs, unsafe speculation on program execution, and long recovery time.This paper proposes an innovative safe technique, called Rx, which can quickly recover programs from many types of software bugs, both deterministic and non-deterministic. Our idea, inspired from allergy treatment in real life, is to rollback the program to a recent checkpoint upon a software failure, and then to re-execute the program in a modified environment. We base this idea on the observation that many bugs are correlated with the execution environment, and therefore can be avoided by removing the "allergen" from the environment. Rx requires few to no modifications to applications and provides programmers with additional feedback for bug diagnosis.We have implemented RX on Linux. Our experiments with four server applications that contain six bugs of various types show that RX can survive all the six software failures and provide transparent fast recovery within 0.017-0.16 seconds, 21-53 times faster than the whole program restart approach for all but one case (CVS). In contrast, the two tested alternatives, a whole program restart approach and a simple rollback and re-execution without environmental changes, cannot successfully recover the three servers (Squid, Apache, and CVS) that contain deterministic bugs, and have only a 40% recovery rate for the server (MySQL) that contains a non-deterministic concurrency bug. Additionally, RX's checkpointing system is lightweight, imposing small time and space overheads.

REFERENCES

• 1: Lorenzo Alvisi , Keith Marzullo, Trade-offs in implementing causal message logging protocols, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.58-67, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248061]
• 2: Cristiana Amza , Alan L. Cox , Willy Zwaenepoel, Data Replication Strategies for Fault Tolerance and Availability on Commodity Clusters, Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8), p.459, June 25-28, 2000
• 3: A. Avizienis. The N-version approach to fault-tolerant software. IEEE Transactions on Software Engineering, SE-11(12), 1985.
• 4: A. Avizienis and L. Chen. On the implementation of N-version programming for software fault tolerance during execution. In Proceedings of the 1st International Computer Software and Applications Conference, Nov 1977.
• 5: Joel F. Bartlett, A NonStop kernel, Proceedings of the eighth ACM symposium on Operating systems principles, p.22-29, December 14-16, 1981, Pacific Grove, California, United States
• 6: Kenneth P. Birman, Building Secure and Reliable Network Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1996
• 7: A. Bobbio and M. Sereno. Fine grained software rejuvenation models. In Proceedings of the 1998 International Computer Performance and Dependability Symposium, Sep 1998.
• 8: Aniruddha Bohra , Iulian Neamtiu , Florin Sultan, Remote Repair of Operating System State Using Backdoors, Proceedings of the First International Conference on Autonomic Computing (ICAC'04), p.256-263, May 17-18, 2004
• 9: Anita Borg , Jim Baumbach , Sam Glazer, A message system supporting fault tolerance, Proceedings of the ninth ACM symposium on Operating systems principles, p.90-99, October 10-13, 1983, Bretton Woods, New Hampshire, United States
• 10: 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]
• 11: Thomas C. Bressoud , Fred B. Schneider, Hypervisor-based fault tolerance, ACM Transactions on Computer Systems (TOCS), v.14 n.1, p.80-107, Feb. 1996 [doi>10.1145/225535.225538]
• 12: George Candea , James Cutler , Armando Fox , Rushabh Doshi , Priyank Garg , Rakesh Gowda, Reducing Recovery Time in a Small Recursively Restartable System, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.605-614, June 23-26, 2002
• 13: G. Candea, S. Kawamoto, Y. Fujiki, G. Friedman, and A. Fox. Microreboot -- A technique for cheap recovery. In Proceedings of the 6th Symposium on Operating System Design and Implementation, Dec 2004.
• 14: Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
• 15: M. Castro and B. Liskov. Proactive recovery in a Byzantine-Fault-Tolerant system. In Proceedings of the 4th Symposium on Operating System Design and Implementation, Oct 2000.
• 16: CERT/CC. Advisories. http://www.cert.org/advisories/.
• 17: Subhachandra Chandra , Peter M. Chen, Whither Generic Recovery from Application Faults? A Fault Study using Open-Source Software, Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8), p.97-106, June 25-28, 2000
• 18: Subhachandra Chandra , Peter M. Chen, The Impact of Recovery Mechanisms on the Likelihood of Saving Corrupted State, Proceedings of the 13th International Symposium on Software Reliability Engineering (ISSRE'02), p.91, November 12-15, 2002
• 19: Yuqun Chen , James S. Plank , Kai Li, CLIP: a checkpointing tool for message-passing parallel programs, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-11, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509626]
• 20: Jeremy Condit , Matthew Harren , Scott McPeak , George C. Necula , Westley Weimer, CCured in the real world, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 21: C. Cowan, C. Pu, D. Maier, J. Walpole, P. Bakke, S. Beattie, A. Grier, P. Wagle, Q. Zhang, and H. Hinton. StackGuard: Automatic adaptive detection and prevention of buffer-overflow attacks. In Proceedings of the 7th USENIX Security Symposium, Jan 1998.
• 22: George W. Dunlap , Samuel T. King , Sukru Cinar , Murtaza A. Basrai , Peter M. Chen, ReVirt: enabling intrusion analysis through virtual-machine logging and replay, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060309]
• 23: E. N. (Mootaz) Elnozahy , Lorenzo Alvisi , Yi-Min Wang , David B. Johnson, A survey of rollback-recovery protocols in message-passing systems, ACM Computing Surveys (CSUR), v.34 n.3, p.375-408, September 2002 [doi>10.1145/568522.568525]
• 24: Yishai A. Feldman , Haim Schneider, Simulating reactive systems by deduction, ACM Transactions on Software Engineering and Methodology (TOSEM), v.2 n.2, p.128-175, April 1993 [doi>10.1145/151257.151259]
• 25: S. Garg, A. Puliafito, M. Telek, and K. S. Trivedi. On the analysis of software rejuvenation policies. In Proceedings of the Annual Conference on Computer Assurance, Jun 1997.
• 26: J. Gray. Why do computers stop and what can be done about it? In Proceedings of the 5th Symposium on Reliable Distributed Systems, Jan 1986.
• 27: W. Gu, Z. Kalbarczyk, R. K. Iyer, and Z.-Y. Yang. Characterization of Linux kernel behavior under errors. In Proceedings of the 2003 International Conference on Dependable Systems and Networks, Jun 2003.
• 28: R. Hasting and B. Joyce. Purify: Fast detection of memory leaks and access errors. In Proceedings of the USENIX Winter 1992 Technical Conference, Dec 1992.
• 29: Nick Kolettis , N. Dudley Fulton, Software Rejuvenation: Analysis, Module and Applications, Proceedings of the Twenty-Fifth International Symposium on Fault-Tolerant Computing, p.381, June 27-30, 1995
• 30: David B. Johnson , Willy Zwaenepoel, Recovery in distributed systems using asynchronous message logging and checkpointing, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.171-181, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62575]
• 31: David B. Johnson , Willy Zwaenepoel, Recovery in distributed systems using optimistic message logging and check-pointing, Journal of Algorithms, v.11 n.3, p.462-491, Sep. 1990 [doi>10.1016/0196-6774(90)90022-7]
• 32: K. Li , J. F. Naughton , J. S. Plank, Real-time, concurrent checkpoint for parallel programs, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.79-88, March 14-16, 1990, Seattle, Washington, United States
• 33: D. E. Lowell, S. Chandra, and P. M. Chen. Exploring failure transparency and the limits of generic recovery. In Proceedings of the 4th Symposium on Operating System Design and Implementation, Oct 2000.
• 34: David E. Lowell , Peter M. Chen, Free transactions with Rio Vista, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.92-101, October 05-08, 1997, Saint Malo, France
• 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, Jul 1998.
• 36: E. Marcus and H. Stern. Blueprints for High Availability. John Willey & Sons, 2000.
• 37: David Mosberger , Tai Jin, httperf—a tool for measuring web server performance, ACM SIGMETRICS Performance Evaluation Review, v.26 n.3, p.31-37, Dec. 1998 [doi>10.1145/306225.306235]
• 38: David Patterson , Aaron Brown , Pete Broadwell , George Candea , Mike Chen , James Cutler , Patricia Enriquez , Armando Fox , Emre Kiciman , Matthew Merzbacher , David Oppenheimer , Naveen Sastry , William Tetzlaff , Jonathan Traupman , Noah Treuhaft, Recovery Oriented Computing (ROC): Motivation, Definition, Techniques,, University of California at Berkeley, Berkeley, CA, 2002
• 39: James S. Plank , Kai Li , Michael A. Puening, Diskless Checkpointing, IEEE Transactions on Parallel and Distributed Systems, v.9 n.10, p.972-986, October 1998 [doi>10.1109/71.730527]
• 40: Feng Qin , Shan Lu , Yuanyuan Zhou, SafeMem: Exploiting ECC-Memory for Detecting Memory Leaks and Memory Corruption During Production Runs, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.291-302, February 12-16, 2005 [doi>10.1109/HPCA.2005.29]
• 41: B. Randell. System structure for software fault tolerance. IEEE Transactions on Software Engineering, 1(2):220--232, 1975.
• 42: B. Randell , P. Lee , P. C. Treleaven, Reliability Issues in Computing System Design, ACM Computing Surveys (CSUR), v.10 n.2, p.123-165, June 1978 [doi>10.1145/356725.356729]
• 43: M. Rinard, C. Cadar, D. Dumitran, D. M. Roy, T. Leu, and W. S. Beebee, Jr. Enhancing server availability and security through failure-oblivious computing. In Proceedings of the 6th Symposium on Operating System Design and Implementation, Dec 2004.
• 44: Rodrigo Rodrigues , Miguel Castro , Barbara Liskov, BASE: using abstraction to improve fault tolerance, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 45: Mark Russinovich , Bryce Cogswell, Replay for concurrent non-deterministic shared-memory applications, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.258-266, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 46: Douglas S. Santry , Michael J. Feeley , Norman C. Hutchinson , Alistair C. Veitch , Ross W. Carton , Jacob Ofir, Deciding when to forget in the Elephant file system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.110-123, December 12-15, 1999, Charleston, South Carolina, United States
• 47: D. Scott. Assessing the costs of application downtime. Gartner Group, May 1998.
• 48: S. Sidiroglou, M. E. Locasto, S. W. Boyd, and A. D. Keromytis. Building a reactive immune system for software services. In Proceedings of the USENIX 2005 Annual Technical Conference, Apr 2005.
• 49: S. Srinivasan, C. Andrews, S. Kandula, and Y. Zhou. Flashback: A light-weight extension for rollback and deterministic replay for software debugging. In Proceedings of the USENIX 2004 Annual Technical Conference, Jun 2004.
• 50: Stuart Staniford , Vern Paxson , Nicholas Weaver, How to Own the Internet in Your Spare Time, Proceedings of the 11th USENIX Security Symposium, p.149-167, August 05-09, 2002
• 51: S. D. Stoller. Testing concurrent Java programs using randomized scheduling. In Proceedings of the 2nd Workshop on Runtime Verification, Jul 2002.
• 52: Rob Strom , Shaula Yemini, Optimistic recovery in distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.3, p.204-226, Aug. 1985 [doi>10.1145/3959.3962]
• 53: M. Sullivan and R. Chillarege. Software defects and their impact on system availability -- A study of field failures in operating systems. In Proceedings of the 21th Annual International Symposium on Fault-Tolerant Computing, Jun 1991.
• 54: M. M. Swift, M. Annamalai, B. N. Bershad, and H. M. Levy. Recovering device drivers. In Proceedings of the 6th Symposium on Operating System Design and Implementation, Dec 2004.
• 55: G. Trent and M. Sake. Webstone: The first generation in http server benchmarking, 1995.
• 56: W. Vogels, D. Dumitriu, A. Agrawal, T. Chia, and K. Guo. Scalability of the Microsoft Cluster Service. In Proceedings of the 2nd USENIX Windows NT Symposium, Aug 1998.
• 57: W. Vogels , D. Dumitriu , K. Birman , R. Gamache , M. Massa , R. Short , J. Vert , J. Barrera , J. Gray, The Design and Architecture of the Microsoft Cluster Service - A Practical Approach to High-Availability and Scalability, Proceedings of the The Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing, p.422, June 23-25, 1998
• 58: Y.-M. Wang, Y. Huang, and W. K. Fuchs. Progressive retry for software error recovery in distributed systems. In Proceedings of the 23rd Annual International Symposium on Fault-Tolerant Computing, Jun 1993.
• 59: Yi-Min Wang , Yennun Huang , Kiem-Phong Vo , Pe-Yu Chung , C. Kintala, Checkpointing and Its Applications, Proceedings of the Twenty-Fifth International Symposium on Fault-Tolerant Computing, p.22, June 27-30, 1995
• 60: Yuanyuan Zhou , Peter M. Chen , Kai Li, Fast cluster failover using virtual memory-mapped communication, Proceedings of the 13th international conference on Supercomputing, p.373-382, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305215]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability

General Terms:
Design, Experimentation, Reliability

Keywords:
availability, bug, reliability, software failure