Backwards-compatible array bounds checking for C with very low overhead

ABSTRACT

The problem of enforcing correct usage of array and pointer references in C and C++ programs remains unsolved. The approach proposed by Jones and Kelly (extended by Ruwase and Lam) is the only one we know of that does not require significant manual changes to programs, but it has extremely high overheads of 5x-6x and 11x-12x in the two versions. In this paper, we describe a collection of techniques that dramatically reduce the overhead of this approach, by exploiting a fine-grain partitioning of memory called Automatic Pool Allocation. Together, these techniques bring the average overhead checks down to only 12% for a set of benchmarks (but 69% for one case). We show that the memory partitioning is key to bringing down this overhead. We also show that our technique successfully detects all buffer overrun violations in a test suite modeling reported violations in some important real-world programs.

REFERENCES

• 1: 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
• 2: 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
• 3: Martin Christopher Carlisle, Olden: parallelizing programs with dynamic data structures on distributed-memory machines, Princeton University, Princeton, NJ, 1996
• 4: Dinakar Dhurjati , Vikram Adve, Efficiently Detecting All Dangling Pointer Uses in Production Servers, Proceedings of the International Conference on Dependable Systems and Networks (DSN'06), p.269-280, June 25-28, 2006 [doi>10.1109/DSN.2006.31]
• 5: 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
• 6: Dinakar Dhurjati , Sumant Kowshik , Vikram Adve , Chris Lattner, Memory safety without garbage collection for embedded applications, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.1, p.73-111, February 2005 [doi>10.1145/1053271.1053275]
• 7: 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
• 8: 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]
• 9: Michael Hicks , Greg Morrisett , Dan Grossman , Trevor Jim, Experience with safe manual memory-management in cyclone, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029883]
• 10: R. W. M. Jones and P. H. J. Kelly. Backwards-compatible bounds checking for arrays and pointers in c programs. In Automated and Algorithmic Debugging, pages 13--26, 1997.
• 11: S. C. Kendall. Bcc: Runtime checking for c programs. In In Proceedings of the USENIX, 1983.
• 12: 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
• 13: Chris Lattner , Vikram Adve, Automatic pool allocation: improving performance by controlling data structure layout in the heap, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 14: Alexey Loginov , Suan Hsi Yong , Susan Horwitz , Thomas W. Reps, Debugging via Run-Time Type Checking, Proceedings of the 4th International Conference on Fundamental Approaches to Software Engineering, p.217-232, April 02-06, 2001
• 15: 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]
• 16: 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]
• 17: O. Ruwase and M. Lam. A practical dynamic buffer overflow detector. In In Proceedings of the Network and Distributed System Security (NDSS) Symposium, pages 159--169, Feb. 2004.
• 18: Joseph L. Steffen, Adding run-time checking to the portable C compiler, Software—Practice & Experience, v.22 n.4, p.305-316, April 1992 [doi>10.1002/spe.4380220403]
• 19: Yichen Xie , Andy Chou , Dawson Engler, ARCHER: using symbolic, path-sensitive analysis to detect memory access errors, ACM SIGSOFT Software Engineering Notes, v.28 n.5, September 2003
• 20: 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
• 21: 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
• 22: M. Zhivich, T. Leek, and R. Lippmann. Dynamic buffer overflow detection. In BUGS: Workshop on the Evaluation of Software Defect Detection Tools, 2005.
• 23: Misha Zitser , Richard Lippmann , Tim Leek, Testing static analysis tools using exploitable buffer overflows from open source code, Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, October 31-November 06, 2004, Newport Beach, CA, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

General Terms:
Languages, Reliability, Security

Keywords:
array bounds checking, automatic pool allocation, compilers, programming languages, region management