[prev in list] [next in list] [prev in thread] [next in thread]
List: soot-list
Subject: Re: [Soot-list] Data Flow Analysis Question
From: Henddher Pedroza <hpedro2 () uic ! edu>
Date: 2013-03-26 16:22:03
Message-ID: CANnsA+wP6d83OogxVUjGzarXSB8xo-3C06v2njTji6VoK28N1w () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
Thank you Marc-Andr=E9.
That's all I was looking for. I see why heros is key.
Thanks again once more.
Henddher
On Mar 26, 2013 11:03 AM, "Marc-Andre Laverdiere-Papineau" <
marc-andre.laverdiere-papineau@polymtl.ca> wrote:
> Hello,
>
> The challenge of interprocedural analysis involves 'connecting' the flows=
.
> Some people use inlining, but that makes your graph explode.
> The other option is mapping the pointers, but that's not so trivial.
>
> The next issue is context insensitivity vs context sensitivity.
>
> If you read the litterature on interprocedural analysis, you'll see that
> its not the challenges that are missing. So you're setting yourself for a
> lot of work.
>
> Of course, some of that work is done for you by Spark, making your life
> easier, but that's not really down to 'easy'.
>
> Anyways, in case you really really want to go ahead without Heros, you ca=
n
> look at any class that implements SceneTransformer (mostly Spark, wjtp an=
d
> wjop). There are few analyses in the code base but it can give you ideas =
on
> how to get started.
>
> Heros implements the IFDS/IDE framework that really makes interprocedural
> analyses easier, in both the mental-strain sense, and in the coding sense=
.
> You just need to implement a flow function factory for 4 cases and let th=
e
> solver do its magic. And it is has the bindings to work with Soot.
>
> I have never tried to analyze any Android stuff, but I know that some
> people in the ML have touched that, so it "should work"
>
> On 2013-03-26 09:59, Henddher Pedroza wrote:
>
>> Thank you Marc-Andre.
>>
>> I will look into Heros.
>>
>> So using Soot for inter-procedural analysis is discouraged because it
>> would require significant amount of work (connecting intra-procedural an=
d
>> inter-procedural)?
>>
>> I didn't mention this in my previous email but the taint analysis I am
>> trying to pursue involves Android. Would that be an issue with Heros?
>>
>> Thanks again.
>>
>> - Henddher
>>
>> On Mar 26, 2013, at 7:41 AM, Marc-Andr=E9 Laverdi=E8re <
>> marc-andre.laverdiere-**papineau@polymtl.ca<marc-andre.laverdiere-papine=
au@polymtl.ca>>
>> wrote:
>>
>> Hello,
>>>
>>> For this type of analysis, I suggest using the Heros IDE solver. Soot
>>> has intraprocedural analyses by default.
>>> --
>>> Marc-Andr=E9 Laverdi=E8re
>>> PhD Candidate - Doctorant
>>> Sent from a mobile device - please excuse the brevity
>>>
>>> Henddher Pedroza <hpedro2@uic.edu> wrote:
>>>
>>> Hello Soot people:
>>>>
>>>> I am trying to understand how to do a taint analysis with Soot 2.5.2. =
I
>>>> presume I would implement a data flow analysis of some kind. Right?
>>>>
>>>> I went over the examples (http://www.bodden.de/tag/**soot-tutorial/<ht=
tp://www.bodden.de/tag/soot-tutorial/>)
>>>> and
>>>> also looked at few of the existing flow analysis:
>>>> SimpleMethodInfoFlowAnalysis, SynchronizedRegionFinder.
>>>>
>>>> Here is my concern:
>>>>
>>>> Consider I have a class MyClass which uses a library class
>>>> LibraryClass. LibraryClass has methods that take an object reference a=
s
>>>> parameter and as a "side-effect" they may modify the object because
>>>> they invoke methods on the object per se, and these may modify the
>>>> internals of the object. For example:
>>>>
>>>> interface Incrementable {
>>>> void incr();
>>>> }
>>>>
>>>> class MyClass implements Incrementable {
>>>> private int counter;
>>>> public void incr() { counter++; }
>>>>
>>>> // This is my entry point for Taint analysis
>>>> public void taintAnalysisEntryPoint() {
>>>> LibraryClass.doSomething(this)**;
>>>> LibraryClass.**doSomethingNative(this);
>>>> }
>>>> }
>>>>
>>>> class LibraryClass {
>>>> public static void doSomething(Incrementable i) {
>>>> i.incr();
>>>> doSomethingNative(i);
>>>> }
>>>> public native void doSomethingNative(**Incrementable i); // This also
>>>> calls i.incr() but from native code.
>>>> }
>>>>
>>>> As you can see, MyClass (also an Incrementable) is passed as param to
>>>> LibraryClass.doSomething() which calls 'incr()', which in turn modifie=
s
>>>> the instance of MyClass as side-effect. Same thing is done in the
>>>> native method LibraryClass.**doSomethingNative(). The entry point of
>>>> the
>>>> taint analysis could be known up front:
>>>> MyClass.**taintAnalysisEntryPoint()
>>>>
>>>> Though in this example I am using the concept of Incrementable, that
>>>> might not be the case in practice.
>>>>
>>>> My questions are these:
>>>> 1. Should the taint analysis perform the analysis of MyClass AND
>>>> LibraryClass so when the analysis of MyClass.**
>>>> taintAnalysisEntryPoint()
>>>> is done, the taint analysis of LibraryClass.doSomething(**
>>>> Incrementable)
>>>> is known and can be propagated correctly?
>>>> 2. What about doing taint analysis of
>>>> LibraryClass.**doSomethingNative(**Incrementable)? (this one cannot be
>>>> analyzed by Soot since the code is not available, true?).
>>>>
>>>> Any help, suggested reading, and/or examples are welcome.
>>>>
>>>> Thanks in advance.
>>>>
>>>> - Henddher
>>>>
>>>>
>>>>
>>>>
>>>> ------------------------------**------------------------------**
>>>> ------------
>>>>
>>>> ______________________________**_________________
>>>> Soot-list mailing list
>>>> Soot-list@sable.mcgill.ca
>>>> http://mailman.cs.mcgill.ca/**mailman/listinfo/soot-list<http://mailma=
n.cs.mcgill.ca/mailman/listinfo/soot-list>
>>>>
>>>
>>>
>>
>>
>
> --
> Marc-Andr=E9 Laverdi=E8re-Papineau
> Doctorant - PhD Candidate
>
>
>
[Attachment #5 (text/html)]
<p>Thank you Marc-André. </p>
<p>That's all I was looking for. I see why heros is key.</p>
<p>Thanks again once more.</p>
<p>Henddher</p>
<div class="gmail_quote">On Mar 26, 2013 11:03 AM, "Marc-Andre \
Laverdiere-Papineau" <<a \
href="mailto:marc-andre.laverdiere-papineau@polymtl.ca">marc-andre.laverdiere-papineau@polymtl.ca</a>> \
wrote:<br type="attribution"> <blockquote class="gmail_quote" style="margin:0 0 0 \
.8ex;border-left:1px #ccc solid;padding-left:1ex">Hello,<br> <br>
The challenge of interprocedural analysis involves 'connecting' the flows. \
Some people use inlining, but that makes your graph explode.<br> The other option is \
mapping the pointers, but that's not so trivial.<br> <br>
The next issue is context insensitivity vs context sensitivity.<br>
<br>
If you read the litterature on interprocedural analysis, you'll see that its not \
the challenges that are missing. So you're setting yourself for a lot of \
work.<br> <br>
Of course, some of that work is done for you by Spark, making your life easier, but \
that's not really down to 'easy'.<br> <br>
Anyways, in case you really really want to go ahead without Heros, you can look at \
any class that implements SceneTransformer (mostly Spark, wjtp and wjop). There are \
few analyses in the code base but it can give you ideas on how to get started.<br>
<br>
Heros implements the IFDS/IDE framework that really makes interprocedural analyses \
easier, in both the mental-strain sense, and in the coding sense. You just need to \
implement a flow function factory for 4 cases and let the solver do its magic. And it \
is has the bindings to work with Soot.<br>
<br>
I have never tried to analyze any Android stuff, but I know that some people in the \
ML have touched that, so it "should work"<br> <br>
On 2013-03-26 09:59, Henddher Pedroza wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex"> Thank you Marc-Andre.<br>
<br>
I will look into Heros.<br>
<br>
So using Soot for inter-procedural analysis is discouraged because it would require \
significant amount of work (connecting intra-procedural and inter-procedural)?<br> \
<br> I didn't mention this in my previous email but the taint analysis I am \
trying to pursue involves Android. Would that be an issue with Heros?<br> <br>
Thanks again.<br>
<br>
- Henddher<br>
<br>
On Mar 26, 2013, at 7:41 AM, Marc-André Laverdière <<a \
href="mailto:marc-andre.laverdiere-papineau@polymtl.ca" \
target="_blank">marc-andre.laverdiere-<u></u>papineau@polymtl.ca</a>> wrote:<br> \
<br> <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex"> Hello,<br>
<br>
For this type of analysis, I suggest using the Heros IDE solver. Soot has \
intraprocedural analyses by default.<br>
--<br>
Marc-André Laverdière<br>
PhD Candidate - Doctorant<br>
Sent from a mobile device - please excuse the brevity<br>
<br>
Henddher Pedroza <<a href="mailto:hpedro2@uic.edu" \
target="_blank">hpedro2@uic.edu</a>> wrote:<br> <br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex"> Hello Soot people:<br>
<br>
I am trying to understand how to do a taint analysis with Soot 2.5.2. I<br>
presume I would implement a data flow analysis of some kind. Right?<br>
<br>
I went over the examples (<a href="http://www.bodden.de/tag/soot-tutorial/" \
target="_blank">http://www.bodden.de/tag/<u></u>soot-tutorial/</a>) and<br> also \
looked at few of the existing flow analysis:<br> SimpleMethodInfoFlowAnalysis, \
SynchronizedRegionFinder.<br> <br>
Here is my concern:<br>
<br>
Consider I have a class MyClass which uses a library class<br>
LibraryClass. LibraryClass has methods that take an object reference as<br>
parameter and as a "side-effect" they may modify the object because<br>
they invoke methods on the object per se, and these may modify the<br>
internals of the object. For example:<br>
<br>
interface Incrementable {<br>
void incr();<br>
}<br>
<br>
class MyClass implements Incrementable {<br>
private int counter;<br>
public void incr() { counter++; }<br>
<br>
// This is my entry point for Taint analysis<br>
public void taintAnalysisEntryPoint() {<br>
LibraryClass.doSomething(this)<u></u>;<br>
LibraryClass.<u></u>doSomethingNative(this);<br>
}<br>
}<br>
<br>
class LibraryClass {<br>
public static void doSomething(Incrementable i) {<br>
i.incr();<br>
doSomethingNative(i);<br>
}<br>
public native void doSomethingNative(<u></u>Incrementable i); // This also<br>
calls i.incr() but from native code.<br>
}<br>
<br>
As you can see, MyClass (also an Incrementable) is passed as param to<br>
LibraryClass.doSomething() which calls 'incr()', which in turn modifies<br>
the instance of MyClass as side-effect. Same thing is done in the<br>
native method LibraryClass.<u></u>doSomethingNative(). The entry point of the<br>
taint analysis could be known up front:<br>
MyClass.<u></u>taintAnalysisEntryPoint()<br>
<br>
Though in this example I am using the concept of Incrementable, that<br>
might not be the case in practice.<br>
<br>
My questions are these:<br>
1. Should the taint analysis perform the analysis of MyClass AND<br>
LibraryClass so when the analysis of MyClass.<u></u>taintAnalysisEntryPoint()<br>
is done, the taint analysis of LibraryClass.doSomething(<u></u>Incrementable)<br>
is known and can be propagated correctly?<br>
2. What about doing taint analysis of<br>
LibraryClass.<u></u>doSomethingNative(<u></u>Incrementable)? (this one cannot be<br>
analyzed by Soot since the code is not available, true?).<br>
<br>
Any help, suggested reading, and/or examples are welcome.<br>
<br>
Thanks in advance.<br>
<br>
- Henddher<br>
<br>
<br>
<br>
<br>
------------------------------<u></u>------------------------------<u></u>------------<br>
<br>
______________________________<u></u>_________________<br>
Soot-list mailing list<br>
<a href="mailto:Soot-list@sable.mcgill.ca" \
target="_blank">Soot-list@sable.mcgill.ca</a><br> <a \
href="http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list" \
target="_blank">http://mailman.cs.mcgill.ca/<u></u>mailman/listinfo/soot-list</a><br> \
</blockquote> <br>
</blockquote>
<br>
<br>
</blockquote>
<br>
<br>
-- <br>
Marc-André Laverdière-Papineau<br>
Doctorant - PhD Candidate<br>
<br>
<br>
</blockquote></div>
_______________________________________________
Soot-list mailing list
Soot-list@sable.mcgill.ca
http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic