Pairwise Testing in Real World

1 Pairwise Testing in real WorldPractical Extensions to Test Case GeneratorsJacek CzerwonkaMicrosoft Microsoft WayRedmond, WA Testing has become an indispensable tool in a soft-ware tester s toolbox. The technique has been known foralmost twenty years [22] but it is the last five years that wehave seen a tremendous increase in its on at least 20 tools that can generate pairwisetest cases, have so far been published [1]. Most tools, how-ever, lack practical features necessary for them to be usedin paper pays special attention to usability of the pairwisetesting technique. In particular, it does not describe anyradically new method of efficient generation of Pairwise testsuites, a topic that has already been researched extensively,neither does it refer to any specific case studies or resultsobtained through this method of test case generation. Itdoes focus on ways in which pure Pairwise Testing approachneeds to be modified to become practically applicable andon features tools need to offer to support a tester trying touse Pairwise in paper makes frequent references to PICT, an existingand publicly available tool built on top of a flexible combina-torial test case generation engine, which implements severalof the concepts described and Subject [Software]: Software Engineering; [SoftwareEngineering]: Testing and Debugging Testing toolsGeneral TermsVerification, DesignKeywordsPairwise Testing , combinatorial Testing , test case generation,test case design1.

2 BACKGROUNDA set of possible inputs for any nontrivial piece of software istoo large to be tested exhaustively. Techniques likeequiva-lence partitioningandboundary-value analysis[17] help con-vert even a large number of test levels into a much smallerset with comparable defect-detection power. Still, if soft-ware under test (SUT) can be influenced by a number ofsuch factors, exhaustive Testing again becomes the years, a number of combinatorial strategies havebeen devised to help testers choose subsets of input combi-nations that would maximize the probability of detecting de-fects:random Testing [16],each-choiceandbase-choice[2] ,anti-random[15] and finallyt-wise Testing strategies withpairwise Testing being the most prominent among these (seeFigure 1). Pairwise Testing strategy is defined as follows:Given a set ofNindependent test factors:f1, f2, .., fN, witheach factorfihavingLipossible levels:fi={li,1.}

3 , li,Li},a set of testsRis produced. Each test inRcontainsNtestlevels, one for each test factorfi, and collectively all testsinRcover all possible pairs of test factor levels (belongingto different parameters) for each pair of factor levelsli,pandlj,q, where 1 p Li, 1 q Lj, andi6=jthereexists at least one test inRthat contains bothli,pandlj, concept can easily be extended from covering all pairsto covering anyt-wise combinations where 1 t 1, the strategy is equivalent toeach-choice; ift=N, the resulting test suite is all pairs of tested factor levels has been extensivelystudied. Mandl described using orthogonal arrays in testingof a compiler [16]. Tatsumi, in his paper on Test Case De-sign Support System used in Fujitsu Ltd [22], talks abouttwo standards for creating test arrays: (1) with all combina-tions covered exactly the same number of times (orthogonalarrays) and (2) with all combinations covered at least making that crucial distinction, he references an ear-lier paper by Shimokawa and Satoh [19].

4 Over the years, Pairwise Testing was shown to be an efficientand effective strategy of choosing tests [4, 5, 6, 10, 13, 23].However, as shown by Smith et al. [20] and later by Bachand Shroeder [3] Pairwise , like any technique, needs to beused appropriately and with 1: Increase in number of exhaustive and Pairwise tests with number of test levelsSince the problem of finding a minimal array covering allpairwise combinations of a given set of test factors is NP-complete [14], understandably a considerable amount of re-search has gone into efficient creation of such arrays. Severalstrategies were proposed in an attempt to minimize numberof tests produced [11].Authors of these combinatorial test case generation strate-gies often describe additional considerations that must betaken into account before their solutions become many cases, they propose methods of handling these incontext of their generation strategies.

5 Tatsumi [22] mentionsconstraintsas a way of specifying unwanted combinations(or more generally, dependencies among test factors). Sher-wood [18] explores adapting conventionalt-wise strategy toinvalid testingand the problem of preventing input mask-ing. Cohen et al. [6] describeseedswhich allow specifyingcombinations that need to appear in the output and coveringcombinations withmixed-strength arraysas a way of puttingmore emphasis on interactions of certain test paper describes PICT, a test case generation tool thathas been in use at Microsoft since 2000, which implementsthet-wise Testing strategy and features making the strategyfeasible in practice of software ModelsPICT was designed with three principles in mind: (1) speedof test generation, (2) ease of use, and (3) extensibility of thecore engine. Even though the ability to create the smallestpossible covering array was given less emphasis, efficiency ofPICT s core algorithm is comparable with other known testgeneration strategies (see Figure 2).

6 Input to PICT is a plain-text file (model) in which a testerspecifies test factors (referred to as testparameterslaterin this paper) and test factor levels (referred to asvaluesof a parameter). Figure 3 shows an example of a simplemodel used to produce test cases for volume creation default, the tool produces a Pairwise test array (t= 2).It is possible, however, to specify a different order of combi-nations. In fact, anytis allowed if only 1 t Test Case Generation EngineThe test generation process in PICT is comprised of twomain phases: (1) preparation and (2) the preparation phase, PICT computes all informationnecessary for the generation phase. This includes the setPof all parameter interactions to be covered. Each com-bination of values to be covered is reflected in a parameterinteraction example, given three parametersA,B(two values each),andC(three values) and pair-wise generation, three para-meter interaction structures are set up:AB,AC, of these has a number of slots corresponding to possiblevalue combinations participating in a particular parameterinteraction (4 slots forAB, 6 slots forACandBC).

7 SeeFigure slot can be markeduncovered,covered, orexcluded. Alltheuncoveredslots in all parameter interactions constitutethe set of combinations to be covered. If any constraintswere defined in a model, they are converted into a set ofex-clusions value combinations that must not appear in thefinal output. Corresponding slots are then markedexcludedin parameter interaction structures and therefore removedfrom combinations to be covered. The slot becomescoveredwhen the algorithm produces a test case satisfying that par-ticular combination. The algorithm terminates when thereare core generation algorithm is a greedy heuristic (see Fig-ure 5). It builds one test case at a time, locally optimizingthe solution. It is similar to the algorithm used in AETG1[6] with key differences being that PICT algorithm is deter-ministic2and it does not produce candidate is a trademark of Telecordia does make pseudo-random choices but unless a userspecifies otherwise, the pseudo-random generator is alwaysinitialized with the same seed value.

8 Therefore two execu-tions on the same input produce the same [14] PairTest [21] TConfig [24] CTS [12] Jenny [1] DDA [8] AllPairs [1] PICT34999911?993131517151518181718415317 2294134403938353437413392352826302928272 6272100101514101615141510201802122312101 93201197210 Figure 2: Comparison of PICT s generation efficiency with other known toolsType: Single, Spanned, Striped, Mirror, RAID-5 Size: 10, 100, 1000, 10000, 40000 Format method: Quick, SlowFile system: FAT, FAT32, NTFSC luster size: 512, 1024, 2048, 4096, 8192, 16384 Compression: On, OffFigure 3: Parameters for volume creation and formattingA: 0, 1B: 0, 1C: 0, 1, 2translates toAB AC BC00 00 0001 01 0110 02 0211 10 1011 1112 12 Figure 4: Parameter interaction structures# Assume test casesr1, .., ri 1are already produced# Slots inPreflecting combinations selected byr1.

9 , ri 1are set tocoveredIf there are any unused seed combinations not violating any exclusionsAdd a seed combination toriMark all slots inPcovered by the seed combination ascoveredWhile there are parameters with no values inriIfriis emptyChoose a parameter interactionpfromPwith mostuncoveredslotsPick the firstuncoveredcombination frompElse# Assume valuesl1, .., lk 1have already been chosen and added toriLook at subsetQofPthat covers at least one parameter with norepresentation inl1, .., lk 1 Look at slots inQwhich values are consistent with already chosen values inl1, .., lk 1If there existuncoveredcombinationsPick a slot with values which when added toriwould cover the mostuncoveredcombinations withl1, .., lk 1and the resulting partial test caseriwould notcontain anexcludedcombinationElsePick randomly acoveredcombination which when added tol1, .., lk 1would notcontain anexcludedcombinationAdd values of this combination toriMark the chosen combination inPascoveredFigure 5: PICT heuristic algorithmThe generation algorithm does not assume anything aboutthe combinations to be covered.

10 It operates on a list of com-binations that is produced in the preparation phase. Thisflexibility of the generation algorithm allows for adding in-teresting new features easily. The algorithm is also quiteeffective. It is able to compute test suites comparable insize to other tools existing in the field and it is fast enoughfor all practical ADVANCED Mixed-strength GenerationMost commonly, whent-wise Testing is discussed it is as-sumed that all parameter interactions have a fixed other words, ift= 3 is requested, all triplets of parame-ter values will be covered. It is sometimes useful, however,to be able to define different orders of combinations for dif-ferent subsets of parameters. For example (see Figure 6),interactions of parametersB,C, andDmight require bettercoverage than interactions ofAorE. We should be able togenerate all possible triplets ofB,C, andDand cover allpairs of all other parameter interactions.