22nd ACM SIGSOFT International Symposium on the Foundations of Software Engineering (FSE 2014), November 16–21, 2014, Hong Kong, China

Desktop Layout

Symbolic Execution
Main Research
Hall 4-7, Chair: Charles Zhang
Statistical Symbolic Execution with Informed Sampling
Antonio Filieri, Corina S. Păsăreanu, Willem Visser, and Jaco Geldenhuys
(University of Stuttgart, Germany; Carnegie Mellon University, USA; NASA Ames Research Center, USA; Stellenbosch University, South Africa)
Publisher's Version
Preprint
Abstract: Symbolic execution techniques have been proposed recently for the probabilistic analysis of programs. These techniques seek to quantify the likelihood of reaching program events of interest, e.g., assert violations. They have many promising applications but have scalability issues due to high computational demand. To address this challenge, we propose a statistical symbolic execution technique that performs Monte Carlo sampling of the symbolic program paths and uses the obtained information for Bayesian estimation and hypothesis testing with respect to the probability of reaching the target events. To speed up the convergence of the statistical analysis, we propose Informed Sampling, an iterative symbolic execution that first explores the paths that have high statistical significance, prunes them from the state space and guides the execution towards less likely paths. The technique combines Bayesian estimation with a partial exact analysis for the pruned paths leading to provably improved convergence of the statistical analysis. We have implemented statistical symbolic execution with informed sampling in the Symbolic PathFinder tool. We show experimentally that the informed sampling obtains more precise results and converges faster than a purely statistical analysis and may also be more efficient than an exact symbolic analysis. When the latter does not terminate symbolic execution with informed sampling can give meaningful results under the same time and memory limits.

Authors:


Time stamp: 2019-12-15T06:31:19+01:00