SoftBound: highly compatible and complete spatial memory safety for c

ABSTRACT

The serious bugs and security vulnerabilities facilitated by C/C++'s lack of bounds checking are well known, yet C and C++ remain in widespread use. Unfortunately, C's arbitrary pointer arithmetic, conflation of pointers and arrays, and programmer-visible memory layout make retrofitting C/C++ with spatial safety guarantees extremely challenging. Existing approaches suffer from incompleteness, have high runtime overhead, or require non-trivial changes to the C source code. Thus far, these deficiencies have prevented widespread adoption of such techniques.

This paper proposes SoftBound, a compile-time transformation for enforcing spatial safety of C. Inspired by HardBound, a previously proposed hardware-assisted approach, SoftBound similarly records base and bound information for every pointer as disjoint metadata. This decoupling enables SoftBound to provide spatial safety without requiring changes to C source code. Unlike HardBound, SoftBound is a software-only approach and performs metadata manipulation only when loading or storing pointer values. A formal proof shows that this is sufficient to provide spatial safety even in the presence of arbitrary casts. SoftBound's full checking mode provides complete spatial violation detection with 67% runtime overhead on average. To further reduce overheads, SoftBound has a store-only checking mode that successfully detects all the security vulnerabilities in a test suite at the cost of only 22% runtime overhead on average.

REFERENCES

• 1: Adobe Reader vulnerability exploited in-the-wild, 2008. http://www.trustedsource.org/blog/118/Recent-Adobe-Reader-vulnerability-exploited-in-the-wild.
• 2: Adobe Security Advisories: APSB08-19, Nov. 2008. http://www.adobe.com/support/security/bulletins/apsb08-19.html.
• 3: Martín Abadi , Mihai Budiu , Úlfar Erlingsson , Jay Ligatti, Control-flow integrity, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102165]
• 4: Periklis Akritidis , Cristian Cadar , Costin Raiciu , Manuel Costa , Miguel Castro, Preventing Memory Error Exploits with WIT, Proceedings of the 2008 IEEE Symposium on Security and Privacy, p.263-277, May 18-21, 2008 [doi>10.1109/SP.2008.30]
• 5: Todd M. Austin , Scott E. Breach , Gurindar S. Sohi, Efficient detection of all pointer and array access errors, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.290-301, June 20-24, 1994, Orlando, Florida, United States
• 6: Emery D. Berger , Benjamin G. Zorn, DieHard: probabilistic memory safety for unsafe languages, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 7: Bruno Blanchet , Patrick Cousot , Radhia Cousot , Jérome Feret , Laurent Mauborgne , Antoine Miné , David Monniaux , Xavier Rival, A static analyzer for large safety-critical software, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 8: Rastislav Bodík , Rajiv Gupta , Vivek Sarkar, ABCD: eliminating array bounds checks on demand, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.321-333, June 18-21, 2000, Vancouver, British Columbia, Canada
• 9: Hans-Juergen Boehm, Space efficient conservative garbage collection, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.197-206, June 21-25, 1993, Albuquerque, New Mexico, United States
• 10: Miguel Castro , Manuel Costa , Tim Harris, Securing software by enforcing data-flow integrity, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.11-11, November 06-08, 2006, Seattle, WA
• 11: J. Condit, M. Harren, Z. Anderson, D. Gay, and G. C. Necula. Dependent Types for Low-Level Programming. In Proceedings of the 16th European Symposium on Programming, Apr. 2007.
• 12: K. D. Cooper, M. W. Hall, and K. Kennedy. A Methodology for Procedure Cloning. Comput. Lang., 19(2):105--117, 1993.
• 13: The Coq Development Team. The Coq Proof Assistant Reference Manual (Version 8.2beta4), 2008.
• 14: C. Cowan, P. Wagle, C. Pu, S. Beattie, and J. Walpole. Buffer Overflows: Attacks and Defenses for the Vulnerability of the Decade. In Proceedings of the Foundations of Intrusion Tolerant Systems, 2003.
• 15: John Criswell , Andrew Lenharth , Dinakar Dhurjati , Vikram Adve, Secure virtual architecture: a safe execution environment for commodity operating systems, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 16: Joe Devietti , Colin Blundell , Milo M. K. Martin , Steve Zdancewic, Hardbound: architectural support for spatial safety of the C programming language, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 17: Dinakar Dhurjati , Vikram Adve, Backwards-compatible array bounds checking for C with very low overhead, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134309]
• 18: Dinakar Dhurjati , Sumant Kowshik , Vikram Adve, SAFECode: enforcing alias analysis for weakly typed languages, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 19: Dinakar Dhurjati , Sumant Kowshik , Vikram Adve , Chris Lattner, Memory safety without runtime checks or garbage collection, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 20: Nurit Dor , Michael Rodeh , Mooly Sagiv, CSSV: towards a realistic tool for statically detecting all buffer overflows in C, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 21: F. C. Eigler. Mudflap: Pointer Use Checking for C/C++. In GCC Developer's Summit, 2003.
• 22: Vinod Ganapathy , Somesh Jha , David Chandler , David Melski , David Vitek, Buffer overrun detection using linear programming and static analysis, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948155]
• 23: 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
• 24: Daniel Joseph Grossman , Greg Morrisett, Safe programming at the c level of abstraction, Cornell University, Ithaca, NY, 2003
• 25: Dan Grossman , Greg Morrisett , Trevor Jim , Michael Hicks , Yanling Wang , James Cheney, Region-based memory management in cyclone, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 26: Brian Hackett , Manuvir Das , Daniel Wang , Zhe Yang, Modular checking for buffer overflows in the large, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134319]
• 27: R. Hastings and B. Joyce. Purify: Fast Detection of Memory Leaks and Access Errors. In Proceedings of the Winter Usenix Conference, 1992.
• 28: Trevor Jim , J. Greg Morrisett , Dan Grossman , Michael W. Hicks , James Cheney , Yanling Wang, Cyclone: A Safe Dialect of C, Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, p.275-288, June 10-15, 2002
• 29: R. W. M. Jones and P. H. J. Kelly. Backwards-Compatible Bounds Checking for Arrays and Pointers in C Programs. In Third International Workshop on Automated Debugging, Nov. 1997.\newpage
• 30: Vladimir Kiriansky , Derek Bruening , Saman P. Amarasinghe, Secure Execution via Program Shepherding, Proceedings of the 11th USENIX Security Symposium, p.191-206, August 05-09, 2002
• 31: G. Kroah-Hartman. The Linux Kernel Driver Model: The Benefits of Working Together. In A. Oram and G. Wilson, editors, Beautiful Code: Leading Programmers Explain How They Think. O'Reilly Media, Inc., June 2007.
• 32: Lap-chung Lam, Checking Array Bound Violation Using Segmentation Hardware, Proceedings of the 2005 International Conference on Dependable Systems and Networks, p.388-397, June 28-July 01, 2005 [doi>10.1109/DSN.2005.25]
• 33: Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
• 34: S. Lu, Z. Li, F. Qin, L. Tan, P. Zhou, and Y. Zhou. Bugbench: Benchmarks for Evaluating Bug Detection tools. In In PLDI Workshop on the Evaluation of Software Defect Detection Tools, June 2005.
• 35: George C. Necula , Jeremy Condit , Matthew Harren , Scott McPeak , Westley Weimer, CCured: type-safe retrofitting of legacy software, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.477-526, May 2005 [doi>10.1145/1065887.1065892]
• 36: N. Nethercote and J. Fitzhardinge. Bounds-Checking Entire Programs Without Recompiling. In Proceedings of the Second Workshop on Semantics, Program Analysis, and Computing Environments for Memory Management, 2004.
• 37: Harish Patil , Charles Fischer, Low-cost, concurrent checking of pointer and array accesses in C programs, Software—Practice & Experience, v.27 n.1, p.87-110, Jan. 1997 [doi>10.1002/(SICI)1097-024X(199701)27:1<87::AID-SPE78>3.0.CO;2-P]
• 38: Jonathan Pincus , Brandon Baker, Beyond Stack Smashing: Recent Advances in Exploiting Buffer Overruns, IEEE Security and Privacy, v.2 n.4, p.20-27, July 2004 [doi>10.1109/MSP.2004.36]
• 39: P. Porras, H. Saidi, and V. Yegneswaran. An Analysis of Conficker's Logic and Rendezvous Points. Technical report, SRI International, Feb. 2009.
• 40: Anne Rogers , Martin C. Carlisle , John H. Reppy , Laurie J. Hendren, Supporting dynamic data structures on distributed-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.233-263, March 1995 [doi>10.1145/201059.201065]
• 41: O. Ruwase and M. S. Lam. A Practical Dynamic Buffer Overflow Detector. In Proceedings of the Network and Distributed Systems Security Symposium, Feb. 2004.
• 42: Julian Seward , Nicholas Nethercote, Using Valgrind to detect undefined value errors with bit-precision, Proceedings of the annual conference on USENIX Annual Technical Conference, p.2-2, April 10-15, 2005, Anaheim, CA
• 43: SoftBound website. http://www.cis.upenn.edu/acg/softbound/.
• 44: D. Wagner, J. S. Foster, E. A. Brewer, and A. Aiken. A First Step towards Automated Detection of Buffer Overrun Vulnerabilities. In Proceedings of the Network and Distributed Systems Security Symposium, 2000.
• 45: J. Wilander and M. Kamkar. A Comparison of Publicly Available Tools for Dynamic Buffer Overflow Prevention. In Proceedings of the Network and Distributed Systems Security Symposium, 2003.
• 46: Thomas Würthinger , Christian Wimmer , Hanspeter Mössenböck, Array bounds check elimination for the Java HotSpot™ client compiler, Proceedings of the 5th international symposium on Principles and practice of programming in Java, September 05-07, 2007, Lisboa, Portugal [doi>10.1145/1294325.1294343]
• 48: Wei Xu , Daniel C. DuVarney , R. Sekar, An efficient and backwards-compatible transformation to ensure memory safety of C programs, Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, October 31-November 06, 2004, Newport Beach, CA, USA
• 49: Suan Hsi Yong , Susan Horwitz, Protecting C programs from attacks via invalid pointer dereferences, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Languages, Performance, Reliability, Security

Keywords:
buffer overflows, c, spatial memory safety