Introduction

Versatile. Doop is a framework for pointer, or points-to, analysis of Java programs. Doop implements a range of algorithms, including context insensitive, call-site sensitive, and object-sensitive analyses, all specified modularly as variations on a common code base.

Fast. Compared to alternative context-sensitive pointer analysis implementations (such as Paddle) Doop is much faster, and scales better. Also, with comparable context-sensitivity features, Doop is more precise in handling some Java features (for example exceptions) than alternatives.

Declarative. Doop builds on the idea of specifying pointer analysis algorithms declaratively, using Datalog: a logic-based language for defining (recursive) relations. Doop carries the declarative approach further than past work (such as bddbddb) by describing the full end-to-end analysis in Datalog and optimizing aggressively through exposition of the representation of relations (for example indexing) to the Datalog language level. Doop uses the Datalog dialect and engine of LogicBlox.

News

OOPSLA 2009

Presentation of paper "Strictly Declarative Specification of Sophisticated Points-to Analyses" at the 24th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2009), October 2009, Orlando, Florida, USA.

ISSTA 2009

Presentation of paper "Exception and Points-to Analysis: Better Together" at the International Symposium on Software Testing and Analysis (ISSTA 2009), July 2009, Chicago, Illinois, USA.

Features

Major features of Doop are:

• Doop supports a range different kinds of context-sensitive pointer analysis (for example call-site-sensitive, object-sensitive, and thread-sensitive). Most of the logic of Doop is entirely generic, so new combinations of context-sensitivity can easily be defined.
• Doop supports a context-sensitive heap abstraction (also known as heap cloning or heap specialization). A context-sensitive heap abstraction can be combined with any other context-sensitive analysis.
• Doop implements subset-based (or inclusion-based) analyses, which preserve the directionality of assignments (unlike equivalence-based analyses).
• Doop produces a precise callgraph by implementing fully on-the-fly callgraph discovery. This means that the pointer information collected by Doop is used to determine callgraph edges and vice versa.
• Doop implements a precise exception analysis by determining for every method which exceptions it may throw. Variables for caught exceptions only point to exception objects that may be thrown in the scope of the try block.
• Doop implements a sophisticated reflection analysis. Doop uses distinct representations of instances of java.lang.Class for every class in the analyzed program. This reduces the number of human configuration points, solves more reflection scenarios automatically (e.g. Class.newInstance, Method.invoke, Constructor.newInstance), and improves precision.
• Doop implements field-sensitive analyses. This means that Doop distinguishes different fields of an object. The analyses are, however, array-element insensitive, which means that Doop does not consider different indexes of an array object as different variables.
• Doop implements flow-insensitive pointer analyses. Doop can achieve some of the benefits of flow-sensitivity for local variables, by applying the analysis on the static single assignment (SSA) form of the program.
• Doop emulates the behavior of some common native methods (such as privileged actions). More will be added in the near future!
• Doop emulates the JVM as precisely as possible. For example, Doop fully supports java.lang.ref.Reference.
• Doop's analyses take type information into account: points-to facts are not propagated if they would violate the JVM type system.
• The analyses of Doop are continuously tested against an extensive testsuite.

Together, these features make Doop by far the most sophisticated and reliable points-to analysis implementation for Java.