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 viContents 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