[Bug analyzer/105285] New: False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[Bug analyzer/105285] New: False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[avarab at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

            Bug ID: 105285
           Summary: False positive with -Wanalyzer-null-dereference in
                    git.git's reftable/reader.c
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: analyzer
          Assignee: dmalcolm at gcc dot gnu.org
          Reporter: avarab at gmail dot com
  Target Milestone: ---

Created attachment 52813
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52813&action=edit
gcc -E of reftable/reader.c

I didn't have time to come up with a nice isolated test case this time for
$subject, sorry, but (maybe this is easier):

    git clone https://github.com/git/git/
    cd git
    make CC=gcc CFLAGS=-fanalyzer reftable/reader.o

Or alternatively the gcc -E output that's attached, but most informative is the
patch I'll attach to git.git to work around this (as the code was pretty
nonsensical anyway).

Why do I think it's a false positive? It's code that's basically doing:

  struct x = { 0 }; /* "foo" member is NULL */
  if (x >= 0)
      return 0; /* early abort */
  [...]
  if (x >= 0)
      return 1; /* we don't init "x.foo" */
  x.foo

I.e. the analyzer thinks you can go through these two and for "x >= 0" to be
true the first time, and false the next, or the other way around.

In this case the types didn't have "const" on them, but to make sure these
*really* weren't being changed I added that in all the relevant places, but it
still complained. The warning was:

reftable/reader.c: In function ‘extract_block_size’:
reftable/reader.c:274:20: warning: dereference of NULL ‘data’ [CWE-476]
[-Wanalyzer-null-dereference]
  274 |         *typ = data[0];
      |                ~~~~^~~

Also, for the GCC 11.2 I have locally (I tested the warning on near-trunk GCC
12.0) I got two different warnings from -fanalyzer, so this seems to be an area
that's seen active changes recently...

[Bug analyzer/105285] False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[avarab at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

--- Comment #1 from Ævar Arnfjörð Bjarmason <avarab at gmail dot com> ---
Created attachment 52814
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52814&action=edit
A patch to git.git that works around the -fanalyzer false positive

A fix to git.git to work around the analyzer false positive, this diff on top
shows an annotated path through the program it thinks we'd take. 24 and 28
can't be true/false false/true, only false/false true/true.

diff --git a/reftable/reader.c b/reftable/reader.c
index ea66771165f..d3a4639d6ca 100644
--- a/reftable/reader.c
+++ b/reftable/reader.c
@@ -61,6 +61,9 @@ static int reader_get_block(struct reftable_block *dest,
                            uint32_t sz, const uint64_t off,
                            const uint64_t r_size)
 {
+       if (off >= r_size) /* (28) following ‘true’ branch (when ‘off >=
r_size’)... */
+               return 0;
+
        if (off + sz > r_size) {
                sz = r_size - off;
        }
@@ -288,13 +291,14 @@ int reader_init_block_reader(struct reftable_reader *r,
struct block_reader *br,
        uint32_t header_off = next_off ? 0 : header_size(r->version);
        int32_t block_size = 0;

-       if (next_off >= r_size)
+       if (next_off >= r_size) /* (24) following ‘false’ branch (when
‘next_off < r_size’)... */
                return 1;

        err = reader_get_block(&block, &r->source, next_off, guess_block_size,
r_size);
-       if (err < 0)
+       if (err < 0) /* (31) following ‘false’ branch (when ‘err >= 0’)... */
                goto done;

+       /* We'll supposedly deference NULL block.data[0] here ... */ 
        block_size = extract_block_size(block.data, &block_typ, next_off,
                                        r->version);
        if (block_size < 0) {

[Bug analyzer/105285] False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[avarab at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

--- Comment #2 from Ævar Arnfjörð Bjarmason <avarab at gmail dot com> ---
This code also errors under -Werror=analyzer-too-complex, including in some
adjacent code, so perhaps the analyzer gave up?

[Bug analyzer/105285] False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[dmalcolm at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

--- Comment #3 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Thanks for filing this bug; I can reproduce it with the initial attachment;
it's unclear to me yet what's going on.

[Bug analyzer/105285] False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[dmalcolm at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

--- Comment #4 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Created attachment 52892
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52892&action=edit
Partially reduced reproducer

I reduced the reproducer and am attaching it.

[Bug analyzer/105285] False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[dmalcolm at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

--- Comment #5 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
I've been attempting to debug this.

I think that there is a bug in both (a) the analyzer, and, possibly (b) in the
software under test (git).

[Bug analyzer/105285] False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[dmalcolm at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

--- Comment #6 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
For (a):

If I'm reading this right:

reader_init_block_reader has:

  struct reftable_block block = {((void *)0)};

reader_init_block_reader checks for (next_off >= r->size) and bails out,
otherwise, block is passed to reader_get_block:

  if (next_off >= r->size)
    return 1;

  err = reader_get_block(r, &block, next_off, guess_block_size);
  if (err < 0)
    goto done;

  block_size = extract_block_size(block.data, &block_typ, next_off,
r->version);

There's an early-reject case in reader_get_block, which is:

  if (off >= r->size)
    return 0;

I believe the analyzer's feasibility checker is getting confused; it appears to
be getting placeholder values when it access r->size, and each time it accesses
r->size it gets a different placeholder value, and thus erroneously considers
the execution path where (next_off >= r->size) && !(off >= r->size) when
next_off == off.

I'm working on a simpler reproducer, and a fix.

[Bug analyzer/105285] False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[dmalcolm at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

--- Comment #7 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
For (b), I'm not convinced git's code is totally correct here.

The early-reject case in reader_get_block returns 0:

  if (off >= r->size)
    return 0;

but at the caller, the condition is < 0:

  err = reader_get_block(r, &block, next_off, guess_block_size);
  if (err < 0)
    goto done;

so if the early reject does happen, the returned "err" will be zero, not
less-than-zero.

Is that a problem?

[Bug analyzer/105285] False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[dmalcolm at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

David Malcolm <dmalcolm at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2022-04-27
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |ASSIGNED

--- Comment #8 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Minimal reproducer for (a):

#include "analyzer-decls.h"

void external_fn(void);
struct st
{
  char *name;
  unsigned size;
};
void test (void *p, unsigned next_off)
{
  struct st *r = p;

  external_fn();

  if (next_off >= r->size)
    return;

  if (next_off >= r->size)
    /* We should have already returned if this is the case.  */
    __analyzer_dump_path (); /* { dg-bogus "path" } */
}

I'm working on a fix.

[Bug analyzer/105285] False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by David Malcolm <dmalcolm@gcc.gnu.org>:

https://gcc.gnu.org/g:d8586b00dd00a1783862da5f0c8811a740400074

commit r13-6-gd8586b00dd00a1783862da5f0c8811a740400074
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Thu Apr 28 13:46:15 2022 -0400

    analyzer: add .fpath.txt dumps to -fdump-analyzer-feasibility

    I found this extension to -fdump-analyzer-feasibility very helpful when
    debugging PR analyzer/105285.

    gcc/analyzer/ChangeLog:
            * diagnostic-manager.cc (epath_finder::process_worklist_item):
            Call dump_feasible_path when a path that reaches the the target
            enode is found.
            (epath_finder::dump_feasible_path): New.
            * engine.cc (feasibility_state::dump_to_pp): New.
            * exploded-graph.h (feasibility_state::dump_to_pp): New decl.
            * feasible-graph.cc (feasible_graph::dump_feasible_path): New.
            * feasible-graph.h (feasible_graph::dump_feasible_path): New
            decls.
            * program-point.cc (function_point::print): Fix missing trailing
            newlines.
            * program-point.h (program_point::print_source_line): Remove
            unimplemented decl.

    gcc/ChangeLog:
            * doc/invoke.texi (-fdump-analyzer-feasibility): Mention the
            fpath.txt output.

    Signed-off-by: David Malcolm <dmalcolm@redhat.com>

[Bug analyzer/105285] False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by David Malcolm <dmalcolm@gcc.gnu.org>:

https://gcc.gnu.org/g:00c4405cd7f6a144d0a439e4d848d246920e6ff3

commit r13-7-g00c4405cd7f6a144d0a439e4d848d246920e6ff3
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Thu Apr 28 13:49:59 2022 -0400

    analyzer: handle repeated accesses after init of unknown size [PR105285]

    PR analyzer/105285 reports a false positive from
    -Wanalyzer-null-dereference on git.git's reftable/reader.c.

    A reduced version of the problem can be seen in test_1a of
    gcc.dg/analyzer/symbolic-12.c in the following:

    void test_1a (void *p, unsigned next_off)
    {
      struct st_1 *r = p;

      external_fn();

      if (next_off >= r->size)
        return;

      if (next_off >= r->size)
        /* We should have already returned if this is the case.  */
        __analyzer_dump_path (); /* { dg-bogus "path" } */
    }

    where the analyzer erroneously considers this path, where
    (next_off >= r->size) is both false and then true:

    symbolic-12.c: In function âtest_1aâ:
    symbolic-12.c:22:5: note: path
       22 |     __analyzer_dump_path (); /* { dg-bogus "path" } */
          |     ^~~~~~~~~~~~~~~~~~~~~~~
      âtest_1aâ: events 1-5
        |
        |   17 |   if (next_off >= r->size)
        |      |      ^
        |      |      |
        |      |      (1) following âfalseâ branch...
        |......
        |   20 |   if (next_off >= r->size)
        |      |      ~            ~~~~~~~
        |      |      |             |
        |      |      |             (2) ...to here
        |      |      (3) following âtrueâ branch...
        |   21 |     /* We should have already returned if this is the case. 
*/
        |   22 |     __analyzer_dump_path (); /* { dg-bogus "path" } */
        |      |     ~~~~~~~~~~~~~~~~~~~~~~~
        |      |     |
        |      |     (4) ...to here
        |      |     (5) here
        |

    The root cause is that, at the call to the external function, the
    analyzer considers the cluster for *p to have been touched, binding it
    to a conjured_svalue, but because p is void * no particular size is
    known for the write, and so the cluster is bound using a symbolic key
    covering the base region.  Later, the accesses to r->size are handled by
    binding_cluster::get_any_binding, but binding_cluster::get_binding fails
    to find a match for the concrete field lookup, due to the key for the
    binding being symbolic, and reaching this code:

    1522  /* If this cluster has been touched by a symbolic write, then the
content
    1523     of any subregion not currently specifically bound is "UNKNOWN". 
*/
    1524  if (m_touched)
    1525    {
    1526      region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
    1527      return rmm_mgr->get_or_create_unknown_svalue (reg->get_type ());
    1528    }

    Hence each access to r->size is an unknown svalue, and thus the
    condition (next_off >= r->size) isn't tracked, leading to the path with
    contradictory conditions being treated as satisfiable.

    In the original reproducer in git's reftable/reader.c, the call to the
    external fn is:
      reftable_record_type(rec)
    which is considered to possibly write to *rec, which is *tab, where tab
    is the void * argument to reftable_reader_seek_void, and thus after the
    call to reftable_record_type some arbitrary amount of *rec could have
    been written to.

    This patch fixes things by detecting the "this cluster has been 'filled'
    with a conjured value of unknown size" case, and handling
    get_any_binding on it by returning a sub_svalue of the conjured_svalue,
    so that repeated accesses to r->size give the same symbolic value, so
    that the constraint manager rejects the bogus execution path, fixing the
    false positive.

    gcc/analyzer/ChangeLog:
            PR analyzer/105285
            * store.cc (binding_cluster::get_any_binding): Handle accessing
            sub_svalues of clusters where the base region has a symbolic
            binding.

    gcc/testsuite/ChangeLog:
            PR analyzer/105285
            * gcc.dg/analyzer/symbolic-12.c: New test.

    Signed-off-by: David Malcolm <dmalcolm@redhat.com>

[Bug analyzer/105285] False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[dmalcolm at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

--- Comment #11 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Should be fixed on trunk for GCC 13 by the above commit.

I hope to backport this to GCC 12; keeping this open until that's done.

[Bug analyzer/105285] False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

--- Comment #12 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by David Malcolm
<dmalcolm@gcc.gnu.org>:

https://gcc.gnu.org/g:1321183a13540b5c3503586b94c758198471c7b3

commit r12-8631-g1321183a13540b5c3503586b94c758198471c7b3
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Wed Jul 27 17:38:53 2022 -0400

    analyzer: add .fpath.txt dumps to -fdump-analyzer-feasibility

    (cherry picked from r13-6-gd8586b00dd00a1783862da5f0c8811a740400074)

    I found this extension to -fdump-analyzer-feasibility very helpful when
    debugging PR analyzer/105285.

    gcc/analyzer/ChangeLog:
            * diagnostic-manager.cc (epath_finder::process_worklist_item):
            Call dump_feasible_path when a path that reaches the the target
            enode is found.
            (epath_finder::dump_feasible_path): New.
            * engine.cc (feasibility_state::dump_to_pp): New.
            * exploded-graph.h (feasibility_state::dump_to_pp): New decl.
            * feasible-graph.cc (feasible_graph::dump_feasible_path): New.
            * feasible-graph.h (feasible_graph::dump_feasible_path): New
            decls.
            * program-point.cc (function_point::print): Fix missing trailing
            newlines.
            * program-point.h (program_point::print_source_line): Remove
            unimplemented decl.

    gcc/ChangeLog:
            * doc/invoke.texi (-fdump-analyzer-feasibility): Mention the
            fpath.txt output.

    Signed-off-by: David Malcolm <dmalcolm@redhat.com>

[Bug analyzer/105285] False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

--- Comment #13 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by David Malcolm
<dmalcolm@gcc.gnu.org>:

https://gcc.gnu.org/g:05530fcea07a9ee5c7501867f3f11f0fbc504a06

commit r12-8632-g05530fcea07a9ee5c7501867f3f11f0fbc504a06
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Wed Jul 27 17:38:53 2022 -0400

    analyzer: handle repeated accesses after init of unknown size [PR105285]

    (cherry-picked from r13-7-g00c4405cd7f6a144d0a439e4d848d246920e6ff3)

    PR analyzer/105285 reports a false positive from
    -Wanalyzer-null-dereference on git.git's reftable/reader.c.

    A reduced version of the problem can be seen in test_1a of
    gcc.dg/analyzer/symbolic-12.c in the following:

    void test_1a (void *p, unsigned next_off)
    {
      struct st_1 *r = p;

      external_fn();

      if (next_off >= r->size)
        return;

      if (next_off >= r->size)
        /* We should have already returned if this is the case.  */
        __analyzer_dump_path (); /* { dg-bogus "path" } */
    }

    where the analyzer erroneously considers this path, where
    (next_off >= r->size) is both false and then true:

    symbolic-12.c: In function âtest_1aâ:
    symbolic-12.c:22:5: note: path
       22 |     __analyzer_dump_path (); /* { dg-bogus "path" } */
          |     ^~~~~~~~~~~~~~~~~~~~~~~
      âtest_1aâ: events 1-5
        |
        |   17 |   if (next_off >= r->size)
        |      |      ^
        |      |      |
        |      |      (1) following âfalseâ branch...
        |......
        |   20 |   if (next_off >= r->size)
        |      |      ~            ~~~~~~~
        |      |      |             |
        |      |      |             (2) ...to here
        |      |      (3) following âtrueâ branch...
        |   21 |     /* We should have already returned if this is the case. 
*/
        |   22 |     __analyzer_dump_path (); /* { dg-bogus "path" } */
        |      |     ~~~~~~~~~~~~~~~~~~~~~~~
        |      |     |
        |      |     (4) ...to here
        |      |     (5) here
        |

    The root cause is that, at the call to the external function, the
    analyzer considers the cluster for *p to have been touched, binding it
    to a conjured_svalue, but because p is void * no particular size is
    known for the write, and so the cluster is bound using a symbolic key
    covering the base region.  Later, the accesses to r->size are handled by
    binding_cluster::get_any_binding, but binding_cluster::get_binding fails
    to find a match for the concrete field lookup, due to the key for the
    binding being symbolic, and reaching this code:

    1522  /* If this cluster has been touched by a symbolic write, then the
content
    1523     of any subregion not currently specifically bound is "UNKNOWN". 
*/
    1524  if (m_touched)
    1525    {
    1526      region_model_manager *rmm_mgr = mgr->get_svalue_manager ();
    1527      return rmm_mgr->get_or_create_unknown_svalue (reg->get_type ());
    1528    }

    Hence each access to r->size is an unknown svalue, and thus the
    condition (next_off >= r->size) isn't tracked, leading to the path with
    contradictory conditions being treated as satisfiable.

    In the original reproducer in git's reftable/reader.c, the call to the
    external fn is:
      reftable_record_type(rec)
    which is considered to possibly write to *rec, which is *tab, where tab
    is the void * argument to reftable_reader_seek_void, and thus after the
    call to reftable_record_type some arbitrary amount of *rec could have
    been written to.

    This patch fixes things by detecting the "this cluster has been 'filled'
    with a conjured value of unknown size" case, and handling
    get_any_binding on it by returning a sub_svalue of the conjured_svalue,
    so that repeated accesses to r->size give the same symbolic value, so
    that the constraint manager rejects the bogus execution path, fixing the
    false positive.

    gcc/analyzer/ChangeLog:
            PR analyzer/105285
            * store.cc (binding_cluster::get_any_binding): Handle accessing
            sub_svalues of clusters where the base region has a symbolic
            binding.

    gcc/testsuite/ChangeLog:
            PR analyzer/105285
            * gcc.dg/analyzer/symbolic-12.c: New test.

    Signed-off-by: David Malcolm <dmalcolm@redhat.com>

[Bug analyzer/105285] False positive with -Wanalyzer-null-dereference in git.git's reftable/reader.c

[dmalcolm at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105285

David Malcolm <dmalcolm at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #14 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
(In reply to David Malcolm from comment #11)
> Should be fixed on trunk for GCC 13 by the above commit.
> 
> I hope to backport this to GCC 12; keeping this open until that's done.

Backported to GCC 12 (for 12.2), so marking this as resolved.