Bounded exhaustive test-input generation on GPUs
Bounded exhaustive test-input generation on GPUs
复制标题
GPU 上的有限详尽测试输入生成
DOI：
10.1145/3133918
复制
发表时间：
2017
影响因子：
--
通讯作者：
Gligoric, Milos
中科院分区：
文献类型：
--
作者：
Celik, Ahmet;Pai, Sreepathi;Khurshid, Sarfraz;Gligoric, Milos
有界详尽测试是检测各种应用程序中错误的有效方法。 Korat 是一种众所周知的有界穷举测试方法。它基于作为可执行谓词编写的正式规范生成所有测试输入，直到给定的小尺寸，并表征所需输入的属性。 Korat 使用候选输入上的谓词执行来实现基于修剪的回溯搜索，以系统地探索所有可能输入的空间并仅生成满足规范的输入。本文提出了一种使用 Korat 加速有界穷举测试的测试生成的新方法。我们的方法的新颖性有两个方面。首先，我们引入了一种新技术，用于根据候选输入的抽象表示来编写规范谓词，以便谓词直接在这些抽象结构上执行，并且每次执行的成本较低。第二，我们使用抽象表示作为基础来定义第一种利用 GPU 使用可执行谓词进行系统测试生成的技术。此外，我们还提出了一套优化方法，可以有效利用现代 GPU 提供的计算资源。我们使用我们的原型工具 KoratG 通过一套 7 个数据结构来实验评估我们的方法，这些数据结构在之前的有界穷举测试研究中使用过。我们的结果表明，我们的抽象表示可以在标准 CPU 上将测试生成速度加快 5.68 倍，而在 GPU 上执行则平均将执行速度加快 17.46 倍。
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.
登录
查看更多内容
影响因子：
1.3
作者：
Betts A
通讯作者：
Betts A
DOI：
10.1109/icstw.2011.100
发表时间：
2011-03
期刊：
2011 IEEE Fourth International Conference on Software Testing, Verification and Validation Workshops
影响因子：
--
作者：
Phil McMinn
通讯作者：
Phil McMinn
通过有限的详尽测试来保证软件
影响因子：
7.4
作者：
D. Coppit;Jinlin Yang;S. Khurshid;Wei Le;K. Sullivan
通讯作者：
K. Sullivan
MKorat：一种记忆 Korat 搜索的新方法和一些潜在的应用
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
Nima Dini
通讯作者：
Nima Dini
DOI：
10.1145/1287624.1287645
发表时间：
2007-09
期刊：
--
影响因子：
--
作者：
Sasa Misailovic;Aleksandar Milicevic;Nemanja Petrović;S. Khurshid;D. Marinov
通讯作者：
Sasa Misailovic;Aleksandar Milicevic;Nemanja Petrović;S. Khurshid;D. Marinov