Context-free language (CFL) reachability is a fundamental framework for formulating program analyses. CFL-reachability analysis works on top of an edge-labeled graph by deriving reachability relations and adding them as labeled edges to the graph. Existing CFL-reachability algorithms typically adopt a single-reachability relation derivation (SRD) strategy, i.e., one reachability relation is derived at a time. Unfortunately, this strategy can lead to redundancy, hindering the efficiency of the analysis.

To address this problem, this paper proposes PEARL, a multi-derivation approach that reduces derivation redundancy for transitive relations that frequently arise when solving reachability relations, significantly improving the efficiency of CFL-reachability analysis. Our key insight is that multiple edges involving transitivity can be simultaneously derived via batch propagation of reachability relations on the transitivity-aware subgraphs that are induced from the original edge-labeled graph. We evaluate the performance of PEARL on two clients, i.e., context-sensitive value-flow analysis and field-sensitive alias analysis for C/C++. By eliminating a large amount of redundancy, PEARL achieves average speedups of 82.73x for value-flow analysis and 155.26x for alias analysis over the standard CFL-reachability algorithm. The comparison with POCR, a state-of-the-art CFL-reachability solver, shows that PEARL runs 10.1x (up to 29.2x) and 2.37x (up to 4.22x) faster on average respectively for value-flow analysis and alias analysis with less consumed memory.

Chenghang Shi

SKLP, Institute of Computing Technology, CAS

China

Haofeng Li

Yulei Sui

University of New South Wales, Sydney

Australia

JieLu

SKLP, Institute of Computing Technology, CAS

Lian Li

Institute of Computing Technology at Chinese Academy of Sciences; University of Chinese Academy of Sciences

China

Jingling Xue

UNSW

Australia