Staged points-to analysis for large code bases

A computer readable medium for performing a staged points-to analysis of a codebase written in an object-oriented programming language, comprising instructions for:

• obtaining the codebase and a points-to query comprising a plurality of query variables in the codebase;
• slicing the codebase based on the points-to query and a plurality of slice rules to obtain a program slice;
• performing a type analysis of the program slice based on a plurality of type rules to compute a type set;
• refining the program slice, after performing the type analysis, by resolving a plurality of virtual dispatch sites based on the type set;
• performing, after refining the program slice and based on a first plurality of points-to rules, a context-insensitive and field-sensitive first points-to analysis of the program slice to compute a first points-to set;
• re-refining the program slice, after performing the first points-to analysis, by resolving the plurality of virtual dispatch sites based on the first points-to set;
• and
• performing, after re-refining the program slice and based on a second plurality of points-to rules, a context-sensitive second points-to analysis of the program slice to compute a second points-to set,
• wherein the second points-to set is provided to a developer.

A system for performing a staged points-to analysis of a codebase written in an object-oriented programming language, comprising:

• an analysis repository storing the codebase, a plurality of slice rules, a plurality of type rules, a first plurality of points-to rules, a second plurality of points-to rules, and a points-to query comprising a plurality of query variables in the codebase;
• a processor;
• and
• a staged analysis platform executing on the processor and comprising:
• a slicing module configured to:
• slice the codebase based on the points-to query and the plurality of slice rules to obtain a program slice,
• refine the program slice, after a type analysis of the program slice is performed, by resolving a plurality of virtual dispatch sites based on a type set, and
• re-refine the program slice, after a first points-to analysis is performed, by resolving the plurality of virtual dispatch sites based on a first points-to set;
• a type analysis engine configured to perform the type analysis of the program slice based on the plurality of type rules to compute the type set;
• and
• a points-to analysis engine configured to:
• perform, after the program slice is refined and based on the first plurality of points-to rules, the first points-to analysis of the program slice to compute the first points-to set, wherein the first points-to analysis is context-insensitive and field-sensitive, and
• perform, after the program slice is re-refined and based on the second plurality of points-to rules, a context-sensitive second points-to analysis of the program slice to compute a second points-to set,
• wherein the second points-to set is provided to a developer.