research-article

Debugging non-deadlock concurrency bugs

Author:

Sangmin ParkAuthors Info & Claims

ISSTA 2013: Proceedings of the 2013 International Symposium on Software Testing and Analysis

Pages 358 - 361

https://doi.org/10.1145/2483760.2492395

Published: 15 July 2013 Publication History

Abstract

Concurrency bugs are difficult to debug because of nondeterministic behaviors of concurrent programs. Existing fault-localization techniques for non-deadlock concurrency bugs do not provide the comprehensive information to identify and understand the bugs. Existing automatic fault-fix techniques for concurrency bugs do not provide confidence that the fault has been fixed. To address the limitations of existing techniques, this research will develop techniques that will assist developers in several aspects of debugging, from finding the locations of concurrency bugs to providing confidence after the fix. The expected contributions of this research include a fault-localization technique that locates concurrency bugs, a fault-comprehension technique that assists understanding of bugs, a fix-confidence technique that provides confidence of fixes, and a framework that implements the techniques and that is used to perform empirical studies to evaluate the techniques.

References

[1]

Nasdaq’s facebook glitch came from race conditions. http://bit.ly/FBNASDQ.

[2]

P. Godefroid and N. Nagappan. Concurrency at Microsoft: An exploratory survey. In (EC)2, July 2008.

[3]

S. Hong, J. Ahn, S. Park, M. Kim, and M. J. Harrold. Testing concurrent programs to achieve high synchronization coverage. In ISSTA, July 2012.

Digital Library

[4]

N. Jalbert, C. Pereira, G. Pokam, and K. Sen. RADBench: a concurrency bug benchmark suite. In HotPar, May 2011.

Digital Library

[5]

G. Jin, L. Song, W. Zhang, S. Lu, and B. Liblit. Automated atomicity-violation fixing. In PLDI, pages 389–400, June 2011.

Digital Library

[6]

G. Jin, A. Thakur, B. Liblit, and S. Lu. Instrumentation and sampling strategies for cooperative concurrency bug isolation. In OOPSLA, pages 241–255, Oct. 2010.

Digital Library

[7]

G. Jin, W. Zhang, D. Deng, B. Liblit, and S. Lu. Automated concurrency-bug fixing. In OSDI, pages 221–236, Oct. 2012.

Digital Library

[8]

J. A. Jones, M. J. Harrold, and J. Stasko. Visualization of test information to assist fault localization. In ICSE, pages 467–477, May 2002.

[9]

S. Lu, S. Park, E. Seo, and Y. Zhou. Learning from mistakes—a comprehensive study on real world concurrency bug characteristics. In ASPLOS, pages 329–339, Mar. 2008.

Digital Library

[10]

S. Lu, J. Tucek, F. Qin, and Y. Zhou. AVIO: Detecting atomicity violations via access interleaving invariants. In ASPLOS, pages 37–48, Oct. 2006.

Digital Library

[11]

B. Lucia and L. Ceze. Finding concurrency bugs with context-aware communication graphs. In MICRO, pages 553–563, Dec. 2009.

Digital Library

[12]

B. Lucia, B. P. Wood, and L. Ceze. Isolating and understanding concurrency errors using reconstructed execution fragments. In PLDI, pages 378–388, June 2011.

Digital Library

[13]

M. Naik and A. Aiken. Conditional must not aliasing for static race detection. In POPL, pages 327–338, January 2007.

Digital Library

[14]

S. Park, M. J. Harrold, and R. Vuduc. Gri n: Grouping suspicious memory-access patterns to improve understanding of concurrency bugs. In ISSTA, July 2013.

Digital Library

[15]

S. Park, R. Vuduc, and M. J. Harrold. Falcon: Fault localization in concurrent programs. In ICSE, pages 245–254, May 2010.

Digital Library

[16]

S. Park, R. Vuduc, and M. J. Harrold. A unified approach for localizing non-deadlock concurrency bugs. In ICST, pages 51–60, Apr. 2012.

Digital Library

[17]

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. Trans. Comput. Syst., 15(4):391–411, 1997.

Digital Library

[18]

Y. Shi, S. Park, Z. Yin, S. Lu, Y. Zhou, W. Chen, and W. Zheng. Do I use the wrong definition? DefUse: Definition-use invariants for detecting concurrency and sequential bugs. In OOPSLA, pages 160–174, Oct. 2010.

Digital Library

[19]

M. Vaziri, F. Tip, and J. Dolby. Associating synchronization constraints with data in an Object-Oriented language. In POPL, pages 334–345, 2006.

Digital Library

[20]

L. Wang and S. D. Stoller. Accurate and e cient runtime detection of atomicity errors in concurrent programs. In PPoPP, pages 137–146, Mar. 2006.

Digital Library

[21]

G. Yang, M. B. Dwyer, and G. Rothermel. Regression model checking. In ICSM, pages 115–124, September 2009.

[22]

Z. Yin, D. Yuan, Y. Zhou, S. Pasupathy, and L. Bairavasundaram. How do fixes become bugs? — a comprehensive characteristic study on incorrect fixes in commercial and open source operating systems. In ESEC/FSE, pages 26–36, Sept. 2011.

Digital Library

[23]

J. Zhou, X. Xiao, and C. Zhang. Stride: Search-based deterministic replay in polynomial time via bounded linkage. In ICSE, pages 892–902, June 2012.

Digital Library

Cited By

Wong WGao RLi YAbreu RWotawa FLi D(2023)Software Fault Localization: an Overview of Research, Techniques, and ToolsHandbook of Software Fault Localization10.1002/9781119880929.ch1(1-117)Online publication date: 21-Apr-2023
https://doi.org/10.1002/9781119880929.ch1
Cai YCao LZhao JBodden ESchäfer WDeursen AZisman A(2017)Adaptively generating high quality fixes for atomicity violationsProceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering10.1145/3106237.3106239(303-314)Online publication date: 21-Aug-2017
https://dl.acm.org/doi/10.1145/3106237.3106239
Abbaspour Asadollah SSundmark DEldh SHansson HAfzal W(2017)10 Years of research on debugging concurrent and multicore softwareSoftware Quality Journal10.1007/s11219-015-9301-725:1(49-82)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s11219-015-9301-7
Show More Cited By

Index Terms

Debugging non-deadlock concurrency bugs
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging
  2. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages

Recommendations

Applying transactional memory to concurrency bugs
ASPLOS XVII: Proceedings of the seventeenth international conference on Architectural Support for Programming Languages and Operating Systems

Multithreaded programs often suffer from synchronization bugs such as atomicity violations and deadlocks. These bugs arise from complicated locking strategies and ad hoc synchronization methods to avoid the use of locks. A survey of the bug databases of ...
Applying transactional memory to concurrency bugs
ASPLOS '12

Multithreaded programs often suffer from synchronization bugs such as atomicity violations and deadlocks. These bugs arise from complicated locking strategies and ad hoc synchronization methods to avoid the use of locks. A survey of the bug databases of ...
Applying transactional memory to concurrency bugs
ASPLOS '12

Multithreaded programs often suffer from synchronization bugs such as atomicity violations and deadlocks. These bugs arise from complicated locking strategies and ad hoc synchronization methods to avoid the use of locks. A survey of the bug databases of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA 2013: Proceedings of the 2013 International Symposium on Software Testing and Analysis

July 2013

381 pages

ISBN:9781450321594

DOI:10.1145/2483760

General Chair:
Mauro Pezzè,
Program Chair:
Mark Harman

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

SIGSOFT: ACM Special Interest Group on Software Engineering

In-Cooperation

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSTA '13

Sponsor:

SIGSOFT

ISSTA '13: Iitsnternational Symposium on Software Testing and Analysis

July 15 - 20, 2013

Lugano, Switzerland

Acceptance Rates

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
400
Total Downloads

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

Reflects downloads up to 25 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wong WGao RLi YAbreu RWotawa FLi D(2023)Software Fault Localization: an Overview of Research, Techniques, and ToolsHandbook of Software Fault Localization10.1002/9781119880929.ch1(1-117)Online publication date: 21-Apr-2023
https://doi.org/10.1002/9781119880929.ch1
Cai YCao LZhao JBodden ESchäfer WDeursen AZisman A(2017)Adaptively generating high quality fixes for atomicity violationsProceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering10.1145/3106237.3106239(303-314)Online publication date: 21-Aug-2017
https://dl.acm.org/doi/10.1145/3106237.3106239
Abbaspour Asadollah SSundmark DEldh SHansson HAfzal W(2017)10 Years of research on debugging concurrent and multicore softwareSoftware Quality Journal10.1007/s11219-015-9301-725:1(49-82)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s11219-015-9301-7
Cai YYang ZLo DApel SKhurshid S(2016)Radius aware probabilistic testing of deadlocks with guaranteesProceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering10.1145/2970276.2970307(356-367)Online publication date: 25-Aug-2016
https://dl.acm.org/doi/10.1145/2970276.2970307
Cai YCao LDillon LVisser WWilliams L(2016)Fixing deadlocks via lock pre-acquisitionsProceedings of the 38th International Conference on Software Engineering10.1145/2884781.2884819(1109-1120)Online publication date: 14-May-2016
https://dl.acm.org/doi/10.1145/2884781.2884819
Wong WGao RLi YAbreu RWotawa F(2016)A Survey on Software Fault LocalizationIEEE Transactions on Software Engineering10.1109/TSE.2016.252136842:8(707-740)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1109/TSE.2016.2521368
Lin ZMarinov DZhong HChen YZhao JCohen MGrunske LWhalen M(2015)JaConTeBeProceedings of the 30th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2015.87(178-189)Online publication date: 9-Nov-2015
https://dl.acm.org/doi/10.1109/ASE.2015.87
Jyoti AArora V(2014)Debugging and visualization techniques for multithreaded programs: A surveyInternational Conference on Recent Advances and Innovations in Engineering (ICRAIE-2014)10.1109/ICRAIE.2014.6909202(1-6)Online publication date: May-2014
https://doi.org/10.1109/ICRAIE.2014.6909202
Jyoti AArora V(2014)Visualization of deadlock and wait-notify anomaly in multithreaded programs2014 IEEE International Conference on Advanced Communications, Control and Computing Technologies10.1109/ICACCCT.2014.7019382(1616-1620)Online publication date: May-2014
https://doi.org/10.1109/ICACCCT.2014.7019382

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.

Figures

Tables

Media

View Table of Conten