research-article

RECONTEST: effective regression testing of concurrent programs

Authors:

Valerio Terragni,

Shing-Chi Cheung,

Charles ZhangAuthors Info & Claims

ICSE '15: Proceedings of the 37th International Conference on Software Engineering - Volume 1

Pages 246 - 256

Published: 16 May 2015 Publication History

Abstract

Concurrent programs proliferate as multi-core technologies advance. The regression testing of concurrent programs often requires running a failing test for weeks before catching a faulty interleaving, due to the myriad of possible interleavings of memory accesses arising from concurrent program executions. As a result, the conventional approach that selects a sub-set of test cases for regression testing without considering interleavings is insufficient In this paper we present ReConTest to address the problem by selecting the new interleavings that arise due to code changes. These interleavings must be explored in order to uncover regression bugs. ReConTest efficiently selects new interleavings by first identifying shared memory accesses that are affected by the changes, and then exploring only those problematic interleavings that contain at least one of these accesses. We have implemented ReConTest as an automated tool and evaluated it using 13 real-world concurrent program subjects. Our results show that ReConTest can significantly reduce the regression testing cost without missing any faulty interleavings induced by code changes.

References

[1]

Apiwattanapong, T., Orso, A. and Harrold, M. J. Efficient and Precise Dynamic Impact Analysis Using Execute-After Sequences. In ICSE, 2005

Digital Library

[2]

Backes, J., Person, S., Rungta, N. and Tkachuk, O. Regression Verification Using Impact Summaries. In SPIN, 2013.

[3]

Beyer, D., Lowe, S., Novikov, E., Stahlbauer, A. and Wendler, P. Precision Reuse for Efficient Regression Verication. In FSE, 2013.

Digital Library

[4]

Bohner, S. A. and Arnold, R. S. Software Change Impact Analysis. In IEEE-CS, 1996.

Digital Library

[5]

Cai, Y. and Chan, W. K. MagicFuzzer: Scalable Deadlock Detection for Large-Scale Applications. In ICSE, 2012.

Digital Library

[6]

Deng, D., Zhang, W. and Lu, S. Efficient Concurrency-Bug Detection Across Inputs. In OOPSLA, 2013.

Digital Library

[7]

Deng, D., Zhang, W., Wang, B., Zhao, P., and Lu, S. Understanding the Interleaving-Space Overlap across Inputs and Software Versions. In HotPar, 2012.

Digital Library

[8]

Do, H., Mirarab, S., Tahvildari, L. and Rothermel, G. The Effects of Time Constraints on Test Case Prioritization: A Series of Controlled Experiments. IEEE TSE, 2010.

Digital Library

[9]

Farchi, E., Nir, Y., and Ur, S. Concurrent Bug Patterns and How to Test Them. IPDPS, 2003.

Digital Library

[10]

Elbaum, S., Malishevsky, A. G. and Rothermel, G. Prioritizing Test Cases for Regression Testing. In ISSTA, 2000.

Digital Library

[11]

Farzan, A. and Madhusudan, P. The Complexity of Predicting Atomicity Violations. In TACAS, 2009.

Digital Library

[12]

Flanagan, C. and Godefroid, P. Dynamic Partial-Order Reduction for Model Checking Software. In POPL, 2005.

Digital Library

[13]

Fluri, B., Wuersch, M., PInzger, M. and Gall, H. Change Distilling: Tree Differencing for Fine-Grained Source Code Change Extraction. IEEE TSE, 2007.

Digital Library

[14]

Harrold, M. J., Jones, J. A., Li, T., Liang, D., Orso, A., Pennings, M., Sinha, S., Spoon, S. A. and Gujarathi, A. Regression Test Selection for Java Software. In OOPSLA, 2001.

Digital Library

[15]

Havelund, K. and Pressburger, T. Model checking JAVA programs using JAVA PathFinder. STTT, 2000.

[16]

Hsu, H. Y. and Orso, A. MINTS: A General Framework and Tool for Supporting Test-Suite Minimization. In ICSE, 2009.

Digital Library

[17]

Huang, J. and Zhang, C. Persuasive Prediction of Concurrency Access Anomalies. In ISSTA, 2011.

Digital Library

[18]

Huang, J., Zhou, J. and Zhang, C. Scaling Predictive Analysis of Concurrent Programs by Removing Trace Redundancy. TOSEM, 2013.

Digital Library

[19]

Jagannath, V., Luo, Q. and Marinov, D. Change-Aware Preemption Prioritization. In ISSTA, 2011.

Digital Library

[20]

Joshi, P., Naik, M., Park, C.-S. and Sen, K. CalFuzzer: An Extensible Active Testing Framework for Concurrent Programs. In CAV, 2009.

Digital Library

[21]

Joshi, P., Park, C.-S., Sen, K. and Naik, M. A Randomized Dynamic Program Analysis Technique for Detecting Real Deadlocks. In PLDI, 2009.

Digital Library

[22]

Lai, Z., Cheung, S. C. and Chan, W. K. Detecting Atomic-Set Serializability Violations in Multithreaded Programs through Active Randomized Testing. In ICSE, 2010.

Digital Library

[23]

Lamport, L. Time, Clocks, and the Ordering of Events in a Distributed System. CACM, 1978.

Digital Library

[24]

Lauterburg, S., Sobeih, A., Marinov, D. and Viswanathan, M. Incremental State-Space Exploration for Programs with Dynamically Allocated Data. In ICSE, 2008.

Digital Library

[25]

Li, B., Sun, X., Leung, H. and Zhang, S. A Survey of Code-Based Change Impact Analysis Techniques. STVR, 2013.

[26]

Liang, P., Tripp, O., Naik, M. and Sagiv, M. A Dynamic Evaluation of the Precision of Static Heap Abstractions. In OOPSLA, 2010.

Digital Library

[27]

Lu, S., Jiang, W. and Zhou, Y. A Study of Interleaving Coverage Criteria. In FSE, 2007.

Digital Library

[28]

Lu, S., Park, S., Seo, E. and Zhou, Y. Learning from Mistakes: A Comprehensive Study on Real World Concurrency Bug Characteristics. In ASPLOS, 2008.

Digital Library

[29]

Mattern, F. Virtual Time and Global States of Distributed Systems. In WDAG, 1989.

[30]

Musuvathi, M., Qadeer, S., Ball, T., Basler, G., Nainar, P. A., and Neamtiu, I. Finding and Reproducing Heisenbugs in Concurrent Programs. In OSDI, 2008.

Digital Library

[31]

Park, S., Lu, S. and Zhou, Y. CTrigger: Exposing Atomicity Violation Bugs from Their Hiding Places. In ASPLOS, 2009.

Digital Library

[32]

Person, S., Yang, G., Rungta, N. and Khurshid, S. Directed Incremental Symbolic Execution. In PLDI 2011.

Digital Library

[33]

Rothermel, G. and Harrold, M. J. Analyzing Regression Test Selection Techniques. IEEE TSE, 1996.

Digital Library

[34]

Rothermel, G. and Harrold, M. J. A safe, Efficient Regression Test Selection Technique. TOSEM, 1997.

Digital Library

[35]

Savage, S., Burrows, M., Nelson, G., Sobalvarro, P. and Anderson, T. Eraser: A Dynamic Data Dace Detector for Multithreaded Programs. In SOSP, 1997.

Digital Library

[36]

Sen, K. Race Directed Random Testing of Concurrent Programs. In PLDI, 2008.

Digital Library

[37]

Sen, K. and Agha, G. Detecting errors in multithreaded programs by generalized predictive analysis of executions. In FMOODS, 2005.

Digital Library

[38]

Shivers, O. Control Flow Analysis in Scheme. In PLDI, 2009.

Digital Library

[39]

Sorrentino, F., Farzan, A. and Madhusudan, P. PENELOPE: Weaving Threads to Expose Atomicity Violations. In FSE, 2010.

Digital Library

[40]

Sumner, W. N., Hammer, C. and Dolby, J. Marathon: Detecting Atomic-Set Serializability Violations with Conflict Graphs. In RV, 2012.

Digital Library

[41]

Sumner, W. N., and Zhang, X. Identifying Execution Points for Dynamic Analyses. In ASE, 2013

Digital Library

[42]

Tian, C., Nagarajan, V., Gupta, R. and Tallam, S. Dynamic Recognition of Synchronization Operations for Improved Data Race Detection. In ISSTA, 2008.

Digital Library

[43]

Vaziri, M., Tip, F. and Dolby, J. Associating Synchronization Constraints with Data in an Object-Oriented Language. In POPL, 2006.

Digital Library

[44]

Xin, B., Sumner, W. N. and Zhang, X. Efficient Program Execution Indexing. In PLDI, 2008.

Digital Library

[45]

Xiong, W., Park, S., Zhang, J., Zhou, Y. and Ma, Z. Ad Hoc Synchronization Considered Harmful. In OSDI, 2010.

Digital Library

[46]

Yang, G., Dwyer, M. B. and Rothermel, G. Regression Model Checking. In ICSM, 2009.

[47]

Yoo, S. and Harman, M. Regression Testing Minimization, Selection and Prioritization: A Survey. STVR, 2010.

Digital Library

[48]

Yu, J., Narayanasamy, S., Pereira, C., and Pokam, G. Maple: A Coverage-Driven Testing Tool for Multithreaded Programs. In OOPSLA, 2012.

Digital Library

[49]

Yu, T., Srisa-an, W. and Rothermel, G. SimRT: An Automated Framework to Support Regression Testing for Data Races. In ICSE, 2014.

Digital Library

Cited By

Liu BHuang J(2018)D4: fast concurrency debugging with parallel differential analysisACM SIGPLAN Notices10.1145/3296979.319239053:4(359-373)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192390
Terragni VPezzè MHuchard MKästner CFraser G(2018)Effectiveness and challenges in generating concurrent tests for thread-safe classesProceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering10.1145/3238147.3238224(64-75)Online publication date: 3-Sep-2018
https://dl.acm.org/doi/10.1145/3238147.3238224
Liu BHuang JFoster JGrossman D(2018)D4: fast concurrency debugging with parallel differential analysisProceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192390(359-373)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3192366.3192390
Show More Cited By

Index Terms

RECONTEST: effective regression testing of concurrent programs
1. 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
        Distributed programming languages
        Parallel programming languages
2. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Parallel computing models

Recommendations

WFR-TM

Transactional Memory (TM) is a promising concurrent programming paradigm which employs transactions to achieve synchronization in accessing common data known as transactional variables. A transaction may either commit, making its updates to ...
Speculation-based techniques for transactional lock-free execution of lock-based programs
Wait-n-GoTM: improving HTM performance by serializing cyclic dependencies
ASPLOS '13

Transactional memory (TM) has been proposed to alleviate some key programmability problems in chip multiprocessors. Most TMs optimistically allow concurrent transactions, detecting read-write or write-write conflicts. Upon conflicts, existing hardware ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICSE '15: Proceedings of the 37th International Conference on Software Engineering - Volume 1

May 2015

999 pages

ISBN:9781479919345

General Chair:
Antonia Bertolino
ISTI-CNR, Italy
,
Program Chairs:
Gerardo Canfora
University of Sannio, Italy
,
Sebastian Elbaum
University of Nebraska-Lincoln

Sponsors

ACM: Association for Computing Machinery
SIGSOFT: ACM Special Interest Group on Software Engineering
IEEE-CS\DATC: IEEE Computer Society
TCSE: IEEE Computer Society's Tech. Council on Software Engin.

Publisher

IEEE Press

Publication History

Published: 16 May 2015

Check for updates

Qualifiers

Research-article

Conference

ICSE '15

Sponsor:

ACM
SIGSOFT
IEEE-CS\DATC
TCSE

ICSE '15: 37th International Conference on Software Engineering

May 16 - 24, 2015

Florence, Italy

Acceptance Rates

Overall Acceptance Rate 276 of 1,856 submissions, 15%

Upcoming Conference

ICSE 2025

2025 IEEE/ACM 46th International Conference on Software Engineering

April 26 - May 3, 2025

Ottawa , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
235
Total Downloads

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

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu BHuang J(2018)D4: fast concurrency debugging with parallel differential analysisACM SIGPLAN Notices10.1145/3296979.319239053:4(359-373)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192390
Terragni VPezzè MHuchard MKästner CFraser G(2018)Effectiveness and challenges in generating concurrent tests for thread-safe classesProceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering10.1145/3238147.3238224(64-75)Online publication date: 3-Sep-2018
https://dl.acm.org/doi/10.1145/3238147.3238224
Liu BHuang JFoster JGrossman D(2018)D4: fast concurrency debugging with parallel differential analysisProceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192390(359-373)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3192366.3192390
Bianchi FMargara APezze M(2018)A Survey of Recent Trends in Testing Concurrent Software SystemsIEEE Transactions on Software Engineering10.1109/TSE.2017.270708944:8(747-783)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1109/TSE.2017.2707089
Bianchi FPezzè MTerragni VBodden ESchäfer WDeursen AZisman A(2017)Reproducing concurrency failures from crash stacksProceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering10.1145/3106237.3106292(705-716)Online publication date: 21-Aug-2017
https://dl.acm.org/doi/10.1145/3106237.3106292
Choudhary ALu SPradel MUchitel SOrso ARobillard M(2017)Efficient detection of thread safety violations via coverage-guided generation of concurrent testsProceedings of the 39th International Conference on Software Engineering10.1109/ICSE.2017.32(266-277)Online publication date: 20-May-2017
https://dl.acm.org/doi/10.1109/ICSE.2017.32
Scott CPanda ABrajkovic VNecula GKrishnamurthy AShenker SArgyraki KIsaacs R(2016)Minimizing faulty executions of distributed systemsProceedings of the 13th Usenix Conference on Networked Systems Design and Implementation10.5555/2930611.2930631(291-309)Online publication date: 16-Mar-2016
https://dl.acm.org/doi/10.5555/2930611.2930631
Guo SKusano MWang CLo DApel SKhurshid S(2016)Conc-iSE: incremental symbolic execution of concurrent softwareProceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering10.1145/2970276.2970332(531-542)Online publication date: 25-Aug-2016
https://dl.acm.org/doi/10.1145/2970276.2970332
Kang YZhou YXu HLyu MZimmermann TCleland-Huang JSu Z(2016)DiagDroid: Android performance diagnosis via anatomizing asynchronous executionsProceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering10.1145/2950290.2950316(410-421)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1145/2950290.2950316

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