[pushed] analyzer: fix false +ves from -Wanalyzer-tainted-array-index with unsigned char index [PR106229]

[pushed] analyzer: fix false +ves from -Wanalyzer-tainted-array-index with unsigned char index [PR106229]

[David Malcolm]

Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.
Successful run of analyzer integration tests on x86_64-pc-linux-gnu.
Pushed to trunk as r14-7266-gce27b66d952127.

gcc/analyzer/ChangeLog:
	PR analyzer/106229
	* analyzer.h (compare_constants): New decl.
	* constraint-manager.cc (compare_constants): Make non-static.
	* sm-taint.cc: Add include "fold-const.h".
	(class concrete_range): New.
	(get_possible_range): New.
	(index_can_be_out_of_bounds_p): New.
	(region_model::check_region_for_taint): Reject
	-Wanalyzer-tainted-array-index if the type of the value makes it
	impossible for it to be out-of-bounds of the array.

gcc/testsuite/ChangeLog:
	PR analyzer/106229
	* c-c++-common/analyzer/taint-index-pr106229.c: New test.

Signed-off-by: David Malcolm <dmalcolm@redhat.com>
---
 gcc/analyzer/analyzer.h                       |   3 +
 gcc/analyzer/constraint-manager.cc            |   2 +-
 gcc/analyzer/sm-taint.cc                      | 114 +++++++++++++++++-
 .../analyzer/taint-index-pr106229.c           | 109 +++++++++++++++++
 4 files changed, 223 insertions(+), 5 deletions(-)
 create mode 100644 gcc/testsuite/c-c++-common/analyzer/taint-index-pr106229.c

diff --git a/gcc/analyzer/analyzer.h b/gcc/analyzer/analyzer.h
index 8dec9649f2fb..23e3f71df0af 100644
--- a/gcc/analyzer/analyzer.h
+++ b/gcc/analyzer/analyzer.h
@@ -427,6 +427,9 @@ bit_offset_to_json (const bit_offset_t &offset);
 extern json::value *
 byte_offset_to_json (const byte_offset_t &offset);
 
+extern tristate
+compare_constants (tree lhs_const, enum tree_code op, tree rhs_const);
+
 } // namespace ana
 
 extern bool is_special_named_call_p (const gcall *call, const char *funcname,
diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc
index 2db6c1734638..e8bcabeb0cd5 100644
--- a/gcc/analyzer/constraint-manager.cc
+++ b/gcc/analyzer/constraint-manager.cc
@@ -54,7 +54,7 @@ along with GCC; see the file COPYING3.  If not see
 
 namespace ana {
 
-static tristate
+tristate
 compare_constants (tree lhs_const, enum tree_code op, tree rhs_const)
 {
   tree comparison
diff --git a/gcc/analyzer/sm-taint.cc b/gcc/analyzer/sm-taint.cc
index 3f7e5cd55837..dc4b078c411f 100644
--- a/gcc/analyzer/sm-taint.cc
+++ b/gcc/analyzer/sm-taint.cc
@@ -40,6 +40,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "digraph.h"
 #include "stringpool.h"
 #include "attribs.h"
+#include "fold-const.h"
 #include "analyzer/supergraph.h"
 #include "analyzer/call-string.h"
 #include "analyzer/program-point.h"
@@ -1369,6 +1370,104 @@ make_taint_state_machine (logger *logger)
   return new taint_state_machine (logger);
 }
 
+/* A closed concrete range.  */
+
+class concrete_range
+{
+public:
+  /* Return true iff THIS is fully within OTHER
+     i.e.
+     - m_min must be >= OTHER.m_min
+     - m_max must be <= OTHER.m_max.  */
+  bool within_p (const concrete_range &other) const
+  {
+    if (compare_constants (m_min, GE_EXPR, other.m_min).is_true ())
+      if (compare_constants (m_max, LE_EXPR, other.m_max).is_true ())
+	return true;
+    return false;
+  }
+
+  tree m_min;
+  tree m_max;
+};
+
+/* Attempt to get a closed concrete range for SVAL based on types.
+   If found, write to *OUT and return true.
+   Otherwise return false.  */
+
+static bool
+get_possible_range (const svalue *sval, concrete_range *out)
+{
+  if (const svalue *inner = sval->maybe_undo_cast ())
+    {
+      concrete_range inner_range;
+      if (!get_possible_range (inner, &inner_range))
+	return false;
+
+      if (sval->get_type ()
+	  && inner->get_type ()
+	  && INTEGRAL_TYPE_P (sval->get_type ())
+	  && INTEGRAL_TYPE_P (inner->get_type ())
+	  && TYPE_UNSIGNED (inner->get_type ())
+	  && (TYPE_PRECISION (sval->get_type ())
+	      > TYPE_PRECISION (inner->get_type ())))
+	{
+	  /* We have a cast from an unsigned type to a wider integral type.
+	     Assuming this is zero-extension, we can inherit the range from
+	     the inner type.  */
+	  enum tree_code op = ((const unaryop_svalue *)sval)->get_op ();
+	  out->m_min = fold_unary (op, sval->get_type (), inner_range.m_min);
+	  out->m_max = fold_unary (op, sval->get_type (), inner_range.m_max);
+	  return true;
+	}
+    }
+
+  if (sval->get_type ()
+      && INTEGRAL_TYPE_P (sval->get_type ()))
+    {
+      out->m_min = TYPE_MIN_VALUE (sval->get_type ());
+      out->m_max = TYPE_MAX_VALUE (sval->get_type ());
+      return true;
+    }
+
+  return false;
+}
+
+/* Determine if it's possible for tainted array access ELEMENT_REG to
+   actually be a problem.
+
+   Check here for index being from e.g. unsigned char when the array
+   contains >= 255 elements.
+
+   Return true if out-of-bounds is possible, false if it's impossible
+   (for suppressing false positives).  */
+
+static bool
+index_can_be_out_of_bounds_p (const element_region *element_reg)
+{
+  const svalue *index = element_reg->get_index ();
+  const region *array_reg = element_reg->get_parent_region ();
+
+  if (array_reg->get_type ()
+      && TREE_CODE (array_reg->get_type ()) == ARRAY_TYPE
+      && TYPE_DOMAIN (array_reg->get_type ())
+      && INTEGRAL_TYPE_P (TYPE_DOMAIN (array_reg->get_type ())))
+    {
+      concrete_range valid_index_range;
+      valid_index_range.m_min
+	= TYPE_MIN_VALUE (TYPE_DOMAIN (array_reg->get_type ()));
+      valid_index_range.m_max
+	= TYPE_MAX_VALUE (TYPE_DOMAIN (array_reg->get_type ()));
+
+      concrete_range possible_index_range;
+      if (get_possible_range (index, &possible_index_range))
+	if (possible_index_range.within_p (valid_index_range))
+	  return false;
+    }
+
+  return true;
+}
+
 /* Complain to CTXT if accessing REG leads could lead to arbitrary
    memory access under an attacker's control (due to taint).  */
 
@@ -1415,10 +1514,17 @@ region_model::check_region_for_taint (const region *reg,
 	    gcc_assert (state);
 	    enum bounds b;
 	    if (taint_sm.get_taint (state, index->get_type (), &b))
-	    {
-	      tree arg = get_representative_tree (index);
-	      ctxt->warn (make_unique<tainted_array_index> (taint_sm, arg, b));
-	    }
+	      {
+		if (index_can_be_out_of_bounds_p (element_reg))
+		  {
+		    tree arg = get_representative_tree (index);
+		    ctxt->warn (make_unique<tainted_array_index> (taint_sm,
+								  arg, b));
+		  }
+		else if (ctxt->get_logger ())
+		  ctxt->get_logger ()->log ("rejecting tainted_array_index as"
+					    " out of bounds is not possible");
+	      }
 	  }
 	  break;
 
diff --git a/gcc/testsuite/c-c++-common/analyzer/taint-index-pr106229.c b/gcc/testsuite/c-c++-common/analyzer/taint-index-pr106229.c
new file mode 100644
index 000000000000..76dca630a038
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/analyzer/taint-index-pr106229.c
@@ -0,0 +1,109 @@
+#include <stdint.h>
+
+/* Attacker-controlled 8 bit values where the array isn't
+   necessarily big enough.  We should warn about these.  */
+
+struct st_s8_field_255_elements
+{
+  int8_t idx;
+  char buf[255];
+};
+
+char __attribute__((tainted_args))
+test_s8_field_255_elements (struct st_s8_field_255_elements s)
+{
+  return s.buf[s.idx]; /* { dg-warning "tainted-array-index" } */
+}
+
+struct st_u8_field_255_elements
+{
+  uint8_t idx;
+  char buf[255];
+};
+
+char __attribute__((tainted_args))
+test_u8_field_255_elements (struct st_u8_field_255_elements s)
+{
+  return s.buf[s.idx]; /* { dg-warning "tainted-array-index" } */
+}
+
+/* Attacker-controlled 8 bit values where the array is
+   big enough, but where the value might be signed.  */
+
+struct st_s8_field_256_elements
+{
+  int8_t idx;
+  char buf[256];
+};
+
+char __attribute__((tainted_args))
+test_s8_field_256_elements (struct st_s8_field_256_elements s)
+{
+  return s.buf[s.idx]; /* { dg-warning "tainted-array-index" } */
+}
+
+struct st_u8_field_256_elements
+{
+  uint8_t idx;
+  char buf[256];
+};
+
+char __attribute__((tainted_args))
+test_u8_field_256_elements (struct st_u8_field_256_elements s)
+{
+  return s.buf[s.idx]; /* { dg-bogus "tainted-array-index" } */
+}
+
+/* Attacker-controlled 16 bit values where the array isn't
+   necessarily big enough.  We should warn about these.  */
+
+struct st_s16_field_256_elements
+{
+  int16_t idx;
+  char buf[256];
+};
+
+char __attribute__((tainted_args))
+test_s16_field_256_elements (struct st_s16_field_256_elements s)
+{
+  return s.buf[s.idx]; /* { dg-warning "tainted-array-index" } */
+}
+
+struct st_u16_field_256_elements
+{
+  uint16_t idx;
+  char buf[256];
+};
+
+char __attribute__((tainted_args))
+test_u16_field_256_elements (struct st_u16_field_256_elements s)
+{
+  return s.buf[s.idx]; /* { dg-warning "tainted-array-index" } */
+}
+
+/* Attacker-controlled 16 bit values where the array is
+   big enough, but where the value might be signed.  */
+
+struct st_s16_field_65536_elements
+{
+  int16_t idx;
+  char buf[65536];
+};
+
+char __attribute__((tainted_args))
+test_s16_field_65536_elements (struct st_s16_field_65536_elements s)
+{
+  return s.buf[s.idx]; /* { dg-warning "tainted-array-index" } */
+}
+
+struct st_u16_field_65536_elements
+{
+  uint16_t idx;
+  char buf[65536];
+};
+
+char __attribute__((tainted_args))
+test_u16_field_65536_elements (struct st_u16_field_65536_elements s)
+{
+  return s.buf[s.idx]; /* { dg-bogus "tainted-array-index" } */
+}
-- 
2.26.3