Home Products Consulting Industries News About IBM

JABA - JAvaTM Bytecode Analysis

We have developed algorithms for accurately analyzing control and data flow in Java progams given only their object files. We are thus able to take into account idosynchrocies of the compilation  process in addition to the program logic. These analyses are complicated in object oriented programs by the fact that most method invocations are virtual and hence are dependent upon the actual type, as opposed to the declared type, of method targets.

We build an invocation graph of the code being analyzed.  The graph constructed is path-insensitive, flow-sensitive and context-sensitive.  By path-insensitive we mean that all possible instruction execution paths through each method are considered. For many of the applications we consider, a path-insensitive invocation graph construction algorithm is sufficient.  For security analysis, we do want to consider all paths through all methods included in the graph.  The graph is flow-sensitive for the intraprocedural analysis since we consider the order of execution of the instructions in each method, accounting for local variable "kills" and casting of object references. By context-sensitive we mean that for each call site in a method, the calling context includes the target method(s), and the possible types for the receiver and parameters.

In addition to the graph construction, a data flow analysis is also performed. This is done to propagate object allocation sites and string constants through the graph.  In particular, we refine the notion of a type to incorproate an object's allocation site.  In the case of nested objects (e.g,. collection classes that contain other objects, such as arrays or other collections), we consider the nesting relationship between the objects to further refine the identity of the type.  The net result is a data flow analysis that is less conservative than other analysis techniques.

Unlike local variables, we treat instance and class fields in a flow insensitive manner.  We make a conservative assumption that any allocated object could end up being accessed from multiple threads.  Therefore, during graph construction and data flow analysis, fields accumulate type information. Instance and class fields do not respect field kills.  We mitigate the effect of this flow insensitivity by recording the accumulated type information by  the field's receiver type.

Our algorithms are sufficiently efficient to carry out the entire interprocedural analysis in memory in real time for real world problems. Many programs of realistic size have been analyzed in just a few seconds, while large parts of the Java runtime library were analyzed in several minutes on a 1GHz Intel workstation.

The invocation graph and data flow analyses can subsequently be used as the basis for other analyses; e.g.,  mutability, permission and performance analyses.

You can return to our home page.

For more information, please feel free to contact us.

Privacy

Legal

Contact