Re: fanalyzer: debugging zero state machine

[David Malcolm <dmalcolm@redhat.com>]

On Sun, 2022-06-12 at 20:27 +0200, Tim Lange wrote:
> 
> 
> On Do, Jun 9 2022 at 13:40:06 -0400, David Malcolm 
> <dmalcolm@redhat.com> wrote:
> > On Thu, 2022-06-09 at 16:49 +0200, Tim Lange wrote:
> > > 
> > >   > On Mi, Jun 8 2022 at 11:12:52 -0400, David Malcolm
> > >  <dmalcolm@redhat.com> wrote:
> > >   > > On Wed, 2022-06-08 at 01:42 +0200, Tim Lange wrote:
> > >   > >
> > >   > > Hi Dave,
> > 
> > Hi Tim; various responses inline below...
> > 
> > >   > >
> > >   > > I did spent some time to think about the zero state machine.
> > > I
> > >  first
> > >   > > thought about distinguishing between "assigned zero" and "EQ
> > > 0
> > >   > > condition on the path" for cases where e.g. unreachable() is
> > >  used
> > >  to
> > >   > > say that some variable will never be zero according to the
> > >  programmer.
> > >   > > In that case the dev might not want zero warnings from
> > >  conditions
> > >   > > outside the if body itself for dev build where unreachable
> > >  expands
> > >  to
> > >   > > some panic exit. But as the condition constraint is not
> > > pruned
> > >  when the
> > >   > > state machine is distinguishing the states, I'm not sure how
> > > to
> > >  know
> > >   > > whether the analysis already left the if body?
> > >   >
> > >   > The analyzer works on the gimple-ssa representation, which uses
> > >  basic
> > >   > blocks in a CFG, rather than an AST, so the only remants we
> > > have
> > >  of
> > >   > scope is in "clobber" statements (a special kind of assignment
> > >  stmt),
> > >   > which the gimplify adds as variables go out of scope.
> > >  If the constraints only lived until the immediate dominator of `if
> > >  (cond)`, I could easily distinguish:
> > >  1. if (x == 0) && still inside the if => zero
> > >  2. if (x == 0) && outside if => maybe zero
> > >  but as this seems to be not the case, if I want to distinguish 1.
> > > &
> > >  2.,
> > >  I'd have to find another way.
> > >   >
> > >   > For pruning, the analyzer's state_machine class has a
> > >  "can_purge_p"
> > >   > virtual function:
> > >   >
> > >   > /* Return true if it safe to discard the given state (to help
> > >   > when simplifying state objects).
> > >   > States that need leak detection should return false. */
> > >   > virtual bool can_purge_p (state_t s) const = 0;
> > >   >
> > >   > which should return true for a "zeroness" state machine, in
> > > that
> > >  we
> > >   > always consider pruning states for svalues that aren't needed
> > >  anymore
> > >   > along a path.
> > >  Is implemented and returns true.
> > >   >
> > >   > Is there some other kind of state explosion you're running
> > > into?
> > >  It's
> > >   > hard to figure this out further without seeing code.
> > >  No, my code is by far not that mature to be tested. I just had in
> > > my
> > >  head that I wanted to find out if I can distinguish the two cases.
> > >   >
> > >   >
> > >   > > Also, while trying out different things, it seems simple
> > >  assignments on
> > >   > > phi like here
> > >   > > int x;
> > >   > > if (argc == 1) {
> > >   > > x = 1; // x_5
> > >   > > } else {
> > >   > > x = 0; // x_4
> > >   > > }
> > >   > > printf("%i", 5 / x); // x_2
> > >   > > automatically work such that x_2 already inherits the state
> > > from
> > >   > > x_4/x_5 without me doing anything inside my sm's on_phi
> > >  function.
> > >  Same
> > >   > > for the simple y = 0; x = y; case. Where does this happen 
> > > inside
> > >  the
> > >   > > code?
> > >   >
> > >   > With the caveat that I'm seeing your code, what's probably
> > >  happening
> > >  is
> > >   > that we have either:
> > >   >
> > >   > BB (a):
> > >   > x_5 = 1;
> > >   > goto BB (c);
> > >   >
> > >   > BB (b):
> > >   > x_4 = 0;
> > >   > goto BB (c);
> > >   >
> > >   > BB (c):
> > >   > x_2 = PHI (x_5 from (a), x_4 from (b));
> > >  I compiled it with -g, so this one is like the dumped gimple.
> > >   >
> > >   > or (at higher optimization levels):
> > >   >
> > >   > BB (a):
> > >   > goto BB (c);
> > >   >
> > >   > BB (b):
> > >   > goto BB (c);
> > >   >
> > >   > BB (c):
> > >   > x_2 = PHI (1 from (a), 0 from (b));
> > >   >
> > >   > and I think that at the phi node we have 
> > > region_model::handle_phi,
> > >   > which is setting x_2 to either the constant 1 or the constant 0
> > > in
> > >  the
> > >   > store, and is calling the on_phi vfunc, leading to on_phi being
> > >  called
> > >   > for all state machines.
> > >  Thanks, that is the case. The set_value inside handle_phi seems to
> > >  this
> > >  for me.
> > >   >
> > >   > BTW, are you implementing an override for this vfunc:
> > >   > virtual state_machine::state_t get_default_state (const svalue
> > > *)
> > >   > const;
> > >   >
> > >   > to capture the inherently known zeroness/nonzeroness of
> > >  constant_svalue
> > >   > instances? That would make those constants have that state.
> > >  Yeah, I saw that on your nullness check. I tried it on a small
> > >  example
> > >  with and without, but didn't noticed a difference in warnings 
> > > (except
> > >  for not having zero(x_4) inside the supergraph.dot). So if I
> > >  understood
> > >  this right, this is just to have one state less for that
> > >  variable/value[0]?
> > 
> > The states are stored in sm_state_map using a mapping from svalue to
> > state.
> > 
> > Given e.g. a parameter, this will be "initial_svalue (parm)", but in
> > the above case where x_4 either has value 1 or has value 0, it's not
> > storing a state for x_4; it's storing a state for 0 or a state for 1.
> > So without implementing the get_default_state vfunc, the
> > sm_state_maps
> > will gradually aquire explicit "this is zero" or "this is nonzero"
> > for
> > all of the constants that get used, leading to an explosion of states
> > for all the different combinations of constants that have been
> > encountered along an execution path, which is probably not going to
> > be
> > useful.  If you do implement the get_default_state vfunc for 
> > constants,
> > then the constants will implicitly have the zero vs nonzero states,
> > and
> > this information won't get stored in the sm_state_map instances.
> > 
> > program_state::can_merge_with_p compares the sm_state_map instances
> > between the two program_state instances - and so if the
> > get_default_state vfunc is implemented for constants, the peer
> > sm_state_maps for the "zero" state machine will both be empty, and 
> > thus
> > equal, and thus it will merge state.
> > 
> > So it might make sense to revamp this sm_state_map comparison so that
> > we consider implicit states in sm_state_maps when merging the store, 
> > so
> > that we see that "1" and "0" have different sm-states for the "zero"
> > state machine, and thus we shouldn't merge states for these.  See
> > binding_cluster::can_merge_p, which calls svalue::can_merge_p.  It
> > might make sense to have svalue::can_merge_p "know" about 
> > sm-state-maps
> > for this.
> > 
> > svalue::can_merge_p calls model_merger::mergeable_svalue_p, so that
> > we
> > can reject merging values that explicitly have different state-
> > machine
> > states, but that code could be reworked so that it considers whether
> > a
> > pair of svalues can be merged, using implicit state-machine states 
> > (and
> > thus have it reject the merger of a zero with a nonzero constant).
> > 
> > Or, whilst prototyping, you could simply hack in a rejection of 
> > merging
> > zero vs non-zero integer values into svalue::can_merge_p.
> > 
> > > 
> > >  If that is right, is it also favorable to "merge" the stop state
> > > and
> > >  non_zero state inside the zero state machine because - for now -
> > >  there
> > >  is no warning planned on non-zero values?
> > > 
> > >  [0] less states are favorable because then the analyzer maybe has
> > >  less
> > >  different enodes to visit and thus less runtime(?)
> > >   >
> > >   > Thanks
> > >   > Dave
> > >   >
> > >   > > - Tim
> > > 
> > >  Also another question unrelated to the ones before. I do have a 
> > > weird
> > >  bug in my zero sm[1] but I'm unsure where my sm is flawed. Take
> > > for
> > >  example, the probably simplest case:
> > >    int x = 0;h
> > >    printf("%d", 42 / x);
> > >  If I use inform to emit a notice for my state machine result, it
> > >  seems
> > >  to be correct and I do get following traversal order (by printing 
> > > the
> > >  gimple stmt inside on_stmt):
> > >    x_2 = 0;
> > >    _1 = 42 % x_2;
> > >    # .MEM_4 = VDEF <.MEM_3(D)>
> > >    printf ("%d", _1);
> > >    _5 = 0;
> > >    <L0>:
> > >    # VUSE <.MEM_4>
> > >    return _5;
> > >  But if i use my zero_diagnostics and sm_ctxt->warn to emit the
> > >  warning,
> > >  I get an unexpected traversal order of:
> > >    x_2 = 0;
> > >    _1 = 42 / x_2;
> > >    # .MEM_4 = VDEF <.MEM_3(D)>
> > >    printf ("%d", _1);
> > >    _5 = 0;
> > >    <L0>:
> > >    # VUSE <.MEM_4>
> > >    return _5;
> > >    x_2 = 0;              <-- why do I get these stmts again but
> > > they
> > >  are not as
> > >  duplicated in the e-supergraph?
> > >    _1 = 42 / x_2;
> > >    _5 = 0;
> > >    _1 = 42 / x_2;
> > >    _5 = 0;
> > 
> > What exactly is your test source file?
> It is just the two lines wrapped into main():
>   #include <stdio.h>
>   int main(int argc, char **argv) {
>     int x = 0;
>     printf("%d", 42 / x);
>     return 0;
>   }
> > 
> > Note that a function being called by another function will get 
> > explored
> > in the exploded_graph twice: once being analyzed "standalone", and
> > again being analyzed as called from the other function.
> > 
> > When you say "I get these stmts again", do you mean the state machine
> > code is seeing them again, or the region model code?
> In the state_machine::on_stmt function.
> > 
> >   sm_ctxt->warn (new foo)
> > 
> > will save an instance of a pending_diagnostic into the
> > diagnotic_manager, associating it with a particular exploded_node
> > (and
> > some other info).
> > 
> > After the exploded_graph has been built, the diagnostic_manager does
> > some deduplication work, and then tries to find a feasible path to 
> > each
> > pending_diagnostic's exploded node.
> > 
> > This feasibility analysis reruns much of the region_model code that
> > was
> > run when building the exploded graph.  So that's another way you can
> > "see" stmts repeatedly.
> Okay, that probably explains it. I had two distinct problems where I 
> thought they might be both related to seeing the statements again:
>     |   13 |   int x = 0;
>     |      |       ^
>     |      |       |
>     |      |       (1) set to zero here
>     |      |       (3) set to zero here
>     |   14 |   printf("%d", 42 / x);
>     |      |   ~~~~~~~~~~~~~~~~~~~~
>     |      |   |
>     |      |   (4) division by zero
>     |   15 |
>     |   16 |   return 0;
>     |      |          ~
>     |      |          |
>     |      |          (2) set to zero here
>     |      |          (5) set to zero here

Aha: when you say "seeing the statements again", you're referring to
the diagnostic_path that's emitted.

gcc/analyzer/diagnostic-manager.cc finds a suitable path through the
exploded graph for the warning, and then walks the path, generating a
list of checker_event instances.  It then "optimizes" this list of
checker_events, and the result is what then gets visualized in ASCII
art.

Something really weird's happening in the above.

The way diagnostic-manager.cc generates events could definitely be
improved - it tries to track the state of interest, and thus generate
events that relate to it, but it only knows about state machine
changes, not region_model changes, and it doesn't do a good job of the
former.

I've got some ideas for rewriting it which I'm hoping to get to later
this month, once I finish my work on SARIF.

Basically, my plan is to update the exploded_graph exploration so that
I capture a list of state changes on each edge, capturing the sequence
of how each source state became each destination state, in a reversible
way, so that for any given diagnostic I hope we'll be able to walk
backwards along a graph and see what the changes were, and where they
came from.

Given that, I think it's best if you put your state machine work on
hold for now, and focus on the other tests you were interested in.

FWIW, I just added some more ideas to the tracker bug here:
  https://gcc.gnu.org/bugzilla/showdependencytree.cgi?id=105887&hide_resolved=1

at least one of which looks fairly easy (105947).

> * In line 13, there are two state changes while I'd expect only one.
> => I re-looked at the other state machines and they transfer to the 
> stop state after the warning. If I do the same, my problem in line 13
> is fixed.
> * The other problem in line 16 is that return 0 is not relevant toward 
> the division by zero.
> => After looking at the diagnostic code, I think those should be 
> filtered out but aren't because x (in gimple x_2) and return 0 (in 
> gimple _5) share the (int)0 state. Inside 
> diagnostic_manager::prune_for_sm_diagnostic there is a check that the
> state_change->m_sval is equal to the sval of the saved_diagnostic, 
> which is not enough to filter unrelated events in the zero state 
> machine case.

I don't know that it makes much sense to track the states on constants;
it makes more sense for things like the initial_value (x), if x were a
parameter.

It may be that the current implementation of state machines in the
analyzer just isn't a good fit for this test.

> I tried to filter the event by comparing the state of interest but that
> doesn't work if the unrelated event is after the related event on the
> path.
> Similarly, I tried to add a new field m_var to state_change_event and
> provide this as a comparison but in most functions that call the 
> constructor of state_change_event, the var is not available.
> 
> Is there is any easy way to filter these unrelated events without 
> considerable changes [1]?
> 
> By the way, I can trigger the same behavior on the malloc null_deref 
> with gcc version 12.1.1 shipped in Fedora 36. Assume this simple 
> program:
>   #include <stddef.h>
>   int main (void)
>   {
>     int *p = NULL;
>     *p = 42;
> 
>     int *q = NULL;
> 
>     return 0;
>   }
> results in the following warning:
> /home/tim/Projects/simple_c/main.c: In function ‘main’:
> /home/tim/Projects/simple_c/main.c:12:6: warning: dereference of NULL
> ‘p’ [CWE-476] [-Wanalyzer-null-dereference]
>    12 |   *p = 42;
>       |   ~~~^~~~
>   ‘main’: events 1-4
>     |
>     |   11 |   int *p = NULL;
>     |      |        ^
>     |      |        |
>     |      |        (1) ‘p’ is NULL
>     |   12 |   *p = 42;
>     |      |   ~~~~~~~
>     |      |      |
>     |      |      (4) dereference of NULL ‘p’
>     |   13 |
>     |   14 |   int *q = NULL;
>     |      |        ~
>     |      |        |
>     |      |        (2) ‘p’ is NULL
>     |      |        (3) ‘p’ is NULL
> 

That definitely looks like a bug in the code I was talking about
earlier.

I've filed this as:
   https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105958


Thanks
Dave


> > 
> > 
> > >  I tracked the cause down the call stack to
> > >  m_saved_diagnostics.safe_push (sd); inside
> > >  diagnostic_manager::add_diagnostic. For whatever reason, the
> > > pushing
> > >  of
> > >  diagnostics bricks the zero sm. It might be a embarrassing error
> > > on
> > >  my
> > >  side, but I'm stuck on this and can't seem to find what I'm doing
> > >  wrong.
> > 
> > FWIW, assuming you're using the gdb support scripts:
> >   
> >  
> > https://gcc-newbies-guide.readthedocs.io/en/latest/debugging.html#support-scripts-for-gdb
> > there's a handy:
> > 
> > (gdb) break-on-saved-diagnostic
> > 
> > command which adds a breakpoint on the analyzer's diagnostic_manager
> > saving a pending_diagnostic.
> > 
> > You might also what to try -fdump-analyzer-stderr, which will dump 
> > lots
> > of information on what the analyzer is doing to stderr, which
> > although
> > verbose is usually very helpful in figuring out why the analyzer is
> > doing something.
> > 
> > Hope this is helpful
> Definitely helped me understand more of the internals!
> 
> - Tim
> > Dave
> > 
> > 
> > 
> > > 
> > >  - Tim
> > > 
> > >  [1]
> > > 
> > >  
> > >  
> > > https://github.com/timll/gcc/blob/castsize/gcc/analyzer/sm-zero.cc#L181
> > > 
> > > 
> > 
> > 
> 
>