An algorithm for generating t-wise covering arrays from large feature models

A scalable approach for software product line testing is required due to the size and complexity of industrial product
lines. In this paper, we present a specialized algorithm
(called ICPL) for generating covering arrays from feature
models. ICPL makes it possible to apply combinatorial interaction testing to software product lines of the size and
complexity found in industry. For example, ICPL allows
pair-wise testing to be readily applied to projects of about
7,000 features and 200,000 constraints, the Linux Kernel,
one of the largest product lines where the feature model
is available. ICPL is compared to three of the leading algorithms for t-wise covering array generation. Based on a
corpus of 19 feature models, data was collected for each algorithm and feature model when the algorithm could finish 100 runs within three days. These data are used for comparing
the four algorithms. In addition to supporting large feature
models, ICPL is quick, produces small covering arrays and,
even though it is non-deterministic, produces a covering array of a similar size within approximately the same time
each time it is run with the same feature model.