[05 Nov]

Null pointer Exception:
1- If we model as NULL as a global object: Then at a point, a.f or a.fun(), if a is a mustalias to NULL, then we yell "bug!". If a isnt a must alias to NULL, then we cant say anything – there may be a bug or there may not be. So what are the case when we can detect bug? If a variable that is referenced is NULL on all paths from entry to that point! Not much credit catching these bugs, becuase if there is a test case that executes this statement, will catch the bug.

2- Alternative solution: We model NOT-NULL as a global object. When we see, a = new () or a = b and b is must aliases to NOT-NULL, we note that a is must-aliased to NOT-NULL after that statement.

So at a point of reference of a, we have a must-aliased to NOT-NULL. We can completely rule out the possibility of NullPointerException for that reference. Note, this is much better (much difficult to infer otherwise) than what we say above: there will be null pointer exception on every path to here.

And other hand, if a isnt must-aliased to NOT-NULL, it means there "may" be a path where a is NULL. I say "may be" because, they may not be must-aliased due to imprecision of may-analysis that is used for side-effect analysis. Example:

value1 = null;
hashMap.put( key1, value1 );
value2 = hashMap.get( key2 ); // possible may-aliasing <value2, value1>. I would call it "implicit aliasing"
value2.fun();                 
// Due to the fact that value1 and value2 are may-alias and value1 is not must-aliased to NOT-NULL, 
// value2 cannot be must-aliased to NOT-NULL

Here from the fact that value2 is not must-aliased to NOT-NULL, we cant say for sure there will be a null pointer exception. But consider the following case,

x = null;
if(...)
  y = x;
else
  y = new ...;
y.fun();        
// y is not must-aliased to NON-NULL. But it isnt because of imprecision of may-analysis. 
// It is because there is one path on which y is aliased to NULL.
// So here that is a strong possibility that there will be a null pointer exception.
// Note: This is still a possibility, becuase there may not be a bug if it happens to be a infeasible path

So it is not very useful for the must alias to say "a is not must aliased to NON-NULL", it must say if it is due to imprecision(implicit aliasing) or simply because there is one path on which a is NULL. One naive way to extract this information is to, do the analysis twice: once with side-effect analysis (will have implicit aliases) and once with without side-effect analysis (which is not sound). Then comparing the results, we can infer why "a is not must aliased to NON-NULL?"

Beyond Null pointer Exception:
At a program point, file.read(), can we say that file is open on all paths to this point using must alias analysis. If the file was un-opened, this statement would throw an exception. Obviously we can. We will model OPENED as a global object and before any read/write statement we must have the file must-aliased to OPENED. Similarly we can check other rules about correct API usage.

In sum, must alias analysis can used for type-state analysis. NON-NULL, OPENED are all typestates. We can check if an object is in the right typestate on all paths to a particular program point!

An example of C++ typestate checking system is ESP from Microsoft research. For java there isnt one like ESP. There is TVLA from Israel, but that is shape analysis – more powerful, more unscalable. More discussion in [02 Nov].

Last modified 5 November 2004 at 12:04 pm by Saswat Anand