Parallel test generation and execution with Korat
Parallel test generation and execution with Korat
复制标题
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
我们提出了新的算法，用于并行测试结构复杂的测试输入的代码。这些算法建立在Korat算法的基础上，用于基于约束的结构复杂测试输入的生成。给定指定期望的结构约束的命令性谓词和限定期望的输入大小的终结化，Korat执行系统搜索以生成满足约束的所有测试输入(在界限内)。我们介绍了如何在Korat中通过并行搜索生成测试输入，以及如何并行执行测试输入，包括离线(当输入保存在磁盘上时)和在线(当生成之后立即执行时)。Korat生成的输入支持有界穷举测试，该测试针对给定边界内的所有输入对被测试代码进行穷举检查。我们还描述了一种减少Korat可以生成的等效输入数量的新方法。我们开发并行Korat和减少等价输入的方法的动机是测试在Google开发的一个应用程序。在谷歌基础设施上的1024台机器上运行并行Korat的实验结果表明，并行测试生成和执行可以获得高达543.55倍的显著加速比。
We present novel algorithms for parallel testing of code that takes structurally complex test inputs. The algorithms build on the Korat algorithm for constraint-based generation of structurally complex test inputs. Given an imperative predicate that specifies the desired structural constraints and a finitization that bounds the desired input size, Korat performs a systematic search to generate all test inputs (within the bounds) that satisfy the constraints. We present how to generate test inputs with a parallel search in Korat and how to execute test inputs in parallel, both off-line (when the inputs are saved on disk) and on-line (when execution immediately follows generation). The inputs that Korat generates enable bounded-exhaustive testing that checks the code under test exhaustively for all inputs within the given bounds. We also describe a novel methodology for reducing the number of equivalent inputs that Korat can generate. Our development of parallel Korat and the methodology for reducing equivalent inputs are motivated by testing an application developed at Google. The experimental results on running parallel Korat across up to 1024 machines on the Google's infrastructure show that parallel test generation and execution can achieve significant speedup, up to 543.55 times.