[21 Nov]

Well, since I dont have anything to do now (because I dont know what I
should do), I thought I could better spend the time writing a report of my
mostly failed attempts at making progress in research during this semester.
Apart from serving as a concise description for you, of where I stand now,
it is probably a medium for venting out my frustrations.

I started out with the goal of reducing instrumentation overhead for
dynamically recording the last use of heap objects. To that end, I thought
must alias analysis would be useful. So I came up with the algorithm and
implemented it in soot (to a good extent). Initially I was complaining
that there arent many must aliases( to be precise, there are not many
local reference variables like a and b intraprocedurally that "must" point
to the same memory location). Later I realized,

fun( x ) { m = new(..); x.f = m; }
fun( a );

b = a.f;

The analysis can detect that b and m are must-alias for this particular
context. I think situations like the above are common, and justifies the
benifits of must alias analysis. Please correct me if I am wrong. But as
always, if it will have any "significant" benifit on reducing the overhead
of instrumentation is unknown.

Then sometime down the line, I became greedy and had this strong urge to
find another application that can use must-alias information in straight
forward manner(in the above I have to write a live variable analysis).
Search for such an application led me "concurrent modification error"
paper first. The problem is about verifying a property of the form
"a.f==b.g", which is obviously a must alias problem. Instead of sticking
to that problem, I looked further (since it did not a interesting class
of bug).

Then I had an (wrong)intuition that must alias analysis can be used to detect
possible null pointer exceptions bugs. The intuition was: to verify that
a stmt will not throw null pointer exception, the object used in the stmt
must be "must-aliased" to NON-NULL. But it is wrong because:

m.f = new(..); n.f = new(..);
if(...) a = m; else a = n;
a.f.fun();

Clearly a.f.fun() cant throw NPE. But after the if stmt, a is not
must-aliased to either m or n because intersection is the confluence operator.
As a result we can not detect that a.f is must-aliased to NON-NULL at
a.f.fun();

The I could see that it is the may alias analysis that we need in this case,
and to check any type state property.

Static checking for bugs is something that I wanted to do. So after the
above brain-storming on type state checking and reading some papers,
which shows a trend towards using invariants and statically checking them,
I decided to switch gear and turn the must alias implementation to may
analysis.

The must analysis used a slightly different abstraction. It did not have
the (ubiquitous) anonymous heap objects, since we are interested in
relationship among variables, not where they are pointing to. So I spent
around a week pondering upon if this abstraction can be useful for may
alias. And I think they are useful, as I was telling Alex last time. It
allows strong updating for stmts like "a.f =...", which, as far as I know,
cannot be done in a flow sensitive analysis, because of the abstract heap
objects. It is a known/open problem that nobody has solved it yet. Or
may be somebody did, but it was not useful. I will leave it for you to
judge!

While exploring on alias analysis for Java, I found Ana Milanova's thesis,
which deals with the general problem of flow analysis (pointer analysis is a
special instance of it, where one is concerned with flow of abstract
heap locations). I find her work interesting because, beyond alias
analysis, any static bug checking system has to have a flow analysis engine
like the one she proposed.

This pretty much sums up what I have done till today. Now I have to decide what
am I going to do in the break and further. But this time, I have decided
not to take the decision myself. Looks like there are plenty of problems,
or are there? But I want you to tell me which one the above, or other than
them, you feel is a "real, interesting & challenging" problem that might
lead to my thesis. Personally, I find static checking for Java is
interesting. But I would refrain from trying to convince you about it!

Last modified 21 November 2004 at 8:52 pm by Saswat Anand