[Soot-list] Call Graph issues and advice needed
Rohan Padhye
rohanpadhye at cse.iitb.ac.in
Thu Apr 25 11:38:04 EDT 2013
Hendddher,
I do not think your analysis would be sound if you use a stub main with
different entry points.
Consider a simple constant analysis:
main() {
e1();
e2();
}
e1() {
x = 10;
}
e2() {
use x;
}
If you use a stub main then your analysis might conclude that x = 10 is
constant at e2(), but that is not the case if the program starts at
e2(). In IFDS terms, you really want results of thread starting at e2
to compute reachability from the zero node only, not all nodes that are
true at the exit of the thread starting at e1.
You would probably be better off performing multiple IFDS solutions, one
for each entry point, and then merging results for each program point
across all such instances if you want to do some optimizations.
Regards,
Rohan Padhye
On Thursday 25 April 2013 08:34 PM, 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
--
Regards,
Rohan Padhye
More information about the Soot-list
mailing list