[Soot-list] Generating a CallGraph
Marc-André Laverdière
marc-andre.laverdiere-papineau at polymtl.ca
Mon Mar 24 12:12:30 EDT 2014
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>> 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>] 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>
> 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>>> 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>>>> 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>>>
> > >> 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>>>
> > > 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
> >
> >
> >
> >
> > --
> > 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
>
> _______________________________________________
> 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