Efficient online validation with delta execution

ABSTRACT

Software systems are constantly changing. Patches to fix bugs and patches to add features are all too common. Every change risks breaking a previously working system. Hence administrators loathe change, and are willing to delay even critical security patches until after fully validating their correctness. Compared to off-line validation, on-line validation has clear advantages since it tests against real life workloads. Yet unfortunately it imposes restrictive overheads as it requires running the old and new versions side-by-side. Moreover, due to spurious differences (e.g. event timing, random number generation, and thread interleavings), it is difficult to compare the two for validation.

To allow more effective on-line patch validation, we propose a new mechanism, called delta execution, that is based on the observation that most patches are small. Delta execution merges the two side-by-side executions for most of the time and splits only when necessary, such as when they access different data or execute different code. This allows us to perform on-line validation not only with lower overhead but also with greatly reduced spurious differences, allowing us to effectively validate changes.

We first validate the feasibility of our idea by studying the characteristics of 240 patches from 4 server programs; our examination shows that 77% of the changes should not be expected to cause large changes and are thereby feasible for Delta execution. We then implemented Delta execution using dynamic instrumentation. Using real world patches from 7 server applications and 3 other programs, we compared our implementation of Delta execution against a traditional side-by-side on-line validation. Delta execution outperformed traditional validation by up to 128%; further, for 3 of the changes, spurious differences caused the traditional validation to fail completely while Delta execution succeeded. This demonstrates that Delta execution can allow administrators to use on-line validation to confidently ensure the correctness of the changes they apply.

REFERENCES

• 1: Brenda S. Baker, Udi Manber, and Robert Muth. Compressing differences of executable code. In ACM SIGPLAN 1999 Workshop on Compiler Support for System Software (WCSSS'99), May 1999.
• 2: Eser Kandogan , John Bailey, Usable Autonomic Computing Systems: The Administrator's Perspective, Proceedings of the First International Conference on Autonomic Computing, p.18-26, May 17-18, 2004
• 3: Timing the Application of Security Patches for Optimal Uptime, Proceedings of the 16th USENIX conference on System administration, November 03-08, 2002, Philadelphia, PA
• 4: Hilary K. Browne , William A. Arbaugh , John McHugh , William L. Fithen, A Trend Analysis of Exploitations, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.214, May 14-16, 2001
• 5: CERT. Cert statistics. http://www.cert.org/ stats/ cert stats.html.
• 6: Jonathan E. Cook , Jeffrey A. Dage, Highly reliable upgrading of components, Proceedings of the 21st international conference on Software engineering, p.203-212, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302466]
• 7: Crispin Cowan, Heather Hinton, Calton Pu, and Jonathan Walpole. The cracker patch choice: An analysis of post hoc security techniques. In Proceedings of the National Information Systems Security Conference (NISSC), Oct 2000.
• 8: Marcelo d'Amorim , Steven Lauterburg , Darko Marinov, Delta execution for efficient state-space exploration of object-oriented programs, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273472]
• 9: Michael Hicks , Jonathan T. Moore , Scott Nettles, Dynamic software updating, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.13-23, June 2001, Snowbird, Utah, United States
• 10: Ashlesha Joshi , Samuel T. King , George W. Dunlap , Peter M. Chen, Detecting past and present intrusions through vulnerability-specific predicates, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005
• 11: David E. Lowell, Yasushi Saito, and Eileen J. Samberg. Devirtualizable virtual machines enabling general, single-node, online maintenance. ASPLOS '04, 39(11):211--223, 2004.
• 12: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 13: Kristis Makris , Kyung Dong Ryu, Dynamic and adaptive updates of non-quiescent subsystems in commodity operating system kernels, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 14: Evan Marcus , Hal Stern, Blueprints for high availability: designing resilient distributed systems, John Wiley & Sons, Inc., New York, NY, 2000
• 15: Paul McDougall. Microsoft pulls buggy Windows Vista SP1 files. InformationWeek, Feb 2008. http://www.informationweek.com/story/showArticle.jhtml?articleID=206800819.
• 16: Microsoft. Revamping the microsoft security bulletin release process, Oct 2003. http://www.microsoft.com/ technet/ security/bulletin/ revsbwp.mspx.
• 17: Kiran Nagaraja , Fábio Oliveira , Ricardo Bianchini , Richard P. Martin , Thu D. Nguyen, Understanding and dealing with operator mistakes in internet services, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.5-5, December 06-08, 2004, San Francisco, CA
• 18: National Institute of Standards and Technlogy (NIST), Department of Commerce. Software errors cost U.S. economy $59.5 billion annually. NIST News Release 2002-10, 2002.
• 19: Rob Pegoraro. Apple updates Leopard--again. The Washington Post, Feb 2008. http://blog.washingtonpost.com/ fasterforward/2008/02/apple updates leopardagain.html.
• 20: Eric Rescorla, Security holes... who cares?, Proceedings of the 12th conference on USENIX Security Symposium, p.6-6, August 04-08, 2003, Washington, DC
• 21: Mark E. Segal , Ophir Frieder, On-the-Fly Program Modification: Systems for Dynamic Updating, IEEE Software, v.10 n.2, p.53-65, March 1993 [doi>10.1109/52.199735]
• 22: Stelios Sidiroglou , Sotiris Ioannidis , Angelos D. Keromytis, Band-aid patching, Proceedings of the 3rd workshop on on Hot Topics in System Dependability, p.6-es, June 26, 2007, Edinburgh, UK
• 23: Linus Torvalds. Re: {rant} linux-irda status. Linux Kernel Mailing List, November 2000.
• 24: Zheng Wang and Ken Pierce. Bmat -- a binary matching tool for stale profile propagation. Instruction-Level Parallelism, 2000.
• 25: Yuanyuan Zhou , Darko Marinov , William Sanders , Craig Zilles , Marcelo d'Amorim , Steven Lauterburg , Ryan M. Lefever , Joe Tucek, Delta execution for software reliability, Proceedings of the 3rd workshop on on Hot Topics in System Dependability, p.16-es, June 26, 2007, Edinburgh, UK

INDEX TERMS

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

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

General Terms:
Reliability, Verification

Keywords:
delta execution, patch validation, testing