Precise and Efficient Points-to Analysis via New Context-Sensitivity and Heap Abstraction

Points-to analysis addresses a fundamental problem in program analysis: determining statically which objects a variable or reference can point to. As a fundamental technique, many real-world clients such as bug detection, security analysis, program understanding, compiler optimization and program verification, depend on the results of points-to analysis.A long-standing problem in points-to analysis is the balance between precision and efficiency. This thesis aims to improve both ends of the balance respectively.For precision, object-sensitivity is usually considered as the most precise context-sensitivity for points-to analysis for object-oriented languages, such as Java. However, it suffers from the scalability problem when increasing the context length and thus it is hard to further improve its precision. We present BEAN, a new object-sensitivity approach for points-to analysis. By identifying and eliminating the redundant context elements which contribute nothing to the precision, BEAN is able to improve the precision of any k-object-sensitive analysis by still using a k-limiting context abstraction.For efficiency, targeting the type-dependent clients such as call graph construction, devirtualization and may-fail casting, we present MAHJONG, a new heap abstraction approach for points-to analysis. By merging equivalent automata representing type-consistent objects that are created by the allocation-site abstraction, MAHJONG enables an allocation-site-based points-to analysis to run significantly faster while achieving nearly the same precision for type-dependent clients.We extensively evaluate BEAN and MAHJONG against the state-of-the-art points-to analysis for Java with large real-world Java applications and library. The results demonstrate that both BEAN and MAHJONG have met their goals of design. BEAN has succeeded in making points-to analysis more precise at only small increases in analysis cost. MAHJONG enables points-to analysis to run significantly faster while achieving nearly the same precision for type-dependent clients. We have released BEAN and MAHJONG as open-source tools