Efficient and Precise Points-to Analysis: Modeling the Heap by Merging Equivalent Automata Tian Tan* Yue Li*Jingling Xue School of Computer Science and Engineering,UNSW,Australia Abstract Every points-to analysis,especially for object-oriented lan- Mainstream points-to analysis techniques for object-oriented guages such as Java and C#,requires a heap abstraction for languages rely predominantly on the allocation-site abstrac- partitioning the infinitely-sized heap into a finite number tion to model heap objects.We present MAHJONG,a novel of(abstract)objects.For object-oriented programs,context- heap abstraction that is specifically developed to address sensitivity is important for achieving useful precision.Due to the needs of an important class of type-dependent clients, many years of research,context-sensitivity can be achieved such as call graph construction,devirtualization and may- by three main approaches with different efficiency and pre- fail casting.By merging equivalent automata representing cision tradeoffs:call-site-sensitivity [15,22,36,42,51,53]. type-consistent objects that are created by the allocation- object-sensitivity [29,40,48]and type-sensitivity [39]. site abstraction,MAHJONG enables an allocation-site-based However,little progress has been made on developing points-to analysis to run significantly faster while achieving heap abstractions for points-to analysis.Mainstream points- nearly the same precision for type-dependent clients. to analysis frameworks for Java,such as CHORD [10], MAHJONG is simple conceptually,efficient,and drops DOOP [14],SOOT [49]and WALA [50],rely predominantly easily on any allocation-site-based points-to analysis.We on the allocation-site abstraction to model heap objects.In demonstrate its effectiveness by discussing some insights on this case,distinct allocation sites are represented by distinct why it is a better alternative of the allocation-site abstraction (abstract)objects,with one object per site,which can be fur- for type-dependent clients and evaluating it extensively on ther separated context-sensitively in an orthogonal manner. 12 large real-world Java programs with five context-sensitive As programming languages become more heap-intensive, points-to analyses and three widely used type-dependent the need for effective heap abstractions is greater [19,38. clients.MAHJONG is expected to provide significant benefits 44].The suitability of the allocation-site abstraction as a uni for many program analyses where call graphs are required. versal solution for all clients of points-to analysis needs to be revisited.While maximizing the precision for may-alias, CCS Concepts·Theory of computation→Program this abstraction often over-partitions the heap without im- analysis proving the precision much for an important class of type- dependent clients such as call graph construction,devirtu- Keywords points-to analysis.heap abstraction alization and may-fail casting,causing often the underlying points-to analysis to be unscalable for large programs.For 1.Introduction this reason,WALA [50]and DOOP [14],provide an option Pointer Analyses should be designed to be appropriate for all objects of a certain class,such as java.lang.String in cost and precision for specific groups of client prob- or java.lang.StringBuffer,to be merged ad hocly. lems.We do not need a different pointer analysis per In this paper,we present MAHJONG,a novel heap ab- client problem,but rather we should look for classes of straction that is specifically developed to address the needs client problems with similar needs. of type-dependent clients.Given a program,we first create a lightweight alternative of the allocation-site abstraction by Barbara Ryder [17] performing a fast but imprecise allocation-site-based points- These authors contributed equally to this work to analysis as a pre-analysis and then use it to drive a subse- quent points-to analysis.Based on the points-to information found during the pre-analysis,MAHJONG merges two ob- Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee pr jects if both are type-consistent,i.e..if the objects reached ovided that opies for advantage and that copies bear this notice and the full cita from both along the same sequence of field accesses have on the first page.Copyrights for components of this work owned by others than ACM must be honored.Abstracting with credit is permitted.To copy otherwise,or republish. a common type.We formulate the problem of checking the to post on servers or to redistribute to lists,requires prior specific permission and/or a type-consistency of two objects as one of testing the equiv- fee.Request permissions from Permissions@acm.org. alence of two sequential automata in almost linear time,by PLDI'17,June 18-23,2017,Barcelona,Spain 92017ACM978-1-4503-4988-8/1706.S15.00 applying a classic Hopcroft-Karp algorithm [18]with minor nttp://dx.doi.org/10.1145/3062341.3062360 278Efficient and Precise Points-to Analysis: Modeling the Heap by Merging Equivalent Automata Tian Tan∗ Yue Li ∗ Jingling Xue School of Computer Science and Engineering, UNSW, Australia Abstract Mainstream points-to analysis techniques for object-oriented languages rely predominantly on the allocation-site abstrac￾tion to model heap objects. We present MAHJONG, a novel heap abstraction that is specifically developed to address the needs of an important class of type-dependent clients, such as call graph construction, devirtualization and may￾fail casting. 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. MAHJONG is simple conceptually, efficient, and drops easily on any allocation-site-based points-to analysis. We demonstrate its effectiveness by discussing some insights on why it is a better alternative of the allocation-site abstraction for type-dependent clients and evaluating it extensively on 12 large real-world Java programs with five context-sensitive points-to analyses and three widely used type-dependent clients. MAHJONG is expected to provide significant benefits for many program analyses where call graphs are required. CCS Concepts •Theory of computation → Program analysis Keywords points-to analysis, heap abstraction 1. Introduction Pointer Analyses should be designed to be appropriate in cost and precision for specific groups of client prob￾lems. We do not need a different pointer analysis per client problem, but rather we should look for classes of client problems with similar needs. — Barbara Ryder [17] ∗ These authors contributed equally to this work Every points-to analysis, especially for object-oriented lan￾guages such as Java and C#, requires a heap abstraction for partitioning the infinitely-sized heap into a finite number of (abstract) objects. For object-oriented programs, context￾sensitivity is important for achieving useful precision. Due to many years of research, context-sensitivity can be achieved by three main approaches with different efficiency and pre￾cision tradeoffs: call-site-sensitivity [15, 22, 36, 42, 51, 53], object-sensitivity [29, 40, 48] and type-sensitivity [39]. However, little progress has been made on developing heap abstractions for points-to analysis. Mainstream points￾to analysis frameworks for Java, such as CHORD [10], DOOP [14], SOOT [49] and WALA [50], rely predominantly on the allocation-site abstraction to model heap objects. In this case, distinct allocation sites are represented by distinct (abstract) objects, with one object per site, which can be fur￾ther separated context-sensitively in an orthogonal manner. As programming languages become more heap-intensive, the need for effective heap abstractions is greater [19, 38, 44]. The suitability of the allocation-site abstraction as a uni￾versal solution for all clients of points-to analysis needs to be revisited. While maximizing the precision for may-alias, this abstraction often over-partitions the heap without im￾proving the precision much for an important class of type￾dependent clients such as call graph construction, devirtu￾alization and may-fail casting, causing often the underlying points-to analysis to be unscalable for large programs. For this reason, WALA [50] and DOOP [14], provide an option for all objects of a certain class, such as java.lang.String or java.lang.StringBuffer, to be merged ad hocly. In this paper, we present MAHJONG, a novel heap ab￾straction that is specifically developed to address the needs of type-dependent clients. Given a program, we first create a lightweight alternative of the allocation-site abstraction by performing a fast but imprecise allocation-site-based points￾to analysis as a pre-analysis and then use it to drive a subse￾quent points-to analysis. Based on the points-to information found during the pre-analysis, MAHJONG merges two ob￾jects if both are type-consistent, i.e., if the objects reached from both along the same sequence of field accesses have a common type. We formulate the problem of checking the type-consistency of two objects as one of testing the equiv￾alence of two sequential automata in almost linear time, by applying a classic Hopcroft-Karp algorithm [18] with minor Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Permissions@acm.org. PLDI’17, June 18–23, 2017, Barcelona, Spain c 2017 ACM. 978-1-4503-4988-8/17/06...$15.00 http://dx.doi.org/10.1145/3062341.3062360 278