More Web Proxy on the site http://driver.im/

research-article

LEAP: lightweight deterministic multi-processor replay of concurrent java programs

Authors:

Charles ZhangAuthors Info & Claims

FSE '10: Proceedings of the eighteenth ACM SIGSOFT international symposium on Foundations of software engineering

Pages 207 - 216

https://doi.org/10.1145/1882291.1882323

Published: 07 November 2010 Publication History

Abstract

The technique of deterministic record and replay aims at faithfully reenacting an earlier program execution. For concurrent programs, it is one of the most important techniques for program understanding and debugging. The state of the art deterministic replay techniques face challenging efficiency problems in supporting multi-processor executions due to the unoptimized treatment of shared memory accesses. We propose LEAP: a deterministic record and replay technique that uses a new type of local order w.r.t. the shared memory locations and concurrent threads. Compared to the related work, our technique records much less information without losing the replay determinism. The correctness of our technique is underpinned by formal models and a replay theorem that we have developed in this work. Through our evaluation using both benchmarks and real world applications, we show that LEAP is more than 10x faster than conventional global-order based approaches and, in most cases, 2x to 10x faster than other local-order based approaches. Our recording overhead on the two large open source multi-threaded applications Tomcat and Derby is less than 10%. Moreover, as the evidence of the deterministic replay, LEAP is able to deterministically reproduce 7 out of 8 real bugs in Tomcat and Derby, 13 out of 16 benchmark bugs in IBM ConTest benchmark suite, and 100% of the randomly injected concurrency bugs.

References

[1]

Gautam Altekar and Ion Stoica. Odr: output deterministic replay for multicore debugging. In SOSP, pages 193--206. ACM, 2009.

Digital Library

[2]

Emery D. Berger, Ting Yang, Tongping Liu, and Gene Novark. Grace: safe multithreaded programming for c/c++. In OOPSLA, pages 81--96. ACM, 2009.

Digital Library

[3]

Robert L. Bocchino, Jr., Vikram S. Adve, Danny Dig, Sarita V. Adve, Stephen Heumann, Rakesh Komuravelli, Jeffrey Overbey, Patrick Simmons, Hyojin Sung, and Mohsen Vakilian. A type and effect system for deterministic parallel java. In OOPSLA, pages 97--116. ACM, 2009.

Digital Library

[4]

Eric Bodden and Klaus Havelund. Racer: effective race detection using aspectj. In ISSTA, pages 155--166. ACM, 2008.

Digital Library

[5]

Jong-Deok Choi and Harini Srinivasan. Deterministic replay of java multithreaded applications. In SPDT, pages 48--59. ACM, 1998.

Digital Library

[6]

Joseph Devietti, Brandon Lucia, Luis Ceze, and Mark Oskin. Dmp: deterministic shared memory multi-processing. In ASPLOS, pages 85--96. ACM, 2009.

Digital Library

[7]

George W. Dunlap, Dominic G. Lucchetti, Michael A. Fetterman, and Peter M. Chen. Execution replay of multiprocessor virtual machines. In VEE, pages 121--130. ACM, 2008.

Digital Library

[8]

Eitan Farchi, Yarden Nir, and Shmuel Ur. Concurrent bug patterns and how to test them. In IPDPS, page 286.2. IEEE Computer Society, 2003.

Digital Library

[9]

Cormac Flanagan and Stephen N Freund. Atomizer: a dynamic atomicity checker for multithreaded programs. In POPL, pages 256--267. ACM, 2004.

Digital Library

[10]

A. Georges, M. Christiaens, M. Ronsse, and K. De Bosschere. Jarec: a portable record/replay environment for multi-threaded java applications. Software Practice and Experience, 34(6):523--547, 2004.

Digital Library

[11]

Richard L. Halpert, Christopher J. F. Pickett, and Clark Verbrugge. Component-based lock allocation. In PACT, pages 353--364. IEEE Computer Society, 2007.

Digital Library

[12]

Derek R. Hower and Mark D. Hill. Rerun: Exploiting episodes for lightweight memory race recording. In ISCA, pages 265--276. IEEE Computer Society, 2008.

Digital Library

[13]

Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558--565, 1978.

Digital Library

[14]

T. J. LeBlanc and J. M. Mellor-Crummey. Debugging parallel programs with instant replay. IEEE Transactions on Computers, 36(4):471--482, 1987.

Digital Library

[15]

Shan Lu, Soyeon Park, Chongfeng Hu, Xiao Ma, Weihang Jiang, Zhenmin Li, Raluca A. Popa, and Yuanyuan Zhou. Muvi: automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs. In SOSP, pages 103--116. ACM, 2007.

Digital Library

[16]

Pablo Montesinos, Luis Ceze, and Josep Torrellas. Delorean: Recording and deterministically replaying shared-memory multi-processor execution efficiently. In ISCA, pages 289--300. IEEE Computer Society, 2008.

Digital Library

[17]

Pablo Montesinos, Matthew Hicks, Samuel T. King, and Josep Torrellas. Capo: a software-hardware interface for practical deterministic multi-processor replay. In ASPLOS, pages 73--84. ACM, 2009.

Digital Library

[18]

Madanlal Musuvathi, Shaz Qadeer, Thomas Ball, Gérard Basler, Piramanayagam A. Nainar, and Iulian Neamtiu. Finding and reproducing heisenbugs in concurrent programs. In OSDI, pages 267--280, 2008.

Digital Library

[19]

Satish Narayanasamy, Cristiano Pereira, Harish Patil, Robert Cohn, and Brad Calder. Automatic logging of operating system effects to guide application-level architecture simulation. In SIGMETRICS, pages 216--227. ACM, 2006.

Digital Library

[20]

Satish Narayanasamy, Gilles Pokam, and Brad Calder. Bugnet: Continuously recording program execution for deterministic replay debugging. In ISCA, pages 284--295. IEEE Computer Society, 2005.

Digital Library

[21]

Satish Narayanasamy, Zhenghao Wang, Jordan Tigani, Andrew Edwards, and Brad Calder. Automatically classifying benign and harmful data racesallusing replay analysis. In PLDI, pages 22--31. ACM, 2007.

Digital Library

[22]

Robert O'Callahan and Jong-Deok Choi. Hybrid dynamic data race detection. In PPoPP, pages 167--178. ACM, 2003.

Digital Library

[23]

Marek Olszewski, Jason Ansel, and Saman Amarasinghe. Kendo: efficient deterministic multithreading in software. In ASPLOS, pages 97--108, New York, NY, USA, 2009. ACM.

Digital Library

[24]

Soyeon Park, Yuanyuan Zhou, Weiwei Xiong, Zuoning Yin, Rini Kaushik, Kyu H. Lee, and Shan Lu. Pres: probabilistic replay with execution sketching on multi-processors. In SOSP, pages 177--192. ACM, 2009.

Digital Library

[25]

Michiel Ronsse and Koen De Bosschere. Recplay: a fully integrated practical record/replay system. ACM TOCS, 17(2):133--152, 1999.

Digital Library

[26]

Michiel Ronsse, Koen De Bosschere, Mark Christiaens, Jacques Chassin de Kergommeaux, and Dieter Kranzlm¨uller. Record/replay for nondeterministic program executions. Communications of the ACM, 46(9):62--67, 2003.

Digital Library

[27]

Mark Russinovich and Bryce Cogswell. Replay for concurrent non-deterministic shared-memory applications. In PLDI, pages 258--266. ACM, 1996.

Digital Library

[28]

Koushik Sen. Race directed random testing of concurrent programs. In PLDI, pages 11--21. ACM, 2008.

Digital Library

[29]

Mandana Vaziri, Frank Tip, and Julian Dolby. Associating synchronization constraints with data in an object-oriented language. In POPL, pages 334--345. ACM, 2006.

Digital Library

[30]

Min Xu, Rastislav Bodik, and Mark D. Hill. A "flight data recorder" for enabling full-system multiprocessor deterministic replay. In ISCA, pages 122--135. ACM, 2003.

Digital Library

[31]

Jie Yu and Satish Narayanasamy. A case for an interleaving constrained shared-memory multi-processor. In ISCA, pages 325--336. ACM, 2009.

Digital Library

Cited By

Schwartz DKowshik APina L(2024)Jmvx: Fast Multi-threaded Multi-version Execution and Record-Replay for Managed LanguagesProceedings of the ACM on Programming Languages10.1145/36897698:OOPSLA2(1641-1669)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689769
Schwartz DSridharan M(2024)JMVX: Improving Record-Replay for Managed LanguagesCompanion Proceedings of the 2024 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity10.1145/3689491.3691819(13-15)Online publication date: 20-Oct-2024
https://dl.acm.org/doi/10.1145/3689491.3691819
Zhao QQiu ZShao SHui XKhan HJin GKloeckner AMoreira J(2022)Understanding and Reaching the Performance Limit of Schedule Tuning on Stable Synchronization DeterminismProceedings of the International Conference on Parallel Architectures and Compilation Techniques10.1145/3559009.3569669(223-238)Online publication date: 8-Oct-2022
https://dl.acm.org/doi/10.1145/3559009.3569669
Show More Cited By

Index Terms

LEAP: lightweight deterministic multi-processor replay of concurrent java programs
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Process validation
        Traceability
      2. Software defect analysis
        Software testing and debugging

Recommendations

LEAP: lightweight deterministic multi-processor replay of concurrent java programs
FSE '10: Proceedings of the eighteenth ACM SIGSOFT international symposium on Foundations of software engineering

The technique of deterministic record and replay aims at faithfully reenacting an earlier program execution. For concurrent programs, it is one of the most important techniques for program understanding and debugging. This demo presents LEAP: an ...
Transparent mutable replay for multicore debugging and patch validation
ASPLOS '13

We present Dora, a mutable record-replay system which allows a recorded execution of an application to be replayed with a modified version of the application. This feature, not available in previous record-replay systems, enables powerful new ...
Transparent mutable replay for multicore debugging and patch validation
ASPLOS '13: Proceedings of the eighteenth international conference on Architectural support for programming languages and operating systems

We present Dora, a mutable record-replay system which allows a recorded execution of an application to be replayed with a modified version of the application. This feature, not available in previous record-replay systems, enables powerful new ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FSE '10: Proceedings of the eighteenth ACM SIGSOFT international symposium on Foundations of software engineering

November 2010

302 pages

ISBN:9781605587912

DOI:10.1145/1882291

General Chair:
Gruia-Catalin Roman
Washington University in St. Louis, USA
,
Program Chair:
André van der Hoek
University of California, Irvine, USA

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 November 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGSOFT/FSE'10

Sponsor:

SIGSOFT

SIGSOFT/FSE'10: 18th ACM SIGSOFT Symposium on the Foundations of Software Engineering

November 7 - 11, 2010

New Mexico, Santa Fe, USA

Acceptance Rates

Overall Acceptance Rate 17 of 128 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

74
Total Citations
View Citations
526
Total Downloads

Downloads (Last 12 months)39
Downloads (Last 6 weeks)7

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Schwartz DKowshik APina L(2024)Jmvx: Fast Multi-threaded Multi-version Execution and Record-Replay for Managed LanguagesProceedings of the ACM on Programming Languages10.1145/36897698:OOPSLA2(1641-1669)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689769
Schwartz DSridharan M(2024)JMVX: Improving Record-Replay for Managed LanguagesCompanion Proceedings of the 2024 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity10.1145/3689491.3691819(13-15)Online publication date: 20-Oct-2024
https://dl.acm.org/doi/10.1145/3689491.3691819
Zhao QQiu ZShao SHui XKhan HJin GKloeckner AMoreira J(2022)Understanding and Reaching the Performance Limit of Schedule Tuning on Stable Synchronization DeterminismProceedings of the International Conference on Parallel Architectures and Compilation Techniques10.1145/3559009.3569669(223-238)Online publication date: 8-Oct-2022
https://dl.acm.org/doi/10.1145/3559009.3569669
Ma XAshraf IChan W(2021)Sound Predictive Atomicity Violation Detection§2021 IEEE 21st International Conference on Software Quality, Reliability and Security (QRS)10.1109/QRS54544.2021.00022(114-125)Online publication date: Dec-2021
https://doi.org/10.1109/QRS54544.2021.00022
Chu JYu THuffman Hayes JHan XZhao Y(2021)Effective fault localization and context‐aware debugging for concurrent programsSoftware Testing, Verification and Reliability10.1002/stvr.179732:1Online publication date: 13-Oct-2021
https://doi.org/10.1002/stvr.1797
Liu YYan FXia MQi ZLiu X(2020)TimelyRep: Timing deterministic replay for Android web applicationsSoftware Testing, Verification and Reliability10.1002/stvr.174530:4-5Online publication date: 6-Jul-2020
https://doi.org/10.1002/stvr.1745
Pobee EChan WDumas MPfahl DApel SRusso A(2019)AggrePlay: efficient record and replay of multi-threaded programsProceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3338906.3338959(567-577)Online publication date: 12-Aug-2019
https://dl.acm.org/doi/10.1145/3338906.3338959
Lidbury CDonaldson AMcKinley KFisher K(2019)Sparse record and replay with controlled schedulingProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314635(576-593)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314635
Pobee EMei XChan WZimmermann TLawall JMarinov D(2019)Efficient transaction-based deterministic replay for multi-threaded programsProceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2019.00076(760-771)Online publication date: 10-Nov-2019
https://dl.acm.org/doi/10.1109/ASE.2019.00076
Zaman THan XYu TZimmermann TLawall JMarinov D(2019)SCMinerProceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2019.00055(515-526)Online publication date: 10-Nov-2019
https://dl.acm.org/doi/10.1109/ASE.2019.00055
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents