Low-fat pointers: compact encoding and efficient gate-level implementation of fat pointers for spatial safety and capability-based security

ABSTRACT

Referencing outside the bounds of an array or buffer is a common source of bugs and security vulnerabilities in today's software. We can enforce spatial safety and eliminate these violations by inseparably associating bounds with every pointer (fat pointer) and checking these bounds on every memory access. By further adding hardware-managed tags to the pointer, we make them unforgeable. This, in turn, allows the pointers to be used as capabilities to facilitate fine-grained access control and fast security domain crossing. Dedicated checking hardware runs in parallel with the processor's normal datapath so that the checks do not slow down processor operation (0% runtime overhead). To achieve the safety of fat pointers without increasing program state, we compactly encode approximate base and bound pointers along with exact address pointers for a 46b address space into one 64-bit word with a worst-case memory overhead of 3%. We develop gate-level implementations of the logic for updating and validating these compact fat pointers and show that the hardware requirements are low and the critical paths for common operations are smaller than processor ALU operations. Specifically, we show that the fat-pointer check and update operations can run in a 4 ns clock cycle on a Virtex 6 (40nm) implementation while only using 1100 6-LUTs or about the area of a double-precision, floating-point adder.

References

1. Introduction to Intel Memory Protection extensions. http://software.intel.com/en-us/articles/ introduction-to-intel-memory-protection-extensions. Accessed: 2013-08-01.
2. P. Akritidis, M. Costa, M. Castro, and S. Hand. Baggy bounds checking: an efficient and backwards-compatible defense against out-of-bounds errors. In Proceedings of the 18th Conference on USENIX Security Symposium, pages 51--66, 2009.
3. Aleph One. Smashing the Stack for Fun and Profit. Phrack, 7(49), November 1996.
4. AMD Corporation. AMD64 Architecture Programmer's Manual, Volume 2: System Programming, revision 3.22 edition, September 2012.
5. N. Binkert, B. Beckmann, G. Black, S. K. Reinhardt, A. Saidi, A. Basu, J. Hestness, D. R. Hower, T. Krishna, S. Sardashti, R. Sen, K. Sewell, M. Shoaib, N. Vaish, M. D. Hill, and D. A. Wood. The gem5 simulator. SIGARCH Comput. Archit. News, 39(2):1--7, Aug. 2011.
6. Bluespec, Inc. Bluespec SystemVerilog.
7. J. Brown, J. Grossman, A. Huang, and T. F. Knight, Jr. A capability representation with embedded address and nearly-exact object bounds. Technical Report 5, MIT AI Lab, April 2000. Aries Project.
8. N. P. Carter, S. W. Keckler, and W. J. Dally. Hardware support for fast capability-based addressing. In Proceedings of the international conference on Architectural support for programming languages and operating systems, ASPLOS-VI, pages 319--327, 1994.
9. S. Chen, B. Falsafi, P. B. Gibbons, M. Kozuch, T. C. Mowry, R. Teodorescu, A. Ailamaki, L. Fix, G. R. Ganger, B. Lin, and S. W. Schlosser. Log-based architectures for general-purpose monitoring of deployed code. In 1st Workshop on Architectural and System Support for Improving Software Dependability (ASID), pages 63--65. ACM, 2006.
10. R. P. Colwell, E. F. Gehringer, and E. D. Jensen. Performance effects of architectural complexity in the Intel 432. ACM Trans. Comput. Syst., 6:296--339, August 1988.
11. J. Criswell, A. Lenharth, D. Dhurjati, and V. Adve. Secure virtual architecture: A safe execution environment for commodity operating systems. In Proceedings of the Symposium on Operating Systems Principles, October 2007.
12. D. Y. Deng and G. E. Suh. High-performance parallel accelerator for flexible and efficient run-time monitoring. In IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 1--12. IEEE Computer Society, 2012.
13. P. J. Denning and S. C. Schwartz. Properties of the working-set model. Communications of the ACM, 15(3):191--198, March 1972.
14. J. B. Dennis and E. C. Van Horn. Programming semantics for multiprogrammed computations. Communications of the ACM, 9(3):143--155, March 1966.
15. J. Devietti, C. Blundell, M. M. K. Martin, and S. Zdancewic. HardBound: Architectural support for spatial safety of the C programming language. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, pages 103--114, 2008.
16. U. Dhawan, A. Kwon, E. Kadric, C. Hri¸tcu, B. C. Pierce, J. M. Smith, A. DeHon, G. Malecha, G. Morrisett, T. F. Knight, Jr., A. Sutherland, T. Hawkins, A. Zyxnfryx, D. Wittenberg, P. Trei, S. Ray, and G. Sullivan. Hardware support for safety interlocks and introspection. In SASO Workshop on Adaptive Host and Network Security, Sept. 2012.
17. R. S. Fabry. Capability-based Addressing. Communications of the ACM, 17(7):403--412, July 1974.
18. E. A. Feustel. On the advantages of tagged architecture. IEEE Transactions on Computers, C-22(7):644--656, July 1973.
19. E. F. Gehringer and J. L. Keedy. Tagged architecture: How compelling are its advantages? In Proceedings of the 12th International Symposium on Computer Architecture, pages 162--170, 1985.
20. R. Greenblatt, T. Knight, Jr., J. Holloway, D. Moon, and D. Weinreb. The LISP machine. In Interactive Programming Environments. McGraw-Hill, 1984.
21. N. Hasabnis, A. Misra, and R. Sekar. Light-weight bounds checking. In Proceedings of the Tenth International Symposium on Code Generation and Optimization, pages 135--144, 2012.
22. J. L. Henning. SPEC CPU2006 benchmark descriptions. SIGARCH Comput. Archit. News, 34(4):1--17, September 2006.
23. M. E. Houdek, F. G. Soltis, and R. L. Hoffman. IBM System/38 Support for Capability-based Addressing. In Proceedings of the Eighth Annual Symposium on Computer Architecture, pages 341--348, 1981.
24. C. Hri¸tcu, M. Greenberg, B. Karel, B. C. Pierce, and G. Morrisett. All your IFCException are belong to us. In 34th IEEE Symposium on Security and Privacy, pages 3--17. IEEE Computer Society Press, May 2013.
25. IBM. IBM System/360 Principles of Operation. 1968.
26. Intel Corporation. Intel64 and IA-32 Architectures Software Developer's Manual, August 2012.
27. T. Jim, J. G. Morrisett, D. Grossman, M. W. Hicks, J. Cheney, and Y. Wang. Cyclone: A safe dialect of C. In ATEC '02: Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, pages 275--288, 2002.
28. D. Johnson. The Intel 432: A VLSI Architecture for Fault-Tolerant Computer Systems. Computer, 17:40--48, August 1984.
29. H. M. Levy. Capability Based Computer Systems. Digital Press, 1984.
30. S. Nagarakatte. Practical Low-overhead Enforcement of Memory Safety for C Programs. PhD thesis, University of Pennsylvania, 2012.
31. S. Nagarakatte, J. Zhao, M. M. K. Martin, and S. Zdancewic. Softbound: Highly compatible and complete spatial memory safety for C. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 245--258, 2009.
32. S. Nagarakatte, J. Zhao, M. M. K. Martin, and S. Zdancewic. CETS: Compiler enforced temporal safety for C. In Proceedings of the International Symposium on Memory Management, pages 31--40, 2010.
33. G. C. Necula, J. Condit, M. Harren, S. McPeak, and W. Weimer. CCured: type-safe retrofitting of legacy software. ACM Trans. Program. Lang. Syst., 27(3):477--526, May 2005.
34. R. M. Needham and R. D. H. Walker. The Cambridge CAP computer and its protection system. In Proceedings of the Symposium on Operating Systems Principles, pages 1--10, Nov. 1977.
35. E. I. Organick. The MULTICS System: An Examination of Its Structure. MIT Press, 1972.
36. E. I. Organick. Computer System Organization: The B5700/B6700 Series. Academic Press, 1973.
37. E. I. Organick. A Programmer's View of the Intel 432 System. McGraw-Hill, 1983.
38. A. T. Phillips and J. S. Tan. Exploring security vulnerabilities by exploiting buffer overflow using the MIPS ISA. In Proceedings of the SIGCSE technical symposium on Computer science education, pages 172--176, New York, NY, USA, 2003. ACM.
39. O. Ruwase and M. S. Lam. A practical dynamic buffer overflow detector. In Proceedings of the 11th Annual Network and Distributed System Security Symposium, pages 159--169, 2004.
40. J. S. Shapiro, J. M. Smith, and D. J. Farber. Eros: a fast capability system. In Proceedings of the Symposium on Operating Systems Principles, pages 170--185. ACM, 1999.
41. R. L. Sites. Alpha AXP Architecture. Digital Technical Journal, 4(4):1--17, 1992. Special Issue.
42. R. N. M. Watson, J. Anderson, B. Laurie, and K. Kennaway. Capsicum: practical capabilities for UNIX. In Proceedings of the 19th USENIX Security Symposium, Washington, DC, August 2010.
43. R. N. M. Watson, P. G. Neumann, J. Woodruff, J. Anderson, R. Anderson, N. Dave, B. Laurie, S. W. Moore, S. J. Murdoch, P. Paeps, M. Roe, and H. Saidi. CHERI: a research platform deconflating hardware virtualization and protection. In Proc. RESoLVE, March 2012.
44. M. V. Wilkes and R. M. Needham. The Cambridge CAP Computer and Its Operating System. North Holland, 1979.
45. W. Wulf, E. Cohen, W. Corwin, A. Jones, R. Levin, C. Pierson, and F. Pollack. Hydra: The kernel of a multiprocessor operating system. Communications of the ACM, 17(6):337--345, June 1974.
46. W. A. Wulf, R. Levin, and S. P. Harbison. HYDRA/C.mmp: An Experimental Computer System. McGraw-Hill, 1981.
47. Xilinx, Inc. Virtex-6 FPGA ML605 Evaluation Kit.
48. Xilinx, Inc., 2100 Logic Drive, San Jose, CA 95124. Virtex-6 FPGA Data Sheet: DC and Switching Characteristics, September 2011. DS512.
49. Xilinx, Inc., 2100 Logic Drive, San Jose, CA 95124. LogiCORE IP Floating-Point Operator v6.0, January 2012.
50. Y. Younan, P. Philippaerts, L. Cavallaro, R. Sekar, F. Piessens, and W. Joosen. Paricheck: an efficient pointer arithmetic checker for C programs. In Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security, pages 145--156, 2010.

Index Terms

• Computer systems organization

  • Architectures

    • Other architectures

      • Special purpose systems

• Hardware

  • Robustness

• Security and privacy

  • Security in hardware

  • Systems security

    • Operating systems security