[Soot-list] Parallel Spark

[Steven Arzt]

Hi,

We have started to look into parallelizing Soot as well. In theory, this
should be easy, in practice it isn't. The problem is that the program under
analysis is loaded on-demand - more precisely: The jimplification is done on
demand. Only when SPARK detects that it needs a certain method, it will be
loaded fully, i.e., including its body. This avoids having to load code that
is never analyzed which is very sensible in general. However, this
jimplification step heavily relies on singletons, so there are a lot of
dependencies to be taken into account.

If you want to parallelize Soot without any major changes to the
jimplification phase, you will have to at least synchronize the critical
parts of the code loading. Also be aware that SPARK uses a number of global
singletons on its own which you need to synchronize. It would be interesting
to see how much performance gain we can actually get despite all those
synchronizations.

By the way, we discussed this problem (among others) at the last SOAP
workshop.

Best regards,
  Steven

-----Ursprüngliche Nachricht-----
Von: soot-list-bounces at CS.McGill.CA [mailto:soot-list-bounces at CS.McGill.CA]
Im Auftrag von 919 at sjtu.edu.cn
Gesendet: Donnerstag, 22. Mai 2014 05:36
An: soot-list at CS.McGill.CA
Cc: chenyt at cs.sjtu.edu.cn; zhao-jj at cs.sjtu.edu.cn
Betreff: [Soot-list] Parallel Spark

    I am writing to you to for advice on parallelism of soot.jimple.spark.
Since spark is one of the most efficient frameworks of points-to analysis
for Java, the algorithm becomes critical in performance. However, whole
program analysis may lead to performance crash because of the propagation
algorithm; sensitivity aggravates the performance; Java library can produce
too many points-to relations and long points-to paths. 

    I tried to inspect the source code of soot.jimple.spark, and explore the
parallelism in the construction of on-fly-call-graph. Many loops were found,
and I think two of those loops can be scaled. The first loop is in the
method OnFlyCallGraphBuilder.processReachables(). The second loop is in the
method MethodPAG.buildNormal(). The first loop can be scaled to a parallel
analysis among different methods. The second loop can be scaled to a
parallel analysis among different statements. 

    
_______________________________________________
Soot-list mailing list
Soot-list at CS.McGill.CA
https://mailman.CS.McGill.CA/mailman/listinfo/soot-list