Resource Page for "An Algorithm for Generating t-wise Covering Arrays from Large Feature Models"

ICPL has been superseded and greatly improved by the algorithm Pairwiser.

Welcome to the resource page for the SPLC 2012 publication titled "An Algorithm for Generating t-wise Covering Arrays from Large Feature Models" written by Martin Fagereng Johansen, Øystein Haugen and Franck Fleurey.


Contents


Tool - implementation of ICPL

The SPL Covering Array Tool v0.3 (SPLC 2012) contains an implementation of the ICPL algorithm for 1-3 wise covering array generation. The source code is available licensed under the Eclipse Public License - v 1.0.

Since CASA, NIST ACTS and MoSo-PoLiTe are only available through their providers, they are not distributed with this download. If you want to test the full version of the tool that includes CASA, NIST ACTS and MoSo-PoLiTe, contact the respective sources to obtain the tools, then contact us to get a version of the tool with the proper adaptors.

When running the tool, ICPL is called 'ICPL', and the algorithm discussed as 'Algorithm 1' in the paper is called 'Chvatal'. ICPL is of course set as the default algorithm. If you want to generate a covering array using ICPL run:

java -jar SPLCATool-v0.3-SPLC2012.jar -t t_wise -a ICPL -s <strength> -fm <feature model>

The tool includes the following software as dependencies, bundled with the tool:

Usage:

java -jar SPLCATool-v0.3-SPLC2012.jar

SPL Covering Array Tool v0.3 (SPLC 2012) (ICPL edition)
http://heim.ifi.uio.no/martifag/splc2012/
Args: {limit=100%, t=help, a=ICPL}
Usage: <task>
Tasks:
 -t count_solutions -fm <feature_model>
 -t sat_time -fm <feature_model>
 -t t_wise -a Chvatal -fm <feature_model> -s <strength, 1-4> (-startFrom <covering array>) (-limit <coverage limit>) (-sizelimit <rows>) (-onlyOnes) (-noAllZeros)
 -t t_wise -a ICPL -fm <feature_model> -s <strength, 1-3> (-startFrom <covering array>) (-onlyOnes) (-noAllZeros) [Inexact: (-sizelimit <rows>) (-limit <coverage limit>)]
 -t t_wise -a CASA -fm <feature_model> -s <strength, 1-6>
 -t calc_cov -fm <feature_model> -s <strength> -ca <covering array>
 -t verify_solutions -fm <feature_model> -check <covering array>
 -t help (this menu)
Supported Feature models formats:
 - Feature IDE GUI DSL (.m)
 - Simple XML Feature Models (.xml)
 - Dimacs (.dimacs)
 - CNF (.cnf)

Examples

> java -jar SPLCATool-v0.3-SPLC2012.jar -t t_wise -a ICPL -s 2 -fm Eshop-fm.xml
SPL Covering Array Tool v0.3 (SPLC 2012) (ICPL edition)
http://heim.ifi.uio.no/martifag/splc2012/
Args: {limit=100%, fm=Eshop-fm.xml, t=t_wise, s=2, a=ICPL}
Loading SXFM: Eshop-fm.xml
Successfully loaded and converted the model:
Features: 287
Constraints: 22
Generating 2-wise covering array with algorithm: ICPL
Running algorithm: ICPL
Covering 100%
--- 1-wise ---
...
1-wise done, solutions: 3, invalid: 28
--- 2-wise ---
...
Uncovered: 0, progress: 100% with solutions: 21
2-wise done, solutions: 21, invalid: 15638
Done. Size: 21, time: 3765 milliseconds
Wrote result to Eshop-fm.xml.ca2.csv
 


Feature Model Corpus

These are the feature models discussed in the paper:

[1]: http://code.google.com/p/linux-variability-analysis-tools/source/browse/?repo=formulas
[2]: http://sourceforge.net/projects/violet/
[3]: http://www.oracle.com/us/products/database/berkeley-db/index.html
[4]: http://www.sei.cmu.edu/productlines/ppl/
[5]: http://www.tightvnc.com/
[6]: http://fame-dbms.org/


Measurements, Scripts and Adaptors

Adaptors

In order to run the test scripts for the three algorithms CASA, NIST ACTS and MoSo-PoLiTe, contact the respective providers to get the implementations. Then, contact us to get the tool that includes adaptors for the tools to run the test scripts for them.

Measurements

These files contain all the measurements done for each strength, algorithm and feature model. The measurements are stored as Office Open XML-files. The measurements for each strength are found in separate tabs.

Scripts

These scripts allow the reproduction of the measurements for each strength, algorithm and model.