19

Can somebody point me to a framework or an implementation of alias analysis for Java. I looked at the asm framework but it only provides data flow analysis and control flow analysis.

Update: Just curious but does anyone know if Findbugs does alias analysis?

Ross Ridge
  • 38,414
  • 7
  • 81
  • 112
pdeva
  • 43,605
  • 46
  • 133
  • 171

5 Answers5

13

I know of three open-source program analysis frameworks with an alias analysis for Java:

  1. WALA (disclaimer: I'm a WALA maintainer).
  2. Soot
  3. Chord

Note that what is actually implemented in these frameworks is a points-to analysis, with which one can determine possible aliasing. Some details on WALA's pointer analyses are available at http://wala.sourceforge.net/wiki/index.php/UserGuide:PointerAnalysis.

Ben Holland
  • 2,309
  • 4
  • 34
  • 50
msridhar
  • 2,846
  • 4
  • 22
  • 23
  • curious how Wala differs from Soot and Chord – pdeva Jan 06 '12 at 08:03
  • 1
    @pdeva Soot can generate optimized bytecodes, whereas WALA has no code generation. WALA has good infrastructure for inter-procedural dataflow analysis, which I'm not sure is in Soot. I don't really know Chord, so I'm not sure how it differs. If you have a specific analysis you'd like to implement in WALA and have questions, you can email the WALA mailing list or me for help. – msridhar Jan 12 '12 at 17:39
  • It looks to me like WALA uses an SSA format as its program representation whereas Soots main format is Jimple which is a non-SSA three address format (but there is an alternative SSA format available). – Lii Dec 01 '13 at 11:22
9

I think this is a pretty important question as points-to analysis/alias analysis is a fundamental piece of most program analysis tasks. So here is my attempt at a more complete listing of frameworks for Java. Some are more complete than others and this is an active research area so I may have missed a few. It's hard to say which implementation is the best, but DOOP and SPARK seem to popular choices among academics.

  1. Soot (SPARK)
    • Released before PADDLE, but still actively used by the Soot community. SPARK is fully integrated into Soot and performs well for context-insensitive analysis.
    • Papers: [1]
    • Resources: [1], [2]
  2. Soot (PADDLE)
    • Released in 2005-2008. Soot includes the frontend interface to PADDLE, but not the backend. The project is no longer maintained (I could not get it to run with the latest releases of Soot). Supported BDD based set representation and multiple abstractions of context-sensitivity for analysis in Soot.
    • Papers: [1], [2], [3], [4]
    • Resources: [1]
  3. bddbddb
    • A declarative Datalog based specification that transforms analysis to efficient BDD based operations.
    • Papers: [1], [2]
    • Resources: [1]
  4. CHORD
    • CHORD offers several standard points-to analysis options for context and context-insensitive analysis.
    • Resources: [1], [2]
  5. WALA
    • WALA has an implementation of the Interprocedural Distributive Environment (IDE) data flow algorithm.
    • Papers: [1]
    • Resources: [1], [2]
  6. DOOP
    • A declarative Datalog based implementation released under the MIT License, but requires the proprietary LogicBlox Datalog framework. I believe this project currently holds the claim for being the fastest and most versatile framework available. It is also a very active project and becoming well adopted in the research community.
    • Papers: [1], [2], [3], [4], [5]
    • Resources: [1], [2], [3], [4]
  7. Atlas (Points-to Toolbox)
    • Released in 2016 by myself. Simple Andersen style points-to analysis for Atlas.
    • Points-To Toolbox released under MIT License, but requires proprietary Atlas framework.
    • Resources: [1]
  8. SCUBA
    • A constraint based solver for context sensitive points-to analysis.
    • Papers: [1]

Bonus supplementary tools for dealing with third party libraries.

  1. Averroes
    • Generates Java bytecode summaries of third party libraries.
    • Papers: [1], [2]
    • Resources: [1]
  2. Flow Miner
    • Generates XML summaries of flows and properties of third party libraries.
    • Papers: [1]
    • Resources: [1]
Ben Holland
  • 2,309
  • 4
  • 34
  • 50
1

There's doop which I saw at an OOPSLA, but I don't know what state it is in.

I know of no other implementations, just a ton of papers.

Pascal Cuoq
  • 79,187
  • 7
  • 161
  • 281
Dave Newton
  • 158,873
  • 26
  • 254
  • 302
  • DOOP appears to be one of the state-of-art solutions at this time. I'll add a link to their 2015 PLDI conference tutorial materials (https://plast-lab.github.io/doop-pldi15-tutorial/), which contains some setup advice and examples. I was able to successfully set up DOOP and experiment a bit within a day. – Ben Holland Dec 17 '15 at 21:58
1

One possibility is Sawja, implemented in OCaml. It doesn't seem to contain an alias analysis yet, but it offers building blocks to make one.

Regarding your update, Bill Pugh's Google talk makes it sound like Findbugs looks for specific patterns in the code without resolving pointers. Of course, that was in 2006, so who knows what has happened since... Time flies fast.

Pascal Cuoq
  • 79,187
  • 7
  • 161
  • 281
0

Our DMS Software Reengineering Toolkit and its Java Front End could be used to build this.

DMS provide general purpose parsing, tree/symbol table building, and flow analysis (control flow, data flow, points-to, call graph, ...) capabilities. By connecting a front end to this machinery, one can implement langauge-specific analyses without having to build most of the machinery from scratch. These have been used to do global points-to analyses and call graph construction on very big C applications, and control flow analysis on C++.

For Java, we have method-local control flow implemented and some aspects of local data flow. To do good alias analysis, you'd need to fill out call graph construction.

Ira Baxter
  • 93,541
  • 22
  • 172
  • 341