[Soot-list] Call Graph issues and advice needed

[Marc-André Laverdière-Papineau]

Hello,

I wonder how we could handle that. My first impression is to generate 
the combinations, but that would lead us straight into combinatorial 
explosion...

Any suggestion?

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

On 04/28/2013 07:22 AM, Rohan Padhye wrote:
> Hello Bernhard,
>
> Yes that makes sense. However, wouldn't you be missing certain
> side-effects due to inter-leaving of intermediate instructions if
> multiple calls were to be run simultaneously in different threads? I
> thought the analysis was considering isolated entry points without
> object sharing or inter-dependent effects which is why I suggested the
> switch-case only stub.
>
> If they are run in combination then there can be so many more orderings
> than just an external loop around the entry points!
>
> Please clarify.
>
> Regards,
> Rohan
>
> On 2013-04-28 16:46, Bernhard Berger wrote:
>> Dear Rohan,
>>
>> the usage of the loop depends on the "lifecycle" of the component you
>> are using. A servlet for instance, is called multiple times during
>> its
>> lifetime. Each call can be trigger a different method (doGet, doPost,
>> … for HttpServlet). If you skip the loop you may miss some
>> side-effects of a certain combination of calls.
>>
>> Regards,
>>
>> Bernhard
>>
>> Am 28.04.2013 um 12:54 schrieb Rohan Padhye
>> <rohanpadhye at cse.iitb.ac.in>:
>>
>>> Dear Henndher,
>>>
>>> You might also want to take a look at Marc-André's suggestion of
>>> using
>>> a switch-case in the stub main to simulate unordered entry points:
>>>
>>> main(){
>>>    switch(...) {
>>>      case 1: e1(); break;
>>>      case 2: e2(); break;
>>>    }
>>> }
>>>
>>> This might allow you to run just a single IFDS solution to get the
>>> merged results directly.
>>>
>>> Note: Marc-André originally suggested a switch-case loop, although I
>>> think the same effect can be achieved without the loop as you just
>>> want
>>> to simulate multiple distinct entry points.
>>>
>>> Regards,
>>> Rohan
>>>
>>> On 2013-04-27 19:53, Henddher Pedroza wrote:
>>>> Thank you Bernhard,
>>>>
>>>> Rohan Padhye noted this:
>>>>
>>>> main() {
>>>>    e1();
>>>>    e2();
>>>> }
>>>>
>>>> e1() {
>>>>    x = 10;
>>>> }
>>>>
>>>> e2() {
>>>>    use x;
>>>> }
>>>>
>>>> If you use a stub main then your analysis might conclude that x =
>>>> 10
>>>> is constant at e2(), but that is not the case if the program starts
>>>> at
>>>> e2(). In IFDS terms, you really want results of thread starting at
>>>> e2
>>>> to compute reachability from the zero node only, not all nodes that
>>>> are true at the exit of the thread starting at e1.
>>>>
>>>> You would probably be better off performing multiple IFDS
>>>> solutions,
>>>> one for each entry point, and then merging results for each program
>>>> point across all such instances if you want to do some
>>>> optimizations.
>>>>
>>>> If I understood correctly, one would need to generate entry points
>>>> per thread and compute IFDS on each set.
>>>>
>>>> Thanks again.
>>>>
>>>> On Apr 27, 2013, at 9:06 AM, Bernhard Berger <berber at tzi.de> wrote:
>>>>
>>>>> Hi,
>>>>>
>>>>>> As for the non-static entry point stuff, I'm going to ask
>>>>>> Bernhard
>>>>>> to
>>>>>> elaborate on that, because he dealt with it a whole lot more than
>>>>>> I
>>>>>> did.
>>>>>> IIRC it was because of the this pointer.
>>>>>>
>>>>>> My guess is that you could patch Spark to deal with it by using
>>>>>> CHA
>>>>>> to
>>>>>> resolve the this pointer whenever you have a non-static entry
>>>>>> point.
>>>>>> After all, you don't have any extra information at that point to
>>>>>> know
>>>>>> what you're pointing to…
>>>>>
>>>>> a year or two ago I tried to use the entry point mechanism to get
>>>>> a
>>>>> call graph of android components. I used probe to dump and check
>>>>> the
>>>>> results of the cg construction and observed that calls where
>>>>> missing.
>>>>> AFAIR there were entry methods that called another method within
>>>>> the
>>>>> class (this.foobar()) and they were missing. Furthermore there
>>>>> were
>>>>> problems with calls on the parameters. I never debugged it but I
>>>>> inferred that the reason is that there is information missing on
>>>>> the
>>>>> concrete type of this and the parameters. At this point I switched
>>>>> to
>>>>> entry point generation (creating a dummy main, creating the
>>>>> objects
>>>>> and parameters and call the methods).
>>>>>
>>>>> Regards,
>>>>> Bernhard
>>>>>
>>>>> _______________________________________________
>>>>> 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
>>>
>>> --
>>> Regards,
>>> Rohan Padhye
>>> _______________________________________________
>>> 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
>