How to shadow every byte of memory used by a program

ABSTRACT

Several existing dynamic binary analysis tools use shadowmemory-they shadow, in software, every byte of memory used by a program with another value that says something about it. Shadow memory is difficult to implement both efficiently and robustly. Nonetheless, existing shadow memory implementations have not been studied in detail. This is unfortunate, because shadow memory is powerful-for example, some of the existing tools that use it detect critical errors such as bad memory accesses, data races, and uses of uninitialised or untrusted data. In this paper we describe the implementation of shadow memory in Memcheck, a popular memory checker built with Valgrind, a dynamic binary instrumentation framework. This implementation has several novel features that make it efficient: carefully chosen data structures and operations result in a mean slow-down factor of only 22.2 and moderate memory usage. This may sound slow, but we show it is 8.9 times faster and 8.5 times smaller on average than a naive implementation, and shadow memory operations account for only about half of Memcheck's execution time. Equally importantly, unlike some tools, Memcheck's shadow memory implementation is robust: it is used on Linux by thousands of programmers on sizeable programs such as Mozilla and OpenOffice, and is suited to almost any memory configuration. This is the first detailed description of a robust shadow memory implementation, and the first detailed experimental evaluation of any shadow memory implementation. The ideas within are applicable to any shadow memory tool built with any instrumentation framework.

References

1. D. Bruening, T. Garnett, and S. Amarasinghe. An infrastructure for adaptive dynamic optimization. In Proceedings of CGO'03, pages 265--276, San Francisco, California, USA, March 2003.
2. M. Burrows. Personal communication, February 2006.
3. M. Burrows, S. N. Freund, and J. L. Wiener. Run-time type checking for binary programs. In Proceedings of CC 2003, pages 90--105, Warsaw, Poland, April 2003.
4. W. Cheng, Q. Zhao, B. Yu, and S. Hiroshige. Tainttrace: Efficient flow tracing with dynamic binary rewriting. In Proceedings of ISCC 2006, pages 749--754, Cagliari, Sardinia, Italy, June 2006.
5. J. J. Harrow, Jr. Runtime checking of multithreaded applications with Visual Threads. In Proceedings of SPIN 2000, pages 331--342, Stanford, California, USA, August 2000.
6. R. Hastings and B. Joyce. Purify: Fast detection of memory leaks and access errors. In Proceedings of the Winter USENIX Conference, pages 125--136, San Francisco, California, USA, January 1992.
7. K. Hazelwood. Code Cache Management in Dynamic Optimization Systems. PhD thesis, Harvard University, Cambridge, Mass., USA, May 2004.
8. V. Kiriansky, D. Bruening, and S. Amarasinghe. Secure execution via program shepherding. In Proceedings of the 11th USENIX Security Symposium, pages 191--206, San Francisco, California, USA, August 2002.
9. C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. Pin: Building customized program analysis tools with dynamic instrumentation. In Proceedings of PLDI 2005, pages 191--200, Chicago, Illinois, USA, June 2005.
10. A. Mühlenfeld and F. Wotawa. Fault detection in multi-threaded C++ server applications. In Informal Proceedings of TV06, pages 191--200, Seattle, Washington, USA, August 2006.
11. S. Narayanasamy, C. Pereira, H. Patil, R. Cohn, and B. Calder. Automatic logging of operation system effects to guide application--level architecture simulation. In Proceedings of SIGMetrics/Performance 2006, pages 216--227, St. Malo, France, June 2006.
12. N. Nethercote. Dynamic Binary Analysis and Instrumentation. PhD thesis, University of Cambridge, United Kingdom, November 2004.
13. N. Nethercote and J. Fitzhardinge. Bounds-checking entire programs without recompiling. In Informal Proceedings of SPACE 2004, Venice, Italy, January 2004.
14. N. Nethercote and A. Mycroft. Redux: A dynamic dataflow tracer. Electronic Notes in Theoretical Computer Science, 89(2), 2003.
15. N. Nethercote and J. Seward. Valgrind: A program supervision framework. Electronic Notes in Theoretical Computer Science, 89(2), 2003.
16. Nicholas Nethercote and Julian Seward. Valgrind: A framework for heavyweight dynamic binary instrumentation. In Proceedings of PLDI 2007, San Diego, California, USA, June 2007.
17. J. Newsome and D. Song. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. In Proceedings of NDSS '05, San Diego, California, USA, February 2005.
18. F. Qin, C. Wang, Z. Li, H. Kim, Y. Zhou, and Y. Wu. Lift: A low-overhead practical information flow tracking system for detecting security attacks. In Proceedings of the Annual IEEE/ACM International Symposium on Microarchitecture (Micro'06), Orlando, Florida, USA, December 2006.
19. M. Ronsse, B. Stougie, J. Maebe, F. Cornelis, and K. De Bosschere. An efficient data race detector backend for DIOTA. In Parallel Computing: Software Technology, Algorithms, Architectures & Applications, volume~13, pages 39--46. Elsevier, February 2004.
20. S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems, 15(4):391--411, November 1997.
21. J. Seward and N. Nethercote. Using Valgrind to detect undefined value errors with bit-precision. In Proceedings of the USENIX'05 Annual Technical Conference, Anaheim, California, USA, April 2005.
22. The Valgrind Developers. Valgrind. url http://www.valgrind.org/.

Index Terms

• Information systems

  • Data management systems

    • Data structures

    • Middleware for databases

      • Distributed transaction monitors

  • Information storage systems

    • Record storage systems

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging

  • Software notations and tools

    • General programming languages

      • Language features

        • Data types and structures

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Monitors

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

  • Theory and algorithms for application domains

    • Database theory

      • Data structures and algorithms for data management