Static and Dynamic Analysis of Call Chains in Java

1. Abstract

This work present a parameterized framework for static and dynamic analysis of call chain in java components.

1. Introduction

• The designers of a call chain analysis have to address several important issues;
  • How to ensure that the analysis reports few infeasible chains?
  • The results should represent the set of call chains in a compact manner;
  • The analysis should employ mechanisms for controlling the number of reported chains;

• Different levels of call edge granularity should be supported (an edge may either represent a relationship "invokes ", or a finer-grain relationship call site inside invokes );
  • A dynamic call chain analysis takes as input a set of call chains computed by some static call chain analysis;
    • It should instrument only the component of interest, and not other components that interact with it;
    • It should identify and ignore run-time events that are not relevant to the given static call chains;
    • It should handle correctly the potential interactions between the instrumented and the non-instrumented parts of the program.
  • Analysis framework
    • This work is designed based on a data structure that is generalized form of a calling context tree;
    • 1) call graph construction algorithm; 2) granularity of call graph edges; 3) mechanism for choosing "interesting"chains, and (4) handling of recursion.
    • This parameterization allows various uses of the approach in software tools;
    • This empirical study addresses two key questions:
      • What exactly is the imprecision in the chains computed using popular class analyses such as Rapid Type Analysis and Andersen-style points-to analysis?
      • What are the limits of call chain precision for all class analyses- that is, how much call chain infeasibility would remain even if the "most powerful" class analysis were available.

1. Static Analysis

• Each non-abstract method in the component is represented by a graph node.
• Call graphs may represent different kinds of relationships:
  • method invokes method ;
  • call site inside invokes ;
  • call site inside invokes on an instance of .
  • Our static and dynamic analyses are designed for the last choice from the list; therefore, we assume that each call graph edge is labeled with a pair of a call site and a receiver class.
  • Artificial node caller is an abstraction of all external callers of the component, and artificial node callee is an abstraction of any external code that is called by the component.
  • Calling Context Trees
    • The root of the tree represents the starting point of the program, and each tree node n represents a particular call chain containing n and all of its ancestors in the tree.
    • We associate a separate calling context tree with each entry method in the component. In the component-level call graph, an entry method has an incoming artificial edge which shows that the method may be called by non-component code.

• Tree Construction

  

  • label(e) is used to denote the pair of a call site and a receiver class associated with call graph edge .
    • createNewChild (t, m‘, label (e)): creates a new tree node attached to , and the link is tagged as . <//build the link between to t, m is entry method which is associated with t>
  • To avoid infeasible chain, this approach use a simple test: for any call through this, the receiver class associated with e should match the receiver class associated with the last edge in chain.
  • use-backedges: creating a back-edge from a tree node to some ancestor of that node. In addition, if use-backedges is true, our analysis uses the same approach (lines 7–9). The call to createNewBackedge at line 8 traverses the ancestors of t, finds the ancestor node t‘that corresponds to m‘, and creates a backedge from t to t‘labeled with label(e). If the flag is false, recursion is unrolled until the stopping criterion indicates that no further unrolling is necessary.

1. Dynamic Analysis

• Instrumentation
  • (1) We need instrumentation at the beginning and at the returns of each entry method. This instrumentation creates run-time events of the form entered (m) and exited (m), where m is an entry method.
  • (2) We need instrumentation immediately before and immediately after certain call sites. <!-- for a call site c, the generated run-time events are before(c, X) and after(c, X), where X is the class of the receiver object.>
  • (3) If c is a call to a static method, we use X = none. Call site instrumentation is needed only for call sites that correspond to edges in the input forest, and for call sites that have outgoing call edges to non-component code.
  • (4)