Article

A study of interleaving coverage criteria

Authors:

Yuanyuan ZhouAuthors Info & Claims

ESEC-FSE '07: Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering

Pages 533 - 536

https://doi.org/10.1145/1287624.1287703

Published: 07 September 2007 Publication History

Abstract

Concurrency bugs are becoming increasingly important due to the prevalence of concurrent programs. A fundamental problem of concurrent program bug detection and testing is that the interleaving space is too large to be thoroughly explored. Practical yet effective interleaving coverage criteria are desired to systematically explore the interleaving space and effectively expose concurrency bugs.

This paper proposes a concurrent program interleaving coverage criteria hierarchy, including seven (including five new) coverage criteria. These criteria are all designed based on different concurrency fault models. Their cost ranges from exponential to linear.

References

[1]

B. Beizer. Software Testing Techniques, 2nd edition. New York: Van Nostrand Reinhold, 1990.

Digital Library

[2]

A. Bron, E. Farchi, Y. Magid, Y. Nir, and S. Ur. Applications of synchronization coverage. In PPoPP, 2005.

Digital Library

[3]

L. A. Clarke, A. Podgurski, D. J. Richardson, and S. J. Zeil. A formal evaluation of data flow path selection criteria. IEEE Trans. Software Eng., 15(11):1318{1332, 1989.

Digital Library

[4]

O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur. Multi-threaded java program test generation. IBM Systems Journal, 2002.

Digital Library

[5]

M. Factor, E. Farchi, Y. Lichtenstein, and Y. Malka. Testing concurrent programs: a formal evaluation of coverage criteria. In ICCSSE, 1996.

Digital Library

[6]

P. G. Frankl and E. J. Weyuker. An applicable family of data flow testing criteria. IEEE Trans. Softw. Eng., 1988.

Digital Library

[7]

M. J. Harrold and B. A. Malloy. Data flow testing of parallelized code. In Proceedings of the International Conference on Software Maintenance, 1992.

[8]

S. Lu, J. Tucek, F. Qin, and Y. Zhou. Avio: Detecting atomicity violations via access interleaving invariants. In ASPLOS, 2006.

Digital Library

[9]

S. Qadeer and D. Wu. Kiss: keep it simple and sequential. In PLDI, 2004.

Digital Library

[10]

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM TOCS, 1997.

Digital Library

[11]

R. N. Taylor, D. L. Levine, and C. D. Kelly. Structural testing of concurrent programs. IEEE Trans. Softw. Eng., 1992.

Digital Library

[12]

M. Vaziri, F. Tip, and J. Dolby. Associating synchronization constraints with data in an object-oriented language. In POPL, 2006.

Digital Library

[13]

S. N. Weiss. A formal framework for the study of concurrent program testing. In Proceedings of the Second Workshop on Software Testing, Verification and Analysis, 1988.

[14]

E. J. Weyuker. More experience with data flow testing. IEEE Trans. Softw. Eng., 19(9):912--919, 1993.

Digital Library

[15]

C.-S. D. Yang, A. L. Souter, and L. L. Pollock. All-du-path coverage for parallel programs. In ISSTA, 1998.

Digital Library

[16]

H. Zhu, P. A. V. Hall, and J. H. R. May. Software unit test coverage and adequacy. ACM Comput. Surv., 1997.

Digital Library

Cited By

Gong SPeng DAltınbüken DFonseca PManiatis PDruschel PKaufmann AMace JFlinn JSeltzer M(2023)Snowcat: Efficient Kernel Concurrency Testing using a Learned Coverage PredictorProceedings of the 29th Symposium on Operating Systems Principles10.1145/3600006.3613148(35-51)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3600006.3613148
Guo YLiang ZZhu SWang JYang ZShen WZhang JCai Y(2023)Sound Predictive Fuzzing for Multi-threaded Programs2023 IEEE 47th Annual Computers, Software, and Applications Conference (COMPSAC)10.1109/COMPSAC57700.2023.00110(810-819)Online publication date: Jun-2023
https://doi.org/10.1109/COMPSAC57700.2023.00110
Mercan HJaveed AYilmaz C(2022)Flexible Combinatorial Interaction TestingIEEE Transactions on Software Engineering10.1109/TSE.2020.301031748:3(1030-1066)Online publication date: 1-Mar-2022
https://doi.org/10.1109/TSE.2020.3010317
Show More Cited By

Index Terms

A study of interleaving coverage criteria
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

A study of interleaving coverage criteria
ESEC-FSE companion '07: The 6th Joint Meeting on European software engineering conference and the ACM SIGSOFT symposium on the foundations of software engineering: companion papers

Concurrency bugs are becoming increasingly important due to the prevalence of concurrent programs. A fundamental problem of concurrent program bug detection and testing is that the interleaving space is too large to be thoroughly explored. Practical yet ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ESEC-FSE '07: Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering

September 2007

638 pages

ISBN:9781595938114

DOI:10.1145/1287624

General Chair:
Ivica Crnkovic
Mälardalen University, Sweden
,
Program Chair:
Antonia Bertolino
ISTI-CNR, Italy

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 September 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ESEC/FSE07

Sponsor:

ESEC/FSE07: Joint 11th European Software Engineering Conference 2007

September 3 - 7, 2007

Dubrovnik, Croatia

Acceptance Rates

Overall Acceptance Rate 112 of 543 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

62
Total Citations
View Citations
414
Total Downloads

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

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gong SPeng DAltınbüken DFonseca PManiatis PDruschel PKaufmann AMace JFlinn JSeltzer M(2023)Snowcat: Efficient Kernel Concurrency Testing using a Learned Coverage PredictorProceedings of the 29th Symposium on Operating Systems Principles10.1145/3600006.3613148(35-51)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3600006.3613148
Guo YLiang ZZhu SWang JYang ZShen WZhang JCai Y(2023)Sound Predictive Fuzzing for Multi-threaded Programs2023 IEEE 47th Annual Computers, Software, and Applications Conference (COMPSAC)10.1109/COMPSAC57700.2023.00110(810-819)Online publication date: Jun-2023
https://doi.org/10.1109/COMPSAC57700.2023.00110
Mercan HJaveed AYilmaz C(2022)Flexible Combinatorial Interaction TestingIEEE Transactions on Software Engineering10.1109/TSE.2020.301031748:3(1030-1066)Online publication date: 1-Mar-2022
https://doi.org/10.1109/TSE.2020.3010317
Bessler GCordova JCullen-Baratloo SDissem SLu EDevin SAbughararh IBang LJuristo N(2021)MetrinomeProceedings of the 43rd International Conference on Software Engineering: Companion Proceedings10.1109/ICSE-Companion52605.2021.00028(29-32)Online publication date: 25-May-2021
https://dl.acm.org/doi/10.1109/ICSE-Companion52605.2021.00028
Shirole MKumar R(2021)Concurrency coverage criteria for activity diagramsIET Software10.1049/sfw2.1200915:1(43-54)Online publication date: 19-Jan-2021
https://doi.org/10.1049/sfw2.12009
Shirole MKumar R(2021)Concurrent behavioral coverage criteria for sequence diagramsInnovations in Systems and Software Engineering10.1007/s11334-021-00413-719:2(157-176)Online publication date: 25-Nov-2021
https://doi.org/10.1007/s11334-021-00413-7
Liu HSilvestro SZhang XHuang JLiu T(2020)WATCHER: in-situ failure diagnosisProceedings of the ACM on Programming Languages10.1145/34282114:OOPSLA(1-27)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428211
Yu THuang ZWang C(2020) ConTesa : Directed Test Suite Augmentation for Concurrent Software IEEE Transactions on Software Engineering10.1109/TSE.2018.286139246:4(405-419)Online publication date: 1-Apr-2020
https://doi.org/10.1109/TSE.2018.2861392
Winzinger SWirtz G(2020)Applicability of Coverage Criteria for Serverless Applications2020 IEEE International Conference on Service Oriented Systems Engineering (SOSE)10.1109/SOSE49046.2020.00013(49-56)Online publication date: Aug-2020
https://doi.org/10.1109/SOSE49046.2020.00013
Liu HSilvestro SWang XDuan LLiu TKandemir MJimborean AMoseley T(2019)CSOD: context-sensitive overflow detectionProceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization10.5555/3314872.3314881(50-60)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.5555/3314872.3314881
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