85
IRUS Total
Downloads
  Altmetric

Iterative Distribution-Aware Sampling for Probabilistic Symbolic Execution

File Description SizeFormat 
2015-fse-qcoral.pdfAccepted version526.96 kBAdobe PDFView/Open
Title: Iterative Distribution-Aware Sampling for Probabilistic Symbolic Execution
Authors: Borges, M
Filieri, A
D Amorim, M
P uas uareanu, CS
Item Type: Conference Paper
Abstract: Probabilistic symbolic execution aims at quantifying the probability of reaching program events of interest assuming that program inputs follow given probabilistic distributions. The technique collects constraints on the inputs that lead to the target events and analyzes them to quantify how likely it is for an input to satisfy the constraints. Current techniques either handle only linear constraints or only support continuous distributions using a “discretization” of the input domain, leading to imprecise and costly results. We propose an iterative distribution-aware sampling approach to support probabilistic symbolic execution for arbitrarily complex mathematical constraints and continuous input distributions. We follow a compositional approach, where the symbolic constraints are decomposed into sub-problems whose solution can be solved independently. At each iteration the convergence rate of the com- putation is increased by automatically refocusing the analysis on estimating the sub-problems that mostly affect the accuracy of the results, as guided by three different ranking strategies. Experiments on publicly available benchmarks show that the proposed technique improves on previous approaches in terms of scalability and accuracy of the results.
Issue Date: 30-Aug-2015
URI: http://hdl.handle.net/10044/1/33294
DOI: http://dx.doi.org/10.1145/2786805.2786832
ISBN: 978-1-4503-3675-8
Publisher: ACM
Start Page: 866
End Page: 877
Journal / Book Title: Proceedings of the 10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering
Copyright Statement: © ACM 2015 This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, http://dx.doi.org/10.1145/2786805.2786832
Notes: location: Bergamo, Italy numpages: 12 keywords: Adaptive software, control theory, dynamic systems, non-functional requirements, run-time verification acceptance: 74/291, 25.4% acronym: ESEC/FSE
Appears in Collections:Computing
Faculty of Engineering