research-article

MR-Scout: Automated Synthesis of Metamorphic Relations from Existing Test Cases

Authors:

Valerio Terragni,

Shing-Chi CheungAuthors Info & Claims

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

Article No.: 150, Pages 1 - 28

https://doi.org/10.1145/3656340

Published: 29 June 2024 Publication History

Abstract

Metamorphic Testing (MT) alleviates the oracle problem by defining oracles based on metamorphic relations (MRs) that govern multiple related inputs and their outputs. However, designing MRs is challenging, as it requires domain-specific knowledge. This hinders the widespread adoption of MT. We observe that developer-written test cases can embed domain knowledge that encodes MRs. Such encoded MRs could be synthesized for testing not only their original programs but also other programs that share similar functionalities.

In this article, we propose MR-Scout to automatically synthesize MRs from test cases in open-source software (OSS) projects. MR-Scout first discovers MR-encoded test cases (MTCs), and then synthesizes the encoded MRs into parameterized methods (called codified MRs), and filters out MRs that demonstrate poor quality for new test case generation. MR-Scout discovered over 11,000 MTCs from 701 OSS projects. Experimental results show that over 97% of codified MRs are of high quality for automated test case generation, demonstrating the practical applicability of MR-Scout. Furthermore, codified-MRs-based tests effectively enhance the test adequacy of programs with developer-written tests, leading to 13.52% and 9.42% increases in line coverage and mutation score, respectively. Our qualitative study shows that 55.76% to 76.92% of codified MRs are easily comprehensible for developers.

References

[1]

John Ahlgren, Maria Eugenia Berezin, Kinga Bojarczuk, Elena Dulskyte, Inna Dvortsova, Johann George, Natalija Gucevska, Mark Harman, Maria Lomeli, Erik Meijer, Silvia Sapora, and Justin Spahr-Summers. 2021. Testing web enabled simulation at scale using metamorphic testing. In Proceedings of the 43rd IEEE/ACM International Conference on Software Engineering: Software Engineering in Practice, ICSE (SEIP) 2021. IEEE, 140–149. DOI:DOI:

Digital Library

[2]

Leonhard Applis, Annibale Panichella, and Arie van Deursen. 2021. Assessing robustness of ML-based program analysis tools using metamorphic program transformations. In Proceedings of the 36th IEEE/ACM International Conference on Automated Software Engineering, ASE 2021. IEEE, 1377–1381. DOI:DOI:

Digital Library

[3]

Andrea Arcuri and Lionel C. Briand. 2014. A Hitchhiker’s guide to statistical tests for assessing randomized algorithms in software engineering. Softw. Test. Verification Reliab. 24, 3 (2014), 219–250. DOI:DOI:

Digital Library

[4]

Jon Ayerdi, Valerio Terragni, Aitor Arrieta, Paolo Tonella, Goiuria Sagardui, and Maite Arratibel. 2021. Generating metamorphic relations for cyber-physical systems with genetic programming: An industrial case study. In Proceedings of the 29th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering. Diomidis Spinellis, Georgios Gousios, Marsha Chechik, and Massimiliano Di Penta (Eds.), ACM, 1264–1274. DOI:DOI:

Digital Library

[5]

Jon Ayerdi, Valerio Terragni, Aitor Arrieta, Paolo Tonella, Goiuria Sagardui, and Maite Arratibel. 2022. Evolutionary generation of metamorphic relations for cyber-physical systems. In Proceedings of the Genetic and Evolutionary Computation Conference, Companion Volume. Jonathan E. Fieldsend and Markus Wagner (Eds.), ACM, 15–16. DOI:DOI:

Digital Library

[6]

Arianna Blasi, Alessandra Gorla, Michael D. Ernst, Mauro Pezzè, and Antonio Carzaniga. 2021. MeMo: Automatically identifying metamorphic relations in Javadoc comments for test automation. J. Syst. Softw. 181 (2021), 111041. DOI:DOI:

Digital Library

[7]

Hudson Borges and Marco Túlio Valente. 2018. What’s in a GitHub star? Understanding repository starring practices in a social coding platform. J. Syst. Softw. 146 (2018), 112–129. DOI:DOI:

[8]

Cristian Cadar and Koushik Sen. 2013. Symbolic execution for software testing: three decades later. Commun. ACM 56, 2 (2013), 82–90. DOI:DOI:

Digital Library

[9]

Jialun Cao, Meiziniu Li, Yeting Li, Ming Wen, Shing-Chi Cheung, and Haiming Chen. 2022. SemMT: A semantic-based testing approach for machine translation systems. ACM Trans. Softw. Eng. Methodol. 31, 2 (2022), 34e:1–34e:36. DOI:DOI:

Digital Library

[10]

T. Y. Chen, S. C. Cheung, and S. M. Yiu. 1998. Metamorphic Testing: A New Approach for Generating Next Test Cases. Technical Report. Technical Report HKUST-CS98-01, Department of Computer Science, The Hong Kong University of Science and Technology.

[11]

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 Comput. Surv. 51, 1 (2018), 4:1–4:27. DOI:DOI:

Digital Library

[12]

Tsong Yueh Chen, Pak-Lok Poon, and Xiaoyuan Xie. 2016. METRIC: METamorphic relation identification based on the category-choice framework. J. Syst. Softw. 116 (2016), 177–190. DOI:DOI:

Digital Library

[13]

Pedro Delgado-Pérez, Aurora Ramírez, Kevin J. Valle-Gómez, Inmaculada Medina-Bulo, and José Raúl Romero. 2023. InterEvo-TR: Interactive evolutionary test generation with readability assessment. IEEE Trans. Software Eng. 49, 4 (2023), 2580–2596. DOI:DOI:

Digital Library

[14]

Alastair F. Donaldson. 2019. Metamorphic testing of Android graphics drivers. In Proceedings of the 4th International Workshop on Metamorphic Testing, MET@ICSE 2019. Xiaoyuan Xie, Pak-Lok Poon, and Laura L. Pullum (Eds.), IEEE / ACM, 1. DOI:DOI:

Digital Library

[15]

Alastair F. Donaldson and Andrei Lascu. 2016. Metamorphic testing for (graphics) compilers. In Proceedings of the 1st International Workshop on Metamorphic Testing, MET@ICSE 2016. ACM, 44–47. DOI:DOI:

Digital Library

[16]

EvoSuite. 2023. EvoSuite. Retrieved August 20, 2023 from https://www.evosuite.org/

[17]

Gordon Fraser and Andrea Arcuri. 2011. EvoSuite: Automatic test suite generation for object-oriented software. In Proceedings of the 19th ACM SIGSOFT Symposium on the Foundations of Software Engineering (FSE-19) and 13th European Software Engineering Conference (ESEC-13). Tibor Gyimóthy and Andreas Zeller (Eds.), ACM, 416–419. DOI:DOI:

Digital Library

[18]

Gordon Fraser and Andrea Arcuri. 2013. EvoSuite: On the challenges of test case generation in the real world. In Proceedings of the 6th IEEE International Conference on Software Testing, Verification and Validation, ICST 2013. IEEE Computer Society, 362–369. DOI:DOI:

Digital Library

[19]

Gordon Fraser and Andrea Arcuri. 2013. Whole test suite generation. IEEE Trans. Software Eng. 39, 2, 276–291. DOI:DOI:

Digital Library

[20]

Gordon Fraser and Andreas Zeller. 2011. Generating parameterized unit tests. In Proceedings of the 20th International Symposium on Software Testing and Analysis, ISSTA 2011. Matthew B. Dwyer and Frank Tip (Eds.), ACM, 364–374. DOI:DOI:

Digital Library

[21]

Alessio Gambi, Gunel Jahangirova, Vincenzo Riccio, and Fiorella Zampetti. 2022. SBST tool competition 2022. In Proceedings of the 15th IEEE/ACM International Workshop on Search-Based Software Testing, SBST@ICSE 2022. IEEE, 25–32. DOI:DOI:

Digital Library

[22]

GitHub. 2023. GitHub. Retrieved August 20, 2023 from https://github.com/

[23]

Grammarly. 2023. Grammarly. Retrieved August 20, 2023 from http://grammarly.com

[24]

Mark Harman, Yue Jia, and Yuanyuan Zhang. 2015. Achievements, open problems and challenges for search based software testing. In Proceedings of the 8th IEEE International Conference on Software Testing, Verification and Validation, ICST 2015. IEEE Computer Society, 1–12. DOI:DOI:

[25]

N. Alan Heckert, James J. Filliben, C. M. Croarkin, B. Hembree, William F. Guthrie, P. Tobias, and J. Prinz. 2002. Handbook 151: Nist/sematech e-handbook of statistical methods. (2002).

[26]

Kaifeng Huang, Bihuan Chen, Congying Xu, Ying Wang, Bowen Shi, Xin Peng, Yijian Wu, and Yang Liu. 2022. Characterizing usages, updates and risks of third-party libraries in Java projects. Empir. Softw. Eng. 27, 4 (2022), 90. DOI:DOI:

Digital Library

[27]

Gunel Jahangirova, David Clark, Mark Harman, and Paolo Tonella. 2016. Test oracle assessment and improvement. In Proceedings of the 25th International Symposium on Software Testing and Analysis, ISSTA 2016. Andreas Zeller and Abhik Roychoudhury (Eds.), ACM, 247–258. DOI:DOI:

Digital Library

[28]

Junit. 2023. Junit4. Retrieved August 20, 2023 from https://junit.org/junit4/javadoc/4.13/org/junit/Assert.html

[29]

Junit. 2023. Junit5. Retrieved August 20, 2023 from https://junit.org/junit5/

[30]

Junit. 2023. Junit5 Assertions. Retrieved August 20, 2023 from https://junit.org/junit5/docs/5.0.3/api/org/junit/jupiter/api/Assertions.html

[31]

Alexander Kampmann and Andreas Zeller. 2019. Carving parameterized unit tests. In Proceedings of the 41st International Conference on Software Engineering: Companion Proceedings, ICSE 2019. Joanne M. Atlee, Tevfik Bultan, and Jon Whittle (Eds.), IEEE/ACM, 248–249. DOI:DOI:

Digital Library

[32]

Upulee Kanewala and James M. Bieman. 2013. Using machine learning techniques to detect metamorphic relations for programs without test oracles. In Proceedings of the IEEE 24th International Symposium on Software Reliability Engineering, ISSRE 2013. IEEE Computer Society, 1–10. DOI:DOI:

[33]

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

Digital Library

[34]

Yun Lin, You Sheng Ong, Jun Sun, Gordon Fraser, and Jin Song Dong. 2021. Graph-based seed object synthesis for search-based unit testing. In Proceedings of the 29th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering. Diomidis Spinellis, Georgios Gousios, Marsha Chechik, and Massimiliano Di Penta (Eds.), ACM, 1068–1080. DOI:DOI:

Digital Library

[35]

Mikael Lindvall, Adam A. Porter, Gudjon Magnusson, and Christoph Schulze. 2017. Metamorphic model-based testing of autonomous systems. In Proceedings of the 2nd IEEE/ACM International Workshop on Metamorphic Testing, MET@ICSE 2017. IEEE Computer Society, 35–41. DOI:DOI:

[36]

Haoyang Ma, Qingchao Shen, Yongqiang Tian, Junjie Chen, and Shing-Chi Cheung. 2023. Fuzzing Deep Learning Compilers with HirGen. In Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis. 248–260. DOI:DOI:

Digital Library

[37]

Pingchuan Ma, Shuai Wang, and Jin Liu. 2020. Metamorphic testing and certified mitigation of fairness violations in NLP models. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, IJCAI 2020. Christian Bessiere (Ed.), ijcai.org, 458–465. DOI:DOI:

[38]

OpenAI. 2023. ChatGPT. Retrieved August 20, 2023 from https://openai.com/blog/chatgpt

[39]

Oracle. 2023. Java Language Specification. Retrieved August 20, 2023 from https://docs.oracle.com/javase/specs/

[40]

Carlos Pacheco and Michael D. Ernst. 2007. Randoop: Feedback-directed random testing for Java. In Proceedings of the Companion to the 22nd Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2007. Richard P. Gabriel, David F. Bacon, Cristina Videira Lopes, and Guy L. Steele Jr. (Eds.), ACM, 815–816. DOI:DOI:

Digital Library

[41]

Matteo Paltenghi and Michael Pradel. 2023. MorphQ: Metamorphic testing of the qiskit quantum computing platform. In Proceedings of the 45th IEEE/ACM International Conference on Software Engineering, ICSE 2023. IEEE, 2413–2424. DOI:DOI:

Digital Library

[42]

PITest. 2023. PITest. Retrieved August 20, 2023 from https://pitest.org/

[43]

Kun Qiu, Zheng Zheng, Tsong Yueh Chen, and Pak-Lok Poon. 2022. Theoretical and empirical analyses of the effectiveness of metamorphic relation composition. IEEE Trans. Software Eng. 48, 3 (2022), 1001–1017. DOI:DOI:

[44]

John A. Rice. 2006. Mathematical Statistics and Data Analysis. Cengage Learning.

[45]

Sergio Segura, Amador Durán, Javier Troya, and Antonio Ruiz Cortés. 2017. A template-based approach to describing metamorphic relations. In Proceedings of the 2nd IEEE/ACM International Workshop on Metamorphic Testing, MET@ICSE 2017. IEEE Computer Society, 3–9. DOI:DOI:

[46]

Sergio Segura, Gordon Fraser, Ana Belén Sánchez, and Antonio Ruiz Cortés. 2016. A survey on metamorphic testing. IEEE Trans. Software Eng. 42, 9 (2016), 805–824. DOI:DOI:

[47]

Sergio Segura, José Antonio Parejo, Javier Troya, and Antonio Ruiz Cortés. 2018. Metamorphic testing of RESTful web APIs. In Proceedings of the 40th International Conference on Software Engineering, ICSE 2018. Michel Chaudron, Ivica Crnkovic, Marsha Chechik, and Mark Harman (Eds.), ACM, 882. DOI:DOI:

Digital Library

[48]

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

[49]

Chang-Ai Sun, Yiqiang Liu, Zuoyi Wang, and W. K. Chan. 2016. \(\mu\)MT: A data mutation directed metamorphic relation acquisition methodology. In Proceedings of the 1st International Workshop on Metamorphic Testing, MET@ICSE 2016. ACM, 12–18. DOI:DOI:

Digital Library

[50]

Valerio Terragni, Gunel Jahangirova, Paolo Tonella, and Mauro Pezzè. 2020. Evolutionary improvement of assertion oracles. In Proceedings of the 28th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering. Prem Devanbu, Myra B. Cohen, and Thomas Zimmermann (Eds.), ACM, 1178–1189. DOI:DOI:

Digital Library

[51]

TestNG. 2023. TestNG. Retrieved August 20, 2023 from https://testng.org

[52]

Suresh Thummalapenta, Madhuri R. Marri, Tao Xie, Nikolai Tillmann, and Jonathan de Halleux. 2011. Retrofitting unit tests for parameterized unit testing. In Proceedings of the 14th International Conference on Fundamental Approaches to Software Engineering, FASE 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011. Dimitra Giannakopoulou and Fernando Orejas (Eds.), Lecture Notes in Computer Science, Vol. 6603. Springer, 294–309. DOI:DOI:

[53]

Yongqiang Tian, Shiqing Ma, Ming Wen, Yepang Liu, Shing-Chi Cheung, and Xiangyu Zhang. 2021. To what extent do DNN-based image classification models make unreliable inferences? Empir. Softw. Eng. 26, 4 (2021), 84. DOI:DOI:

Digital Library

[54]

MR-Scout. 2023. MR-Scout. Retrieved August 20, 2023 from https://mr-scout.github.io

[55]

Shuai Wang and Zhendong Su. 2020. Metamorphic object insertion for testing object detection systems. In Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering. 1053–1065. DOI:DOI:

Digital Library

[56]

Ying Wang, Bihuan Chen, Kaifeng Huang, Bowen Shi, Congying Xu, Xin Peng, Yijian Wu, and Yang Liu. 2020. An empirical study of usages, updates and risks of third-party libraries in Java projects. In Proceedings of the IEEE International Conference on Software Maintenance and Evolution, ICSME 2020. IEEE, 35–45. DOI:DOI:

[57]

Dongwei Xiao, Zhibo Liu, Yuanyuan Yuan, Qi Pang, and Shuai Wang. 2022. Metamorphic testing of deep learning compilers. Proc. ACM Meas. Anal. Comput. Syst. 6, 1 (2022), 15:1–15:28. DOI:DOI:

Digital Library

[58]

Bo Zhang, Hongyu Zhang, Junjie Chen, Dan Hao, and Pablo Moscato. 2019. Automatic discovery and cleansing of numerical metamorphic relations. In Proceedings of the 2019 IEEE International Conference on Software Maintenance and Evolution, ICSME 2019. IEEE, 235–245. DOI:DOI:

[59]

Jie Zhang, Junjie Chen, Dan Hao, Yingfei Xiong, Bing Xie, Lu Zhang, and Hong Mei. 2014. Search-based inference of polynomial metamorphic relations. In Proceedings of the ACM/IEEE International Conference on Automated Software Engineering, ASE ’14. Ivica Crnkovic, Marsha Chechik, and Paul Grünbacher (Eds.), ACM, 701–712. DOI:DOI:

Digital Library

[60]

Zhi Quan Zhou, Liqun Sun, Tsong Yueh Chen, and Dave Towey. 2020. Metamorphic relations for enhancing system understanding and use. IEEE Trans. Software Eng. 46, 10 (2020), 1120–1154. DOI:DOI:

[61]

Hengcheng Zhu, Lili Wei, Ming Wen, Yepang Liu, Shing-Chi Cheung, Qin Sheng, and Cui Zhou. 2020. MockSniffer: Characterizing and recommending mocking decisions for unit tests. In Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering, ASE 2020. IEEE, 436–447. DOI:DOI:

Digital Library

Cited By

Xu CChen SWu JCheung STerragni VZhu HCao JFilkov VRay BZhou M(2024)MR-Adopt: Automatic Deduction of Input Transformation Function for Metamorphic TestingProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3696020(557-569)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3696020

Index Terms

MR-Scout: Automated Synthesis of Metamorphic Relations from Existing Test Cases
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

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 ...
A New Method for Constructing Metamorphic Relations
QSIC '12: Proceedings of the 2012 12th International Conference on Quality Software

A fundamental problem for software testing is the oracle problem, which means that in many practical situations, it is extremely expensive, if not impossible, to verify the test result given any possible program input. Metamorphic testing is an approach ...
On Testing Effectiveness of Metamorphic Relations: A Case Study
SSIRI '11: Proceedings of the 2011 Fifth International Conference on Secure Software Integration and Reliability Improvement

One fundamental challenge for software testing is the oracle problem, which means that either there does not exist a mechanism (called oracle) to verify the test output given any possible program input, or it is very expensive, if not impossible, to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Software Engineering and Methodology

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

July 2024

951 pages

EISSN:1557-7392

DOI:10.1145/3613693

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: 29 June 2024

Online AM: 09 April 2024

Accepted: 20 March 2024

Revised: 05 January 2024

Received: 23 August 2023

Published in TOSEM Volume 33, Issue 6

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation of China
Hong Kong Research Grant Council/General Research Fund
Hong Kong Research Grant Council/Research Impact Fund

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
369
Total Downloads

Downloads (Last 12 months)369
Downloads (Last 6 weeks)32

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xu CChen SWu JCheung STerragni VZhu HCao JFilkov VRay BZhou M(2024)MR-Adopt: Automatic Deduction of Input Transformation Function for Metamorphic TestingProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3696020(557-569)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3696020

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