analyzer: fix taint false positives with UNKNOWN [PR112850]

PR analyzer/112850 reports a false positive from
-Wanalyzer-tainted-allocation-size on the Linux kernel [1] where
-fanalyzer complains that an allocation size is attacker-controlled
despite the value being correctly sanitized against upper and lower
limits.

The root cause is that the expression is sufficiently complex
to exceed the -param=analyzer-max-svalue-depth= threshold,
currently at 12, with depth 13, and so it is treated as UNKNOWN.
Hence the sanitizations are seen as comparisons of an UNKNOWN
symbolic value against constants, and these were being ignored
by the taint state machine.

The expression in question is relatively typical for those seen in
Linux kernel ioctl handlers, and I was surprised that it had exceeded
the analyzer's default expression complexity limit.

This patch addresses this problem in three ways:
(a) the default value of the threshold parameter is increased, from 12
to 18, so that such expressions are precisely handled
(b) adding a new -Wanalyzer-symbol-too-complex to warn when the symbol
complexity limit is reached.  This is off by default for users, and
on by default in the test suite.
(c) the taint state machine handles comparisons against UNKNOWN svalues
by dropping all taint information on that execution path, so that if
the complexity limit has been exceeded we don't generate false positives

As well as fixing the taint false positive (PR analyzer/112850), the
patch also fixes a couple of leak false positives seen on flex-generated
scanners (PR analyzer/103546).

[1] specifically, in sound/core/rawmidi.c's handler for
SNDRV_RAWMIDI_STREAM_OUTPUT.

gcc/ChangeLog:
	PR analyzer/103546
	PR analyzer/112850
	* doc/invoke.texi: Add -Wanalyzer-symbol-too-complex.

gcc/analyzer/ChangeLog:
	PR analyzer/103546
	PR analyzer/112850
	* analyzer.opt (-param=analyzer-max-svalue-depth=): Increase from
	12 to 18.
	(Wanalyzer-symbol-too-complex): New.
	* diagnostic-manager.cc
	(null_assignment_sm_context::clear_all_per_svalue_state): New.
	* engine.cc (impl_sm_context::clear_all_per_svalue_state): New.
	* program-state.cc (sm_state_map::clear_all_per_svalue_state):
	New.
	* program-state.h (sm_state_map::clear_all_per_svalue_state): New
	decl.
	* region-model-manager.cc
	(region_model_manager::reject_if_too_complex): Add
	-Wanalyzer-symbol-too-complex.
	* sm-taint.cc (taint_state_machine::on_condition): Handle
	comparisons against UNKNOWN.
	* sm.h (sm_context::clear_all_per_svalue_state): New.

gcc/testsuite/ChangeLog:
	PR analyzer/103546
	PR analyzer/112850
	* c-c++-common/analyzer/call-summaries-pr107158-2.c: Add
	-Wno-analyzer-symbol-too-complex.
	* c-c++-common/analyzer/call-summaries-pr107158.c: Likewise.
	* c-c++-common/analyzer/deref-before-check-pr109060-haproxy-cfgparse.c:
	Likewise.
	* c-c++-common/analyzer/feasibility-3.c: Add
	-Wno-analyzer-too-complex and -Wno-analyzer-symbol-too-complex.
	* c-c++-common/analyzer/flex-with-call-summaries.c: Add
	-Wno-analyzer-symbol-too-complex.  Remove fail for
	PR analyzer/103546 leak false positive.
	* c-c++-common/analyzer/flex-without-call-summaries.c: Remove
	xfail for PR analyzer/103546 leak false positive.
	* c-c++-common/analyzer/infinite-recursion-3.c: Add
	-Wno-analyzer-symbol-too-complex.
	* c-c++-common/analyzer/null-deref-pr108251-smp_fetch_ssl_fc_has_early-O2.c:
	Likewise.
	* c-c++-common/analyzer/null-deref-pr108251-smp_fetch_ssl_fc_has_early.c:
	Likewise.
	* c-c++-common/analyzer/null-deref-pr108400-SoftEtherVPN-WebUi.c:
	Likewise.
	* c-c++-common/analyzer/null-deref-pr108806-qemu.c: Likewise.
	* c-c++-common/analyzer/null-deref-pr108830.c: Likewise.
	* c-c++-common/analyzer/pr94596.c: Likewise.
	* c-c++-common/analyzer/strtok-2.c: Likewise.
	* c-c++-common/analyzer/strtok-4.c: Add -Wno-analyzer-too-complex
	and -Wno-analyzer-symbol-too-complex.
	* c-c++-common/analyzer/strtok-cppreference.c: Likewise.
	* gcc.dg/analyzer/analyzer.exp: Add -Wanalyzer-symbol-too-complex
	to DEFAULT_CFLAGS.
	* gcc.dg/analyzer/attr-const-3.c: Add
	-Wno-analyzer-symbol-too-complex.
	* gcc.dg/analyzer/call-summaries-pr107072.c: Likewise.
	* gcc.dg/analyzer/doom-s_sound-pr108867.c: Likewise.
	* gcc.dg/analyzer/explode-4.c: Likewise.
	* gcc.dg/analyzer/null-deref-pr102671-1.c: Likewise.
	* gcc.dg/analyzer/null-deref-pr105755.c: Likewise.
	* gcc.dg/analyzer/out-of-bounds-curl.c: Likewise.
	* gcc.dg/analyzer/pr101503.c: Likewise.
	* gcc.dg/analyzer/pr103892.c: Add -Wno-analyzer-too-complex and
	-Wno-analyzer-symbol-too-complex.
	* gcc.dg/analyzer/pr94851-4.c: Add
	-Wno-analyzer-symbol-too-complex.
	* gcc.dg/analyzer/pr96860-1.c: Likewise.
	* gcc.dg/analyzer/pr96860-2.c: Likewise.
	* gcc.dg/analyzer/pr98918.c: Likewise.
	* gcc.dg/analyzer/pr99044-2.c: Likewise.
	* gcc.dg/analyzer/uninit-pr108806-qemu.c: Likewise.
	* gcc.dg/analyzer/use-after-free.c: Add -Wno-analyzer-too-complex
	and -Wno-analyzer-symbol-too-complex.
	* gcc.dg/plugin/plugin.exp: Add new tests for
	analyzer_kernel_plugin.c.
	* gcc.dg/plugin/taint-CVE-2011-0521-4.c: Update expected results.
	* gcc.dg/plugin/taint-CVE-2011-0521-5.c: Likewise.
	* gcc.dg/plugin/taint-CVE-2011-0521-6.c: Likewise.
	* gcc.dg/plugin/taint-CVE-2011-0521-5-fixed.c: Remove xfail.
	* gcc.dg/plugin/taint-pr112850-precise.c: New test.
	* gcc.dg/plugin/taint-pr112850-too-complex.c: New test.
	* gcc.dg/plugin/taint-pr112850-unsanitized.c: New test.
	* gcc.dg/plugin/taint-pr112850.c: New test.

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

8 files changed, 50 insertions, 1 deletions

diff --git a/gcc/analyzer/analyzer.opt b/gcc/analyzer/analyzer.opt
index a3c30ca..d0fe5a4 100644
--- a/gcc/analyzer/analyzer.opt
+++ b/gcc/analyzer/analyzer.opt
@@ -43,7 +43,7 @@ Common Joined UInteger Var(param_analyzer_max_recursion_depth) Init(2) Param
 The maximum number of times a callsite can appear in a call stack within the analyzer, before terminating analysis of a call that would recurse deeper.
 
 -param=analyzer-max-svalue-depth=
-Common Joined UInteger Var(param_analyzer_max_svalue_depth) Init(12) Param
+Common Joined UInteger Var(param_analyzer_max_svalue_depth) Init(18) Param
 The maximum depth of a symbolic value, before approximating the value as unknown.
 
 -param=analyzer-min-snodes-for-call-summary=
@@ -262,6 +262,10 @@ Wanalyzer-use-of-uninitialized-value
 Common Var(warn_analyzer_use_of_uninitialized_value) Init(1) Warning
 Warn about code paths in which an uninitialized value is used.
 
+Wanalyzer-symbol-too-complex
+Common Var(warn_analyzer_symbol_too_complex) Init(0) Warning
+Warn if expressions are too complicated for the analyzer to fully track.
+
 Wanalyzer-too-complex
 Common Var(warn_analyzer_too_complex) Init(0) Warning
 Warn if the code is too complicated for the analyzer to fully explore.
diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc
index ecd5737..38bd308 100644
--- a/gcc/analyzer/diagnostic-manager.cc
+++ b/gcc/analyzer/diagnostic-manager.cc
@@ -2043,6 +2043,11 @@ struct null_assignment_sm_context : public sm_context
     /* No-op.  */
   }
 
+  void clear_all_per_svalue_state () final override
+  {
+    /* No-op.  */
+  }
+
   void on_custom_transition (custom_transition *) final override
   {
   }
diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index 825b3af..d2524e3 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -474,6 +474,11 @@ public:
     m_new_state->m_checker_states[m_sm_idx]->set_global_state (state);
   }
 
+  void clear_all_per_svalue_state () final override
+  {
+    m_new_state->m_checker_states[m_sm_idx]->clear_all_per_svalue_state ();
+  }
+
   void on_custom_transition (custom_transition *transition) final override
   {
     transition->impl_transition (&m_eg,
diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
index 9bb81e6..78f739e 100644
--- a/gcc/analyzer/program-state.cc
+++ b/gcc/analyzer/program-state.cc
@@ -526,6 +526,14 @@ sm_state_map::clear_any_state (const svalue *sval)
   m_map.remove (sval);
 }
 
+/* Clear all per-svalue state within this state map.  */
+
+void
+sm_state_map::clear_all_per_svalue_state ()
+{
+  m_map.empty ();
+}
+
 /* Set the "global" state within this state map to STATE.  */
 
 void
diff --git a/gcc/analyzer/program-state.h b/gcc/analyzer/program-state.h
index c9b3aa0..ef1a2ad 100644
--- a/gcc/analyzer/program-state.h
+++ b/gcc/analyzer/program-state.h
@@ -146,6 +146,7 @@ public:
 		       const svalue *origin,
 		       const extrinsic_state &ext_state);
   void clear_any_state (const svalue *sval);
+  void clear_all_per_svalue_state ();
 
   void set_global_state (state_machine::state_t state);
   state_machine::state_t get_global_state () const;
diff --git a/gcc/analyzer/region-model-manager.cc b/gcc/analyzer/region-model-manager.cc
index 921edc5..b631bcb 100644
--- a/gcc/analyzer/region-model-manager.cc
+++ b/gcc/analyzer/region-model-manager.cc
@@ -185,6 +185,16 @@ region_model_manager::reject_if_too_complex (svalue *sval)
       return false;
     }
 
+  pretty_printer pp;
+  pp_format_decoder (&pp) = default_tree_printer;
+  sval->dump_to_pp (&pp, true);
+  if (warning_at (input_location, OPT_Wanalyzer_symbol_too_complex,
+		  "symbol too complicated: %qs",
+		  pp_formatted_text (&pp)))
+    inform (input_location,
+	    "max_depth %i exceeds --param=analyzer-max-svalue-depth=%i",
+	    c.m_max_depth, param_analyzer_max_svalue_depth);
+
   delete sval;
   return true;
 }
diff --git a/gcc/analyzer/sm-taint.cc b/gcc/analyzer/sm-taint.cc
index d01e3f0..6b5d51c 100644
--- a/gcc/analyzer/sm-taint.cc
+++ b/gcc/analyzer/sm-taint.cc
@@ -1038,6 +1038,20 @@ taint_state_machine::on_condition (sm_context *sm_ctxt,
   if (stmt == NULL)
     return;
 
+  if (lhs->get_kind () == SK_UNKNOWN
+      || rhs->get_kind () == SK_UNKNOWN)
+    {
+      /* If we have a comparison against UNKNOWN, then
+	 we've presumably hit the svalue complexity limit,
+	 and we don't know what is being sanitized.
+	 Give up on any taint already found on this execution path.  */
+      // TODO: warn about this
+      if (get_logger ())
+	get_logger ()->log ("comparison against UNKNOWN; removing all taint");
+      sm_ctxt->clear_all_per_svalue_state ();
+      return;
+    }
+
   // TODO
   switch (op)
     {
diff --git a/gcc/analyzer/sm.h b/gcc/analyzer/sm.h
index 3ff9c26..ef63d73 100644
--- a/gcc/analyzer/sm.h
+++ b/gcc/analyzer/sm.h
@@ -299,6 +299,8 @@ public:
   virtual state_machine::state_t get_global_state () const = 0;
   virtual void set_global_state (state_machine::state_t) = 0;
 
+  virtual void clear_all_per_svalue_state () = 0;
+
   /* A vfunc for handling custom transitions, such as when registering
      a signal handler.  */
   virtual void on_custom_transition (custom_transition *transition) = 0;