[Soot-list] Generating a CallGraph
Graziella Galea
gra.galea at gmail.com
Tue Mar 25 14:56:20 EDT 2014
Hi Marc-André.
I added the setting Options.v().set_no_bodies_for_excluded(true); and it
only took around 25 seconds which is good. Then I tried to use SPARK since
it is more precise. The problem is that I do not think that the whole
callgraph is being generated. This is because for particular methods, I
identify their source methods and some of which are not being found.
The following is my code:
private CallGraph setUp(String path, String javafiles, String testSuite)
throws Exception{
Options.v().set_no_bodies_for_excluded(true);
Options.v().set_whole_program(true);
Options.v().set_allow_phantom_refs(true);
Options.v().set_process_dir(Arrays.asList(path)); //library dir
Options.v().set_soot_classpath("C:\\Program
Files\\Java\\jre7\\lib\\rt.jar;"+path+";" +
"C:\\Program Files\\Java\\jre7\\lib\\jce.jar");
//library dir along with rt.jar/jce.jar from JRE/JDK
Scene.v().loadNecessaryClasses();
getAllMethods(path);
//identify source files
identifySources(javafiles);
System.out.println("sources identifed");
identifyTestClasses(testSuite);
Transform sparkTranform = new Transform( "cg.spark", null );
PhaseOptions.v().setPhaseOption( sparkTranform, "verbose:true" );
Map options = PhaseOptions.v().getPhaseOptions( sparkTranform );
PointsToAnalysis spark = new PAG(new SparkOptions(options));
CallGraphBuilder builder = new CallGraphBuilder(spark);
builder.build();
return builder.getCallGraph();
}
private ArrayList<SootMethod> getAllMethods(String path) throws Exception{
Parser p = new Parser();
ArrayList<File> allFiles = p.getSourceFiles(path, false);
ArrayList<SootMethod> entryPoints = new ArrayList<SootMethod>();
for(File f: allFiles){
//remove the path and leave package path only
String name = f.getAbsolutePath().replace(path+"\\", "");
name = name.replace("\\", ".");
name = name.replace(".class", "");
SootClass sootClass = Scene.v().forceResolve(name,
SootClass.BODIES);
sootClass.setApplicationClass();
for(SootMethod m: sootClass.getMethods()){
if (!m.isAbstract()) {
entryPoints.add(m);
}
}
}
Scene.v().addBasicClass("java.lang.ThreadGroup",SootClass.SIGNATURES);
Scene.v().setEntryPoints(entryPoints);
return entryPoints;
}
Is this fine?
Thanks for your help.
On 24 March 2014 22:47, Marc-André Laverdière <
marc-andre.laverdiere-papineau at polymtl.ca> wrote:
> 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
> >
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>
--
Graziella Galea
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20140325/232f140f/attachment-0001.html
More information about the Soot-list
mailing list