Implementation of Generation Algorithm

How to Implement a Constrained Covering Array Generation Algorithm

In order to implement a new constrained covering array generation algorithm in CCAG, you only need to:

1. create a class that extends CAGenerator
2. specify feasible constraint handlers in the supportedHandlers variable (for example, the Tolerate handler can only be used when there is a fitness function, while the others are usually general enough to be used in any generation algorithm)
3. implement the process() method to construct a covering array (use isValid() and penaltyTerm() to deal with constraints)

As such, when the generation() method of CAGenerator is invoked, the following procedure will be automatically executed to find a covering array: (1) initialise the constraint handler by its PreProcess() method; (2) invoke the implemented process() method; and (3) update the generated test suite by the PostProcess() method of the constraint handler.

For example, the following code implements a BaiscRandom algorithm, in which a valid test case is generated at random at each time, until all t-way combinations are covered.

import combinatorial.CTModel;
import combinatorial.TestSuite;
import handler.ConstraintHandler;
import static handler.ConstraintHandler.Handlers.*;
import java.util.Random;

public class BasicRandom extends CAGenerator {

  private Random random;

  public BasicRandom() {
    // explicitly specify feasible constraint handlers
    supportedHandlers = new ConstraintHandler.Handlers[]{Verify, Solver, Replace};
    random = new Random();
  }

  /**
   * The particular generation algorithm. Use handler.isValid() and handler.penaltyTerm()
   * methods to deal with constraints encountered during the generation process.
   * @param model a combinatorial test model
   * @param handler the constraint handler
   * @param ts the generated test suite
   */
  @Override
  public void process(CTModel model, ConstraintHandler handler, TestSuite ts) {
    // remove invalid combinations from the set of to-be-covered combinations
    model.removeInvalidCombinations(handler);

    while (model.UNCOVERED() != 0) {
      // sample a test case at random
      int[] test = sample(model);
      while (!handler.isValid(test))
        test = sample(model);
      // add into the test suite
      ts.suite.add(test);
      // mark the combinations in test as covered
      model.coverUpdate(test);
    }
  }

  private int[] sample(CTModel model) {
    int[] tc = new int[model.parameter];
    for (int i = 0; i < model.parameter; i++)
      tc[i] = random.nextInt(model.value[i]);
    return tc;
  }
  
  public static void main(String[] args) {
    // a demo of use
    // for a test model that has 5 parameters, each of which has 2 values; no constraint
    CTModel model = new CTModel(5, new int[]{2, 2, 2, 2, 2}, 2, null);
    TestSuite ts = new TestSuite();
    CAGenerator br = new BasicRandom();
    // use the Verify constraint handler for generation
    br.generation(model, Verify, ts);
    // display the generated covering array
    System.out.println(ts);
    System.out.println(br.size);
  }

Next, we explain the APIs provided by the CTModel and ConstraintHandler objects, which provide powerful building blocks for implementing constrained covering array generation algorithms. We have also implemented six popular generation algorithms (AETG, DDA, IPO, PSO, SA, and TS) for demonstration and reference.

CTModel

1. Parameters, Values, and Constraints

The CTModel defines the parameters and their values, as well as constraints of the Software Under Test (SUT). It is straightforward to access them:

int parameter = model.parameter;
int[] value = model.value;
List<int[]> constraint = model.constraint;

Note that each constraint is represented using the disjunction form of boolean variables, indicating a forbidden tuple in the SUT. For example, for a SUT with four parameters (P0, P1, P2 and P3) and three values for each parameter (V0, V1 and V2), the following gives the boolean variables assigned to each parameter value:

    P0  P1  P2  P3
V0   1   4   7  10
V1   2   5   8  11 
V2   3   6   9  12

As a result, the integer array [-2, -4] indicates the forbidden tuple P0 = 1 AND P1 = 0. This parameter value combination is thus invalid and cannot appear in any test case of the covering array.

2. Cover Matrix

CTModel maintains a cover matrix, which is a two dimensional array cover[][], indicating the state of every t-way combination:

• Uncoverd: cover[i][j] = 0
• Covered: cover[i][j] = a positive value, representing how many times it is covered
• Invalid: cover[i][j] = -1

A mapping relationship is established between t-way combinations and positions in the cover matrix, specifically,

• Each row corresponds a particular combination of t parameters, with a total number of C(parameter, t) rows.
• Each column corresponds a particular value combination of the t parameters.

For example, for parameter = 3, value = [2, 2, 3] and t = 2, rows 0, 1, and 2 indicate parameters [0 1], [0 2], and [1 2], respectively. Both rows 0 and 1 have 2 * 2 = 4 corresponding columns; while row 2 has 2 * 3 = 6 columns, with the order of value combinations as [0, 0], [0, 1], [0, 2], [1, 0], [1, 1], and [1, 2].

3. APIs

CTModel provides the following APIs for manipulating the cover matrix:

1. Methods for initialisation:

   • initialization(): initialise all combiantions that need to be covered. It assigns 0 (uncovered) to all of them.

   • removeInvalidCombinations(ConstraintHandler handler): mark all invalid combiantions in the cover matrix (namely, assign -1 to all of them). This will iterative each and every t-way combination, and might thus be time-consuming.

2. Methods for backup and restore of cover matrix (this could be used to avoid multiple re-initialisations).

   • copyCoverMatrix(int[][] array): copy the cover matrix to the given array.

   • resetCoverMatrix(final int[][] array): use the array to reset cover matrix.

3. Methods for evaluating the state of t-way combinations:

   • UNCOVERED(): get the number of currently uncovered combinations (namely, the number of zeros in the cover matrix).

   • coverNumber(final int[] test): get the number of uncovered combinations that can be covered by the given test case.

   • coverState(int[] position, int[] schema) and coverState(int row, int column): get the state of the given t-way combination, namely, the value of cover matrix cover[row][column].

   • fitnessDelta(final int[] a1, final int[] a2): calculate fitness(A') - fitness(A), where fitness() is defined as the number of yet-to-be covered combinations.

4. Methods for updating the cover matrix:

   • setCoverValue(int row, int column, int value): assign a value to the particular position of cover matrix.

   • setInvalid(final int[] position, final int[] schema): mark a t-way combination as an invalid combination.

   • coverUpdate(final int[] test): mark all t-way combinations in the given test case as covered (for example, a new test case is added into the suite).

   • coverUpdate(int[] position, int[] schema) and coverUpdate(int row, int column): mark the given t-way combinations as covered (basically, cover[row][column]++).

5. Methods for getting uncovered t-way combinations:

   • getAnUncoveredTuple(): get a currently uncovered t-way combination at random.

   • getUncoveredTuple(int[] position): get the set of uncovered and valid tuples corresponding to the given set of parameters.

ConstraintHandler

There are only two methods of ConstraintHandler that should be used to implement the generation algorithm:

• isValid(final int[] test) and isValid(final TestSuite ts): determine whether the given test case, or test suite, is constraint satisfying. Note that the test case can be incomplete with unfixed parameters (assigned to -1), such as [-1, 0, 1, -1, 3], which can be used to represent a particular t-way combination.

• penaltyTerm(final int[] test) and penaltyTerm(final TestSuite ts): calculate the number of constraint violations of the given test case, or test suite. Note that this method should only be used when calculating the fitness value in search based algorithms.