Provable improvements on branch testing.pdfVIP

Provable Improvements on Branch TestingPhyllis G. Frankl  Elaine J. WeyukeryKeywords: fault detection, program testing, software testingdata ow testing, mutation testing, condition-coverage testingAbstractThis paper compares the fault-detecting ability of several software test dataadequacy criteria. It has previously been shown that if C1 properly coversC2, then C1 is guaranteed to be better at detecting faults than C2, in thefollowing sense: a test suite selected by independent random selection ofone test case from each subdomain induced by C1 is at least as likely todetect a fault as a test suite similarly selected using C2. In contrast, if C1subsumes but does not properly cover C2, this is not necessarily the case.These results are used to compare a number of criteria, including several thathave been proposed as stronger alternatives to branch testing. We comparethe relative fault-detecting ability of data ow testing, mutation testing, andthe condition-coverage techniques, to branch testing, showing that most of thecriteria examined are guaranteed to be better than branch testing accordingto two probabilistic measures. We also show that there are criteria thatcan sometimes be poorer at detecting faults than substantially less expensivecriteria.1 IntroductionAlthough a large number of software testing techniques have been proposed during thelast two decades, there has been surprisingly little concrete information about how ef-fectively they detect faults. This is true both in the case of theoretical analyses andAuthors address: Computer Science Dept., Polytechnic University, 6 Metrotech, Brooklyn, N.Y.11201. Supported in part by NSF Grant CCR-9206910 and by the New York State Science and Tech-nology Foundation Center for Advanced Technology program.yAuthors address: Computer Science Dept., Courant Institute of Mathematical Sciences, New YorkUniversity, 251 Mercer Street, New York, NY 10012. Supported in part by NSF grant CCR-8920701and by NASA grant NAG-1-1238