Question

Consider a system that consists of 4 parameters, P1, P2, P3, and P4. Each parameter has two values 0 and 1. Apply algorithm IPO to create a pairwise test set for this system. Use “-” to represent don’t care values, i.e., values that do not affect coverage. Clearly indicate your tie-breaking rules that may be needed in the test generation process. You must show intermediate steps to obtain full credits.

Answer 1

Solution(s):

An IPO strategy is deterministic, it means that IPO strategy will always produces the same test set    for the same system configuration.The IPOG strategy frame work can be decribed as:

For a system with t or more parameters, the IPOG strategy builds a t-way test set for the first t parameters, extends the test set to build a t-way test set for the first t + 1 parameters, and then continues to extend the test set until it builds a t-way test set for all the parameters. (The parameters can be in an arbitrary order.) The extension of an existing t-way test set for an additional parameter is one in two steps:

1. Horizontal growth
2. Vertical growth

1.Horizontal growth: It is the growth in which each existing test extends by adding one value for the new parameter.

2.Vertical growth :  In vertical growth it adds new tests, if it is required, so it add new test to the test set produced by horizontal growth.

IPOG-Test :   IPOG-Test is a test generation algorithm that implements this framework. The algorithm takes as input an integer t and a set ps of parameters, and produces as output a t-way test set for the parameters in set ps. It is assumed that the number n of parameters in set ps is greater than or equal to t example system consists of four parameters P1, P2, P3, and P4, where P1, P2, P3 have two values 0 and 1, and P4 has three values 0, 1, and 2. In the following, we will use this application as a running example to explain how algorithm IPOG-Test works.

Algorithm IPOG-Test begins by initializing test set ts to be empty (line 1), and by putting the input parameters into an arbitrary order (line 2). Note that test set ts will be used to hold the resulting test set. Next, the algorithm builds a t-way test set for the first t parameters. This is trivially done by adding into test set ts a test for every combination of the first t parameters (line 3). In Fig. 3, the 3-way test set built for the first three parameters is shown which contains all the 8 possible combinations of the first three parameters, i.e., P1, P2, and P3.If the number n of parameters is greater than the strength t of coverage, the remaining parameters are covered, one at each iteration, by the outermost for-loop (line 4). Let Pi be the parameter that the current iteration is trying to cover. We first compute the set π of combinations that must be covered in order to cover parameter Pi(line 5). Covering parameter Pi means extending test set ts so that it becomes a t-way test set for parameters P1, ..., Pi-1, and Pi. Note that test set ts is already a t-way test set for parameters P1, ..., Pi-1. Thus,   we   only need to cover all the t-way combinations involving Pi and any group of t 1 parameters among P1, ..., Pi-1, which are the parameters that are already covered.so, in order to cover P4, we need to cover all the 3-way combinations of the following parameter groups, (P1, P2, P4), (P1, P3, P4), and(P2, P3, P4).    We will not list each of the combination in those parameter groups, as they can easily be enumerated.   Instead, we only point out that each of these groups has 12combinations. Thus, there are in total 36 combinations in the setπ.The combinations in setπ are covered in the following two steps:

•Horizontal growth: This step extends each of the existing tests by adding a value for parameter Pi (lines7- 10). These values are chosen in a greedymanner, i.e., at each step, the value chosen is one that covers the largest number of combinations in setπ (line 8). Each time a value is added, the set of combinations covered due to this addition are removed from set π(line 9).The 4th test is extended by adding the value 0 for P4, which covers three combinations in set π:{(P1.0,   P2.1,   P4.0),   (P1.0,   P3.1,   P4.0),   (P2.1),  

Algorithm: IPOG-Test(int t, ParameterSet ps)

{

1. initialize test set ts to be an empty set

2. denote the parameters in ps, in an arbitrary order, as P1, P2, ..., and Pn

3. add into test set ts a test for each combination of values of the first t parameters

4. for(int i = t + 1; i ≤n; i ++){

5. let πbe the set of t-way combinations of values involving parameter

Pi and t -1 parameters among the first i – 1 parameters

6. // horizontal extension for parameter Pi

7.     for(each test τ = (v1, v2, ..., vi-1) in test set ts) {

8.   choose a value vi of Pi and replace τ with τ’ = (v1, v2, ..., vi-1, vi) so that τ’ covers the most number of combinations of values in π

9. remove from π the combinations of values covered by τ’

10.   }

11.   // vertical extension for parameter Pi

12.   for(each combination σin set π){

13.      if (there exists a test that already covers σ) {

14.   remove σ from π

15.      } else{

16.   change an existing test, if possible, or otherwise add a new test to cover σ and remove it from π

17.      }

18.   }

19.}

20.return ts;

}

As per the problem, the system consists of four parameters P1, P2, P3, and P4, where P1, P2, P3 have two values 0 and 1, and P4 has three values 0, 1, and 2. In the following, we will use this application as a running example to explain how algorithm IPOG-Test works.

      Algorithm IPOG-Test begins by initializing test set ts to be empty (line 1), and by putting the input parameters into an arbitrary order (line 2). Note that test set ts will be used to hold the resulting test set. Next, the algorithm builds a t-way test set for the first t parameters. This is trivially done by adding into test set ts a test for every combination of the first t parameters (line 3). The 3-way test set built for the first three parameters is shown in part (a), which contains all the 8 possible combinations of the first three parameters, i.e., P1, P2, and P3. If the number n of parameters is greater than the strength t of coverage, the remaining parameters are covered, one at each iteration, by the outermost for-loop (line 4).

Let Pi be the parameter that the current iteration is trying to cover. We first compute the set Π of combinations that must be covered in order to cover parameter Pi(line 5). Covering parameter Pi means extending test set ts so that it becomes a t-way test set for parameters P1, ..., Pi-1, and Pi.Note that test set ts is already a t-way test set for parameters P1, …………,Pi-1. Thus,   we   only   need   to   cover   all   the t-way combinations involving Pi and any group of t -1 parameters among P1, ..., Pi-1, which are the parameters that are already covered. For example, in Fig. 3, in order to cover P4, we need to cover all the 3-way combinations of the following parameter groups, (P1, P2, P4), (P1, P3, P4), and (P2, P3, P4).    We will not list each of the combination in those parameter groups, as they can easily be enumerated.    Instead, we only point out that each of these groups has 12 combinations.