[Soot-list] about Heros

[Marc-André Laverdière-Papineau]

Hello,

I am butting in, because I had on my mind to try context sensitivity in 
IFDS at some point too...

The inherent problem with a bounded stack of context strings is that it 
is bounded :)

So the problem you mention could be hit even without recursion. I sort 
of remember algorithms to detect recursion, but I'd have to dust off my 
Dragon Book to get in the details of that.

The question is: why bother?

I am thinking that one may define an IFDS analysis that use the 
MethodOrMethodContext API and the Geometric encoding - which removes the 
need for context strings altogether.

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

On 13-04-19 09:56 AM, Rohan Padhye wrote:
> Hello Eric,
>
> That is an interesting approach. I also have a requirement of
> context-sensitive data flow values so allow me to butt into this thread.
>
> How would such a model work in the presence of recursion? Wouldn't
> bounding the call-string stack limit the precision for call sequences
> deeper than that bound? And would the algorithmic complexity increase by
> a cubic factor of the stack-bound? Or am I getting it wrong?
>
> Alternatively, if a client wants to query whether a data flow fact "x"
> holds at a point "p" along a particular call-sequence "c_1...c_k", would
> it make sense (this is just a stab in the dark, I may be absolutely
> wrong) to only compute graph reachability starting from <entry, zero> to
> <p, x> along paths that contain the call sequence "c_1...c_k"? Or is
> this an incorrect understanding?
>
> Thanks,
> Rohan
>
> On 2013-04-19 15:07, Bodden, Eric wrote:
>> Hi Zhang.
>>
>> IFDS formulates context-sensitive analysis in such a way that a
>> context is characterized by domain values, not by (method-signature
>> based) calling-context strings. You should hence design your abstract
>> domain accordingly. For instance, in case you really need a
>> calling-context string then your domain should hold a (bounded) stack
>> of those strings.
>>
>> Eric
>>
>>
>>
>> On 18.04.2013, at 17:46, Zhang Yufeng <yuffonzhang at 163.com> wrote:
>>
>>> Hi Eric,
>>> I am using Heros in my project.
>>> I have two questions about the "context-sensitive" problem.
>>>
>>> The first question:
>>> In my IFDS problem,
>>> in implementing the function
>>> public FlowFunction<Local> getNormalFlowFunction(Unit curr, Unit
>>> succ) {}
>>> I need to know the context about where the method including 'curr'
>>> is invoked.
>>>
>>> In my problem, the operations on the Domain D for the same unit are
>>> different in different context.
>>> For example, in the following fuction:
>>>
>>> void foo() {
>>> obj1=obj2;
>>> }
>>>
>>> for statement
>>> obj1=obj2;
>>>
>>> the operation on the 'facts' in the domain 'D' is different in the
>>> different context (where the function foo() is invoked).
>>>
>>> But in the function
>>> public FlowFunction<Local> getNormalFlowFunction(Unit curr, Unit
>>> succ) {}
>>> there is no information indicating that the curr unit is encountered
>>> under what context.
>>>
>>> Can I do this in Heros?
>>>
>>>
>>> The second question is also about the context-sensitive problem.
>>> After I get the results by solving the IFDS problem.
>>> I can get the result at each unit by using:
>>> solver.resultsAt((Stmt)unit);
>>> right?
>>> My question is:
>>> does Heros keep the context-sensitive information in the results?
>>> In some cases, the results at the same unit are different in
>>> different context.
>>> How can I get this from Heros?
>>>
>>> I don't know whether I make it clear.
>>>
>>> Thanks.
>>> Best.
>>> Yufeng
>>> _______________________________________________
>>> 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
>
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>