[Soot-list] Sideeffectanalysis

Ondrej Lhotak olhotak at uwaterloo.ca
Sun Mar 6 14:56:38 EST 2011 

When you run Paddle using context:objsens, the contexts are object
allocation sites (for details on object sensitivity, see Milanova
et al.'s paper in TOSEM 14(1)). In Paddle, these are represented by
AllocNodes. Each Paddle points-to set is a set of AllocNodes (possibly
also with Context, depending on the settings). So to determine the
context inside a call o.foo(), you need to get the points-to set of the
receiver o, and then analyze foo() with all of the AllocNodes in it as
contexts.

More generally, the biggest thing you will need to do is reimplement the
side-effect anaylsis to be context sensitive. Although the points-to
analysis in Paddle is already context sensitive, the side-effect
analysis in Soot is not.

Ondrej

On Fri, Mar 04, 2011 at 07:27:13PM +0100, Eric Bodden wrote:
> Hmmm, maybe Ondrej can shed some light on this? I have never used that
> particular interface, I am afraid.
> 
> Eric
> 
> On 4 March 2011 18:56, Jochen Huck <jochen.huck at student.kit.edu> wrote:
> > Additionally I have to say, that the exception occours running paddle with
> > context:objsens. It does not occur running it with context:1cfa (I think
> > that the call graph expects an AllocNode in case of objsens as the interface
> > description of Context suggests). I still have no clue where to get an
> > AllocNode from.
> >
> > Jochen
> >
> > Am 04.03.2011 18:33, schrieb Jochen Huck:
> >>
> >> Hi again,
> >>
> >> I already tried that. I get the following exception:
> >> Exception in thread "Thread-4" java.lang.ClassCastException:
> >> soot.jimple.internal.JInvokeStmt cannot be cast to soot.util.Numberable
> >>      at soot.util.ArrayNumberer.get(ArrayNumberer.java:47)
> >>      at soot.util.JeddNumberer.get(JeddNumberer.java:35)
> >>      at jedd.internal.Jedd.literal(Jedd.java:158)
> >>      at
> >>
> >> soot.jimple.paddle.PaddleContextSensitiveCallGraph.edgesOutOf(PaddleContextSensitiveCallGraph.java:97)
> >>      at
> >>
> >> soot.jimple.toolkits.pointer.SideEffectTagger.keyFor(SideEffectTagger.java:113)
> >>      at
> >>
> >> soot.jimple.toolkits.pointer.SideEffectTagger.internalTransform(SideEffectTagger.java:170)
> >>      at soot.BodyTransformer.transform(BodyTransformer.java:51)
> >>      at soot.Transform.apply(Transform.java:104)
> >>      at soot.BodyPack.internalApply(BodyPack.java:49)
> >>      at soot.Pack.apply(Pack.java:124)
> >>      at soot.PackManager.runBodyPacks(PackManager.java:779)
> >>      at soot.PackManager.runBodyPacks(PackManager.java:454)
> >>      at soot.PackManager.runBodyPacks(PackManager.java:373)
> >>      at soot.PackManager.runPacks(PackManager.java:350)
> >>      at soot.Main.run(Main.java:198)
> >>      at soot.Main.main(Main.java:141)
> >>
> >> Jochen
> >>
> >> Am 04.03.2011 17:47, schrieb Eric Bodden:
> >>>
> >>> Oh now I see.
> >>>
> >>> If I am not mistaken then any Stmt can function as a context. At least
> >>> that's what the type hierarchy suggests:
> >>> http://www.sable.mcgill.ca/soot/doc/soot/Context.html
> >>>
> >>> So you can just pass in the Jimple statement I suppose.
> >>>
> >>> Eric
> >>>
> >>> On 4 March 2011 17:14, Jochen Huck<jochen.huck at student.kit.edu>   wrote:
> >>>>
> >>>> No I am not using Spark and Paddle. Only the interface description of
> >>>> Context says that a context is a Spark AllocNode in case of an
> >>>> object-sensitive call graph. I only use Paddle and therefore only
> >>>> instances
> >>>> of Paddle AllocNode will be available.
> >>>> In a bodyTransformer I have (for the example code) "method=main" and
> >>>> "unit=f1.inc()" and I want to query the call graph for the edge going
> >>>> out of
> >>>> f1.inc(). If cg is the instance of ContextSensitiveCallGraph I get the
> >>>> Iterator over all edges going out of f1.inc() by cg.edgesOutOf(context,
> >>>> method, unit). But I don't know where i can get the context instance
> >>>> from. I
> >>>> assume it somehow has to do with the pointsToSet of f1.
> >>>>
> >>>> Thanks again,
> >>>> Jochen
> >>>>
> >>>>
> >>>> Am 04.03.2011 17:05, schrieb Eric Bodden:
> >>>>>
> >>>>> So are you trying to use Spark and Paddle at the same time? That won't
> >>>>> work.
> >>>>>
> >>>>> I have not used Paddle in a while but I think that paddle implements
> >>>>> its own CallGraph subclass that accepts paddle AllocNode instances as
> >>>>> input.
> >>>>>
> >>>>> As an alternative to using paddle you can also use the demand-driven
> >>>>> context-sensitive points-to analysis "DemandCSPointsTo".
> >>>>>
> >>>>> Eric
> >>>>>
> >>>>> On 4 March 2011 16:54, Jochen Huck<jochen.huck at student.kit.edu>
> >>>>> wrote:
> >>>>>>
> >>>>>> Thanks! This is what I thought too.
> >>>>>> I've got a question according the ContextSensitiveCallGraph (cg): I
> >>>>>> will
> >>>>>> need to know the call graph edges that go out of f1.inc().
> >>>>>> Given the declaringMethod(main) and the unit(f1.inc()) I have to ask
> >>>>>> cg.edgesOutOf(context, method, unit). But where do I get the context
> >>>>>> from?
> >>>>>> The description of the interface Context says that context is a Spark
> >>>>>> AllocNode in the case of an object-sensitive call graph. Using Paddle
> >>>>>> I
> >>>>>> would only have access to a Paddle AllocNode, right? Where do I get
> >>>>>> the
> >>>>>> AllocNode from? I am a little confused...
> >>>>>>
> >>>>>> Jochen
> >>>>>>
> >>>>>>
> >>>>>> Am 04.03.2011 16:38, schrieb Eric Bodden:
> >>>>>>>
> >>>>>>> Hi Jochen.
> >>>>>>>
> >>>>>>>
> >>>>>>> If I am not mistaken then you are looking for a 1-object-sensitive
> >>>>>>> analysis. I think Ondrej wrote a paper a while ago in which he found
> >>>>>>> out that object-sensitivity usually works best and a context length
> >>>>>>> of
> >>>>>>> 1 is often sufficient - at least that's what I remember.
> >>>>>>>
> >>>>>>> Eric
> >>>>>>>
> >>>>>>> On 4 March 2011 14:42, Jochen Huck<jochen.huck at student.kit.edu>
> >>>>>>>   wrote:
> >>>>>>>>
> >>>>>>>> Hi,
> >>>>>>>>
> >>>>>>>> the current implementation of the sideeffectanalysis
> >>>>>>>> (soot.jimple.toolkits.pointer.SideEffectAnalysis) is
> >>>>>>>> context-insensitive
> >>>>>>>> and therefore really imprecise. For
> >>>>>>>>
> >>>>>>>> class Foo {
> >>>>>>>>      int i;
> >>>>>>>>      public static void main(String[] args) {
> >>>>>>>>          Foo f1 = new Foo();
> >>>>>>>>          Foo f2 = new Foo();
> >>>>>>>>          f1.inc();
> >>>>>>>>          f2.inc();
> >>>>>>>>      }
> >>>>>>>>      public void inc() {
> >>>>>>>>          i++;
> >>>>>>>>      }
> >>>>>>>> }
> >>>>>>>>
> >>>>>>>> it reports that f1.inc() and f2.inc() have the same dependencies,
> >>>>>>>> since
> >>>>>>>> the analysis is context-insensitive.
> >>>>>>>>
> >>>>>>>> I would like to improve the precisson using Paddle. Which option
> >>>>>>>> (1cfg,
> >>>>>>>> object-sensitive) would I need, that it is possible to infer that
> >>>>>>>> the
> >>>>>>>> calls to inc() have no dependencies?
> >>>>>>>> I will have to rewrite some methods of SideEffectAnalysis and
> >>>>>>>> SideEffectTagger. Any suggestions how difficult that would be?
> >>>>>>>>
> >>>>>>>> Thanks,
> >>>>>>>> Jochen
> >>>>>>>>
> >>>>>>>>
> >>>>>>>> _______________________________________________
> >>>>>>>> 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
> >
> >
> 
> 
> 
> -- 
> Dr. Eric Bodden, http://bodden.de/
> Principal Investigator in Secure Services at CASED
> Coordinator of the CASED Advisory Board of Study Affairs
> PostDoc at Software Technology Group, Technische Universität Darmstadt
> Tel: +49 6151 16-5478    Fax: +49 6151 16-5410
> Mailing Address: S2|02 A209, Hochschulstraße 10, 64289 Darmstadt
>

More information about the Soot-list mailing list