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

[Sai Z. <sz...@cs...>]

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


On Mon, Oct 24, 2011 at 6:11 PM, Sai Zhang <sz...@cs...> wrote:

> 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();
>>     }
>> }
>>
>
>