PREACH: A Heuristic for Probabilistic Reachability to Identify Hard to Reach Statements

Seemanta Saha, Mara Downing, Tegan Brennan, Tevfik Bultan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations

Abstract

We present a heuristic for approximating the likelihood of reaching a given program statement using 1) branch selectivity (representing the percentage of values that satisfy a branch condition), which we compute using model counting, 2) dependency analysis, which we use to identify input-dependent branch conditions that influence statement reachability, 3) abstract interpretation, which we use to identify the set of values that reach a branch condition, and 4) a discrete-time Markov chain model, which we construct to capture the control flow structure of the program together with the selectivity of each branch. Our experiments indicate that our heuristic-based probabilistic reachability analysis tool PReach can identify hard to reach statements with high precision and accuracy in benchmarks from software verification and testing competitions, Apache Commons Lang, and the DARPA STAC program. We provide a detailed comparison with probabilistic symbolic execution and statistical symbolic execution for the purpose of identifying hard to reach statements. PREACH achieves comparable precision and accuracy to both probabilistic and statistical symbolic execution for bounded execution depth and better precision and accuracy when execution depth is unbounded and the number of program paths grows exponentially. Moreover, PReach is more scalable than both probabilistic and statistical symbolic execution.

Original languageEnglish
Title of host publicationProceedings - 2022 ACM/IEEE 44th International Conference on Software Engineering, ICSE 2022
Pages1706-1717
Number of pages12
ISBN (Electronic)9781450392211
DOIs
StatePublished - 2022
Event44th ACM/IEEE International Conference on Software Engineering, ICSE 2022 - Pittsburgh, United States
Duration: 22 May 202227 May 2022

Publication series

NameProceedings - International Conference on Software Engineering
Volume2022-May
ISSN (Print)0270-5257

Conference

Conference44th ACM/IEEE International Conference on Software Engineering, ICSE 2022
Country/TerritoryUnited States
CityPittsburgh
Period22/05/2227/05/22

Fingerprint

Dive into the research topics of 'PREACH: A Heuristic for Probabilistic Reachability to Identify Hard to Reach Statements'. Together they form a unique fingerprint.

Cite this