research-article

The RoadRunner Dynamic Analysis Framework for Concurrent Programs

Authors:

Cormac Flanagan,

Stephen N. FreundAuthors Info & Claims

PASTE '10: Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering

Pages 1 - 8

https://doi.org/10.1145/1806672.1806674

Published: 06 May 2010 Publication History

Abstract

RoadRunner is a dynamic analysis framework designed to facilitate rapid prototyping and experimentation with dynamic analyses for concurrent Java programs. It provides a clean API for communicating an event stream to back-end analyses, where each event describes some operation of interest performed by the target program, such as accessing memory, synchronizing on a lock, forking a new thread, and so on. This API enables the developer to focus on the essential algorithmic issues of the dynamic analysis, rather than on orthogonal infrastructure complexities.

Each back-end analysis tool is expressed as a filter over the event stream, allowing easy composition of analyses into tool chains. This tool-chain architecture permits complex analyses to be described and implemented as a sequence of more simple, modular steps, and it facilitates experimentation with different tool compositions. Moreover, the ability to insert various monitoring tools into the tool chain facilitates debugging and performance tuning.

Despite RoadRunner's flexibility, careful implementation and optimization choices enable RoadRunner-based analyses to offer comparable performance to traditional, monolithic analysis prototypes, while being up to an order of magnitude smaller in code size. We have used RoadRunner to develop several dozen tools and have successfully applied them to programs as large as the Eclipse programming environment.

References

[1]

R. Agarwal and S. D. Stoller. Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables. In PADTAD, pages 51--60, 2006.

Digital Library

[2]

Byte Code Engineering Library. http://jakarta.apache.org/bcel/, 2007.

[3]

E. Bruneton, R. Lenglet, and T. Coupaye. ASM: A code manipulation tool to implement adaptable systems. In Adaptable and extensible component systems, 2002.

[4]

J. Burnim and K. Sen. Asserting and checking determinism for multithreaded programs. In FSE, pages 3--12, 2009.

Digital Library

[5]

J.-D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan. Efficient and precise datarace detection for multithreaded object-oriented programs. In PLDI, pages 258--269, 2002.

Digital Library

[6]

M. Christiaens and K. D. Bosschere. TRaDe: Data Race Detection for Java. In International Conference on Computational Science, pages 761--770, 2001.

Digital Library

[7]

The Eclipse programming environment, version 3.4.0. Available at http://www.eclipse.org, 2009.

[8]

T. Elmas, S. Qadeer, and S. Tasiran. Goldilocks: A race and transaction-aware Java runtime. In PLDI, pages 245--255, 2007.

Digital Library

[9]

C. Flanagan and S. N. Freund. Atomizer: A dynamic atomicity checker for multithreaded programs. Sci. Comput. Program., 71(2):89--109, 2008.

Digital Library

[10]

C. Flanagan and S. N. Freund. FastTrack: efficient and precise dynamic race detection. In PLDI, pages 121--133, 2009.

Digital Library

[11]

C. Flanagan and S. N. Freund. Adversarial memory for detecting destructive races. In PLDI, 2010.

Digital Library

[12]

C. Flanagan, S. N. Freund, and J. Yi. Velodrome: A sound and complete dynamic atomicity checker for multithreaded programs. In PLDI, pages 293--303, 2008.

Digital Library

[13]

J. Hatcliff, Robby, and M. B. Dwyer. Verifying atomicity specifications for concurrent object-oriented software using model-checking. In VMCAI, pages 175--190, 2004.

[14]

Java Grande Forum. Java Grande benchmark suite. Available at http://www.javagrande.org/, 2008.

[15]

P. Joshi, M. Naik, C.-S. Park, and K. Sen. Calfuzzer: An extensible active testing framework for concurrent programs. In CAV, pages 675--681, 2009.

Digital Library

[16]

P. Joshi, C.-S. Park, K. Sen, and M. Naik. A randomized dynamic program analysis technique for detecting real deadlocks. In PLDI, pages 110--120, 2009.

Digital Library

[17]

G. Kiczales, J. Lamping, A. Mendhekar, C. Maeda, C. V. Lopes, J.-M. Loingtier, and J. Irwin. Aspect-oriented programming. In ECOOP, pages 220--242, 1997.

[18]

A. Kinneer, M. B. Dwyer, and G. Rothermel. Sofya: Supporting rapid development of dynamic program analyses for Java. ICSE Companion, pages 51--52, 2007.

Digital Library

[19]

F. Mattern. Virtual time and global states of distributed systems. In Workshop on Parallel and Distributed Algorithms, 1988.

[20]

N. Nethercote and J. Seward. Valgrind: A framework for heavyweight dynamic binary instrumentation. In PLDI, pages 89--100, June 2007.

Digital Library

[21]

R. O'Callahan and J.-D. Choi. Hybrid dynamic data race detection. In PPOPP, pages 167--178, 2003.

Digital Library

[22]

E. Pozniansky and A. Schuster. MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs. Concurrency and Computation: Practice and Experience, 19(3):327--340, 2007.

Digital Library

[23]

C. Sadowski, S. N. Freund, and C. Flanagan. SingleTrack: A dynamic determinism checker for multithreaded programs. In ESOP, pages 394--409, 2009.

Digital Library

[24]

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. E. Anderson. Eraser: A dynamic data race detector for multi-threaded programs. TOCS, 15(4):391--411, 1997.

Digital Library

[25]

A. Srivastava and A. Eustace. ATOM : A system for building customized program analysis tools. In PLDI, pages 196--205, 1994.

Digital Library

[26]

R. Vallee-Rai, E. Gagnon, L. Hendren, P. Lam, P. Pominville, and V. Sundaresan. Optimizing Java bytecode using the Soot framework: Is it feasible? In Compiler Construction, pages 18--34, 2000.

Digital Library

[27]

C. von Praun and T. Gross. Object race detection. In OOPSLA, pages 70--82, 2001.

Digital Library

[28]

L. Wang and S. D. Stoller. Runtime analysis of atomicity for multithreaded programs. IEEE Trans. Software Eng., 32(2):93--110, 2006.

Digital Library

[29]

M. Xu, R. Bodík, and M. D. Hill. A serializability violation detector for shared-memory server programs. In PLDI, pages 1--14, 2005.

Digital Library

[30]

J. Yi, C. Sadowski, and C. Flanagan. SideTrack: generalizing dynamic atomicity analysis. In PADTAD, 2009.

Digital Library

[31]

Y. Yu, T. Rodeheffer, and W. Chen. RaceTrack: Efficient detection of data race conditions via adaptive tracking. In SOSP, pages 221--234, 2005.

Digital Library

Cited By

Hora ARoychoudhury APaiva AAbreu RStorey M(2024)SpotFlow: Tracking Method Calls and States at RuntimeProceedings of the 2024 IEEE/ACM 46th International Conference on Software Engineering: Companion Proceedings10.1145/3639478.3640029(35-39)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3639478.3640029
Zheng DSen KRoychoudhury APaiva AAbreu RStorey MAniche MNagappan N(2024)Dynamic Inference of Likely Symbolic Tensor Shapes in Python Machine Learning ProgramsProceedings of the 46th International Conference on Software Engineering: Software Engineering in Practice10.1145/3639477.3639718(147-156)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3639477.3639718
Ang ZMathur U(2024)Predictive Monitoring against Pattern Regular LanguagesProceedings of the ACM on Programming Languages10.1145/36329158:POPL(2191-2225)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632915
Show More Cited By

Index Terms

The RoadRunner Dynamic Analysis Framework for Concurrent Programs

Recommendations

Opportunities for concurrent dynamic analysis with explicit inter-core communication
PASTE '10: Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering

Multicore is now the dominant processor trend, and the number of cores is rapidly increasing. The paradigm shift to multicore forces the redesign of the software stack, which includes dynamic analysis. Dynamic analyses provide rich features to software ...
Race directed random testing of concurrent programs
PLDI '08

Bugs in multi-threaded programs often arise due to data races. Numerous static and dynamic program analysis techniques have been proposed to detect data races. We propose a novel randomized dynamic analysis technique that utilizes potential data race ...
Race directed random testing of concurrent programs
PLDI '08: Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation

Bugs in multi-threaded programs often arise due to data races. Numerous static and dynamic program analysis techniques have been proposed to detect data races. We propose a novel randomized dynamic analysis technique that utilizes potential data race ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PASTE '10: Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering

June 2010

96 pages

ISBN:9781450300827

DOI:10.1145/1806672

Program Chairs:
Sorin Lerner
University of California, San Diego, USA
,
Atanas Rountev
Ohio State University, 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 May 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PASTE '10

Sponsor:

PASTE '10: ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering

June 5 - 6, 2010

Ontario, Toronto, Canada

Acceptance Rates

Overall Acceptance Rate 57 of 159 submissions, 36%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

128
Total Citations
View Citations
560
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)3

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hora ARoychoudhury APaiva AAbreu RStorey M(2024)SpotFlow: Tracking Method Calls and States at RuntimeProceedings of the 2024 IEEE/ACM 46th International Conference on Software Engineering: Companion Proceedings10.1145/3639478.3640029(35-39)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3639478.3640029
Zheng DSen KRoychoudhury APaiva AAbreu RStorey MAniche MNagappan N(2024)Dynamic Inference of Likely Symbolic Tensor Shapes in Python Machine Learning ProgramsProceedings of the 46th International Conference on Software Engineering: Software Engineering in Practice10.1145/3639477.3639718(147-156)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3639477.3639718
Ang ZMathur U(2024)Predictive Monitoring against Pattern Regular LanguagesProceedings of the ACM on Programming Languages10.1145/36329158:POPL(2191-2225)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632915
Titzer BGilbert ETeo BAnand YTakayama KMiller HTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Flexible Non-intrusive Dynamic Instrumentation for WebAssemblyProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651338(398-415)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651338
Artho CParízek PQu DGalgali VYi P(2024)JPF: From 2003 to 2023Tools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-031-57249-4_1(3-22)Online publication date: 5-Apr-2024
https://doi.org/10.1007/978-3-031-57249-4_1
Wang MSrikant SSamak MO’Reilly UFerrara PHadarean L(2023)RaceInjector: Injecting Races to Evaluate and Learn Dynamic Race Detection AlgorithmsProceedings of the 12th ACM SIGPLAN International Workshop on the State Of the Art in Program Analysis10.1145/3589250.3596142(63-70)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3589250.3596142
Castañeda ARodríguez GOshman RNolin AHalldorsson MBalliu A(2023)Asynchronous Wait-Free Runtime Verification and Enforcement of LinearizabilityProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594563(90-101)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594563
Ma XAshraf IChan W(2023)Davida: A Decentralization Approach to Localizing Transaction Sequences for Debugging Transactional Atomicity ViolationsIEEE Transactions on Reliability10.1109/TR.2022.317668072:2(808-826)Online publication date: Jun-2023
https://doi.org/10.1109/TR.2022.3176680
Bendler DFelderer M(2022)Competency Models for Information Security and Cybersecurity Professionals: Analysis of Existing Work and a New ModelACM Transactions on Computing Education10.1145/357320523:2(1-33)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1145/3573205
Arvanitis INtousakis GIoannidis SVasilakis NLindorfer MPolakis J(2022)A systematic analysis of the event-stream incidentProceedings of the 15th European Workshop on Systems Security10.1145/3517208.3523753(22-28)Online publication date: 5-Apr-2022
https://dl.acm.org/doi/10.1145/3517208.3523753
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