Symbolic parallel adaptive importance sampling for probabilistic program analysis
Symbolic parallel adaptive importance sampling for probabilistic program analysis
复制标题
用于概率程序分析的符号并行自适应重要性采样
DOI：
10.1145/3468264.3468593
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Yuanshuo Zhou
中科院分区：
文献类型：
--
作者：
Yicheng Luo;A. Filieri;Yuanshuo Zhou
概率软件分析旨在使用概率编程构造来量化在处理不确定传入数据或编写自身的程序的执行期间发生目标事件的概率。最近的技术将符号执行与模型计数或解空间量化方法相结合，以获得对罕见目标事件发生概率的准确估计，例如任务关键系统中的故障。然而，在分析具有高维和相关多变量输入分布的软件处理时，它们面临一些可伸缩性和适用性限制。本文提出了符号并行自适应重要性抽样(SYMPAIS)，这是一种新的推理方法，用于分析具有高维相关输入分布的程序的符号执行所产生的路径条件。SYMPAIS将重要性抽样和约束求解的结果结合在一起，为当前解空间量化方法无法分析的一大类约束产生满足概率的准确估计。在一组来自不同应用领域的问题上，我们将SYMPAIS的通用性和性能与最先进的替代方案进行了比较。
Probabilistic software analysis aims at quantifying the probability of a target event occurring during the execution of a program processing uncertain incoming data or written itself using probabilistic programming constructs. Recent techniques combine symbolic execution with model counting or solution space quantification methods to obtain accurate estimates of the occurrence probability of rare target events, such as failures in a mission-critical system. However, they face several scalability and applicability limitations when analyzing software processing with high-dimensional and correlated multivariate input distributions. In this paper, we present SYMbolic Parallel Adaptive Importance Sampling (SYMPAIS), a new inference method tailored to analyze path conditions generated from the symbolic execution of programs with high-dimensional, correlated input distributions. SYMPAIS combines results from importance sampling and constraint solving to produce accurate estimates of the satisfaction probability for a broad class of constraints that cannot be analyzed by current solution space quantification methods. We demonstrate SYMPAIS's generality and performance compared with state-of-the-art alternatives on a set of problems from different application domains.
影响因子：
1.4
作者：
Tang, Xiaoyu;Xie, Xiang;Zhou, Hongliang
通讯作者：
Zhou, Hongliang