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 vii3.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.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