Software systems are often perceived to be fragile and brittle, vulnerable to security exploits and errors that cause the system to crash. We have developed a set of techniques that make software systems more robust, resilient, reliable, and secure by enabling them to survive a range of otherwise fatal errors. The overall goal is to make the software survive any error, continue to execute, and provide acceptable service to its users. One particularly important application of this technology is to eliminate security vulnerabilities such as defects that enable remote software injection attacks.
Together, these techniques are designed to ensure that programs preserve basic acceptability properties such as continued execution in the face of otherwise fatal errors. We call the resulting approach acceptability-oriented computing. One of the basic principles behind acceptability-oriented computing is that complex computer systems have a natural resilience to errors, but this resilience has been explicitly removed by attempts to make programs fail at the first sign of an error. One of goals of our research project is to develop new mechanisms that help deployed programs execute successfully through errors. The ideal end result will be more robust and resilient computer systems.
My Onward! 2003 paper on Acceptability-Oriented Computing presents the conceptual foundations behind this approach to robust software systems and provides several examples of how developers can implement components that enforce acceptability properties. Our Onward! 2005 paper on Exploring the Acceptability Envelope further explores the implications of acceptability-oriented computing.
Acceptability-Oriented Computing
(Most Notable Paper Award, Onward! 2013)
Martin C. Rinard
2003 ACM SIGPLAN Conference on Object-Oriented Programming
Systems, Languages, and Applications Companion (OOPSLA '03 Companion)
Onwards! Session
Anaheim, California, October 2003
Talk slides available here
Exploring the Acceptability Envelope
(PostScript)
Martin C. Rinard, Cristian Cadar, and Huu Hai Nguyen
2005 ACM SIGPLAN Conference on Object-Oriented Programming
Systems, Languages, and Applications Companion (OOPSLA '05 Companion)
Onwards! Session
San Diego, California, USA. October 2005
Specific acceptability-oriented computing techniques include:
Failure-Oblivious Computing: Memory errors can cause fatal memory corruption or cause the program to throw exceptions that terminate the computation. Failure-oblivious computing is a technique for enabling the program to survive otherwise fatal memory errors. This technique performs bounds checks on all memory accesses. It discards out of bounds writes and manufactures values to return as the result of out of bounds reads. Our results show that this technique enables a set of open-source server programs (Pine, Apache, Sendmail, Midnight Commander, and Mutt) to survive otherwise fatal buffer overflow attacks. See our OSDI 2004 paper on this topic for more information. <\p>
Enhancing Server Availability and Security Through Failure-Oblivious Computing
Martin C. Rinard, Cristian Cadar, Daniel Dumitran, Daniel M. Roy, Tudor Leu, and William S. Beebee, Jr.
Proceedings of the 6th Symposium on Operating Systems Design and Implementation
San Francisco, California, December 2004
Boundless Memory Blocks: Instead of discarding out of bounds writes, boundless memory blocks store out of bounds writes in a hash table, enabling the system to return the stored values on corresponding out of bounds reads. Conceptually, this technique gives each allocated block of memory unbounded size. Our results show that this technique enables a set of server programs to survive otherwise fatal buffer overflow attacks. See our ACSAC 2004 paper on this topic for more information.
A Dynamic Technique for Eliminating Buffer Overflow Vulnerabilities
(and Other Memory Errors)
Martin C. Rinard, Cristian Cadar, Daniel Dumitran, Daniel M. Roy, and Tudor Leu
Proceedings of the 2004 Annual Computer Security Applications Conference
Tucson, Arizona, December 2004
Recovery Shepherding: Techniques such as failure-oblivious computing that manufacture new values as part of an error recovery process may have cascading effects on the ensuing computation as repair effects from the manufactured values propagate. Recovery Shepherding attaches to a running application when an error occurs, repairs the execution, tracks the repair effects as the execution continues, contains the repair effects within the application process, determines when all of the repair effects are flushed from the process state, then detaches. Recovery shepherding therefore makes it possible to determine when the repair effects have been flushed and incurs negligible overhead during the normal execution of the application See our PLDI 2014 paper on this topic for more information.
Automatic Runtime Error Repair and Containment via Recovery Shepherding
Fan Long, Stelios Sidiroglou-Douskos, and Martin Rinard
Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2014)
Edinburgh, UK, June 2014
Exiting Infinite Loops: My research group has developed two systems, Bolt and Jolt, for automatically exiting infinite loops. When activated, Jolt observes loop executions to determine if the state is the same on successive iterations. If so, it exits the loop by jumping to a location outside the loop. Our ECOOP 2011 paper describes the technique in more detail and presents experimental results that demonstrate its effectiveness in eliminating infinite loops in a set of benchmark applications.
Bolt operates on stripped x86 and x64 binaries, dynamically attaches and detaches to and from the running program as needed, and dynamically detects loops and creates program state checkpoints to enable exploration of different loop escape strategies. Bolt can detect and escape from loops in off-the-shelf software, without available source code, and with no overhead in standard production use. Our OOPSLA 2012 paper describes the implementation in more detail and presents experimental results that demonstrate its effectiveness.
Bolt: On-Demand Infinite Loop Escape in Unmodified Binaries
Michael Kling, Sasa Misailovic, Michael Carbin, and Martin Rinard
Proceedings of the 27th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2012)
Tucson, Arizona October 2012
Detecting and Escaping Infinite Loops with Jolt
Michael Carbin, Sasa Misailovic, Michael Kling, and Martin Rinard
25th European Conference on Object-Oriented Programming (ECOOP 2011)
Lancaster UK, July 2011
Eliminating Memory Leaks: Memory leaks can cause a system to exhaust its address space and fail. Cyclic memory allocation eliminates memory leaks by allocating a single fixed-size buffer for a given allocation site, then cyclically allocating objects from that site in that buffer. Our results show that this technique can eliminate remotely-exploitable errors that otherwise cause the system to leak memory. See our ISMM 2007 paper on this topic for more information.
Detecting and Eliminating Memory Leaks Using Cyclic Memory Allocation
(PostScript)
Huu Hai Nguyen and Martin C. Rinard
2007 International Symposium on Memory Management
Montreal, Canada, October 2007
Input Rectification: My Onward! 2007 paper shows how to manually build input rectifiers that automatically transform inputs to eliminate security exploits and features that exercise untested or poorly tested parts of the software system. Our ICSE 2012 paper shows how to automatically construct rectifiers by learning characteristics of typical inputs that the system processes correctly. When placed between the system and its input sources, input rectifiers can increase security and robustness by keeping the system within a tested and reliable region of its execution envelope. A key concept is the comfort zone of a system - the region of the input space that the system can process without failure, typically because the system has been tested extensively on this region.
Living in the Comfort Zone
(PostScript)
Martin C. Rinard
2007 ACM SIGPLAN Conference on Object-Oriented Programming
Systems, Languages, and Applications
Onwards! Session
Montreal, Canada, October 2007
Automatic Input Rectification
Fan Long, Vijay Ganesh, Michael Carbin, Stelios Sidiroglou, and Martin Rinard
Proceedings of the 34th International Conference on Software Engineering
Zurich, Switzerland June 2012
Data Structure Repair: Software errors and hardware failures can cause data structures in running programs to violate key data structure consistency properties. This violation can cause the program to produce unacceptable results or even fail. Our IEEE TSE 2006 paper presents techniques that repair the data structure, eliminate inconsistencies, and enable the system to continue to execute successfully. We have used our data structure repair system to repair inconsistent data structures and eliminate failures in a variety of applications, including an air-traffic control system, an open-source word processing system, and an interactive multiplayer game.
Earlier versions of this research appeared in Our ICSE 2005 paper, our OOPSLA 2003 paper, our ISSRE 2003 paper, and our SMS 2003 paper.
Modular Pluggable Analyses for Data Structure Consistency
Viktor Kuncak, Patrick Lam, Karen Zee, and Martin C. Rinard
IEEE Transactions on Software Engineering
Volume 32, Number 12, December 2006
Data Structure Repair Using Goal-Directed Reasoning
(Distinguished Paper Award)
Brian Demsky and Martin C. Rinard
Proceedings of the 2005 International Conference on Software Engineering
St. Louis, Missouri, May 2005
Automatic Detection and Repair of Errors in Data Structures
Brian Demsky and Martin C. Rinard
Proceedings of the 2003 ACM SIGPLAN Conference on Object-Oriented Programming
Systems, Languages, and Applications (OOPSLA '03)
Anaheim, California, October 2003
Static Specification Analysis for Termination of Specification-Based Data Structure Repair
Brian Demsky and Martin C. Rinard
Proceedings of the 14th IEEE International Symposium on Software Reliability Engineering
Denver, Colorado, November 2003
Automatic Data Structure Repair for Self-Healing Systems
Brian Demsky and Martin C. Rinard
First Workshop on Algorithms and Architectures for Self-Managed Systems
San Diego, California, June 2003