Parasaram, Nikhil; Barr, Earl T; Mechtaev, Sergey; Böhme, Marcel; (2023) Precise Data-Driven Approximation for Program Analysis via Fuzzing. In: 2023 38th IEEE/ACM International Conference on Automated Software Engineering (ASE). (pp. pp. 611-623). IEEE (Institute of Electrical and Electronics Engineers): Luxembourg, Luxembourg.

Preview

Text ase23.pdf - Accepted Version Download (677kB) | Preview

Abstract

Program analysis techniques such as abstract interpretation and symbolic execution suffer from imprecision due to over- and underapproximation, which results in false alarms and missed violations. To alleviate this imprecision, we propose a novel data structure, program state probability (PSP), that leverages execution samples to probabilistically approximate reachable program states. The core intuition of this approximation is that the probability of reaching a given state varies greatly, and thus we can considerably increase analysis precision at the cost of a small probability of unsoundness or incompleteness, which is acceptable when analysis targets bug-finding. Specifically, PSP enhances existing analyses by disregarding low-probability states deemed feasible by overapproximation and recognising highprobability states deemed infeasible by underapproximation. We apply PSP in three domains. First, we show that PSP enhances the precision of the Clam abstract interpreter in terms of MCC from 0.09 to 0.27 and F1 score from 0.22 to 0.34. Second, we demonstrate that a symbolic execution search strategy based on PSP that prioritises program states with a higher probability increases the number of found bugs and reduces the number of solver calls compared to state-of-the-art techniques. Third, a program repair patch prioritisation strategy based on PSP reduces the average patch rank by 26%.

Download activity - last month

Export as CSVXMLJSON

Download activity - last 12 months

Export as CSVXMLJSON

Downloads by country - last 12 months

Export as JSONCSVXML

Archive Staff Only

View Item