AbstractThe solution of data-flow analysis of object-oriented programming languages such as C++/Java is needed for many important applications: aggressive code optimization, side-effect analysis, program specialization, program slicing and data-flow-based testing. However, data-flow analysis of object-oriented programming languages is difficult due to a large number of heap-allocated objects whose fields point to other heap-allocated objects (recursive structures), dynamic dispatch, frequent method invocations, a large number of methods, many invocation contexts per method and exceptions. In this thesis we present a new data-flow analysis technique called Relevant Context Inference (RCI) for modular, flow- and context-sensitive data-flow analysis of statically typed object-oriented programming languages such as C++ and Java. This technique has been designed to overcome the above difficulties. RCI has several long sought-after characteristics: 1. It can analyze programs by keeping only a part of the programs in memory at a time, with a constant bound on the number of times a procedure needs to be in memory. 2. It can analyze incomplete programs such as libraries. 3. It can analyze programs that have exceptions. We have built a prototype of RCI for points-to analysis of C++ programs. The empirical results obtained using this prototype and presented in this thesis show that RCI is effective in practice. We present several new complexity characterizations of points-to analysis in the presence of object-oriented language constructs: exceptions and dynamic dispatch. Our results clearly identify the difficult features and indicate approximations that any efficient algorithm has to make. We also present a new approach to data-flow-based testing of object-oriented libraries using RCI . We show how the information computed by RCI can be used for generating relevant test cases.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).