Falcon: A Fused Approach to Path-Sensitive Sparse Data Dependence Analysis

This paper presents a scalable path- and context-sensitive data dependence analysis. The key is to address the aliasing-path-explosion problem when enforcing a path-sensitive memory model. Specifically, our approach decomposes the computational efforts of disjunctive reasoning into 1) a context- and...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of ACM on programming languages 2024-06, Vol.8 (PLDI), p.567-592, Article 170
Main Authors: Yao, Peisen, Zhou, Jinguo, Xiao, Xiao, Shi, Qingkai, Wu, Rongxin, Zhang, Charles
Format: Article
Language:English
Subjects:
Program analysis
Theory of computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents a scalable path- and context-sensitive data dependence analysis. The key is to address the aliasing-path-explosion problem when enforcing a path-sensitive memory model. Specifically, our approach decomposes the computational efforts of disjunctive reasoning into 1) a context- and semi-path-sensitive analysis that concisely summarizes data dependence as the symbolic and storeless value-flow graphs, and 2) a demand-driven phase that resolves transitive data dependence over the graphs, piggybacking the computation of fully path-sensitive pointer information with the resolution of data dependence of interest. We have applied the approach to two clients, namely thin slicing and value-flow bug finding. Using a suite of 16 C/C++ programs ranging from 13 KLoC to 8 MLoC, we compare our techniques against a diverse group of state-of-the-art analyses, illustrating the significant precision and scalability advantages of our approach.
ISSN:2475-1421
2475-1421
DOI:10.1145/3656400