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

research-article

Multithreaded test synthesis for deadlock detection

Authors:

Malavika Samak,

Murali Krishna RamanathanAuthors Info & Claims

OOPSLA '14: Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications

Pages 473 - 489

https://doi.org/10.1145/2660193.2660238

Published: 15 October 2014 Publication History

Abstract

Designing and implementing thread-safe multithreaded libraries can be a daunting task as developers of these libraries need to ensure that their implementations are free from concurrency bugs, including deadlocks. The usual practice involves employing software testing and/or dynamic analysis to detect deadlocks. Their effectiveness is dependent on well-designed multithreaded test cases. Unsurprisingly, developing multithreaded tests is significantly harder than developing sequential tests for obvious reasons.

In this paper, we address the problem of automatically synthesizing multithreaded tests that can induce deadlocks. The key insight to our approach is that a subset of the properties observed when a deadlock manifests in a concurrent execution can also be observed in a single threaded execution. We design a novel, automatic, scalable and directed approach that identifies these properties and synthesizes a deadlock revealing multithreaded test. The input to our approach is the library implementation under consideration and the output is a set of deadlock revealing multithreaded tests.

We have implemented our approach as part of a tool, named OMEN¹. OMEN is able to synthesize multithreaded tests on many multithreaded Java libraries. Applying a dynamic deadlock detector on the execution of the synthesized tests results in the detection of a number of deadlocks, including 35 real deadlocks in classes documented as thread-safe. Moreover, our experimental results show that dynamic analysis on multithreaded tests that are either synthesized randomly or developed by third-party programmers are ineffective in detecting the deadlocks.

References

[1]

COLT API Documentation. https://acs.lbl.gov/software/colt/api/.

[2]

M. D. Bond, M. Kulkarni, M. Cao, M. Zhang, M. Fathi Salmi, S. Biswas, A. Sengupta, and J. Huang. Octet: Capturing and controlling cross-thread dependences efficiently. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA '13, pages 693--712, 2013.

Digital Library

[3]

Y. Cai and W. K. Chan. Magicfuzzer: Scalable deadlock detection for large-scale applications. In Proceedings of the 2012 International Conference on Software Engineering, ICSE 2012.

Digital Library

[4]

D. Deng, W. Zhang, and S. Lu. Efficient concurrency-bug detection across inputs. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA '13, pages 785--802, 2013.

Digital Library

[5]

J. Deshmukh, E. A. Emerson, and S. Sankaranarayanan. Symbolic deadlock analysis in concurrent libraries and their clients. In Proceedings of the 2009 IEEE/ACM International Conference on Automated Software Engineering, ASE '09, pages 480--491, 2009.

Digital Library

[6]

T. Elmas, J. Burnim, G. Necula, and K. Sen. Concurrit: A domain specific language for reproducing concurrency bugs. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '13, pages 153--164, 2013.

Digital Library

[7]

M. Eslamimehr and J. Palsberg. Race directed scheduling of concurrent programs. In Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '14, pages 301--314, 2014.

Digital Library

[8]

C. Flanagan and S. N. Freund. Fasttrack: Efficient and precise dynamic race detection. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '09.

Digital Library

[9]

P. Godefroid, N. Klarlund, and K. Sen. Dart: Directed automated random testing. In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '05.

Digital Library

[10]

J. Huang, C. Zhang, and J. Dolby. Clap: Recording local executions to reproduce concurrency failures. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '13.

Digital Library

[11]

V. Jagannath, M. Gligoric, D. Jin, Q. Luo, G. Rosu, and D. Marinov. Improved multithreaded unit testing. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering, ESEC/FSE '11, pages 223--233, 2011.

Digital Library

[12]

C. S. Jensen, M. R. Prasad, and A. Møller. Automated testing with targeted event sequence generation. In Proc. 22nd International Symposium on Software Testing and Analysis (ISSTA), July 2013.

Digital Library

[13]

P. Joshi, M. Naik, K. Sen, and D. Gay. An effective dynamic analysis for detecting generalized deadlocks. In Proceedings of the Eighteenth ACMSIGSOFT International Symposium on Foundations of Software Engineering, FSE, 2010.

Digital Library

[14]

P. Joshi, C.-S. Park, K. Sen, and M. Naik. A randomized dynamic program analysis technique for detecting real deadlocks. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '09.

Digital Library

[15]

S. McPeak, C.-H. Gros, and M. K. Ramanathan. Scalable and incremental software bug detection. In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2013.

Digital Library

[16]

M. Musuvathi and S. Qadeer. Iterative context bounding for systematic testing of multithreaded programs. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '07.

Digital Library

[17]

S. Nagarakatte, S. Burckhardt, M. M. Martin, and M. Musuvathi. Multicore acceleration of priority-based schedulers for concurrency bug detection. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '12.

Digital Library

[18]

M. Naik, C.-S. Park, K. Sen, and D. Gay. Effective static deadlock detection. In Proceedings of the 31st International Conference on Software Engineering, ICSE '09.

Digital Library

[19]

R. Nokhbeh Zaeem and S. Khurshid. Test input generation using dynamic programming. In Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering, FSE '12, 2012.

Digital Library

[20]

C. Pacheco and M. D. Ernst. Randoop: Feedback-directed random testing for java. In Companion to the 22Nd ACM SIGPLAN Conference on Object-oriented Programming Systems and Applications Companion, OOPSLA '07.

Digital Library

[21]

S. Park, Y. Zhou, W. Xiong, Z. Yin, R. Kaushik, K. H. Lee, and S. Lu. Pres: Probabilistic replay with execution sketching on multiprocessors. In Proceedings of the ACMSIGOPS 22nd Symposium on Operating Systems Principles, SOSP '09.

Digital Library

[22]

M. Pradel and T. R. Gross. Fully automatic and precise detection of thread safety violations. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '12.

Digital Library

[23]

M. Samak and M. K. Ramanathan. Trace driven dynamic deadlock detection and reproduction. In Proceedings of the 2014 ACM SIGPLAN Conference on Principles and Practices of Parallel Programming, PPoPP '14.

Digital Library

[24]

K. Sen and G. Agha. Cute and jcute: Concolic unit testing and explicit path model-checking tools. In Proceedings of the 18th International Conference on Computer Aided Verification, CAV'06.

Digital Library

[25]

S. Thummalapenta, T. Xie, N. Tillmann, J. de Halleux, and Z. Su. Synthesizing method sequences for high-coverage testing. In Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA '11, pages 189--206, 2011.

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 International Conference on Compiler Construction, LNCS 1781, pages 18--34, 2000.

Digital Library

[27]

A. Williams, W. Thies, and M. D. Ernst. Static deadlock detection for java libraries. In ECOOP 2005-Object-Oriented Programming. Springer Berlin Heidelberg.

Digital Library

[28]

C. Yan, W. Shangru, and W. K. Chan. Conlock: A constraint-based approach to dynamic checking on deadlocks in multithreaded programs. In Proceedings of the 36th International Conference on Software Engineering, ICSE '14.

Digital Library

[29]

J. Yang, H. Cui, J. Wu, Y. Tang, and G. Hu. Making parallel programs reliable with stable multithreading. Communications of the ACM, 57(3).

Digital Library

[30]

J. Yu, S. Narayanasamy, C. Pereira, and G. Pokam. Maple: A coverage-driven testing tool for multithreaded programs. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA '12.

Digital Library

Cited By

Tunç HMathur UPavlogiannis AViswanathan M(2023)Sound Dynamic Deadlock Prediction in Linear TimeProceedings of the ACM on Programming Languages10.1145/35912917:PLDI(1733-1758)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591291
Stoica BLu SMusuvathi MNath SFedorova ANarayanan DDi Luna GQuerzoni L(2023)WAFFLE: Exposing Memory Ordering Bugs Efficiently with Active Delay InjectionProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3567507(111-126)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3552326.3567507
Zhao YWang ZLiu SSun JChen JChen X(2023)Achieving High MAP-Coverage Through Pattern Constraint ReductionIEEE Transactions on Software Engineering10.1109/TSE.2022.314448049:1(99-112)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TSE.2022.3144480
Show More Cited By

Index Terms

Multithreaded test synthesis for deadlock detection
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Process validation
        Traceability
      2. Software defect analysis
        Software testing and debugging

Recommendations

Multithreaded test synthesis for deadlock detection
OOPSLA '14

Designing and implementing thread-safe multithreaded libraries can be a daunting task as developers of these libraries need to ensure that their implementations are free from concurrency bugs, including deadlocks. The usual practice involves employing ...
Omen+: a precise dynamic deadlock detector for multithreaded Java libraries
FSE 2014: Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering

Designing thread-safe libraries without concurrency defects can be a challenging task. Detecting deadlocks while invoking methods in these libraries concurrently is hard due to the possible number of method invocation combinations, the object ...
A Priority Based Distributed Deadlock Detection Algorithm

Deadlock handling is an important component of transaction management in a database system. In this paper, we contribute to the development of techniques for transaction management by presenting an algorithm for detecting deadlocks in a distributed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '14: Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications

October 2014

946 pages

ISBN:9781450325851

DOI:10.1145/2660193

General Chair:
Andrew Black
Portland State University, USA
,
Program Chair:
Todd Millstein
University of California, Los Angeles, USA

ACM SIGPLAN Notices Volume 49, Issue 10
OOPSLA '14
October 2014
907 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2714064
Editor:
Andy Gill
University of Kansas, Lawrence, KS
Issue’s Table of Contents

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

In-Cooperation

SIGAda: ACM Special Interest Group on Ada Programming Language

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 October 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Ministry of Human Resources Development

Conference

SPLASH '14

Sponsor:

SIGPLAN

SPLASH '14: Conference on Systems, Programming, and Applications: Software for Humanity

October 20 - 24, 2014

Oregon, Portland, USA

Acceptance Rates

OOPSLA '14 Paper Acceptance Rate 52 of 186 submissions, 28%;

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
572
Total Downloads

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

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tunç HMathur UPavlogiannis AViswanathan M(2023)Sound Dynamic Deadlock Prediction in Linear TimeProceedings of the ACM on Programming Languages10.1145/35912917:PLDI(1733-1758)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591291
Stoica BLu SMusuvathi MNath SFedorova ANarayanan DDi Luna GQuerzoni L(2023)WAFFLE: Exposing Memory Ordering Bugs Efficiently with Active Delay InjectionProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3567507(111-126)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3552326.3567507
Zhao YWang ZLiu SSun JChen JChen X(2023)Achieving High MAP-Coverage Through Pattern Constraint ReductionIEEE Transactions on Software Engineering10.1109/TSE.2022.314448049:1(99-112)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TSE.2022.3144480
Rahman SLi CShi AGrundy J(2023)TSVD4J: Thread-Safety Violation Detection for JavaProceedings of the 45th International Conference on Software Engineering: Companion Proceedings10.1109/ICSE-Companion58688.2023.00029(78-82)Online publication date: 14-May-2023
https://dl.acm.org/doi/10.1109/ICSE-Companion58688.2023.00029
Zhou JYang HLange JLiu TRyu SSmaragdakis Y(2022)Deadlock prediction via generalized dependencyProceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3533767.3534377(455-466)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1145/3533767.3534377
Chabbi MRamanathan MJhala RDillig I(2022)A study of real-world data races in GolangProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523720(474-489)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523720
Gong SAltinbüken DFonseca PManiatis P(2021)SnowboardProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles10.1145/3477132.3483549(66-83)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3477132.3483549
Qiu ZShao SZhao QJin G(2021)A Characteristic Study of Deadlocks in Database-Backed Web Applications2021 IEEE 32nd International Symposium on Software Reliability Engineering (ISSRE)10.1109/ISSRE52982.2021.00059(510-521)Online publication date: Oct-2021
https://doi.org/10.1109/ISSRE52982.2021.00059
Khanna DPurandare RSharma S(2021)Synthesizing Multi-threaded Tests from Sequential Traces to Detect Communication Deadlocks2021 14th IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST49551.2021.00013(1-12)Online publication date: Apr-2021
https://doi.org/10.1109/ICST49551.2021.00013
Santos IFurlanetti AMelo Sde Souza PDelamaro MSouza SCavalcante EDantas FBatista T(2020)Contributions to improve the combined selection of concurrent software testing techniquesProceedings of the 5th Brazilian Symposium on Systematic and Automated Software Testing10.1145/3425174.3425214(69-78)Online publication date: 20-Oct-2020
https://dl.acm.org/doi/10.1145/3425174.3425214
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