Header menu link for other important links
X
EagerMerge: An optimistic technique for efficient points-to analysis
Published in Association for Computing Machinery, Inc
2016
Pages: 47 - 58
Abstract
We present an information-merging technique for efficient computation of points-to information for C programs. Invalid use of pointers can lead to hard-to-find bugs and may expose security vulnerabilities. Thus, analyzing them is critical for software analysis as well as optimization. Pointer analysis is a key step during compilation, and the computed points-to information is useful for client analyses from varied domains such as bug finding, data-flow analysis, identifying security vulnerabilities, and parallelization, to name a few. Former research on pointer analysis has indicated that the main bottleneck towards scalability is large propagation of points-to information in the constraint graph. To reduce the propagation cost, we present a technique based on temporal similarity of points-to sets. The method tracks pointers whose dynamically changing points-to information remains equal for a while. Based on the optimism gained by observing the points-to sets over time, the analysis decides to merge the corresponding nodes. Using the notion of merge and split, we build a family of points-to analyses, and compare their relative precisions in the context of existing analyses. We illustrate the effectiveness of our approach using a suite of sixteen SPEC 2000 benchmarks and three large open-source programs, and show that the technique improves the analysis time over BDD and bitmap based Hybrid Cycle Detection, well-known Andersen's analysis, and Deep Propagation, affecting minimal precision (precision is 96.4% on an average). Specifically, it is faster than Deep Propagation by 45%. © 2016 ACM.
About the journal
JournalData powered by TypesetISSTA 2016 - Proceedings of the 25th International Symposium on Software Testing and Analysis
PublisherData powered by TypesetAssociation for Computing Machinery, Inc
Open AccessNo
Concepts (15)
  •  related image
    C (programming language)
  •  related image
    Flow graphs
  •  related image
    Merging
  •  related image
    Open source software
  •  related image
    Security of data
  •  related image
    Software testing
  •  related image
    Approximation
  •  related image
    Constraint graph
  •  related image
    Efficient computation
  •  related image
    FLOW-INSENSITIVE ANALYSIS
  •  related image
    OPEN SOURCE PROJECTS
  •  related image
    OPTIMISTIC TECHNIQUES
  •  related image
    Points-to analysis
  •  related image
    Security vulnerabilities
  •  related image
    Data flow analysis