Write a Blog >>
SPLASH 2017
Sun 22 - Fri 27 October 2017 Vancouver, Canada
Thu 26 Oct 2017 16:14 - 16:37 at Regency A - Testing Chair(s): Christian Hammer

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

splash-2017-OOPSLA
15:30 - 17:22: OOPSLA - Testing at Regency A
Chair(s): Christian HammerUniversity of Potsdam
splash-2017-OOPSLA15:30 - 15:52
Talk
Talia RingerUniversity of Washington, Dan GrossmanUniversity of Washington, Daniel Schwartz-NarbonneAmazon, n.n., Serdar TasiranAmazon, n.n.
DOI
splash-2017-OOPSLA15:52 - 16:14
Talk
Alastair DonaldsonImperial College London, Hugues EvrardImperial College London, UK, Andrei LascuImperial College London, Paul ThomsonImperial College London
DOI
splash-2017-OOPSLA16:14 - 16:37
Talk
Ahmet CelikUniversity of Texas at Austin, USA, Sreepathi PaiUniversity of Rochester, Sarfraz KhurshidUniversity of Texas at Austin, Milos GligoricUniversity of Texas at Austin
DOI
splash-2017-OOPSLA16:37 - 16:59
Talk
Xia LiUniversity of Texas at Dallas, USA, Lingming Zhang
DOI
splash-2017-OOPSLA16:59 - 17:22
Talk
Erik Krogh KristensenAarhus University, Denmark, Anders MøllerAarhus University
DOI