Combinatorial Interaction Testing

Software customization, through the modification of run-time or compile-time preferences, allows users to make controlled variations to how their software behaves. Customizable systems such as web servers (e.g. Apache), databases (e.g. MySQL), application servers (e.g. Tomcat), or office applications (e.g. MS Word) which have dozens or even hundreds of customizable options can have an enormous number of configurations.

While validating the correctness of the system across its entire configuration space is desirable, exhaustive testing of all configurations is generally infeasible; configuration spaces grow exponentially in the number of configuration options.  One solution approach, called combinatorial interaction testing (CIT), systematically samples the configuration space and tests only the selected configurations.

CIT approaches generally work by first defining a model of the system's configuration space -- the set of valid ways it can be configured. Typically, this model includes a set of configuration options, each of which can take on a small number of option settings, and a set of system-wide inter-option constraints (i.e., not all configurations may be valid). Given this model, CIT methods next compute a small set of concrete configurations, a t-way covering array,  in which each valid combination of option settings for every combination of t options appears at least once.  Finally, the system is tested by running its test suite on each configuration in the covering array.

Covering array approaches generally assume that there are no unknown control dependencies among the configuration options, option setting combinations that effectively cancel other options setting combinations.  Known control dependencies are worked around by specifying constraints or by defining a set of default test cases in addition to the covering array.  Given these assumptions, and assuming the existence of a well constructed test suite, the basic justification for covering arrays is that they can cost-effectively exercise all system behaviors caused by the settings of t or fewer options.

We hypothesize however that in practice many such behaviors are not actually tested due to masking effects. We define a masking effect as an effect that prevents a test case from testing all the required option setting combinations present in a configuration, which the test case is normally expected to test. That is, masking effects perturb program execution in ways that prevent other option-related behaviors from being tested. As a result, masking effects cause developers to develop a false confidence in their test processes by making them to believe that they have tested certain option setting combinations, when they in fact have not. One simple example of a masking effect would be an error that crashes a program early in the program's execution. The crash then prevents some configuration dependent behaviors, that would normally occur later in the program's execution, from being exercised. Unless the combinations controlling those behaviors are tested in a different configuration, or unless the error is fixed and the faulty configuration is re-tested, one cannot conclude that those configuration dependent behaviors have been tested.

In this project we develop algorithms, techniques, and tools to reduce the harmful consequences of masking effects.


Gulsen Demiroz, Ph.D.


Emine Dumlu, M.S., Spring 2010 (first position: TUBITAK)


Emine Dumlu, Cemal Yilmaz, Myra B. Cohen, and Adam Porter. Feedback driven adaptive combinatorial testing. In  the Proceedings of the 2011 International Symposium on Software Testing and Analysis (ISSTA '11), pages 243-253, ACM, New York, NY, USA, 2011.

Cemal Yilmaz. Test Case-Aware Covering Arrays (ongoing work)

Emine Dumlu, Cemal Yilmaz, Myra B. Cohen, and Adam Porter. Feedback driven adaptive combinatorial testing (journal extension of the ISSTA’11 publication)

Emine Dumlu, Cemal Yilmaz, Myra B. Cohen, and Adam Porter. Geribesleme gudumlu adaptif kombinasyonel test etme yaklasimi (ongoing work in Turkish).