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

research-article

Public Access

Data race detection on compressed traces

Authors:

Mahesh ViswanathanAuthors Info & Claims

ESEC/FSE 2018: Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering

Pages 26 - 37

https://doi.org/10.1145/3236024.3236025

Published: 26 October 2018 Publication History

Abstract

We consider the problem of detecting data races in program traces that have been compressed using straight line programs (SLP), which are special context-free grammars that generate exactly one string, namely the trace that they represent. We consider two classical approaches to race detection --- using the happens-before relation and the lockset discipline. We present algorithms for both these methods that run in time that is linear in the size of the compressed, SLP representation. Typical program executions almost always exhibit patterns that lead to significant compression. Thus, our algorithms are expected to result in large speedups when compared with analyzing the uncompressed trace. Our experimental evaluation of these new algorithms on standard benchmarks confirms this observation.

References

[1]

2017. RV-Predict, Runtime Verification. https://runtimeverification.com/predict/. Accessed: 2017-11-01. 2017. Sequitur: Inferring Hierarchies From Sequences. http://www.sequitur.info/. Accessed: 2017-08-01. 2018. RAPID: Dynamic Analysis for Concurrent Programs. https://github.com/ umangm/rapid. Accessed: July 30, 2018. 2018. ZipTrack: Race Detection on Compressed Traces. https://github.com/ umangm/ziptrack. Accessed: July 30, 2018.

[2]

M. Abadi, C. Flanagan, and S.N. Freund. 2006. Types for safe locking: Static race detection for Java. ACM Transactions on Programming Languages and Systems 28, 2 (2006), 207–255.

Digital Library

[3]

J.L. Balcázar. 1996. The complexity of searching implicit graphs. Artificial Intelligence 86, 1 (1996), 171–188.

Digital Library

[4]

Swarnendu Biswas, Jipeng Huang, Aritra Sengupta, and Michael D. Bond. 2014. DoubleChecker: Efficient Sound and Precise Atomicity Checking. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation. 28–39.

Digital Library

[5]

S.M. Blackburn, R. Garner, C. Hoffmann, A.M. Khang, K.S. McKinley, R. Bentzur, A. Diwan, D. Feinberg, D. Frmpton, S.Z. Guyer, M. Hirzel, A. Hosking, M. Jump, H. Lee, J.E.B. Moss, A. Phansalkar, D. Stefanović, T. VanDrunen, D von Dincklage, and B. Wiedermann. 2006. The DaCapo Benchmarks: Java Benchmarking Development and Analysis. In Proceedings of the ACM SIGPLA Conference on Object-Oriented Programming Systems, Languages, and Applications. 169–190.

Digital Library

[6]

C. Boyapati, R. Lee, and M. Rinard. 2002. Ownership types for safe programming: Preventing data races and deadlocks. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming Systems, Lanaguages, and Applications. 211–230.

Digital Library

[7]

G.-I. Cheng, M. Feng, C.E. Leiserson, K.H. Randall, and A.F. Stark. 1998. Detecting Data Races in Cilk Programs That Use Locks. In Proceedings of the ACM Symposium on Parallel Algorithms and Architectures. 298–309.

Digital Library

[8]

B. Das, P. Scharpfenecker, and J. Torán. 2014. Succinct encodings of graph isomorphism. In Proceedings of the Internation Conference on Languages and Automata Theory and Applications. 285–296.

Digital Library

[9]

T. Elmas, S. Qadeer, and S. Tasiran. 2007. Goldilocks: A Race and Transactionaware Java Runtime. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 245–255.

Digital Library

[10]

D. Engler and K. Ashcraft. 2003. RacerX: Effective, static detection of race conditions and deadlocks. In Proceedings of the ACM Symposium on Operating Systems Principles. 237–252.

Digital Library

[11]

M. Eslamimehr and J. Palsberg. 2014. Sherlock: Scalable deadlock detection for concurrent programs. In Proceedings of the ACM SIGSOFT International Symposium on Foundations of Software Engineering. 353–365.

Digital Library

[12]

E. Farchi, Y. Nir, and S. Ur. 2003. Concurrent Bug Patterns and How to Test Them. In Proceedings of the International Symposium on Parallel and Distributed Processing.

Digital Library

[13]

J. Feigenbaum, S. Kannan, M.Y. Vardi, and M. Viswanathan. 1998. Complexity of Problems on Graphs Represented as OBDDs. In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science. 216–226.

Digital Library

[14]

M. Feng and C.E. Leiserson. 1997. Efficient Detection of Determinacy Races in Cilk Programs. In Proceedings of the ACM Symposium on Parallel Algorithms and Architectures. 1–11.

Digital Library

[15]

C.J. Fidge. 1988. Timestamps in message-passing systems that preserve the partial ordering. In Proceedings of the Australian Computer Science Conference. 56–66.

[16]

C. Flanagan and S.N. Freund. 2000. Type-based race detection for Java. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 219–232.

Digital Library

[17]

C. Flanagan and S.N. Freund. 2009. FastTrack: Efficient and Precise Dynamic Race Detection. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 121–133.

Digital Library

[18]

C. Flanagan and S.N. Freund. 2010. The RoadRunner Dynamic Analysis Framework for Concurrent Programs. In Proceedings of the SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering. 1–8.

Digital Library

[19]

Cormac Flanagan, Stephen N. Freund, and Jaeheon Yi. 2008. Velodrome: A Sound and Complete Dynamic Atomicity Checker for Multithreaded Programs. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation. 293–303.

Digital Library

[20]

H. Galperin and A. Wigderson. 1983. Succinct Representations of Graphs. Information and Control 56, 3 (1983), 183–198.

Digital Library

[21]

J. Huang, P.O. Meredith, and G. Rosu. 2014. Maximal sound predictive race detection with control flow abstraction. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 337–348.

Digital Library

[22]

J. Huang and A.K. Rajagopalan. 2016. Precise and maximal race detection from incomplete traces. In Proceedings of the ACM SIGPLAN International Conference on Object-oriented Programming, Systems, Languages, and Applications. 462–476.

Digital Library

[23]

S.F. Kaplan, Y. Smaragdakis, and P.R. Wilson. 2003. Flexible reference trace reduction for VM simulations. ACM Transactions on Modeling and Computer Simulation 13, 1 (2003), 1–38.

Digital Library

[24]

J.C. Kieffer and E.-H. Yang. 2000. Grammar-based codes: a new class of universal lossless source codes. IEEE Transactions on Information Theory 46, 3 (2000), 737–754.

Digital Library

[25]

J.C. Kieffer, E.-H. Yang, G.J. Nelson, and P. Cosman. 2000. Universal lossless compression via multilevel pattern matching. IEEE Transactions on Information Theory 46, 4 (2000), 1227–1245.

Digital Library

[26]

D. Kini, U. Mathur, and M. Viswanathan. 2017. Dynamic Race Prediction in Linear Time. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 157–170.

Digital Library

[27]

Dileep Kini, Umang Mathur, and Mahesh Viswanathan. 2018. Data Race Detection on Compressed Traces. CoRR abs/1807.08427 (2018). http://arxiv.org/abs/1807.

[28]

08427

[29]

A. Kinneer, M.B. Dwyer, and G. Rothermel. 2007. Sofya: Supporting Rapid Development of Dynamic Program Analyses for Java. In Companion to the Proceedings of the 29th International Conference on Software Engineering. 51–52.

Digital Library

[30]

L. Lamport. 1978. Time, Clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (1978), 558–565.

Digital Library

[31]

N.J. Larsson and A. Moffat. 2000. Off-line dictionary-based compression. Proc. IEEE 88, 11 (2000), 1722–1732.

[32]

P. Liu, O. Tripp, and X. Zhang. 2016. IPA: Improving Predictive Analysis with Pointer Analysis. In Proceedings of the International Symposium on Software Testing and Analysis. 59–69.

Digital Library

[33]

A. Lozano and J.L. Balcázar. 1986. The complexity of graph problems for succinctly represented graphs. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science. 277–286.

Digital Library

[34]

F. Mattern. 1988. Virtual time and Global states of distributed systems. In Proceedings of the International Workshop on Parallel and Distributed Algorithms. 215–226.

[35]

A. Milenković and M. Milenković. 2007. An Efficient Single-Pass Trace Compression Technique Utilizing Instruction Streams. ACM Transactions on Modeling and Computer Simulation 17, 1 (2007).

Digital Library

[36]

M. Musuvathi, S. Qadeer, T. Ball, G. Basler, P.A. Nainar, and I. Neamtiu. 2008. Finding and Reproducing Heisenbugs in Concurrent Programs. In Proceedings of the USENIX Conference on Operating Systems Design and Implementation. 267–280.

Digital Library

[37]

M. Naik, A. Aiken, and J. Whaley. 2006. Effective static race detection for Java. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 308–319.

Digital Library

[38]

C.G. Nevill-Manning. 1996. Inferring Sequential Structure. Ph.D. Dissertation. University of Waikato.

[39]

C.G. Nevill-Manning and I.H. Witten. 1997. Identifying hierarchical structure in sequences: A linear time algorithm. Journal of Artificial Intelligence 7 (1997), 67–82.

Digital Library

[40]

C.H. Papadimitriou and M. Yannakakis. 1986. A note on succinct representations of graphs. Information and Control 71, 3 (1986), 181–185.

Digital Library

[41]

E. Pozniansky and A. Schuster. 2003. Efficient On-the-fly Data Race Detection in Multithreaded C++ Programs. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 179–190.

Digital Library

[42]

P. Pratikakis, J.S. Foster, and M. Hicks. 2011. LOCKSMITH: Practical static race detection for C. ACM Transactions on Programming Languages and Systems 33, 1 (2011), 3:1–3:55.

Digital Library

[43]

C.v. Praun and T.R. Gross. 2001. Object race detection. In Proceedings of the ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications. 70–82.

Digital Library

[44]

C. Ra

[45]

R. Raman, J. Zhao, V. Sarkar, M. Vechev, and E. Yahav. 2012. Scalable and Precise Dynamic Datarace Detection for Structured Parallelism. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 531–542.

Digital Library

[46]

M. Said, C. Wang, Z. Yang, and K. Sakallah. 2011. Generating Data Race Witnesses by an SMT-based Analysis. In Proceedings of the International Conference on NASA Formal Methods. 313–327.

Digital Library

[47]

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. 1997. Eraser: A dynamic data race detector for multi-threaded programs. In Proceedings of the ACM Symposium on Operating Systems Principles. 27–37.

Digital Library

[48]

K. Sen. 2008. Race directed random testing of concurrent programs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 11–21.

Digital Library

[49]

Y. Smaragdakis, J. Evans, C. Sadowski, J. Yi, and C. Flanagan. 2012. Sound Predictive Race Detection in Polynomial Time. In Proceedings of the ACM SIGPLANSIGACT Symposium on Principles of Programming Languages. 387–400.

Digital Library

[50]

L.A. Smith, J.M. Bull, and J. Obdrzálek. 2001. A Parallel Java Grande benchmark suite. In Proceedings of the ACM/IEEE Conference on Supercomputing. 8–8.

Digital Library

[51]

R. Surendran and V. Sarkar. 2016. Dynamic determinacy race detection for task parallelism with futures. In Proceedings of the International Conference on Runtime Verification. 368–385. ESEC/FSE ’18, November 4–9, 2018, Lake Buena Vista, FL, USA Dileep Kini, Umang Mathur, and Mahesh Viswanathan

[52]

H. Veith. 1996. Succinct Representation, Leaf Languages, and Projection Reductions. In Proceedings of the IEEE Conference on Computational Complexity. 118–126.

Digital Library

[53]

J.W. Voung, R. Jhala, and S. Lerner. 2007. RELAY: Static race detection on millions of lines of code. In Proceedings of the ACM SIGSOFT International Symposium on Foundations of Software Engineering. 205–214.

Digital Library

[54]

C. Wang, S. Kundu, M. Ganai, and A. Gupta. 2009. Symbolic Predictive Analysis for Concurrent Programs. In Proceedings of the World Congress on Formal Methods. 256–272.

Digital Library

[55]

T.A. Welch. 1984. A Technique for High-Performance Data Compression. Computer 17, 6 (1984), 8–19.

Digital Library

[56]

E. Yahav. 2001. Verifying Safety Properties of Concurrent Java Programs Using 3-valued Logic. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 27–40.

Digital Library

[57]

En-Hui Yang and J. C. Kieffer. 2000. Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. I. Without context models. IEEE Transactions on Information Theory 46, 3 (2000), 755–777.

Digital Library

[58]

A. Yoga, S. Nagarakatte, and A. Gupta. 2016. Parallel Data Race Detection for Task Parallel Programs with Locks. In Proceedings of the ACM SIGSOFT International Symposium on Foundations of Software Engineering. 833–845.

Digital Library

[59]

S. Zhan and J. Huang. 2016. ECHO: Instantaneous in situ race detection in the IDE. In Proceedings of the ACM SIGSOFT International Symposium on Foundations of Software Engineering. 775–786.

Digital Library

Cited By

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
Farzan AMathur U(2024)Coarser Equivalences for Causal ConcurrencyProceedings of the ACM on Programming Languages10.1145/36328738:POPL(911-941)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632873
Thokair MZhang MMathur UViswanathan M(2023)Dynamic Race Detection with O(1) SamplesProceedings of the ACM on Programming Languages10.1145/35712387:POPL(1308-1337)Online publication date: 9-Jan-2023
https://dl.acm.org/doi/10.1145/3571238
Show More Cited By

Index Terms

Data race detection on compressed traces
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Formal software verification
      2. Software defect analysis
        Software testing and debugging

Recommendations

Dynamic Race Detection with O(1) Samples

Happens before-based dynamic analysis is the go-to technique for detecting data races in large scale software projects due to the absence of false positive reports. However, such analyses are expensive since they employ expensive vector clock updates at ...
What happens-after the first race? enhancing the predictive power of happens-before based dynamic race detection

Dynamic race detection is the problem of determining if an observed program execution reveals the presence of a data race in a program. The classical approach to solving this problem is to detect if there is a pair of conflicting memory accesses that are ...
Sound predictive race detection in polynomial time
POPL '12: Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Data races are among the most reliable indicators of programming errors in concurrent software. For at least two decades, Lamport's happens-before (HB) relation has served as the standard test for detecting races--other techniques, such as lockset-based ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ESEC/FSE 2018: Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering

October 2018

987 pages

ISBN:9781450355735

DOI:10.1145/3236024

General Chair:
Gary T. Leavens
University of Central Florida, USA
,
Program Chairs:
Alessandro Garcia
PUC-Rio, Brazil
,
Corina S. Păsăreanu
NASA Ames Research Center, USA

Copyright © 2018 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 the author(s) 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: 26 October 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

ESEC/FSE '18

Sponsor:

SIGSOFT

ESEC/FSE '18: 26th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering

November 4 - 9, 2018

FL, Lake Buena Vista, USA

Acceptance Rates

Overall Acceptance Rate 112 of 543 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
555
Total Downloads

Downloads (Last 12 months)87
Downloads (Last 6 weeks)11

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

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
Farzan AMathur U(2024)Coarser Equivalences for Causal ConcurrencyProceedings of the ACM on Programming Languages10.1145/36328738:POPL(911-941)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632873
Thokair MZhang MMathur UViswanathan M(2023)Dynamic Race Detection with O(1) SamplesProceedings of the ACM on Programming Languages10.1145/35712387:POPL(1308-1337)Online publication date: 9-Jan-2023
https://dl.acm.org/doi/10.1145/3571238
Zhu SGuo YZhang LCai YGrundy JPollock LPenta M(2023)Tolerate Control-Flow Changes for Sound Data Race PredictionProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00118(1342-1354)Online publication date: 14-May-2023
https://dl.acm.org/doi/10.1109/ICSE48619.2023.00118
Huang YWang TYin ZMercer EOgles B(2022)Improving the Efficiency of Deadlock Detection in MPI Programs through Trace CompressionIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.3218346(1-16)Online publication date: 2022
https://doi.org/10.1109/TPDS.2022.3218346
Navarro GOlivares FUrbina C(2022)Balancing Run-Length Straight-Line ProgramsString Processing and Information Retrieval10.1007/978-3-031-20643-6_9(117-131)Online publication date: 1-Nov-2022
https://doi.org/10.1007/978-3-031-20643-6_9
Zhang MMathur UViswanathan MSpinellis DGousios GChechik MDi Penta M(2021)Checking LTL[F,G,X] on compressed traces in polynomial timeProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468557(131-143)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468557
Mathur UViswanathan MLarus JCeze LStrauss K(2020)Atomicity Checking in Linear Time using Vector ClocksProceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3373376.3378475(183-199)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.1145/3373376.3378475
Bo LJiang SQian JWang RYao Y(2019)Performance Evaluation of Data Race Detection Based on Thread Sharing Analysis With Different Granularities: An Empirical StudyIEEE Access10.1109/ACCESS.2019.29209477(73819-73829)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2920947
Nakade RMercer EAldous PStorey KOgles BHooker JPowell SMcCarthy J(2019)Model-checking task-parallel programs for data-raceInnovations in Systems and Software Engineering10.1007/s11334-019-00343-5Online publication date: 18-May-2019
https://doi.org/10.1007/s11334-019-00343-5

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten