GPU-based parallel computing methods for constructing covering arrays

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

As software systems becomes more complex, demand for e cient approaches to test these kind of systems with a lower cost is increased highly, too. One example of such applications can be given highly configurable software systems such as web servers (e.g. Apache) and databases (e.g. MySQL). They have many configurable options which interact each other and these option interactions lead having exponential growth of option configurations. Hence, these software systems become more prone to bugs which are caused by the interaction of options. A solution to this problem can be combinatorial interaction testing which systematically samples the configuration space and tests each of these samples, individually. Combinatorial interaction testing computes a small set of option configurations to be used as test suites, called covering arrays. A t-way covering array aims to cover all t-length option interactions of system under test with a minimum number of configurations where t is a small number in practical cases. Applications of covering arrays are especially encouraged after many researches empirically pointed out that substantial number of faults are caused by smaller value of option interaction. Nevertheless, computing covering arrays with a minimal number of configurations in a reasonable time is not easy task, especially when the configuration space is large and system has inter-option constraints that invalidate some configurations. Therefore, this study field attracts various researchers. Although most of approaches su er in scalability issue, many successful attempts have been also done to construct covering arrays. However, as the configuration scape gets larger, most of the approaches start to su er. Combinatorial problems e.g., in our case constructing covering arrays, are mainly solved by using e cient counting techniques. Based on this assumption, we conjecture that covering arrays can be computed using parallel algorithms e ciently since counting is an easy task which can be carried out with parallel programming strategies. Although di erent architectures are e ective in di erent researches, we choose to use GPU-based parallel computing techniques since GPUs have hundreds even sometimes thousands of cores however with small arithmetic logic units. Despite the fact that these cores are exceptionally constrained and limited, they serve our purpose very well since all we need to do is basic counting, repeatedly. We apply this idea in order to decrease the computation time on a meta-heuristic, search method simulated annealing, which is well studied in construction of covering arrays and, in general, gives the smallest size results in previous studies. Moreover, we present a technique to generate multiple neighbour states in each step of simulated annealing in parallel. Finally, we propose a novel hybrid approach using SAT solver with parallel computing techniques to decrease the negative e ect of pure random search and decrease the covering array size further. Our results prove our assumption that parallel computing is an e ective and e cient way to compute combinatorial objects.