[Soot-list] Spark and aliasing analysis

Thu May 10 09:46:18 EDT 2012

Thanks for your help.

I tested paddle, cs-demand and geom-pta.

1) Paddle:

It used the following settings / phase options:

             Options.v().setPhaseOption("cg","implicit-entry:false");

             Options.v().setPhaseOption("cg.paddle","enabled:true");

             Options.v().setPhaseOption("cg.paddle","bdd:true");

             Options.v().setPhaseOption("cg.paddle","backend:buddy");

             Options.v().setPhaseOption("cg.paddle","context:kcfa");

             Options.v().setPhaseOption("cg.paddle","k:3");

Options.v().setPhaseOption("cg.paddle","string-constants:true");          

             Options.v().setPhaseOption("cg.paddle","context-heap:true");

It works fine for the following tests: o5,o6,o7 and o8 are not aliases any
more.

             Object o5 = new Object();

             Object o6 = new Object();

             Object o7 = k1.getNewO();

             Object o8 = k2.getNewO();

But in the next example, I am not sure, if the result is correct / precise. 

             Integer i = new Integer(5);

             String iString = i.toString(); 

             Integer j = new Integer(5);

             String jString = j.toString();

Paddle says, the iString and jString have an non empty intersection. Hence,
they may point to the same object. I do not know, if this appends because
"k:3" is not powerful enough or because they may point to the same string
constant. What would be your explanation?

Here is the toString implementation of an Integer:

  738       public String toString() {
  739           return toString(value);
  740       }

  327       public static String toString(int i) {

  328           if (i == Integer.MIN_VALUE)

  329               return "-2147483648";

  330           int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);

  331           char[] buf = new char[size];

  332           getChars(i, size, buf);

  333           return new String(0, size, buf);

  334       }

I tried another paddle configuration, for example 

Options.v().setPhaseOption("cg.paddle","conf:ofcg-context-aot");

but then I get the error *1 at line:

                PackManager.v().getPack("cg").apply();

Did I forgot something?

2) cs-demand:

My setting:

soot.options.Options.v().setPhaseOption("cg.spark","enabled:true");

soot.options.Options.v().setPhaseOption("cg.spark","cs-demand:true");

But only the method
<http://www.sable.mcgill.ca/soot/doc/soot/jimple/spark/ondemand/DemandCSPoin
tsTo.html#reachingObjects%28soot.Local%29> reachingObjects(
<http://www.sable.mcgill.ca/soot/doc/soot/Local.html> Local l)is
implemented. Thus, I cannot compare fields and local variables. I need also
methods like
<http://www.sable.mcgill.ca/soot/doc/soot/jimple/spark/ondemand/DemandCSPoin
tsTo.html#reachingObjects%28soot.PointsToSet,%20soot.SootField%29>
reachingObjects( <http://www.sable.mcgill.ca/soot/doc/soot/PointsToSet.html>
PointsToSet s,  <http://www.sable.mcgill.ca/soot/doc/soot/SootField.html>
SootField f). 

Is an implementation of these methods in process?

3) geom-pta:

I think, I did not find the best setting / option combination, because the
results are not better than paddle.

             Options.v().setPhaseOption("cg","implicit-entry:false");

             Options.v().setPhaseOption("cg.spark","enabled:true");

             Options.v().setPhaseOption("cg.spark","string-constants:true");

             Options.v().setPhaseOption("cg.spark","geom-pta:true");

             Options.v().setPhaseOption("cg.spark","geom-runs:5");

The analysis says, that o7 and o8 may point to the same object:

             ..     

Object o7 = k1.getNewO();

                    Object o8 = k2.getNewO();

                               ..

public Object getNewO() {

                    return new Object();

              }

How can I get  a more precise result using geom-pta?

Thanks for reading my long eMail ;)

Please let me know, if you have any ideas, how I can improve my results.

Best regards,

                Florian

*1)

java.lang.ClassCastException: soot.util.IntegerNumberer cannot be cast to
soot.jimple.paddle.ContextStringNumberer

                at
soot.jimple.paddle.BDDKCFAStaticContextManager.shiftWidth(BDDKCFAStaticConte
xtManager.java:24)

                at
soot.jimple.paddle.BDDKCFAStaticContextManager.update(BDDKCFAStaticContextMa
nager.java:31)

                at
soot.jimple.paddle.DependencyManager.update(DependencyManager.java:76)

                at soot.jimple.paddle.OFCGScene.solve(OFCGScene.java:168)

                at
soot.jimple.paddle.OFCGContextAOTConfig.solve(OFCGContextAOTConfig.java:42)

                at
soot.jimple.paddle.PaddleScene.solve(PaddleScene.java:1390)

                at
soot.jimple.paddle.PaddleTransformer.solve(PaddleTransformer.java:99)

                at
soot.jimple.paddle.PaddleTransformer.internalTransform(PaddleTransformer.jav
a:46)

                at soot.SceneTransformer.transform(SceneTransformer.java:39)

                at
soot.jimple.paddle.PaddleHook.internalTransform(PaddleHook.java:43)

                at soot.SceneTransformer.transform(SceneTransformer.java:39)

                at soot.Transform.apply(Transform.java:89)

                at soot.RadioScenePack.internalApply(RadioScenePack.java:57)

                at
soot.jimple.toolkits.callgraph.CallGraphPack.internalApply(CallGraphPack.jav
a:49)

                at soot.Pack.apply(Pack.java:114)

                at
de.unikl.softech.strauss.masterthesis.analyser.impl.SootInitializerImpl.runS
ootPacks(SootInitializerImpl.java:253)

                at
de.unikl.softech.strauss.masterthesis.analyser.impl.SootInitializerImpl.setu
p(SootInitializerImpl.java:194)

                at
de.unikl.softech.strauss.masterthesis.analyser.impl.SootInitializerImpl.setu
p(SootInitializerImpl.java:49)

                at
de.unikl.softech.strauss.masterthesis.tests.AliasTestsPaddle.init(AliasTests
Paddle.java:63)

                at sun.reflect.NativeMethodAccessorImpl.invoke0(Native
Method)

                at
sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39
)

                at
sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl
.java:25)

                at java.lang.reflect.Method.invoke(Method.java:597)

                at
org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.
java:44)

                at
org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.j
ava:15)

                at
org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.ja
va:41)

                at
org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:27
)

                at
org.junit.internal.runners.statements.RunAfters.evaluate(RunAfters.java:31)

                at org.junit.runners.ParentRunner.run(ParentRunner.java:236)

                at 

Von: soot-list-bounces at sable.mcgill.ca
[mailto:soot-list-bounces at sable.mcgill.ca] Im Auftrag von Lei Shang
Gesendet: Donnerstag, 10. Mai 2012 03:59
An: Florian Strauß
Cc: soot-list at sable.mcgill.ca
Betreff: Re: [Soot-list] Spark and aliasing analysis

Spark is a context-insensitive analysis, which cannot distinguish the object
from factory method (getNew) as they regard (new Object) as the same memory
location. That's why context-sensitivity is needed to get more precise
results.

You should try context-sensitive analyses (cs-demand or geom-pta provided in
soot-2.5.0). 

Lei

2012/5/9 Florian Strauß <f_straus at informatik.uni-kl.de>

Hello,

thanks for the helpful tools / framework Soot and Spark. 

In my settings, something is wrong. In want to find out, if two variables
may point to the same object. Therefore I compare the PointsToSets of these
variables. 

Example:

             Object o5 = new Object();

             Object o6 = new Object();

This example works fine. In my analyzer the following lines return false: 

PointsToAnalysis pointsToGraph = Scene.v().getPointsToAnalysis();

PointsToSet pts1 = pointsToGraph.reachingObjects(localO5);

PointsToSet pts2 = pointsToGraph.reachingObjects(localO6);

return pts1.hasNonEmptyIntersection(pts2);

The next example is similar:

              ClassA k1 = new ClassA();

             ClassA k2 = new ClassA();

Object o7 = k1.getNewO();

             Object o8 = k2.getNewO();

.

             //In class ClassA:

public Object getNewO() {

                    return new Object();

              }

But in this case, the framework says that the two pointsTo-Sets (of o7 and
o8) has an non empty intersection. 

Furthermore, I found out that the base of a method call is always ignored.
The consequence is that for example two iterator, which are returned by
java.util.AbstractList, point to the same objects even if the list instances
and elements are different.  

Is there any option to make the analysis / pointsTo-set more precise?

I am using soot 2.5 and the following options:

//Soot:

             Options.v().set_keep_line_number(true);

             Options.v().set_app(true);

             Options.v().set_xml_attributes(true);

             Options.v().set_whole_program(true);

             PhaseOptions.v().setPhaseOption("jb" ,
"use-original-names:true"); // use original names

             PhaseOptions.v().setPhaseOption("jb.ulp" , "enabled:false"); //
do not minimize the number of stack variables

             PhaseOptions.v().setPhaseOption("jj" ,
"use-original-names:true");

             PhaseOptions.v().setPhaseOption("jj.ulp" , "enabled:false");

             PhaseOptions.v().setPhaseOption("jj.a",
"only-stack-locals:false");

             //Spark:

             Options.v().setPhaseOption("cg","implicit-entry:false");

             Options.v().setPhaseOption("cg.spark","enabled:true");

             //explicit:

             Options.v().setPhaseOption("cg.spark","field-based:false");

             Options.v().setPhaseOption("cg.spark","types-for-sites:false");

             if(IN_DEBUG_MODE){

soot.options.Options.v().setPhaseOption("cg.spark","verbose:true");

             }

I tried the field-based options, but it does not matter if the option is
true or false. The outcome is the same.  

Do you have any ideas?

Best regards,

       Florian

Btw. I am not able to access the website any more:
http://www.sable.mcgill.ca/

Is this a local problem or did someone else notice it?

_______________________________________________
Soot-list mailing list
Soot-list at sable.mcgill.ca
http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20120510/6cfa711a/attachment-0001.html 