[Bug analyzer/106147] New: RFE: -fanalyzer could complain about some cases of infinite loops and infinite recursion

[Bug analyzer/106147] New: RFE: -fanalyzer could complain about some cases of infinite loops and infinite recursion

[dmalcolm at gcc dot gnu.org]

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

            Bug ID: 106147
           Summary: RFE: -fanalyzer could complain about some cases of
                    infinite loops and infinite recursion
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: analyzer
          Assignee: dmalcolm at gcc dot gnu.org
          Reporter: dmalcolm at gcc dot gnu.org
  Target Milestone: ---

We can't solve the halting problem, but maybe we can detect some cases where
the code *definitely* loops forever or has infinite recursion, where there are
no state changes or possible interactions with the outside world.

See:
  https://cwe.mitre.org/data/definitions/674.html
and:
  https://cwe.mitre.org/data/definitions/835.html

Juliet 1.3 has testcases for:
  (a) CWE674_Uncontrolled_Recursion/
  (b) CWE835_Infinite_Loop/

where (a) makes a distinction between actually unbounded vs a buggy loop that
counts down from UINT_MAX (pushing UINT_MAX stack frames is probably going to
crash).

All of the test cases in (b) perform output in an infinite loop, which I'd
argue is not a bug, as the program is generating output that's visible to the
outside world.

Compare CWE 835 examples 1 and 2.  Example 1 repeatedly calls "connect" in a
loop, which I don't think -fanalyzer is going to be able to reason about,
whereas 2 has logic:

  while (inventoryCount > minimumCount) {
    inventoryCount = inventoryCount - rateSold;
    days++;
  }

where if rateSold is 0, this effectively becomes:

  while (inventoryCount > minimumCount) {
    days++;
  }

and thus an infinite loop with no observable effects; possible interaction with
taint (e.g. if rateSold is under attacker control)

[Bug analyzer/106147] RFE: -fanalyzer could complain about some cases of infinite loops and infinite recursion

[dmalcolm at gcc dot gnu.org]

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

--- Comment #1 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Possible implementation idea: look at state merging when building the exploded
graph: if we're merging an identical state in a loop, with no variants, then
complain.

[Bug analyzer/106147] RFE: -fanalyzer could complain about some cases of infinite loops and infinite recursion

[dmalcolm at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2022-07-29
             Status|UNCONFIRMED                 |ASSIGNED
            Version|12.0                        |13.0

--- Comment #2 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
I've been prototyping an implementation of this; marking as assigned.

[Bug analyzer/106147] RFE: -fanalyzer could complain about some cases of infinite loops and infinite recursion

[dmalcolm at gcc dot gnu.org]

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

--- Comment #3 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
See also https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106203#c1 (w.r.t possible
revamp of how source locations are tracked in the analyzer, given that an
infinite loop might not contain any statements)

[Bug analyzer/106147] RFE: -fanalyzer could complain about some cases of infinite loops and infinite recursion

[dmalcolm at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=88232

--- Comment #4 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
-Winfinite-recursion was implemented as PR 88232, which complains if every path
through a function calls itself.

I have a mostly-finished implementation of a new -Wanalyzer-infinite-recursion
which complains if there is an interprocedural path through the code in which a
function is called recursively where there's no significant change to the
content of memory between calls, so it detects cases like:

void test_guarded (int flag)
{
  if (flag)
    test_guarded (flag);
}

[Bug analyzer/106147] RFE: -fanalyzer could complain about some cases of infinite loops and infinite recursion

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 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:12c583a2a3da798e82737c2d0e11fd686636cfeb

commit r13-3912-g12c583a2a3da798e82737c2d0e11fd686636cfeb
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Fri Nov 11 15:58:40 2022 -0500

    analyzer: new warning: -Wanalyzer-infinite-recursion [PR106147]

    This patch adds a new -Wanalyzer-infinite-recursion warning to
    -fanalyzer, which complains about certain cases of infinite recursion.

    Specifically, when it detects recursion during its symbolic execution
    of the user's code, it compares the state of memory to that at the
    previous level of recursion, and if nothing appears to have effectively
    changed, it issues a warning.

    Unlike the middle-end warning -Winfinite-recursion (added by Martin
    Sebor in GCC 12; r12-5483-g30ba058f77eedf), the analyzer warning
    complains if there exists an interprocedural path in which recursion
    occurs in which memory has not changed, whereas -Winfinite-recursion
    complains if *every* intraprocedural path through the function leads to
    a self-call.

    Hence the warnings complement each other: there's some overlap, but each
    also catches issues that the other misses.

    For example, the new warning complains about a guarded recursion in
    which the guard is passed unchanged:

    void test_guarded (int flag)
    {
      if (flag)
        test_guarded (flag);
    }

    t.c: In function 'test_guarded':
    t.c:4:5: warning: infinite recursion [CWE-674]
[-Wanalyzer-infinite-recursion]
        4 |     test_guarded (flag);
          |     ^~~~~~~~~~~~~~~~~~~
      'test_guarded': events 1-4
        |
        |    1 | void test_guarded (int flag)
        |      |      ^~~~~~~~~~~~
        |      |      |
        |      |      (1) initial entry to 'test_guarded'
        |    2 | {
        |    3 |   if (flag)
        |      |      ~
        |      |      |
        |      |      (2) following 'true' branch (when 'flag != 0')...
        |    4 |     test_guarded (flag);
        |      |     ~~~~~~~~~~~~~~~~~~~
        |      |     |
        |      |     (3) ...to here
        |      |     (4) calling 'test_guarded' from 'test_guarded'
        |
        +--> 'test_guarded': events 5-6
               |
               |    1 | void test_guarded (int flag)
               |      |      ^~~~~~~~~~~~
               |      |      |
               |      |      (5) recursive entry to 'test_guarded'; previously
entered at (1)
               |      |      (6) apparently infinite recursion
               |

    whereas the existing warning doesn't complain, since when "flag" is
    false the function doesn't recurse.

    The new warning doesn't trigger for e.g.:

      void test_param_variant (int depth)
      {
        if (depth > 0)
          test_param_variant (depth - 1);
      }

    on the grounds that "depth" is changing, and appears to be a variant
    that enforces termination of the recursion.

    gcc/ChangeLog:
            PR analyzer/106147
            * Makefile.in (ANALYZER_OBJS): Add analyzer/infinite-recursion.o.

    gcc/analyzer/ChangeLog:
            PR analyzer/106147
            * analyzer.opt (Wanalyzer-infinite-recursion): New.
            * call-string.cc (call_string::count_occurrences_of_function):
            New.
            * call-string.h (call_string::count_occurrences_of_function): New
            decl.
            * checker-path.cc (function_entry_event::function_entry_event):
            New ctor.
            (checker_path::add_final_event): Delete.
            * checker-path.h (function_entry_event::function_entry_event): New
            ctor.
            (function_entry_event::get_desc): Drop "final".
            (checker_path::add_final_event): Delete.
            * diagnostic-manager.cc
            (diagnostic_manager::emit_saved_diagnostic): Create the final
            event via a new pending_diagnostic::add_final_event vfunc, rather
            than checker_path::add_final_event.
            (diagnostic_manager::add_events_for_eedge): Create function entry
            events via a new pending_diagnostic::add_function_entry_event
            vfunc.
            * engine.cc (exploded_graph::process_node): When creating a new
            PK_BEFORE_SUPERNODE node, call
            exploded_graph::detect_infinite_recursion on it after adding the
            in-edge.
            * exploded-graph.h (exploded_graph::detect_infinite_recursion):
            New decl.
            (exploded_graph::find_previous_entry_to): New decl.
            * infinite-recursion.cc: New file.
            * pending-diagnostic.cc
            (pending_diagnostic::add_function_entry_event): New.
            (pending_diagnostic::add_final_event): New.
            * pending-diagnostic.h
            (pending_diagnostic::add_function_entry_event): New vfunc.
            (pending_diagnostic::add_final_event): New vfunc.

    gcc/ChangeLog:
            PR analyzer/106147
            *
doc/gcc/gcc-command-options/options-that-control-static-analysis.rst:
            Add -Wanalyzer-infinite-recursion.
            *
doc/gcc/gcc-command-options/options-to-request-or-suppress-warnings.rst
            (-Winfinite-recursion): Mention -Wanalyzer-infinite-recursion.

    gcc/testsuite/ChangeLog:
            PR analyzer/106147
            * g++.dg/analyzer/infinite-recursion-1.C: New test.
            * g++.dg/analyzer/infinite-recursion-2.C: New test, copied from
            g++.dg/warn/Winfinite-recursion-2.C.
            * g++.dg/analyzer/infinite-recursion-3.C: New test, adapted from
            g++.dg/warn/Winfinite-recursion-3.C.
            * gcc.dg/analyzer/infinite-recursion-2.c: New test.
            * gcc.dg/analyzer/infinite-recursion-3.c: New test.
            * gcc.dg/analyzer/infinite-recursion-4-limited-buggy.c: New test.
            * gcc.dg/analyzer/infinite-recursion-4-limited.c: New test.
            * gcc.dg/analyzer/infinite-recursion-4-unlimited-buggy.c: New test.
            * gcc.dg/analyzer/infinite-recursion-4-unlimited.c: New test.
            * gcc.dg/analyzer/infinite-recursion-5.c: New test, adapted from
            gcc.dg/Winfinite-recursion.c.
            * gcc.dg/analyzer/infinite-recursion-alloca.c: New test.
            * gcc.dg/analyzer/infinite-recursion-inlining.c: New test.
            * gcc.dg/analyzer/infinite-recursion-multiline-1.c: New test.
            * gcc.dg/analyzer/infinite-recursion-multiline-2.c: New test.
            * gcc.dg/analyzer/infinite-recursion-variadic.c: New test.
            * gcc.dg/analyzer/infinite-recursion.c: Add dg-warning directives
            where infinite recursions occur.
            * gcc.dg/analyzer/malloc-ipa-12.c: Likewise.
            * gcc.dg/analyzer/pr105365.c: Likewise.
            * gcc.dg/analyzer/pr105366.c: Likewise.
            * gcc.dg/analyzer/pr97029.c: Likewise.

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

[Bug analyzer/106147] RFE: -fanalyzer could complain about some cases of infinite loops and infinite recursion

[dmalcolm at gcc dot gnu.org]

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

--- Comment #6 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
The above patch implements -Wanalyzer-infinite-recursion for GCC 13.

I also have the beginnings of an implementation of -Wanalyzer-infinite-loop,
but it won't be ready for the close of GCC 13 stage 1.

Keeping this RFE open to track -Wanalyzer-infinite-loop.

[Bug analyzer/106147] RFE: -fanalyzer could complain about some cases of infinite loops and infinite recursion

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 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:841008d3966c0fe7a80ec10703a50fbdab7620ac

commit r14-5566-g841008d3966c0fe7a80ec10703a50fbdab7620ac
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Fri Nov 17 19:55:25 2023 -0500

    analyzer: new warning: -Wanalyzer-infinite-loop [PR106147]

    This patch implements a new analyzer warning: -Wanalyzer-infinite-loop.

    It works by examining the exploded graph once the latter has been
    fully built.  It attempts to detect cycles in the exploded graph in
    which:
    - no externally visible work occurs
    - no escape is possible from the cycle once it has been entered
    - the program state is "sufficiently concrete" at each step:
      - no unknown activity could be occurring
      - the worklist was fully drained for each enode in the cycle
        i.e. every enode in the cycle is processed

    For example, it correctly complains about this bogus "for" loop:

      int sum = 0;
      for (struct node *iter = n; iter; iter->next)
        sum += n->val;
      return sum;

    like this:

    infinite-loop-linked-list.c: In function âfor_loop_noop_nextâ:
    infinite-loop-linked-list.c:110:31: warning: infinite loop [CWE-835]
[-Wanalyzer-infinite-loop]
      110 |   for (struct node *iter = n; iter; iter->next)
          |                               ^~~~
      âfor_loop_noop_nextâ: events 1-5
        |
        |  110 |   for (struct node *iter = n; iter; iter->next)
        |      |                               ^~~~
        |      |                               |
        |      |                               (1) infinite loop here
        |      |                               (2) when âiterâ is non-NULL:
always following âtrueâ branch...
        |      |                               (5) ...to here
        |  111 |     sum += n->val;
        |      |     ~~~~~~~~~~~~~
        |      |         |   |
        |      |         |   (3) ...to here
        |      |         (4) looping back...
        |

    gcc/ChangeLog:
            PR analyzer/106147
            * Makefile.in (ANALYZER_OBJS): Add analyzer/infinite-loop.o.
            * doc/invoke.texi: Add -fdump-analyzer-infinite-loop and
            -Wanalyzer-infinite-loop.  Add missing CWE link for
            -Wanalyzer-infinite-recursion.
            * timevar.def (TV_ANALYZER_INFINITE_LOOPS): New.

    gcc/analyzer/ChangeLog:
            PR analyzer/106147
            * analyzer.opt (Wanalyzer-infinite-loop): New option.
            (fdump-analyzer-infinite-loop): New option.
            * checker-event.h (start_cfg_edge_event::get_desc): Drop "final".
            (start_cfg_edge_event::maybe_describe_condition): Convert from
            private to protected.
            * checker-path.h (checker_path::get_logger): New.
            * diagnostic-manager.cc (process_worklist_item): Update for
            new context param of maybe_update_for_edge.
            * engine.cc
            (impl_region_model_context::impl_region_model_context): Add
            out_could_have_done_work param to both ctors and use it to
            initialize mm_out_could_have_done_work.
            (impl_region_model_context::maybe_did_work): New vfunc
            implementation.
            (exploded_node::on_stmt): Add out_could_have_done_work param and
            pass to ctxt ctor.
            (exploded_node::on_stmt_pre): Treat setjmp and longjmp as "doing
            work".
            (exploded_node::on_longjmp): Likewise.
            (exploded_edge::exploded_edge): Add "could_do_work" param and use
            it to initialize m_could_do_work_p.
            (exploded_edge::dump_dot_label): Add result of could_do_work_p.
            (exploded_graph::add_function_entry): Mark edge as doing no work.
            (exploded_graph::add_edge): Add "could_do_work" param and pass to
            exploded_edge ctor.
            (add_tainted_args_callback): Treat as doing no work.
            (exploded_graph::process_worklist): Likewise when merging nodes.
            (maybe_process_run_of_before_supernode_enodes::item): Likewise.
            (exploded_graph::maybe_create_dynamic_call): Likewise.
            (exploded_graph::process_node): Likewise for phi nodes.
            Pass in a "could_have_done_work" bool when handling stmts and use
            when creating edges.  Assume work is done at bifurcation.
            (exploded_path::feasible_p): Update for new context param of
            maybe_update_for_edge.
            (feasibility_state::feasibility_state): New ctor.
            (feasibility_state::operator=): New.
            (feasibility_state::maybe_update_for_edge): Add ctxt param and use
            it.  Fix missing newline when logging state.
            (impl_run_checkers): Call exploded_graph::detect_infinite_loops.
            * exploded-graph.h
            (impl_region_model_context::impl_region_model_context): Add
            out_could_have_done_work param to both ctors.
            (impl_region_model_context::maybe_did_work): New decl.
            (impl_region_model_context::checking_for_infinite_loop_p): New.
            (impl_region_model_context::on_unusable_in_infinite_loop): New.
            (impl_region_model_context::m_out_could_have_done_work): New
            field.
            (exploded_node::on_stmt): Add "out_could_have_done_work" param.
            (exploded_edge::exploded_edge): Add "could_do_work" param.
            (exploded_edge::could_do_work_p): New accessor.
            (exploded_edge::m_could_do_work_p): New field.
            (exploded_graph::add_edge): Add "could_do_work" param.
            (exploded_graph::detect_infinite_loops): New decl.
            (feasibility_state::feasibility_state): New ctor.
            (feasibility_state::operator=): New decl.
            (feasibility_state::maybe_update_for_edge): Add ctxt param.
            * infinite-loop.cc: New file.
            * program-state.cc (program_state::on_edge): Log the rejected
            constraint when region_model::maybe_update_for_edge fails.
            * region-model.cc (region_model::on_assignment): Treat any writes
            other than to the stack as "doing work".
            (region_model::on_stmt_pre): Treat all asm stmts as "doing work".
            (region_model::on_call_post): Likewise for all calls to functions
            with unknown side effects.
            (region_model::handle_phi): Add svals_changing_meaning param.
            Mark widening svalue in phi nodes as changing meaning.
            (unusable_in_infinite_loop_constraint_p): New.
            (region_model::add_constraint): If we're checking for an infinite
            loop, bail out on unusable svalues, or if we don't have a definite
            true/false for the constraint.
            (region_model::update_for_phis): Gather all svalues changing
            meaning in phi nodes, and purge constraints involving them.
            (region_model::replay_call_summary): Treat all call summaries as
            doing work.
            (region_model::can_merge_with_p): Purge constraints involving
            svalues that change meaning.
            (model_merger::on_widening_reuse): New.
            (test_iteration_1): Likewise.
            (selftest::test_iteration_1): Remove assertion that model6 "knows"
            that i < 157.
            * region-model.h (region_model::handle_phi): Add
            svals_changing_meaning param
            (region_model_context::maybe_did_work): New pure virtual func.
            (region_model_context::checking_for_infinite_loop_p): Likewise.
            (region_model_context::on_unusable_in_infinite_loop): Likewise.
            (noop_region_model_context::maybe_did_work): Implement.
            (noop_region_model_context::checking_for_infinite_loop_p):
            Likewise.
            (noop_region_model_context::on_unusable_in_infinite_loop):
            Likewise.
            (region_model_context_decorator::maybe_did_work): Implement.
            (region_model_context_decorator::checking_for_infinite_loop_p):
            Likewise.
            (region_model_context_decorator::on_unusable_in_infinite_loop):
            Likewise.
            (model_merger::on_widening_reuse): New decl.
            (model_merger::m_svals_changing_meaning): New field.
            * sm-signal.cc (register_signal_handler::impl_transition): Assume
            the edge "does work".
            * supergraph.cc (supernode::get_start_location): Use CFG edge's
            goto_locus if available.
            (supernode::get_end_location): Likewise.
            (cfg_superedge::dump_label_to_pp): Dump edges with a "goto_locus"
            * supergraph.h (cfg_superedge::get_goto_locus): New.
            * svalue.cc (svalue::can_merge_p): Call on_widening_reuse for
            widening values.
            (involvement_visitor::visit_widening_svalue): New.
            (svalue::involves_p): Update assertion to allow widening svalues.

    gcc/testsuite/ChangeLog:
            PR analyzer/106147
            * c-c++-common/analyzer/gzio-2.c: Add dg-warning for infinite
            loop, marked as xfail.
            * c-c++-common/analyzer/infinite-loop-2.c: New test.
            * c-c++-common/analyzer/infinite-loop-4.c: New test.
            * c-c++-common/analyzer/infinite-loop-crc32c.c: New test.
            *
c-c++-common/analyzer/infinite-loop-doom-d_main-IdentifyVersion.c:
            New test.
            * c-c++-common/analyzer/infinite-loop-doom-v_video.c: New test.
            * c-c++-common/analyzer/infinite-loop-g_error.c: New test.
            * c-c++-common/analyzer/infinite-loop-linked-list.c: New test.
            * c-c++-common/analyzer/infinite-recursion-inlining.c: Add
            dg-warning directives for infinite loop.
            * c-c++-common/analyzer/inlining-4-multiline.c: Update expected
            paths for event 5 having a location.
            * gcc.dg/analyzer/boxed-malloc-1.c: Add dg-warning for infinite
            loop.
            * gcc.dg/analyzer/data-model-20.c: Likewise.  Add comment about
            suspect code, and create...
            * gcc.dg/analyzer/data-model-20a.c: ...this new test by cleaning
            it up.
            * gcc.dg/analyzer/edges-1.c: Add a placeholder statement to avoid
            the "...to here" from the if stmt occurring at the "while", and
            thus being treated as a bogus event.
            * gcc.dg/analyzer/explode-2a.c: Add dg-warning for infinite loop.
            * gcc.dg/analyzer/infinite-loop-1.c: New test.
            * gcc.dg/analyzer/malloc-1.c: Add dg-warning for infinite loop.
            * gcc.dg/analyzer/out-of-bounds-coreutils.c: Add TODO.
            * gcc.dg/analyzer/paths-4.c: Add dg-warning for infinite loop.
            * gcc.dg/analyzer/pr103892.c: Likewise.
            * gcc.dg/analyzer/pr93546.c: Likewise.

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

[Bug analyzer/106147] RFE: -fanalyzer could complain about some cases of infinite loops and infinite recursion

[dmalcolm at gcc dot gnu.org]

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

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

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

--- Comment #8 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
-Wanalyzer-infinite-loop implemented for GCC 14 by the above patch, so marking
this one as resolved.

[Bug analyzer/106147] RFE: -fanalyzer could complain about some cases of infinite loops and infinite recursion

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |14.0
           Keywords|                            |diagnostic