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 many 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 man, techniques based on greedy or heuristic algorithms that may lead to suboptimal 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.