COST-AWARE COMBINATORIAL INTERACTION TESTING
Computer Science and Engineering, PhD Dissertation, 2017
Asst. Prof. Dr. Cemal Yılmaz (Thesis Advisor), Assoc. Prof. Hüsnü Yenigün,
Assoc. Prof. Tonguç Ünlüyurt, Assoc. Prof. Hasan Sözer, Assoc. Prof. Myra B. Cohen
Date & Time: July 13th, 2017 – 3:00 PM
Place: FENS 2008
Keywords : Software Testing, Combinatorial Interaction Testing, Covering Arrays,
Cost-Aware Covering Arrays, Cost Estimation, Cost Model Discovery
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 (CIT) 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 settings, a t-way covering array is a set of valid configurations in which each valid combination of option settings for every combination of t options appears at least once. The basic justification for using covering arrays is that they can effectively exercise the system behaviors caused by the settings 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 setting 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 different 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 cost-aware covering arrays can significantly reduce the actual cost of testing without adversely affecting the coverage properties, compared to existing covering arrays. One thing we observe in all these studies is that it could be difficult for practitioners to develop accurate and precise cost functions. The less accurate and the less precise the cost function is, the more the opportunity to further reduce the testing cost, is missed. Consequently, we also develop efficient and effective approaches to automatically discover the cost model in configuration spaces.