[Soot-list] Generating a CallGraph
Marc-André Laverdière
marc-andre.laverdiere-papineau at polymtl.ca
Mon Mar 24 17:47:00 EDT 2014
Hi Graziella,
I don't know much about the .build file, so no comments.
I am surprised that CHA is taking so long - do you have very large
libraries? Did you try using Spark in CHA mode? I think that the
CHATransformer is very old code - Spark has optimizations that work for
all analyses.
Spark should take more time, that's obvious. A way to work around that
is to use exclusions and no-bodies-for-exclusions. You truncate your
call graph, which is unsound, but you may not care so much about some
parts of it. I do that all the time when analyzing JEE.
Also, note that the wjtp phase runs after Spark executes (if Spark is
enabled, that is).
Marc-André Laverdière-Papineau
Doctorant - PhD Candidate
On 03/24/2014 02:13 PM, Graziella Galea wrote:
> Thanks for your help Marc-André.
>
> I have read a bit about what you said and on the paper 'A Survivor's
> Guide to Java Program Analysis with Soot' it is also argued that
> SPARK provides a more precise callgraph while CHA is considered as a
> dumb version.
>
> Before continuing any further though, I have realised that generating a
> callgraph using CHA takes approximately a minute. In the same
> paper it is said that SPARK provides a better callgraph at the expense
> of complicated setup and time. Obviously, I do not want the
> callgraph generation to take longer (already not very happy with the
> current execution time especially because the call graph
> handling barely takes a second.). Do you think that SPARK will take
> even longer than a minute? The currently implementation for the
> callgraph generation takes a lot of time (a minute) because of this line:
>
> PackManager.v().getPack("wjtp").apply();
>
>
> On a different note, is it true that there is a way of generating a
> callgraph using the .build file? I never saw such solution on the web but
> I know of someone who did but do not know how and it seems as though it
> does not take a long time for such generation.
>
>
>
> On 24 March 2014 17:12, Marc-André Laverdière
> <marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>> wrote:
>
> Hello Graziella,
>
> It wouldn't hurt to do some reading on call graph construction
> algorithms if you want to know more. I think that Lhoták's masters'
> thesis on SPARK, even if you just skim through it, will be very
> instructive.
>
> Anyways, here is an executive summary.
> CHA = declared type's class + all subclasses
> RTA = CHA - types that aren't instanciated
> VTA, SPARK, etc. = RTA + Fancy constraint propagation to narrow it down
> even more.
>
> So, CHA will always be 'good' if you use very flat hierarchies, or if
> the program you analyze always declares the exact same type as the one
> used (e.g. no List meh = new ArrayList, but ArrayList meh = new
> ArrayList). I am sure that this kind of code exists, but I doubt that
> you'll analyze only this stuff :)
>
> Marc-André Laverdière-Papineau
> Doctorant - PhD Candidate
>
> On 03/24/2014 11:31 AM, Graziella Galea wrote:
> > Hi!
> >
> > Why is the CHA algorithm less precise? I have tested it and
> worked fine
> > till now but it is very important for me that I have precise results.
> >
> > Regards,
> >
> > Graziella
> >
> >
> > On 24 March 2014 09:49, Steven Arzt <Steven.Arzt at cased.de
> <mailto:Steven.Arzt at cased.de>
> > <mailto:Steven.Arzt at cased.de <mailto:Steven.Arzt at cased.de>>> wrote:
> >
> > Hi all,
> >
> > It really depends on the type of callgraph you are looking
> for. SPARK
> > definitely does not work with non-static entry points, i.e. it
> will miss
> > edges because it does not have valid points-to-sets for all "this"
> > fields
> > inside the instance methods on the boundary. So if no one
> > instantiates your
> > class A and A.method() is an entry point, then there will be
> an empty
> > points-to-set for "this" in A.method() since no one ever
> creates an
> > instance
> > of A.
> >
> > If you have non-static entry points and need SPARK's full
> precision, you
> > will have to create a dummy main method. For doing so, you can
> use the
> > DefaultEntryPointCreator class from FlowDroid
> > (https://github.com/secure-software-engineering/soot-infoflow)
> which
> > should
> > make it fairly simple.
> >
> > The other option would be to try a less precise CG algorithm
> such as
> > CHA or
> > RTA as already discussed.
> >
> > Best regards,
> > Steven
> >
> > -----Ursprüngliche Nachricht-----
> > Von: soot-list-bounces at sable.mcgill.ca
> <mailto:soot-list-bounces at sable.mcgill.ca>
> > <mailto:soot-list-bounces at sable.mcgill.ca
> <mailto:soot-list-bounces at sable.mcgill.ca>>
> > [mailto:soot-list-bounces at sable.mcgill.ca
> <mailto:soot-list-bounces at sable.mcgill.ca>
> > <mailto:soot-list-bounces at sable.mcgill.ca
> <mailto:soot-list-bounces at sable.mcgill.ca>>] Im Auftrag von Marc-André
> > Laverdière-Papineau
> > Gesendet: Samstag, 22. März 2014 20:22
> > An: soot-list at sable.mcgill.ca
> <mailto:soot-list at sable.mcgill.ca> <mailto:soot-list at sable.mcgill.ca
> <mailto:soot-list at sable.mcgill.ca>>
> > Betreff: Re: [Soot-list] Generating a CallGraph
> >
> > Hi Graziella,
> >
> > This code uses CHA. Is that what you really want?
> >
> > I honestly don't know of anybody who got a call graph in this kind
> > of case
> > with SPARK without generating a stubbed main.
> >
> > Eric wrote the blog entry about custom entry points, he's probably
> > the best
> > person to ask...
> >
> > Marc-André Laverdière-Papineau
> > Doctorant - PhD Candidate
> >
> > On 22/03/14 05:57 AM, Graziella Galea wrote:
> > > I have followed the following solution to generate a callgraph
> > > http://marc.info/?l=soot-list&m=134095873818018&w=2
> > > and it does not mention anything about static classes - in
> fact it
> > > sets every method in the project to be analysed as an
> entrypoint.
> > > This is the reason I thought this is a good solution since I
> don't
> > > have a main class. Is there some tutorial which specifies
> exactly
> > what
> > settings
> > > need to be configured in order to generate a call graph? The
> > code for
> > > using the call graph is fine because I analysed another
> project and
> > > the settings worked perfectly. Then I applied it to another
> project
> > > and it didn't work. All I need to know is the settings - I
> have the
> > > logic to handle a call graph then.
> > >
> > > Thanks again for your help!
> > >
> > >
> > > On 21 March 2014 22:42, Marc-André Laverdière
> > > <marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>
> > <mailto:marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>>
> > > <mailto:marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>
> > <mailto:marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>>>> wrote:
> > >
> > > Hello,
> > >
> > > Using the Soot main requires that you have a main class
> in your
> > program.
> > > Custom entry points won't work in that case.
> > > Before we go there, would you please confirm that your entry
> > points
> > are
> > > static?
> > >
> > > The next thing: I suggest that you add a transformer
> that will
> > list
> > all
> > > non-phantom classes loaded in your Scene. This is probably
> > going to
> > help
> > > diagnose problems.
> > >
> > > My suggestion is that you start small: have it working on a
> > simpler
> > test
> > > case (all classes local, only one version), then add a
> feature
> > > (downloading class definitions), and then add the other.
> > >
> > > Marc-André Laverdière-Papineau
> > > Doctorant - PhD Candidate
> > >
> > > On 03/21/2014 04:25 PM, Graziella Galea wrote:
> > > > Thanks for your response Marc-Andre.
> > > >
> > > > I am using a class loader in order to be able to retrieve
> > classes
> > and
> > > > set them as application classes. I previously used
> > > > Scene.v().loadNecessaryClasses() but it is not good
> for my case
> > > since I
> > > > need to generate a call graph for different versions
> of the same
> > > > project. I have been recommended to use the soot.Main
> but I am
> > > not sure
> > > > what parameters I need to pass. How do you recommend
> to use the
> > > > soot.Main method?
> > > >
> > > > Thanks for your help.
> > > >
> > > > Regards,
> > > >
> > > > Graziella.
> > > >
> > > >
> > > > On 21 March 2014 20:05, Marc-Andre Laverdiere-Papineau
> > > > <marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>
> > <mailto:marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>>
> > > <mailto:marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>
> > <mailto:marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>>>
> > > > <mailto:marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>
> > <mailto:marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>>
> > > <mailto:marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>
> > <mailto:marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>>>>> wrote:
> > > >
> > > > Hi Graziella,
> > > >
> > > > Soot doesn't care about the class loader that you
> use - it
> > > uses its
> > > > own class loading logic. You would need to either
> change
> > that
> > > > mechanism, or dump the classes you get from other
> > sources to the
> > > > disk and let Soot retrieve that.
> > > >
> > > > Also, it is generally recommended to use the Soot
> main if
> > > you're new
> > > > at Soot.
> > > >
> > > > Also, note that entry points need to be static. IIRC,
> > when you
> > are
> > > > working in app mode, you need to have an explicit main
> > method,
> > but
> > > > I'm not 100% sure about that.
> > > >
> > > > BTW, you can join us on IRC at #soot on Freenode
> if that's
> > > your thing.
> > > >
> > > > Le 2014-03-21 10:48, Graziella Galea a écrit :
> > > >>
> > > >> I am currently working on a project whereby I need to
> > generate
> > a
> > > >> call graph for Java code analysis using SOOT.
> > Unfortunately,
> > for
> > > >> each class in the project I am analyzing, soot is
> > returning a
> > > >> warning that the class in a phantom reference.
> Now, if
> > I am not
> > > >> mistaken, a phantom reference is a class which I
> cannot
> > provide
> > > >> but I am actually providing it. I first started
> > thinking that
> > the
> > > >> problem was with the Soot's classpath but I think
> it is
> > correct.
> > > >> The path String variable used to set the
> classpath (as
> > shown in
> > > >> the code snippet below) specifies the bin folder
> of the
> > project
> > > >> I'm analysing.
> > > >>
> > > >> Could anyone help me? It's been over a week and
> cannot seem
> > > to get
> > > >> it right.
> > > >>
> > > >> Code used for setup:
> > > >>
> > > >>
> > > >> |
> > > >>
> > >
> >
> privateCallGraphsetUp(ArrayList<String>paths,StringtestSuite)throwsException
> >
> {Options.v().set_whole_program(true);Options.v().set_allow_phantom_refs(true
> > );
> > > >>
> > > >>
> > > >> Options.v().set_app(!
> > > >> true);
> > > >>
> Options.v().set_no_bodies_for_excluded(true);//set each
> > method
> > in
> > > >> the source folder as an entry pointParserp
> > > >> =newParser();List<SootMethod>entryPoints
> > > >> =newArrayList<SootMethod>();//the arraylist paths
> > contains the
> > > >> path to the test suite and the path to the source
> > > >> folderfor(Stringpath:paths){if(path !=null
> > > >> ){__//if it is null then the user chose to
> identify the
> > > methods only
> > > >> //create a classLoader for this pathFilefile
> > > >> =newFile(path);ClassLoaderclassLoader
> > > >>
> > >
> >
> =newURLClassLoader(newURL[]{file.toURI().toURL()},parent);MultiClassLoadermc
> > l
> > > >>
> > >
> >
> =newMultiClassLoader();mcl.addClassLoader(classLoader);ArrayList<File>allFil
> > es
> > > >>
> > >
> >
> =p.getSourceFiles(path,false__);Options.v().set_process_dir(Arrays.asList(pa
> > th+"\\"));__
> > > >> Options.v().set_soot_classpath("C:\\Program
> > > >> Files\\Java\\jre7\\lib\\rt.jar;"+path+"\\;C:\\Program
> > > >>
> > >
> Files\\Java\\jre7\\lib\\jce.jar");for(Filef:allFiles){//remove the
> > > >> path and leave package path onlyStringname
> > =f.getAbsolutePath()
> > > >> .replace(path+"\\","");name =name.replace("\\",____
> > ".");name
> > > >> =name.replace(".class", "");//saves test files so
> as to be
> > > able to
> > > >> distinguish between normal methods and test cases
> > > >>
> > > >> if(path.equals(testSui!
> > > >> te<
> > > >> span class=""
> > >
> >
> style="margin:0px;padding:0px;border:0px;font-size:14px;vertical-align:basel
> > ine;background-color:transparent">)){
> > > >> testFiles.add(name);}//load the classClass<?>cls
> =mcl.getCl
> > > >> assLoader(0).loadClass(name);SootClasssootClass
> > > >> =Scene.v().loadClassAndSupport(cls.getName
> > > >>
> > > >> ());
> > > >> __sootClass.setApplicationClass();//set all of the
> > methods in
> > > this
> > > >> class as entrypoints since there is no main method
> > > >>
> > >
> >
> availablefor(SootMethodm:sootClass.getMethods()){if(!m.isAbstract()){System.
> > out.println("entrypoint
> > > >>
> > >
> >
> "+m);entryPoints.add(m);}}}mcl.removeClassLoader(classLoader);}}Scene.v().ad
> > dBasicClass("java.
> > > >>
> > lang.ThreadGroup",SootClass.SIGNATURES);Scene.v().setEntryPoints(
> > > >>
> > > >> entryPoints__);
> > > >> PackManager.v().runPacks();
> > > >> return Scene.v().get!
> > > >> CallGraph<
> > > >> /span>();
> > > >> }|
> > > >> --
> > > >> Graziella Galea
> > > >>
> > > >>
> > > >> _______________________________________________
> > > >> Soot-list mailing list
> > > >> Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>
> > <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>>
> <mailto:Soot-list at sable.mcgill.ca <mailto:Soot-list at sable.mcgill.ca>
> > <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>>>
> > > <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>
> > <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>>
> <mailto:Soot-list at sable.mcgill.ca <mailto:Soot-list at sable.mcgill.ca>
> > <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>>>>
> > > >>
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> > > >
> > > > --
> > > > Marc-André Laverdière-Papineau
> > > > Doctorant - PhD Candidate
> > > >
> > > >
> > > > _______________________________________________
> > > > Soot-list mailing list
> > > > Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>
> > <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>>
> <mailto:Soot-list at sable.mcgill.ca <mailto:Soot-list at sable.mcgill.ca>
> > <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>>>
> > > <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>
> > <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>>
> <mailto:Soot-list at sable.mcgill.ca <mailto:Soot-list at sable.mcgill.ca>
> > <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>>>>
> > > > http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> > > >
> > > >
> > > >
> > > >
> > > > --
> > > > Graziella Galea
> > > >
> > > >
> > > > _______________________________________________
> > > > Soot-list mailing list
> > > > Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca> <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>>
> > <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca> <mailto: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> <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>>
> > <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca> <mailto:Soot-list at sable.mcgill.ca
> <mailto:Soot-list at sable.mcgill.ca>>>
> > > http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> > >
> > >
> > >
> > >
> > > --
> > > Graziella Galea
> > >
> > >
> > > _______________________________________________
> > > Soot-list mailing list
> > > Soot-list at sable.mcgill.ca <mailto:Soot-list at sable.mcgill.ca>
> <mailto: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>
> <mailto: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>
> <mailto:Soot-list at sable.mcgill.ca <mailto:Soot-list at sable.mcgill.ca>>
> > http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> >
> >
> >
> >
> > --
> > Graziella Galea
> >
> >
> > _______________________________________________
> > 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
>
>
>
>
> --
> Graziella Galea
>
>
> _______________________________________________
> 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