Code Coverage Analysis of Combinatorial Testing

1 code Coverage Analysis of Combinatorial TestingEun-Hye Choi , Osamu Mizuno , Yifan Hu National Institute of Advanced Industrial Science and Technology (AIST), Ikeda, JapanEmail: Kyoto Institute of Technology, Kyoto, JapanEmail: Combinatorialt-way Testing with smalltis known asan e cient black-box Testing technique to detect parameter inter-action failures. So far, several empirical studies have reported thee ectiveness oft-way Testing on fault detection abilities. However,few studies have investigated the e ectiveness oft-way testingoncodecoverage, which is one of the most important coveragecriteria widely used for software Testing . This paper presents aquantitative Analysis to evaluate the code - Coverage e ectivenessoft-way Testing . Using three open source utility programs, wecomparet-way Testing with exhaustive (all combination) testingw. r. t. code Coverage and test suite Testing ;t-way Testing ; Exhaustive test-ing; code Coverage ; Line Coverage ; Branch IntroductionCombinatorial Testing [15], [20] is a common black-boxtesting to detect failures caused by parameter software systems have a lot of parameters, and thustheir interactions are too numerous to be exhaustively Testing [15], [20], wheretis called aninteraction strength, addresses this problem by Testing all valuecombinations oftparameters with smallt, instead of Testing allparameter-value combinations Testing hasbeen applied to e.

2 G. conformance Testing for DOM (DocumentObject Model) Events standard [19], rich web applications[18], commercial MP3 players [25], and a ticket gate systemfor transportation companies [14].Kuhn et al. [16] investigated the fault detection e ectivenessoft-way Testing ; their result showed thatt-way Testing withsmall interaction strengtht( 4) can e ciently detect mostinteraction failures while significantly reducing the numberof test cases compared toexhaustive Testing , which tests allparameter-value combinations. Other studies [2], [8], [25] alsosupported the result by Kuhn et al. [16].On the other hand, as far as we know, the only work byGiannakopoulou et al. [10] reported the e ectiveness oft-way Testing oncode Coverage . They compared code coveragebetween their model-checker based exhaustive Testing and3-way Testing with two program modules for a NASA airtransportation Coverage , which measures what percentage of sourcecode is executed by a test suite, has been considered as one ofthe most important Coverage metrics for software Testing andis required by many industrial software development standards(e.)

3 G. [1]). Therefore, the code Coverage e ectiveness oft-waytesting would be of big interest to practitioners who considerapplyingt-way Testing to their software thatt-way Testing is a black-box Testing and thus isdi cult to achieve 100% code Coverage and its code coveragedepends on thesystem under test (SUT)model, e. g. parametersand their values, designed fort-way Testing . Therefore, in orderto evaluate the code Coverage e ectiveness oft-way Testing ,we compare code Coverage obtained byt-way Testing with thatby exhaustive Testing , similarly to [10].In order to quantitatively analyze the code Coverage e ec-tiveness oft-way Testing compared to exhaustive Testing , weset up the following two research questions: RQ1: How high code Coverage cant-way Testing achievecompared to exhaustive Testing ? Cant-way Testing obtainhigher code Coverage earlier compared to exhaustivetesting? How large interaction strengthtis necessary fort-way Testing to achieve the code Coverage close to thatby exhaustive Testing ?

4 RQ2: With the same number of test cases, how di erentaret-way Testing and exhaustive Testing on code Coverage ?For evaluating the code Coverage e ectiveness oft-waytesting, RQ1 comparest-way Testing and exhaustive testingin their original sizes, while RQ2 comparest-way Testing andexhaustive Testing in the same answer the above research questions, we perform a casestudy that analyzest-way test suites with 1 t 4 on two kindsof widely used code Coverage ;line Coverage (i. e., statementcoverage) andbranch Coverage (i. e., decision Coverage ). Foran empirical case study, we use seventeen versions of threeC program projects,flex,grep, andmake, from the Software-artifact Infrastructure Repository (SIR) [7]. To preparet-waytest suites, we first construct SUT models with constraintsfrom test plans in Test Specification Language (TSL) [21]of the repository. We next generatet-way test suites for theSUT models using two state-of-the-artt-way test generationtools,ACTS[3], [26] andPICT[6], [31].

5 We evaluate thecode Coverage e ectiveness oft-way Testing by comparing thet-way test suites and exhaustive test suites on the examiningline Coverage and branch Coverage with test suite Organization: SectionII-Aexplains combinatorialt-way Testing and SectionII-Bdescribes related work onthe e ectiveness evaluation oft-way Testing . Section IIIdescribes our experimental setting, and Section IV explainsexperimental results which answer the research V concludes this International Workshop on Quantitative Approaches to Software Quality (QuASoQ 2016)43 TABLE IAn mode (=p1) on, o Bypass use (=p2)on, o Fast scanner (=p3) FastScan (=1), FullScan (=2), o Constraint:(Fast scanner=FullScan)!(Bypass use,on)TABLE IIAn example of all possible pairs of pairs Parameter-value pairs(p1,p2)(on, on), (on, o ), (o , on), (o ,o )(p1,p3)(on, 1), (on, 2), (on, o ), (o , 1), (o , 2), (o ,o )(p2,p3)(on, 1), (on, o ), (o , 1), (o , 2), (o ,o )II.

6 Background andRelatedWorkA. Combinatorial t-way TestingTheSystem Under Test (SUT)for Combinatorial testingis modeled from parameters, their associated values fromfinite sets, and constraints between parameter-values. Forinstance, the SUT model shown in Table I, has three parameters(p1,p2,p3); the first two parameters have two possible valuesand the other has three possibilities. Constraints amongparameter-values exist when some parameter-value combina-tions cannot occur. The example SUT has a constraint suchthatp2,onifp3=1, i. e., the combination ofp2=onandp3=1 is not formally, a model of an SUT is defined as follows:Definition 1(SUT model).AnSUT modelis a triplehP,V, i,where P is a finite set of parameters p1,..,p|P|, Vis a family that assigns a finite value domainViforeach parameter pi(1 i |P|), and is a constraint on parameter-value caseis a value assignment for the parameters thatsatisfies the SUT constraint.

7 For example, a 3-tuple (p1=on,p2=on,p3=1) is a test case for our example SUT model. Wecall a sequence of test cases atest test suite(i. combination test suite) isa sequence of all possible test cases, i. e., a test suite thatcovers all parameter-value combinations satisfying the SUTconstraint. In general, exhaustive Testing is impractical since itstipulates to test all possible test cases and thus its size (thenumber of test cases) increases exponentially with the numberof Testing (e. g.,pairwise, whent=2)alternatively stipulates to test allt-wayparameter-value combi-nations satisfying the SUT constraint at least once. We calltaninteraction strength. An exhaustive test suite correspondsto at-way test suite witht=|P|.Definition 2(t-way test suite).LethP,V, ibe an SUT IIIA 2-way test on on 12 on o o 3o o 14o on o 5o o 26 on o 1 TABLE IVAn exhaustive test on on 12 on on o 3 on o 14 on o 25 on o o 6o on 17o on o 8o o 19o o 210 o o o TABLE VRelated studiedCode Coverage Fault detectionKuhn et al.

8 (2004) [16]XZhang et al. (2012) [25]XPetke et al. (2015) [22]XHenard et al. (2015) [11]XChoi et al. (2016) [4]XGiannakopoulou et al. (2011) [10]XThis paperXWe say that a tuple oft(1 t |P|) parameter-values ispossiblei it does not contradict the SUT constraint .At-way test suitefor the SUT model is a test suite that coversall possible t-tuples of parameter-values in the SUT the SUT model in Table I andt= exist15possiblet-tuples (pairs) of parameter-values, asshown in Table II. The test suitesT1in Table III is a 2-way(pairwise) test suite since it covers all the possible parameter-value pairs in Table Table IV is a 3-way test suiteand corresponds to the exhaustive test suite since the numberof parameters in the example model is three .Many algorithms to e ciently constructt-way test suiteshave been proposed so far. Approaches to generatet-waytest suites for SUT models with constraints include greedyalgorithms (e.)

9 G., AETG [5], PICT [6], [31], and ACTS [3],[26]), heuristic search (e. g., CASA [9], HHSA [12], andTCA [17]), and SAT-based approaches (e. g., Calot [23], [24]).B. Related Work: E ectiveness evaluation of t-way testingThe e ectiveness oft-way Testing with small interactionstrengthton fault detection have been reported by severalempirical studies so far [13], [15], but the code Coverage oft-way Testing has not been studied well. Table V summarizesthe e ectiveness metrics studied in related et al. [16] investigated parameter interactions inducingactual failures of four systems; a software for medical devices,a browser, a server, and a database system. As a result, 29 68%of the faults involved a single parameter; 70 97% (89 99%)of the faults involved up to two (three) parameter interactions;96 100% of the faults involved up to four and five parameter4th International Workshop on Quantitative Approaches to Software Quality (QuASoQ 2016)44interactions; no fault involved more than six parameters.

10 Fromthe result, the authors concluded that most failures are triggeredby parameter interactions with smallt(at most four to six)and thust-way Testing with 4 t 6 could provide the faultdetection ability of pseudo-exhaustive et al. [25] also explored that failures of actualcommercial MP3 players are triggered byt-way parameterinteractions with at mostt= et al. [22] more thoroughly studied the e ciency ofearly fault detection byt-way Testing with 2 t 6. Theyused six projects,flex,make,grep,gzip,nanoxml, andsiena,from the Software artifact Infrastructure Repository (SIR) andshowed the number of faults detected after 25%, 50%, 70%,and 100% of test cases are et al. [11] used five projects,grep,sed,flex,make,andgzip, also from SIR and compared the number of faultsdetected by test suite prioritization witht-way Coverage (2 t 4) and other black-box and white-box et al. [4] used three projects,flex,grep, andmake,from SIR and investigated a correlation of the fault detection ef-fectiveness with two evaluation metrics, called weight coverageand KL divergence, for prioritizedt(=2)-way our knowledge, the only work by Giannakopoulou etal.