About Indus
Indus is an effort to provide a collection of program analyses and transformations implemented in Java to customize and adapt Java programs. It is intended to serve as an umbrella for
- static analyses such as points-to analysis, escape analysis, and dependence analyses,
- transformations such as program slicing and program specialization via partial evaluation, and
- any software module that delivers the analyses/transformations into a particular application such as Bandera or platform such as Eclipse.
News
Starting from v0.8.3.6, the source code from Indus project is available under Eclipse Public License (EPL).
Overview
At present, there are 3 modules that are part of Indus. More modules are expected to be added over the course of time. We provide an overview of the intent of each module that are available at present.
Indus is a module that houses the implementation pertaining to algorithms and data structures common to analyses and transformations that are part of or are planned to be part of Indus. This module contains interface definition common to most analyses and transformations to provide a framework in which various implementations of analyses/transformations can be combined to form systems with ease. Hence, this module is updated when a new sort of analysis/transformation is implemented as a module in Indus. However, a new implementation of an analysis/transformation will not affect this module as it will implement an existing interface.
StaticAnalyses module is intended to be the collection of static analyses such as object-flow analysis, escape analysis, and dependence analyses. The analyses in this module use common interfaces and implementations from Indus and may define/provide new interfaces/implementations specific to new analyses. Existing analyses are mentioned below.
Object-flow Analysis (OFA) is a points-to analysis for Java. Each allocation site in the analyzed system is treated as an abstract object and its flow through the system is tracked to infer the possible types an receiver at a call-site to enable the construction of a precise call-graph. The precision of the analysis can be varied in terms of flow-sensitiveness for method local variables and object-sensitiveness for instance fields.
Escape Analysis is an extended implementation of the escape analysis proposed by Ruf for the purpose of pruning interference and ready dependence edges. The extensions are in the form of seamless addition of value equivalence to the analysis to improve the detection of conflicting field reads/writes occurring in different threads beyond just using type equality of the primaries of the access expressions. The analysis also uses object-flow information orthogonally to further improve precision.
Dependence Analyses is a collection of dependence analyses: entry-based control, exit-based control, identifier-based data, reference-based data, interference, ready, synchronization, and divergence, required by analyses/transformations such program slicing and partial evaluation. Interference and Ready dependence analyses depend on the previous escape analysis while reference-based data and synchronization dependence analyses depend on object-flow information and the calculated call-graph information. Some analyses have varying levels of precision which can be varied via a well defined interface.
Side-Effect Analysis provides method-level side-effect information. The user can query if any of the arguments/parameters to a call-site/method will be affected either directly (immediate members) or indirectly (recursively reachable members). Similarly, the user can provide a data access path rooted at arguments/parameters to a call-site/method and query if end point of the data access path is affected by the call/method.
Monitor Anlaysis is a simple analysis that provides monitor/lock graph information for the given system.
Safe Lock Analysis is an analysis that conservatively discovers if a lock (monitors) will not be held indefinitely. This information is used in conjunction with temporal dependences steming for Object.wait() and Object.notify()/ Object.notifyAll() as it is done in ready dependence.
Atomicity Analysis provides information about atomicity in the given system. Current implementation relies on escape analysis to predict if a statement can be executed atomically. This information is used to detect atomic region of codes. This information is useful in applications such as model checking to reduce the the size of the state space, hence, improve performance.
Some analyses may be large enough to constitute module on their own and such analyses will be hosted as different modules in Indus rather than being consumed by this module.
Java Program Slicer module contains the core implementation of Java program slicer along with adapters that deliver the slicer in other applications such as Bandera and Eclipse. The implementation is architected as a library rather than as an application to facilitate the reuse of it's subparts. The core is independent of the application; Each application's requirement of the slice can be satisfied by coding up implementations of post-processing interfaces and hooking in these implementations to form a customized slicer.
This module relies heavily on the information provided by dependence analyses and also the call-graph provided by OFA via well-defined interfaces that enables external implementations to be used for slicing.
This implementation of slicer is delivered to Eclipse with an intuitive UI via Kaveri plugin.
Features:
Backward and Forward slice generation. Complete slices (union of backward and forward slices starting from the same slice criteria) can be generated.
Support to residualize (appropriate) slices into executable class files.
Support for context-sensitive slicing via context rich slice criteria specification.
Support to restrict the slice to a particular part of the system by scope specifications.
Support to serialize slice criteria, slicer configurations, and slices.
All modules in Indus project work on Jimple, an intermediate representation of Java, provided by Soot toolkit from Sable group in McGill University. Each module in the project will be exposed as one or more Eclipse plugins if the provided information is useful to the user and amenable for user consumption via a graphical user interface.
Software Engineering Philosophy
Each module in this project will provide just the required functionality via well-defined interfaces that can be implemented to assemble a customized system with suitable extensions that fulfill specific requirement. As the interface is clearly separated from the implementation, any external implementation that provides the required interface can be seamlessly used with modules from this project.
Background
The implementation of most of the analyses was driven by the requirements of Java program slicer required by Bandera. However, as the program slicer could be used outside Bandera and the analyses could be used to enable other transformations such as program specialization via partial evaluation, we moved the analyses and transformations into a new project called Indus.
Funding
The development of Indus has been funded through a variety of sources including U.S. Army Research Office (DAAD190110564), DARPA/IXO's PCES program (AFRL Contract F33615-00-C-3044), Air Force Office of Scientific Research (FA9550-006-1-0223), NSF (CCF-0429149, CRI-0454348, CCF-04444167), Lockheed Martin, and >Rockwell Collins.