Tradeoffs in fine-grained heap memory protection

ABSTRACT

Different uses of memory protection schemes have different needs in terms of granularity. For example, heap security can benefit from chunk separation (by using protected "padding" boundaries) and meta-data protection. However, such protection can be done at different granularity (eg. per-word, per-block, or per-page), with different performance, cost and memory overhead tradeoffs for different applications. In this paper, we explore these tradeoffs for the purpose of heap security in order to discover whether the "right" granularity exists and how the granularity of protection affects design decisions.We evaluate such tradeoffs based on the current heap-security approaches in a single address spare operating system. The access control granularities we use are word, 8-byte, 16-byte, 32-byte, and page. We find that none of these schemes is optimal across all applications. In some applications, excessive padding degrades caching performance for coarse-granularity schemes, while in others, large-block permission changes introduce large overheads for finer granularities. To overcome these limitations, we propose a new two-granularity scheme, which uses word- and page-granularity protection to eliminate padding but allow fast page-size permission changes for large memory blocks. On all applications, this new scheme performs as well or better than the best single-granularity scheme. It also performs on par with the more complex Mondrian Memory Protection, which uses a complex trie structure and multiple permissions caching mechanisms to support a hierarchy of protection granularities.

REFERENCES

• 1: Anonymous. Once upon a free(). Phrack Magazine, 57(9), 2001.
• 2: Marc L. Corliss , E. Christopher Lewis , Amir Roth, DISE: a programmable macro engine for customizing applications, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 3: C. Cowan, S. Beattie, J. Johansen, and P. Wagle. PointGuard: Protecting Pointers from Buffer Overflow Vulnerabilities. in Proc. of the 12th USENIX Security Symp., pages 91--104, 2003.
• 4: C. Cowan, C. Pu, D. Maier, J. Walpole, P. Bakke, S. Beattie, A. Grier, P. Wagle, Q. Zhang, and H. Hinton. StackGuard: Automatic Adaptive Detection and Prevention of Buffer-Overflow Attacks. in Proc. of the 7th USENIX Security Symp., pages 63--78, 1998.
• 5: C. Cowan, F. Wagle, C. Pu, S. Beattie, and J. Walpole. Buffer overflows: Attacks and defenses for the vulnerability of the decade. In DARPA Information Survivability Conf. & Exposition - Volume 2, pages 119--129, 2000.
• 6: W. J. Dally and et al. The j-machine: a fine-grain concurrent computer. In G. X. Ritter (ed.), Information Processing 89, North Holland, 1989. Elsevier Science Publishers B.V.
• 7: Doug Lea. A Memory Allocator. http://gee.cs.oswego.edu/dl/html/malloc.html, 2000.
• 8: IBM Corporation. IBM Rational Purify. http://www.ibm.com/software/awdtools/purify/, 2005.
• 9: Eric J. Koldinger , Jeffrey S. Chase , Susan J. Eggers, Architecture support for single address space operating systems, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.175-186, October 12-15, 1992, Boston, Massachusetts, United States
• 10: F. Perriot and P. Szor. An Analysis of the Slapper Worm Exploit. http://securityresponse.symantec.com/avcenter/reference/analysis.slapper.worm.pdf, 2003.
• 11: J. Renau et al. SESC. http://sesc.sourceforge.net, 2006.
• 12: Security Focus. Wu-Ftpd File Globbing Heap Corruption Vulnerability. http://www.securityfocus.com/bid/3581, 2002.
• 13: Security Focus. CVS Directory Request Double Free Heap Corruption Vulnerability. http://www.securityfocus.com/bid/6650, 2003.
• 14: Security Focus. Sudo Password Prompt Heap Overflow Vulnerability. http://www.securityfocus.com/bid/4593, 2003.
• 15: J. Seward. Valgrind, An Open-Source Memory Debugger for x86-GNU/Linux. http://valgrind.kde.org/, 2004.
• 16: R. Shetty, M. Kharbutli, Y. Solihin, and M. Prvulovic. HeapMon: a Low Overhead, Automatic, and Programmable Memory Bug Detector. In IBM T.J. Watson Conf. on Interaction between Architecture, Circuits, and Compilers, 2004.
• 17: Standard Performance Evaluation Corporation. SPEC Benchmarks. http://www.spec.org, 2000.
• 18: Emmett Witchel , Josh Cates , Krste Asanović, Mondrian memory protection, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 19: Pin Zhou , Wei Liu , Long Fei , Shan Lu , Feng Qin , Yuanyuan Zhou , Samuel Midkiff , Josep Torrellas, AccMon: Automatically Detecting Memory-Related Bugs via Program Counter-Based Invariants, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.269-280, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.3]
• 20: Pin Zhou , Feng Qin , Wei Liu , Yuanyuan Zhou , Josep Torrellas, iWatcher: Efficient Architectural Support for Software Debugging, Proceedings of the 31st annual international symposium on Computer architecture, p.224, June 19-23, 2004, München, Germany

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL

Keywords:
heap security, memory protection, protection granularity