Research On Theory And Techniques Of Metamorphic Relation Identification,Selection,and Prioritization In Metamorphic Testing

Software testing is an important approach for software quality assurance,which aims at revealing hidden defects by executing test cases and checking whether the corresponding output is as expected.The extreme difficulty or the high cost of obtaining the expected output of a test case(which is known as the oracle problem)remains one of the open problems in software testing.With the increasing scale and complexity of software systems,the oracle problem becomes more prominent.Metamorphic testing(MT)is a promising technique that can effectively alleviate the oracle problem.Rather than directly validating-the correctness of the outputs of individual test inputs,MT checks whether some necessary properties(known as metamorphic relations,MRs)hold among multiple inputs and their corresponding execution outputs.I n recent years,a large number of studies have been focused on how to adopt MT in various application domains to solve the oracle problem.However,some fundamental problems of MT still deserve substantial effort to address,specifically:(1)MRs are the key of MT to detect defects,however,a general and efficient MR identification approach is still missing.(2)A test adequacy measurement that guides the selection of MRs and test cases is still missing,and accordingly,it is difficult to determine the stopping condition of MT.(3)Prioritization techniques that schedule the execution order of both MRs and test cases are missing,which hinders the fault detection efficiency of MT.This dissertation aims to explore the above fundamental issues of MT,with emphasis on the development of general yet efficient MR identification approaches,test adequacy criteria and measurements for MT,and prioritization based optimization strategies for MT.The main contributions of this dissertation are as follows:1.Regarding the identification issue of MRs,an MR identification approach based on category choice framework and software output domain is proposed,namely METRIC+.This approach leverages the category choice framework to divide the input and output domains of software under test and employs the concept of category,choice,and complete test frame to characterize the input and output partitions.On this basis,METRIC+takes into account both input domain partition and output domain partition to help software testers identify MR in a precise and efficient way.A supporting tool named MR-GEN+was developed to automate most steps of MR identification based on METRIC+.An empirical study involving four real-life software systems from different application domains was conducted to evaluate METRIC+ in terms of MR identification effectiveness and efficiency as well as the fault detection effectiveness of identified MRs.The experimental results have shown that compared with baseline approaches,METRIC+is highly effective and efficient in MR identification,and the identified MRs are effective in fault detection.2.Regarding the test adequacy measurement of MT,a test adequacy criterion,namely the k output sub-relation coverage criterion,is proposed and a test adequacy measurement is designed.This criterion is an extension of traditional test adequacy criteria,which takes into consideration not only source test cases but also MRs and the association relationship between MRs and source test cases.Based on this criterion,a test adequacy measurement is further designed to quantify the degree of MT’s-test adequacy.The proposed criterion and measurement provide guidelines for selecting MRs and source test cases in MT.An empirical study involving seven software systems from various application domains and five test case adequacy criteria was conducted to evaluate the effectiveness of the proposed test adequacy criterion and measurement.The experimental results have shown that MRs and source test cases that collectively achieve a higher degree of test adequacy usually exhibit higher fault detection capability;in addition,our experiment discovered a defect in a widely studied subject software that has never been reported in previous studies.3.To further improve the fault detection efficiency of MT,a prioritization approach that schedules the execution order of both MRs and test cases is proposed.The approach determines the priority of MRs and test cases based on the degree of contribution of test cases to test adequacy,the timing of result verification in the testing procedure,and the strictness of MR’s output subrelation.Accordingly,the approach schedules the execution order of MRs and test cases such that MRs and test cases with a higher potential of fault detection are executed earlier.An empirical study involving seven subject programs and two baseline approaches was conducted to evaluate the proposed prioritization approach in terms of fault detection efficiency and the time overhead of prioritization.The experimental results have shown that the proposed approach can effectively speed up the fault detection of MT compared with random prioritization approach and those considering only MR prioritization.In addition,the proposed approach brings cost-effective acceleration of fault detection with a relatively low time overhead.