From ef7827b0bd7cd980da625fcd12e6c56f51a166c2 Mon Sep 17 00:00:00 2001
From: David Malcolm <dmalcolm@redhat.com>
Date: Fri, 13 Dec 2019 19:48:06 -0500
Subject: [PATCH] analyzer: purge state for unknown function calls

Whilst analyzing the reproducer for detecting CVE-2005-1689
(krb5-1.4.1's src/lib/krb5/krb/recvauth.c), the analyzer reports
a false double-free of the form:

  krb5_xfree(inbuf.data);
  krb5_read_message(..., &inbuf);
  krb5_xfree(inbuf.data); /* false diagnostic here.  */

where the call to krb5_read_message overwrites inbuf.data with
a freshly-malloced buffer.

This patch fixes the issue by purging state more thorougly when
handling a call with unknown behavior, by walking the graph of
memory regions that are reachable from the call.

gcc/analyzer/ChangeLog:
	* analyzer.h (fndecl_has_gimple_body_p): New decl.
	* engine.cc (impl_region_model_context::on_unknown_change): New
	function.
	(fndecl_has_gimple_body_p): Make non-static.
	(exploded_node::on_stmt): Treat __analyzer_dump_exploded_nodes as
	known.  Track whether we have a call with unknown side-effects and
	pass it to on_call_post.
	* exploded-graph.h (impl_region_model_context::on_unknown_change):
	New decl.
	* program-state.cc (sm_state_map::on_unknown_change): New function.
	* program-state.h (sm_state_map::on_unknown_change): New decl.
	* region-model.cc: Include "bitmap.h".
	(region_model::on_call_pre): Return a bool, capturing whether the
	call has unknown side effects.
	(region_model::on_call_post): Add arg "bool unknown_side_effects"
	and if true, call handle_unrecognized_call.
	(class reachable_regions): New class.
	(region_model::handle_unrecognized_call): New function.
	* region-model.h (region_model::on_call_pre): Return a bool.
	(region_model::on_call_post): Add arg "bool unknown_side_effects".
	(region_model::handle_unrecognized_call): New decl.
	(region_model_context::on_unknown_change): New vfunc.
	(test_region_model_context::on_unknown_change): New function.

gcc/testsuite/ChangeLog:
	* gcc.dg/analyzer/data-model-1.c: Remove xfail.
	* gcc.dg/analyzer/data-model-5b.c: Likewise.
	* gcc.dg/analyzer/data-model-5c.c: Likewise.
	* gcc.dg/analyzer/setjmp-3.c: Mark "foo" as pure.
	* gcc.dg/analyzer/setjmp-4.c: Likewise.
	* gcc.dg/analyzer/setjmp-6.c: Likewise.
	* gcc.dg/analyzer/setjmp-7.c: Likewise.
	* gcc.dg/analyzer/setjmp-7a.c: Likewise.
	* gcc.dg/analyzer/setjmp-8.c: Likewise.
	* gcc.dg/analyzer/setjmp-9.c: Likewise.
	* gcc.dg/analyzer/unknown-fns.c: New test.
---
 gcc/analyzer/ChangeLog                        |  26 +++
 gcc/analyzer/analyzer.h                       |   2 +
 gcc/analyzer/engine.cc                        |  28 ++-
 gcc/analyzer/exploded-graph.h                 |   2 +
 gcc/analyzer/program-state.cc                 |   8 +
 gcc/analyzer/program-state.h                  |   2 +
 gcc/analyzer/region-model.cc                  | 217 +++++++++++++++++-
 gcc/analyzer/region-model.h                   |  16 +-
 gcc/testsuite/ChangeLog                       |  14 ++
 gcc/testsuite/gcc.dg/analyzer/data-model-1.c  |   4 +-
 gcc/testsuite/gcc.dg/analyzer/data-model-5b.c |   3 +-
 gcc/testsuite/gcc.dg/analyzer/data-model-5c.c |  10 +-
 gcc/testsuite/gcc.dg/analyzer/setjmp-3.c      |   2 +-
 gcc/testsuite/gcc.dg/analyzer/setjmp-4.c      |   2 +-
 gcc/testsuite/gcc.dg/analyzer/setjmp-6.c      |   2 +-
 gcc/testsuite/gcc.dg/analyzer/setjmp-7.c      |   2 +-
 gcc/testsuite/gcc.dg/analyzer/setjmp-7a.c     |   2 +-
 gcc/testsuite/gcc.dg/analyzer/setjmp-8.c      |   2 +-
 gcc/testsuite/gcc.dg/analyzer/setjmp-9.c      |   2 +-
 gcc/testsuite/gcc.dg/analyzer/unknown-fns.c   | 115 ++++++++++
 20 files changed, 423 insertions(+), 38 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/analyzer/unknown-fns.c

diff --git a/gcc/analyzer/ChangeLog b/gcc/analyzer/ChangeLog
index 9afb288266d..96d5ce99538 100644
--- a/gcc/analyzer/ChangeLog
+++ b/gcc/analyzer/ChangeLog
@@ -1,3 +1,29 @@
+2020-01-14  David Malcolm  <dmalcolm@redhat.com>
+
+	* analyzer.h (fndecl_has_gimple_body_p): New decl.
+	* engine.cc (impl_region_model_context::on_unknown_change): New
+	function.
+	(fndecl_has_gimple_body_p): Make non-static.
+	(exploded_node::on_stmt): Treat __analyzer_dump_exploded_nodes as
+	known.  Track whether we have a call with unknown side-effects and
+	pass it to on_call_post.
+	* exploded-graph.h (impl_region_model_context::on_unknown_change):
+	New decl.
+	* program-state.cc (sm_state_map::on_unknown_change): New function.
+	* program-state.h (sm_state_map::on_unknown_change): New decl.
+	* region-model.cc: Include "bitmap.h".
+	(region_model::on_call_pre): Return a bool, capturing whether the
+	call has unknown side effects.
+	(region_model::on_call_post): Add arg "bool unknown_side_effects"
+	and if true, call handle_unrecognized_call.
+	(class reachable_regions): New class.
+	(region_model::handle_unrecognized_call): New function.
+	* region-model.h (region_model::on_call_pre): Return a bool.
+	(region_model::on_call_post): Add arg "bool unknown_side_effects".
+	(region_model::handle_unrecognized_call): New decl.
+	(region_model_context::on_unknown_change): New vfunc.
+	(test_region_model_context::on_unknown_change): New function.
+
 2020-01-14  David Malcolm  <dmalcolm@redhat.com>
 
 	* diagnostic-manager.cc (saved_diagnostic::operator==): Move here
diff --git a/gcc/analyzer/analyzer.h b/gcc/analyzer/analyzer.h
index e207d7a9436..7fc6959c460 100644
--- a/gcc/analyzer/analyzer.h
+++ b/gcc/analyzer/analyzer.h
@@ -80,6 +80,8 @@ extern void register_analyzer_pass ();
 
 extern label_text make_label_text (bool can_colorize, const char *fmt, ...);
 
+extern bool fndecl_has_gimple_body_p (tree fndecl);
+
 /* An RAII-style class for pushing/popping cfun within a scope.
    Doing so ensures we get "In function " announcements
    from the diagnostics subsystem.  */
diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index 720fa219d16..573f9f6e35b 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -135,6 +135,15 @@ impl_region_model_context::on_svalue_purge (svalue_id first_unused_sid,
   return total;
 }
 
+void
+impl_region_model_context::on_unknown_change (svalue_id sid)
+{
+  int sm_idx;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
+    smap->on_unknown_change (sid);
+}
+
 /* class setjmp_svalue : public svalue.  */
 
 /* Compare the fields of this setjmp_svalue with OTHER, returning true
@@ -876,7 +885,7 @@ exploded_node::dump (const extrinsic_state &ext_state) const
 /* Return true if FNDECL has a gimple body.  */
 // TODO: is there a pre-canned way to do this?
 
-static bool
+bool
 fndecl_has_gimple_body_p (tree fndecl)
 {
   if (fndecl == NULL_TREE)
@@ -935,6 +944,10 @@ exploded_node::on_stmt (exploded_graph &eg,
   if (const greturn *return_ = dyn_cast <const greturn *> (stmt))
     state->m_region_model->on_return (return_, &ctxt);
 
+  /* Track whether we have a gcall to a function that's not recognized by
+     anything, for which we don't have a function body, or for which we
+     don't know the fndecl.  */
+  bool unknown_side_effects = false;
   if (const gcall *call = dyn_cast <const gcall *> (stmt))
     {
       /* Debugging/test support.  */
@@ -977,6 +990,11 @@ exploded_node::on_stmt (exploded_graph &eg,
 	  /* TODO: is there a good cross-platform way to do this?  */
 	  raise (SIGINT);
 	}
+      else if (is_special_named_call_p (call, "__analyzer_dump_exploded_nodes",
+					1))
+	{
+	  /* This is handled elsewhere.  */
+	}
       else if (is_setjmp_call_p (stmt))
 	state->m_region_model->on_setjmp (call, this, &ctxt);
       else if (is_longjmp_call_p (call))
@@ -985,7 +1003,7 @@ exploded_node::on_stmt (exploded_graph &eg,
 	  return on_stmt_flags::terminate_path ();
 	}
       else
-	state->m_region_model->on_call_pre (call, &ctxt);
+	unknown_side_effects = state->m_region_model->on_call_pre (call, &ctxt);
     }
 
   bool any_sm_changes = false;
@@ -1001,7 +1019,9 @@ exploded_node::on_stmt (exploded_graph &eg,
 			    change,
 			    old_smap, new_smap);
       /* Allow the state_machine to handle the stmt.  */
-      if (!sm.on_stmt (&ctxt, snode, stmt))
+      if (sm.on_stmt (&ctxt, snode, stmt))
+	unknown_side_effects = false;
+      else
 	{
 	  /* For those stmts that were not handled by the state machine.  */
 	  if (const gcall *call = dyn_cast <const gcall *> (stmt))
@@ -1019,7 +1039,7 @@ exploded_node::on_stmt (exploded_graph &eg,
     }
 
   if (const gcall *call = dyn_cast <const gcall *> (stmt))
-    state->m_region_model->on_call_post (call, &ctxt);
+    state->m_region_model->on_call_post (call, unknown_side_effects, &ctxt);
 
   return on_stmt_flags (any_sm_changes);
 }
diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h
index 8c29e552cac..357a1b478f0 100644
--- a/gcc/analyzer/exploded-graph.h
+++ b/gcc/analyzer/exploded-graph.h
@@ -70,6 +70,8 @@ class impl_region_model_context : public region_model_context
 
   void on_condition (tree lhs, enum tree_code op, tree rhs) FINAL OVERRIDE;
 
+  void on_unknown_change (svalue_id sid ATTRIBUTE_UNUSED) FINAL OVERRIDE;
+
   exploded_graph *m_eg;
   log_user m_logger;
   const exploded_node *m_enode_for_diag;
diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
index 04346ae9dc8..c9b595eca2b 100644
--- a/gcc/analyzer/program-state.cc
+++ b/gcc/analyzer/program-state.cc
@@ -480,6 +480,14 @@ sm_state_map::on_cast (svalue_id src_sid,
   impl_set_state (dst_sid, state, get_origin (src_sid));
 }
 
+/* Purge state from SID (in response to a call to an unknown function).  */
+
+void
+sm_state_map::on_unknown_change (svalue_id sid)
+{
+  impl_set_state (sid, (state_machine::state_t)0, svalue_id::null ());
+}
+
 /* Assert that this object is sane.  */
 
 void
diff --git a/gcc/analyzer/program-state.h b/gcc/analyzer/program-state.h
index 75b65b780c9..155eaf877ef 100644
--- a/gcc/analyzer/program-state.h
+++ b/gcc/analyzer/program-state.h
@@ -184,6 +184,8 @@ public:
   void on_cast (svalue_id src_sid,
 		svalue_id dst_sid);
 
+  void on_unknown_change (svalue_id sid);
+
   void validate (const state_machine &sm, int num_svalues) const;
 
   iterator_t begin () const { return m_map.begin (); }
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 2b0945a4ce8..b492222d64d 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -39,6 +39,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "diagnostic-metadata.h"
 #include "diagnostic-core.h"
 #include "tristate.h"
+#include "bitmap.h"
 #include "selftest.h"
 #include "function.h"
 #include "analyzer/analyzer.h"
@@ -4115,9 +4116,13 @@ region_model::on_assignment (const gassign *assign, region_model_context *ctxt)
 
    Updates to the region_model that should be made *before* sm-states
    are updated are done here; other updates to the region_model are done
-   in region_model::on_call_post.  */
+   in region_model::on_call_post.
 
-void
+   Return true if the function call has unknown side effects (it wasn't
+   recognized and we don't have a body for it, or are unable to tell which
+   fndecl it is).  */
+
+bool
 region_model::on_call_pre (const gcall *call, region_model_context *ctxt)
 {
   region_id lhs_rid;
@@ -4135,6 +4140,8 @@ region_model::on_call_pre (const gcall *call, region_model_context *ctxt)
     for (unsigned i = 0; i < gimple_call_num_args (call); i++)
       check_for_poison (gimple_call_arg (call, i), ctxt);
 
+  bool unknown_side_effects = false;
+
   if (tree callee_fndecl = get_fndecl_for_call (call, ctxt))
     {
       if (is_named_call_p (callee_fndecl, "malloc", call, 1))
@@ -4147,7 +4154,7 @@ region_model::on_call_pre (const gcall *call, region_model_context *ctxt)
 		= get_or_create_ptr_svalue (lhs_type, new_rid);
 	      set_value (lhs_rid, ptr_sid, ctxt);
 	    }
-	  return;
+	  return false;
 	}
       else if (is_named_call_p (callee_fndecl, "__builtin_alloca", call, 1))
 	{
@@ -4160,7 +4167,7 @@ region_model::on_call_pre (const gcall *call, region_model_context *ctxt)
 		= get_or_create_ptr_svalue (lhs_type, new_rid);
 	      set_value (lhs_rid, ptr_sid, ctxt);
 	    }
-	  return;
+	  return false;
 	}
       else if (is_named_call_p (callee_fndecl, "strlen", call, 1))
 	{
@@ -4179,7 +4186,7 @@ region_model::on_call_pre (const gcall *call, region_model_context *ctxt)
 		  svalue_id result_sid
 		    = get_or_create_constant_svalue (t_cst);
 		  set_value (lhs_rid, result_sid, ctxt);
-		  return;
+		  return false;
 		}
 	    }
 	  /* Otherwise an unknown value.  */
@@ -4199,18 +4206,20 @@ region_model::on_call_pre (const gcall *call, region_model_context *ctxt)
 	  /* Use quotes to ensure the output isn't truncated.  */
 	  warning_at (call->location, 0,
 		      "num heap regions: %qi", num_heap_regions);
+	  return false;
 	}
+      else if (!fndecl_has_gimple_body_p (callee_fndecl)
+	       && !DECL_PURE_P (callee_fndecl))
+	unknown_side_effects = true;
     }
-
-  /* Unrecognized call.  */
+  else
+    unknown_side_effects = true;
 
   /* Unknown return value.  */
   if (!lhs_rid.null_p ())
     set_to_new_unknown_value (lhs_rid, lhs_type, ctxt);
 
-  /* TODO: also, any pointer arguments might have been written through,
-     or the things they point to (implying a graph traversal, which
-     presumably we need to do before overwriting the old value).  */
+  return unknown_side_effects;
 }
 
 /* Update this model for the CALL stmt, using CTXT to report any
@@ -4218,10 +4227,15 @@ region_model::on_call_pre (const gcall *call, region_model_context *ctxt)
 
    Updates to the region_model that should be made *after* sm-states
    are updated are done here; other updates to the region_model are done
-   in region_model::on_call_pre.  */
+   in region_model::on_call_pre.
+
+   If UNKNOWN_SIDE_EFFECTS is true, also call handle_unrecognized_call
+   to purge state.  */
 
 void
-region_model::on_call_post (const gcall *call, region_model_context *ctxt)
+region_model::on_call_post (const gcall *call,
+			    bool unknown_side_effects,
+			    region_model_context *ctxt)
 {
   /* Update for "free" here, after sm-handling.
 
@@ -4264,6 +4278,185 @@ region_model::on_call_post (const gcall *call, region_model_context *ctxt)
 	  }
 	return;
       }
+
+  if (unknown_side_effects)
+    handle_unrecognized_call (call, ctxt);
+}
+
+/* Helper class for region_model::handle_unrecognized_call, for keeping
+   track of all regions that are reachable, and, of those, which are
+   mutable.  */
+
+class reachable_regions
+{
+public:
+  reachable_regions (region_model *model)
+  : m_model (model), m_reachable_rids (), m_mutable_rids ()
+  {}
+
+  /* Lazily mark RID as being reachable, recursively adding regions
+     reachable from RID.  */
+  void add (region_id rid, bool is_mutable)
+  {
+    gcc_assert (!rid.null_p ());
+
+    unsigned idx = rid.as_int ();
+    /* Bail out if this region is already in the sets at the IS_MUTABLE
+       level of mutability.  */
+    if (!is_mutable && bitmap_bit_p (m_reachable_rids, idx))
+      return;
+    bitmap_set_bit (m_reachable_rids, idx);
+
+    if (is_mutable)
+      {
+	if (bitmap_bit_p (m_mutable_rids, idx))
+	  return;
+	else
+	  bitmap_set_bit (m_mutable_rids, idx);
+      }
+
+    /* If this region's value is a pointer, add the pointee.  */
+    region *reg = m_model->get_region (rid);
+    svalue_id sid = reg->get_value_direct ();
+    svalue *sval = m_model->get_svalue (sid);
+    if (sval)
+      if (region_svalue *ptr = sval->dyn_cast_region_svalue ())
+	{
+	  region_id pointee_rid = ptr->get_pointee ();
+	  /* Use const-ness of pointer type to affect mutability.  */
+	  bool ptr_is_mutable = true;
+	  if (ptr->get_type ()
+	      && TREE_CODE (ptr->get_type ()) == POINTER_TYPE
+	      && TYPE_READONLY (TREE_TYPE (ptr->get_type ())))
+	    ptr_is_mutable = false;
+	  add (pointee_rid, ptr_is_mutable);
+	}
+
+    /* Add descendents of this region.  */
+    region_id_set descendents (m_model);
+    m_model->get_descendents (rid, &descendents, region_id::null ());
+    for (unsigned i = 0; i < m_model->get_num_regions (); i++)
+      {
+	region_id iter_rid = region_id::from_int (i);
+	if (descendents.region_p (iter_rid))
+	  add (iter_rid, is_mutable);
+      }
+  }
+
+  bool mutable_p (region_id rid)
+  {
+    gcc_assert (!rid.null_p ());
+    return bitmap_bit_p (m_mutable_rids, rid.as_int ());
+  }
+
+private:
+  region_model *m_model;
+
+  /* The region ids already seen.  This has to be an auto_bitmap rather than
+     an auto_sbitmap as new regions can be created within the model during
+     the traversal.  */
+  auto_bitmap m_reachable_rids;
+
+  /* The region_ids that can be changed (accessed via non-const pointers).  */
+  auto_bitmap m_mutable_rids;
+};
+
+/* Handle a call CALL to a function with unknown behavior.
+
+   Traverse the regions in this model, determining what regions are
+   reachable from pointer arguments to CALL and from global variables,
+   recursively.
+
+   Set all reachable regions to new unknown values and purge sm-state
+   from their values, and from values that point to them.  */
+
+void
+region_model::handle_unrecognized_call (const gcall *call,
+					region_model_context *ctxt)
+{
+  tree fndecl = get_fndecl_for_call (call, ctxt);
+
+  reachable_regions reachable_regions (this);
+
+  /* Determine the reachable regions and their mutability.  */
+  {
+    /* Globals.  */
+    region_id globals_rid = get_globals_region_id ();
+    if (!globals_rid.null_p ())
+      reachable_regions.add (globals_rid, true);
+
+    /* Params that are pointers.  */
+    tree iter_param_types = NULL_TREE;
+    if (fndecl)
+      iter_param_types = TYPE_ARG_TYPES (TREE_TYPE (fndecl));
+    for (unsigned arg_idx = 0; arg_idx < gimple_call_num_args (call); arg_idx++)
+      {
+	/* Track expected param type, where available.  */
+	tree param_type = NULL_TREE;
+	if (iter_param_types)
+	  {
+	    param_type = TREE_VALUE (iter_param_types);
+	    gcc_assert (param_type);
+	    iter_param_types = TREE_CHAIN (iter_param_types);
+	  }
+
+	tree parm = gimple_call_arg (call, arg_idx);
+	svalue_id parm_sid = get_rvalue (parm, NULL);
+	svalue *parm_sval = get_svalue (parm_sid);
+	if (parm_sval)
+	  if (region_svalue *parm_ptr = parm_sval->dyn_cast_region_svalue ())
+	    {
+	      region_id pointee_rid = parm_ptr->get_pointee ();
+	      bool is_mutable = true;
+	      if (param_type
+		  && TREE_CODE (param_type) == POINTER_TYPE
+		  &&  TYPE_READONLY (TREE_TYPE (param_type)))
+		is_mutable = false;
+	      reachable_regions.add (pointee_rid, is_mutable);
+	    }
+	// FIXME: what about compound parms that contain ptrs?
+      }
+  }
+
+  /* OK: we now have all reachable regions.
+     Set them all to new unknown values.  */
+  for (unsigned i = 0; i < get_num_regions (); i++)
+    {
+      region_id iter_rid = region_id::from_int (i);
+      if (reachable_regions.mutable_p (iter_rid))
+	{
+	  region *reg = get_region (iter_rid);
+
+	  /* Purge any sm-state for any underlying svalue.  */
+	  svalue_id curr_sid = reg->get_value_direct ();
+	  if (!curr_sid.null_p ())
+	    ctxt->on_unknown_change (curr_sid);
+
+	  set_to_new_unknown_value (iter_rid,
+				    reg->get_type (),
+				    ctxt);
+	}
+    }
+
+  /* Purge sm-state for any remaining svalues that point to regions that
+     were reachable.  This helps suppress leak false-positives.
+
+     For example, if we had a malloc call that was cast to a "foo *" type,
+     we could have a temporary void * for the result of malloc which has its
+     own svalue, not reachable from the function call, but for which the
+     "foo *" svalue was reachable.  If we don't purge it, the temporary will
+     be reported as a leak.  */
+  int i;
+  svalue *svalue;
+  FOR_EACH_VEC_ELT (m_svalues, i, svalue)
+    if (region_svalue *ptr = svalue->dyn_cast_region_svalue ())
+      {
+	region_id pointee_rid = ptr->get_pointee ();
+	if (reachable_regions.mutable_p (pointee_rid))
+	  ctxt->on_unknown_change (svalue_id::from_int (i));
+      }
+
+  validate ();
 }
 
 /* Update this model for the RETURN_STMT, using CTXT to report any
diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h
index ec5282f6956..2d0c0618bd0 100644
--- a/gcc/analyzer/region-model.h
+++ b/gcc/analyzer/region-model.h
@@ -1578,8 +1578,12 @@ class region_model
 
   void check_for_poison (tree expr, region_model_context *ctxt);
   void on_assignment (const gassign *stmt, region_model_context *ctxt);
-  void on_call_pre (const gcall *stmt, region_model_context *ctxt);
-  void on_call_post (const gcall *stmt, region_model_context *ctxt);
+  bool on_call_pre (const gcall *stmt, region_model_context *ctxt);
+  void on_call_post (const gcall *stmt,
+		     bool unknown_side_effects,
+		     region_model_context *ctxt);
+  void handle_unrecognized_call (const gcall *call,
+				 region_model_context *ctxt);
   void on_return (const greturn *stmt, region_model_context *ctxt);
   void on_setjmp (const gcall *stmt, const exploded_node *enode,
 		  region_model_context *ctxt);
@@ -1827,6 +1831,10 @@ class region_model_context
      to ptrs becoming known to be NULL or non-NULL, rather than just
      "unchecked") */
   virtual void on_condition (tree lhs, enum tree_code op, tree rhs) = 0;
+
+  /* Hooks for clients to be notified when an unknown change happens
+     to SID (in response to a call to an unknown function).  */
+  virtual void on_unknown_change (svalue_id sid) = 0;
 };
 
 /* A bundle of data for use when attempting to merge two region_model
@@ -1993,6 +2001,10 @@ public:
   {
   }
 
+  void on_unknown_change (svalue_id sid ATTRIBUTE_UNUSED) FINAL OVERRIDE
+  {
+  }
+
 private:
   /* Implicitly delete any diagnostics in the dtor.  */
   auto_delete_vec<pending_diagnostic> m_diagnostics;
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 1cdaa810d77..efff14c4141 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,17 @@
+2020-01-14  David Malcolm  <dmalcolm@redhat.com>
+
+	* gcc.dg/analyzer/data-model-1.c: Remove xfail.
+	* gcc.dg/analyzer/data-model-5b.c: Likewise.
+	* gcc.dg/analyzer/data-model-5c.c: Likewise.
+	* gcc.dg/analyzer/setjmp-3.c: Mark "foo" as pure.
+	* gcc.dg/analyzer/setjmp-4.c: Likewise.
+	* gcc.dg/analyzer/setjmp-6.c: Likewise.
+	* gcc.dg/analyzer/setjmp-7.c: Likewise.
+	* gcc.dg/analyzer/setjmp-7a.c: Likewise.
+	* gcc.dg/analyzer/setjmp-8.c: Likewise.
+	* gcc.dg/analyzer/setjmp-9.c: Likewise.
+	* gcc.dg/analyzer/unknown-fns.c: New test.
+
 2020-01-14  David Malcolm  <dmalcolm@redhat.com>
 
 	* gcc.dg/analyzer/CVE-2005-1689-dedupe-issue.c: New test.
diff --git a/gcc/testsuite/gcc.dg/analyzer/data-model-1.c b/gcc/testsuite/gcc.dg/analyzer/data-model-1.c
index 7260e3bb59a..a5840a25944 100644
--- a/gcc/testsuite/gcc.dg/analyzer/data-model-1.c
+++ b/gcc/testsuite/gcc.dg/analyzer/data-model-1.c
@@ -326,9 +326,7 @@ void test_16e (int i)
   __analyzer_eval (j == i); /* { dg-warning "TRUE" } */
 
   might_write_to (&j);
-  __analyzer_eval (j == i); /* { dg-warning "UNKNOWN" "" { xfail *-*-* } } */
-  /* { dg-warning "TRUE" "" { target *-*-* } .-1 } */
-  // TODO(xfail)
+  __analyzer_eval (j == i); /* { dg-warning "UNKNOWN" } */
 }
 
 /* TODO: and more complicated graph-like examples, where anything that's
diff --git a/gcc/testsuite/gcc.dg/analyzer/data-model-5b.c b/gcc/testsuite/gcc.dg/analyzer/data-model-5b.c
index b0203af9975..6866f5bf469 100644
--- a/gcc/testsuite/gcc.dg/analyzer/data-model-5b.c
+++ b/gcc/testsuite/gcc.dg/analyzer/data-model-5b.c
@@ -87,5 +87,4 @@ void test_1 (const char *str)
   //__analyzer_dump();
   if (obj)
     unref (obj);
-} /* { dg-bogus "leak of 'obj'" "" { xfail *-*-* } } */
-// TODO (xfail): not sure why this is treated as leaking
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/data-model-5c.c b/gcc/testsuite/gcc.dg/analyzer/data-model-5c.c
index 1e52350c6c1..4dc559c1fcd 100644
--- a/gcc/testsuite/gcc.dg/analyzer/data-model-5c.c
+++ b/gcc/testsuite/gcc.dg/analyzer/data-model-5c.c
@@ -66,19 +66,13 @@ string_obj *new_string_obj (const char *str)
 
 void unref (string_obj *obj)
 {
-  //__analyzer_dump();
   if (--obj->str_base.ob_refcnt == 0)
-    {
-      //__analyzer_dump();
-      free (obj);
-    }
+    free (obj);
 }
 
 void test_1 (const char *str)
 {
   string_obj *obj = new_string_obj (str);
-  //__analyzer_dump();
   if (obj)
     unref (obj);
-} /* { dg-bogus "leak of 'obj'" "" { xfail *-*-* } } */
-// TODO (xfail): not sure why this is treated as leaking
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/setjmp-3.c b/gcc/testsuite/gcc.dg/analyzer/setjmp-3.c
index 19504d20c44..0c082b82a70 100644
--- a/gcc/testsuite/gcc.dg/analyzer/setjmp-3.c
+++ b/gcc/testsuite/gcc.dg/analyzer/setjmp-3.c
@@ -5,7 +5,7 @@
 #include <stddef.h>
 #include "analyzer-decls.h"
 
-extern void foo (int);
+extern int foo (int) __attribute__ ((__pure__));
 
 static jmp_buf env;
 
diff --git a/gcc/testsuite/gcc.dg/analyzer/setjmp-4.c b/gcc/testsuite/gcc.dg/analyzer/setjmp-4.c
index 5325612855a..bfac6170d91 100644
--- a/gcc/testsuite/gcc.dg/analyzer/setjmp-4.c
+++ b/gcc/testsuite/gcc.dg/analyzer/setjmp-4.c
@@ -4,7 +4,7 @@
 #include <setjmp.h>
 #include "analyzer-decls.h"
 
-extern int foo (int);
+extern int foo (int) __attribute__ ((__pure__));
 static jmp_buf buf;
 
 void inner (int x)
diff --git a/gcc/testsuite/gcc.dg/analyzer/setjmp-6.c b/gcc/testsuite/gcc.dg/analyzer/setjmp-6.c
index 84a6318ed3c..d7319129070 100644
--- a/gcc/testsuite/gcc.dg/analyzer/setjmp-6.c
+++ b/gcc/testsuite/gcc.dg/analyzer/setjmp-6.c
@@ -2,7 +2,7 @@
 #include <stddef.h>
 #include <stdlib.h>
 
-extern void foo (int);
+extern int foo (int) __attribute__ ((__pure__));
 
 static jmp_buf env;
 
diff --git a/gcc/testsuite/gcc.dg/analyzer/setjmp-7.c b/gcc/testsuite/gcc.dg/analyzer/setjmp-7.c
index ee4183dfb2a..3a14534434d 100644
--- a/gcc/testsuite/gcc.dg/analyzer/setjmp-7.c
+++ b/gcc/testsuite/gcc.dg/analyzer/setjmp-7.c
@@ -2,7 +2,7 @@
 #include <stddef.h>
 #include <stdlib.h>
 
-extern void foo (int);
+extern int foo (int) __attribute__ ((__pure__));
 
 static jmp_buf env;
 
diff --git a/gcc/testsuite/gcc.dg/analyzer/setjmp-7a.c b/gcc/testsuite/gcc.dg/analyzer/setjmp-7a.c
index 10cb4c165c4..1e2c348af3e 100644
--- a/gcc/testsuite/gcc.dg/analyzer/setjmp-7a.c
+++ b/gcc/testsuite/gcc.dg/analyzer/setjmp-7a.c
@@ -4,7 +4,7 @@
 #include <setjmp.h>
 #include <stdlib.h>
 
-extern void foo (int);
+extern int foo (int) __attribute__ ((__pure__));
 
 static jmp_buf env;
 
diff --git a/gcc/testsuite/gcc.dg/analyzer/setjmp-8.c b/gcc/testsuite/gcc.dg/analyzer/setjmp-8.c
index 2fb88d2ae64..fb931653803 100644
--- a/gcc/testsuite/gcc.dg/analyzer/setjmp-8.c
+++ b/gcc/testsuite/gcc.dg/analyzer/setjmp-8.c
@@ -5,7 +5,7 @@
 #include <stddef.h>
 #include "analyzer-decls.h"
 
-extern void foo (int);
+extern int foo (int) __attribute__ ((__pure__));
 
 static jmp_buf env;
 
diff --git a/gcc/testsuite/gcc.dg/analyzer/setjmp-9.c b/gcc/testsuite/gcc.dg/analyzer/setjmp-9.c
index c17aaa10fd0..fa2d3152c27 100644
--- a/gcc/testsuite/gcc.dg/analyzer/setjmp-9.c
+++ b/gcc/testsuite/gcc.dg/analyzer/setjmp-9.c
@@ -5,7 +5,7 @@
 #include <stddef.h>
 #include "analyzer-decls.h"
 
-extern void foo (int);
+extern int foo (int) __attribute__ ((__pure__));
 
 static jmp_buf env;
 
diff --git a/gcc/testsuite/gcc.dg/analyzer/unknown-fns.c b/gcc/testsuite/gcc.dg/analyzer/unknown-fns.c
new file mode 100644
index 00000000000..76cb68eaa56
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/unknown-fns.c
@@ -0,0 +1,115 @@
+/* Verify that the analyzer correctly purges state when it sees a call to
+   an unknown function.  */
+
+#include <stdlib.h>
+
+/* Verify fix for false-positive when checking for CVE-2005-1689.  */
+
+typedef struct _krb5_data {
+  char *data;
+} krb5_data;
+
+extern void krb5_read_message(krb5_data *buf);
+
+void
+test_1 (krb5_data inbuf)
+{
+  free(inbuf.data);
+  krb5_read_message(&inbuf); 
+  free(inbuf.data); /* { dg-bogus "double-'free'" } */
+}
+
+/* Verify that __pure__ functions are treated as not having side-effects.  */
+
+extern int called_by_test_1a (void *)
+  __attribute__ ((__pure__));
+void test_1a (krb5_data inbuf)
+{
+  free (inbuf.data);
+  called_by_test_1a (&inbuf);
+  free (inbuf.data); /* { dg-warning "double-'free'" } */
+}
+
+/* Verify that global pointers can be affected by an unknown function.  */
+
+void *global_ptr;
+extern void unknown_side_effects (void);
+
+void test_2 (void)
+{
+  free (global_ptr);
+  unknown_side_effects ();
+  free (global_ptr);
+}
+
+extern void called_by_test_3 (void *);
+
+void test_3a (void)
+{
+  void *ptr = malloc (1024);
+  called_by_test_3 (ptr);
+}  /* { dg-bogus "leak" } */
+
+void test_3b (void)
+{
+  krb5_data k;
+  k.data = malloc (1024);
+  called_by_test_3 (&k);
+} /* { dg-bogus "leak" } */
+
+/* Verify that we traverse the graph of regions that are reachable from
+   the call.  */
+
+struct foo
+{
+  struct foo *next;
+  int *ptr;
+};
+
+/* First, without a call to an unknown function.  */
+
+void test_4a (void)
+{
+  struct foo node_a;
+  struct foo node_b;
+  node_a.next = &node_b;
+  node_b.ptr = malloc (sizeof (int));
+  global_ptr = &node_a;
+  *node_b.ptr = 42; /* { dg-warning "possibly-NULL" } */
+  /* { dg-warning "leak" "" { target *-*-* } .-1 } */
+  /* FIXME: the above leak report is correct, but is reported at the wrong
+     location.  */
+} /* { dg-warning "leak" } */
+
+/* With a call to an unknown function.  */
+
+void test_4b (void)
+{
+  struct foo node_a;
+  struct foo node_b;
+  node_a.next = &node_b;
+  node_b.ptr = malloc (sizeof (int));
+  global_ptr = &node_a;
+  unknown_side_effects (); /* everything potentially visible through global_ptr.  */
+  *node_b.ptr = 42; /* { dg-bogus "possibly-NULL" } */
+} /* { dg-bogus "leak" } */
+
+extern void called_by_test_5 (const char *);
+void test_5 (void)
+{
+  called_by_test_5 ("???");
+}
+
+extern void called_by_test_6 (const struct foo *);
+void test_6 (void)
+{
+  struct foo node;
+  node.next = NULL;
+  node.ptr = malloc (sizeof (int));
+
+  /* This is a const ptr, but struct foo's ptr is non-const,
+     so we ought to assume it could be written to.  */
+  called_by_test_6 (&node);
+} /* { dg-bogus "leak" } */
+
+/* TODO: things reachable from "outside" i.e. by params to caller to entrypoint.  */
-- 
2.30.2