[Wala-wala] about building context-sensitive call graph

[Sai Zhang]

Hi-

First, thanks to Steve's reply on my previous post:

https://sourceforge.net/mailarchive/forum.php?thread_name=OF8B4D7A3C.FC4CA418-ON85257930.006489F0-85257930.006555AA%40us.ibm.com&forum_name=wala-wala

Sorry that I did not receive an email notification, until I went to wala-wala's archive to

check the original post. any ideas on receiving posts timely? I used the default setting of the

wala-wala mailing list.

I am a little bit confused on building context-sensitive call graphs using wala for Java.

I followed the available documents in: http://wala.sourceforge.net/wiki/index.php/UserGuide:CallGraph

And try to build a context-sensitive CG using the following code snippet:

String appPath = "path/to/a/set/of/java class files"

AnalysisScope scope = AnalysisScopeReader.makeJavaBinaryAnalysisScope(

             appPath, FileProvider.getFile(CallGraphTestUtil.REGRESSION_EXCLUSIONS));

ClassHierarchy cha = ClassHierarchy.make(scope);

Iterable<Entrypoint> entrypoints = Util.makeMainEntrypoints(scope, cha);

AnalysisOptions options = CallGraphTestUtil.makeAnalysisOptions(scope,entrypoints);

//I want to build a 0-1-CFA CG here

CallGraph cg = CallGraphTestUtil.buildZeroOneContainerCFA(options, new AnalysisCache(), cha, scope);

//However, the context prints out are Everywhere, indicating it

//is a context-insensitive CG

Iterator<CGNode> it = cg.iterator();

while(it.hasNext()) {

    System.out.println(it.next().getContext());

}

I am wondering do I need to redefine the ContextSelector? According to the Wala examples, it seems

to be unnecessary. Or do I build the context-sensitive call graph in a wrong way? or other reasons?

or is the result specific to the tested programs?  (my tested program is appended at the end)

Thanks a lot. any comments are appreciated.

thanks

-Sai

============my tested program===========

class A {

public void foo() { }

}

class B extends A {

    public void foo() { err(); }

    public void err() {}

}

class C extends A {

    public void foo() { }

}

public class ContextSensitiveCG {

public void dispatchCalls(A a) {

a.foo();

}

public void dispatchViaB() {

B b = new B();

dispatchCalls(b);

}

    public void dispatchViaC() {

    C b = new C();

dispatchCalls(b);

}

    

    public void main(String[] args) {

    ContextSensitiveCG icg = new ContextSensitiveCG();

    icg.dispatchViaB();

    icg.dispatchViaC();

    ContextSensitiveCG icg2 = new ContextSensitiveCG();

    icg2.dispatchViaB();

    icg2.dispatchViaC();

    }

}

[Sai Zhang]

I also attempted to modify the graph building method in Wala's built-in example: com.ibm.wala.examples.drivers.PDFCallGraph, by changing line 158 from:

builder = Util.makeZeroCFABuilder(options, new AnalysisCache(), cha, scope);

to

builder = Util.makeZeroOneCFABuilder(options, new AnalysisCache(), cha, scope);

However, the call graph output statistics does not change at all, it shows:

Call graph stats:

  Nodes: 856

  Edges: 1926

  Methods: 816

  Bytecode Bytes: 58247

In both configurations.

So, is there any trick in invoking this context-sensitive call graph construction?

Thanks a lot.

-Sai

[Stephen Fink]

Hi Sai,

Firstly, most people would call our "ZeroOneCFA" a context-insensitive call graph builder, since it's pretty much the "standard" Andersen's analysis.    See http://wala.sourceforge.net/wiki/index.php/UserGuide:PointerAnalysis#ZeroOneContainerCFA

When I run the PDFCallGraph out of the box (on JLex), using ZeroCFA, I get:
Call graph stats:
  Nodes: 1326
  Edges: 3131
  Methods: 1257
  Bytecode Bytes: 79601

When I change line 158 of PDFCallGraph.java to use Util.makeZeroOneCFABuilder, I get:
Call graph stats:
  Nodes: 1326
  Edges: 3131
  Methods: 1257
  Bytecode Bytes: 79601

As you observed, the call graph is unchanged.   This means that using allocation sites rather than types didn't happen to change the precision of the call graph in this case.  

The "most context-sensitive" builder represented in com.ibm.wala.callgraph.impl.Util.java is the zero-one-container builder (see description on wiki) When I change line 158 of PDFCallGraph to use Util.makeZeroOneCFABuilder, I get:
Call graph stats:
  Nodes: 1823
  Edges: 4066
  Methods: 1231
  Bytecode Bytes: 78892

So the container object-sensitivity policy is starting to kick in -- we see more nodes (clones) but fewer distinct methods discovered ... so the call graph was more precise.

Most people would consider a "real" context-sensitive call graph to do something like at least one level of call string context.   In WALA, this is supported by the nCFABuilder.   I don't see any clients in the open-source code base that use this builder -- probably because we would not expect it to scale well on any real program.   Nevertheless, we can try it on JLex.

I created a factory for one-cfa:
 
  /**
   * @param options options that govern call graph construction
   * @param cha governing class hierarchy
   * @param scope representation of the analysis scope
   * @return a 0-CFA Call Graph Builder.
   * @throws IllegalArgumentException if options is null
   */
  public static SSAPropagationCallGraphBuilder makeOneCFABuilder(AnalysisOptions options, AnalysisCache cache,
      IClassHierarchy cha, AnalysisScope scope) {

    if (options == null) {
      throw new IllegalArgumentException("options is null");
    }
    addDefaultSelectors(options, cha);
    addDefaultBypassLogic(options, scope, Util.class.getClassLoader(), cha);

    return new nCFABuilder(1, cha, options, cache, null, null);
  }

Using this factory (after checking in a bug fix to nCFABuilder, which had rotted) I get:

Call graph stats:
  Nodes: 4539
  Edges: 10515
  Methods: 1257
  Bytecode Bytes: 79601

Viva context-sensitivity :)  

SJF
------------------------------------------------------------------------
Stephen Fink
IBM T.J. Watson Research Center
sjf...@us.ibm.com
(914)784-7776

From:	Sai Zhang <szh...@cs.washington.edu>
To:	wala...@lists.sourceforge.net
Date:	10/24/2011 09:12 PM
Subject:	Re: [Wala-wala] about building context-sensitive call graph

---

------------------------------------------------------------------------------
The demand for IT networking professionals continues to grow, and the
demand for specialized networking skills is growing even more rapidly.
Take a complimentary Learning@Cisco Self-Assessment and learn
about Cisco certifications, training, and career opportunities.
http://p.sf.net/sfu/cisco-dev2dev_______________________________________________
Wala-wala mailing list
Wala...@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/wala-wala

[Sai Zhang]

Thanks a lot, Steve, for your answer on how to build a context sensitive call graph.

I tried the sample code, and found it works (at least on small subjects). Just want to confirm

a few points:

(1) When I print out each CGNode, it looks like:

    < Application, Ltest/sensitivecg/B, <init>()V > Context: CallStringContext: [ dispatchViaB@4 ]

     If I did not interpret wrong, CallStringContext represents, for example, <int>() is called from method dispatchViaB at an invocation site: 4.So, the number 4 does not mean line number, of other program information. It merely represents a unique call site (inside dispatchViaB method) added by Wala, right? and there is no relationship between each call sites.

(2) As you mentioned before, 0-1-container CFA uses container object-sensitivity to refine call graph. In other words, the object-sensitivity is *ONLY* for any allocation sites in collection objects: the allocation site is named by a tuple of allocation sites extending to the outermost enclosing collection allocation.

In my understanding, the following (1) (2) allocation sites will be distinguished, right?

foo() {

    List l1 = new LinkedList();

    l1.add(new Object());    //(1)

    List l2 = new LinkedList();

    l2.add(new Object());   //(2)

//so that the analysis can conclude l1, and l2 are disjointed!

}

The object-sensitivity is NOT used for any other call sites un-related to collection objects, 

e.g., it will not distinguish call site (3) and (4) in the following example, right? (which 1-CFA will distinguish)

foo() {

   Bar bar1 = new Bar();

   Bar bar2 = new Bar();

   bar1.bar();   //(3)

   bar2.bar();   //(4)

}

Another related question, is the object-sensitive policy adapted in the built-in pointer-to analysis in Wala?

Thanks a lot.

-Sai

[Yufeng]

Hi,

I have a question on the context sensitive call graph builder.

Now I can use the bounded call string context sensitive call graph builder to build call graph with calls strings as the context.

But when I fetch the pointer analysis results, I find that the all the PointerKey point to the same InstanceKey.

I don't know why.

Is there any other configurations I need to set when I use the context sensitive call graph?

Thank you very much.

Yufeng
在 2011年10月25日星期二UTC+8上午2时27分42秒，Sai Zhang写道：

[Yufeng]

Hi,

I have a question on the context sensitive call graph builder.

Now I can use the bounded call string context sensitive call graph builder to build call graph with calls strings as the context.

But when I fetch the pointer analysis results, I find that the all the PointerKey point to the same InstanceKey.

I don't know why.

Is there any other configurations I need to set when I use the context sensitive call graph?

Thank you very much.

Yufeng

在 2011年10月25日星期二UTC+8上午2时27分42秒，Sai Zhang写道：

Hi-