Parallel symbolic execution for structural test generation
Parallel symbolic execution for structural test generation
复制标题
DOI：
10.1145/1831708.1831732
复制
发表时间：
2010-07
期刊：
影响因子：
--
通讯作者：
Matthew Staats;C. Păsăreanu
中科院分区：
文献类型：
--
作者：
Matthew Staats;C. Păsăreanu
符号执行是一种自动生成实现高结构覆盖率的测试用例的流行技术。符号执行遇到可扩展性问题，因为对于大多数现实程序而言，需要探索的符号路径的数量非常大（甚至是无限）。为了解决这个问题，我们提出了一种技术，简单的静态分区，以并行化符号执行。该技术使用一组前条件来划分符号执行树，使我们能够有效地分发符号执行并减少探索符号执行树所需的时间。所提出的技术需要平行实例之间的通信，旨在与各种体系结构合作，从快速的多核机到云到云或网格计算环境。我们在Java Pathfinder验证工具集中实施我们的技术，并在探索有限的符号执行树并进行自动测试生成时在六个案例研究中对其进行评估。我们在两个有限符号执行树上的分析时间和相对于连续执行的测试所需的时间中都表明了加速度的加速，使用128名工人观察到90倍的最大分析时间速度，并使用64名工人观察到的最大测试生成速度为70倍。 。
Symbolic execution is a popular technique for automatically generating test cases achieving high structural coverage. Symbolic execution suffers from scalability issues since the number of symbolic paths that need to be explored is very large (or even infinite) for most realistic programs. To address this problem, we propose a technique, Simple Static Partitioning, for parallelizing symbolic execution. The technique uses a set of pre-conditions to partition the symbolic execution tree, allowing us to effectively distribute symbolic execution and decrease the time needed to explore the symbolic execution tree. The proposed technique requires little communication between parallel instances and is designed to work with a variety of architectures, ranging from fast multi-core machines to cloud or grid computing environments. We implement our technique in the Java PathFinder verification tool-set and evaluate it on six case studies with respect to the performance improvement when exploring a finite symbolic execution tree and performing automatic test generation. We demonstrate speedup in both the analysis time over finite symbolic execution trees and in the time required to generate tests relative to sequential execution, with a maximum analysis time speedup of 90x observed using 128 workers and a maximum test generation speedup of 70x observed using 64 workers.