Metamorphic testing

Last updated

Metamorphic testing (MT) is a property-based software testing technique, which can be an effective approach for addressing the test oracle problem and test case generation problem. The test oracle problem is the difficulty of determining the expected outcomes of selected test cases or to determine whether the actual outputs agree with the expected outcomes.

Contents

Metamorphic relations (MRs) are necessary properties of the intended functionality of the software, and must involve multiple executions of the software. Consider, for example, a program that implements sin x correct to 100 significant figures; a metamorphic relation for sine functions is "sin (π − x) = sin x". Thus, even though the expected value of sin x1 for the source test case x1 = 1.234 correct to the required accuracy is not known, a follow-up test case x2 = π− 1.234 can be constructed. We can verify whether the actual outputs produced by the program under test from the source test case and the follow-up test case are consistent with the MR in question. Any inconsistency (after taking rounding errors into consideration) indicates a failure [1] : 31  of the program, caused by a fault [1] : 31  in the implementation.

MRs are not limited to programs with numerical inputs or equality relations. As an example, when testing a booking website, a web search for accommodation in Sydney, Australia, returns 1,671 results; are the results of this search correct and complete? This is a test oracle problem. Based on a metamorphic relation, we may filter the price range or star rating and apply the search again; it should return a subset of the previous results. A violation of this expectation would similarly reveal a failure of the system.

Metamorphic testing was invented by T.Y. Chen in the technical report [2] in 1998. Since then, more than 150 international researchers and practitioners have applied the technique to real-life applications. Some examples include web services, [3] computer graphics, [4] embedded systems, [5] simulation and modeling, [6] machine learning, [7] decision support, [8] bioinformatics, [9] components, [10] numerical analysis, [11] and compilers. [12] The first major survey of the field of MT was conducted in 2016. [13] It was followed by another major survey in 2018, [14] which highlights the challenges and opportunities and clarifies common misunderstandings.

Although MT was initially proposed as a software verification technique, it was later developed into a paradigm that covers verification, validation, and other types of software quality assessment. [15] MT can be applied independently, and can also be combined with other static and dynamic software analysis techniques such as proving and debugging. [16]

In August 2018, Google acquired GraphicsFuzz, a startup from Imperial College London, to apply metamorphic testing to graphics device drivers for Android smartphones. [17] [18]

See also

Related Research Articles

Code review is a software quality assurance activity in which one or more people check a program, mainly by viewing and reading parts of its source code, either after implementation or as an interruption of implementation. At least one of the persons must not have authored the code. The persons performing the checking, excluding the author, are called "reviewers".

Peter Pin-Shan Chen is a Taiwanese American computer scientist. He is a (retired) distinguished career scientist and faculty member at Carnegie Mellon University and Distinguished Chair Professor Emeritus at LSU. He is known for the development of the entity–relationship model in 1976.

In programming and software development, fuzzing or fuzz testing is an automated software testing technique that involves providing invalid, unexpected, or random data as inputs to a computer program. The program is then monitored for exceptions such as crashes, failing built-in code assertions, or potential memory leaks. Typically, fuzzers are used to test programs that take structured inputs. This structure is specified, e.g., in a file format or protocol and distinguishes valid from invalid input. An effective fuzzer generates semi-valid inputs that are "valid enough" in that they are not directly rejected by the parser, but do create unexpected behaviors deeper in the program and are "invalid enough" to expose corner cases that have not been properly dealt with.

Search-based software engineering (SBSE) applies metaheuristic search techniques such as genetic algorithms, simulated annealing and tabu search to software engineering problems. Many activities in software engineering can be stated as optimization problems. Optimization techniques of operations research such as linear programming or dynamic programming are often impractical for large scale software engineering problems because of their computational complexity or their assumptions on the problem structure. Researchers and practitioners use metaheuristic search techniques, which impose little assumptions on the problem structure, to find near-optimal or "good-enough" solutions.

Virgil Dorin Gligor is a Romanian-American professor of electrical and computer engineering who specializes in the research of network security and applied cryptography.

Jock D. Mackinlay is an American information visualization expert and Vice President of Research and Design at Tableau Software. With Stuart Card, George G. Robertson and others he invented a number of information visualization techniques.

In computing, software engineering, and software testing, given an input for a system a test oracle is a procedure that distinguishes between the correct and incorrect behaviors of the System Under Test (SUT). The use of oracles involves comparing the output(s) of the system under test, for a given test-case input, to the output(s) that the oracle determines that product should have. The term "test oracle" was first introduced in a paper by William E. Howden. Additional work on different kinds of oracles was explored by Elaine Weyuker.

In computing, compiler correctness is the branch of computer science that deals with trying to show that a compiler behaves according to its language specification. Techniques include developing the compiler using formal methods and using rigorous testing on an existing compiler.

Philip S. Yu is an American computer scientist and professor of information technology at the University of Illinois at Chicago. He is a prolific author, holds over 300 patents, and is known for his work in the field of data mining.

<span class="mw-page-title-main">T.H. Tse</span>

T.H. Tse is a Hong Kong academic who is a professor and researcher in program testing and debugging. He is ranked internationally as the second most prolific author in metamorphic testing. According to Bruel et al., "Research on integrated formal and informal techniques can trace its roots to the work of T.H. Tse in the mid-eighties." The application areas of his research include object-oriented software, services computing, pervasive computing, concurrent systems, imaging software, and numerical programs. In addition, he creates graphic designs for non-government organizations.

<span class="mw-page-title-main">American Fuzzy Lop (software)</span> Software fuzzer that employs genetic algorithms

American Fuzzy Lop (AFL), stylized in all lowercase as american fuzzy lop, is a free software fuzzer that employs genetic algorithms in order to efficiently increase code coverage of the test cases. So far it has detected dozens of significant software bugs in major free software projects, including X.Org Server, PHP, OpenSSL, pngcrush, bash, Firefox, BIND, Qt, and SQLite.

Automatic bug-fixing is the automatic repair of software bugs without the intervention of a human programmer. It is also commonly referred to as automatic patch generation, automatic bug repair, or automatic program repair. The typical goal of such techniques is to automatically generate correct patches to eliminate bugs in software programs without causing software regression.

Differential testing, also known as differential fuzzing, is a popular software testing technique that attempts to detect bugs, by providing the same input to a series of similar applications, and observing differences in their execution. Differential testing complements traditional software testing, because it is well-suited to find semantic or logic bugs that do not exhibit explicit erroneous behaviors like crashes or assertion failures. Differential testing is sometimes called back-to-back testing.

Zehra Meral Özsoyoglu is a Turkish-American computer scientist specializing in databases, including research on query languages, database model, and indexes, and applications of databases in science, bioinformatics, and medical informatics. She is the Andrew R. Jennings Professor Emeritus of Computer Science at Case Western Reserve University.

Gregg Evan Rothermel is an American computer scientist, software engineer and academic born in March 1959 living in Apex, North Carolina. He is Professor and Head of the Department of Computer Science at North Carolina State University. Rothermel is still working as a professor, even though he has reached the full retirement age, given that he is older than 65 years old.

Tsong Yueh Chen is an Australian academic at the Swinburne University of Technology who is a professor and researcher in program testing and debugging. He is ranked internationally as the most prolific author in metamorphic testing.

References

  1. 1 2 610.12-1990 - IEEE Standard Glossary of Software Engineering Terminology, IEEE, 1990, doi:10.1109/IEEESTD.1990.101064, ISBN   9781559370677
  2. ↑ T.Y. Chen; S.C. Cheung; S.M. Yiu (1998), "Metamorphic testing: A new approach for generating next test cases", Technical Report HKUST-CS98-01 (PDF), Department of Computer Science, The Hong Kong University of Science and Technology, Hong Kong, arXiv: 2002.12543 .
  3. ↑ C. Castro-Cabrera and I. Medina-Bulo, "An approach to metamorphic testing for WS-BPEL compositions", in Proceedings of the International Conference on e-Business, IEEE (2011).
  4. ↑ R. Guderlei and J. Mayer, "Towards automatic testing of imaging software by means of random and metamorphic testing", International Journal of Software Engineering and Knowledge Engineering 17 (6): 757−781 (2007).
  5. ↑ T.H. Tse, S.S. Yau, W.K. Chan, H. Lu, and T.Y. Chen, "Testing context-sensitive middleware-based software applications", in Proceedings of the 28th Annual International Computer Software and Applications Conference (COMPSAC '04), vol. 1, IEEE Computer Society, pp. 458−465 (2004).
  6. ↑ S. Segura, R.M. Hierons, D. Benavides, and A. Ruiz-Cortes, "Automated test data generation on the analyses of feature models: a metamorphic testing approach", in Proceedings of the 3rd International Conference on Software Testing, Verification, and Validation (ICST '10), IEEE Computer Society, pp. 35−44 (2010).
  7. ↑ J. Ding, X.-H. Hu, and V. Gudivada, "A machine learning based framework for verification and validation of massive scale image data", IEEE Transactions on Big Data (2017). doi: 10.1109/TBDATA.2017.2680460.
  8. ↑ F.-C. Kuo, Z.Q. Zhou, J. Ma, and G. Zhang, "Metamorphic testing of decision support systems: A case study", IET Software 4 (4): 294−301 (2010).
  9. ↑ L.L. Pullum and O. Ozmen, "Early results from metamorphic testing of epidemiological models", in Proceedings of the 2012 ASE/IEEE International Conference on BioMedical Computing (BioMedCom '12), IEEE Computer Society, pp. 62−67 (2012).
  10. ↑ S. Beydeda, "Self-metamorphic-testing components", in Proceedings of the 30th Annual International Computer Software and Applications Conference (COMPSAC '06), vol. 1, IEEE Computer Society, pp. 265−272 (2006).
  11. ↑ C. Aruna and R.S.R. Prasad, "Metamorphic relations to improve the test accuracy of multi precision arithmetic software applications", in Proceedings of the 2014 International Conference on Advances in Computing, Communications and Informatics (ICACCI '14), IEEE (2014).
  12. ↑ C. Lidbury, A. Lascu, N. Chong, and A.F. Donaldson, "Many-core compiler fuzzing", in Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '15), ACM, pp. 65−76 (2015).
  13. ↑ S. Segura, G. Fraser, A.B. Sanchez, and A. Ruiz-Cortes, "A survey on metamorphic testing", IEEE Transactions on Software Engineering 42 (9}: 805-824 (2016).
  14. ↑ T.Y. Chen, F.-C. Kuo, H. Liu, P.-L. Poon, D. Towey, T.H. Tse, and Z.Q. Zhou, "Metamorphic testing: A review of challenges and opportunities", ACM Computing Surveys 51 (1): 4:1-4:27 (2018).
  15. ↑ Z.Q. Zhou, S. Xiang, and T.Y. Chen, "Metamorphic testing for software quality assessment: A study of search engines", IEEE Transactions on Software Engineering 42 (3): 264-28s4 (2016).
  16. ↑ T.Y. Chen, T.H. Tse, and Z.Q. Zhou, "Semi-proving: an integrated method for program proving, testing, and debugging", IEEE Transactions on Software Engineering 37 (1): 109-125 (2011).
  17. ↑ "GraphicsFuzz is acquired by Google". GraphicsFuzz. 6 August 2018. Retrieved 23 December 2020.
  18. ↑ "Google buys GraphicsFuzz, bringing fuzzy logic and metamorphic testing to Android graphics drivers". Packt. 8 August 2018. Retrieved 27 December 2020.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.