Points-to Algorithms

  • CHA: Class Hierarchy Analysis - it assumes that all reference variables can point to any object of the correct type
  • geomPTA:
  • I heard that it is buggy. Is it?


  • Scene:
    • application classes (to be analyzed)
    • the main class (entry point)
    • points-to info
    • call-graphs
  • Points-to analysis: SPARK and Paddle
  • A Unit is a statement
    • Get values used in it: getUseBoxes
    • Get valued defined in it: getDefBoxes
    • Get units jumping to it: getBoxesPointingToThis
    • Get units it is jumping to: getUnitBoxes
  • Boxes is a reference
    • UnitBoxes: code, branching
    • ValueBoxes
  • Four IR are parallel, having different characteristics:
    • Baf: bytecode similar
    • Jimple: 3-address, semi-like Java, applicable to most analysis
    • Shimple: SSA form, simplifies analysis
    • Grimp: more human-readable than Jimple
  • Inter-procedural analysis: “-w” whole-program analysis switch
    • cg phase
    • wjtp phase: whole jimple transformation pack
    • wjap
    • “-W” switch will further add whole-program optimizations:
      • wjop
    • What is wjpp? Pre-processing pack
  • List help for a pack: java soot.Main -ph PACK
  • -include-all All classes referred to by any argument classes will be treated as application classes.
  • -f J to produce a Jimple file
  • The data-flow framework
    • Backwards or forwards flow analysis?
    • Branching or not?
    • May or must analysis?
    • Soot data-flow framework is designed to handle any form of cfg implementing the interface soot.toolkits.graph.DirectedGraph
  • Soot provides four implementations of flow sets: ArraySparseSet, ArrayPacked-Set, ToppedSet and DataFlowSet. We will describe only the first three.
    • ArraySparseSet is an unbounded flow set. The set is represented as an array of references
    • ArrayPackedSet is a bounded flow set. Requires that the programmer provides a FlowUniverse object
    • ToppedSet wraps another flow set (bounded or not) adding information regarding whether it is the top set (⊤) of the lattice.
  • CFG
    • BriefUnitGraph is very simple in the sense that it doesn’t have edges representing control flow due to exceptions being thrown.
    • ExceptionalUnitGraph includes edges from throw clauses to their handler (catch block, referred to in Soot as Trap), that is if the trap is local to the method body.
    • TrapUnitGraph like ExceptionalUnitGraph, takes into account exceptions that might be thrown.
  • The call graph has methods to query for the edges coming into a method, edges coming out of method and edges coming from a particular statement (edgesInto(method), edgesOutOf(method) and edgesOutOf(statement), respectively
  • IR for Abstracting CFG:
  • Implement the analysis interface:




Using Soot to instrument a class file





Android (Investigative) Tools Mobile Security Alerts

Datasets: M0Droid ContagioDump



Lecture Slides: Taint Analysis

VASCO: Capable of encoding more problem than IFDS/IDE.