research-article

SherLock: unsupervised synchronization-operation inference

Authors:

Madanlal Musuvathi,

Suman NathAuthors Info & Claims

ASPLOS '21: Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems

Pages 314 - 328

https://doi.org/10.1145/3445814.3446754

Published: 17 April 2021 Publication History

Abstract

Synchronizations are fundamental to the correctness and performance of concurrent software. Unfortunately, correctly identifying all synchronizations has become extremely difficult in modern soft-ware systems due to the various types of synchronizations. Previous work either only infers specific type of synchronization by code analysis or relies on manual effort to annotate the synchronization. This paper proposes SherLock, a tool that uses unsupervised inference to identify synchronizations. SherLock leverages the fact that most synchronizations appear around the conflicting operations and form it into a linear system with a set of synchronization proper-ties and hypotheses. To collect enough observations, SherLock runs the unit tests a small number of times with feedback-based delay injection. We applied SherLock on 8 C# open-source applications. Without any prior knowledge, SherLock inferred 122 unique synchronizations, with few false positives. These inferred synchronizations cover a wide variety of types, including lock operations, fork-join operations, asynchronous operations, framework synchronization, and custom synchronization.

References

[1]

Building async coordination primitives. https://devblogs.microsoft.com/pfxteam. Accessed: 2021-1-1.

[2]

Flipy : linear solver. https://pypi.org/project/flipy/. Accessed: 2020-8-9.

[3]

Ibm thread and monitor dump analyze for java. https://www.ibm.com/support/pages/ibm-thread-and-monitor-dump-analyzerjava-tmda. Accessed: 2020-8-9.

[4]

Microsoft tsvd. https://github.com/microsoft/TSVD. Accessed: 2020-8-9.

[5]

Mono.cecil. https://www.mono-project.com/docs/tools+libraries/libraries/Mono. Cecil/. Accessed: 2020-8-9.

[6]

Overview of synchronization primitives. https://docs.microsoft.com/en-us/ dotnet/standard/threading/overview-of-synchronization-primitives. Accessed: 2020-8-9.

[7]

Sarita V Adve and Mark D Hill. Weak ordering-a new definition. ACM SIGARCH Computer Architecture News, 18 (2SI): 2-14, 1990.

Digital Library

[8]

Mohammad Mejbah Ul Alam, Tongping Liu, Guangming Zeng, and Abdullah Muzahid. Syncperf: Categorizing, detecting, and diagnosing synchronization performance bugs. In Gustavo Alonso, Ricardo Bianchini, and Marko Vukolic, editors, EuroSys, 2017.

[9]

Sebastian Burckhardt, Pravesh Kothari, Madanlal Musuvathi, and Santosh Nagarakatte. A randomized scheduler with probabilistic guarantees of finding bugs. In ASPLOS, 2010.

Digital Library

[10]

Feng Chen, Traian-Florin Serbanuta, and Grigore Rosu. jpredictor: a predictive runtime analysis tool for java. In Wilhelm Schäfer, Matthew B. Dwyer, and Volker Gruhn, editors, ICSE, 2008.

[11]

Xu Chen, Ming Zhang, Zhuoqing Morley Mao, and Paramvir Bahl. Automating network application dependency discovery: Experiences, limitations, and new solutions. In OSDI, volume 8, pages 117-130, 2008.

Digital Library

[12]

Victor Chibotaru, Benjamin Bichsel, Veselin Raychev, and Martin Vechev. Scalable taint specification inference with big code. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 760-774, 2019.

Digital Library

[13]

Michael Chow, David Meisner, Jason Flinn, Daniel Peek, and Thomas F Wenisch. The mystery machine: End-to-end performance analysis of large-scale internet services. In 11th {USENIX} Symposium on Operating Systems Design and Implementation ({ OSDI} 14), pages 217-231, 2014.

[14]

Florian David, Gael Thomas, Julia Lawall, and Gilles Muller. Continuously measuring critical section pressure with the free-lunch profiler. ACM SIGPLAN Notices, 49 ( 10 ): 291-307, 2014.

[15]

Dawson Engler, David Yu Chen, Seth Hallem, Andy Chou, and Benjamin Chelf. Bugs as deviant behavior: A general approach to inferring errors in systems code. In SOSP, 2001.

Digital Library

[16]

Michael Ernst, Adam Czeisler, William G. Griswold, and David Notkin. Quickly detecting relevant program invariants. In ICSE, 2000.

[17]

Cormac Flanagan and Stephen N Freund. Fasttrack: eficient and precise dynamic race detection. ACM Sigplan Notices, 44 ( 6 ): 121-133, 2009.

[18]

Cormac Flanagan and Stephen N Freund. The fasttrack2 race detector. Technical report, Technical report, Williams College, 2017.

[19]

Sudheendra Hangal and Monica S. Lam. Tracking down software bugs using automatic anomaly detection. In ICSE, 2002.

[20]

Chun-Hung Hsiao, Satish Narayanasamy, Essam Muhammad Idris Khan, Cristiano L. Pereira, and Gilles A. Pokam. Asyncclock: Scalable inference of asynchronous event causality. In Yunji Chen, Olivier Temam, and John Carter, editors, ASPLOS, 2017.

[21]

Chun-Hung Hsiao, Cristiano Pereira, Jie Yu, Gilles Pokam, Satish Narayanasamy, Peter M. Chen, Ziyun Kong, and Jason Flinn. Race Detection for Event-Driven Mobile Applications. In PLDI, 2014.

Digital Library

[22]

Guoliang Jin, Linhai Song, Wei Zhang, Shan Lu, and Ben Liblit. Automated atomicity-violation fixing. In PLDI, 2011.

Digital Library

[23]

Guoliang Jin, Wei Zhang, Dongdong Deng, Ben Liblit, and Shan Lu. Automated concurrency-bug fixing. In OSDI, 2012.

Digital Library

[24]

Horatiu Jula, Daniel Tralamazza, Cristian Zamfir, and George Candea. Deadlock immunity: Enabling systems to defend against deadlocks. In OSDI, 2008.

Digital Library

[25]

Baris Kasikci, Cristian Zamfir, and George Candea. Data Races vs. Data Race Bugs: Telling the Diference with Portend. In ASPLOS, 2012.

[26]

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

[27]

Guangpu Li, Haopeng Liu, Xianglan Chen, Haryadi S Gunawi, and Shan Lu. Dfix: automatically fixing timing bugs in distributed systems. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 994-1009, 2019.

Digital Library

[28]

Guangpu Li, Shan Lu, Madanlal Musuvathi, Suman Nath, and Rohan Padhye. Eficient scalable thread-safety-violation detection. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, 2019.

Digital Library

[29]

Jiaxin Li, Yuxi Chen, Haopeng Liu, Shan Lu, Yiming Zhang, Haryadi S Gunawi, Xiaohui Gu, Xicheng Lu, and Dongsheng Li. Pcatch: automatically detecting performance cascading bugs in cloud systems. In Proceedings of the Thirteenth EuroSys Conference, pages 1-14, 2018.

[30]

Ben Liblit, Mayur Naik, Alice X. Zheng, Alexander Aiken, and Michael I. Jordan. Scalable statistical bug isolation. In PLDI, 2005.

Digital Library

[31]

Benjamin Livshits, Aditya V Nori, Sriram K Rajamani, and Anindya Banerjee. Merlin: specification inference for explicit information flow problems. ACM Sigplan Notices, 44 ( 6 ): 75-86, 2009.

[32]

Shan Lu, Joseph Tucek, Feng Qin, and Yuanyuan Zhou. AVIO: Detecting Atomicity Violations via Access Interleaving Invariants. In ASPLOS, 2006.

Digital Library

[33]

Brandon Lucia, Joseph Devietti, Karin Strauss, and Luis Ceze. Atom-Aid: Detecting and surviving atomicity violations. In ISCA, 2008.

[34]

Pallavi Maiya, Aditya Kanade, and Rupak Majumdar. Race Detection for Android Applications. In PLDI, 2014.

Digital Library

[35]

Boris Petrov, Martin T. Vechev, Manu Sridharan, and Julian Dolby. Race detection for web applications. In PLDI, 2012.

Digital Library

[36]

Siegfried Rasthofer, Steven Arzt, and Eric Bodden. A machine-learning approach for classifying and categorizing android sources and sinks. In NDSS, volume 14, page 1125. Citeseer, 2014.

[37]

Michiel Ronsse and Koenraad De Bosschere. Recplay : A fully integrated practical record/replay system. ACM Trans. Comput. Syst., 17 ( 2 ): 133-152, 1999.

[38]

Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM TOCS, 1997.

Digital Library

[39]

Aater M. Suleman, Onur Mutlu, Moinuddin K Qureshi, and Yale N. Patt. Accelerating critical section execution with asymmetric multi-core architectures. In ASPLOS '09, pages 253-264.

[40]

Chen Tian, Vijay Nagarajan, Rajiv Gupta, and Sriraman Tallam. Dynamic recognition of synchronization operations for improved data race detection. In ISSTA, 2008.

Digital Library

[41]

Kaushik Veeraraghavan, Dongyoon Lee, Benjamin Wester, Jessica Ouyang, Peter M. Chen, Jason Flinn, and Satish Narayanasamy. Doubleplay: Parallelizing sequential logging and replay. In ASPLOS, 2011.

Digital Library

[42]

Benjamin P. Wood, Luis Ceze, and Dan Grossman. Low-level detection of language-level data races with lard. In ASPLOS, 2014.

Digital Library

[43]

Weiwei Xiong, Soyeon Park, Jiaqi Zhang, Yuanyuan Zhou, and Zhiqiang Ma. Ad hoc synchronization considered harmful. In OSDI, 2010.

Digital Library

[44]

Yuan Yu, Tom Rodehefer, and Wei Chen. Racetrack: eficient detection of data race conditions via adaptive tracking. In Proceedings of the twentieth ACM symposium on Operating systems principles, pages 221-234, 2005.

Digital Library

[45]

Jiaqi Zhang, Weiwei Xiong, Yang Liu, Soyeon Park, Yuanyuan Zhou, and Zhiqiang Ma. Atdetector: improving the accuracy of a commercial data race detector by identifying address transfer. In Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture, pages 206-215, 2011.

Digital Library

[46]

Wei Zhang, Junghee Lim, Ramya Olichandran, Joel Scherpelz, Guoliang Jin, Shan Lu, and Thomas Reps. ConSeq: Detecting Concurrency Bugs through Sequential Errors. In ASPLOS, 2011.

Cited By

Li NGuo JHuang BLi YZhang YLi CHuang W(2024)TCSA: Efficient Localization of Busy-Wait Synchronization Bugs for Latency-Critical ApplicationsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.334257335:2(297-309)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TPDS.2023.3342573
Cai YYao PYe CZhang CCalandrino JTroncoso C(2023)Place your locks wellProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620446(3727-3744)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620446
Yu TJia CChen RLi CWang BJiang Y(2023)Precise Dynamic Data Race Prediction for Interrupt-Driven Embedded Software2023 IEEE 34th International Symposium on Software Reliability Engineering Workshops (ISSREW)10.1109/ISSREW60843.2023.00049(69-74)Online publication date: 9-Oct-2023
https://doi.org/10.1109/ISSREW60843.2023.00049
Show More Cited By

Index Terms

SherLock: unsupervised synchronization-operation inference
1. Computer systems organization
  1. Dependable and fault-tolerant systems and networks
    1. Reliability
2. Software and its engineering
  1. Software notations and tools
    1. Software maintenance tools

Recommendations

Performance of memory reclamation for lockless synchronization

Achieving high performance for concurrent applications on modern multiprocessors remains challenging. Many programmers avoid locking to improve performance, while others replace locks with non-blocking synchronization to protect against deadlock, ...
Brief Announcement: Extending Transactional Memory with Atomic Deferral
SPAA '17: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures

Atomic deferral is a language-level mechanism for transactional memory (TM) that enables programmers to move output and long-running operations out of a transaction's body without sacrificing serializability: the deferred operation appears to execute as ...
Semantics based synchronization in database systems

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPLOS '21: Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems

April 2021

1090 pages

ISBN:9781450383172

DOI:10.1145/3445814

General Chair:
Tim Sherwood
University of California at Santa Barbara, USA
,
Program Chairs:
Emery Berger
University of Massachusetts at Amherst, USA
,
Christos Kozyrakis
Stanford University, USA

Copyright © 2021 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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 April 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

CSR: Medium:Collaborative Research:Holistic,Cross-Site,Hybrid System Anomaly Debugging for Large Scale Hosting Infrastructures
CSR:Medium:DCRUGS:Combating Distributed Concurrency Bugs in Cloud Systems
FMitF: Collaborative Research: User-Centered Verification and Repair of Trigger-Action Programs
CNS Core: Medium: Accurate Anytime Learning for Energy and Timeliness in Software Systems
CSR:Medium:Understanding and Automatically Adjusting Performance Sensitive Software
BIGDATA: Collaborative Research: F: Holistic Optimization of Data-Driven Applications

Conference

ASPLOS '21

Sponsor:

SIGPLAN

ASPLOS '21: 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems

April 19 - 23, 2021

Virtual, USA

Acceptance Rates

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
328
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)6

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li NGuo JHuang BLi YZhang YLi CHuang W(2024)TCSA: Efficient Localization of Busy-Wait Synchronization Bugs for Latency-Critical ApplicationsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.334257335:2(297-309)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TPDS.2023.3342573
Cai YYao PYe CZhang CCalandrino JTroncoso C(2023)Place your locks wellProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620446(3727-3744)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620446
Yu TJia CChen RLi CWang BJiang Y(2023)Precise Dynamic Data Race Prediction for Interrupt-Driven Embedded Software2023 IEEE 34th International Symposium on Software Reliability Engineering Workshops (ISSREW)10.1109/ISSREW60843.2023.00049(69-74)Online publication date: 9-Oct-2023
https://doi.org/10.1109/ISSREW60843.2023.00049
Leesatapornwongsa TRen XNath SRoychoudhury ACadar CKim M(2022)FlakeRepro: automated and efficient reproduction of concurrency-related flaky testsProceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3540250.3558956(1509-1520)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3540250.3558956

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