Keywords

1 Introduction

A covering array (CA) is a mathematical object defined by four positive integers and denoted as CA(N; t, k, v). It is a \(N \times k\) matrix where N is the number of rows, k the number of columns (often referred to as parameters), t the size of interactions that are covered and v is the size of the alphabet. A covering array is defined by its t-covering property: for any t-selection of columns, all \(v^t\) t-tuples between the selected columns occur at least once in the array. t is called the strength of the CA. A mixed-level covering array (MCA) is a generalization of a CA where each column i has its own alphabet size \(v_i\). An MCA is denoted as \(MCA(N; t, k, (v_1,\dots ,v_k))\). The tuple \((t, k, (v_1,\dots ,v_k))\) (\(t \le k\)) is referred to as the configuration of an MCA.

The general problem of constructing optimal covering arrays (i.e., in terms of minimal size N) is believed to be a hard combinatorial optimization problem and it has significant applications in software and hardware testing [8, 9]. Moreover, it is tightly coupled with NP-hard problems [2]. As a result, there has been a lot of effort on developing and improving algorithmic approaches for covering array generation (c.f. Sect. 2).

The In-Parameter-Order (IPO) family of algorithms is a set of greedy algorithms for constructing covering arrays and their representatives have been shown to produce acceptable sized covering arrays [3]. There have been multiple efforts in the area of improving the IPO variants, in terms of reducing the size of generated covering arrays, but to the best of our knowledge, no systematic evaluation of these proposals exist. In this work, we aim to provide an overview of these optimization efforts and evaluate their effectiveness.

This paper is structured as follows: In Sect. 2 we discuss preliminaries and related work. Section 3 presents the IPO family of algorithms and existing and novel methods to parameterize it. Section 4 proposes an evaluation of the algorithms and discusses the results and finally, Sect. 5 concludes the paper.

2 Background

The In-Parameter-Order (IPO) strategy was first proposed in [15] as a greedy algorithm for covering array construction. It constructs a covering array one column at a time and each extension is divided into a horizontal and an optional vertical extension. We discuss the algorithm in greater detail in Sect. 3.

While the original algorithm was limited to arrays of strength 2 (pair-wise), subsequent works have generalized the algorithm to allow the generation of higher strength arrays [13] (IPOG) as well as integrated constraint handling in [17, 18]. In [5], the authors propose variants of the IPO strategy, namely IPOG-F, IPOG-F2, by extending the search space in the horizontal extension. In [14], the IPOG-D variant is presented which includes a recursive construction method aimed at reducing the number of combinations to be enumerated.

Many works have been dedicated to improving parts of the IPO algorithms in order to minimize covering arrays sizes. In [4] a graph-coloring scheme integrated into the vertical extension is proposed to reduce the resulting array sizes. [16] modify IPOG with additional optimizations aimed at reducing don’t-care values in order to minimize the number of rows. [6, 7] discuss and evaluate the impact of tie-breaking on the generated arrays and propose a new tie-breaker which reduces the generated array sizes.

Related to the aim of this paper is the works of [1] for “one-test-at-a-time” greedy construction algorithms. There, the authors propose a general framework of such algorithms and provide concrete ways to instantiate it. In their analysis they evaluate the most important parameters which contribute to smaller covering array sizes.

3 The IPO Family of Algorithms

The IPO family of algorithms is a set of algorithms for constructing covering arrays and has seen use in many applications in practice [12]. The most important representatives are IPOG [13], IPOG-F [5] and IPOG-F2 [5]. They are greedy algorithms able to generate (mixed-level) covering arrays for any configuration. They all follow the same basic schema (c.f. Algorithm 1) and start out by building an initial covering array of strength t by constructing the cross-product of the first t columns.

figure a

Then, the array is extended one column at a time in a two-dimensional fashion. First, a new column is added to the array by a horizontal extension. This step will assign values to the new column in a greedy manner with the objective to maximize coverage gain. Algorithm 2 shows the procedure for IPOG. Here, rows are considered from top to bottom and in each one the value with the maximum coverage gain (in terms of previously uncovered t-tuples) is selected. If multiple values provide maximum gain then the tie must be broken with a predefined strategy. This will be discussed in further detail in Sect. 3.1.

IPOG-F and IPOG-F2 extend the search space in the horizontal extension by also optimizing the order in which rows are extended. For this purpose, unassigned rows are additionally scanned in each iteration to find the best position and value to assign. While IPOG-F considers the actual coverage to decide on the best value, IPOG-F2 tries to estimate the amount of covered tuples. This is an optimization which allows for a faster implementation compared to IPOG-F, but it sacrifices accuracy. The estimation is achieved by keeping an estimated value of covered tuples in an array for each row and value. When a value a is chosen in row r, the estimator is incremented by the number of shared tuples between row s and all other unassigned rows s.

figure b

The horizontal extension either finishes when all tuples have been covered or each entry in the new column has been assigned a value. In the latter case, there are still tuples left which have not yet been covered and they are added in the vertical extension step. This step grows the array by adding more rows which include missing tuples.

In the vertical extension all remaining uncovered tuples are added to the array to ensure that the first i columns form a covering array. Tuples can either be added by appending a new row to the array that contains the tuple or by finding an already existing row which can fit the tuple. The latter case is possible since don’t-care values can occur in the array and may be overwritten by a tuple without destroying the t-covering property.

3.1 Tie-Breakers

During the horizontal extension, tie-breaking may be necessary in the case that two or more values for a row in the new column provide the same, maximum coverage gain, i.e. cover the most new t-tuples. We will refer to these values as candidates. In the following we will give an overview to possible tie-breaking strategies.

Random Tie-Breaker. The simplest approach is to choose one value out of all candidates at random. This can be implemented efficiently but it will introduce non-determinism to algorithm and the generated covering arrays will possibly differ on subsequent runs of the algorithm. This tie-breaker is oblivious to the previous history of the extension.

Deterministically-Seeded Random Tie-Breaker. This is a variant of the Random tie-breaker. Here, ties are still broken randomly with the help of a pseudorandom generator, but the generator is seeded with a constant at the beginning which results in a deterministic behaviour of the algorithm.

Lexicographic Tie-Breaker. This tie-breaker will always prefer the (lexicographically) smallest candidate if multiple are available. This can of course introduce a bias towards smaller values in the new column.

Cyclic Tie-Breaker. This tie-breaker builds upon the Lexicographic tie-breaker, but maintains the last chosen value and starts the search from this one instead of the first. The aim is to remove bias towards smaller values, however the last chosen value is more likely to be picked again in the next iteration.

Cyclic-Next Tie-Breaker. This tie-breaker works exactly as the Cyclic tie-breaker, but will start from the next value following the last chosen value. This tie-breaker was first proposed in [6, 7].

Value-Balanced Tie-Breaker. This tie-breaker keeps track of how many times a value has been used so far in the extended column. In an optimal situation, each value for the new column occurs exactly the same amount of times and the aim of this tie-breaker is to mimic this behaviour by balancing the occurrences of these values. Values are preferred when they so far have occured less frequently than other candidate values.

\(\alpha \)-balanced Tie-Breaker. This tie-breaker builds upon the value-balanced tie-breaker by not only considering the balance of values in the new column, but the balance of lower-strength tuples involving the new parameter. This is based on the notion of \(\alpha \)-balance which was introduced by [10] and functions as a tie-breaker in the following way: first, the number of would-be-covered \(t-1\) tuples are compared for each candidate. If there still is a tie, the next lower strength is tried and so on. If at \(t=1\) there still exists a tie, then the smallest value will be preferred.

3.2 Tuple Enumeration Order

In the vertical extension, uncovered tuples are added one-by-one to the array. So far it has not been studied, if different enumeration orders of these tuples have any impact on the resulting arrays. We propose besides the common lexicographically-ascending (tuples of small lexicographical order first) order, the reverse, i.e. from lexicographically largest to smallest. Furthermore, switching between the orderings every other vertical extension could prove beneficial to achieve smaller arrays.

3.3 Parameter Ordering

One simple option to influence the covering array generation is the order in which columns are extended. Since the covering property is not affected by column permutations one can permute the configuration before starting the generation and apply the reverse permutation afterwards. Note that this is only useful for mixed-level covering arrays. Informal consensus is that the IPO strategy generates smaller arrays when columns are sorted by decreasing alphabet size, but, to the best of our knowledge, this has so far not been subject to an experimental evaluation.

While the number of column permutations in general is too large in practice, we propose to investigate the following:

  • Ascending Sort columns with increasing alphabet size from smallest to largest

  • Descending Sort columns with decreasing alphabet size from largest to smallest

  • Alternating Intersperse large and small columns and switch between large and small columns from one extension to the next. We propose two variants. The first starts with the smallest, followed by the largest and thirdly the second-smallest, etc. The second starts with the largest, followed by the smallest and so on.

4 Evaluation

4.1 Setup

To evaluate the different algorithm configurations we chose a set of (M)CA instances based upon the benchmarks used in [1] to study the behaviour of greedy, one-test-at-a-time MCA generation algorithms. The instances are summarized in Fig. 1a.

Fig. 1.
figure 1

Benchmark setup

Full size image

We implemented all IPO variants in our own implementation described further in [11]. The particular algorithm as well as the tie-breaker, tuple order and parameter ordering are selectable via a configuration option at runtime. This results in 63 distinct algorithm configurations for CA generation and 252 distinct configurations for MCA generation. The configuration options are summarized in Fig. 1b.

Each algorithm configuration was used to generate (M)CAs for the selected benchmark instances for strengths between 2 and 4. The experiments were conducted on the Graham cluster of the Shared Hierarchical Academic Research Computing Network (SHARCNET). Configurations involving the Random tie-breaker were repeated 10 times. Due to space limitations, we only discuss selected and aggregated results, but we provide the full data set as well as visualizations on a dedicated websiteFootnote 1 for the interested reader. There we also provide further measurements into the test generation time differences observed between the tested configurations.

4.2 Results

In order to meaningfully compare different configurations options across instances we first normalized the computed covering array sizes to a relative measure representing the deviation of the mean. We computed the mean for each instance and based on the result computed the relative improvement or degradation for each individual run. This value shows how much better or worse one configuration performs in comparison to the other ones. The results are summarized in Table 1 and are visualized in Figs. 2a and b.

Table 1. Relative improvement for different configurations compared to the mean
Full size table

In general, IPOG-F produces the smallest arrays, followed by IPOG and IPOG-F2. Comparing the results for the different tie-breakers, no one choice seems to impact array sizes significantly, however, the Cyclic-next tie-breaker overall yields the best results. It, together with the Cyclic tie-breaker is able to generate some arrays with up to 50% less rows. However, the Cyclic tie-breaker exhibits extreme results in the other direction and in corner-cases with array sizes exceeding 50% larger than the mean are produced. This is also the case for the Alpha-balanced and Lexicographic tie-breaker.

Judging from the results in Table 1, the order in which tuples are enumerated does not seem to affect the resulting covering array size in any significant way.

The largest impact can be attributed to the sorting order of columns. Sorting in descending order of alphabet size leads to significantly smaller covering arrays, especially in the case of IPOG-F. Alternating between large and small columns has some impact and is better than sorting columns in ascending order.

Fig. 2.
figure 2

Relative improvement compared to the mean

Full size image

Selected benchmark results. Aside from the general performance, for specific instances the various configuration options can have differing impact. In the following, we discuss some results for selected instances. In order to meaningfully analyze the results we have grouped the results by both the algorithm (i.e., IPOG, IPOG-F or IPOG-F2) and one of either tie-breaker, tuple-order or parameter-order. Inside each group we have computed the mean and the standard deviation. The results show absolute values instead of relative difference.

Fig. 3.
figure 3

Results for different tie-breakers

Full size image
Table 2. Results for CA experiments
Full size table

\(\mathbf {3^{40}}\) \({\varvec{(t = 3)}}\) The results of this experiment are summarized in Table 2 and the generated covering array sizes per tie-breaker are visualized in Fig. 3a. IPOG-F produces the smallest arrays and shows very low variance when comparing different tie-breakers. In contrast, the results for IPOG are much more dependent on the tie-breaker. Here, the best results are obtained with the Value-balanced tie-breaker which produces arrays 16% smaller than when using the Alpha-balanced tie-breaker. IPOG-F2 shows no significantly differing behavior with different tie-breakers. Furthermore, the order in which tuples are enumerated have no major impact.

\({\mathbf {10^4}}\) \({\varvec{(t = 3)}}\) The results for this experiment can be found in Table 2 and a comparison of the tie breakers can be found in Fig. 3b. Here, the configurations which use either the Cyclic or Resuming tie-breakers manage to generate an orthogonal array (since the size is equal to \(v^t\)) for the three algorithms. Interestingly, the Lexicographic tie-breaker, although similar to the other two, performs the worst in all cases with almost 30% larger array sizes. As before, in this case the tuple order has no real impact.

4.3 \(6^65^53^4\) (\(t=3\))

For this instance (see Table 3), there is no large variance when comparing different tie-breakers. IPOG-F produces the smallest arrays, while IPOG-F2 produces the largest. Here, the parameter order has a measurable impact and ordering the parameters by descending size can improve array sizes by up to 5% in this case. These results are visualized in Fig. 4a.

\(\varvec{5^{10}2^{10} (t=3)}\) The results for this instance are described in Table 3 and a comparison of different tuple orders is visualized in Fig. 4b. The tuple order seems to only make a difference for IPOG-F2, where both the Alternating and Descending order outperform the Ascending order. This is also the case in instance \(6^65^53^4\) (\(t=3\)).

Fig. 4.
figure 4

Results for different parameter orders (left) and tuple orders (right)

Full size image
Table 3. Results for MCA experiments
Full size table

5 Conclusion

In this paper we have studied the impact of tie-breaking, parameter ordering and tuple enumeration order in the IPO family of algorithms. We have compared their effectiveness in terms of their ability to reduce covering array sizes in a large evaluation. In summary, IPOG-F overall manages to produce the smallest arrays compared to IPOG and IPOG-F2. Furthermore, the choice of tie-breaker seems to not matter a great deal when averaging over all instances, but the right choice can have large impact on selected instances. In the case of MCA generation, we measured the largest reduction in array size when ordering columns by decreasing alphabet size, with up to 12% reduction in size compared to the mean.