Re: fanalyzer: debugging zero state machine

[Tim Lange <mail@tim-lange.me>]

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
* 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 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

> 
> 
>>  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
>> 
>> 
> 
>