Annotated inclusion constraints for precise flow analysis

Program flow analysis has many applications in software tools for program understanding, restructuring, verification, testing and reverse engineering. There are two important requirements for a flow analysis to be applied successfully in software tools: precision and practicality. We propose annotated inclusion constraints - a new general framework for formulating and implementing precise inclusion-based flow analyses. The framework can be instantiated in two dimensions: one can select a flow analysis that can be modeled using inclusion constraints (e.g., class analysis, points-to analysis) and add a dimension of precision by choosing appropriate annotations (e.g., field sensitivity, context sensitivity). The framework encompasses a large spectrum of relatively precise flow analyses. We formulate and implement several points-to analyses for Java as instances of the framework. The experiments show that precision dimensions such as field sensitivity and context sensitivity have significant impact on the points-to analysis and its clients. In the same time, using annotations to model these precision dimensions results in efficient and practical analysis. Therefore, flow analyses based on annotated constraints can be successfully incorporated in software tools.