Reducing Redundant Test Executions in Software Product Line Testing—A Case Study

Abstract

In the context of software product line (SPL) engineering, test cases can be reused for testing a family of products that share common parts of source code. An approach to test the products of a product family is to exhaustively execute each test case on all the products. However, such an approach would be very inefficient because the common parts of source code will be tested multiple times unnecessarily. To reduce unnecessary repetition of testing, we previously proposed a method to avoid equivalent test executions of a product line in the context of regression testing. However, it turns out that the same approach can be used in a broader context than just regression testing of product families. In this paper, we argue the generality of the method in the sense that it can be used for testing of the first version of a product family as well as regression testing of its subsequent versions. In addition, in this paper, in order to make the method practically usable for users, we propose a process for applying it to SPL testing. We demonstrate the generality of our method and the practical applicability of the proposed process for the method by conducting a case study.

1. Introduction

Software product line (SPL) engineering is a paradigm of software development for reusing managed artifacts to produce a product family that shares common artifacts [1] (pp. 14–15). In a product family, products are different, yet similar to each other. Due to the commonality shared between products, exhaustively testing all the products of a product family would have much redundancy and result in an unnecessarily high testing cost.

To reduce such redundancy, combinatorial techniques [2,3,4,5,6] have been proposed. They reduce the number of products to test by selecting only a subset of products to increase the coverage of combinatorial feature interactions. However, the redundancy problem still remains with the techniques because the selected products of a product family would have to be individually tested as they do not provide ways of exploiting commonality between selected products. To overcome this drawback, delta-oriented techniques [7,8,9,10,11] have been proposed. They reduce unnecessary testing by reusing test cases of one product of a product family for the other products of the family that share common artifacts. However, when test cases are executed on the products that reuse them, these test executions can include redundant test executions that traverse the same sequence of code statements and produce the same test results (i.e., pass or fail). For this reason, in the context of SPL testing, there is a possibility of reducing test redundancy at the level of test executions, in addition to the levels of products or test cases.

Given a set of test cases T, let E_T be the set of test executions obtained by applying the test cases in T and Faults(E_T) be the set of the faults that are detected by E_T. A test execution e in E_T is said to be a redundant test execution of T if Faults(E_T − {e}) = Faults(E_T) (i.e., e does not help finding faults). Redundant test executions can occur when two products have common source code [12]. For example, when products of a product family, say P1, P2 and P3, have the same feature that is independent of other features, if the feature has been tested in P1, then testing it again in P2 would be redundant because it does not increase the chance of detecting defects in the feature. The existing variability-aware test execution methods [13,14,15] reduce redundant test executions for a configurable system by executing it so that the source code common to multiple configurations is covered only once. With some adjustments, the methods can be applied to testing of a product line that produces a set of products which are obtained by assembling a set of code fragments of the product line. However, their methods do not address the execution of existing test cases and thus cannot be applied to regression testing of a product line.

In our previous work [16], we proposed a method of reducing redundant test executions of a product line in the context of regression testing. Given a modified product family and a set of test cases selected for a retest through an existing regression test selection method, our previously proposed method (to be abbreviated as our method in this paper) builds the checksum matrix for the modified product family, which contains checksum values of every code unit (i.e., a section of code written in a programming language that can be executed [16]) of the family. The checksum value of a code unit is computed by applying a hash function to the statements of the code unit. Using the checksum matrix, our method avoids repetitions of equivalent test executions by identifying products where a test case covers the same sequence of identical code units. Through these steps, it reduces the total number of test executions by avoiding test executions that will produce the same execution traces and test results. However, the method focused only on the context of regression testing.

The products of a product family can be viewed as different versions of one product of the family. Then, differences between two products of a family can be viewed as regression deltas. Thus, a regression testing strategy can be applied for testing of a (single version of) software product line [7]. Several techniques [7,8,9,10,11] on SPL testing applied regression testing strategies for SPL testing and reported its validity and effectiveness. Along this direction, our method, which was originally proposed for SPL regression testing in [16], can also be applied for the testing of the initial version of a software product line, not just for its subsequent versions.

In this paper, we argue the generality of our method in the sense that it can be used for the testing of the first version of a software product line as well as the regression testing of its subsequent versions. Also in this paper, we propose an SPL testing process for applying our method and provide an algorithm for reducing redundant test executions, which improves the algorithm of our previous work [16]. Based on the process and the algorithm, we conduct a case study. As the SPL of our case study, we use the VendingMachine SPL because it has been well documented [17] and served as benchmarks in the literature [18].

This paper makes the following contributions:

• We extend our previous method [16] to make it more practicable by providing an improved algorithm that avoids equivalent test executions in order to reduce unnecessary repetition of test executions and unnecessary collection of test execution traces.
• We propose a practical process for applying our method to testing of the first version of a product family as well as regression testing of its subsequent versions.
• Through a case study based on the proposed process, we demonstrate the generality of our method and how it can be used for efficient testing of software product lines. The case study shows that, for the first version and its two subsequent versions of the VendingMachine SPL, our method reduces 42.3% of test executions compared to the exhaustive execution.

The rest of the paper is organized as follows: Section 2 describes how to identify equivalent test executions; Section 3 presents an SPL testing process and an improved version of our previous algorithm for avoiding equivalent test executions; Section 4 demonstrates the generality of our method through a case study; in Section 5, we discuss related work regarding SPL testing; finally, in Section 6, we conclude the paper.

2. Equivalence of Test Executions in SPL

This section provides an example with code snippets to illustrate the notion of equivalence of test executions in SPL that was defined in our previous paper [16]. Figure 1 shows the Lock module of the DoorLock SPL, which has one variation point (i.e., Lock) and three variants (i.e., Fingerprint Scanner, Keypad and Magnetic Card). The Lock variation point has an alternative relationship with its variants, which requires that only one variant among its variants can be selected to produce a product. When a variant is selected to produce a product, the corresponding code is enabled and the code for the other variants is disabled. For example, if the Fingerprint Scanner is selected, line 5 of the Lock class and the code of the FingerPrintAccess class are enabled and lines 6 and 7 of the Lock class and the code of the PINAccess and MagneticAccess classes are disabled. It is assumed that none of the classes in the Lock module contain non-deterministic functions (e.g., the random function). Based on this principle, the DoorLock SPL can produce a set of products as a product family by selecting, for each product, variants of variation points for all the modules (including the modules omitted in this example). We denote the set of products containing the Fingerprint Scanner variant as P_FS, the set of products containing the Keypad variant as P_K, the set of products containing the Magnetic Card as P_MC and the set of all products that can be produced from the DoorLock SPL as P_ALL. Then, P_ALL is equal to P_FS ∪ P_K ∪ P_MC.

Let us suppose that test cases t1, t2, t3 and t4 are used to test products in P_ALL. In this case, the executions of t1 applied to the products in P_FS are equivalent because, for each product p $\in$ P_FS, t1 traverses only FingerPrintAccess on any p $\in$ P_FS and the source code of the FingerPrintAccess class is the same for all the products in P_FS. Likewise, the executions of t2 applied to the products in P_K are equivalent and the executions of t3 applied to the products in P_MC are equivalent. Therefore, executing each test case on all the relevant products is redundant [16].

3. SPL Testing Process for Avoiding Equivalent Test Executions

In this section, we argue the generality of our method and present a practical process for applying our method to SPL testing in general including regression testing.

In our previous work [16], our method was presented in the context of regression testing where the regression testing is performed by executing only a subset of the existing test cases that is affected by changes. That is, in our method, regression testing is performed by executing a subset of the previous version of test cases on the current version of product family. A special case of this “current version” is the first version. If a testing method requires artifacts (e.g., fault detection history, change information, code dependencies, etc.) from the previous version of product family, the method cannot be used for testing of the first version. However, our method uses only the artifacts for the current version of product family, without relying on the artifacts from the previous version of product family. For this reason, our method of avoiding redundant test executions for regression testing, which is a testing of the second and later versions, can be used for testing of the very first version of the product family by using the full set of test cases as input. This implies that our method is general enough for testing of any version of a product family including the first version.

Figure 2 shows a process for avoiding equivalent test executions that can be used in the general cases (i.e., the testing of one SPL version and the regression testing of its subsequent versions). The inputs are (1) the code base of a product line and (2) the test cases of the product line. The process first obtains a product family (in Step 1) and constructs its checksum matrix (in Step 2). Then, it selects test cases to run (in Step 3) and executes them (in Step 4). Generation of new test cases and deletion of obsolete test cases are not the scope of this paper. Therefore, we assume that the initial set of test cases is given and that new test cases are generated and obsolete test cases are deleted when a product line is modified. The resulting set of test cases is used as the input, i.e., ‘Test cases of a product family’ shown in the bottom part of Figure 2.

The proposed application process includes a minimal set of steps necessary to apply our method to SPL testing. Thus, for the full testing of a product line, additional steps for minimization and prioritization of test cases, change impact analysis, etc. can be added to the process.

3.1. Step 1: Obtain a Product Family

This step obtains a product family from the code base of a product line. At the time of testing the first version, all the products of a product family are instantiated from the code base. However, when changes are made to a product line code base, a new version of product family is obtained in this step by propagating changes to the products instantiated from the modified code base. The change propagation technique [19] can be used for this step.

3.2. Step 2: Build/Update Checksum Matrix

To check whether two code units are identical, our method compares their checksums. If the checksums of the two code units are the same, then they are identical, and otherwise, they are not identical. To store the checksum values of code units, this step builds the checksum matrix for a product family. For each product of a product family, it obtains a set of code units from the product. Then, for each code unit, it computes its checksum value and stores it to the checksum matrix.

Table 1. An example of checksum matrix.

	Class	Foo.class	Bar.class	Baz.class
Product
P1		9da53bba	8a841cc2	-
P2		9da53bba	-	30cea121
P3		f253ab1c	83523abb	-

shows an example of the checksum matrix for a product family consisting of P1, P2 and P3 implemented in the Java language. In this example, 8-bit checksum is used. This example checksum matrix shows that P1 and P3 contain Foo.class and Bar.class and P2 contains Foo.class and Baz.class. It also shows that Foo.class for P1 is identical to that for P2 as their checksum values are the same. The checksum matrix of a product family is built only once at the time of testing the first version of the family. From the next version of the family, this step updates the existing checksum matrix by modifying only the checksum values of changed classes.

3.3. Step 3: Select Test Cases to Execute

This step selects test cases to be executed on the products of a product family. At the time of testing the first version of a product line, the full set of test cases is selected. However, at the time of regression testing of its subsequent versions, this step selects a subset of the existing test cases that is affected by changes. The existing regression test selection approach can be used to select regression test cases. In our case study to be presented in Section 4, we apply the approach of Lity et al. [7], which selects test cases that traverse changes. For example, if a class of a product line has changed and a test case traverses the class, the test case is selected for regression testing of the product line.

3.4. Step 4: Execute Test Cases and Collect Execution Traces

This step executes test cases selected in Step 3 on the products of a product family and collects their test execution traces. For collection of test execution traces, the bytecode instrumentation library such as ASM [20] and BCEL [21] can be used. To reduce redundant test executions, this step uses the testExecution function of Algorithm 1, which is a generalized version of our previous algorithm [16]. Like its previous version, Algorithm 1 avoids unnecessary execution of test cases and unnecessary collection of test execution traces. However, unlike our previous algorithm, Algorithm 1 allows the testing of the first version as well as the testing of its subsequent versions, which makes our method a general SPL testing method.

Algorithm 1 An algorithm for avoiding equivalent test executions

Input: TP: target products Input: SelectedTCs: set of test cases selected from Step 3 Input: chksumMatrix: checksum matrix for a product family Use:execute(t, p): execute a test case t on a product p         and collect the execution trace of t on p 1.  function testExecution(TP, chksumMatrix) 2.   Map ETrace ← ∅    // key: test case, value: set of traces 3.   for each p ∈ TP do: 4.      T ← SelectedTCs.for(p) 5.      CandidateTCs.addAll(T) 6.      foreach t ∈ T do: 7.         TR ← ETrace.getTracesOf(t) 8.         for each tr ∈ TR do: // tr: classes covered by t on products 9.             chksumListA ← chksumMatrix.lookup(p, tr.classes) 10.               chksumListB ← chksumMatrix.lookup(tr.product, tr.classes) 11.            if chksumListA equals chksumListB then: 12.              CandidateTCs.delete(t) 13.            end if 14.        end for 15.     end for 16.     pairs <TestCase, Trace> ← execute(CandidateTCs, p) 17.     ETrace.appendAll(pairs) 18.     CandidateTCs ← ∅ 19.  end for 20. end function

For each product (p) of target products (TP), it obtains the test cases for p (lines 3–4) and adds these test cases to a set of the candidate test cases (CandidateTCs) (line 5). At the time of testing the first version of a product family, all products of the family are used as TP and at the time of regression testing of a product family, the changed products of the family are used as TP. Then, for each test case (t) for p, if p has classes that are identical to classes that t traversed on the previously tested one product, then the execution of t on p is excluded from CandidateTCs (lines 6–15) because the executions of t on the two products would be equivalent (Cf. Section 2). In this step, the order of selecting products and test cases does not affect the number of repetitions of test case execution. Finally, all the test cases in CandidateTCs are executed on p and their execution traces are collected for the testing of the next product (lines 16–18). This algorithm executes all the test cases of a product if it is the first chosen product of a product family. However, from the next product, the algorithm selectively executes test cases for the product, avoiding equivalent test executions. To identify the code units that are covered by each test case, this algorithm executes all the test cases at least once on a product of the family.

4. Case Study Using the VendingMachine SPL

In this section, we conduct a case study that applies the process for SPL testing presented in Section 3 (Figure 2). We use the VendingMachine SPL for this case study because its behavioral specifications and evolving scenarios have been well documented [17]. We apply the process to the testing of the first version of the VendingMachine SPL, SPL_V0, (in Section 4.1) and the regression testing of its subsequent versions, SPL_V1 and SPL_V2 (in Section 4.2 and Section 4.3). Then, we discuss the results (in Section 4.4).

Figure 3 shows the feature model for SPL_V0. We first implemented features of the feature model using Java language, based on the behavioral specifications of the document [17]. These features were implemented using classes with the same name as the feature name except the VendingMachine feature. The VendingMachine feature was implemented using three classes whose names are VMachine, DrinkOrder and Display. Then, we generated the nine test cases for the first version of the product line, as specified in

Table 2. Test cases for SPL_V0.

Test Case	Input	Expected Output	Description
t1	1	True	Checks whether a cup of tea is provided when 1 is inputted.
t2	2	True	Checks whether a cup of coffee is provided when 2 is inputted.
t3	3	True	Checks whether a cup of cappuccino is provided when 3 is inputted.
t4	“Coffee”	True	Checks whether sugar is poured when a cup of coffee is made.
t5	1	“1 Euro”	Checks whether “1 euro” is displayed when 1 euro is inserted.
t6	5	“5 Dollars”	Checks whether “5 dollars” is displayed when 5 dollars is inserted.
t7	BeberageDelevered(=True)	True	Checks whether a tone is emitted when a beverage has been delivered.
t8	Ring-Off(=False)	False	Checks whether the turn-off switch of the ring correctly works.
t9	ErrNotEnough Sugar(=1)	“not enough sugar”	Checks whether an error message is displayed.

. Each test case validates the expected output for a given input, executing a subset of classes. Finally, we defined a product family consisting of four products.

Table 3. A product family SPL_V0.

Product (LOC)	Test Case	Feature Configuration	Class Set
P1 (167)	t1, t5, t7, t8, t9	VendingMachine, Beverages, Tea, RingTone, Currency, Euro	VMachine, DrinkOrder, Display, Beverages, Tea, RingTone, Currency
P2 (167)	t3, t6, t7, t8, t9	VendingMachine, Beverages, Cappuccino, RingTone, Currency, Dollar	VMachine, DrinkOrder, Display, Beverages, Cappuccino, RingTone, Currency
P3 (182)	t2, t3, t4, t6, t7, t8, t9	VendingMachine, Beverages, Coffee, Cappuccino, RingTone, Currency, Dollar	VMachine, DrinkOrder, Display, Beverages, Coffee, Cappuccino, RingTone, Currency
P4 (140)	t1, t5, t9	VendingMachine, Beverages, Tea, Currency, Euro	VMachine, DrinkOrder, Display, Beverages, Tea, Currency

lists the identifier of each product with the lines of code (LOC) in parentheses, test cases, feature configuration, and class set. Because each product contains a different set of classes, a different set of test cases is assigned to each product.

4.1. Testing of the Initial Version of a Product Line (Testing of SPL_V0)

In this section, we present a testing of the first version of the VendingMachine SPL.

Step 1. Obtain a product family. Because this is the first testing of a product family, all the products of the family, i.e., P1, P2, P3 and P4, are instantiated from the code base. Then, the corresponding classes are assembled for each product as presented in Table 3.

Step 2. Build/update checksum matrix. The checksum matrix for the VendingMachine product family is constructed.

Table 4. The checksum matrix for SPL_V0.

	Class	VMachine	Beverages	Coffee	Tea	Cappuccino	DrinkOrder	RingTone	Currency	Display
Product
P1		a	e	-	g	-	i	k	l	n
P2		b	e	-	-	h	j	k	m	n
P3		c	e	f	-	h	j	k	m	n
P4		d	e	-	g	-	i	-	l	n

presents the checksum matrix of the family. To simplify the example, we present the checksum value as a single character (e.g., a, b, c and d). Two classes with the same character indicate that their checksum values are the same and so they have an identical source code. The checksum values (i.e., a, b, c and d) of the VMachine class are different for the products of the family because each product provides a different set of beverages and so the source code of the VMachine classes are different for the products. In addition, the checksum value (i.e., i) of the DrinkOrder class for P1 and P4 is different from that for P2 and P3 (i.e., j) because P1 and P4 provide only sugar for serving beverages but P2 and P3 provide milk in addition to sugar. The checksum value (i.e., l) of the Currency class for P1 and P4 is different from that (i.e., m) for P2 and P3 because P1 and P4 use euro for payment while P2 and P3 use dollar.

Step 3. Select test cases to execute. Because this is the testing of the first version of a product family, all the test cases, i.e., 9 test cases, are selected.

Step 4. Execute test cases and collect execution traces. If all the test cases are executed exhaustively on all the products that use the test cases, the total number of test executions is 20. To reduce redundant executions of the test cases, we use Algorithm 1. Because this is the first testing of the product family, all the products of the family are used as the input of the algorithm, ‘TP’. First, all test cases for P1 are executed and their execution traces are collected as presented in

Table 5. Execution traces of test cases and their checksum values for SPL_V0.

Test Case	Used Products	Test Execution Trace	Checksum Values
t1	P1, P4	{P1}: [VMachine, Currency, Beverages, DrinkOrder, Tea, RingTone, Display] {P4}: [VMachine, Currency, Beverages, DrinkOrder, Tea, Display]	P1: aleigkn, P4: dleign
t2	P3	{P3}: [VMachine, Currency, Beverages, DrinkOrder, Coffee, RingTone, Display]	P3: cmejfkn
t3	P2, P3	{P2, P3}: [VMachine, Currency, Beverages, DrinkOrder, Cappuccino, RingTone, Display]	P2: bmejhkn, P3: cmejhkn
t4	P3	{P3}: [DrinkOrder]	P3: j
t5	P1, P4	{P1, P4}: [Currency, Display]	P1: ln, P4: ln
t6	P2, P3	{P2, P3}: [Currency, Display]	P2: mn, P3: mn
t7	P1, P2, P3	{P1, P2, P3}: [DrinkOrder, RingTone]	P1: ik, P2: jk, P3: jk
t8	P1, P2, P3	{P1, P2, P3}: [RingTone]	P1: k, P2: k, P3: k
t9	P1, P2, P3, P4	{P1, P2, P3, P4}: [Display]	P1: n, P2: n, P3: n, P4: n

. For example, t1 is executed on P1 in the sequence of VMachine, Currency, Beverages, DrinkOrder, Tea, RingTone and Display and is executed on P4 in the sequence of VMachine, Currency, Beverages, DrinkOrder, Tea and Display. After that, for each test case of the next product, P2, if P2 has a set of classes identical to a set of classes that the test case traversed on P1, then the test case is not executed on P2. In our case study, as Table 4 and Table 5 show, t8 traversed the RingTone class on P1 and the RingTone class for P1 is identical to that for P2 (i.e., the checksum values are the same as ‘k’). Thus, t8 is not executed on P2 because the test executions of t8 on P1 and P2 would be equivalent. In the same way, t9 is not executed on P2, too. By the same principle, for the testing of P3, the executions of t6, t7, t8 and t9 are avoided and for the testing of P4, t5 and t9 are avoided because their executions would be equivalent on previously tested products. Consequently, 8 test executions are reduced and so the total number of test executions is 12.

4.2. Modification for Adding New Test Cases (Testing of SPL_V1)

When a product line is modified, new features can be added to the product line and new test cases can be generated to verify these features. As the modified product line in Figure 4 shows, features for beverage size are added and the Size feature has an ‘exclude’ relationship with the Dollar feature. Thus, only when the Euro feature is selected, different choices for the beverage size are allowed. We marked the changed parts using a dotted line. Based on the evolving scenario, we modified the DrinkOrder class of the product line code base so that choosing features of different beverage sizes is allowed. Then, we generated new test cases for new features, as specified in

Table 6. New test cases for SPL_V1.

Test Case	Input	Expected Output	Description
t10	1	“Small”	Checks whether a small size beverage is chosen.
t11	2	“Regular”	Checks whether a regular size beverage is chosen.
t12	3	“Large”	Checks whether a large size beverage is chosen.

. For test case generation, we used the method of Lity et al. [7]. Finally, we modified the VendingMachine product family by adding new features for beverage size, presented as bold type in

Table 7. A product family SPL_V1. Features or classes changed in SPL_V0 are presented as bold type.

Product (LOC)	Test Case	Feature Configuration	Class Set
P1 (194)	t1, t5, t7, t8, t9, t10, t11, t12	VendingMachine, Beverages, Tea, RingTone, Currency, Euro, Size, Small, Regular, Large	VMachine, DrinkOrder, Display, Beverages, Tea, RingTone, Currency
P2 (167)	t3, t6, t7, t8, t9	VendingMachine, Beverages, Cappuccino, RingTone, Currency, Dollar	VMachine, DrinkOrder, Display, Beverages, Cappuccino, RingTone, Currency
P3 (182)	t2, t3, t4, t6, t7, t8, t9	VendingMachine, Beverages, Coffee, Cappuccino, RingTone, Currency, Dollar	VMachine, DrinkOrder, Display, Beverages, Coffee, Cappuccino, RingTone, Currency
P4 (167)	t1, t5, t9, t10, t11, t12	VendingMachine, Beverages, Tea, Currency, Euro, Size, Small, Regular, Large	VMachine, DrinkOrder, Display, Beverages, Tea, Currency

. Only the feature configurations for P1 and P4 have been modified because P2 and P3 have the Dollar feature, which is mutually exclusive with the Size feature.

Step 1. Obtain a product family. Changes of the DrinkOrder class are propagated to P1 and P4, and P2 and P3 remain the same as their previous versions.

Step 2. Build/update checksum matrix. This step updates the existing checksum matrix by re-computing the checksum of the modified class (i.e., the DrinkOrder class).

Table 8. The checksum matrix for SPL_V1. Checksum values changed in SPL_V0 are presented as bold type.

	Class	VMachine	Beverages	Coffee	Tea	Cappuccino	DrinkOrder	RingTone	Currency	Display
Product
P1		a	e	-	g	-	o	k	l	n
P2		b	e	-	-	h	j	k	m	n
P3		c	e	f	-	h	j	k	m	n
P4		d	e	-	g	-	o	-	l	n

presents the updated checksum matrix of the VendingMachine product family. Because the evolving scenario affects only the DrinkOrder class, only the checksum values of the DrinkOrder class change and the other values remain the same. We presented the changed values in bold in Table 7.

Step 3. Select test cases to execute. All the new test cases, t10, t11 and t12, are selected to test new features relevant to beverage size. Additionally, because the DrinkOrder class changed according to the evolving scenario, the test cases that traversed the DrinkOrder class in the previous version are selected. In our case, t1, t2, t3, t4 and t7 are selected since as presented in Table 5, they traversed the DrinkOrder in the previous version.

Step 4. Execute test cases and collect execution traces. If the test cases selected in Step 3 (i.e., t1, t2, t3, t4, t7, t10, t11 and t12) are executed exhaustively, the total number of test executions is 15. However, these test executions include redundant test executions, and our algorithm can reduce them in the context of regression testing as well. Because P1 and P4 have been affected by the changes, only these products are targets for regression testing and used as the input ‘TP’ of Algorithm 1. The algorithm first executes the test cases applicable to P1 (i.e., t1, t7, t10, t11 and t12).

Table 9. Execution traces of test cases and their checksum values for SPL_V1. Checksum values changed in SPL_V0 are presented as bold type.

Test Case	Used Products	Test Execution Trace	Checksum Values
t1	P1, P4	{P1}: [VMachine, Currency, Beverages, DrinkOrder, Tea, RingTone, Display] {P4}: [VMachine, Currency, Beverages, DrinkOrder, Tea, Display]	P1: aleogkn, P4: dleogn
t2	P3	{P3}: [VMachine, Currency, Beverages, DrinkOrder, Coffee, RingTone, Display]	P3: cmejfkn
t3	P2, P3	{P2, P3}: [VMachine, Currency, Beverages, DrinkOrder, Cappuccino, RingTone, Display]	P2: bmejhkn, P3: cmejhkn
t4	P3	{P3}: [DrinkOrder]	P3: j
t5	P1, P4	{P1, P4}: [Currency, Display]	P1: ln, P4: ln
t6	P2, P3	{P2, P3}: [Currency, Display]	P2: mn, P3: mn
t7	P1, P2, P3	{P1, P2, P3}: [DrinkOrder, RingTone]	P1: ok, P2: jk, P3: jk
t8	P1, P2, P3	{P1, P2, P3}: [RingTone]	P1: k, P2: k, P3: k
t9	P1, P2, P3, P4	{P1, P2, P3, P4}: [Display]	P1: n, P2: n, P3: n, P4: n
t10	P1, P4	{P1, P4}: [DrinkOrder, Display]	P1: on, P4: on
t11	P1, P4	{P1, P4}: [DrinkOrder, Display]	P1: on, P4: on
t12	P1, P4	{P1, P4}: [DrinkOrder, Display]	P1: on, P4: on

shows the test execution traces and their checksum values. Checksum values of test execution traces that contain a changed class (i.e., the DrinkOrder class for P1 and P4) change. We presented the values changed from the values in the previous version in bold. Then, when the test cases applicable to P4 (i.e., t1, t10, t11 and t12) are executed, the executions of t10, t11 and t12 are excluded because P4 has a set of classes identical to a set of classes that these test cases traversed on P1, which indicates that their test executions would be equivalent. For example, t10 traversed the DrinkOrder class and the Display class on P1 and those classes for P1 are identical to those for P4 (i.e., the checksum values are the same as ‘on’). For this reason, the execution of t10 on P4 is redundant. Even though t2, t3 and t4 are selected in Step 3, they are not executed on any products because they have not been used for the changed products, P1 or P4. Consequently, 9 test executions are reduced and so the total number of test executions is 6.

4.3. Modification Affecting Existing Test Cases (Testing of SPL_V2)

Some modifications in a product line can affect the existing test cases by causing them to traverse different classes depending on the products to be tested. As the modified product line in Figure 5 shows, the feature for small beverage size is deleted and the Milk feature is newly added. The Milk feature has the ‘require’ relationships with the ‘Cappuccino’ feature. So only a product that offers cappuccino has the Milk feature. According to this evolving scenario, we first added the Milk class to the product line code base and implemented its functions that when a cup of cappuccino is made, a cup of milk is supplied and when the amount of milk is not enough, the VendingMachine displays an error message. Next, to support the milk supply and stop serving the small size of beverages, we modified the DrinkOrder class. Due to this modification, the code coverages of the existing test cases are changed. Then, as specified in

Table 10. New test cases for SPL_V2.

Test Case	Input	Expected Output	Description
t13	0	ErrNotEnoughMilk	Checks whether the ErrNotEnoughMilk event is created when the amount of milk is not enough.

, we generated new test cases for the Milk feature. Finally, as presented in

Table 11. A product family SPL_V2. Features or classes changed in SPL_V1 are presented as bold type.

Product (LOC)	Test Case	Feature Configuration	Class Set
P1 (189)	t1, t5, t7, t8, t9, t10, t11, t12	VendingMachine, Beverages, Tea, RingTone, Currency, Euro, Size, Regular, Large	VMachine, DrinkOrder, Display, Beverages, Tea, RingTone, Currency
P2 (185)	t3, t6, t7, t8, t9, t13	VendingMachine, Beverages, Cappuccino, RingTone, Currency, Dollar, Milk	VMachine, DrinkOrder, Display, Beverages, Cappuccino, RingTone, Currency, Milk
P3 (200)	t2, t3, t4, t6, t7, t8, t9, t13	VendingMachine, Beverages, Coffee, Cappuccino, RingTone, Currency, Dollar, Milk	VMachine, DrinkOrder, Display, Beverages, Coffee, Cappuccino, RingTone, Currency, Milk
P4 (162)	t1, t5, t9, t10, t11, t12	VendingMachine, Beverages, Tea, Currency, Euro, Size, Regular, Large	VMachine, DrinkOrder, Display, Beverages, Tea, Currency

, we modified the feature configurations for all the products of the VendingMachine product family by adding the Milk feature or deleting the Small feature for the relevant products.

Step 1. Obtain a product family. Changes of the DrinkOrder class are propagated to all the products and addition of the Milk feature is propagated to P2 and P3.

Step 2. Build/update checksum matrix. This step updates again the previous version of the checksum matrix by computing the checksum value of the DrinkOrder class and the Milk class, as presented in

Table 12. The checksum matrix for SPL_V2. Checksum values changed in SPL_V1 are presented as bold type.

	Class	VMachine	Beverages	Coffee	Tea	Cappuccino	DrinkOrder	RingTone	Currency	Display	Milk
Product
P1		a	e	-	g	-	p	k	l	n	-
P2		b	e	-	-	h	q	k	m	n	r
P3		c	e	f	-	h	q	k	m	n	r
P4		d	e	-	g	-	p	-	l	n	-

. Thus, the checksum values of the DrinkOrder class change for all the products and the checksum values for the Milk class are added to columns for P2 and P3. The other values remain the same.

Step 3. Select test cases to execute. t13 is selected for retest because it is a new test case. Additionally, t1, t2, t3, t4, t7, t10, t11 and t12 are selected since they traversed the changed class (i.e., DrinkOrder class) in the previous version, as presented in Table 9.

Step 4. Execute test cases and collect execution traces. Because all the products have been affected by the changes, all the products of the family are targets for regression testing. The algorithm first executes the test cases applicable to P1 (i.e., t1, t7, t10, t11 and t12).

Table 13. Execution traces of test cases and their checksum values for SPL_V2. Checksum values changed in SPL_V1 are presented as bold type.

Test Case	Used Products	Test Execution Trace	Checksum Values
t1	P1, P4	{P1}: [VMachine, Currency, Beverages, DrinkOrder, Tea, RingTone, Display] {P4}: [VMachine, Currency, Beverages, DrinkOrder, Tea, Display]	P1: alepgkn, P4: dlepgn
t2	P3	{P3}: [VMachine, Currency, Beverages, DrinkOrder, Coffee, RingTone, Display]	P3: cmeqfkn
t3	P2, P3	{P2, P3}: [VMachine, Currency, Beverages, DrinkOrder, Cappuccino, RingTone, Display]	P2: bmeqhkn, P3: cmeqhkn
t4	P3	{P3}: [DrinkOrder]	P3: q
t5	P1, P4	{P1, P4}: [Currency, Display]	P1: ln, P4: ln
t6	P2, P3	{P2, P3}: [Currency, Display]	P2: mn, P3: mn
t7	P1, P2, P3	{P1, P2, P3}: [DrinkOrder, RingTone]	P1: pk, P2: qk, P3: qk
t8	P1, P2, P3	{P1, P2, P3}: [RingTone]	P1: k, P2: k, P3: k
t9	P1, P2, P3, P4	{P1, P2, P3, P4}: [Display]	P1: n, P2: n, P3: n, P4: n
t10	P1, P4	{P1, P4}: [DrinkOrder, Display]	P1: pn, P4: pn
t11	P1, P4	{P1, P4}: [DrinkOrder, Display]	P1: pn, P4: pn
t12	P1, P4	{P1, P4}: [DrinkOrder, Display]	P1: pn, P4: pn
t13	P2, P3	{P2, P3}: [DrinkOrder, Milk, Display]	P2: qrn, P3: qrn

shows the test execution traces and their checksum values. Next, the test cases applicable to P2 (i.e., t3, t7 and t13) are executed. At this time, no test execution is avoided because t3 and t13 were not previously executed on any products and t7 were executed on P1 but P2 does not have the identical set of classes that t7 traversed on P1. In the same way, for the test cases applicable to P3 (i.e., t2, t3, t4, t7 and t13), the algorithm does not execute t7 and t13 on P3, and for the test cases applicable to P4 (i.e., t1, t10, t11 and t12), the algorithm does not execute t10, t11 and t12 on P4. In summary, 5 test executions are reduced and so the total number of test executions is 12.

4.4. Threats to Validity

In the case study, the reliability of the target product line can be a threat to the validity of the case study. To mitigate this problem, we selected the vending machine product line, which has been well documented [17] and evaluated [7]. Moreover, we chose from the document evolving scenarios that can show various application cases of our method.

The overhead of our method more or less depends on the programming language. In the case of the Java language, even though multiple classes are implemented in a single file, separate class files are produced. In this case, checksum comparison between two classes is not costly. However, in the case of the C++ language, the overhead in parsing each class from a file occurs in order to conduct checksum comparison between two classes. This overhead can be reduced by using a code unit of a coarser level of granularity. However, the effect in reducing repetitions of test execution may decrease.

4.5. Result and Discussion

Scope of this work. In our previous paper [16], we proposed a method of reducing redundant test executions of a product line. However, it focused on constructing technical theory for our method and it did not provide a practical guidance on how to apply our method. Moreover, the previous paper focused only on the context of regression testing even if with some adjustments it can be generalized to the initial version of a product line. For these reasons, as a follow-up work of our previous paper, this paper proposed a generalized process for applying our method to testing of the initial version of a product family as well as regression testing of its subsequent versions, an improved algorithm that avoids equivalent test executions, and demonstrated the generality under the proposed process. Scalable evaluation is not the scope of this work, and we will perform such extended evaluation in future work.

Result of the case study. In this case study, we tested three versions of the VendingMachine SPL under the application process presented in Figure 2. For the first version, SPL_V0, and its two subsequent versions, SPL_V1 and SPL_V2, overall, our method reduced test executions by 42.3% (={12 + 6 + 12}/{20 + 15 + 17}) compared to the exhaustive execution. This case study shows how our method works to reduce repetitions of equivalent test executions, and its result demonstrates the practical applicability of the proposed process for the method and the generality of our method.

Impacts of commonality and size of a product family. This effect can increase when a product family with a lot of commonality is used, because the more commonality a product family has, the more the products of a product family will reuse test cases and so the more our method will reduce (equivalent) test executions. Moreover, our method is more effective when it is applied to a product family that contains many products because, as test cases are reused for more products, our method reduces equivalent test executions more.

Cost reduction and fault detection effect. Our method can be used when the first version of a product family has been developed and whenever the product family has changed. Thus, it can reduce the significant amount of SPL testing cost during the testing phase and the maintenance phase of the software development lifecycle. Nonetheless, our method does not miss faults that would be detected by the exhaustive execution of test cases because it avoids only equivalent test executions that do not contribute to detecting faults.

Overhead of our method. To avoid equivalent test executions, our method builds the checksum matrix in Step 2 and determines the equivalence of test executions in Step 4. However, as shown in Section 4.2 and Section 4.4, because these activities do not include any in-depth analysis of source code and test cases, the overhead incurred in avoiding test execution equivalence is small. To measure the overhead incurred in our method, we obtained the BerkeleyDB SPL from the SPL2go repository [22] and produced a product family that contains 10 products, which are implemented by, on average, 263 files and 40,078 lines. Then, we measured the time required for avoiding equivalent test executions. As a result, it took 2.64 s on Windows 7 with an Intel Core i7 CPU (3.40 GHz) and 12 GB RAM and this accounts only for 7.7% of the end-to-end time (i.e., Steps 1~4) for SPL testing.

Impacts of N-to-1 relationships between features and source code. Our method requires additional work in the case that multiple features are implemented in a single class. For example, when features A and B are implemented in a different part of class C, executions of the two test cases t1 and t2 for features A and B, respectively, produce the same checksum value because they commonly traverse class C. In this case, our method selects only one test case for testing of two features because the execution trace of t1 is the same as that of t2. To avoid this problem, class C should be separated into two different classes that implement features A and B, respectively. This practice is reasonable because it makes loose coupling between features.

5. Related Work

This section discusses related work regarding testing of a single SPL version (in Section 5.1), regression testing of its subsequent versions (in Section 5.2) and reduction of test redundancy at the level of test executions (in Section 5.3).

5.1. Studies on Testing of a Single SPL Version

In the product line testing community, two different interests have gained main attention: selection of products to test and actual testing of products [23].

The first one is the problem of selecting a representative set of products to test in order to verify a product line. To address this problem, combinatorial interaction testing techniques select a minimal set of products in which at least one product covers t-wise interaction, based on feature model [2,3,4,5,6,24,25,26,27], source code [25,26], dependency graph [27], etc. Their common insight is that most faults are caused by interactions among a fixed number of at most t features. Even though they do not verify all the products that can be produced from a product line, they are promising in maximizing the fault detection capability under limited resources. As another solution, search-based techniques randomly select an initial set of products and then gradually optimize the product set under a certain set of constraints [28]. To find the optimized set of products, they use an evolutionary algorithm that optimizes coverage [29,30,31], number of products [30,31], similarity [30,32], mutation score [30,33], complexity [29], etc. The other approaches include the greedy approach and the manual approach [28]. The techniques discussed above reduce test redundancy at the level of products. However, they still have test redundancy because they do not avoid the duplicate testing of common parts between products. To avoid this redundancy, these techniques should be used together with a technique like our method that reduces unnecessary test repetition by exploiting the commonality and variability of a product family.

The second one is the problem of how to check the correctness of the products that are produced from a product line. There have been extensive techniques to address this problem. Incremental delta-oriented techniques [7,8,10,34] incrementally construct test artifacts for every product by exploiting the commonality and variability between two consecutive products. Stepping from one product to the next product, they reuse test artifacts of the previous products for the next product. Search-based techniques [35,36,37,38] address a multi-objective optimization problem for testing a product line using a meta-heuristic algorithm. These techniques generate a test suite optimized with multi-objective functions under time constraints. Similarity-based techniques [32,38,39] increase feature interaction coverage by maximizing the diversity of products to test or test cases to run. They generate dissimilar test cases [38] or prioritize products [32,39] in the order in which the next product is dissimilar with the previous products. Other techniques include the coverage-based technique [40], the fault-history based technique [41], the risk-based technique [42], etc. These techniques discussed above reduce test redundancy at the level of test cases. However, they can have test redundancy at the level of test executions. When a product line test case is executed on the products that reuse it, its executions can be equivalent on these products. Such test executions should be avoided because they do not contribute to finding new faults.

The existing SPL testing techniques reduce test redundancy at the level of products and test cases, but not at the level of test executions. Our technique proposed in this paper reduces test redundancy at the level of test executions by avoiding equivalent executions of a given set of test cases. For this reason, it can be used with the existing techniques discussed above in a complementary way and can further save cost in addition to the cost saved by using them.

5.2. Studies on SPL Regression Testing

Techniques on SPL regression testing have been proposed for three research topics: selection, test prioritization and minimization of test cases.

Lity et al. [7] proposed a model-based test case selection technique for delta-oriented SPLs. They applied incremental model slicing to capture changes between the products of a product family and between different versions of the family. When changes are made to a product family, regression test suites are selected by applying retest coverage criteria to model slices, which consist of states and transitions affected by the change. We previously proposed a code-based SPL regression test selection technique [43]. To reduce the overall testing efforts, this technique handles changes to the common parts of source code and changes to the variable parts of source code, separately. For the changes to the common parts of code, it minimizes unnecessary collections of test execution traces and unnecessary executions of test cases based on the commonality between the products of a product family. For the changes to the variable parts of code, it identifies the test cases that can never be affected by the changes and filters them out without any in-depth analysis of source code and test cases.

Al-Hajjaji et al. [39] and Henard et al. [32] proposed techniques which prioritize products of a product line based on similarity of their selected features. Their common insight is that two dissimilar products are likely to contain different sets of faults in a product line and so a diverse set of products should be tested first for early fault detection. For this reason, the products that have little similarity with the previously tested products have high priorities. Lachmann et al. [9] proposed an approach that computes regression deltas, and then ranks test cases in accordance with their capability to cover changes. Ensan et al. [44] proposed an approach which first assigns priorities to features and their relevant test cases according to the degree of the stakeholder’s goal satisfaction. Wang et al. [45] and Arrieta et al. [46] proposed a test prioritization approach that uses search-based algorithms to address a multi-objective optimization problem for SPL test prioritization.

To minimize the size of test suites and the test execution cost, Baller et al. [47] uses a multi-objective technique and Wang et al. [48] uses a random-weighted generic algorithm.

When a set of test cases that are selected, prioritized and/or minimized using the techniques discussed above is executed on the products of a product family, their redundant executions can be reduced if these techniques are used in conjunction with our method. In addition, when time constraints exist due to a resource limit, our method allows regression test cases to be executed more under the time constraints, which makes a product line more reliable. For this reason, regression testing techniques can also be used with our method in a complementary way.

5.3. Studies on Reducing Test Redundancy at the Level of Test Executions

The existing techniques presented in Section 5.1 and Section 5.2 reduce test redundancy only at the level of products or test cases. Thus, they still have test redundancy at the level of test executions. To address this problem, Kim et al. [13], Nguyen et al. [14] and Wong et al. [15] suggested variability-aware execution methods for testing of a configurable system. All of these methods execute common code only once, not executing it on each and every configuration. These methods share the same research direction with our method in that they reduce redundant test executions without decreasing the chance of detecting new faults. However, the methods do not address the execution of existing test cases and therefore cannot be applied to regression testing of a product line.

For testing of a product line system that our method targets, Stricker et al. [12] proposed a data flow-based technique called ScenTED-DF. ScenTED-DF avoids redundant testing of common parts of a product line using an annotated variable activity diagram. However, ScenTED-DF requires the intervention of human experts when modeling the annotated variable activity diagram [12]. In contrast, our technique is an automated one and requires only source code and test cases of a product line.

Li et al. [49] proposed a method of reusing test execution traces for an SPL by recording the name, version, inputs and outputs of modules that the executed test case traverses over a product. If another test case traverses a module with the same name, the same version and the same inputs, then the recorded output is used without re-executing the test case. However, this method does not consider that even when two modules of two different products have the same name, the same version or the same inputs, the two modules can still produce different outputs when implementations of the modules are not equivalent. For this reason, some part of source code may not be tested and so, due to the decreased test coverage, faults that would be detected by the exhaustive test execution can be missed. In addition, it conducts only a small case study.

In summary, the methods discussed above reduce redundancy at the level of test execution. However, they either have limitations in fault detection and automation or have different application scopes.

6. Conclusions

In this paper, we showed that our method proposed in our previous work can be applied not just to SPL regression testing but to SPL testing in general. To that end, we first argued that our method is applicable for testing of both the first version of a software product line and its subsequent versions. Then, we proposed a practical process for applying the method to SPL testing and an algorithm that improves our previous algorithm in order to reduce unnecessary repetition of test execution and unnecessary collection of test execution traces. The case study result that we conducted based on the proposed process showed that our method reduced test executions by 42.3% (22/52) compared to those of the exhaustive execution approach.

Our method is easy to apply for most product lines because it requires only source code and does not require other artifacts such as requirements and architecture that are often hard to obtain and reducing repetitions of equivalent test executions through check-sum comparison is fully automated. For this reason, with the use of our method for SPL testing can be conducted more efficiently.

For future work, we plan to extend our method to make it applicable at a finer granularity level. Moreover, we considered in this paper test redundancy only at the test execution level, but we plan to extend our method by applying product sampling techniques that reduce test redundancy at the product level. Finally, we plan to demonstrate the scalability of our method by applying it to larger size software product lines from the industry.