[Soot-list] What kind of analysis is appropriate?

Wed Apr 24 02:22:22 EDT 2013

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> 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>
>> *To:* 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>
>>> 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
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list

--
Eric Bodden, Ph.D., 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
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/20130423/be04c216/attachment.html 