From Value-Flow Graphs to Flow-Sensitive Constraint Graphs: Sparse Pointer Analysis

Pointer analysis determines the potential memory locations a pointer may reference during runtime, serving as a foundational component of static program analysis. This analysis enables numerous applications across software security, program verification, and compiler optimization. Enhancing the efficiency and precision of pointer analysis represents a long-standing research challenge, as its effectiveness directly influences the quality of downstream static analysis tasks. Flow-sensitive pointer analysis constitutes an essential component of precise program analysis for accurately modeling pointer behaviors by incorporating control flows. Flow-sensitive pointer analysis is extensively used in alias analysis, taint analysis, program understanding, compiler optimization, etc. Existing flow-sensitive pointer analysis approaches, which are conducted based on control flow graphs, have significantly advanced the precision of pointer analysis via sophisticated techniques to leverage control flow information. However, they inevitably suffer from computational inefficiencies when resolving points-to information due to the inherent complex structures of control flow graphs. This thesis presents a Flow-Sensitive Constraint Graph (FSConsG) based flow-sensitive pointer analysis framework to overcome the inefficiency of control-flow-graph-based analysis. This framework uses a flow-sensitive variant to leverage the structural advantages of set-constraint graphs (which are commonly used in flow-insensitive pointer analysis) while keeping the flow sensitivity of variable definitions and uses, allowing the incorporation of sophisticated graph optimization and dynamic solving techniques. In this way, the framework achieves significant efficiency improvements while keeping the precision of flow-sensitive analysis.