GSoC 2021 - Static analyzer project

GSoC 2021 - Static analyzer project

[Ankur Saini]

Hello,

While looking for some project to contribute on for GSOC 2021, I came across project about extending static analyser pass, especially the part that involve adding C++ support to it.

I have already used -fanalyzer option ( which I initially came to know about via some blog post ) a couple of times to make debugging process of some of my C projects easier and faster ( especially thanks to the part where it also provides CWE code of the error along with the error message )  but always wanted a C++ version of it ever since ( as that is the language I use the most ), and finding it as a project idea for this years GSOC sounded a perfect opportunity for me to try and contribute something to this project.

I have already built the compiler from the source code and was able to run a testsuit for it as mentioned in “Before you apply” section of the “Summer Of Code” page of gcc (https://gcc.gnu.org/wiki/SummerOfCode <https://gcc.gnu.org/wiki/SummerOfCode>),

currently I am in process of reading this ( https://gcc.gnu.org/onlinedocs/gccint/Analyzer-Internals.html#Analyzer-Internals <https://gcc.gnu.org/onlinedocs/gccint/Analyzer-Internals.html#Analyzer-Internals>) documentation to understand how things are going on under the hood and trying to make sense out of the source code of the analyzer itself with the help of it.

I have some questions before applying

- Am I on right path before applying for the project ? 

- Is there a way I can contribute some small bug fixes before applying for the real project itself 
( although I am scanning the bug tracker(https://gcc.gnu.org/bugzilla/buglist.cgi?bug_status=UNCONFIRMED&bug_status=NEW&bug_status=ASSIGNED&bug_status=SUSPENDED&bug_status=WAITING&bug_status=REOPENED&bug_status=VERIFIED&component=analyzer&product=gcc <https://gcc.gnu.org/bugzilla/buglist.cgi?bug_status=UNCONFIRMED&bug_status=NEW&bug_status=ASSIGNED&bug_status=SUSPENDED&bug_status=WAITING&bug_status=REOPENED&bug_status=VERIFIED&component=analyzer&product=gcc>) for any potential quick fix but any help in finding one would be a great ) ? 

- Is there anything else I should be aware of before applying ?

Thanks,
Ankur

Re: GSoC 2021 - Static analyzer project

[David Malcolm]

On Fri, 2021-03-05 at 17:04 +0530, Ankur Saini via Gcc wrote:
> Hello,

Hi Ankur

> While looking for some project to contribute on for GSOC 2021, I came
> across project about extending static analyser pass, especially the
> part that involve adding C++ support to it.
> 
> I have already used -fanalyzer option ( which I initially came to
> know about via some blog post ) a couple of times to make debugging
> process of some of my C projects easier and faster ( especially
> thanks to the part where it also provides CWE code of the error along
> with the error message )  but always wanted a C++ version of it ever
> since ( as that is the language I use the most ), and finding it as a
> project idea for this years GSOC sounded a perfect opportunity for me
> to try and contribute something to this project.
> 
> I have already built the compiler from the source code and was able
> to run a testsuit for it as mentioned in “Before you apply” section
> of the “Summer Of Code” page of gcc (   
> https://gcc.gnu.org/wiki/SummerOfCode <   
> https://gcc.gnu.org/wiki/SummerOfCode>),
> currently I am in process of reading this (    
> https://gcc.gnu.org/onlinedocs/gccint/Analyzer-Internals.html#Analyzer-Internals
>  <   
> https://gcc.gnu.org/onlinedocs/gccint/Analyzer-Internals.html#Analyzer-Internals
> >) documentation to understand how things are going on under the hood
> and trying to make sense out of the source code of the analyzer
> itself with the help of it.

Sounds great.

> I have some questions before applying
> 
> - Am I on right path before applying for the project ? 

What you're doing sounds like the right approach.

> - Is there a way I can contribute some small bug fixes before
> applying for the real project itself 
> ( although I am scanning the bug tracker(   
> https://gcc.gnu.org/bugzilla/buglist.cgi?bug_status=UNCONFIRMED&bug_status=NEW&bug_status=ASSIGNED&bug_status=SUSPENDED&bug_status=WAITING&bug_status=REOPENED&bug_status=VERIFIED&component=analyzer&product=gcc
>  <   
> https://gcc.gnu.org/bugzilla/buglist.cgi?bug_status=UNCONFIRMED&bug_status=NEW&bug_status=ASSIGNED&bug_status=SUSPENDED&bug_status=WAITING&bug_status=REOPENED&bug_status=VERIFIED&component=analyzer&product=gcc
> >) for any potential quick fix but any help in finding one would be a
> great ) ? 

I fear that at this point I've fixed all the easy bugs and it's only
the more difficult ones remaining :(

If you run the analyzer on your own code, and can trigger a false
positive or a false negative with the analyzer on it, and try to figure
out the issue, that could be a useful step (though it might turn out to
be a difficult one to fix, of course...)


There is a tracker bug for C++ support in the analyzer here:
  https://gcc.gnu.org/bugzilla/showdependencytree.cgi?id=97110
though obviously that would be actually doing the project itself.

To set expectations of what's reasonable to do in one summer - I don't
expect someone to be able to fully implement C++ support in one GSoC
project; for example, both of
  (a) implementing exception-handling and
  (b) implementing RTTI/vfuncs
are each probably big enough by themselves to take all summer.  So you
might want to pick one of those two to focus on (there are some notes
on each in the bugzilla comments).

> - Is there anything else I should be aware of before applying ?

I think if you've read the internals doc and the various organization
stuff on https://gcc.gnu.org/wiki/SummerOfCode page you're on the right
lines.

Hope this is helpful; good luck!

Dave

Re: GSoC 2021 - Static analyzer project

[Ankur Saini]

> On 06-Mar-2021, at 6:05 AM, David Malcolm <dmalcolm@redhat.com> wrote:
> 
> If you run the analyzer on your own code, and can trigger a false
> positive or a false negative with the analyzer on it, and try to figure
> out the issue, that could be a useful step (though it might turn out to
> be a difficult one to fix, of course…)
> 

ok, I will see what can I do

> 
> There is a tracker bug for C++ support in the analyzer here:
>  https://gcc.gnu.org/bugzilla/showdependencytree.cgi?id=97110 <https://gcc.gnu.org/bugzilla/showdependencytree.cgi?id=97110>
> though obviously that would be actually doing the project itself.
> 
> To set expectations of what's reasonable to do in one summer - I don't
> expect someone to be able to fully implement C++ support in one GSoC
> project; for example, both of
>  (a) implementing exception-handling and
>  (b) implementing RTTI/vfuncs
> are each probably big enough by themselves to take all summer.  So you
> might want to pick one of those two to focus on (there are some notes
> on each in the bugzilla comments).

thanks, I will go through them and see what suites me best

> 
>> - Is there anything else I should be aware of before applying ?
> 
> I think if you've read the internals doc and the various organization
> stuff on https://gcc.gnu.org/wiki/SummerOfCode <https://gcc.gnu.org/wiki/SummerOfCode> page you're on the right
> lines.
> 

good to hear that, so I will continue to understand the source code with help of internal docs for now and will report back when I would have successfully triggered a false positive or false negative with the analyser with it’s cause ( and if possible the fix also )

> Hope this is helpful; good luck!

> 
> Dave

thanks again,

Ankur

Re: GSoC 2021 - Static analyzer project

[Ankur Saini]

hello sir 

in my quest of finding a bug ( which ended up being a feature ) along with it’s source in the analyzer, I tested the code on these 2 code snippets and here’s how I went towards it 

(1)
int main()
{
    int *ptr = (int *)malloc(sizeof(int));
    return 0;
}

link to running example (https://godbolt.org/z/1jGW1qYez <https://godbolt.org/z/1jGW1qYez>)

(2)
int definaltly_main()
{
    int *ptr = (int *)malloc(sizeof(int));
    return 0;
}

link to running example (https://godbolt.org/z/bzjMYex4M <https://godbolt.org/z/bzjMYex4M>)


where on second snipper analyzer is warning us about the leak as it should be, but in the first one it isn’t. 

and as the gimple representation of both looks exactly the same apart from function name, which made me think that either intentionally or unintentionally, analyzer handles case of main() differently than any other function.

so while looking at it’s exploded graphs I found out that the only 2 differences in them 

1. There is one less exploded node(after node E-8) created in first one ( I earlier thought state merging or state pruning is taking place here but it isn’t because the results are not affected even after disabling those using  `-fno-analyzer-state-purge` and `-fno-analyzer-state-merge` options )

2. no diagnosis for malloc leak happening at the end of first one even though there exist a pointer in unchecked state at the end ( according to the malloc state machine )

In quest to find the cause I started navigating through the source code of the analyser starting off with the run_checkers() function in engine.cc which looks like the entry point of the analyser ( found via the commit history of the analyzer ). But finally it ended at `impl_region_model_context::on_state_leak()` function where I found out that analyzer is intentionally skipping the leak report when it is in main. 

This gave rise to some questions

1. why does the analyzer make exceptions with the main() function ?

2. even if it is not complaining about the leak then this still doesn’t explain the reason for one less exploded node in this case of main() function.

thanks

- Ankur

Re: GSoC 2021 - Static analyzer project

[David Malcolm]

On Tue, 2021-03-30 at 16:36 +0530, Ankur Saini wrote:
> hello sir 
> 
> in my quest of finding a bug ( which ended up being a feature ) along
> with it’s source in the analyzer, I tested the code on these 2 code
> snippets and here’s how I went towards it 
> 
> (1)
> int main()
> {
>     int *ptr = (int *)malloc(sizeof(int));
>     return 0;
> }
> 
> link to running example (https://godbolt.org/z/1jGW1qYez <
> https://godbolt.org/z/1jGW1qYez>)
> 
> (2)
> int definaltly_main()
> {
>     int *ptr = (int *)malloc(sizeof(int));
>     return 0;
> }
> 
> link to running example (https://godbolt.org/z/bzjMYex4M <
> https://godbolt.org/z/bzjMYex4M>)
> 
> 
> where on second snipper analyzer is warning us about the leak as it
> should be, but in the first one it isn’t. 
> 
> and as the gimple representation of both looks exactly the same apart
> from function name, which made me think that either intentionally or
> unintentionally, analyzer handles case of main() differently than any
> other function.

Correct - the analyzer special-cases "main".

Specifically, in impl_region_model_context::on_state_leak, there's this
code:
  https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/analyzer/engine.cc;h=d7866b5598b4fcb791ec6ff511dde9b7615e7794;hb=HEAD#l624

 624   /* Don't complain about leaks when returning from "main".  */
 625   if (m_enode_for_diag->get_supernode ()
 626       && m_enode_for_diag->get_supernode ()->return_p ())
 627     {
 628       tree fndecl = m_enode_for_diag->get_function ()->decl;
 629       if (id_equal (DECL_NAME (fndecl), "main"))
 630         {
 631           if (logger)
 632             logger->log ("not reporting leak from main");
 633           return;
 634         }
 635     }

on the grounds that for the resources that the analyzer currently
tracks, it doesn't matter if they aren't cleaned up as the process
exits, so we don't bother the user with a report about them.

> so while looking at it’s exploded graphs I found out that the only 2
> differences in them 
> 
> 1. There is one less exploded node(after node E-8) created in first
> one ( I earlier thought state merging or state pruning is taking
> place here but it isn’t because the results are not affected even
> after disabling those using  `-fno-analyzer-state-purge` and `-fno-
> analyzer-state-merge` options )

Well spotted.

I see that too.

For (1) EN 8, has 2 stmts, the label and the return, but for (2), it
splits them with EN: 8 having just the label, and the return split into
EN 9.

I was surprised by this and did some digging in gdb, for both (1) and
(2).  The reason seems to be rather arbitrary; specifically in (2),
stmt_requires_new_enode_p is returning true due to hitting this case:

2894	  /* If we had a PREV_STMT with an unknown location, and this stmt
2895	     has a known location, then if a state change happens here, it
2896	     could be consolidated into PREV_STMT, giving us an event with
2897	     no location.  Ensure that STMT gets its own exploded_node to
2898	     avoid this.  */
2899	  if (get_pure_location (prev_stmt->location) == UNKNOWN_LOCATION
2900	      && get_pure_location (stmt->location) != UNKNOWN_LOCATION)
2901	    return true;

and presumably it isn't hitting this for (1).

Specifically, where "stmt" is the return stmt and "prev_stmt" is the
label statement.

for (1):

(gdb) p /x stmt->location
$1 = 0x0
(gdb) p /x prev_stmt->location
$2 = 0x0

whereas for (2):

(gdb) p /x stmt->location
$5 = 0x800000f2
(gdb) p /x prev_stmt->location
$6 = 0x0

So with (1) the return stmt has UNKNOWN_LOCATION:

(gdb) call inform (stmt->location, "return stmt in (1)")
In function ‘main’:
cc1: note: return stmt in (1)

whereas for (2) the return stmt has a source location:

(gdb) call inform (stmt->location, "return stmt in (2)")
In function ‘definaltly_main’:
/tmp/2.c:6:12: note: return stmt in (2)
    6 |     return 0;
      |            ^

This slight difference in the recorded location of the return stmt for
the "main" vs non-"main" case affects the splitting of the nodes.

Athough a curiosity, I don't think this is significant.  (In theory one
could use a hardware watchpoint on stmt->location to track this
discrepancy down further, but I don't think it's important enough to
bother).


> 2. no diagnosis for malloc leak happening at the end of first one
> even though there exist a pointer in unchecked state at the end (
> according to the malloc state machine )

Correct - the analyzer specialcases "main" and ignores it, as noted
above.


> In quest to find the cause I started navigating through the source
> code of the analyser starting off with the run_checkers() function in
> engine.cc which looks like the entry point of the analyser ( found
> via the commit history of the analyzer ). But finally it ended at
> `impl_region_model_context::on_state_leak()` function where I found
> out that analyzer is intentionally skipping the leak report when it
> is in main. 

Sounds like you successfully tracked this down.

> This gave rise to some questions
> 
> 1. why does the analyzer make exceptions with the main() function ?

The user's attention is important - we don't want to spam the user with
unnecessary reports if we can help it.

> 2. even if it is not complaining about the leak then this still
> doesn’t explain the reason for one less exploded node in this case of
> main() function.

As above, it seems to be a side-effect of differences in source
locations.

> thanks
> 
> - Ankur

Hope this is helpful
Dave

Re: GSoC 2021 - Static analyzer project

[Ankur Saini]

> On 30-Mar-2021, at 7:27 PM, David Malcolm <dmalcolm@redhat.com> wrote:

>> This gave rise to some questions
>> 
>> 1. why does the analyzer make exceptions with the main() function ?
> 
> The user's attention is important - we don't want to spam the user with
> unnecessary reports if we can help it.

make sense. 

——

After fiddling around with a lot of C codes, I switched to C++ programs  in-order to find how exactly the analyzer doesn’t understand exception handling and more interestingly calls to virtual functions ( which I am thinking to work on this summer ). 

It was comparatively harder to find such an example where it would fail as looks like gcc do amazingly nice job at devirtualising the function calls ( even with -O0 option ) but finally after a lot of attempts and reading online about devirtualisation, I found this particular example where the analyzer generates a false positive

#include <cstdlib>

struct A
{
    virtual int foo (void) 
    {
        return 42;
    }
};

struct B: public A
{
    int *ptr;
    void alloc ()
    {
        ptr = (int*)malloc(sizeof(int));
    }
	int foo (void) 
    { 
        free(ptr);
        return 0;
    }
};

int test()
{
    struct B b, *bptr=&b;
    b.alloc();
    bptr->foo();
    return bptr->foo();
}

int main()
{
    test();
}

working link of the above code (https://godbolt.org/z/n17WK4MxG <https://godbolt.org/z/n17WK4MxG>)

here as the analyzer doesn’t understand the call to virtual function, wasn’t able to locate a double free in the program which was found at runtime.

so I went through it’s exploded graph to see how exactly is this being processed. And from the looks of things the anayzer doesn’t understood the function call which according to me was the following part in gimple representation :

1 = bptr_8->D.3795._vptr.A;
 _2 = *_1;
OBJ_TYPE_REF(_2;(struct B)bptr_8->0) (bptr_8)

after scanning the source-code a bit i found out that such calls were being processed by "region_model::handle_unrecognized_call()” where it just keeps track of reachable states from that node.

——

Questions 

1. The link to the bug tracker for vfunc() [ https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97114 <https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97114> ] says that for vfuncs() to be understood by anayzer, it ought to be able to devirtualize calls, but is it possible to devirtualise all the calls ? what if it is random or depends on user input ?

2. Even though analyzer didn’t understood calls to virtual function, it didn’t gave warning about a memory leak either which according to it, should exist if the functions were never called to deallocate the pointer ( after exploded node 152 and 118, the state of malloc changes automatically ) ?

sorry if I am asking a lot of questions.

Thank you

- Ankur

Re: GSoC 2021 - Static analyzer project

[David Malcolm]

On Tue, 2021-04-06 at 17:56 +0530, Ankur Saini wrote:

Hi Ankur.

Various replies inline below throughout.

> > On 30-Mar-2021, at 7:27 PM, David Malcolm <dmalcolm@redhat.com>
> > wrote:
> 
> > > This gave rise to some questions
> > > 
> > > 1. why does the analyzer make exceptions with the main() function
> > > ?
> > 
> > The user's attention is important - we don't want to spam the user
> > with
> > unnecessary reports if we can help it.
> 
> make sense. 
> 
> ——
> 
> After fiddling around with a lot of C codes, I switched to C++
> programs  in-order to find how exactly the analyzer doesn’t
> understand exception handling and more interestingly calls to virtual
> functions ( which I am thinking to work on this summer ). 

Sounds like a good focus.

> It was comparatively harder to find such an example where it would
> fail as looks like gcc do amazingly nice job at devirtualising the
> function calls ( even with -O0 option ) but finally after a lot of
> attempts and reading online about devirtualisation, I found this
> particular example where the analyzer generates a false positive
> 
> #include <cstdlib>
> 
> struct A
> {
>     virtual int foo (void) 
>     {
>         return 42;
>     }
> };
> 
> struct B: public A
> {
>     int *ptr;
>     void alloc ()
>     {
>         ptr = (int*)malloc(sizeof(int));
>     }
>         int foo (void) 
>     { 
>         free(ptr);
>         return 0;
>     }
> };
> 
> int test()
> {
>     struct B b, *bptr=&b;
>     b.alloc();
>     bptr->foo();
>     return bptr->foo();
> }
> 
> int main()
> {
>     test();
> }
> 
> working link of the above code (https://godbolt.org/z/n17WK4MxG < 
> https://godbolt.org/z/n17WK4MxG>)
> 
> here as the analyzer doesn’t understand the call to virtual function,
> wasn’t able to locate a double free in the program which was found at
> runtime.

Good work.

> so I went through it’s exploded graph to see how exactly is this
> being processed. And from the looks of things the anayzer doesn’t
> understood the function call which according to me was the following
> part in gimple representation :
> 
> 1 = bptr_8->D.3795._vptr.A;
>  _2 = *_1;
> OBJ_TYPE_REF(_2;(struct B)bptr_8->0) (bptr_8)
> 
> after scanning the source-code a bit i found out that such calls were
> being processed by "region_model::handle_unrecognized_call()” where
> it just keeps track of reachable states from that node.

Again, good detective work.

Right - the analyzer "sees" the jump through a function pointer, and it
doesn't yet have any special knowledge about what that function pointer
might be.

Given that we know we have a B, we ought to be able to assume that B::B
initializes the vtable of the instance, and make assumptions about what
the values in that vtable are.  The analyzer doesn't have any of this
special-case knowledge yet - hence bug 97114.

> ——
> 
> Questions 
> 
> 1. The link to the bug tracker for vfunc() [   
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97114 <  
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97114> ] says that for
> vfuncs() to be understood by anayzer, it ought to be able to
> devirtualize calls, but is it possible to devirtualise all the calls
> ? what if it is random or depends on user input ?

It's not possible for the general case.  Consider that there could be
other subclasses of A that we don't about in this translation unit.

But for this case, -fdump-ipa-analyzer=stderr shows this gimple at the
start of "test":

  B::B (&b);
  bptr_8 = &b;
  B::alloc (&b);
  _1 = bptr_8->D.3290._vptr.A;
  _2 = *_1;
  OBJ_TYPE_REF(_2;(struct B)bptr_8->0) (bptr_8);

As noted above, I think that we can add enough logic to the analyzer to
so that it "knows" that B::B should stores a vtable ptr, and then when
that vtable is accessed, it should know what functions are being
pointed to.  I think it would mean adding a new region subclass in the
analyzer, where an instance represents the vtable for a given class in
the user's code.

For cases where we have a "base *" and don't know which subclass the
instance is, we could potentially have the analyzer speculate about the
subclasses it knows about, adding exploded edges to speculated calls
for the various subclasses.  I don't yet know if this is a good idea,
but it seems worth experimenting with.

> 2. Even though analyzer didn’t understood calls to virtual function,
> it didn’t gave warning about a memory leak either which according to
> it, should exist if the functions were never called to deallocate the
> pointer ( after exploded node 152 and 118, the state of malloc
> changes automatically ) ?

If the analyzer "sees" a call to an unknown function (either through a
unknown function pointer, or to a function it doesn't have the body
of), it acts conservatively by resetting all of the state-machine state
for the values that are reachable by the function call, to avoid false
leak reports.  Hence it resets the state of B's ptr from the
"unchecked" allocation state back to the "start" state.

> sorry if I am asking a lot of questions.

It's fine - part of the point of GSoC is to learn, and by asking these
questions on the mailing list you're getting me to explain things here,
where everyone else can see them too, which helps improve the "bus
factor" of the analyzer.

Also, you've clearly taken the time to dig into the code and create
examples, and you are asking good questions - thanks!

Hope the above makes sense and is helpful
Dave