am deeply indebted to my parents for their fantastic love,endless support and everything else they have given me all through these years.Without them,I would not have been where I am now.I dedicate my dissertation and love to them
am deeply indebted to my parents for their fantastic love, endless support and everything else they have given me all through these years. Without them, I would not have been where I am now. I dedicate my dissertation and love to them. v
Contents Abstract i Acknowledgements iv 1 Introduction 1 1.1 Challenges.. 2 1.2 Contributions 1.3 Organization 5 2 Background:Context-Sensitive Points-to Analysis 7 2.1 Preliminary 7 2.2 Formalism .. 10 2.2.1 Notations.............. 10 2.2.2 Context-Sensitive Points-to Analysis 12 2.2.3 Context-Sensitivity ............... 13 3 BEAN:Precise Points-to Analysis via Object Allocation Graph 17 3.1 Overview.......... 17 3.2 Motivation.......····· 20 3.2.1 Redundant Elements in Method Contexts·..·.····. 20 3.2.2 Redundant Elements in Heap Contexts..··....···. 22 vi
Contents Abstract i Acknowledgements iv 1 Introduction 1 1.1 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Background: Context-Sensitive Points-to Analysis 7 2.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Formalism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.2 Context-Sensitive Points-to Analysis . . . . . . . . . . . . . 12 2.2.3 Context-Sensitivity . . . . . . . . . . . . . . . . . . . . . . . 13 3 Bean: Precise Points-to Analysis via Object Allocation Graph 17 3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2.1 Redundant Elements in Method Contexts . . . . . . . . . . 20 3.2.2 Redundant Elements in Heap Contexts . . . . . . . . . . . . 22 vi
3.2.3 Discussion.... 24 3.3 BEAN 25 3.3.1 Object Allocation Graph 26 3.3.2 Context Selection. 27 3.3.3 Discussion.... 28 3.4 Formalism........·· 29 3.4.1 Object Allocation Graph.... 29 3.4.2 Context Selection 31 3.4.3 BEAN-directed Object-Sensitive Points-to Analysis 36 3.4.4 Properties·... 36 3.5 Implementation.. 38 3.6 Evaluation..········ 38 3.6.1 Experimental Setting.....····..·········· 39 3.6.2 RQ1:Precision and Performance Measurements ...... 40 3.6.3 RQ2:A Real-World Case Study 43 3.7 Related Work······· 46 4 MAHJONG:Efficient Points-to Analysis by Merging Equivalent Au- tomata 49 4.1 Overview.........::···..···· 49 4.2 Motivation...............··… 52 4.2.1 Allocation-Type Abstraction:A Naive Solution....... 53 4.2.2 MAHJONG:Our Solution.... 54 4.3MAHJ0NG...... 60 4.3.1 Overview of MAHJONG... 60 4.3.2 The NFA Builder.... 61 4.3.3 The DFA Converter..... 61 vii
3.2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3 Bean . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.3.1 Object Allocation Graph . . . . . . . . . . . . . . . . . . . . 26 3.3.2 Context Selection . . . . . . . . . . . . . . . . . . . . . . . . 27 3.3.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4 Formalism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.4.1 Object Allocation Graph . . . . . . . . . . . . . . . . . . . . 29 3.4.2 Context Selection . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4.3 Bean-directed Object-Sensitive Points-to Analysis . . . . . 36 3.4.4 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.5 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.6.1 Experimental Setting . . . . . . . . . . . . . . . . . . . . . . 39 3.6.2 RQ1: Precision and Performance Measurements . . . . . . . 40 3.6.3 RQ2: A Real-World Case Study . . . . . . . . . . . . . . . . 43 3.7 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4 Mahjong: Efficient Points-to Analysis by Merging Equivalent Automata 49 4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.2.1 Allocation-Type Abstraction: A Naive Solution . . . . . . . 53 4.2.2 Mahjong: Our Solution . . . . . . . . . . . . . . . . . . . . 54 4.3 Mahjong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.3.1 Overview of Mahjong . . . . . . . . . . . . . . . . . . . . . 60 4.3.2 The NFA Builder . . . . . . . . . . . . . . . . . . . . . . . . 61 4.3.3 The DFA Converter . . . . . . . . . . . . . . . . . . . . . . . 61 vii
4.3.4 The Automata Equivalence Checker........ 62 4.3.5 The Heap Modeler 62 4.3.6 MAHJONG-based Points-.to Analysis..······· 62 4.4 Algorithms..... 66 4.4.1 MAHJONG.... 66 4.4.2 The NFA Builder..............·.... 68 4.4.3 The DFA Converter.....··· 69 4.4.4 The Automata Equivalence Checker 70 4.4.5 The Heap Modeler ........ 72 4.5 Implementation......... 72 4.6 Evaluation... 73 4.6.1 RQ1:MAHJONG's Effectiveness as a Pre-Analysis...... 75 4.6.2RQ2:MAHJONG-based Points-.to Analysis..·...···· 78 4.7 Related Work.......... 85 5 Conclusions and Future Work 88 5.1 Conclusions 88 5.2 Future Work.... 89 Bibliography 90 viii
4.3.4 The Automata Equivalence Checker . . . . . . . . . . . . . . 62 4.3.5 The Heap Modeler . . . . . . . . . . . . . . . . . . . . . . . 62 4.3.6 Mahjong-based Points-to Analysis . . . . . . . . . . . . . . 62 4.4 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.4.1 Mahjong . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.4.2 The NFA Builder . . . . . . . . . . . . . . . . . . . . . . . . 68 4.4.3 The DFA Converter . . . . . . . . . . . . . . . . . . . . . . . 69 4.4.4 The Automata Equivalence Checker . . . . . . . . . . . . . . 70 4.4.5 The Heap Modeler . . . . . . . . . . . . . . . . . . . . . . . 72 4.5 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.6.1 RQ1: Mahjong’s Effectiveness as a Pre-Analysis . . . . . . 75 4.6.2 RQ2: Mahjong-based Points-to Analysis . . . . . . . . . . 78 4.7 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5 Conclusions and Future Work 88 5.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Bibliography 90 viii
List of Figures 2 1 Notations...················· 11 2.2 Context-sensitive points-to analysis...···..····.····· 12 3.1 Method contexts for 2-obj and BEAN.................. 21 3.2 Heap contexts for2-obj and BEAN..·......·.....·... 23 3.3 Overview of BEAN...······.················· 25 3.4 The OAGs for the two motivating programs in Figures 3.1 and 3.2. 26 3.5 Notations for object allocation graph.................. 29 3.6 Rules for building the OAG,G=(N,E),for a program based on a 30 3.7 Rules for basic relations in an OAG,G=(N,E).·,···.···· 31 3.8 Rules for context selection in an OAG,G=(N,E).········ 32 3.9 An OAG...······ 33 3.10 Three Cases marked for [Hcrx-DIv]and [Hcrx-Cyc]in Figure 3.8... 35 3.11 A real--world application for using java.util.HaseSet...,···. 44 3.l2 Part of OAG related to HS,/1 and HS/2.....··.·.·..···. 45 4.1 An example program illustrating object merging...·..····.· 53 4.2 Field points-to graph rooted at of and o2............... 55 4.3 Illustrating Condition 2 in Definition 1................. 57 ix
List of Figures 2.1 Notations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Context-sensitive points-to analysis. . . . . . . . . . . . . . . . . . . 12 3.1 Method contexts for 2-obj and Bean. . . . . . . . . . . . . . . . . . 21 3.2 Heap contexts for 2-obj and Bean. . . . . . . . . . . . . . . . . . . 23 3.3 Overview of Bean. . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4 The OAGs for the two motivating programs in Figures 3.1 and 3.2. 26 3.5 Notations for object allocation graph. . . . . . . . . . . . . . . . . . 29 3.6 Rules for building the OAG, G = (N, E), for a program based on a pre-analysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.7 Rules for basic relations in an OAG, G = (N, E). . . . . . . . . . . 31 3.8 Rules for context selection in an OAG, G = (N, E). . . . . . . . . . 32 3.9 An OAG. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.10 Three Cases marked for [Hctx-Div] and [Hctx-Cyc] in Figure 3.8. . . 35 3.11 A real-world application for using java.util.HaseSet. . . . . . . . 44 3.12 Part of OAG related to HS/1 and HS/2. . . . . . . . . . . . . . . . . 45 4.1 An example program illustrating object merging. . . . . . . . . . . 53 4.2 Field points-to graph rooted at o T 1 and o T 2 . . . . . . . . . . . . . . . 55 4.3 Illustrating Condition 2 in Definition 1. . . . . . . . . . . . . . . . . 57 ix