Combinatorial Interaction Regression Testing: A Study of ...

1 Combinatorial Interaction Regression testing : A Study of Test Case Generationand PrioritizationXiao Qu, Myra B. Cohen, Katherine M. WoolfDepartment of Computer Science and EngineeringUniversity of testing is an expensive part of the softwaremaintenance process. Effective Regression testing tech-niques select and order (or prioritize) test cases betweensuccessive releases of a program. However, selection andprioritization are dependent on the quality of the initial testsuite. An effective and cost efficient test generation tech-nique is Combinatorial Interaction testing , CIT, which sys-tematically samples all t-way combinations of input param-eters.

2 Research on CIT, to date, has focused on single ver-sion software systems. There has been little work that em-pirically assesses the use of CIT test generation as the ba-sis for selection or prioritization. In this paper we exam-ine the effectiveness of CIT across multiple versions of twosoftware subjects. Our results show that CIT performs wellin finding seeded faults when compared with an exhaustivetest set. We examine several CIT prioritization techniquesand compare them with a re-generation/prioritization tech-nique. We find that prioritized and re-generated/prioritizedCIT test suites may find faults earlier than unordered CITtest suites, although the re-generated/prioritized test suitessometimes exhibit decreased fault IntroductionRegression testing is an expensive part of the softwareprocess.

3 As systems evolve, before new versions are re-leased, software must be re-tested to ensure quality. Oneconcern in Regression testing is the effectiveness of testsuites in finding new faults in successive program second issue is the efficiency of running the test suitesgiven limited resources and time. Small test suites that re-tain high fault detection ability are desirable. A focus of re-gression testing research has been the reduction of test suitesize between versions. This can be accomplished throughtest suite selection [15]. A further improvement, once testsare selected, is to order orprioritize[16] test cases to in-crease the likelihood of faults being discovered early in thetest process.

4 Detecting faults early, means that work to re-pair faults can begin sooner, and if resources are exhaustedbefore all tests complete, the consequences are less much of Regression testing research has fo-cused on test suite selection and prioritization, the originaltest suite generated and used during the lifetime of evolv-ing software is also important. The quality of this test suitesets the upper bound for the quality of selected tests, andimpacts the ability to order test suites effectively in all suc-cessive specification based test generation technique is touse the category partition method and the Test Specifica-tion Language or TSL [14] to define program parametersand environments and partition the resulting categories intochoices.

5 The choices are combined to generate test are added to categories and choices to reducethe test space since combining all choices of these cate-gories results in a Combinatorial related specification based technique for generatingtest suites is Combinatorial Interaction testing [3, 5, 6, 12,19] orCIT, although less is known about its use in regres-sion testing . In CIT the program is divided into partitions asin TSL. To reduce the final number of test cases, parametersare tested together so that allt-way combinations appear atleast once. This technique has been shown to produce smalltest suites, with high code coverage, that exhibit good faultdetection ability [5, 7, 19].

6 Although CIT has shown to be an effective test genera-tion technique, it has mostly been examined in the contextof single version software systems. There has been littleresearch examining the effectiveness of CIT in regressiontesting, applied across evolving versions of a software pro-gram. Furthermore, there is no work that applies prioritiza-tion techniques to such an environment. In [4] Bryce andColbourn present an algorithm toprioritizeCIT test do not, however, experiment on real software subjects,nor do they address the key element of weighting the vari-ous elements that drive prioritization. Additionally, it is ourobservation that their prioritization technique is a combinedgeneration and prioritization technique, rather than pure pri-oritization, since it does not re-order tests, but re-generatesthem each time.

7 We call this techniquere-gen/prio. This issimilar to the work of Avritzer et al. [2] who also present anordered test generation leaves us with several questions. We would like tounderstand if CIT is effective when used in Regression test-ing for multiple versions of a program. We would also liketo understand if prioritization improves early fault detectionin CIT test suites, and finally, we would like to understandhowto prioritize CIT test this paper we address each of these issues. We haveconducted an empirical Study on two software subjects,each with multiple successive versions. We first examinethe effectiveness of CIT test suites compared with an ex-haustive strategy.

8 We then apply both prioritization and re-gen/prio and compare their effectiveness on CIT test examine several different ways to control the prioriti-zation. We use methods that leverage code coverage fromprior releases, as well as one that is specification based. Ourresults show that the CIT test suites may be an effective wayto reduce the test space and that prioritization improves theability to detect faults early in certain rest of this paper is organized as follows. Section2 presents related work on Regression testing and combina-torial Interaction testing , Section 3 discusses prior work onprioritization algorithms for CIT and presents methods forweighting the prioritization.

9 Section 4 introduces our em-pirical Study . Section 5 presents our results and Section 6concludes and presents future BackgroundIn this section we provide some background on regres-sion testing and Combinatorial Interaction Test Case Selection and PrioritizationThe test caseselectionproblem can be stated as an initial version of a programPand a set of testcases,T, select a subset of tests fromT,T to test a newversion of programP,P [16]. The simplest method istore-test all. However, this suffers from the problem ofaccumulating too many tests over time. Other techniquesincludecode coverage,dataflow,minimization,safeandad -hoc/random[10]. In this paper we do not address thetest case selection problem.

10 Instead we generate CIT testsuites that are already small in size and use there-test allapproach. Prioritization techniques [9, 13, 16, 17] comple-ment the selection technique. In prioritization test cases areordered to improve the likelihood that faults will be detectedearly in the testing process. Techniques for prioritization in-clude statement coverage, function coverage and fault find-ing exposure, among others [9, 13, 16, 17]. Test Case Specification LanguageThe Test Specification Language [14] is a specificationbased method to define the combinations of program param-eters that should be tested together. TSL partitions the sys-tem inputs into parameters and environments which makeup the categories.