Re: [Wala-wala] The use of DFSPathFinder on InterprocedureCFG

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

Hi,
     Just elaborate a bit, what I did is 

1./ Create a CallGraph with com.ibm.wala.ipa.callgraph.impl.
makeVanillaZeroOneCFABuilder

2../ Create a InterproceduralCFG using CallGraph created in step 1

3./ Then use DSFPathFinder to search thru this graph in step 2.

    So after step 1, 2, should I expect a context sensitive InterprocedureCFG or I need to do extra step??

thx
dongyu

--- On Tue, 10/28/08, dongyu sun <sun...@ya...> wrote:

From: dongyu sun <sun...@ya...>
Subject: Re: [Wala-wala] The use of DFSPathFinder on InterprocedureCFG
To: "WALA discussion and Q&A" <wal...@li...>
Cc: "Tan Hee Beng Kuan" <ib...@nt...>
Date: Tuesday, October 28, 2008, 3:05 AM

thx stephen. But when I construct the CallGraph, I create using 
Util.makeVanillaZeroOneCFABuilder

Should it be already a context sensitive CFA??

If above does not meant to create the context sensitive InterprcoCFG, how to build one? As in our program analysis, I need to analze how different variable are defined and used as such a context sensitive InterprocCfa is needed...

thanks
donny

--- On Mon, 10/27/08, Stephen Fink <sj...@us...> wrote:

From: Stephen Fink <sj...@us...>
Subject: Re: [Wala-wala] The use of DFSPathFinder on InterprocedureCFG
To: "WALA discussion and Q&A" <wal...@li...>
Date: Monday, October 27, 2008, 3:48 PM

I think the issue here is that the interprocedural CFG is not context-sensitive, so you are finding a path which is infeasible according to matched call-return pairs.  Specifically, you are finding a path in the IPCFG as follows: 

1) sayHello calls say1 
2) say1 calls println 
3) println returns to the the 'else' branch of sayHello 
4) sayHello calls say2 

which is a path in the IPCFG, but infeasible since the call 2) is unmatched with the return 3). 

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

dongyu sun <sun...@ya...> 
10/27/2008 02:06 PM 

Please respond to
WALA discussion and Q&A <wal...@li...>

To
wal...@li... 

cc

Subject
[Wala-wala] The use of DFSPathFinder on InterprocedureCFG

Hi, 

       I am testing the DFSPathFinder on a InterprocedureCFG. I have a simple test program like following 

public class HelloWorld { 
/** 
* @param args 
*/ 
public static void main(String[] args) { 
// TODO Auto-generated method stub 
HelloWorld h=new HelloWorld(); 
int i[]=new int[0]; 
int i2=i.length; 
int i3=i2; 
int i4=i3; 
i=null; 
h.sayHello("hi "); 
} 
public void sayHello(String greeting) 
{ 
TestClass testClas=new TestClass(); 
String test="test"; 
if(greeting =="") 
{ 
System.out.println(greeting); 
// testClas.method1_1(greeting); 
say1(); 
} 
else 
{ 
System.out.println(test); 
// testClas.method2(test); 
say2(); 
} 
} 
void say1() 
{ 
System.out.println("say1()"); 
} 
void say2() 
{ 
System.out.println("say2()"); 
} 
} 

I first constructed the InterprocedureCFG from the CallGraph, then I use the DSFPathFinder on this InterprocedureCFG to try to find any path between the call to say1() to the call to say2(). 
In above helloWorld class, as this two function call are on the two branches of the if statement, I didn't expect any path to exist between them, but suprisingly I got one path like following when run the DSFPathFinder. 

the line with issBlk===>.. is produced by printing the toString() output of each of the 
BasicBlockInContext<ISSABasicBlock> 

the line witn ins (...) is the toString() output of each instruction in each of the 
BasicBlockInContext<ISSABasicBlock>. the number in the bracket is the line number in the source code. 
--------------------------------------------------------------------- 

issBlk===>BB[SSA:12..13]5 - simple.HelloWorld.sayHello(Ljava/lang/String;)V 
ins ( 29 ): invokevirtual < Application, Lsimple/HelloWorld, say1()V > 1 @25 exception:13 
def Value String : v13 
use Value String : v1 
loca name ( this ) 
issBlk===>BB[SSA:-1..-2]0 - simple.HelloWorld.say1()V 
issBlk===>BB[SSA:0..2]1 - simple.HelloWorld.say1()V 
ins ( 43 ): 3 = getstatic < Application, Ljava/lang/System, out, <Application,Ljava/io/PrintStream> > 
def Value String : v3 
ins ( 43 ): invokevirtual < Application, Ljava/io/PrintStream, println(Ljava/lang/String;)V > 3,4 @5 exception:5 
def Value String : v5 
use Value String : v3 
use Value String : v4:#say1() 
issBlk===>BB[SSA:-1..-2]0 - java.io.PrintStream.println(Ljava/lang/String;)V 
issBlk===>BB[SSA:0..3]1 - java.io.PrintStream.println(Ljava/lang/String;)V 
issBlk===>BB[SSA:4..6]2 - java.io.PrintStream.println(Ljava/lang/String;)V 
issBlk===>BB[SSA:7..8]3 - java.io.PrintStream.println(Ljava/lang/String;)V 
issBlk===>BB[SSA:9..10]4 - java.io.PrintStream.println(Ljava/lang/String;)V 
issBlk===>BB[SSA:11..11]5 - java.io.PrintStream.println(Ljava/lang/String;)V 
issBlk===>BB[SSA:17..17]8 - java.io.PrintStream.println(Ljava/lang/String;)V 
issBlk===>BB[SSA:-1..-2]9 - java.io.PrintStream.println(Ljava/lang/String;)V 
issBlk===>BB[SSA:18..19]8 - simple.HelloWorld.sayHello(Ljava/lang/String;)V 
ins ( 35 ): invokevirtual < Application, Lsimple/HelloWorld, say2()V > 1 @39 exception:10 
def Value String : v10 
use Value String : v1 
loca name ( this ) 

It seems that the path is from the call to say1() go into the function definition of say(), then come out and jump on to the call to say2().. Is this path right in a CFG? 

thanks 
dongyu
-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/_______________________________________________
Wala-wala mailing list
Wal...@li...
https://lists.sourceforge.net/lists/listinfo/wala-wala

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's
challenge
Build the coolest Linux based applications with Moblin SDK & win great
prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/_______________________________________________
Wala-wala mailing list
Wal...@li...
https://lists.sourceforge.net/lists/listinfo/wala-wala