Cost-Aware combinatorial interaction testing

Official URL: http://risc01.sabanciuniv.edu/record=b1655753 (Table of Contents)

Exhaustive testing of highly configurable software systems is generally infeasible as the number of possible configurations grows exponentially with the number of configuration options. Combinatorial Interaction Testing approaches systematically sample the configuration spaces and test only the selected configurations. The sampling is typically carried out by computing a combinatorial object, called a t-way covering array. Given a configuration space model that includes a set of configuration options, each of which takes a value from a discrete domain, together with inter-option constraints (if any), which invalidate certain combinations of option values, a t-way covering array is a set of valid configurations in which each valid combination of option values for every combination of t options appears at least once. The basic justification for using covering arrays is that they can e ectively exercise the system behaviors caused by the values of t or fewer options. Consequently, covering arrays have been widely used for testing in many domains, including the systematic testing of configurable systems, input parameter spaces, graphical user interfaces, network protocols, and software product lines. To reduce the actual cost of testing, covering arrays aim to reduce the number of configurations selected. By doing so, they implicitly assume that the cost of testing each configuration is the same. In this thesis, we, however, empirically demonstrate that, in practice, the cost often varies from one configuration to another and that when the cost varies, reducing the number of configurations is not necessarily the same as reducing the actual cost of testing. To overcome this issue, we first define a novel combinatorial object for testing called, a cost-aware covering array, which takes the cost of testing into account when computing interaction test suites. In a nutshell, given a configuration space model, enhanced with a cost function, which models the actual cost of testing at the level of option value combinations, a t-way cost-aware covering array is a standard t-way covering array that “minimizes” the given cost function, rather than the number of configurations selected. We then develop specialized construction approaches to turn two di erent types of existing covering arrays, namely standard covering arrays and test case-aware covering arrays, into cost-aware interaction test suites. The results of our experiments conducted on large, widely-used, and highly-configurable software systems strongly suggest that costaware covering arrays can significantly reduce the actual cost of testing without adversely a ecting the coverage properties, compared to existing covering arrays. One thing we observe in all these studies is that it could be di cult for practitioners to develop accurate and precise cost functions. The opportunity to further reduce the testing cost decreases as the cost function is less accurate or less precise. To address this, we develop e cient and e ective approaches to automatically discover the cost model in configuration spaces.