research-article

An Interleaving Guided Metamorphic Testing Approach for Concurrent Programs

Authors:

Tsong Yueh Chen,

Jinqiu WangAuthors Info & Claims

ACM Transactions on Software Engineering and Methodology, Volume 33, Issue 1

Article No.: 8, Pages 1 - 21

https://doi.org/10.1145/3607182

Published: 23 November 2023 Publication History

Abstract

Concurrent programs are normally composed of multiple concurrent threads sharing memory space. These threads are often interleaved, which may lead to some non-determinism in execution results, even for the same program input. This poses huge challenges to the testing of concurrent programs, especially on the test result verification—that is, the prevalent existence of the oracle problem. In this article, we investigate the application of metamorphic testing (MT), a mainstream technique to address the oracle problem, into the testing of concurrent programs. Based on the unique features of interleaved executions in concurrent programming, we propose an extended notion of metamorphic relations, the core part of MT, which are particularly designed for the testing of concurrent programs. A comprehensive testing approach, namely ConMT, is thus developed and a tool is built to automate its implementation on concurrent programs written in Java. Empirical studies have been conducted to evaluate the performance of ConMT, and the experimental results show that in addition to addressing the oracle problem, ConMT outperforms the baseline traditional testing techniques with respect to a higher degree of automation, better bug detection capability, and shorter testing time. It is clear that ConMT can significantly improve the cost-effectiveness for the testing of concurrent programs and thus advances the state of the art in the field. The study also brings novelty into MT, hence promoting the fundamental research of software testing.

References

[1]

John Ahlgren, Maria Berezin, Kinga Bojarczuk, Elena Dulskyte, Inna Dvortsova, Johann George, Natalija Gucevska, et al. 2021. Testing web enabled simulation at scale using metamorphic testing. In Proceedings of the IEEE/ACM 43rd International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP’21). 140–149.

Digital Library

[2]

Andrea Arcuri and Lionel Briand. 2011. A practical guide for using statistical tests to assess randomized algorithms in software engineering. In Proceedings of the 33rd International Conference on Software Engineering (ICSE’11). IEEE, Los Alamitos, CA, 1–10.

Digital Library

[3]

Earl T. Barr, Mark Harman, Phil McMinn, Muzammil Shahbaz, and Shin Yoo. 2015. The oracle problem in software testing: A survey. IEEE Transactions on Software Engineering 41, 5 (2015), 507–525.

Digital Library

[4]

Francesco Adalberto Bianchi, Alessandro Margara, and Mauro Pezzè. 2017. A survey of recent trends in testing concurrent software systems. IEEE Transactions on Software Engineering 44, 8 (2017), 747–783.

Digital Library

[5]

Pierre Bourqueand Richard E. Fairley (Eds.). 2014. SWEBOC V3.0: Guide to the Software Engineering Body of Knowledge. IEEE, Los Alamitos, CA.

[6]

Yan Cai, Hao Yun, Jinqiu Wang, Lei Qiao, and Jens Palsberg. 2021. Sound and efficient concurrency bug prediction. In Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE’21). 255–267.

Digital Library

[7]

W. K. Chan, T. Y. Chen, S. C. Cheung, T. H. Tse, and Zhenyu Zhang. 2007. Towards the testing of power-aware software applications for wireless sensor networks. In Reliable Software Technologies—Ada Europe 2007). Lecture Notes in Computer Science, Vol. 4498. Springer, 84–99.

[8]

W. K. Chan, S. C. Cheung, and Karl R. P. H. Leung. 2005. Towards a metamorphic testing methodology for service-oriented software applications. In Proceedings of the 5th International Conference on Quality Software (QSIC’05). 470–476.

Digital Library

[9]

Tsong Yueh Chen, Joshua W. K. Ho, Huai Liu, and Xiaoyuan Xie. 2009. An innovative approach for testing bioinformatics programs using metamorphic testing. BMC Bioinformatics 10, 1 (2009), 24–32.

[10]

Tsong Yueh Chen, Fei-Ching Kuo, Huai Liu, Pak-Lok Poon, Dave Towey, T. H. Tse, and Zhi Quan Zhou. 2018. Metamorphic testing: A review of challenges and opportunities. ACM Computing Surveys 51, 1 (2018), Article 4, 27 pages.

[11]

M. C. de Castro-Cabrera, A. García-Domínguez, and I. Medina-Bulo. 2019. Using constraint solvers to support metamorphic testing. In Proceeding of the IEEE/ACM 4th International Workshop on Metamorphic Testing (MET’19). 32–39.

Digital Library

[12]

J. Ding, T. Wu, J. Q. Lu, and X. Hu. 2010. Self-checked metamorphic testing of an image processing program. In Proceedings of the 4th International Conference on Secure Software Integration and Reliability Improvement (SSIRI’10). 190–197.

Digital Library

[13]

Anurag Dwarakanath, Sanjay Podder, Neville Dubash, Kishore P. Durg, Manish Ahuja, Raghotham M. Rao, Samarth Sikand, and Jagadeesh Chandra Bose Rantham Prabhakara. 2019. Verification by metamorphic testing of applications that utilize artificial intelligence. US Patent 20190108443. Filed Sept. 28, 2018. Issued Oct. 8, 2019.

[14]

Yaniv Eytani, Klaus Havelund, Scott D. Stoller, and Shmuel Ur. 2007. Towards a framework and a benchmark for testing tools for multi-threaded programs. Concurrency and Computation: Practice and Experience 19, 3 (2007), 267–279.

Digital Library

[15]

Yaniv Eytani and Shmuel Ur. 2004. Compiling a benchmark of documented multi-threaded bugs. In Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS’04). IEEE, Los Alamitos, CA, 266.

[16]

Cormac Flanagan and Stephen N. Freund. 2004. Atomizer: A dynamic atomicity checker for multithreaded programs. In Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’04). 256–267.

Digital Library

[17]

Cormac Flanagan and Stephen N. Freund. 2009. FastTrack: Efficient and precise dynamic race detection. In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’09). 121–133.

Digital Library

[18]

Patrice Godefroid. 1997. Model checking for programming languages using VeriSoft. In Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’97). 174–186.

Digital Library

[19]

Patrice Godefroid and Nachi Nagappan. 2008. Concurrency at Microsoft: An Exploratory Survey. Technical Report MSR-TR-2008-75. Microsoft. https://www.microsoft.com/en-us/research/publication/concurrency-at-microsoft-an-exploratory-survey/.

[20]

Brian Goetz, Tim Peierls, Doug Lea, Joshua Bloch, Joseph Bowbeer, and David Holmes. 2006. Java Concurrency in Practice. Pearson Education.

Digital Library

[21]

GraphicsFuzz. 2018. GraphicsFuzz is acquired by Google. GraphicsFuzz. Retrieved February 16, 2021 from https://www.graphicsfuzz.com/.

[22]

R. Hamlet. 2002. Random Testing. Retrieved July 9, 2023 from

[23]

Christian Hammer, Julian Dolby, Mandana Vaziri, and Frank Tip. 2008. Dynamic detection of atomic-set-serializability violations. In Proceedings of the 30th International Conference on Software Engineering (ICSE’08). 231–240.

Digital Library

[24]

S. Y. Huang. 2020. Maximal-Causality-Reduction (MCR) Java Version. Retrieved July 9, 2023 from https://github.com/parasol-aser/JMCR.

[25]

Shiyou Huang and Jeff Huang. 2017. Speeding up maximal causality reduction with static dependency analysis. In Proceedings of the 31st European Conference on Object-Oriented Programming (ECOOP’17).

[26]

Jacob Jackson. 2012. Nasdaq’s Facebook glitch came from ‘race conditions’. COMPUTERWORLD. Retrieved February 16, 2021 from https://www.computerworld.com/article/2504676/nasdaq-s-facebook-glitch-came-from--race-conditions-.html.

[27]

Pallavi Joshi, Chang-Seo Park, Koushik Sen, and Mayur Naik. 2009. A randomized dynamic program analysis technique for detecting real deadlocks. In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’09). 110–120.

Digital Library

[28]

JUnit. 2020. Junit 5. Retrieved July 9, 2023 from https://junit.org/junit5/.

[29]

Christian Gram Kalhauge and Jens Palsberg. 2018. Sound deadlock prediction. Proceedings of the ACM on Programming Languages 2, OOPSLA (2018), 1–29.

Digital Library

[30]

Upulee Kanewala, James M. Bieman, and Asa Ben-Hur. 2016. Predicting metamorphic relations for testing scientific software: A machine learning approach using graph kernels. Software Testing, Verification and Reliability 26, 3 (2016), 245–269.

Digital Library

[31]

Z. F. Lai, S. C. Cheung, and W. K. Chan. 2010. Detecting atomic-set serializability violations in multithreaded programs through active randomized testing. In Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering (ICSE’10). 235–244.

Digital Library

[32]

Leslie Lamport. 1978. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM 21, 7 (1978), 558–565.

Digital Library

[33]

Vu Le, Mehrdad Afshari, and Zhendong Su. 2014. Compiler validation via equivalence modulo inputs. ACM SIGPLAN Notices 49 (2014), 216–226.

[34]

N. G. Leveson and C. S. Turner. 1993. An investigation of the Therac-25 accidents. Computer 26, 7 (1993), 18–41.

Digital Library

[35]

M. Lindvall, D. Ganesan, R. Árdal, and R. E. Wiegand. 2015. Metamorphic model-based testing applied on NASA DAT—An experience report. In Proceeding of the 37th IEEE International Conference on Software Engineering (ICSE’15). 129–138.

[36]

Huai Liu, Fei-Ching Kuo, Dave Towey, and Tsong Yueh Chen. 2014. How effectively does metamorphic testing alleviate the oracle problem? IEEE Transactions on Software Engineering 40, 1 (2014), 4–22.

Digital Library

[37]

B. Lucia, J. Devietti, K. Strauss, and L. Ceze. 2008. Atom-Aid: Detecting and surviving atomicity violations. In Proceedings of the 35th International Symposium on Computer Architecture (ISCA’08). 277–288.

Digital Library

[38]

Linhai Ma, Peng Wu, and Tsong Yueh Chen. 2018. Diversity driven adaptive test generation for concurrent data structures. Information and Software Technology 103 (2018), 162–173.

[39]

Umang Mathur, Dileep Kini, and Mahesh Viswanathan. 2018. What happens-after the first race? Enhancing the predictive power of happens-before based dynamic race detection. Proceedings of the ACM on Programming Languages 2, OOPSLA (2018), 1–29.

Digital Library

[40]

N. Mouha, M. S. Raunak, D. R. Kuhn, and R. Kacker. 2018. Finding bugs in cryptographic hash function implementations. IEEE Transactions on Reliability 67, 3 (2018), 870–884.

[41]

J. Oberg. 1999. Why the Mars probe went off course [accident investigation]. IEEE Spectrum 36, 12 (1999), 34–39.

Digital Library

[42]

Robert O’Callahan and Jong-Deok Choi. 2003. Hybrid dynamic data race detection. In Proceedings of the 9th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP’03). ACM, New York, NY, 167–178.

Digital Library

[43]

Chang-Seo Park and Koushik Sen. 2008. Randomized active atomicity violation detection in concurrent programs. In Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of Software Engineering (SIGSOFT’08/FSE-16). 135–145.

Digital Library

[44]

Andreas Pavlogiannis. 2019. Fast, sound and effectively complete dynamic race prediction. arXiv preprint arXiv: 1901.08857 (2019).

[45]

K. Qiu, Z. Zheng, T. Y. Chen, and P. Poon. 2022. Theoretical and empirical analyses of the effectiveness of metamorphic relation composition. IEEE Transactions on Software Engineering 48, 3 (2022), 1001–1017.

[46]

Malavika Samak and Murali Krishna Ramanathan. 2014. Trace driven dynamic deadlock detection and reproduction. In Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP’14). 29–42.

Digital Library

[47]

Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson. 1997. Eraser: A dynamic data race detector for multithreaded programs. ACM Transactions on Computing Systems 15, 4 (1997), 391–411.

Digital Library

[48]

Kevin Poulsen. 2004. Software bug contributed to blackout. The Register. Retrieved July 9, 2023 from https://www.theregister.com/2004/02/12/software_bug_contributed_to_blackout/.

[49]

Sergio Segura, Gordon Fraser, Ana B. Sanchez, and Antonio Ruiz-Cortés. 2016. A survey on metamorphic testing. IEEE Transactions on Software Engineering 42, 9 (2016), 805–824.

[50]

Koushik Sen. 2008. Race directed random testing of concurrent programs. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’08). 11–21.

Digital Library

[51]

Ohad Shacham, Mooly Sagiv, and Assaf Schuster. 2007. Scaling model checking of dataraces using dynamic information. Journal of Parallel and Distributed Computing 67, 5 (2007), 536–550.

Digital Library

[52]

Chang-Ai Sun, An Fu, Pak-Lok Poon, Xiaoyuan Xie, and Tsong Yueh Chen. 2021. METRIC+: A metamorphic relation identification technique based on input plus output domains. IEEE Transactions on Software Engineering 47, 9 (2021), 1764–1785.

[53]

Chang-Ai Sun, Guan Wang, Baohong Mu, Huai Liu, ZhaoShun Wang, and Tsong Yueh Chen. 2011. Metamorphic testing for web services: Framework and a case study. In Proceedings of the 9th IEEE International Conference on Web Services (ICWS’11). 283–290.

Digital Library

[54]

Chang-Ai Sun, Yan Zhao, Lin Pan, Xiao He, and Dave Towey. 2016. A transformation-based approach to testing concurrent programs using UML activity diagrams. Software: Practice and Experience 46, 4 (2016), 551–576.

Digital Library

[55]

Yuchi Tian, Kexin Pei, Suman Jana, and Baishakhi Ray. 2018. DeepTest: Automated testing of deep-neural-network-driven autonomous cars. In Proceedings of the 40th International Conference on Software Engineering (ICSE’18). 303–314.

Digital Library

[56]

T. H. Tse and S. S. Yau. 2004. Testing context-sensitive middleware-based software applications. In Proceedings of the 28th Annual International Computer Software and Applications Conference (COMPSAC’04). 458–466.

[57]

L. Wang and S. D. Stoller. 2006. Runtime analysis of atomicity for multithreaded programs. IEEE Transactions on Software Engineering 32, 2 (2006), 93–110.

Digital Library

[58]

Zan Wang, Yingquan Zhao, Shuang Liu, Jun Sun, Xiang Chen, and Huarui Lin. 2019. MAP-Coverage: A novel coverage criterion for testing thread-safe classes. In Proceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering (ASE’19). 722–734.

Digital Library

[59]

Yingquan Zhao, Zan Wang, Shuang Liu, Jun Sun, Junjie Chen, and Xiang Chen. 2023. Achieving high MAP-coverage through pattern constraint reduction. IEEE Transactions on Software Engineering 49, 1 (2023), 99–112.

[60]

Z. Q. Zhou, S. Xiang, and T. Y. Chen. 2016. Metamorphic testing for software quality assessment: A study of search engines. IEEE Transactions on Software Engineering 42, 3 (2016), 264–284.

Digital Library

Cited By

Zheng ZRen DLiu HChen TLi T(2024)Identifying the Failure-Revealing Test Cases in Metamorphic Testing: A Statistical ApproachACM Transactions on Software Engineering and Methodology10.1145/3695990Online publication date: 13-Sep-2024
https://doi.org/10.1145/3695990
Luo JShi HZhang YWang RShen YChen YShi XLiu RHu CJiang Yd'Amorim M(2024)CVECenter: Industry Practice of Automated Vulnerability Management for Linux Distribution CommunityCompanion Proceedings of the 32nd ACM International Conference on the Foundations of Software Engineering10.1145/3663529.3663852(329-339)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3663529.3663852
Ji YSun CZheng XLiu H(2024)MT4SC: A User-Behavior-Sequence-Aware Metamorphic Testing Approach for Smart Contracts2024 IEEE International Conference on Web Services (ICWS)10.1109/ICWS62655.2024.00118(992-1002)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ICWS62655.2024.00118

Index Terms

An Interleaving Guided Metamorphic Testing Approach for 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

Recommendations

Feedback-Directed Metamorphic Testing
Over the past decade, metamorphic testing has gained rapidly increasing attention from both academia and industry, particularly thanks to its high efficacy on revealing real-life software faults in a wide variety of application domains. On the basis of a ...
Metamorphic Testing: A Review of Challenges and Opportunities

Metamorphic testing is an approach to both test case generation and test result verification. A central element is a set of metamorphic relations, which are necessary properties of the target function or algorithm in relation to multiple inputs and ...
Accurate and efficient runtime detection of atomicity errors in concurrent programs
PPoPP '06: Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming

Atomicity is an important correctness condition for concurrent systems. Informally, atomicity is the property that every concurrent execution of a set of transactions is equivalent to some serial execution of the same transactions. In multi-threaded ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Software Engineering and Methodology

ACM Transactions on Software Engineering and Methodology Volume 33, Issue 1

January 2024

933 pages

EISSN:1557-7392

DOI:10.1145/3613536

Editor:
Mauro Pezzè
USI Universitá della Svizzera italiana and SIT Schaffhausen Institute of Technology, Switzerland

Issue’s Table of Contents

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 the author(s) 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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 November 2023

Online AM: 03 July 2023

Accepted: 12 June 2023

Revised: 06 May 2023

Received: 30 July 2022

Published in TOSEM Volume 33, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Natural Science Foundation of China
Fundamental Research Funds for the Central Universities
Beijing Natural Science Foundation
Aeronautical Science Foundation of China
Youth Innovation Promotion Association of the Chinese Academy of Sciences (YICAS)
Key Research Program of Frontier Sciences, CAS

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
551
Total Downloads

Downloads (Last 12 months)398
Downloads (Last 6 weeks)40

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zheng ZRen DLiu HChen TLi T(2024)Identifying the Failure-Revealing Test Cases in Metamorphic Testing: A Statistical ApproachACM Transactions on Software Engineering and Methodology10.1145/3695990Online publication date: 13-Sep-2024
https://doi.org/10.1145/3695990
Luo JShi HZhang YWang RShen YChen YShi XLiu RHu CJiang Yd'Amorim M(2024)CVECenter: Industry Practice of Automated Vulnerability Management for Linux Distribution CommunityCompanion Proceedings of the 32nd ACM International Conference on the Foundations of Software Engineering10.1145/3663529.3663852(329-339)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3663529.3663852
Ji YSun CZheng XLiu H(2024)MT4SC: A User-Behavior-Sequence-Aware Metamorphic Testing Approach for Smart Contracts2024 IEEE International Conference on Web Services (ICWS)10.1109/ICWS62655.2024.00118(992-1002)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ICWS62655.2024.00118

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents