too expensive to be used. Metamorphic testing is a testing

How Effectively Does Metamorphic Testing Alleviate the Oracle Problem? Huai Liu, Member, IEEE, Fei-Ching Kuo, Member, IEEE, Dave Towey, Member, IEEE, and Tsong Yueh Chen, Member, IEEE Abstract—In software testing, something which can verify the correctness of test case execution results is called an oracle. The oracle problem occurs when either an oracle does not exist, or exists but is too expensive to be used. Metamorphic testing is a testing approach which uses metamorphic relations, properties of the software under test represented in the form of relations among inputs and outputs of multiple executions, to help verify the correctness of a program. This paper presents new empirical evidence to support this approach, which has been used to alleviate the oracle problem in various applications and to enhance several software analysis and testing techniques. It has been observed that identification of a sufficient number of appropriate metamorphic relations for testing, even by inexperienced testers, was possible with a very small amount of training. Furthermore, the cost-effectiveness of the approach could be enhanced through the use of more diverse metamorphic relations. The empirical studies presented in this paper clearly show that a small number of diverse metamorphic relations, even those identified in an ad hoc manner, had a similar fault-detection capability to a test oracle, and could thus effectively help alleviate the oracle problem. Index Terms—Software testing, test oracle, oracle problem, metamorphic testing, metamorphic relation Ç 1 INTRODUCTION THE scale and use of software systems around the world have been growing exponentially, yet at the same time, reports of problems due to software faults have also been growing. Software quality assurance has become one of the most important areas in the software industry as well as in the academic community. Software testing, a major approach in software quality assurance, is widely acknowledged as a critical activity and a main research focus in software engineering [18]. One of the objectives of software testing is to detect as many software faults as possible, and to do so as quickly as possible [33]. Although many effective test case selection strategies have been proposed [11], [14], the majority of these strategies rely on the availability of a test oracle [20], a mechanism which can systematically verify the correctness of a test result for any given test case (input). Only with a test oracle can it be clearly claimed that the output of the program under test passes or fails for any given input. In many situations, however, a test oracle either does not exist, or is too expensive to be used. This problem, referred to as the oracle problem, is a fundamental challenge for software testing, because it significantly restricts the applicability and effectiveness of most test case selection strategies. Metamorphic testing [5] is an approach to alleviating the oracle problem. In metamorphic testing, some necessary properties (hereafter referred to as metamorphic relations) are identified for the software under test, usually from the software specifications. These metamorphic relations provide a new perspective on verifying test results. Traditionally, after a test case is executed, its corresponding test output is verified using a test oracle. Unlike traditional testing, metamorphic testing always involves multiple test case executions, with their corresponding outputs being verified using the metamorphic relations rather than a test oracle. Metamorphic testing has been applied in various application domains, successfully detecting faults [6], [25], [32], [37], [40], and has also been integrated with other software analysis and testing technologies to extend their applicability to those programs without test oracles [4], [10], [41]. The effectiveness of metamorphic relations has been studied, with attempts made to establish guidelines for the selection of “good” metamorphic relations [7], [29]. Studies [21], [42] have also been conducted comparing metamorphic testing with other techniques, such as assertion checking, for alleviating the oracle problem. There remain, however, some as yet unanswered, fundamental research questions related to metamorphic testing, such as: whether, and to what extent, metamorphic relations can alleviate the oracle problem; how many metamorphic relations are required to match the fault-detection effectiveness of a test oracle; and what are the key factors that influence the effectiveness of metamorphic testing. This paper presents an investigation of these questions through a series of empirical studies. The remainder of the paper is organized as follows: In Section 2, the procedure and background information for metamorphic testing are  H. Liu is with Australia-India Centre for Automation Software Engineering, RMIT University, Melbourne 3001 VIC, Australia. E-mail: [email protected]  F.-C. Kuo and T.Y. Chen are with the Faculty of Information and Communication Technologies, Swinburne University of Technology, Hawthorn 3122 VIC, Australia. E-mail: {dkuo, tychen}@swin.edu.au.  D. Towey is with the Division of Computer Science, The University of Nottingham, Ningbo, 315100, Zhejiang, China. E-mail: [email protected] Manuscript received 13 Feb. 2013; revised 28 July 2013; accepted 14 Sept. 2013; date of publication 27 Sep. 2013; date of current version 24 Feb. 2014. Recommended for acceptance by P. Tonella. For information on obtaining reprints of this article, please send e-mail to: [email protected], and reference the Digital Object Identifier below. Digital Object Identifier no. 10.1109/TSE.2013.46 4 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 40, NO. 1, JANUARY 2014 0098-5589  2014 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. presented. Work related to metamorphic testing is discussed in Section 3. In Section 4, the three fundamental research questions in this study are explained. Details of the empirical studies are presented in Section 5, the results of which, and the answers to the research questions, are reported in Section 6. In Section 7, potential threats to the validity of this study are discussed. Finally, Section 8 summarizes the paper. 2 METAMORPHIC TESTING The basic steps for implementing metamorphic testing are as follows: 1. Some necessary properties of the software under test are identified (normally extracted from the specifications), and represented in the form of relations, referred to as metamorphic relations. Each metamorphic relation involves multiple test case inputs and their corresponding outputs. 2. Some test cases, referred to as the source test cases, are generated using traditional test case selection strategies. 3. New test cases, called the follow-up test cases, are constructed from the source test cases according to the metamorphic relations. 4. Both source and follow-up test cases are applied to the software under test. 5. The test case outputs are checked against the relevant metamorphic relations to confirm whether the relations are satisfied, or have been violated. The following example illustrates how metamorphic testing works. Suppose that a program P searches for the shortest path between two nodes in an undirected graph. One metamorphic relation of P is that if the start and goal nodes are swapped, the length of the shortest path should remain unchanged. Suppose that a source test case ðG; a; bÞ is selected according to some testing strategy, where G is an undirected graph, and a and b are the start and goal nodes, respectively. According to the metamorphic relation, a follow-up test case ðG; b; aÞ can be constructed. After the execution of both test cases, the outputs can be checked against the relation by confirming whether or not jPðG; a; bÞj ¼ jPðG; b; aÞj is satisfied (where jj denotes the length of a path). If the relation has been violated, it can be
concluded that P is faulty. Metamorphic testing is not only simple in concept, but once the metamorphic relations have been identified, it can also be easily automated. Since metamorphic testing first appeared, it has been widely applied in various application domains. Murphy et al. [32] developed a framework for implementing metamorphic testing in machine learning; their framework includes a degree of automation, and can also be applied in other disciplines. Segura et al. [37] applied metamorphic testing to the analysis of feature models. Furthermore, metamorphic testing has detected real-life faults in a number of programs, including a bioinformatics program [6], two C compilers [40], a wireless metering system [25], and three programs in the popular Siemens suite (schedule, schedule2, and print_tokens) [35], [41] which have been extensively used and tested in the literature [13]. The detection of these faults proves that metamorphic testing has brought a new perspective to testing, not only for test result verification, but also for test case generation. In other words, metamorphic testing can be viewed as a test case selection method complementary to existing methods. Metamorphic testing has also been integrated with other software analysis and testing techniques. Beydeda [4], for example, presented an approach integrating the self-testing COTS components method with metamorphic testing, which, because metamorphic testing provided an automatic way for test result verification, significantly enhanced the COTS self-testability. Chen et al. [10] integrated metamorphic testing with symbolic execution, resulting in a method which can help verify program correctness with respect to certain necessary properties. The method also provided some important and useful information to support debugging. Gotlieb and Botella [17] developed an automatic testing framework by combining metamorphic testing with constraint logic programming. Xie et al. [41] applied metamorphic testing to fault localization, and proposed a methodology that supports spectrum-based fault localization without the need for a test oracle. Their investigations included the development of metamorphic slicing, an integration of metamorphic relations with slicing techniques. 3 RELATED WORK An approach to addressing the oracle problem may involve the construction of oracles from formal specifications. Hierons [20], for example, developed algorithms for two types of conformance relations to test physically distributed systems using the framework of finite state machines. However, such an approach requires specifications expressed in a formal notation, which is not always feasible. Compared with this, metamorphic testing is a more generic approach, because it is applicable regardless of how the specifications are written. The assertion checking technique [36] uses assertions, normally embedded in the source code during the programming phase. These assertions are constraints on specific portions of the source code, which, when the program is executed, help detect software faults that violate the constraints at runtime. With assertion checking, a fault could be revealed with a single execution of the program under test, whereas metamorphic testing always requires multiple executions. The fault-detection capability of assertion checking has been compared with that of metamorphic testing [21], [42]. It has been demonstrated that metamorphic testing consistently detects more faults than assertion checking, but may incur additional overheads. Different from these studies, in the current paper we attempt to directly compare the fault-detection effectiveness of metamorphic testing with that of a test oracle, and thus answer more fundamental research questions, such as, whether or not metamorphic testing really provides an effective mechanism for imitating a test oracle. As will be discussed in Section 5.3, random testing with a base program as the oracle is used to simulate the automatic test result verification against an oracle, and thus provides a benchmark for evaluating the effectiveness of metamorphic testing. LIU ET AL.: HOW EFFECTIVELY DOES METAMORPHIC TESTING ALLEVIATE THE ORACLE PROBLEM? 5 Another approach to alleviating the oracle problem has been to use multiple versions of the program under test to play the role of test oracle. Manolache and Kourie [28] achieved this using N-version programming [2], which was originally designed as a fault tolerance technique. They developed a so-called M-mp testing strategy, in which M (M  1) “model programs” are used together with the program under test to construct “an approximate test oracle.” Such an approach, however, is not always reliable: Knight and Leveson [24] have reported that different versions of a program may not be developed independently. Furthermore, there is also the possibility of faults common to all versions appearing. Ammann and Knight [1] proposed the fault tolerance technique of data diversity for situations where one and only one version of a program exists. Their method requires an input t to be “reexpressed” into t0, where t0 and t contain the same information, but in different forms. For example, since a property of sine is that for a given angle t, sinðtÞ ¼ sinð  tÞ; if P is a program which calculates the sine value of t, and outputs a value greater than 1 (which obviously shows that P does not compute this input correctly), then input t0 is set to ð  tÞ, and executed, hopefully resulting in a correct output. However, this technique was designed with the assumed existence of a test oracle, and, given the nature of fault tolerance, has the constraint that only the equality relation is allowed. Recently, the mutation analysis technique [12] was used to help construct test oracles. Staats et al. [38] proposed a mutation-based method for automatically selecting some variables to construct a test oracle, however, such a method assumed the existence of an oracle—among all well-defined internal state or output variables, it selects some which show high effectiveness in killing mutants. Fraser and Zeller [16] investigated how to generate unit tests and oracles based on a mutation technique, but the oracles defined in their method are effectively a list of assertions. Our study focuses on whether, and to what extent, metamorphic testing effectively alleviates the oracle problem. Thus, rather than comparing metamorphic testing with other techniques, we concentrate on evaluating its effectiveness against the benchmark provided by a simulated and automated oracle— which is actually random testing applied to a base program, as explained in Section 5.3. Some relatively simple ways to detect faults without a complete test oracle also exist. Testers can use as inputs, some “special” values for which the expected outputs are well-known (e.g., sinð=2Þ must be 1). However, the applicability of such special case testing is very limited. Another method is to reveal faults by causing the program under test to crash (have an execution error, such as segmentation fault, infinite loop, divide-by-zero, etc). Although such an approach has successfully revealed faults [15], [30], [31], only certain types of faults can be detected. In addition to research into the application of metamorphic testing, studies of its core components, metamorphic relations, have also been conducted. Chen et al. [7] investigated how to distinguish metamorphic relations with better fault-detection potential. They suggested that testers should understand not only the application domain, but also the algorithm’s structure, and reported that for “good” metamorphic relations, the execution behavior of the source test case should be very different from that of the follow-up test case. In addition, Mayer and Guderlei [29] examined several determinant computation programs to identify their metamorphic relations, finding that relations with rich semantic properties had better fault-detection effectiveness. Although there have already been many studies of vario
us aspects of metamorphic testing, to date, no work has been done to evaluate how effectively metamorphic relations may be able to approach the fault-finding efficiency of a test oracle. This paper attempts to answer the research questions surrounding this issue through a series of empirical studies. 4 RESEARCH QUESTIONS This section summarizes the fundamental research questions for metamorphic testing, and how they will be answered through the empirical studies.  RQ1: How effectively can metamorphic relations detect software faults? Metamorphic relations, the core components of metamorphic testing, provide a test result verification mechanism which can imitate a test oracle. Their fault-detection effectiveness is the major factor determining to what extent metamorphic testing can alleviate the oracle problem. In the empirical studies presented in this paper, the fault-detection effectiveness of metamorphic relations was evaluated from the following perspectives: the performance of each individual metamorphic relation was measured according to the number of faults it revealed; the total number of faults revealed by all identified metamorphic relations for a subject program was calculated; and finally, the relationship between the number of metamorphic relations used and the overall fault-detection effectiveness was analyzed. Through the investigation of RQ1, not only can we qualitatively assess how effectively metamorphic testing alleviates the oracle problem, but we can also quantitatively evaluate how many metamorphic relations would normally be required to effectively imitate a test oracle, based on which some guidelines could be provided for applying metamorphic testing in practice. As detailed in Section 5.3, the effectiveness of metamorphic relations is evaluated against two benchmarks: random testing with and without an oracle. If a set of metamorphic relations can deliver a fault-detection effectiveness much higher than that of random testing without oracle, and similar to that of random testing with an oracle, they could be considered to effectively imitate a test oracle.  RQ2: How capable are testers of alleviating the oracle problem using metamorphic testing? Obviously, the applicability and effectiveness of a testing method depend on human factors, such as how easily testers can learn the method, and how effectively they can apply it. Previous studies [21], [42] have shown that it is not difficult for testers to understand the basic concept of metamorphic 6 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 40, NO. 1, JANUARY 2014 testing, and be able to identify some appropriate metamorphic relations. In this study, an in-depth analysis was conducted of how easily metamorphic testing is understood and applied, and also of the extent to which testers could use metamorphic testing to alleviate the oracle problem. This was done as follows: the number of faults detected by the metamorphic relations identified by each individual tester was measured; the overall performance of individual testing teams, each consisting of several testers, was examined; and the relationship between the fault-detection effectiveness and the number of testers involved was investigated.  RQ3: How can the cost-effectiveness of metamorphic testing be optimized? The two previous research questions focus on faultdetection effectiveness, which is measured as the number of detected faults. However, high faultdetection effectiveness may not be useful if its cost is too high. A good testing method should have high cost-effectiveness, that is, it should detect as many faults as possible at a relatively low cost. The costeffectiveness of metamorphic testing depends on the number of metamorphic relations and their faultdetection effectiveness. This study investigated the fundamental factors affecting the cost-effectiveness of metamorphic relations; a better understanding of these factors should make it possible to optimize the cost-effectiveness of metamorphic testing. 5 EXPERIMENT An empirical analysis was adopted to answer the research questions in Section 4. The design and settings of the experiments are described in this section. 5.1 Subject Programs and Mutant Generation When we selected the subject programs, a consideration was that for appropriate identification of proper metamorphic relations, the testers may need a significant amount of specific domain knowledge. Because there are many application domains (such as scientific computing, financial calculations, web services, database applications, image processing, clinical systems, etc), it is practically infeasible, if not impossible, to conduct an investigation for general domains—it is extremely difficult to recruit a sufficient number of testers with in-depth domain knowledge for the various applications—therefore, our investigation needed to be constrained to just a few domains. In the experiments, all the testers were university students in computer science and/or software engineering without any commercial experience. We selected the algorithmic programs for which the testers had sufficient domain knowledge to identify metamorphic relations. In addition, the subject programs were selected such that they were neither too complex nor too simple: If too complex, the experiment would have required a prohibitively long time, and this study aimed to complete both the training and experimental application, for each individual participant, within a single day. If too simple, the faults could easily have been detected by any testing method, and might thereby undermine the validity of the experiment. Five Java programs representing different application areas were selected as the subjects of the experiments (see Table 1). Understanding their specifications only required some basic knowledge of data structures and search algorithms, which the university students in these studies had already acquired. Mutants for the subject programs were generated automatically using muJava [27]. Since the focus was on the basic functionality of each program, not the class interfaces, only the “traditional” mutation operators (such as arithmetic operator replacement, relational operator replacement, etc.) were used to generate the mutants, each of which contained a single fault. It should also be noted that, like other specification-based techniques, the effectiveness of metamorphic testing is hindered if mistakes exist in the software’s specifications. Nevertheless, the subject program’s specifications were well-defined, with little ambiguity, and were examined very carefully before being distributed to the testers. Therefore, the possibility of problems in the specifications, and their potential impact on our study, were minimized. As will be discussed in Sections 5.2 and 6.1, the metamorphic relations identified in this study detected real-life faults in the original MultipleKnapsack [26] and SparseMatrixMultiply [22] programs. These faulty programs were fixed, and the corrected versions were then used as subjects in the study. 5.2 Metamorphic Relation Identification For each subject program, two testing teams were assigned to identify its metamorphic relations. Each team was composed of four to seven members, who were postgraduate or senior undergraduate students in computer science and/or software engineering from the same university. Although some of the students participating in the study had already learned some basic software testing concepts, they had neither the knowledge of metamorphic testing nor the practical experience in testing. Before working on the subject programs, all students were given a three-hour training session covering basic metamorphic testing concepts and some examples of metamorphic relations for TABLE 1 Subject Program Information LIU ET AL.: HOW EFFECTIVELY DOES METAMORPHIC TESTING ALLEVIATE THE ORACLE PROBLEM? 7 applications other than the subject programs. The training session consisted of a 90-minute tutorial and a 90-minute exercise. In the tutorial, a trainer (a coauthor of this paper) first gave a one-hour presentation on metamorphic testing and
metamorphic relations, during which several examples were used to illustrate the metamorphic relation identification. The trainer then hosted a 30-minute discussion session, during which the students were encouraged to raise any questions and to discuss the related topics. Next, to examine their understanding of the training content, the students were given an exercise involving the calculation of average, standard deviation, and median values for a set of real numbers. They were then asked to work individually to identify as many metamorphic relations as possible within a period of one hour. In the final 30 minutes, the trainer commented on the identified relations, discussing and providing feedback to the students. After the three-hour training, each student was next assigned up to two subject programs, for each of which they were asked to identify as many metamorphic relations as possible within 90 minutes. Students worked individually and independently during the metamorphic relation identification process: They were not permitted to communicate with each other. At this point, students who had been given the same subject program, and who came from the same university, were considered to form a testing team (even though they had not collaborated on the relations identification). To minimize the learning effects, we allocated the subject programs according to the following criteria: 1) Subject programs were given in different orders—for example, one team was required to first work on the MultipleKnapsack program, and then, after this, on a different program; at the same time, another team was given a different program, after they finished with which, they then worked on MultipleKnapsack. 2) Each pair of testing teams had at most one common subject program— no two testing teams were allocated exactly the same subject programs. For example, a testing team from University A worked on the SparseMatrixMultiply and FindKNN programs; while another testing team, from University B, worked on FindKNN and SetCover. After the identification process, the trainer (different testing teams may be associated with different trainers) checked all identified metamorphic relations, keeping the valid relations, and discarding all others. The checked results were then also confirmed by other trainers/coauthors, to further assure the correctness. Table 2 summarizes the results of the metamorphic relation identification process. In the table, the totals for metamorphic and invalid relations refer to distinct relations—for MinimizeDFA, for example, the testing team from University B identified eleven distinct metamorphic relations and two distinct invalid relations, and the team from University C identified 10 distinct metamorphic relations and two distinct invalid relations, but in total, only 16 distinct metamorphic relations and three distinct invalid relations were identified. From the table it can be observed that, on average, each student was able to identify two to six distinct metamorphic relations for each subject program, which is consistent with other studies involving ad hoc identification of metamorphic relations [21], [42]. It can also be observed that each testing team could identify seven to 18 distinct metamorphic relations for each program. Table 2 also shows that for each subject program, only up to three of the relations identified by the testers were not valid metamorphic relations. The average number of invalid relations was always less than one per tester, per subject program, and usually no greater than 0:5. Moreover, it was also easy for the trainer (who is very familiar with the specifications) to identify invalid relations, usually in less than a minute, simply by reading them. In other words, the impact of invalid relations was very small. As a reminder, the identification process was conducted in an ad hoc manner: The students were not taught any systematic method to generate the metamorphic relations. All identified metamorphic relations were first verified against the original programs. Surprisingly, this verification process revealed two real-life faults in MultipleKnapsack, and one fault in SparseMatrixMultiply (details are reported in Section 6.1)—in other words, the metamorphic relations, even defined in such an ad hoc way, were TABLE 2 Identification of Metamorphic Relations 8 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 40, NO. 1, JANUARY 2014 very effective at revealing real faults! After fixing these faults, since the corrected versions of these two programs, and the other three original subject programs, satisfied all metamorphic relations, they were referred to as the base programs in the experiments. 5.3 Random Testing with and without a Test Oracle The fault-detection effectiveness of metamorphic testing was evaluated against two benchmarks: random testing without a test oracle, referred to as RT in this paper; and random testing with a test oracle, referred to as RTo in this paper. Both of these methods show a high degree of testing automation—test case generation and test result verification are automated—with little human bias, and thus provide simple, but fair, comparison benchmarks for evaluating how effectively metamorphic testing alleviates the oracle problem. Intuitively speaking, the fault-detection effectiveness of RT should be the lower bound for the effectiveness of metamorphic testing: If the performance of metamorphic testing is similar to that of RT, then metamorphic testing cannot effectively alleviate the oracle problem. In the absence of a test oracle, as was the case with RT, a fault could only be revealed when the program crashed (refer to Section 3 for the definition of “crash”). Such a “crash only” verification scheme has been widely used in research into random testing without a test oracle [15], [30], [31]. Since, in addition to crashing the program, metamorphic testing uses the violation of metamorphic relations to detect faults, intuitively speaking, it should not perform worse than RT. On the other hand, RTo provides an upper bound for the fault-detection effectiveness of metamorphic testing: If a number of metamorphic relations can collectively detect a similar number of faults to RTo, then they could be considered to effectively imitate a test oracle. In RTo, the base program served as a test oracle to verify the results of mutants, as has been commonly adopted in other experiments using mutation analysis techniques [12]. In addition to crashing, for certain test cases, some mutants produced different outputs to the base program, in which case these mutants were said to be “killed” by these test cases. Both crashing and killing implied the detection of faults. In the testing, the following categories of fault-detection were of interest: 1) crashed only mutants that were not killed by any other test cases (hereafter referred to as crashed mutants); 2) crashed mutants that were also killed by some other test cases (hereafter referred to as crashed and killed mutants); and 3) non-crashed mutants that were killed by some test cases (hereafter referred to as killed mutants). RT could only identify mutants of category 1 (that is, crashed mutants), while both RTo and metamorphic testing could identify mutants of all three categories (that is, killed or crashed mutants). Note that RTo and metamorphic testing had slightly different meanings of “kill:” RTo killed a mutant when the mutant had an output different from that of the corresponding base program which was used as the test oracle; metamorphic testing killed a mutant when a metamorphic relation was violated by the outputs of some related source and follow-up test cases for that mutant. Suppose that nc mutants were crashed by RT, nkc mutants were killed or crashed by RTo, and nMT mutants were killed or crashed by metamorphic testing using a set of metamorphic relations. In order to quantitatively evaluate how effectively metamorphic testing imitates a test oracle, we introduce an oracle imitation measure (Moim), defined as follows: Moim ¼ nMT  nc
nkc  nc : (1) Note that (1) is applicable when nkc > nc. Theoretically speaking, although extremely unlikely, it is possible for nkc to equal nc, which would imply that all faults can be revealed by crashing alone, and thus neither an automated oracle nor metamorphic relations would improve the fault-detection effectiveness. If Moim approaches 0 (that is, nMT  nc), it means that metamorphic testing could not effectively alleviate the oracle problem. On the other hand, if Moim approaches 1 (that is, nMT  nkc), it implies that metamorphic testing could effectively imitate a test oracle. However, it should be pointed out that, as explained in Section 6, because metamorphic testing and RTo use different test cases in our experiments, metamorphic testing was able to detect more faults than RTo (that is, Moim was greater than 1 in some cases); in other words, the fault-detection effectiveness of RTo is only considered to be the theoretical upper bound. 5.4 Test Case Generation For each subject program, one thousand test cases were generated randomly according to uniform distribution using the pseudorandom number generator provided in the Java standard library. By uniform distribution, we mean that all possible program inputs had the same probability of being selected as test cases. For instance, the MultipleKnapsack program accepts three sets of integers as input: two n-tuple sets P ¼ fp1; p2; . . . ; png and W ¼ fw1; w2; . . . ; wng, which respectively represent the profits and weights of n items to be selected, and one mtuple set C ¼ fc1; c2; . . . ; cmg, which represents the capacities of m knapsacks to hold the selected items. The following procedure was implemented to generate the random test cases for MultipleKnapsack: First, randomly select the values for n and m. Second, randomly select the values of pi and wi for each of the n items (i ¼ 1; 2; . . . ; n). Third, randomly select the value of cj for each of the m knapsacks (j ¼ 1; 2; . . .;m). An example of the test cases randomly generated for MultipleKnapsack is as follows: P ¼ f95; 30; 93; 72; 19; 14; 68; 31; 56; 99g, W ¼ f46; 70; 91; 17; 80; 39; 88; 35; 24; 62g, and C ¼ f113; 129; 150g, where n ¼ 10, and m ¼ 3. All one thousand random test cases were used in the execution of RT and RTo. Metamorphic testing involves two types of test cases, the source and the follow-up. In the experiments, some of the one thousand random test cases were selected as the source test cases, based on which follow-up test cases were generated. In order to have a fair comparison with RT and RTo, both of which used one thousand random test cases, the total number of source and follow-up test cases was kept as close as possible to one thousand, without exceeding it, and the number of common test cases for metamorphic testing and RT/RTo was maximized. We applied the following settings in the experiments: Suppose a metamorphic relation requires ms source test LIU ET AL.: HOW EFFECTIVELY DOES METAMORPHIC TESTING ALLEVIATE THE ORACLE PROBLEM? 9 cases and mf follow-up test cases. When only one metamorphic relation was used in testing, the first b 1000 1þmf=ms c random test cases were used as source test cases. For example, suppose that MRa was used, and it required two source test cases and one follow-up test case. First, b 1000 1þ1=2c ¼ 666 random test cases were used as source test cases. Then, 333 follow- up test cases were generated, each of which was constructed from two source test cases according to MRa. Thus, a total of 999 (666 source þ333 follow-up) test cases were used for testing with MRa. When the testing of a subject program used multiple metamorphic relations, MR1, MR2, . . ., and MRn, each of which required mi s source test cases and mi f follow-up test cases (i ¼ 1; 2; . . . ; n), the first b 1000 1þPn i¼1 mi f =mi s c random test cases were used as source test cases. Based on the source test cases, follow-up test cases were constructed according to each of the relevant metamorphic relations. For example, suppose that two metamorphic relations, MRb and MRc, were used: MRb required one source test case and one follow- up test case; and MRc required one source test case and two follow-up test cases. First, b 1000 1þð1þ2Þc ¼ 250 random test cases were selected as source test cases. Next, each source test case was then used to construct one follow-up test case according to MRb, and two follow-up test cases according to MRc. This resulted in a total of 1; 000 test cases (250  (1 source þ1 follow-up for MRb þ2 follow-up for MRc)). As shown, this test case generation arrangement ensured that up to a thousand test cases were generated and executed for each run of metamorphic testing on an individual subject program. 6 EXPERIMENTAL RESULTS 6.1 Detection of Real-Life Faults The metamorphic relations identified by the testers were first tested on the original programs, surprisingly revealing real-life faults in the MultipleKnapsack and Sparse- MatrixMultiply programs, as detailed in this section. In the Java code of SparseMatrixMultiply [22], the 194th line was “ic[0] ¼ 1;”, but should have been “ic[1] ¼ 1;”. This fault was revealed by 17 of the 22 identified metamorphic relations. Nine of the 10 testers who had been assigned the SparseMatrixMultiply program identified metamorphic relations capable of revealing this fault. There were two faults found in the Java code of MultipleKnapsack [26]: one was on the 95th line, which was “q += origw[j]” but should have been “q þ ¼ origp[j];” and the other was on the 190th line, which was “idex1 ¼ aux[i]” but should have been “idx1 ¼ aux[1].” Of all 27 metamorphic relations identified for Multiple- Knapsack, 11 could reveal the first fault, and 19 could reveal the second. All nine testers who had been assigned MultipleKnapsack identified metamorphic relations that revealed the second fault; and seven testers identified relations that revealed the first. Previous studies of metamorphic testing have also reported revealing real-life faults, even for well-tested software, including three programs in the popular Siemens suite (schedule, schedule2, and print_tokens) [35], [41], C compilers [40], bioinformatics programs [6], and wireless embedded systems [25]. The detection of these real-life faults implies that in addition to alleviating the oracle problem, metamorphic testing is also an effective test case selection method complementary to existing methods. As a reminder, the mutation analysis in the following Sections (6.2 to 6.4) was based on the corrected versions of MultipleKnapsack and SparseMatrixMultiply, and the original versions of the other three programs. In other words, the base programs satisfied all the metamorphic relations before mutation began, and hence were used as test oracles in this analysis. 6.2 RQ1: Fault-Detection Effectiveness of Metamorphic Relations 6.2.1 Fault-Detection Effectiveness of Individual Metamorphic Relations Fig. 1 summarizes the fault-detection effectiveness of individual metamorphic relations compared with RT; with RTo; and with all identified metamorphic relations. In Fig. 1 (also in Figs. 3 and 4), crashed mutants are displayed as white boxes; crashed and killed mutants are displayed as black boxes on top of white ones; and killed mutants are displayed as gray boxes on top of black ones. As a reminder, since RT referred to random testing without a test oracle, it could only identify crashed mutants, while both RTo and metamorphic testing could kill mutants in addition to crashing. Because different test cases were used, the numbers of crashed mutants for metamorphic testing were not necessarily equal to those for RT (although they were quite similar): RT used the whole pool of the one thousand randomly generated test cases; while metamorphic testing used part of this random pool as source test cases, and generated new follow-up test cases. As can be observed from Fig. 1, apart from two metamorphic relations (MR13 for SparseMatrixMultiply and MR10 for FindKNN),
the overwhelming majority of the relations (97 out of 99) both killed and crashed mutants. In other words, it was very likely that metamorphic testing using a single metamorphic relation had a higher faultdetection effectiveness than RT. Hypothesis testing was conducted to verify whether this observation was statistically significant. The significance level was set to 0:05, and the null hypotheses (H0) were that each individual metamorphic relation had similar faultdetection effectiveness to RT. When the p-value was smaller than the significance level of 0:05, the null hypothesis was rejected; otherwise, it was accepted. The two-tailed t-tests results are reported in the second column of Table 3, in each cell of which, the decision (reject or accept) was given based on the p-value represented by the number in parentheses. It was shown that for each subject program, the null hypothesis was rejected. Based on these t-test results, and the data shown in Fig. 1, it can be concluded that even though the metamorphic relations were identified in an ad hoc way, each one by itself had significantly higher fault-detection effectiveness than RT. In summary, in this instance of the oracle problem, metamorphic relations definitely helped to reveal more faults than RT, which depended entirely on program “crashing” to reveal faults. 10 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 40, NO. 1, JANUARY 2014 The t-tests for the comparison between individual metamorphic relations and RTo are summarized in the third column of Table 3. Obviously, an arbitrary metamorphic relation could not be expected to outperform a test oracle, therefore an investigation was conducted into how well individual metamorphic relations could alleviate the oracle problem. A histogram analysis was used to quantitatively compare the fault-detection capabilities of the individual metamorphic relations and a test oracle. For each subject program, 10 groups of metamorphic relations were defined as follows: Each of the first 9 groups was defined as the group of metamorphic relations that individually has the value of Moim 2 ½ði  1Þ  0:1; i  0:1Þ, where i ¼ 1; 2; . . . ; 9. The 10th group contains the metamorphic relations that have Moim  0:9. Technically speaking, each group (with the exception of Group 10) represents a 10 percent difference in effectiveness between RT and RTo. The grouping of metamorphic relations is summarized in Table 4, where the number of metamorphic relations in each group for each program is given. For example, the value of “5” in the entry corresponding to Group 7 and the program MinimizeDFA means that there were five metamorphic relations for MinimizeDFA, each of which outperformed RT by 60 to 70 percent of the difference in effectiveness between RT and RTo. Based on Table 4, it can be observed that there were 19 metamorphic relations (Group 10, 19:19 percent of all), each of which outperformed RT by at least 90 percent of the difference in effectiveness between RT and RTo. Since 55.56 percent (ð6 þ 10 þ 8 þ 12 þ 19Þ=99) of the metamorphic relations are in Groups 6-10, this means that over half of identified metamorphic relations each achieved a faultdetection effectiveness at least half way between that of RT and that of RTo. 6.2.2 Fault-Detection Effectiveness When Using All Identified Metamorphic Relations We compared the fault-detection effectiveness of using all identified metamorphic relations with that of RTo and of RT, as summarized in Table 5. It can be observed that the use of all identified metamorphic relations always had much higher fault-detection effectiveness than RT. It can also be observed that when using all identified metamorphic relations, metamorphic testing killed or crashed a Fig. 1. Relationship between individual metamorphic relations and the number of killed/crashed mutants. TABLE 3 T-Tests for Comparing Individual Metamorphic Relations with RT and RTo H0: Each individual metamorphic relation had similar fault-detection effectiveness to RT/RTo. LIU ET AL.: HOW EFFECTIVELY DOES METAMORPHIC TESTING ALLEVIATE THE ORACLE PROBLEM? 11 similar (or sometimes even larger) number of mutants compared with RTo. For one program (FindKNN), the fault-detection effectiveness when using all identified metamorphic relations was only marginally lower than that of RTo (0:95 < Moim < 1). For another program (SetCover), the use of all identified metamorphic relations and RTo had exactly the same fault-detection effectiveness (Moim ¼ 1). For the remaining three programs (MinimizeDFA, MultipleKnapsack, and SparseMatrixMultiply), the use of all identified metamorphic relations was able to outperform RTo. Note that although RTo had been expected to play the role of an upper bound on performance, it was possible for metamorphic testing in this experiment to detect more faults than RTo because they used different test cases. In summary, the collection of all identified metamorphic relations, even though they were identified in an ad hoc way, can be regarded as an effective imitation for a test oracle. 6.2.3 Relationship between Fault-Detection Effectiveness and the Number of Metamorphic Relations Used in Metamorphic Testing Fig. 2 reports how many mutants for individual subject programs were killed or crashed when a certain number of metamorphic relations were used together in the testing. In Fig. 2, each box-plot represents the statistical distribution of the number of mutants killed or crashed by a given number of metamorphic relations (note that for this given number, there were various possible groups of metamorphic relations). The upper and lower bounds of the box denote the third and first quartile of the number of killed or crashed mutants, respectively, while the middle line inside the box represents the median value. The top and bottom whiskers denote the maximum and minimum values, respectively, and a square dot denotes the mean number of mutants killed or crashed by a given number of metamorphic relations. For ease of comparison, the fault-detection effectiveness of RTo and RT are given as the horizontal dot lines in Fig. 2. Fig. 2 shows a trend that when more metamorphic relations were used, not only were more mutants killed or crashed, but also the variation between the faultdetection capabilities of various groups of the same number of metamorphic relations decreased. In other words, with an increase in the number of metamorphic relations, the fault-detection effectiveness was not only increased, but also stabilized. Based on the data in Fig. 2, it is possible to calculate the average number (nMR) of metamorphic relations required to outperform RT by at least 90 percent of the difference in effectiveness between RT and RTo. It was found that for FindKNN, MinimizeDFA, MultipleKnapsack, SparseMatrixMultiply, and SetCover, nMR was 5 (31:25 percent of 16), 4 (25 percent of 16), 4 (14:81 percent of 27), 3 (13:63 percent of 22), and 6 (33:33 percent of 18), respectively. These results imply that even though 16 to 27 metamorphic relations were identified for each subject program in this investigation, it may not have been cost-effective to use all of them in the testing. For each program under investigation, there was a very good chance of outperforming RT by at least 90 percent of the difference in effectiveness between RT and RTo by using just three to six of the metamorphic relations. In other words, to imitate a test oracle, it may have been more cost-effective for metamorphic testing to use an arbitrary choice of at most a third of all the identified metamorphic relations—even though these relations were identified by different testers without extensive experience in testing. 6.3 RQ2: Capabilities of Testers 6.3.1 Capability of Individual Testers The fault-detection effectiveness of metamorphic relations identified by individual testers for each subject program is TABLE 4 Grouping of Metamorphic Relations, Comparing with RT and RTo TABLE 5 Fault-Detection Effectiveness for All Metamorphic Relations Compared with RTo/RT 12 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL.
40, NO. 1, JANUARY 2014 reported in Fig. 3, which, for ease of comparison, also includes the results for using all metamorphic relations, for RTo, and for RT. Fig. 3 clearly shows that each tester was able to identify metamorphic relations that were sufficient by themselves to reveal more faults than RT. It can also be observed that the fault-detection effectiveness of the identified metamorphic relations varied from tester to tester. Table 6 reports the results of two-tailed t-tests conducted to compare the faultdetection effectiveness of the metamorphic relations identified by each tester with RT and RTo. In the tests, the null hypotheses (H0) were that the group of metamorphic relations identified by an individual tester had similar faultdetection effectiveness to RT/RTo; the significance level was set to 0:05. As can be observed from Table 6 and Fig. 3, it is statistically significant that the metamorphic relations identified by a single tester detected more faults than RT. However, we could not obtain a general conclusion whether the metamorphic relations identified by a single tester were as effective as RTo with respect to the number of revealed faults. For two programs (MultipleKnapsack and SparseMatrixMultiply), there was no statistically significant difference between the fault-detection Fig. 2. Relationship between the number of metamorphic relations used and the number of killed/crashed mutants. LIU ET AL.: HOW EFFECTIVELY DOES METAMORPHIC TESTING ALLEVIATE THE ORACLE PROBLEM? 13 effectiveness of RTo and the metamorphic relations identified by a single tester; for the remaining three programs, it was statistically significant that RTo had higher faultdetection effectiveness than all the metamorphic relations identified by a single tester. A histogram analysis was again used to quantitatively compare the fault-detection capabilities of the metamorphic relations identified by a single tester and a test oracle (refer to Table 4 and related discussion in Section 6.2.1 for details of such a method and the grouping scheme). The grouping of the fault-detection effectiveness of testers is summarized in Table 7, where the number of testers in each group for each subject program is given. For example, the value of “2” in the entry corresponding to Group 9 and the program FindKNN means that there were two testers who individually identified a group of metamorphic relations for FindKNN that outperformed RT by 80 to 90 percent of the difference in effectiveness between RT and RTo. Table 7 shows that, on average, 58.82 percent (30=51) of testers identified metamorphic relations that outperformed RT by at least 90 percent of the difference in effectiveness Fig. 3. Relationship between metamorphic relations identified by the same tester and the number of killed/crashed mutants. 14 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 40, NO. 1, JANUARY 2014 between RT and RTo (that is, Group 10). 94.12 percent (ð3 þ 5 þ 2 þ 8 þ 30Þ=51, from Groups 6 to 10) of testers were able to identify metamorphic relations that achieved a fault-detection effectiveness half way between that of RT and that of RTo. In summary, although each tester was a student without training or experience in metamorphic testing prior to this experiment, and was asked to identify metamorphic relations in an independent and ad hoc way, the majority of these students performed well (achieving a fault-detection effectiveness at least half way between that of RT and that of RTo), and over half of them could use metamorphic testing to achieve a very high faultdetection effectiveness (improving on RT by at least 90 percent of the difference between RT and RTo). Nevertheless, no single tester applying metamorphic testing could guarantee that a sufficient number of metamorphic relations were identified to imitate an oracle: A testing team composed of different testers was required, as is discussed in the following. 6.3.2 Capability of Testing Teams In the experiments, every subject program was investigated by two testing teams, each of which consisted of four to seven students from the same university. Fig. 4 reports the fault-detection effectiveness of metamorphic relations with respect to the testing teams, and Table 8 compares this fault-detection effectiveness with that of RT and that of RTo. As can be observed from Table 8 and Fig. 4, each testing team always identified a set of metamorphic relations that were altogether more effective than RT at revealing faults. On the other hand, generally speaking, there was no significant difference between the fault-detection effectiveness of RTo and the metamorphic relations identified by a testing team. In other words, the set of metamorphic relations identified by a testing team effectively imitates a test oracle, in spite of the fact that the team consisted of inexperienced testers who identified the metamorphic relations in an individual and ad hoc way. 6.3.3 Relationship between Fault-Detection Effectiveness and the Number of Testers Fig. 5 reports the fault-detection effectiveness of metamorphic relations identified by a group of testers. Based on the data in Fig. 5, it is possible to calculate the average number of testers (ntr) required to identify a sufficient number of metamorphic relations to outperform RT by at least 90 percent of the difference in effectiveness between RT and RTo. It was found that ntr ¼ 2, 3, 1, 2, and 1, for FindKNN, MinimizeDFA, MultipleKnapsack, SparseMatrixMultiply, and SetCover, respectively. These results imply that if three testers were involved, then the metamorphic testing in this case could have been as effective as RTo. In other words, only a small number of testers were sufficient to identify metamorphic relations acting as a test result verification mechanism which was as effective as a test oracle, even though the metamorphic relations were identified in an ad hoc way by inexperienced testers. 6.4 RQ3: Enhancement of Metamorphic Testing Cost-Effectiveness Further investigations revealed that the groups of metamorphic relations with the smallest number of killed or crashed mutants displayed some degree of “similarity:” These metamorphic relations appeared to be related to the same properties or characteristics of the subject program. These observations motivated the question of how to enhance the cost-effectiveness of metamorphic testing, and led to the TABLE 6 T-Tests for Comparing the Metamorphic Relations Identified by a Single Tester with RT and RTo H0: The group of metamorphic relations identified by the same individual tester had similar fault-detection effectiveness to RT/RTo. TABLE 7 Grouping of Testers as Compared with RT and RTo LIU ET AL.: HOW EFFECTIVELY DOES METAMORPHIC TESTING ALLEVIATE THE ORACLE PROBLEM? 15 conjecture that relations having more “diversity” (less similarity) would be more cost-effective. Intuitively, for the same number of metamorphic relations, more diverse relations could deliver higher fault-detection effectiveness than similar relations; likewise, comparable fault-detection effectiveness could still be achieved using fewer, but more diverse, metamorphic relations. Therefore, diversity in metamorphic relations should enhance the cost-effectiveness of metamorphic testing. Experiments were conducted to validate this conjecture. Four assessors with experience in metamorphic testing were recruited to group the metamorphic relations identified in the previous experiments based on their own ideas of similarity. As expected, Table 9 shows that different Fig. 4. Relationship between metamorphic relations identified by the same testing team and the number of killed/crashed mutants. 16 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 40, NO. 1, JANUARY 2014 assessors had different grouping outcomes, reflecting their different interpretations of similarity. The effectiveness of an assessor’s grouping was analyzed as follows. Suppose that an assessor had classified all metamorphic relations for the same subject program into g groups. From these g groups, m (m ¼ 2; 3; . . . ; g) groups were randomly chosen, a
nd from each of these m groups, one and only one metamorphic relation was then randomly selected. Intuitively speaking, such m selected metamorphic relations exhibit some kind of diversity because they have been selected from different groups of similar metamorphic relations. The fault-detection effectiveness of these m “diverse” metamorphic relations was then compared with that of m randomly sampled metamorphic relations, which was reported in Section 6.2.3 and Fig. 2. The comparisons were conducted from two perspectives: the average number of killed or crashed mutants (average effectiveness); and the standard deviation of the number of killed or crashed mutants (effectiveness reliability). Note that we removed redundant metamorphic relations prior to the random sampling: The random sampling was on a pool of distinct metamorphic relations. The massive amount of data used to derive the average effectiveness and effectiveness reliability of diverse metamorphic relations will not be reported here, but Tables 10 and 11 summarize the two-tailed t-test results for the comparisons. In the tables, the rightmost bottom cell presents the t-test result for all programs and all assessors; each cell in the rightmost column shows the t-test result for each program for all assessors; each cell in the bottom row reports the t-test result for each assessor for all programs; and each of the remaining cells has the t-test result for each combination of program and assessor. The null hypotheses for these t-tests were that m diverse metamorphic relations had a similar performance to m randomly sampled metamorphic relations in terms of the average effectiveness (see Tables 10) and the effectiveness reliability (see Tables 11). In each cell of the tables, the number in parentheses represents the p-value, based on which the decision (reject or accept) was made. Based on the experimental data and the t-test results in Tables 10 and 11, it can be observed that when considering all programs and all assessors, it was statistically significant that both the average effectiveness and the average effectiveness reliability were enhanced by the use of diverse metamorphic relations. Fourteen of the 20 different assessor–program scenarios had statistically significant higher fault-detection effectiveness and reliability for m diverse metamorphic relations than m randomly sampled metamorphic relations. Only in one scenario (Assessor1 for program SparseMatrixMultiply), was there no statistically significant difference for either the average effectiveness or the effectiveness reliability. With respect to individual subject programs, the t-test results show that the average effectiveness could not be significantly enhanced by more diverse metamorphic relations for two programs (FindKNN and MultipleKnapsack, as shown in the rightmost column of Table 10), but more diverse metamorphic relations could result in more statistically reliable fault-detection effectiveness for all five subject programs (as shown in the rightmost column of Table 11). Furthermore, although the different assessors had different intuitions regarding similarity and diversity, their groupings helped to select diverse metamorphic relations which significantly enhanced both the average effectiveness and the effectiveness reliability (as shown in the bottom rows of Tables 10 and 11). 7 THREATS TO VALIDITY The threats to validity of this study are discussed as follows: The threat to internal validity is mainly related to the implementation of metamorphic testing, and the generation of (pseudo) random test cases. The programming required was relatively small-scale, and all the source code was carefully reviewed, several times. We are confident that both the metamorphic testing and the random test case generation have been correctly implemented in the experiments. The major potential threats to external validity relate to the selection of subject programs and the identification of their associated metamorphic relations. As mentioned in Section 5.1, due to the experimental constraints, we selected five subject programs of the algorithmic type, and these programs could neither be too complex, nor require much specific domain knowledge—therefore it might be argued that the findings of this study cannot be generalized to any type of program. Nevertheless, we believe that our results are still very useful for providing guidelines for the application of metamorphic testing in practice. Metamorphic testing has been successfully used in the testing of different types of TABLE 8 Fault-Detection Effectiveness for Metamorphic Relations Identified by the Testing Teams Compared with RTo/RT LIU ET AL.: HOW EFFECTIVELY DOES METAMORPHIC TESTING ALLEVIATE THE ORACLE PROBLEM? 17 programs, such as online ATM [39], telecommunications [8], wireless metering [25], compilers [40], and office applications [21], [42]. In these previous studies, it has been consistently shown that testers with adequate domain knowledge could identify a sufficient number of metamorphic relations. Compared with the subject programs in this study (each of which implemented a single functionality), simpler programs may need even fewer metamorphic relations to effectively alleviate the oracle problem; similarly, more complicated systems, with multiple distinct functionalities, may require more metamorphic relations to effectively imitate a test oracle. Moreover, since each tester identified metamorphic relations in an independent and ad hoc manner, such a process was somewhat subjective. Several invalid metamorphic relations were also generated, and the number of these might vary with application domains. The recruited testers were university students, who had neither prior knowledge of metamorphic testing nor formal experience in software testing. Nevertheless, if these testers could deliver such promising results after a brief training, it is very likely that more professional testers would be able to identify even more diverse and effective metamorphic relations. In our study, four assessors with experience in metamorphic testing were recruited to classify the identified Fig. 5. Relationship between the number of testers involved and the number of killed/crashed mutants. 18 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 40, NO. 1, JANUARY 2014 metamorphic relations into similar groups. Although such a grouping process was subjective and dependent on the assessors’ individual understanding of similarity, it did significantly improve the effectiveness of metamorphic testing. The main potential threat to construct validity is in the measurements used in this study. Fault-detection effectiveness was evaluated based on the number of killed or crashed mutants, a measurement metric commonly used in experiments using mutation analysis, which has been acknowledged as a popular and fair method for evaluating a testing method’s effectiveness. In addition, we introduced an oracle imitation measure to quantitatively examine the extent to which metamorphic testing can imitate the fault-detection effectiveness of a test oracle. This measure compares metamorphic testing’s fault-detection with that of random testing with and without an oracle, giving the relative degree to which metamorphic testing approximates the oracle. There should be little threat to the conclusion validity in this study: A large number of test cases were used in the testing, and the experiments resulted in a huge amount of data, which enabled a statistically reliable conclusion. Furthermore, formal statistical tests were employed to verify the statistical significance of the experimental results. 8 DISCUSSION AND CONCLUSION Metamorphic testing is an approach to software testing which can alleviate the oracle problem. It makes use of some necessary properties (metamorphic relations) of the software under test to provide a test result verification mechanism which can imitate a test oracle. This paper has presented empirical evidence to support this approach, including providing answers to the following questions: to what extent can metamorphic testing a
lleviate the oracle problem; how easily and successfully can testers detect TABLE 10 Comparison of the Average Effectiveness of Diverse and Randomly Sampled Metamorphic Relations H0: m diverse metamorphic relations had similar average effectiveness to m randomly sampled metamorphic relations. TABLE 11 Comparing the Effectiveness Reliability of Diverse and Randomly Sampled Metamorphic Relations H0: m diverse metamorphic relations had similar effectiveness reliability to m randomly sampled metamorphic relations. TABLE 9 Grouping of Metamorphic Relations According to the Assessor’s Own Intuition of Similarity LIU ET AL.: HOW EFFECTIVELY DOES METAMORPHIC TESTING ALLEVIATE THE ORACLE PROBLEM? 19 faults using metamorphic testing; and what are the key factors that influence the effectiveness of metamorphic testing? In the presented study, several groups of undergraduate and postgraduate students were recruited to identify metamorphic relations in five subject programs of algorithmic type. Even though the metamorphic relations were identified in an individual, independent, and ad hoc manner, by students who had neither formal testing experience nor prior knowledge of metamorphic testing, the identified metamorphic relations had very high fault-detection effectiveness. The fault-detection effectiveness and the average number of metamorphic relations identified by an individual tester are consistent with results observed in independent studies involving subject programs from different application domains [21], [42]. In the experiments, almost every identified metamorphic relation (except MR13 for SparseMatrixMultiply and MR10 for FindKNN) was able to detect more faults than the commonly adopted approach of crashing. It was observed that for each program, the aggregate of all its identified metamorphic relations could reveal a similar number of faults to a test oracle, which is the base program in this study. Further investigation revealed that the cost-effectiveness of the approach could be improved by reducing the number of metamorphic relations used: It was found that an average of three to six diverse metamorphic relations were sufficient to achieve comparable fault-detection effectiveness to a test oracle. Although it was initially surprising that a small number of diverse metamorphic relations were sufficient to match the fault-detection effectiveness of a test oracle, a reflection shows that it is in fact intuitively appealing. Consider the following simple example, which explains the underlying rationale for why several metamorphic relations may be able to imitate a test oracle. Suppose a program P accepts a real number x, and outputs the value of a polynomial of degree n, fðxÞ ¼ Pn i¼0 aixi. According to the competent programmer hypothesis, a faulty program should not be very different from the correct implementation [12]. Technically speaking, even if P is faulty, it would most likely output the value of a similar function, for example, another polynomial of degree m, gðxÞ ¼ Pm i¼0 bixi. Define hðxÞ ¼ fðxÞ  gðxÞ ¼ Pmaxðm;nÞ i¼0 cixi, where ci ¼ ai  bi if i  minðm; nÞ; ai if m < i  n; bi if n < i  m: 8< : Since h is a polynomial of, at most, degree maxðm; nÞ, there are at most maxðm; nÞ roots for the equation hðxÞ ¼ 0. In other words, if P is faulty, there are at most maxðm; nÞ values of x for which fðxÞ and gðxÞ give the same value (that is, fðxÞ ¼ gðxÞ). Consequently, any set of ðmaxðm; nÞ þ 1Þ ðx; fðxÞÞ pairs is sufficient to verify whether P is implementing f or g. Suppose that there are a total of N possible inputs for P (that is, possible values of x). Normally, N maxðm; nÞ; in theory, N may be infinite. If P implements g instead of f, then the probability of selecting a value of x such that gðxÞ ¼ fðxÞ is very small, that is, ProbðgðxÞ ¼ fðxÞÞ  maxðm;nÞ N 1. Given k (k < maxðm; nÞ) arbitrarily selected values for x, ProbðgðxÞ 6¼ fðxÞ for at least one xÞ  ð1 Qk1 j¼0 maxðm;nÞj Nj Þ. Since maxðm;nÞj Nj is very small, a small k is already enough to bring ð1 Qk1 j¼0 maxðm;nÞj Nj Þ close to 1. In other words, even if testing involves a small number of values for x, it is very likely to reveal that the implementation is actually for g instead of the intended f. In this example, ðmaxðm; nÞ þ 1Þ ðx; fðxÞÞ pairs collectively serve as a test oracle to distinguish f and g; and each individual ðx; fðxÞÞ pair is a necessary condition for the correct implementation of f instead of g, and hence can be considered analogous to a metamorphic relation, which is also a necessary property of the program. Considering such an analogy—that the comparison of k and ðmaxðm; nÞ þ 1Þ ðx; fðxÞÞ pairs is similar to the comparison of a few metamorphic relations to a test oracle—we can say that if a number of diverse metamorphic relations hold, it is very likely that the specifications have been correctly implemented. Therefore, it is intuitively appealing that a few diverse metamorphic relations should be able to perform as well as a test oracle in terms of revealing faults in a program. As found previously [21], [42], this study demonstrated that metamorphic testing is simple in concept and thus easy to understand and use. The potential ease with which testers could apply metamorphic testing was also investigated. Although the recruited testers were students inexperienced in testing, and were given only a small amount of training, most of them could easily identify a sufficient number of metamorphic relations to achieve a fault-detection effectiveness at least half way between that of using a test oracle and that from only crashing; and over half of them could identify metamorphic relations that collectively revealed a similar number of faults to a test oracle. However, in general, an individual tester applying metamorphic testing could not be guaranteed to identify sufficient metamorphic relations to imitate a test oracle. On the other hand, every testing team, consisting of four to seven testers, was able to identify enough metamorphic relations to have a similar faultdetection effectiveness to a test oracle. The experimental results also showed that a testing team could be composed of as few as three testers and still yield a sufficient number of metamorphic relations to achieve comparable faultdetection effectiveness to a test oracle. Further investigation of the experimental results determined that a critical factor affecting the cost-effectiveness of metamorphic testing was the diversity of the metamorphic relations used. It was found that when the metamorphic relations exhibited a certain degree of diversity, they tended to cover different types of faults, and thus had a high faultdetection effectiveness. As long as they were diverse, a small number of metamorphic relations were as effective as a test oracle in revealing faults. Using this notion of diversity, the cost-effectiveness of metamorphic testing could be significantly improved. This is consistent with observations made in investigations for the second research question (see Section 6.3), namely that a testing team composed of several testers was more likely than an individual tester to identify sufficient metamorphic relations to deliver comparable fault-detection effectiveness to a test oracle. Additionally, the results of the empirical studies also provide important insights into how to best conduct metamorphic testing. First and foremost, the diversity of metamorphic relations has been identified as more important than their quantity. In this study, a small number of diverse metamorphic relations were sufficient to detect most faults. Consequently, a smaller team of testers with 20 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 40, NO. 1, JANUARY 2014 diverse backgrounds may be better than a larger team of testers with simi
lar backgrounds, because the former is more likely to identify more diverse metamorphic relations. Moreover, it is strongly recommended that a tester should take diversity into account when selecting metamorphic relations for testing. All the experimental results consistently showed that metamorphic testing was a simple yet effective approach to alleviating the oracle problem. It is therefore worthwhile to continue research into metamorphic testing. As a first attempt to evaluate how effectively metamorphic relations may be able to approach the fault-finding efficiency of a test oracle, this study used some algorithmic programs as the subjects in our experiments. As shown in previous studies, as long as testers had adequate domain knowledge, it was not difficult to identify sufficient metamorphic relations for various application domains, such as online ATM [39], telecommunications [8], wireless metering [25], compilers [40], and office applications [21], [42]. Large-scale studies in these domains would further demonstrate the general applicability of metamorphic testing in practice. There exist a few other techniques for tackling the oracle problem, such as those mentioned in Section 3. It will be interesting to continue our research through comparing metamorphic testing with these techniques. In addition, although metamorphic relations identified in an ad hoc manner may already have a good performance, it is still essential to develop more systematic approaches for their identification: Only when metamorphic relations can be systematically identified, can the performance of metamorphic testing become more predictable and controllable. With a systematic approach, it should also become possible to provide testers with better training, and thus achieve better testing results. Another important research direction relates to the concept and interpretation of diversity for metamorphic relations. Although diversity has been widely used in test case selection [9], [19], its application to metamorphic relations, as investigated in this paper, is relatively abstract and subjective, and strongly dependent on the experience and background of the testers. It will be interesting to develop a more concrete concept of diversity for metamorphic testing, as has already been done in the area of test case selection, and apply it to the identification or selection of metamorphic relations. We are strongly confident that such investigations will further enhance the costeffectiveness of metamorphic testing and software testing. ACKNOWLEDGMENTS We are grateful to Kai-Yuan Cai of Beihang University, Chang-ai Sun of University of Science and Technology Beijing, Zhenyu Chen of Nanjing University, and Jianjun Zhao of Shanghai Jiao Tong University for their help in facilitating the experiments. We are also thankful to the students from these universities who participated in the experiments. This research project is supported by an Australian Research Council Discovery Grant. REFERENCES [1] P.E. Ammann and J.C. Knight, “Data Diversity: An Approach to Software Fault Tolerance,” IEEE Trans. Computers, vol. 37, no. 4, pp. 418-425, Apr. 1988. [2] A. Avizienis, “The N-Version Approach to Fault-Tolerant Software,” IEEE Trans. Software Engineering, vol. 11, no. 12, pp. 1491-1501, Dec. 1985. [3] A.C. Barus, T.Y. Chen, D. Grant, F.-C. Kuo, and M.-F. Lau, “Testing of Heuristic Methods: A Case Study of Greedy Algorithm,” Proc. Third IFIP TC 2 Central and Eastern European Conf. Software Eng. Techniques (CEE-SET ’08), Lecture Notes in Computer Science,, vol. 4980, pp. 246-260, 2011. [4] S. Beydeda, “Self-Metamorphic-Testing Components,” Proc. 30th Ann. Int’l Computer Software and Applications Conf. (COMPSAC ’06), pp. 265-272, 2006. [5] T.Y. Chen, S.C. Cheung, and S.M. Yiu, “Metamorphic Testing: A New Approach for Generating Next Test Cases,” Technical Report HKsUST-CS98-01, Dept. of Computer Science, Hong Kong Univ. of Science and Technology, 1998. [6] T.Y. Chen, J.W.K. Ho, H. Liu, and X. Xie, “An Innovative Approach for Testing Bioinformatics Programs Using Metamorphic Testing,” BMC Bioinformatics, vol. 10, pp. 24:1-24:12, 2009. [7] T.Y. Chen, D.H. Huang, T.H. Tse, and Z.Q. Zhou, “Case Studies on the Selection of Useful Relations in Metamorphic Testing,” Proc. Fourth Ibero-American Symp. Software Eng. and Knowledge Eng. (JIISIC ’04), pp. 569-583, 2004. [8] T.Y. Chen, F.-C. Kuo, H. Liu, and S. Wang, “Conformance Testing of Network Simulators Based on Metamorphic Testing Technique,” Proc. 29th IFIP Int’l Conf. Formal Techniques for Networked and Distributed Systems (FORTE ’09), vol. 5522, pp. 243-248, 2009. [9] T.Y. Chen, F.-C. Kuo, R.G. Merkel, and T.H. Tse, “Adaptive Random Testing: The ART of Test Case Diversity,” J. Systems and Software, vol. 83, no. 1, pp. 60-66, 2010. [10] T.Y. Chen, T.H. Tse, and Z. Zhou, “Semi-Proving: An Integrated Method for Program Proving, Testing, and Debugging,” IEEE Trans. Software Eng., vol. 37, no. 1, pp. 109-125, Jan./Feb. 2011. [11] T.Y. Chen and Y.T. Yu, “On the Relationship Between Partition and Random Testing,” IEEE Trans. Software Eng., vol. 20, no. 12, pp. 977-980, Dec. 1994. [12] R.A. DeMillo, R.J. Lipton, and F.G. Sayward, “Hints on Test Data Selection: Help for the Practicing Programmer,” Computer, vol. 11, no. 4, pp. 34-41, Apr. 1978. [13] H. Do, S. Elbaum, and G. Rothermel, “Supporting Controlled Experimentation with Testing Techniques: An Infrastructure and Its Potential Impact,” Empirical Software Eng., vol. 10, no. 4, pp. 405-435, 2005. [14] X. Feng, D.L. Parnas, T.H. Tse, and T. O’Callaghan, “A Comparison of Tabular Expression-Based Testing Strategies,” IEEE Trans. Software Eng., vol. 37, no. 5, pp. 616-634, Sept./Oct. 2011. [15] J.E. Forrester and B.P. Miller, “An Empirical Study of the Robustness of Windows NT Applications Using Random Testing,” Proc. Fourth USENIX Windows Systems Symp. (USENIX-WIN ’00), pp. 59-68, 2000. [16] G. Fraser and A. Zeller, “Mutation-Driven Generation of Unit Tests and Oracles,” Proc. 19th Int’l Symp. Software Testing and Analysis (ISSTA ’10), pp. 147-158, 2010. [17] A. Gotlieb and B. Botella, “Automated Metamorphic Testing,” Proc. 27th Ann. Int’l Computer Software and Applications Conf. (COMPSAC ’03), pp. 34-40, 2003. [18] B. Hailpern and P. Santhanam, “Software Debugging, Testing, and Verification,” IBM Systems J., vol. 41, no. 1, pp. 4-12, 2002. [19] H. Hemmati, A. Arcuri, and L. Briand, “Achieving Scalable Model-Based Testing Through Test Case Diversity,” ACM Trans. Software Eng. and Methodology, vol. 22, no. 1, pp. 6:1- 6:42, 2013. [20] R.M. Hierons, “Oracles for Distributed Testing,” IEEE Trans. Software Eng., vol. 38, no. 3, pp. 629-641, May/June 2012. [21] P. Hu, Z. Zhang, W.K. Chan, and T.H. Tse, “An Empirical Comparison between Direct and Indirect Test Result Checking Approaches,” Proc. Third Int’l Workshop Software Quality Assurance (SOQUA ’06), pp. 6-13, 2006. [22] Y.F. Hu, R.J. Allan, and K.C.F. Maguire, “Comparing the Performance of JAVA with Fortran and C for Numerical Computing,” technical report, Daresbury Laboratory, CCLRC, http:// www.dl.ac.uk/TCSC/UKHEC/JASPA/bench.pdf, 2000. [23] JFlex, The fast scanner generator for java. http://jflex.de/, 2009. [24] J.C. Knight and N.G. Leveson, “An Experimental Evaluation of the Assumption of Independence in Multi-Version Programming,” IEEE Trans. Software Eng., vol. 12, no. 1, pp. 96-109, Jan. 1986. LIU ET AL.: HOW EFFECTIVELY DOES METAMORPHIC TESTING ALLEVIATE THE ORACLE PROBLEM? 21 [25] F.-C. Kuo, T.Y. Chen, and W.K. Tam, “Testing Embedded Software by Metamorphic Testing: A Wireless Metering System Case Study,” Proc. 36th IEEE Conf. Local Computer Networks (LCN ’11), pp. 295-298, 2011. [26] H.T. Lau, A Java Library of Graph Algorithms and Optimisation. T
aylor & Francis, 2007. [27] Y.-S. Ma, J. Offutt, and Y.-R. Kwon, “MuJava: An Automated Class Mutation System,” Software Testing, Verification and Reliability, vol. 15, no. 2, pp. 97-133, 2005. [28] L.I. Manolache and D.G. Kourie, “Software Testing Using Model Programs,” Software: Practice and Experience, vol. 31, no. 13, pp. 1211-1236, 2001. [29] J. Mayer and R. Guderlei, “An Empirical Study on the Selection of Good Metamorphic Relations,” Proc. 30th Ann. Int’l Computer Software and Applications Conf. (COMPSAC ’06), pp. 475-484, 2006. [30] B.P. Miller, G. Cooksey, and F. Moore, “An Empirical Study of the Robustness of MacOS Applications Using Random Testing,” ACM SIGOPS Operating Systems Rev., vol. 41, no. 1, pp. 78-86, 2007. [31] B.P. Miller, L. Fredriksen, and B. So, “An Empirical Study of the Reliability of UNIX Utilities,” Comm. ACM, vol. 33, no. 12, pp. 32- 44, 1990. [32] C. Murphy, K. Shen, and G.E. Kaiser, “Automatic System Testing of Programs without Test Oracles,” Proc. 18th Int’l Symp. Software Testing and Analysis (ISSTA ’09), pp. 189-200, 2009. [33] G.J. Myers, The Art of Software Testing, second ed. John Wiley & Sons, Revised and updated by T. Badgett and T. M. Thomas with C. Sandler, 2004. [34] W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery, Numerical Recipes in C: The Art of Scientific Computing. Cambridge Univ. Press, 1992. [35] P. Rao, Z. Zheng, T.Y. Chen, N. Wang, and K. Cai, “Impacts of Test Suites Class Imbalance on Spectrum-Based Fault Localization Techniques,” Proc. 13th Int’l Conf. Quality Software (QSIC ’13), pp. 260-267, 2013. [36] D.S. Rosenblum, “A Practical Approach to Programming with Assertions,” IEEE Trans. Software Eng., vol. 21, no. 1, pp. 19-31, Jan. 1995. [37] S. Segura, R.M. Hierons, D. Benavides, and A. Ruiz-Cortes, “Automated Metamorphic Testing on the Analyses of Feature Models,” Information and Software Technology, vol. 53, no. 3, pp. 245-258, 2011. [38] M. Staats, G. Gay, and M.P.E. Heimdahl, “Automated Oracle Creation Support, or: How I Learned to Stop Worrying about Fault Propagation and Love Mutation Testing,” Proc. 34th Int’l Conf. Software Eng. (ICSE ’12), pp. 870-880, 2012. [39] C. Sun, G. Wang, B. Mu, H. Liu, Z. Wang, and T. Y. Chen, “Metamorphic Testing for Web Services: Framework and a Case Study,” Proc. Ninth Int’l Conf. Web Services (ICWS ’10), pp. 283-290, 2011. [40] Q. Tao, W. Wu, C. Zhao, and W. Shen, “An Automatic Testing Approach for Compiler Based on Metamorphic Testing Technique,” Proc. 17th Asia Pacific Software Eng. Conf. (APSEC ’10), 2010. [41] X. Xie, W.E. Wong, T.Y. Chen, and B. Xu, “Metamorphic Slice: An Application in Spectrum-Based Fault Localization,” Information and Software Technology, vol. 55, no. 5, pp. 866-879, 2013. [42] Z. Zhang, W.K. Chan, T.H. Tse, and P. Hu, “Experimental Study to Compare the Use of Metamorphic Testing and Assertion Checking,” J. Software, vol. 20, no. 10, pp. 2637-2654, 2009. Huai Liu received the BEng in physioelectronic technology and MEng in communications and information systems, both from Nankai University, China, and the PhD degree in software engineering from the Swinburne University of Technology, Australia. He is a research fellow at the Australia-India Centre for Automation Software Engineering, RMIT University, Australia. His current research interests include software testing, cloud computing, and end-user software engineering. Fei-Ching Kuo received the bachelor of science degree (honors) in computer science and the PhD degree in software engineering, both from the Swinburne University of Technology, Australia. She is a senior lecturer at the Faculty of Information and Communication Technologies, Swinburne University of Technology, Australia. She was a lecturer at the University of Wollongong, Australia. She was also the program committee chair for the 10th International Conference on Quality Software 2010 (QSIC’10) and guest editor of a special issue for the Journal of Systems and Software, special issue for Software Practice and Experience, and special issue for International Journal of Software Engineering and Knowledge Engineering. Her current research interests include software analysis, testing, and debugging. Dave Towey received the BA and MA degrees in computer science, linguistics, and languages from the University of Dublin, Trinity College, and the PhD degree in computer science from the University of Hong Kong. He is an assistant professor in the Division of Computer Science, The University Nottingham Ningbo China, prior to which he was with Beijing Normal University- Hong Kong Baptist University: United International College, China. His research interests include software testing, software design, and technology-enhanced education. He is a member of both the IEEE and the ACM. Tsong Yueh Chen received the BSc and MPhil degrees from The University of Hong Kong, the MSc and DIC degrees from the Imperial College of Science and Technology, and the PhD degree from the University of Melbourne. He is a professor of software engineering at the Faculty of Information and Communication Technologies, Swinburne University of Technology, Australia. His current research interests include software testing, debugging, software maintenance, and software design. . For more information on this or any other computing topic, please visit our Digital Library at www.computer.org/publications/dlib. 22 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 40, NO. 1, JANUARY 2014

Leave a Reply

Your email address will not be published.