Support for symmetric shadow memory in multiprocessors

ABSTRACT

Runtime monitoring support serves as a foundation for the important tasks of providing security [15, 14, 2], performing debugging [13, 11, 8], and improving performance of applications [1]. Runtime monitoring, typically, requires the maintenance of meta data associated with each of the application's original memory location, which are held in corresponding shadow memory locations. Each original memory instruction (OMI) is then accompanied by additional shadow memory instructions (SMIs) that manipulate the meta data associated with the memory location. Often the SMIs associated with OMIs are symmetric, in that, original stores (loads) are accompanied by shadow stores (loads). Unfortunately, existing shadow memory implementations need thread serialization to ensure that OMIs and SMIs are executed atomically [12]. Naturally this is not an efficient approach, especially in the now ubiquitous multiprocessors.

In this paper, we present an efficient shadow memory implementation that handles symmetric shadow instructions. By coupling the coherency of shadow memory with the coherency of the main memory, we ensure that the SMIs execute atomically with their corresponding OMIs. We also couple the allocation of application memory pages with its associated shadow pages, for enabling fast translation of original addresses into corresponding shadow memory addresses. Our experiments show that the overheads of run-time monitoring tasks are significantly reduced in comparison to previous software implementations.

REFERENCES

• 1: 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
• 2: Winnie Cheng , Qin Zhao , Bei Yu , Scott Hiroshige, TaintTrace: Efficient Flow Tracing with Dynamic Binary Rewriting, Proceedings of the 11th IEEE Symposium on Computers and Communications, p.749-754, June 26-29, 2006 [doi>10.1109/ISCC.2006.158]
• 3: J. Chung, M. Dalton, H. Kannan, and C. Kozyrakis. Thread-safe binary translation using transactional memory. In HPCA, 2008.
• 4: Michael Dalton , Hari Kannan , Christos Kozyrakis, Raksha: a flexible information flow architecture for software security, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 5: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 6: 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
• 7: José F. Martínez , Jose Renau , Michael C. Huang , Milos Prvulovic , Josep Torrellas, Cherry: checkpointed early resource recycling in out-of-order microprocessors, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 8: V. Nagarajan, D. Jeffrey, R. Gupta, and N. Gupta. Ontrac: A system for efficient online tracing for debugging. In ICSM, pages 445--454, 2007.
• 9: Satish Narayanasamy , Gilles Pokam , Brad Calder, BugNet: Recording Application-Level Execution for Deterministic Replay Debugging, IEEE Micro, v.26 n.1, p.100-109, January 2006 [doi>2006-02-17 02:00:03.800]
• 10: Naveen Neelakantam , Ravi Rajwar , Suresh Srinivas , Uma Srinivasan , Craig Zilles, Hardware atomicity for reliable software speculation, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 11: N. Nethercote and A. Mycroft. Redux: A dynamic dataflow tracer. Electronic Notes in Theoretical Computer Science 89 No. 2, 2003.
• 12: Nicholas Nethercote , Julian Seward, How to shadow every byte of memory used by a program, Proceedings of the 3rd international conference on Virtual execution environments, June 13-15, 2007, San Diego, California, USA [doi>10.1145/1254810.1254820]
• 13: Nicholas Nethercote , Julian Seward, Valgrind: a framework for heavyweight dynamic binary instrumentation, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 14: J. Newsome and D. Song. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. In NDSS, 2005.
• 15: 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]
• 16: J. Renau, B. Fraguela, J. Tuck, W. Liu, M. Prvulovic, L. Ceze, S. Sarangi, P. Sack, K. Strauss, and P. Montesinos. SESC simulator, January 2005. http://sesc.sourceforge.net.
• 17: G. Edward Suh , Jae W. Lee , David Zhang , Srinivas Devadas, Secure program execution via dynamic information flow tracking, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 18: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy
• 19: Min Xu , Rastislav Bodik , Mark D. Hill, A "flight data recorder" for enabling full-system multiprocessor deterministic replay, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids; Tracing
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

General Terms:
Experimentation, Measurement, Reliability

Keywords:
monitoring, symmetric shadow memory