Joseph Tucek
Yuanyuan Zhou
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.
- 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.Google Scholar
- Rob Barrett, Paul P. Maglio, Eser Kandogan, and John Bailey. Usable autonomic computing systems: The administrator's perspective. In Proceedings of the First International Conference on Autonomic Computing (ICAC'04), pages 18--26. IEEE Computer Society, 2004. Google ScholarDigital Library
- Steve Beattie, Seth Arnold, Crispin Cowan, Perry Wagle, Chris Wright, and Adam Shostack. Timing the application of security patches for optimal uptime, 2002. In Proceedings of the 16th USENIX Systems Administration Conference (LISA'02), 2002. Google ScholarDigital Library
- Hilary K. Browne, William A. Arbaugh, John McHugh, and William L. Fithen. A trend analysis of exploitations. In SP '01: Proceedings of the 2001 IEEE Symposium on Security and Privacy, page 214, Washington, DC, USA, 2001. IEEE Computer Society. Google ScholarDigital Library
- CERT. Cert statistics. http://www.cert.org/ stats/ cert stats.html.Google Scholar
- Jonathan E. Cook and Jeffrey A. Dage. Highly reliable upgrading of components. In International Conference on Software Engineering, pages 203--212, 1999. Google ScholarDigital Library
- 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.Google Scholar
- Marcelo d'Amorim, Steven Lauterburg, and Darko Marinov. Delta execution for efficient state-space exploration of object-oriented programds. In ISSTA'07: Proceedings of the 2007 International Symposium on Software Testing and Analysis, 2007. Google ScholarDigital Library
- Michael Hicks, Jonathan T. Moore, and Scott Nettles. Dynamic software updating. In PLDI '01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, pages 13--23, New York, NY, USA, 2001. ACM. Google ScholarDigital Library
- Ashlesha Joshi, Samuel T. King, George W. Dunlap, and Peter M. Chen. Detecting past and present intrusions through vulnerability-specific predicates. SIGOPS Oper. Syst. Rev., 39:91--104, 2005. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoff Lowney, Steven Wallace and Vijay Janapa Reddi, and Kim Hazelwood. Pin: Building customized program analysis tools with dynamic instrumentation. In PLDI, 2005. Google ScholarDigital Library
- Kristis Makris and Kyung Dong Ryu. Dynamic and adaptive updates of non-quiescent subsystems in commodity operating system kernels. In EuroSys '07: Proceedings of the ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, pages 327--340, New York, NY, USA, 2007. ACM. Google ScholarDigital Library
- Evan Marcus and Hal Stern. Blueprints for High Availability. John Willey & Sons, 2000. Google ScholarDigital Library
- Paul McDougall. Microsoft pulls buggy Windows Vista SP1 files. InformationWeek, Feb 2008. http://www.informationweek.com/story/showArticle.jhtml?articleID=206800819.Google Scholar
- Microsoft. Revamping the microsoft security bulletin release process, Oct 2003. http://www.microsoft.com/ technet/ security/bulletin/ revsbwp.mspx.Google Scholar
- Kiran Nagaraja, F´abio Oliveira, Ricardo Bianchini, Richard P. Martin, and Thu D. Nguyen. Understanding and dealing with operator mistakes in internet services. In OSDI, 2004. Google ScholarDigital Library
- 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.Google Scholar
- Rob Pegoraro. Apple updates Leopard--again. The Washington Post, Feb 2008. http://blog.washingtonpost.com/ fasterforward/2008/02/apple updates leopardagain.html.Google Scholar
- Eric Rescorla. Security holes.. who cares? In Proceedings of the 12th USENIX Security Conference, Aug 2003. Google ScholarDigital Library
- Mark E. Segal and Ophir Frieder. On-the-fly program modification: Systems for dynamic updating. IEEE Softw., 10(2):53--65, 1993. Google ScholarDigital Library
- Stelios Sidiroglou, Sotiris Ioannidis, and Angelos D. Keromytis. Band-aid patching. In HotDep'07: Proceedings of the 3rd Workshop on Hot Topics in System Dependability. USENIX Association, 2007. Google ScholarDigital Library
- Linus Torvalds. Re: {rant} linux-irda status. Linux Kernel Mailing List, November 2000.Google Scholar
- Zheng Wang and Ken Pierce. Bmat -- a binary matching tool for stale profile propagation. Instruction-Level Parallelism, 2000.Google Scholar
- Yuanyuan Zhou, Darko Marinov, William Sanders, Craig Zilles, Marcelo d'Amorim, Steven Lauterburg, Ryan M. Lefever, and Joseph Tucek. Delta execution for software reliability. In HotDep'07: Proceedings of the 3rd Workshop on Hot Topics in System Dependability. USENIX Association, 2007. Google ScholarDigital Library
Index Terms
- Efficient online validation with delta execution
Recommendations
Efficient online validation with delta execution
ASPLOS 2009Software 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 ...
Efficient online validation with delta execution
ASPLOS 2009Software 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 ...
Delta execution for efficient state-space exploration of object-oriented programs
ISSTA '07: Proceedings of the 2007 international symposium on Software testing and analysisState-space exploration is the essence of model checking and an increasingly popular approach for automating test generation. A key issue in exploration of object-oriented programs is handling the program state, in particular the heap. Previous research ...
Comments