Solving the Test Oracle Problem: Automatically find Regular Expressions (RegEx) that define applicability constraints for Metamorphic Relations (MRs)
Organization
Software Engineering Analytics
Abstract
According to Wikipedia, “Metamorphic testing (MT) is a property-based software testing technique, which can be an effective approach for addressing the test oracle and, thus, automatic test case generation problem. A Metamorphic Relation (MR) defines for a Software Under Test (SUT) how for a valid input x the output y = SUT(x) must change if x is modified, i.e., what properties must apply to y’ = SUT(x’) where x’ results from applying a specific transformation f on x, i.e., x’ = f(x). If for all valid inputs x the resulting outputs y fulfil the given MR, then there is no reason to assume the SUT is faulty (assuming the MR is actually applicable).
The problem with MT is that it is not easy to find a sufficiently large set of applicable MRs to a specific SUT. Much domain knowledge is needed to handcraft good MRs that can be used for generating a strong test suite. Since it is rarely the case that an MR holds universally for all valid inputs x, and to have a richer set of applicable MRs, one might define that an MR must only hold for a subset of all valid inputs (i.e., only for positive numbers or for all numbers but 0).
To overcome these problems, one might try to select suitable MRs from a large set of empirically known MRs. A first and easy to apply filter for automatic selection of MRs from this large set is that only those MRs are chosen that syntactically match the signature (or API) of a function or SUT. Once the syntactically applicable MRs can be automatically applied to the SUT using a fuzzer. For each applied MR, several observations can be made (and recorded): a) For all inputs x, the corresponding outputs y fulfill the properties defined by the MR, or b) For none of the inputs x, the corresponding y fulfill the properties, or c) for some x the corresponding y fulfill and for some they don’t fulfill the properties.
The two extreme cases a) and b) can easily exploited for building regression test suites (i.e., after sufficient trust has been built into the correctness of the SUT). However, the MRs that fall under case c) are difficult to reuse, because it is unclear whether the choice of a not yet tried x’ must produce an output y’ that fulfills or that doesn’t fulfill the property defined by the MR. In other words, it is difficult to describe the input space T that corresponds to the partition where y’ fulfills the property and what is the input space F that doesn’t.
The idea of this thesis topic is to derive RegEx that would define the two partitions of the input space based on the data available from the executed tests using the fuzzer and violation/non-violation of the MR information. A solution to this problem might involve Generative AI.
In the context of the Regex Golf challenge similar problems have been tackled (see: https://link.springer.com/article/10.1007/s10710-021-09411-x)
The goal of this thesis project is to devise a method and develop a supporting tool that helps testers to semi-automatically derive regression test suites for a given SUT starting out from a set of MRs and using a fuzzer (see: https://www.fuzzingbook.org). The resulting method and tool must be evaluated.
References:
•\tde Almeida Farzat, A., de Oliveira Barros, M. Automatic generation of regular expressions for the Regex Golf challenge using a local search algorithm. Genet Program Evolvable Mach 23, 105–131 (2022). https://doi.org/10.1007/s10710-021-09411-x
•\tT.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.
The problem with MT is that it is not easy to find a sufficiently large set of applicable MRs to a specific SUT. Much domain knowledge is needed to handcraft good MRs that can be used for generating a strong test suite. Since it is rarely the case that an MR holds universally for all valid inputs x, and to have a richer set of applicable MRs, one might define that an MR must only hold for a subset of all valid inputs (i.e., only for positive numbers or for all numbers but 0).
To overcome these problems, one might try to select suitable MRs from a large set of empirically known MRs. A first and easy to apply filter for automatic selection of MRs from this large set is that only those MRs are chosen that syntactically match the signature (or API) of a function or SUT. Once the syntactically applicable MRs can be automatically applied to the SUT using a fuzzer. For each applied MR, several observations can be made (and recorded): a) For all inputs x, the corresponding outputs y fulfill the properties defined by the MR, or b) For none of the inputs x, the corresponding y fulfill the properties, or c) for some x the corresponding y fulfill and for some they don’t fulfill the properties.
The two extreme cases a) and b) can easily exploited for building regression test suites (i.e., after sufficient trust has been built into the correctness of the SUT). However, the MRs that fall under case c) are difficult to reuse, because it is unclear whether the choice of a not yet tried x’ must produce an output y’ that fulfills or that doesn’t fulfill the property defined by the MR. In other words, it is difficult to describe the input space T that corresponds to the partition where y’ fulfills the property and what is the input space F that doesn’t.
The idea of this thesis topic is to derive RegEx that would define the two partitions of the input space based on the data available from the executed tests using the fuzzer and violation/non-violation of the MR information. A solution to this problem might involve Generative AI.
In the context of the Regex Golf challenge similar problems have been tackled (see: https://link.springer.com/article/10.1007/s10710-021-09411-x)
The goal of this thesis project is to devise a method and develop a supporting tool that helps testers to semi-automatically derive regression test suites for a given SUT starting out from a set of MRs and using a fuzzer (see: https://www.fuzzingbook.org). The resulting method and tool must be evaluated.
References:
•\tde Almeida Farzat, A., de Oliveira Barros, M. Automatic generation of regular expressions for the Regex Golf challenge using a local search algorithm. Genet Program Evolvable Mach 23, 105–131 (2022). https://doi.org/10.1007/s10710-021-09411-x
•\tT.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.
Graduation Theses defence year
2024-2025
Supervisor
Dietmar Pfahl
Spoken language (s)
English
Requirements for candidates
Level
Masters
Keywords
Application of contact
Name
Dietmar Pfahl
Phone
E-mail