[Soot-list] What kind of analysis is appropriate?
Zeinab Lashkaripour
lashkaripour at yahoo.com
Wed Apr 24 16:47:42 EDT 2013
Thanks Marc-André,
I think I some how got the point and need to study a bit.
Thanks for helping me.
Zeinab
----- Original Message -----
From: Marc-André Laverdière-Papineau <marc-andre.laverdiere-papineau at polymtl.ca>
To: soot-list at sable.mcgill.ca
Cc:
Sent: Thursday, April 25, 2013 12:39 AM
Subject: Re: [Soot-list] What kind of analysis is appropriate?
Hello,
Looking at your requirements, it looks like information flow is enough.
Aliasing would not be enough, I think, because propagation by other
means than assignment wouldn't be taken in consideration.
Slicing risks being overkill for your needs: you get a subset of the
original program, with all the statements that depend on the 'seed'
statement (your input). If you are interested in e.g. the body of the
else branch on which your input is used as a condition, then slicing is
a good tool.
Nevertheless, if you want to learn more about slicing, I suggest to read
the TAJ paper from IBM Research.
www.cs.tau.ac.il/~omertrip/pldi09/paper.pdf
Marc-André Laverdière-Papineau
Doctorant - PhD Candidate
On 04/24/2013 02:22 AM, Zeinab Lashkaripour wrote:
> Hi,
> Thank you Marc-André and Eric for your replies and sorry for my delay I
> was a bit busy.
> Consider the function bellow:
> (I should mention that by loop I mean both loops and if-else statements)
> fn (input1)
> {
> loop with condition related to input -----> direct / indirect / not
> related
> {
> string that can use the input either direct or indirect
> }
> }
>
> I might have the situations bellow that I want to extract these parts
> and use them for adding transformation:
> 1: no loop only the string that uses the input (direct or indirect) -> I
> want that string
> 2. loop's condition is not related to the input but has a string that
> uses the input inside the loop -> I want that string
> 3. loop's condition is related to the input (direct or indirect) but has
> no string that uses the input inside the loop -> I want that condition
> 4. loop's condition is related to the input (direct or indirect) and has
> a string that uses the input inside the loop -> I want that condition
> and the string
>
> As I said loops might be if-else statements therefore there might be an
> else and that should be considered too.
>
> Thanks in advance
> Regards
> Zeinab
> ------------------------------------------------------------------------
> *From:* "Bodden, Eric" <eric.bodden at sit.fraunhofer.de>
> *To:* Marc-André Laverdière-Papineau
> <marc-andre.laverdiere-papineau at polymtl.ca>
> *Cc:* "soot-list at sable.mcgill.ca" <soot-list at sable.mcgill.ca>
> *Sent:* Tuesday, April 23, 2013 11:33 AM
> *Subject:* Re: [Soot-list] What kind of analysis is appropriate?
>
> Hi all.
>
> To me it sounds like Zeinab is really looking for something like
> slicing, not alias analysis. But it really depends on what is meant by
> "related to the inputs". Zeinab could you clarify?
>
> Eric
>
>
>
> On 22.04.2013, at 16:46, Marc-André Laverdière-Papineau
> <marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>> wrote:
>
> > Hello,
> >
> > I wasn't clear I guess.
> >
> > a = secret()
> > b = a
> > c = b
> > print(c)
> >
> > That can be solved with a plain and simple alias analysis. C aliases a,
> > things are simple.
> >
> > Flow analysis is more useful when you have things like this:
> >
> > a = secret
> > b = propagatingFn(a)
> > c = anotherPropagatingFn(b)
> > print(c)
> >
> > Back to your question, you are asking something important. My
> > understanding of alias analysis is that the alias information takes this
> > information in consideration.
> >
> > Suppose we have
> > 1 a = secret()
> > 2 a = "harcoded constant"
> > 3 b = a
> > 4 c = b
> > 5 print(c)
> >
> > The alias information for c at line 5 should be 2,3,4.
> >
> > Compiler people: please tell me if I'm wrong on this. I don't really
> > touch that part of compiler theory often ;)
> >
> > Marc-André Laverdière-Papineau
> > Doctorant - PhD Candidate
> >
> > On 13-04-20 07:30 AM, Zeinab Lashkaripour wrote:
> >>
> >> Thanks Marc-André,
> >>
> >>> It sounds to me like you are interested in doing an intraprocedural
> >> alias analysis. And intersect the results with the loop conditions.
> >>
> >> Yes, your right but it might change to interprocedural (for now its
> intra).
> >>
> >>> ...then an information flow analysis would make sense.
> >>
> >> As I understand, you mean that I need a flow-based alias analysis?
> >>
> >> I should mention that I am looking for special strings that use the
> >> parameter of the function that they are inside (these strings can be
> >> identified easily). Therefore the things I need after identifying these
> >> strings are: loop conditions and local variables that have used the
> >> parameter. As you said alias analysis is suitable but,does reaching
> >> definition (UD chain) need to be used beside alias analysis or does
> >> flow-based alias analysis do the work by it self?
> >>
> >> Thanks in advance,
> >> Zeinab
> >>
> >> ------------------------------------------------------------------------
> >> *From:* Marc-André Laverdière-Papineau
> >> <marc-andre.laverdiere-papineau at polymtl.ca
> <mailto:marc-andre.laverdiere-papineau at polymtl.ca>>
> >> *To:* soot-list at sable.mcgill.ca <mailto:soot-list at sable.mcgill.ca>
> >> *Sent:* Saturday, April 20, 2013 6:11 AM
> >> *Subject:* Re: [Soot-list] What kind of analysis is appropriate?
> >>
> >> Hello,
> >>
> >> It sounds to me like you are interested in doing an intraprocedural
> >> alias analysis. And intersect the results with the loop conditions.
> >>
> >> Of course, if you want to handle cases where there could be operations
> >> other than assignment of the variables, then an information flow
> >> analysis would make sense.
> >>
> >> Soot provides classes that computes de CFG for you (ExceptionalUnitGraph
> >> IIRC), and there is a built-in LocalMustAliasAnalysis that should do the
> >> trick. Note that I haven't used those classes personally, so I could be
> >> wrong.
> >>
> >> Marc-André Laverdière-Papineau
> >> Doctorant - PhD Candidate
> >>
> >> On 13-04-19 01:13 PM, Zeinab Lashkaripour wrote:
> >>> Hi everyone,
> >>>
> >>> I have done part of my analysis with Soot and for the rest of it I'm
> >>> looking for the following information that I don't know what kind of
> >>> analysis is suitable?
> >>>
> >>> I have some functions that they have inputs. In these functions these
> >>> inputs can be used in local variables of the function, inside loop
> >>> conditions.
> >>> I want to identify those local variables that have used these
> inputs and
> >>> also process loop conditions to see if they are related to the input or
> >>> not. (relation with input in condition and local variable can be direct
> >>> or indirect)
> >>>
> >>> Regards,
> >>> Zeinab
> >>>
> >>>
> >>> _______________________________________________
> >>> 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>
> > http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>
> --
> Eric Bodden, Ph.D., http://sse.ec-spride.de/
> <http://sse.ec-spride.de/>http://bodden.de/
> Head of Secure Software Engineering Group at EC SPRIDE
> Tel: +49 6151 16-75422 Fax: +49 6151 16-72051
> Room 3.2.14, Mornewegstr. 30, 64293 Darmstadt
>
> _______________________________________________
> 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
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20130424/c422a31c/attachment.html
More information about the Soot-list
mailing list