Document Open Access Logo

Dynamic Data-Race Detection Through the Fine-Grained Lens

Authors Rucha Kulkarni , Umang Mathur , Andreas Pavlogiannis

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2021.16.pdf
  • Filesize: 1.07 MB
  • 23 pages

Document Identifiers

Author Details

Rucha Kulkarni
  • University of Illinois at Urbana-Champaign, IL, USA
Umang Mathur
  • University of Illinois at Urbana-Champaign, IL, USA
Andreas Pavlogiannis
  • Aarhus University, Denmark

Funding

  • Mathur, Umang: partially funded by a Google PhD Fellowship and by the Simons Institute for the Theory of Computing.

Cite AsGet BibTex

Rucha Kulkarni, Umang Mathur, and Andreas Pavlogiannis. Dynamic Data-Race Detection Through the Fine-Grained Lens. In 32nd International Conference on Concurrency Theory (CONCUR 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 203, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik (2021)
https://doi.org/10.4230/LIPIcs.CONCUR.2021.16

Abstract

Data races are among the most common bugs in concurrency. The standard approach to data-race detection is via dynamic analyses, which work over executions of concurrent programs, instead of the program source code. The rich literature on the topic has created various notions of dynamic data races, which are known to be detected efficiently when certain parameters (e.g., number of threads) are small. However, the fine-grained complexity of all these notions of races has remained elusive, making it impossible to characterize their trade-offs between precision and efficiency. In this work we establish several fine-grained separations between many popular notions of dynamic data races. The input is an execution trace Οƒ with 𝒩 events, 𝒯 threads and β„’ locks. Our main results are as follows. First, we show that happens-before HB races can be detected in O(𝒩⋅ min(𝒯, β„’)) time, improving over the standard O(𝒩⋅ 𝒯) bound when β„’ = o(𝒯). Moreover, we show that even reporting an HB race that involves a read access is hard for 2-orthogonal vectors (2-OV). This is the first rigorous proof of the conjectured quadratic lower-bound in detecting HB races. Second, we show that the recently introduced synchronization-preserving races are hard to detect for 3-OV and thus have a cubic lower bound, when 𝒯 = Ξ©(𝒩). This establishes a complexity separation from HB races which are known to be strictly less expressive. Third, we show that lock-cover races are hard for 2-OV, and thus have a quadratic lower-bound, even when 𝒯 = 2 and β„’ = Ο‰(log 𝒩). The similar notion of lock-set races is known to be detectable in O(𝒩⋅ β„’) time, and thus we achieve a complexity separation between the two. Moreover, we show that lock-set races become hitting-set (HS)-hard when β„’ = Θ(𝒩), and thus also have a quadratic lower bound, when the input is sufficiently complex. To our knowledge, this is the first work that characterizes the complexity of well-established dynamic race-detection techniques, allowing for a rigorous comparison between them.

Subject Classification

ACM Subject Classification
  • Software and its engineering β†’ Software testing and debugging
  • Theory of computation β†’ Parameterized complexity and exact algorithms
Keywords
  • dynamic analyses
  • data races
  • fine-grained complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Helgrind: a thread error detector. Accessed: 2021-04-30. URL: https://valgrind.org/docs/manual/hg-manual.html.
  2. Intel inspector. Accessed: 2021-04-30. URL: https://software.intel.com/content/www/us/en/develop/tools/oneapi/components/inspector.html.
  3. Amir Abboud, Virginia Vassilevska Williams, and Joshua Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, page 377–391, USA, 2016. Society for Industrial and Applied Mathematics. Google Scholar
  4. Utpal Banerjee, Brian Bliss, Zhiqiang Ma, and Paul Petersen. A theory of data race detection. In Proceedings of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging, PADTAD '06, pages 69-78, New York, NY, USA, 2006. ACM. URL: https://doi.org/10.1145/1147403.1147416.
  5. Hans-J. Boehm. How to miscompile programs with β€œbenign” data races. In Proceedings of the 3rd USENIX Conference on Hot Topic in Parallelism, HotPar’11, page 3, USA, 2011. USENIX Association. Google Scholar
  6. Hans-J. Boehm. Position paper: Nondeterminism is unavoidable, but data races are pure evil. In Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability, RACES ’12, page 9–14, New York, NY, USA, 2012. Association for Computing Machinery. URL: https://doi.org/10.1145/2414729.2414732.
  7. Hans-J. Boehm and Sarita V. Adve. Foundations of the C++ Concurrency Memory Model. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '08, page 68–78, New York, NY, USA, 2008. Association for Computing Machinery. URL: https://doi.org/10.1145/1375581.1375591.
  8. Karl Bringmann. Fine-Grained Complexity Theory (Tutorial). In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1-4:7, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.4.
  9. Marco L Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 261-270, 2016. Google Scholar
  10. Bernadette Charron-Bost. Concerning the size of logical clocks in distributed systems. Information Processing Letters, 39(1):11-16, 1991. URL: https://doi.org/10.1016/0020-0190(91)90055-M.
  11. Peter Chini, Jonathan Kolberg, Andreas Krebs, Roland Meyer, and Prakash Saivasan. On the Complexity of Bounded Context Switching. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms (ESA 2017), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1-27:15, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.27.
  12. Peter Chini, Roland Meyer, and Prakash Saivasan. Fine-grained complexity of safety verification. In Dirk Beyer and Marieke Huisman, editors, Tools and Algorithms for the Construction and Analysis of Systems, pages 20-37, Cham, 2018. Springer International Publishing. Google Scholar
  13. Peter Chini and Prakash Saivasan. A Framework for Consistency Algorithms. In Nitin Saxena and Sunil Simon, editors, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020), volume 182 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1-42:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum fΓΌr Informatik. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2020.42.
  14. Anne Dinning and Edith Schonberg. Detecting access anomalies in programs with critical sections. In Proceedings of the 1991 ACM/ONR Workshop on Parallel and Distributed Debugging, PADD '91, pages 85-96, New York, NY, USA, 1991. ACM. URL: https://doi.org/10.1145/122759.122767.
  15. Tayfun Elmas, Shaz Qadeer, and Serdar Tasiran. Goldilocks: A race and transaction-aware java runtime. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '07, pages 245-255, New York, NY, USA, 2007. ACM. URL: https://doi.org/10.1145/1250734.1250762.
  16. Cormac Flanagan and Stephen N. Freund. Fasttrack: Efficient and precise dynamic race detection. In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '09, pages 121-133, New York, NY, USA, 2009. ACM. URL: https://doi.org/10.1145/1542476.1542490.
  17. Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams. Completeness for first-order properties on sparse structures with algorithmic applications. ACM Trans. Algorithms, 15(2), December 2018. URL: https://doi.org/10.1145/3196275.
  18. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  19. Ayal Itzkovitz, Assaf Schuster, and Oren Zeev-Ben-Mordehai. Toward integration of data race detection in dsm systems. J. Parallel Distrib. Comput., 59(2):180-203, November 1999. URL: https://doi.org/10.1006/jpdc.1999.1574.
  20. Baris Kasikci, Cristian Zamfir, and George Candea. Racemob: Crowdsourced data race detection. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP ’13, page 406–422, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2517349.2522736.
  21. Dileep Kini, Umang Mathur, and Mahesh Viswanathan. Dynamic race prediction in linear time. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017, pages 157-170, New York, NY, USA, 2017. ACM. URL: https://doi.org/10.1145/3062341.3062374.
  22. Rucha Kulkarni, Umang Mathur, and Andreas Pavlogiannis. Dynamic data-race detection through the fine-grained lens, 2021. URL: http://arxiv.org/abs/2107.03569.
  23. Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558-565, 1978. URL: https://doi.org/10.1145/359545.359563.
  24. Umang Mathur, Dileep Kini, and Mahesh Viswanathan. What happens-after the first race? enhancing the predictive power of happens-before based dynamic race detection. Proc. ACM Program. Lang., 2(OOPSLA):145:1-145:29, October 2018. URL: https://doi.org/10.1145/3276515.
  25. Umang Mathur, Andreas Pavlogiannis, and Mahesh Viswanathan. The complexity of dynamic data race prediction. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’20, page 713–727, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3373718.3394783.
  26. Umang Mathur, Andreas Pavlogiannis, and Mahesh Viswanathan. Optimal prediction of synchronization-preserving races. Proc. ACM Program. Lang., 5(POPL), January 2021. URL: https://doi.org/10.1145/3434317.
  27. Satish Narayanasamy, Zhenghao Wang, Jordan Tigani, Andrew Edwards, and Brad Calder. Automatically classifying benign and harmful data races using replay analysis. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’07, page 22–31, New York, NY, USA, 2007. Association for Computing Machinery. URL: https://doi.org/10.1145/1250734.1250738.
  28. Robert O'Callahan and Jong-Deok Choi. Hybrid dynamic data race detection. SIGPLAN Not., 38(10):167-178, June 2003. URL: https://doi.org/10.1145/966049.781528.
  29. Andreas Pavlogiannis. Fast, sound, and effectively complete dynamic race prediction. Proc. ACM Program. Lang., 4(POPL), 2019. URL: https://doi.org/10.1145/3371085.
  30. Eli Pozniansky and Assaf Schuster. Efficient on-the-fly data race detection in multithreaded C++ programs. SIGPLAN Not., 38(10):179-190, 2003. URL: https://doi.org/10.1145/966049.781529.
  31. Jake Roemer, Kaan Genç, and Michael D. Bond. High-coverage, unbounded sound predictive race detection. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018, pages 374-389, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3192366.3192385.
  32. Grigore Rosu. Rv-predict, runtime verification, 2018. URL: https://runtimeverification.com/predict.
  33. Mahmoud Said, Chao Wang, Zijiang Yang, and Karem Sakallah. Generating data race witnesses by an smt-based analysis. In Proceedings of the Third International Conference on NASA Formal Methods, NFM'11, pages 313-327, Berlin, Heidelberg, 2011. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=1986308.1986334.
  34. Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst., 15(4):391-411, 1997. URL: https://doi.org/10.1145/265924.265927.
  35. Koushik Sen, Grigore Roşu, and Gul Agha. Detecting errors in multithreaded programs by generalized predictive analysis of executions. In Martin Steffen and Gianluigi Zavattaro, editors, Formal Methods for Open Object-Based Distributed Systems, pages 211-226, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  36. Konstantin Serebryany and Timur Iskhodzhanov. ThreadSanitizer: Data Race Detection in Practice. In WBIA '09: Proceedings of the Workshop on Binary Instrumentation and Applications, 2009. Google Scholar
  37. Jaroslav Ševčík and David Aspinall. On validity of program transformations in the java memory model. In Jan Vitek, editor, ECOOP 2008 - Object-Oriented Programming, pages 27-51, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  38. Yannis Smaragdakis, Jacob Evans, Caitlin Sadowski, Jaeheon Yi, and Cormac Flanagan. Sound predictive race detection in polynomial time. In Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '12, pages 387-400, New York, NY, USA, 2012. ACM. URL: https://doi.org/10.1145/2103656.2103702.
  39. Martin Sulzmann and Kai StadtmΓΌller. Efficient, near complete, and often sound hybrid dynamic data race prediction. In Proceedings of the 17th International Conference on Managed Programming Languages and Runtimes, MPLR 2020, page 30–51, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3426182.3426185.
  40. Christoph von Praun. Race Detection Techniques, pages 1697-1706. Springer US, Boston, MA, 2011. URL: https://doi.org/10.1007/978-0-387-09766-4_38.
  41. Jaroslav Ε evčík. Safe optimisations for shared-memory concurrent programs. SIGPLAN Not., 46(6):306–316, June 2011. URL: https://doi.org/10.1145/1993316.1993534.
  42. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2-3):357-365, 2005. Google Scholar
  43. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the ICM, volume 3, pages 3431-3472. World Scientific, 2018. Google Scholar
  44. M. Zhivich and R. K. Cunningham. The real cost of software errors. IEEE Security and Privacy, 7(2):87–90, March 2009. URL: https://doi.org/10.1109/MSP.2009.56.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact