HDTrans: an open source, low-level dynamic instrumentation system

ABSTRACT

Dynamic translation is a general purpose tool used for instrumenting programs at run time. Performance of translated execution relies on balancing the cost of translation against the benefits of any optimizations achieved, and many current translators perform substantial rewriting during translation in an attempt to reduce execution time. Our results show that these optimizations offer no significant benefit even when the translated program has a small, hot working set. When used in a broader range of applications, such as ubiquitous policy enforcement or penetration detection, translator performance cannot rely on the presence of a hot working set to amortize the cost of translation. A simpler, more maintainable, adaptable, and smaller translator appears preferable to more complicated designs in most cases.HDTrans is a light-weight dynamic instrumentation system for the IA-32 architecture that uses some simple and effective translation techniques in combination with established trace linearization and code caching optimizations. We present an evaluation of translation overhead under both benchmark and less idealized conditions, showing that conventional benchmarks do not provide a good prediction of translation overhead when used pervasively.A further contribution of this paper is an analysis of the effectiveness of post-link static pre-translation techniques for overhead reduction. Our results indicate that static pre-translation is effective only when expensive instrumentation or optimization is performed.

REFERENCES

• 1: Advanced Micro Devices, Inc. AMD64 Architecture Tech Docs, 2005. http://www.amd.com/us-en/Processors/TechnicalResources/0,,30_182_739_7044,00.html.
• 2: Altman, E., Gschwind, M., and Sathaye, S. BOA: The architecture of a binary translation processor. In Research Report RC21665 IBM T.J. Watson Research Center (2000).
• 3: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 4: James R. Bell, Threaded code, Communications of the ACM, v.16 n.6, p.370-372, June 1973 [doi>10.1145/362248.362270]
• 5: Bellard, F. QEMU, a Fast and Portable Dynamic Translator. In Proc. 2005 USENIX Annual Technical Conference, FREENIX Track (2005), pp. 41--46.
• 6: Derek L. Bruening , Saman Amarasinghe, Efficient, transparent, and comprehensive runtime code manipulation, Massachusetts Institute of Technology, Cambridge, MA, 2004
• 7: Derek Bruening , Saman Amarasinghe, Maintaining Consistency and Bounding Capacity of Software Code Caches, Proceedings of the international symposium on Code generation and optimization, p.74-85, March 20-23, 2005 [doi>10.1109/CGO.2005.19]
• 8: Derek Bruening , Timothy Garnett , Saman Amarasinghe, An infrastructure for adaptive dynamic optimization, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 9: Derek Bruening , Vladimir Kiriansky , Timothy Garnett , Sanjeev Banerji, Thread-Shared Software Code Caches, Proceedings of the International Symposium on Code Generation and Optimization, p.28-38, March 26-29, 2006 [doi>10.1109/CGO.2006.36]
• 10: Bungale, P., Sridhar, S., and Shapiro, J. S. Low-Complexity Dynamic Translation in VDebug. Tech. Rep. SRL2004-02, Johns Hopkins University Systems Research Laboratory, May 2004.
• 11: Bungale, P., Sridhar, S., and Shapiro, J. S. Supervisor-Mode Virtualization for x86 in VDebug. Tech. Rep. SRL2004-01, Johns Hopkins University Systems Research Laboratory, May 2004.
• 12: Chen, W. K., Lerner, S., Chaiken, R., and Gillies, D. M. Mojo: A Dynamic Optimization System. In ACM Workshop on Feedback-directed and Dynamic Optimization (FDDO-3) (Dec 2000).
• 13: Cristina Cifuentes , Mike Van Emmerik, UQBT: Adaptable Binary Translation at Low Cost, Computer, v.33 n.3, p.60-66, March 2000 [doi>10.1109/2.825697]
• 14: Cifuentes, C., Lewis, B., and Ung, D. Walkabout--A Retargetable Dynamic Binary Translation Framework. In Technical report 2002-106, Sun Microsystems Laboratories (January 2002).
• 15: Bob Cmelik , David Keppel, Shade: a fast instruction-set simulator for execution profiling, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.128-137, May 16-20, 1994, Nashville, Tennessee, United States
• 16: L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
• 17: Devine, S., Bugnion, E., and Rosenblum, M. Virtualization System Including a Virtual Machine Monitor for a Computer with a Segmented Architecture. In United States Patent 6,397,242 (May 2002).
• 18: Robert B. K. Dewar, Indirect threaded code, Communications of the ACM, v.18 n.6, p.330-331, June 1975 [doi>10.1145/360825.360849]
• 19: Paul Barham , Boris Dragovic , Keir Fraser , Steven Hand , Tim Harris , Alex Ho , Rolf Neugebauer , Ian Pratt , Andrew Warfield, Xen and the art of virtualization, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 20: Kemal Ebcioğlu , Erik R. Altman, DAISY: dynamic compilation for 100% architectural compatibility, Proceedings of the 24th annual international symposium on Computer architecture, p.26-37, June 01-04, 1997, Denver, Colorado, United States
• 21: Dawson R. Engler, VCODE: a retargetable, extensible, very fast dynamic code generation system, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.160-170, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 22: Dawson R. Engler , Wilson C. Hsieh , M. Frans Kaashoek, C: a language for high-level, efficient, and machine-independent dynamic code generation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.131-144, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237765]
• 23: Dawson R. Engler , M. Frans Kaashoek, DPF: fast, flexible message demultiplexing using dynamic code generation, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.53-59, August 28-30, 1996, Palo Alto, California, United States
• 24: Dawson R. Engler , Todd A. Proebsting, DCG: an efficient, retargetable dynamic code generation system, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.263-272, October 05-07, 1994, San Jose, California, United States
• 25: Hazelwood, K. Code Cache Management in Dynamic Optimization Systems. PhD thesis, Harvard University, Cambridge, MA, May 2004.
• 26: Kim Hazelwood , Robert Cohn, A Cross-Architectural Interface for Code Cache Manipulation, Proceedings of the International Symposium on Code Generation and Optimization, p.17-27, March 26-29, 2006 [doi>10.1109/CGO.2006.3]
• 27: Kim Hazelwood , James E. Smith, Exploring Code Cache Eviction Granularities in Dynamic Optimization Systems, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.89, March 20-24, 2004, Palo Alto, California
• 28: Kim Hazelwood , Michael D. Smith, Code Cache Management Schemes for Dynamic Optimizers, Proceedings of the Sixth Annual Workshop on Interaction between Compilers and Computer Architectures, p.102, February 03-03, 2002
• 29: Kim Hazelwood , Michael D. Smith, Generational Cache Management of Code Traces in Dynamic Optimization Systems, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.169, December 03-05, 2003
• 30: Raymond J. Hookway , Mark A. Herdeg, DIGITAL FX!32: combining emulation and binary translation, Digital Technical Journal, v.9 n.1, p.3-12, 1997
• 31: Colin Hunter , John Banning, DOS at RISC, BYTE, v.14 n.12, p.361-368, November 1989
• 32: Vladimir Kiriansky , Derek Bruening , Saman P. Amarasinghe, Secure Execution via Program Shepherding, Proceedings of the 11th USENIX Security Symposium, p.191-206, August 05-09, 2002
• 33: Kruegel, C., Robertson, W., Valeur, F., and Vigna, G. Static Disassembly of Obfuscated Binaries. In Proceedings of USENIX Security 2004 (August 2004).
• 34: 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
• 35: C. May, Mimic: a fast system/370 simulator, Papers of the Symposium on Interpreters and interpretive techniques, p.1-13, June 24-26, 1987, St. Paul, Minnesota, United States
• 36: Nethercote, N. Dynamic Binary Analysis and Instrumentation. PhD thesis, University of Cambridge, November 2004.
• 37: Operation, A. U. S. System V Interface Definition. 1989.
• 38: B. Ramakrishna Rau, Levels of representation of programs and the architecture of universal host machines, Proceedings of the 11th annual workshop on Microprogramming, p.67-79, November 19-22, 1978, Pacific Grove, California, United States
• 39: Reddi, V. J., Connors, D. A., and Cohn, R. S. Persistence in Dynamic Code Transformation Systems. In Proc. 2005 Workshop on Binary Instrumentation and Analysis (Sept. 2005).
• 40: Scott, K., Kumar, N., Childers, B., Davidson, J., and Soffa, M. Overhead Reduction Techniques for Software Dynamic Translation. In NSF Workshop on Next Generation Software (April 2004).
• 41: K. Scott , N. Kumar , S. Velusamy , B. Childers , J. W. Davidson , M. L. Soffa, Retargetable and reconfigurable software dynamic translation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 42: Shapiro, J. Debug: The Next Generation UNIX Debugger, 1989.
• 43: Shapiro, J. S., Northup, E., Doerrie, M. S., and Sridhar, S. Coyotos Microkernel Specification, 2006. http:// www.coyotos.org/.
• 44: Jonathan S. Shapiro , Jonathan M. Smith , David J. Farber, EROS: a fast capability system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.170-185, December 12-15, 1999, Charleston, South Carolina, United States
• 45: Shiveley, R. Enhanced Virtualization on Intel Architecture-based Servers. In Technology@Intel Magazine (April 2005).
• 46: Sridhar, S., Shapiro, J. S., and Bungale, P. P. HDTrans: A Low-Overhead Dynamic Translator. In Proc. 2005 Workshop on Binary Instrumentation and Analysis (Sept. 2005).
• 47: Standard Performance Evaluation Corporation. SPEC OMP OpenMP Benchmark Suite, version 3.0, Dec. 2003. http://www.spec.org/omp.
• 48: Standard Performance Evaluation Corporation. SPEC CPU2000 Benchmark Suite, version 1.3, Nov. 2005. http://www.spec.org/ osg/cpu2000.
• 49: Emmett Witchel , Mendel Rosenblum, Embra: fast and flexible machine simulation, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.68-79, May 23-26, 1996, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

General Terms:
Languages, Performance, Security

Keywords:
binary translation, dynamic instrumentation, dynamic translation