[Soot-list] Call Graph issues and advice needed

Marc-André Laverdière marc-andre.laverdiere-papineau at polymtl.ca
Sat Apr 27 06:34:04 EDT 2013 

Hello,

I use plain spark personally and it's working fine. You mileage may vary :)

The loop is there to simulate the non-determinism of the order of the entry points.
-- 
Marc-André Laverdière
PhD Candidate - Doctorant
Sent from a mobile device - please excuse the brevity

Henddher Pedroza <hpedro2 at uic.edu> wrote:

>Thank you Marc-Andre
>
>What options would you advice to use for the cg phase before Heros?
>
>Regarding the following, I am sorry but I totally lost you:
>
>When it comes to an IFDS analysis, the solution when the order is 
>unknown is that you should put it in a loop with a random.
>
>switch (random.nextInt()) {
>case 0: ... break;
>case 1: ... break;
>...
>default: return
>}
>What do you mean? "order" of what?
>
>Thanks again!
>
>- Henddher
>
>On Apr 26, 2013, at 8:11 PM, Marc-André Laverdière-Papineau
><marc-andre.laverdiere-papineau at polymtl.ca> wrote:
>
>> Just a small clarification...
>> 
>> Heros uses whatever call graph you give it. So if you see Heros using
>
>> CHA, that is probably because some options need to be set in the cg
>phase :)
>> 
>> Marc-André Laverdière-Papineau
>> Doctorant - PhD Candidate
>> 
>> On 04/25/2013 11:04 AM, Henddher Pedroza wrote:
>>> Thank you Marc-Andre.
>>> 
>>> I will try soot.Main also.
>>> 
>>> What Graph creation would you recommend, Spark, Paddle, CHA? It
>seems like CHA is being used by default by IFDS/Heros. Again, I just
>need the most accurate graph that can be created.
>>> 
>>> Regarding the stub main:
>>> Would the exploded graph (in IFDS terms) created from a "stubbed
>main" be different from the real exploded graph(s) should no stubbed
>main existed?
>>> 
>>> IOW:
>>> Consider stub calling 2 entry points e1 and e2. In the real system,
>e1 is only called by thread1 whereas e2 is only called by thread2. 
>Thus, in the real case, there are 2 problems: problem1 for thread1 and
>e1 and problem2 for thread2 and e2. From thread1 perspective there
>would only be one entry point e1 and its derived nodes, it would not
>contain e2 graph because e2 belongs to thread2. The issue is that
>thread1 would never traverse any path traversed by thread2 because
>there are in fact 2 different graphs altogether. They may share object
>instances though but that's beyond the point of graph reachabiity.
>>> 
>>> It seems to me that these would be 2 different problems that would
>generate 2 different graphs.
>>> Doesn't that matter for IFDS purposes?
>>> (I do not fully understand IFDS)
>>> 
>>> - Henddher
>>> 
>>> On Apr 25, 2013, at 9:42 AM, Marc-André Laverdière-Papineau
><marc-andre.laverdiere-papineau at polymtl.ca> wrote:
>>> 
>>>> Hello,
>>>> 
>>>> I tried using that API for entry points in the past and I would
>just set
>>>> the entry points and then run Soot Main.
>>>> 
>>>> That being said, I hit the static method problem. The way I worked
>>>> around it (with Bernhard's help) was to generate a stub that had a
>main
>>>> and make it instantiate the classes and call the entry points. I
>realize
>>>> that it is a lot of work.
>>>> 
>>>> If you are very brave, you could try to do something inside Spark
>to
>>>> handle non-static entry points. I think few people know that code
>well,
>>>> so the workaround is the preferred solution.
>>>> 
>>>> I haven't used this all-reacheable option, so I am not familiar
>with it.
>>>> If you can confirm there is a bug, it'd be great if you are able to
>>>> write a patch.
>>>> 
>>>> Marc-André Laverdière-Papineau
>>>> Doctorant - PhD Candidate
>>>> 
>>>> On 04/24/2013 05:32 PM, Henddher Pedroza wrote:
>>>>> Thank you Marc-Andre.
>>>>> 
>>>>> Does each entry point need to be a static method?
>>>>> Couldn't a non-static arbitrary method of any class be marked as
>an
>>>>> entry point?
>>>>> 
>>>>> Does the driver cited below have anything wrong?
>>>>> (I am using my own because I need to manipulate entry points. The
>>>>> standard entry points in android do not seem to be handled
>automatically
>>>>> when I use -src-prec apk. If the entry points for android were
>known, or
>>>>> could be specified in another way, I would be able to use
>soot.Main I guess)
>>>>> 
>>>>> What about the option "all-reachable:true"? What is it expected to
>do?
>>>>> 
>>>>> On Apr 24, 2013, at 3:46 PM, Marc-André Laverdière-Papineau
>>>>> <marc-andre.laverdiere-papineau at polymtl.ca
>>>>> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>> wrote:
>>>>> 
>>>>>> Hello,
>>>>>> 
>>>>>> 1) For Paddle, did you include the separate Paddle jar?
>>>>> 
>>>>> I didn't know about this. I will search for it.
>>>>> 
>>>>>> 2) For all-reachable, I would encourage you to dump the CG using
>Probe
>>>>>> and double-check that its really due to the call graph.
>>>>>> http://plg.uwaterloo.ca/~olhotak/probe/
>>>>>> Also, I would encourage you to use the soot main instead of
>rolling your
>>>>>> own driver. I would say that this is the source of so many
>problems we
>>>>>> see reported on the ML that its always the first thing that gets
>>>>>> suggested.
>>>>>> 
>>>>> 
>>>>> I will look into this.
>>>>> 
>>>>>> By the way, note that you need entry points no matter what,
>because your
>>>>>> CG needs a root. There is a catch: the entry points need to be
>static,
>>>>>> otherwise Spark will produce a CG with missing edges.
>>>>>> 
>>>>> 
>>>>> Is static a mandatory requirement for entry points?
>>>>> 
>>>>>> 3) Those call on CG objects... are they done inside a
>transformer?
>>>>>> Outside of one, you are guaranteed to get an empty CG.
>>>>> 
>>>>> They are inside internalTransform after the instantiation of CG:
>>>>> 
>>>>> this.cg = new JimpleBasedInterproceduralCFG();
>>>>> ...
>>>>> cg.getCallersOf(sm); // sm is my method of interest
>>>>> 
>>>>> 
>>>>>> 
>>>>>> 4) I don't know about the Android side of things, sorry.
>>>>>> 
>>>>>> 5) I saw this NPE in getBodyFromMethodSource before. IIRC, it
>happens
>>>>>> when trying to load a body from an excluded class.
>>>>>> 
>>>>> 
>>>>> I am not explicitly excluding classes.
>>>>> 
>>>>>> I hope this helps. Regards,
>>>>>> 
>>>>>> Marc-André Laverdière-Papineau
>>>>>> Doctorant - PhD Candidate
>>>>>> 
>>>>>> On 04/24/2013 11:00 AM, Henddher Pedroza wrote:
>>>>>>> Hello all:
>>>>>>> 
>>>>>>> I am trying to obtain the most complete CFG there can be for
>>>>>>> Interprocedural analysis to use with Heros. I am analyzing
>Android apps.
>>>>>>> 
>>>>>>> *) cg.paddle does not seem to be complete. Apparently
>PaddleTransformer
>>>>>>> is missing. Exception in thread "main"
>java.lang.RuntimeException: Could
>>>>>>> not find soot.jimple.paddle.PaddleTransformer. Did you include
>Paddle on
>>>>>>> your Java classpath?
>>>>>>> at soot.jimple.paddle.PaddleHook.instantiate(PaddleHook.java:51)
>>>>>>> *) Neither cg.spark and cg.cha seem to obey the
>"all-reachable:true"
>>>>>>> option.
>>>>>>> 
>>>>>>> I am using JimpleBasedInterproceduralCFG and it seems like the
>cg is not
>>>>>>> complete. I create this instance within the body of
>internalTransform of
>>>>>>> my SceneTransformer phase added to the "wjtp" pack.
>>>>>>> 
>>>>>>> I have my own driver:
>>>>>>> // command line: java -cp lib/soot.jar:bin/ -Xmx4000m -ea
>MyDriver -f J
>>>>>>> -d ./sootOutput/ -cp $APPCP -process-dir $APK
>-no-bodies-for-excluded
>>>>>>> -allow-phantom-refs -w -pp -src-prec apk -android-jars
>>>>>>> ../Documents/android-sdk-macosx/platforms/ -ire -p cg
>>>>>>> all-reachable:true -p cg.spark enabled:true
>>>>>>> 
>>>>>>> // MyDriver.java
>>>>>>> public static void main(String[] args) {
>>>>>>>  Options.v().parse(Arrays.copyOf(args, args.length));
>>>>>>> 
>>>>>>>  Scene.v().loadNecessaryClasses();
>>>>>>> 
>>>>>>>     addMyEntryPointsTo(Scene.v().getEntryPoints()); // here I
>add my
>>>>>>> entry points because "all-reachable:true" seems to do nothing
>>>>>>> PackManager.v().getPack("wjtp").add(newTransform("wjtp.ifds",
>>>>>>> newMyAnalysis()));
>>>>>>>  PackManager.v().runPacks();
>>>>>>> }
>>>>>>> 
>>>>>>> Any advice of how I should instruct Soot to create the CG for
>>>>>>> interprocedural?
>>>>>>> 
>>>>>>> I am experiencing multiple problems:
>>>>>>> 
>>>>>>> 1. When I query all the callers (callsites) of a given callee
>method, I
>>>>>>> get an empty set (i.e. cg.getCallersOf(callee).isEmpty() is
>true). But,
>>>>>>> if I specify one of the known callers (i.e.
>knownCallerSootMethod) as an
>>>>>>> entry point
>(Scene.v().getEntryPoints().add(knownCallerSootMethod)),
>>>>>>> then cg.getCallersOf(callee) returns the callsite unit where my
>callee
>>>>>>> is invoked. The fact that I have to add knownCallerSootMethod to
>entry
>>>>>>> points tells me that the knownCallerSootMethod is not an entry
>point
>>>>>>> automatically found by Soot even though is an entry point for
>Android
>>>>>>> app (aka Acvitity.onCreate(Bundle)). Doesn't Soot know the
>standard
>>>>>>> entry points for android apps when the -src-prec option is
>"apk"?
>>>>>>> And, why does "all-reachable:true" option seem to do nothing in
>my case?
>>>>>>> 
>>>>>>> 2. The cg constructed seems to be incomplete even when I choose
>.class
>>>>>>> file analysis instead of .apk. IOW, cg.getCallersOf(callee)
>returns
>>>>>>> empty even when I use -src-prec class AND add the
>android-platform path
>>>>>>> (not stubs) to soot classpath.
>>>>>>> 
>>>>>>> 3. For some apps (.apk), the construction of cg fails with NPE
>depending
>>>>>>> on which entry points I explicitly add. Note that my command
>line
>>>>>>> specifies "cg.spark" (a) but similar results (NPE) are produced
>when I
>>>>>>> use cg.cha (b).
>>>>>>> 
>>>>>>> a)
>>>>>>> Exception in thread "main" java.lang.NullPointerException
>>>>>>> at soot.SootMethod.getBodyFromMethodSource(SootMethod.java:89)
>>>>>>> at soot.SootMethod.retrieveActiveBody(SootMethod.java:322)
>>>>>>> at
>>>>>>>
>soot.jimple.toolkits.callgraph.OnFlyCallGraphBuilder.processNewMethod(OnFlyCallGraphBuilder.java:532)
>>>>>>> at
>>>>>>>
>soot.jimple.toolkits.callgraph.OnFlyCallGraphBuilder.processReachables(OnFlyCallGraphBuilder.java:427)
>>>>>>> at
>soot.jimple.spark.solver.OnFlyCallGraph.build(OnFlyCallGraph.java:55)
>>>>>>> at
>>>>>>>
>soot.jimple.spark.builder.ContextInsensitiveBuilder.build(ContextInsensitiveBuilder.java:77)
>>>>>>> at
>>>>>>>
>soot.jimple.spark.SparkTransformer.internalTransform(SparkTransformer.java:84)
>>>>>>> at soot.SceneTransformer.transform(SceneTransformer.java:39)
>>>>>>> b)
>>>>>>> Exception in thread "main" java.lang.NullPointerException
>>>>>>> at soot.SootMethod.getBodyFromMethodSource(SootMethod.java:89)
>>>>>>> at soot.SootMethod.retrieveActiveBody(SootMethod.java:322)
>>>>>>> at
>>>>>>>
>soot.jimple.toolkits.callgraph.OnFlyCallGraphBuilder.processNewMethod(OnFlyCallGraphBuilder.java:532)
>>>>>>> at
>>>>>>>
>soot.jimple.toolkits.callgraph.OnFlyCallGraphBuilder.processReachables(OnFlyCallGraphBuilder.java:427)
>>>>>>> at
>>>>>>>
>soot.jimple.toolkits.callgraph.CallGraphBuilder.build(CallGraphBuilder.java:84)
>>>>>>> at
>>>>>>>
>soot.jimple.toolkits.callgraph.CHATransformer.internalTransform(CHATransformer.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.java:49)
>>>>>>> at soot.Pack.apply(Pack.java:114)
>>>>>>> 
>>>>>>> Any suggestion is welcome.
>>>>>>> 
>>>>>>> - Henddher
>>>>>>> 
>>>>>>> 
>>>>>>> 
>>>>>>> 
>>>>>>> _______________________________________________
>>>>>>> Soot-list mailing list
>>>>>>> Soot-list at sable.mcgill.ca <mailto:Soot-list at sable.mcgill.ca>
>>>>>>> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>>>>>>> 
>>>>>> _______________________________________________
>>>>>> Soot-list mailing list
>>>>>> Soot-list at sable.mcgill.ca <mailto:Soot-list at sable.mcgill.ca>
>>>>>> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>>>>> 
>>>> _______________________________________________
>>>> Soot-list mailing list
>>>> Soot-list at sable.mcgill.ca
>>>> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>>> 
>>> 
>> _______________________________________________
>> Soot-list mailing list
>> Soot-list at sable.mcgill.ca
>> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list

More information about the Soot-list mailing list