[StaticAnalyzer] How to give hint on path execution

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

[StaticAnalyzer] How to give hint on path execution

Nat! via cfe-dev
Hi,

I wrote a checker similar to the  SimpleStreamChecker except that the close function that moves the state of the stream to released,  takes a second parameter, a callback, for instance

close(FILE *, mycallback). 

When the stream moves to release state, the callback is executed. 

The "close" function is defined externally so that the checker cannot reason on it except using the rules I give it in checkPostCall callback. How can I make the analyzer  aware that the callback has to be executed when the state move to release?

Thanks for any help,

Paul

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [StaticAnalyzer] How to give hint on path execution

Nat! via cfe-dev
Unfortunately, allowing checkers to trigger an immediate inlining of a
function is quite tricky to implement, and we don't have a ready-made
mechanism for that (though some of the existing checkers could make use
of such functionality).

It might theoretically be possible, within a checker callback, to
manually construct an exploded graph node that represents entering a
stack frame of the callback function, and then addTransition() to such
node (similarly to how ExprEngine does that) and see what happens.
That'd be an interesting problem to tackle, and such mechanism would be
good to have.

Also, are you sure it is necessary to model the callback exactly in your
use case? Maybe a simple invalidation/escape pass would suffice to avoid
false positives?


On 5/7/17 11:03 PM, Paul Bert via cfe-dev wrote:

> Hi,
>
> I wrote a checker similar to the  SimpleStreamChecker except that the
> close function that moves the state of the stream to released,  takes
> a second parameter, a callback, for instance
>
> close(FILE *, mycallback).
>
> When the stream moves to release state, the callback is executed.
>
> The "close" function is defined externally so that the checker cannot
> reason on it except using the rules I give it in checkPostCall
> callback. How can I make the analyzer  aware that the callback has to
> be executed when the state move to release?
>
> Thanks for any help,
>
> Paul
>
>
> _______________________________________________
> cfe-dev mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [StaticAnalyzer] How to give hint on path execution

Nat! via cfe-dev
Yay: It turns out that it might be a lot easier to accomplish with body
farms(!)

Generally, the idea is to provide a fake body instead of the unavailable
body of your close() function which would probably look like:

   void close(FILE *fp, void (*callback)(void)) {
     fclose(fp);
     callback();
   }

See how, for example, dispatch_sync() is modeled in
lib/Analysis/BodyFarm.cpp.

Once you have a fake body, the path-sensitive engine would be able to
execute it with the desired effect. It's much easier than what i
originally proposed.

Adding Gábor because it's his realm :)

On 5/8/17 8:08 PM, Artem Dergachev wrote:

> Unfortunately, allowing checkers to trigger an immediate inlining of a
> function is quite tricky to implement, and we don't have a ready-made
> mechanism for that (though some of the existing checkers could make
> use of such functionality).
>
> It might theoretically be possible, within a checker callback, to
> manually construct an exploded graph node that represents entering a
> stack frame of the callback function, and then addTransition() to such
> node (similarly to how ExprEngine does that) and see what happens.
> That'd be an interesting problem to tackle, and such mechanism would
> be good to have.
>
> Also, are you sure it is necessary to model the callback exactly in
> your use case? Maybe a simple invalidation/escape pass would suffice
> to avoid false positives?
>
>
> On 5/7/17 11:03 PM, Paul Bert via cfe-dev wrote:
>> Hi,
>>
>> I wrote a checker similar to the  SimpleStreamChecker except that the
>> close function that moves the state of the stream to released,  takes
>> a second parameter, a callback, for instance
>>
>> close(FILE *, mycallback).
>>
>> When the stream moves to release state, the callback is executed.
>>
>> The "close" function is defined externally so that the checker cannot
>> reason on it except using the rules I give it in checkPostCall
>> callback. How can I make the analyzer  aware that the callback has to
>> be executed when the state move to release?
>>
>> Thanks for any help,
>>
>> Paul
>>
>>
>> _______________________________________________
>> cfe-dev mailing list
>> [hidden email]
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [StaticAnalyzer] How to give hint on path execution

Nat! via cfe-dev
+ Gabor, who worked on extending body farms last

> On May 8, 2017, at 1:06 PM, Artem Dergachev via cfe-dev <[hidden email]> wrote:
>
> Yay: It turns out that it might be a lot easier to accomplish with body farms(!)
>
> Generally, the idea is to provide a fake body instead of the unavailable body of your close() function which would probably look like:
>
>  void close(FILE *fp, void (*callback)(void)) {
>    fclose(fp);
>    callback();
>  }
>
> See how, for example, dispatch_sync() is modeled in lib/Analysis/BodyFarm.cpp.
>
> Once you have a fake body, the path-sensitive engine would be able to execute it with the desired effect. It's much easier than what i originally proposed.
>
> Adding Gábor because it's his realm :)
>
> On 5/8/17 8:08 PM, Artem Dergachev wrote:
>> Unfortunately, allowing checkers to trigger an immediate inlining of a function is quite tricky to implement, and we don't have a ready-made mechanism for that (though some of the existing checkers could make use of such functionality).
>>
>> It might theoretically be possible, within a checker callback, to manually construct an exploded graph node that represents entering a stack frame of the callback function, and then addTransition() to such node (similarly to how ExprEngine does that) and see what happens. That'd be an interesting problem to tackle, and such mechanism would be good to have.
>>
>> Also, are you sure it is necessary to model the callback exactly in your use case? Maybe a simple invalidation/escape pass would suffice to avoid false positives?
>>
>>
>> On 5/7/17 11:03 PM, Paul Bert via cfe-dev wrote:
>>> Hi,
>>>
>>> I wrote a checker similar to the  SimpleStreamChecker except that the close function that moves the state of the stream to released,  takes a second parameter, a callback, for instance
>>>
>>> close(FILE *, mycallback).
>>>
>>> When the stream moves to release state, the callback is executed.
>>>
>>> The "close" function is defined externally so that the checker cannot reason on it except using the rules I give it in checkPostCall callback. How can I make the analyzer  aware that the callback has to be executed when the state move to release?
>>>
>>> Thanks for any help,
>>>
>>> Paul
>>>
>>>
>>> _______________________________________________
>>> cfe-dev mailing list
>>> [hidden email]
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>
>
> _______________________________________________
> cfe-dev mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [StaticAnalyzer] How to give hint on path execution

Nat! via cfe-dev
Hi!

I think this is a great use case for the body farm!

There is one possible mistake that is easy to make when one uses this feature. (Which does not affect your example, so do not worry about that. I just wanted to share this for future reference.)

Let's imagine you have an API call like:

func(int *,  void (*callback)(void))

If you provide a fake body like:
void func(int *, void (*callback)(void)) {
  callback();
}

This can introduce false positives. The reason is the following:
* When you do not have a fake body, the memory region that is pointed by the first argument is invalidated (pointer escape happens).
* When you have the fake body, pointer escape won't happen, the analyzer will derive from the fake body that the first argument is unchanged

The proper way to model something like this:
void func(int *p, void (*callback)(void)) {
  void unknownFunction(int*);
  unknownFunction(p);
  callback();
}

So the call to unknownFunction (which has no body) will trigger the pointer escape.

Regards,
Gábor

On 10 May 2017 at 07:44, Anna Zaks <[hidden email]> wrote:
+ Gabor, who worked on extending body farms last

> On May 8, 2017, at 1:06 PM, Artem Dergachev via cfe-dev <[hidden email]> wrote:
>
> Yay: It turns out that it might be a lot easier to accomplish with body farms(!)
>
> Generally, the idea is to provide a fake body instead of the unavailable body of your close() function which would probably look like:
>
>  void close(FILE *fp, void (*callback)(void)) {
>    fclose(fp);
>    callback();
>  }
>
> See how, for example, dispatch_sync() is modeled in lib/Analysis/BodyFarm.cpp.
>
> Once you have a fake body, the path-sensitive engine would be able to execute it with the desired effect. It's much easier than what i originally proposed.
>
> Adding Gábor because it's his realm :)
>
> On 5/8/17 8:08 PM, Artem Dergachev wrote:
>> Unfortunately, allowing checkers to trigger an immediate inlining of a function is quite tricky to implement, and we don't have a ready-made mechanism for that (though some of the existing checkers could make use of such functionality).
>>
>> It might theoretically be possible, within a checker callback, to manually construct an exploded graph node that represents entering a stack frame of the callback function, and then addTransition() to such node (similarly to how ExprEngine does that) and see what happens. That'd be an interesting problem to tackle, and such mechanism would be good to have.
>>
>> Also, are you sure it is necessary to model the callback exactly in your use case? Maybe a simple invalidation/escape pass would suffice to avoid false positives?
>>
>>
>> On 5/7/17 11:03 PM, Paul Bert via cfe-dev wrote:
>>> Hi,
>>>
>>> I wrote a checker similar to the  SimpleStreamChecker except that the close function that moves the state of the stream to released,  takes a second parameter, a callback, for instance
>>>
>>> close(FILE *, mycallback).
>>>
>>> When the stream moves to release state, the callback is executed.
>>>
>>> The "close" function is defined externally so that the checker cannot reason on it except using the rules I give it in checkPostCall callback. How can I make the analyzer  aware that the callback has to be executed when the state move to release?
>>>
>>> Thanks for any help,
>>>
>>> Paul
>>>
>>>
>>> _______________________________________________
>>> cfe-dev mailing list
>>> [hidden email]
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>
>
> _______________________________________________
> cfe-dev mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev



_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [StaticAnalyzer] How to give hint on path execution

Paul Bert
This post has NOT been accepted by the mailing list yet.
Hi!

Thank you for your very useful input, both of you!
However, it is not clear to me how I should proceed. At which stage of the analysis should I do this?
If we take the example below:
func(int *,  void (*callback)(void))

Should I implement the callback checkBeginFunction and when I hit 'func', create the body?
Will the analyzer pick the definition on the fly? Or maybe at checkPreCall?
It is not clear to me how this get inserted properly in the ExplodedGraph.
Also, I don't see in the clang code base any user of BodyFarm.cpp's defined classes.

Thanks for your help

Paul
Reply | Threaded
Open this post in threaded view
|

[StaticAnalyzer] How to give hint on path execution

Nat! via cfe-dev
In reply to this post by Nat! via cfe-dev
Hi! 

Thank you for your very useful input, both of you! 
However, it is not clear to me how I should proceed. At which stage of the analysis should I do this? 
If we take the example below: 
func(int *,  void (*callback)(void)) 

Should I implement the callback checkBeginFunction and when I hit 'func', create the body? 
Will the analyzer pick the definition on the fly? Or maybe at checkPreCall? 
It is not clear to me how this get inserted properly in the ExplodedGraph. 
Also, I don't see in the clang code base any user of BodyFarm.cpp's defined classes. 

Thanks for your help
Paul



Le mercredi 10 mai 2017, Gábor Horváth <<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;xazax.hun@gmail.com&#39;);" target="_blank">xazax.hun@...> a écrit :
Hi!

I think this is a great use case for the body farm!

There is one possible mistake that is easy to make when one uses this feature. (Which does not affect your example, so do not worry about that. I just wanted to share this for future reference.)

Let's imagine you have an API call like:

func(int *,  void (*callback)(void))

If you provide a fake body like:
void func(int *, void (*callback)(void)) {
  callback();
}

This can introduce false positives. The reason is the following:
* When you do not have a fake body, the memory region that is pointed by the first argument is invalidated (pointer escape happens).
* When you have the fake body, pointer escape won't happen, the analyzer will derive from the fake body that the first argument is unchanged

The proper way to model something like this:
void func(int *p, void (*callback)(void)) {
  void unknownFunction(int*);
  unknownFunction(p);
  callback();
}

So the call to unknownFunction (which has no body) will trigger the pointer escape.

Regards,
Gábor

On 10 May 2017 at 07:44, Anna Zaks <[hidden email]> wrote:
+ Gabor, who worked on extending body farms last

> On May 8, 2017, at 1:06 PM, Artem Dergachev via cfe-dev <[hidden email]> wrote:
>
> Yay: It turns out that it might be a lot easier to accomplish with body farms(!)
>
> Generally, the idea is to provide a fake body instead of the unavailable body of your close() function which would probably look like:
>
>  void close(FILE *fp, void (*callback)(void)) {
>    fclose(fp);
>    callback();
>  }
>
> See how, for example, dispatch_sync() is modeled in lib/Analysis/BodyFarm.cpp.
>
> Once you have a fake body, the path-sensitive engine would be able to execute it with the desired effect. It's much easier than what i originally proposed.
>
> Adding Gábor because it's his realm :)
>
> On 5/8/17 8:08 PM, Artem Dergachev wrote:
>> Unfortunately, allowing checkers to trigger an immediate inlining of a function is quite tricky to implement, and we don't have a ready-made mechanism for that (though some of the existing checkers could make use of such functionality).
>>
>> It might theoretically be possible, within a checker callback, to manually construct an exploded graph node that represents entering a stack frame of the callback function, and then addTransition() to such node (similarly to how ExprEngine does that) and see what happens. That'd be an interesting problem to tackle, and such mechanism would be good to have.
>>
>> Also, are you sure it is necessary to model the callback exactly in your use case? Maybe a simple invalidation/escape pass would suffice to avoid false positives?
>>
>>
>> On 5/7/17 11:03 PM, Paul Bert via cfe-dev wrote:
>>> Hi,
>>>
>>> I wrote a checker similar to the  SimpleStreamChecker except that the close function that moves the state of the stream to released,  takes a second parameter, a callback, for instance
>>>
>>> close(FILE *, mycallback).
>>>
>>> When the stream moves to release state, the callback is executed.
>>>
>>> The "close" function is defined externally so that the checker cannot reason on it except using the rules I give it in checkPostCall callback. How can I make the analyzer  aware that the callback has to be executed when the state move to release?
>>>
>>> Thanks for any help,
>>>
>>> Paul
>>>
>>>
>>> _______________________________________________
>>> cfe-dev mailing list
>>> [hidden email]
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>
>
> _______________________________________________
> cfe-dev mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev



_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [StaticAnalyzer] How to give hint on path execution

Nat! via cfe-dev
Hi Paul!

On 11 May 2017 at 10:05, Paul Bert via cfe-dev <[hidden email]> wrote:
Hi! 

Thank you for your very useful input, both of you! 
However, it is not clear to me how I should proceed. At which stage of the analysis should I do this? 
If we take the example below: 
func(int *,  void (*callback)(void)) 

Should I implement the callback checkBeginFunction and when I hit 'func', create the body? 
Will the analyzer pick the definition on the fly? Or maybe at checkPreCall? 
It is not clear to me how this get inserted properly in the ExplodedGraph. 
Also, I don't see in the clang code base any user of BodyFarm.cpp's defined classes. 

Unfortunately you do not really have control of this from the checker. So in case you want to
model some functions with fake function bodies you need to maintain a separate patch on
clang.

It will be invoked by AnalysisDeclContext, which is used to get the body of
a function which is used by the analyzer to determine the function body to
analyze.

So once you add the code to build the AST for your fake body and extend
the getBody method of BodyFarm, you should be ready.

Regards,
Gábor

 


Thanks for your help
Paul




Le mercredi 10 mai 2017, Gábor Horváth <[hidden email]> a écrit :
Hi!

I think this is a great use case for the body farm!

There is one possible mistake that is easy to make when one uses this feature. (Which does not affect your example, so do not worry about that. I just wanted to share this for future reference.)

Let's imagine you have an API call like:

func(int *,  void (*callback)(void))

If you provide a fake body like:
void func(int *, void (*callback)(void)) {
  callback();
}

This can introduce false positives. The reason is the following:
* When you do not have a fake body, the memory region that is pointed by the first argument is invalidated (pointer escape happens).
* When you have the fake body, pointer escape won't happen, the analyzer will derive from the fake body that the first argument is unchanged

The proper way to model something like this:
void func(int *p, void (*callback)(void)) {
  void unknownFunction(int*);
  unknownFunction(p);
  callback();
}

So the call to unknownFunction (which has no body) will trigger the pointer escape.

Regards,
Gábor

On 10 May 2017 at 07:44, Anna Zaks <[hidden email]> wrote:
+ Gabor, who worked on extending body farms last

> On May 8, 2017, at 1:06 PM, Artem Dergachev via cfe-dev <[hidden email]> wrote:
>
> Yay: It turns out that it might be a lot easier to accomplish with body farms(!)
>
> Generally, the idea is to provide a fake body instead of the unavailable body of your close() function which would probably look like:
>
>  void close(FILE *fp, void (*callback)(void)) {
>    fclose(fp);
>    callback();
>  }
>
> See how, for example, dispatch_sync() is modeled in lib/Analysis/BodyFarm.cpp.
>
> Once you have a fake body, the path-sensitive engine would be able to execute it with the desired effect. It's much easier than what i originally proposed.
>
> Adding Gábor because it's his realm :)
>
> On 5/8/17 8:08 PM, Artem Dergachev wrote:
>> Unfortunately, allowing checkers to trigger an immediate inlining of a function is quite tricky to implement, and we don't have a ready-made mechanism for that (though some of the existing checkers could make use of such functionality).
>>
>> It might theoretically be possible, within a checker callback, to manually construct an exploded graph node that represents entering a stack frame of the callback function, and then addTransition() to such node (similarly to how ExprEngine does that) and see what happens. That'd be an interesting problem to tackle, and such mechanism would be good to have.
>>
>> Also, are you sure it is necessary to model the callback exactly in your use case? Maybe a simple invalidation/escape pass would suffice to avoid false positives?
>>
>>
>> On 5/7/17 11:03 PM, Paul Bert via cfe-dev wrote:
>>> Hi,
>>>
>>> I wrote a checker similar to the  SimpleStreamChecker except that the close function that moves the state of the stream to released,  takes a second parameter, a callback, for instance
>>>
>>> close(FILE *, mycallback).
>>>
>>> When the stream moves to release state, the callback is executed.
>>>
>>> The "close" function is defined externally so that the checker cannot reason on it except using the rules I give it in checkPostCall callback. How can I make the analyzer  aware that the callback has to be executed when the state move to release?
>>>
>>> Thanks for any help,
>>>
>>> Paul
>>>
>>>
>>> _______________________________________________
>>> cfe-dev mailing list
>>> [hidden email]
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>
>
> _______________________________________________
> cfe-dev mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev



_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev



_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev