[Soot-list] Data Flow Analysis Question

[Marc-Andre Laverdiere-Papineau]

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 
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.

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.

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 and 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é Laverdière <marc-andre.laverdiere-papineau at polymtl.ca> wrote:
>
>> Hello,
>>
>> For this type of analysis, I suggest using the Heros IDE solver. Soot has intraprocedural analyses by default.
>> --
>> Marc-André Laverdière
>> PhD Candidate - Doctorant
>> Sent from a mobile device - please excuse the brevity
>>
>> Henddher Pedroza <hpedro2 at 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/) 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 as
>>> 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 modifies
>>> 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 at sable.mcgill.ca
>>> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>>
>
>


-- 
Marc-André Laverdière-Papineau
Doctorant - PhD Candidate