Bounded exhaustive testing is an effective methodology for detecting bugs in a wide range of applications. A well-known approach for bounded exhaustive testing is Korat. It generates all test inputs, up to a given small size, based on a formal specification that is written as an executable predicate and characterizes properties of desired inputs. Korat uses the predicate's executions on candidate inputs to implement a backtracking search based on pruning to systematically explore the space of all possible inputs and generate only those that satisfy the specification.
This paper presents a novel approach for speeding up test generation for bounded exhaustive testing using Korat. The novelty of our approach is two-fold. One, we introduce a new technique for writing the specification predicate based on an abstract representation of candidate inputs, so that the predicate executes directly on these abstract structures and each execution has a lower cost. Two, we use the abstract representation as the basis to define the first technique for utilizing GPUs for systematic test generation using executable predicates. Moreover, we present a suite of optimizations that enable effective utilization of the computational resources offered by modern GPUs. We use our prototype tool KoratG to experimentally evaluate our approach using a suite of 7 data structures that were used in prior studies on bounded exhaustive testing. Our results show that our abstract representation can speed up test generation by 5.68 times on a standard CPU, while execution on a GPU speeds up the execution, on average, by 17.46 times.
Thu 26 Oct
|15:30 - 15:52|
Talia RingerUniversity of Washington, Dan GrossmanUniversity of Washington, Daniel Schwartz-NarbonneAmazon, n.n., Serdar TasiranAmazon, n.n.DOI
|15:52 - 16:14|
Alastair DonaldsonImperial College London, Hugues EvrardImperial College London, UK, Andrei LascuImperial College London, Paul ThomsonImperial College LondonDOI
|16:14 - 16:37|
Ahmet CelikUniversity of Texas at Austin, USA, Sreepathi PaiUniversity of Rochester, Sarfraz KhurshidUniversity of Texas at Austin, Milos GligoricUniversity of Texas at AustinDOI
|16:37 - 16:59|
|16:59 - 17:22|