IPO-s: incremental generation of combinatorial interaction test data based on symmetries of covering arrays

Verification and validation of highly-configurable software systems, such as those supporting many optional or customizable features, is a challenging activity. In fact, due to its intrinsic complexity, formal modeling of the whole system may require a great effort. Modeling activities may become extremely expensive and time consuming, and the tester may decide to model (at least initially) only the inputs and require they are sufficiently covered by tests. The recent wide spreading usage of combinatorial interaction testing (CIT) is dramatically improving the effectiveness of this activity. Although there exist analytical ways to derive minimal sized CIT test suites, they are not applicable to all task sizes. Therefore, researchers have explored many techniques based on greedy or heuristic algorithms that may lead to sub-optimal result in the size of the built test suite but that are applicable to problems of real size. In this paper, a new parameter-based heuristic algorithm for the construction of pairwise covering test suites is presented; it is based on a symmetry property of covering arrays and it is called IPOS. Time and space complexity of IPOS is discussed in comparison especially with the only other parameter-based approach existing in literature. The proposed approach is supported by a prototype implementation, and experimental assessment is also presented