Pointer Analysis in Java Programs using Execution Path Information

MPhil Thesis Defence


Title: "Pointer Analysis in Java Programs using Execution Path Information"

By

Mr. Jian WANG


Abstract

This thesis investigates the pointer alias information in Java programs.
The basic idea is to get the pointer alias information by generating and
analyzing the trace of one-time-run of the target programs. After
collecting traces of different runs of the target programs with various
inputs, we can perform the analysis on the reference variables with the
same type, which are equivalent to pointers. Being different from the
previous research, this research is a hybrid of static and dynamic
analysis. We obtain the execution trace by running the program, and then
we statically analyze the trace to discover the pointer alias information.

A trace tracks the complete information of one-time-run of the target
program with certain input. With different inputs, we can get different
traces of the program demonstrating the behavior of the program. After
analyzing a particular trace, we are sure to discover the portion of the
pointer alias pairs related to that run. And the result is obviously
sound. We can approximate the complete result by analyzing the traces with
different inputs and check the set of alias pair for convergence. Being
similar to other dynamic analysis algorithm, the choice and coverage of
the inputs are important to the result we discover.

To the best of our knowledge, this is the first to analyze the pointer
alias information in Java programs by execution traces on the source code
level. The contribution of our work is that the algorithm we propose is
precise compared the flow-insensitive algorithms of Steensgaard's and
Andersen's, while the time complexity is moderate. We believe that with
the development of computer hardware, the analysis of flow-sensitive
pointer alias shall be more and more important because of its preciseness.


Date:				Tuesday, 29 January 2008

Time:				3:00p.m.-5:00p.m.

Venue:				Room 3304
				Lifts 17-18

Committee Members:		Prof. Fangzhen Lin (Supervisor)
				Dr. Shing-Chi Cheung (Chairperson)
				Dr. Zonghua Gu


**** ALL are Welcome ****