skip to main content
10.1145/1639622.1639630acmconferencesArticle/Chapter ViewAbstractPublication PagesisstaConference Proceedingsconference-collections
research-article

SideTrack: generalizing dynamic atomicity analysis

Published: 19 July 2009 Publication History

Abstract

Atomicity is a key correctness specification for multithreaded programs. Prior dynamic atomicity analyses include precise tools, which report an error if and only if the observed trace is not serializable; and imprecise tools, which generalize from the observed trace to report errors that might occur on other traces, but which may also report false alarms.
This paper presents SideTrack, a lightweight online dynamic analysis that generalizes from the observed trace without introducing the potential for false alarms. If SideTrack reports an error, then some feasible trace of the source program is not serializable. Experimental results show that this generalization ability increases the number of atomicity violations detected by SideTrack by 40%.

References

[1]
S. V. Adve and K. Gharachorloo. Shared memory consistency models: A tutorial. IEEE Computer, 29(12):66--76, 1996.
[2]
C. Artho, K. Havelund, and A. Biere. High-level data races. In International Workshop on Verification and Validation of Enterprise Information Systems, 2003.
[3]
P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987.
[4]
R. L. Bocchino, Jr., V. S. Adve, D. Dig, S. Adve, S. Heumann, R. Komuravelli, J. Overbey, P. Simmons, H. Sung, and M. Vakilian. A type and effect system for Deterministic Parallel Java. Technical Report UIUCDCS-R-2009-3032, Department of Computer Science, University of Illinois at Urbana-Champaign, 2009.
[5]
CERN. Colt 1.2.0. Available from http://dsd.lbl.gov/~hoschek/colt/, 2007.
[6]
F. Chen, T. F. Şerbănuţă, and G. Roşu. jPredictor: a predictive runtime analysis tool for Java. In International Conference on Software Engineering, 221--230. ACM, 2008.
[7]
Q. Chen, L. Wang, Z. Yang, and S. D. Stoller. HAVE: Integrated dynamic and static analysis for atomicity violations. In International Conference on Fundamental Approaches to Software Engineering (FASE), 2009.
[8]
O. Edelstein, E. Farchi, E. Goldin, Y. Nir, G. Ratsaby, and S. Ur. Framework for testing multi-threaded java programs. In Concurrency and Computation: Practice and Experience, volume 15, 2003.
[9]
T. Elmas, S. Qadeer, and S. Tasiran. Goldilocks: a race and transaction-aware Java runtime. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 245--255, 2007.
[10]
A. Farzan and P. Madhusudan. Causal atomicity. In Computer Aided Verification (CAV), 315--328, 2006.
[11]
A. Farzan and P. Madhusudan. Monitoring atomicity in concurrent programs. In Computer Aided Verification (CAV), 52--65, 2008.
[12]
A. Farzan and P. Madhusudan. The complexity of predicting atomicity violations. In Tools and Algorithms for the Construction and Analysis of Systems (TACAS), 2009.
[13]
C. Flanagan and S. N. Freund. Atomizer: A dynamic atomicity checker for multithreaded programs. In ACM SIGPLAN - SIGACT Symposium on Principles of Programming Languages (POPL), 256--267, 2004.
[14]
C. Flanagan and S. N. Freund. FastTrack: Efficient and precise dynamic race detection. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2009. To appear.
[15]
C. Flanagan, S. N. Freund, M. Lifshin, and S. Qadeer. Types for atomicity: Static checking and inference for Java. Transactions on Programming Languages and Systems, 30(4):1--53, 2008.
[16]
C. Flanagan, S. N. Freund, and S. Qadeer. Exploiting purity for atomicity. IEEE Transactions on Software Engineering, 31(4):275--291, 2005.
[17]
C. Flanagan, S. N. Freund, and J. Yi. Velodrome: A sound and complete dynamic atomicity checker for multithreaded programs. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2008.
[18]
C. Flanagan and S. Qadeer. A type and effect system for atomicity. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 338--349, 2003.
[19]
Java Grande Forum. Java Grande benchmark suite. http://www.javagrande.org, 2008.
[20]
R. J. Lipton. Reduction: A method of proving properties of parallel programs. Communications of the ACM, 18(12):717--721, 1975.
[21]
S. Lu, S. Park, E. Seo, and Y. Zhou. Learning from mistakes: a comprehensive study on real world concurrency bug characteristics. SIGPLAN Notices, 2008.
[22]
F. Mattern. Virtual time and global states of distributed systems. In International Workshop on Parallel and Distributed Algorithms. 1988.
[23]
R. H. B. Netzer and B. P. Miller. What are race conditions? Some issues and formalizations. ACM Letters on Programming Languages and Systems (LOPLAS), 1:74--88, 1992.
[24]
C.-S. Park and K. Sen. Randomized active atomicity violation detection in concurrent programs. In ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE), 135--145. ACM, 2008.
[25]
C. Sadowski, S. N. Freund, and C. Flanagan. SingleTrack: A dynamic determinism checker for multithreaded programs. In European Symposium on Programming (ESOP), 2009.
[26]
C. Sadowski and J. Yi. Tiddle: A trace description language for generating concurrent benchmarks to test dynamic analyses. In International Workshop on Dynamic Analysis (WODA), 2009. To appear.
[27]
A. Sasturkar, R. Agarwal, L. Wang, and S. D. Stoller. Automated type-based analysis of data races and atomicity. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 83--94, 2005.
[28]
SPEC. Standard Performance Evaluation Corporation JBB2000 Benchmark. http://www.spec.org/osg/jbb2000/, 2000.
[29]
M. Vaziri, F. Tip, and J. Dolby. Associating synchronization constraints with data in an object-oriented language. In ACM SIGPLAN - SIGACT Symposium on Principles of Programming Languages (POPL), 334--345, 2006.
[30]
C. von Praun and T. Gross. Static conflict analysis for multi-threaded object-oriented programs. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 115--128, 2003.
[31]
L. Wang and S. D. Stoller. Runtime analysis for atomicity. In International Workshop on Runtime Verification (RV), 2003.
[32]
L. Wang and S. D. Stoller. Static analysis of atomicity for programs with non-blocking synchronization. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 61--71, 2005.
[33]
L. Wang and S. D. Stoller. Accurate and efficient runtime detection of atomicity errors in concurrent programs. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 137--146, 2006.
[34]
L. Wang and S. D. Stoller. Runtime analysis of atomicity for multithreaded programs. IEEE Transactions on Software Engineering, 32:93--110, Feb. 2006.

Cited By

View all
  • (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
  • (2023)Race Condition Error Detection in a Program Executed on a Device with Limited Memory ResourcesDistributed Computing and Artificial Intelligence, Special Sessions, 19th International Conference10.1007/978-3-031-23210-7_2(13-20)Online publication date: 22-Feb-2023
  • (2018)A Method for Predicting Two-Variable Atomicity Violations2018 IEEE International Conference on Software Quality, Reliability and Security (QRS)10.1109/QRS.2018.00024(103-110)Online publication date: Jul-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PADTAD '09: Proceedings of the 7th Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging
July 2009
99 pages
ISBN:9781605586557
DOI:10.1145/1639622
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: 19 July 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. atomicity
  2. dynamic analysis
  3. serializability

Qualifiers

  • Research-article

Conference

ISSTA '09

Upcoming Conference

ISSTA '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 23 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (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
  • (2023)Race Condition Error Detection in a Program Executed on a Device with Limited Memory ResourcesDistributed Computing and Artificial Intelligence, Special Sessions, 19th International Conference10.1007/978-3-031-23210-7_2(13-20)Online publication date: 22-Feb-2023
  • (2018)A Method for Predicting Two-Variable Atomicity Violations2018 IEEE International Conference on Software Quality, Reliability and Security (QRS)10.1109/QRS.2018.00024(103-110)Online publication date: Jul-2018
  • (2017)Verifying Concurrent Programs Using Contracts2017 IEEE International Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST.2017.25(196-206)Online publication date: Mar-2017
  • (2015)AtomChaseProceedings of the 2015 IEEE 26th International Symposium on Software Reliability Engineering (ISSRE)10.1109/ISSRE.2015.7381795(12-23)Online publication date: 2-Nov-2015
  • (2015)A Method for Improving the Precision and Coverage of Atomicity Violation PredictionsProceedings of the 21st International Conference on Tools and Algorithms for the Construction and Analysis of Systems - Volume 903510.1007/978-3-662-46681-0_8(116-130)Online publication date: 11-Apr-2015
  • (2014)Generating effective tests for concurrent programs via AI automated planning techniquesInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-013-0277-y16:1(49-65)Online publication date: 1-Feb-2014
  • (2013)ConMemACM Transactions on Software Engineering and Methodology10.1145/2430545.243054622:2(1-33)Online publication date: 1-Mar-2013
  • (2012)Predicting null-pointer dereferences in concurrent programsProceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering10.1145/2393596.2393651(1-11)Online publication date: 11-Nov-2012
  • (2012)DTAMProceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering10.1145/2393596.2393650(1-11)Online publication date: 11-Nov-2012
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media