|
 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
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
| |
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
|
|
| |
5
|
|
| |
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
|
|
 |
9
|
Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
|
| |
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
|
Satish Narayanasamy , Cristiano Pereira , Harish Patil , Robert Cohn , Brad Calder, Automatic logging of operating system effects to guide application-level architecture simulation, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
|
| |
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
|
|
| |
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
|
Feng Qin , Cheng Wang , Zhenmin Li , Ho-seop Kim , Yuanyuan Zhou , Youfeng Wu, LIFT: A Low-Overhead Practical Information Flow Tracking System for Detecting Security Attacks, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.135-148, December 09-13, 2006
[doi> 10.1109/MICRO.2006.29]
|
| |
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
|
|
| |
21
|
|
| |
22
|
The Valgrind Developers. Valgrind. url http://www.valgrind.org/.
|
CITED BY 14
|
|
|
|
|
|
|
|
|
|
|
Vijay Nagarajan , Rajiv Gupta, Support for symmetric shadow memory in multiprocessors, Proceedings of the 6th workshop on Parallel and distributed systems: testing, analysis, and debugging, p.1-9, July 20-21, 2008, Seattle, Washington
|
|
|
Olatunji Ruwase , Phillip B. Gibbons , Todd C. Mowry , Vijaya Ramachandran , Shimin Chen , Michael Kozuch , Michael Ryan, Parallelizing dynamic information flow tracking, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
|
|
|
Chen Tian , Vijay Nagarajan , Rajiv Gupta , Sriraman Tallam, Dynamic recognition of synchronization operations for improved data race detection, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA
|
|
|
Shimin Chen , Michael Kozuch , Theodoros Strigkos , Babak Falsafi , Phillip B. Gibbons , Todd C. Mowry , Vijaya Ramachandran , Olatunji Ruwase , Michael Ryan , Evangelos Vlachos, Flexible Hardware Acceleration for Instruction-Grain Program Monitoring, ACM SIGARCH Computer Architecture News, v.36 n.3, p.377-388, June 2008
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.2