DOOP

Project Site

This site is maintained infrequently. The best resource for Doop is currently the project’s source repo.

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.

News

Tutorial Survey
“Pointer Analysis” (Foundations and Trends in PL).
APLAS 2015
“More Sound Static Handling of Java Reflection” Asian Symposium on Programming Languages and Systems (APLAS’15), November 2015.
PLDI 2014
“Introspective Analysis: Context Sensitivity, Across the Board” Programming Language Design and Implementation (PLDI’14), June 2014.
OOPSLA 2013
“Set-Based Pre-Processing for Points-To Analysis” Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA’13), October 2013.
PLDI 2013
“Hybrid Context Sensitivity for Points-To Analysis” Programming Language Design and Implementation (PLDI’13), June 2013.

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.newInstanceMethod.invokeConstructor.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.