ISOLATOR: dynamically ensuring isolation in comcurrent programs

ABSTRACT

In this paper, we focus on concurrent programs that use locks to achieve isolation of data accessed by critical sections of code. We present ISOLATOR, an algorithm that guarantees isolation for well-behaved threads of a program that obey a locking discipline even in the presence of ill-behaved threads that disobey the locking discipline. ISOLATOR uses code instrumentation, data replication, and virtual memory protection to detect isolation violations and delays ill-behaved threads to ensure isolation. Our instrumentation scheme requires access only to the code of well-behaved threads. We have evaluated ISOLATOR on several benchmark programs and found that ISOLATOR can ensure isolation with reasonable runtime overheads. In addition, we present three general desiderata - safety, isolation, and permissiveness - for any scheme that attempts to ensure isolation, and formally prove that ISOLATOR satisfies all of these desiderata.

REFERENCES

• 1: Linux memory protection. http://linux.about.com/library/cmd/blcmdl2 mprotect.htm, March 2008.
• 2: Memory protection Windows. http://msdn2.microsoft.com/enus/library/aa366785(VS.85).aspx, March 2008.
• 3: Andrew W. Appel , Kai Li, Virtual memory primitives for user programs, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.96-107, April 08-11, 1991, Santa Clara, California, United States
• 4: Lee Baugh , Naveen Neelakantam , Craig Zilles, Using Hardware Memory Protection to Build a High-Performance, Strongly-Atomic Hybrid Transactional Memory, Proceedings of the 35th International Symposium on Computer Architecture, p.115-126, June 21-25, 2008
• 5: Dawson Engler , Ken Ashcraft, RacerX: effective, static detection of race conditions and deadlocks, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 6: C. Flanagan and S. N. Freund. Automatic Synchronization Correction. In Electronic Proc. of SCOOL, 2005.
• 7: Bohuslav Krena , Zdenek Letko , Rachel Tzoref , Shmuel Ur , Tomáš Vojnar, Healing data races on-the-fly, Proceedings of the 2007 ACM workshop on Parallel and distributed systems: testing and debugging, July 09-09, 2007, London, United Kingdom [doi>10.1145/1273647.1273658]
• 8: Vitaliy B. Lvin , Gene Novark , Emery D. Berger , Benjamin G. Zorn, Archipelago: trading address space for reliability and security, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 9: Paruj Ratanaworabhan , Martin Burtscher , Darko Kirovski , Benjamin Zorn , Rahul Nagpal , Karthik Pattabiraman, Detecting and tolerating asymmetric races, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
• 10: Mayur Naik , Alex Aiken , John Whaley, Effective static race detection for Java, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 11: Eli Pozniansky , Assaf Schuster, Efficient on-the-fly data race detection in multithreaded C++ programs, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 12: Polyvios Pratikakis , Jeffrey S. Foster , Michael Hicks, LOCKSMITH: context-sensitive correlation analysis for race detection, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 13: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 14: Tatiana Shpeisman , Vijay Menon , Ali-Reza Adl-Tabatabai , Steven Balensiefer , Dan Grossman , Richard L. Hudson , Katherine F. Moore , Bratin Saha, Enforcing isolation and ordering in STM, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 15: Emmett Witchel , Josh Cates , Krste Asanović, Mondrian memory protection, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 16: Yuan Yu , Tom Rodeheffer , Wei Chen, RaceTrack: efficient detection of data race conditions via adaptive tracking, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 17: Pin Zhou , Feng Qin , Wei Liu , Yuanyuan Zhou , Josep Torrellas, iWatcher: Efficient Architectural Support for Software Debugging, Proceedings of the 31st annual international symposium on Computer architecture, p.224, June 19-23, 2004, München, Germany
• 18: S Rajamani, G. Ramalingam, V. P. Ranganath and K. Vaswani. Isolator: Dynamically Ensuring Isolation in Concurrent Programs. Technical Report MSR-TR-2008-91, Microsoft Research, 2008.
• 19: Martín Abadi , Tim Harris , Mojtaba Mehrara, Transactional memory with strong atomicity using off-the-shelf memory protection hardware, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

General Terms:
Performance, Reliability

Keywords:
concurreny, isolation, memory protection