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

[Stephen F. <sj...@us...>]

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
sj...@us...
(914)784-7776




From:
Sai Zhang <sz...@cs...>
To:
wal...@li...
Date:
10/24/2011 09:12 PM
Subject:
Re: [Wala-wala] about building context-sensitive call graph



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

On Mon, Oct 24, 2011 at 11:27 AM, Sai Zhang <sz...@cs...> 
wrote:
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();
    }
}
------------------------------------------------------------------------------
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
Wal...@li...
https://lists.sourceforge.net/lists/listinfo/wala-wala