analyzer: support for symbolic values in the out-of-bounds checker [PR106625]

This patch adds support for reasoning about the inequality of two symbolic
values in the special case specifically suited for reasoning about
out-of-bounds past the end of the buffer. With this patch, the analyzer
catches off-by-one errors and more even when the offset and capacity is
symbolic.

Regrtested on Linux x86_64 and tested on coreutils, curl, httpd and
openssh as usual.

2022-09-07  Tim Lange  <mail@tim-lange.me>

gcc/analyzer/ChangeLog:

	PR analyzer/106625
	* analyzer.h (region_offset): Eliminate m_is_symbolic member.
	* region-model-impl-calls.cc (region_model::impl_call_realloc):
	Refine implementation to be more precise.
	* region-model.cc (class symbolic_past_the_end):
	Abstract diagnostic class to complain about accesses past the end
	with symbolic values.
	(class symbolic_buffer_overflow):
	Concrete diagnostic class to complain about buffer overflows with
	symbolic values.
	(class symbolic_buffer_overread):
	Concrete diagnostic class to complain about buffer overreads with
	symbolic values.
	(region_model::check_symbolic_bounds): New function.
	(maybe_get_integer_cst_tree): New helper function.
	(region_model::check_region_bounds):
	Add call to check_symbolic_bounds if offset is not concrete.
	(region_model::eval_condition_without_cm):
	Add support for EQ_EXPR and GT_EXPR with binaryop_svalues.
	(is_positive_svalue): New hleper function.
	(region_model::symbolic_greater_than):
	New function to handle GT_EXPR comparisons with symbolic values.
	(region_model::structural_equality): New function to compare
	whether two svalues are structured the same, i.e. evaluate to
	the same value.
	(test_struct): Reflect changes to region::calc_offset.
	(test_var): Likewise.
	(test_array_2): Likewise and add selftest with symbolic i.
	* region-model.h (class region_model): Add check_symbolic_bounds,
	symbolic_greater_than and structural_equality.
	* region.cc (region::get_offset):
	Reflect changes to region::calc_offset.
	(region::calc_offset):
	Compute the symbolic offset if the offset is not concrete.
	(region::get_relative_symbolic_offset): New function to return the
	symbolic offset in bytes relative to its parent.
	(field_region::get_relative_symbolic_offset): Likewise.
	(element_region::get_relative_symbolic_offset): Likewise.
	(offset_region::get_relative_symbolic_offset): Likewise.
	(bit_range_region::get_relative_symbolic_offset): Likewise.
	* region.h: Add get_relative_symbolic_offset.
	* store.cc (binding_key::make):
	Reflect changes to region::calc_offset.
	(binding_map::apply_ctor_val_to_range): Likewise.
	(binding_map::apply_ctor_pair_to_child_region): Likewise.
	(binding_cluster::bind_compound_sval): Likewise.
	(binding_cluster::get_any_binding): Likewise.
	(binding_cluster::maybe_get_compound_binding): Likewise.

gcc/ChangeLog:

	PR analyzer/106625
	* doc/invoke.texi:
	State that the checker also reasons about symbolic values.

gcc/testsuite/ChangeLog:

	PR analyzer/106625
	* gcc.dg/analyzer/data-model-1.c: Change expected result.
	* gcc.dg/analyzer/out-of-bounds-5.c: New test.
	* gcc.dg/analyzer/out-of-bounds-realloc-grow.c: New test.
	* gcc.dg/analyzer/symbolic-gt-1.c: New test.

1 files changed, 15 insertions, 2 deletions

diff --git a/gcc/analyzer/region.h b/gcc/analyzer/region.h
index 34ce1fa..6315fac 100644
--- a/gcc/analyzer/region.h
+++ b/gcc/analyzer/region.h
@@ -175,7 +175,7 @@ public:
 
   bool involves_p (const svalue *sval) const;
 
-  region_offset get_offset () const;
+  region_offset get_offset (region_model_manager *mgr) const;
 
   /* Attempt to get the size of this region as a concrete number of bytes.
      If successful, return true and write the size to *OUT.
@@ -196,6 +196,11 @@ public:
      Otherwise return false.  */
   virtual bool get_relative_concrete_offset (bit_offset_t *out) const;
 
+  /* Get the offset in bytes of this region relative to its parent as a svalue.
+     Might return an unknown_svalue.  */
+  virtual const svalue *
+  get_relative_symbolic_offset (region_model_manager *mgr) const;
+
   /* Attempt to get the position and size of this region expressed as a
      concrete range of bytes relative to its parent.
      If successful, return true and write to *OUT.
@@ -226,7 +231,7 @@ public:
   region (complexity c, unsigned id, const region *parent, tree type);
 
  private:
-  region_offset calc_offset () const;
+  region_offset calc_offset (region_model_manager *mgr) const;
 
   complexity m_complexity;
   unsigned m_id; // purely for deterministic sorting at this stage, for dumps
@@ -751,6 +756,8 @@ public:
   tree get_field () const { return m_field; }
 
   bool get_relative_concrete_offset (bit_offset_t *out) const final override;
+  const svalue *get_relative_symbolic_offset (region_model_manager *mgr)
+    const final override;
 
 private:
   tree m_field;
@@ -835,6 +842,8 @@ public:
 
   virtual bool
   get_relative_concrete_offset (bit_offset_t *out) const final override;
+  const svalue *get_relative_symbolic_offset (region_model_manager *mgr)
+    const final override;
 
 private:
   const svalue *m_index;
@@ -919,6 +928,8 @@ public:
   const svalue *get_byte_offset () const { return m_byte_offset; }
 
   bool get_relative_concrete_offset (bit_offset_t *out) const final override;
+  const svalue *get_relative_symbolic_offset (region_model_manager *mgr)
+    const final override;
   const svalue * get_byte_size_sval (region_model_manager *mgr)
     const final override;
 
@@ -1245,6 +1256,8 @@ public:
   bool get_bit_size (bit_size_t *out) const final override;
   const svalue *get_byte_size_sval (region_model_manager *mgr) const final override;
   bool get_relative_concrete_offset (bit_offset_t *out) const final override;
+  const svalue *get_relative_symbolic_offset (region_model_manager *mgr)
+    const final override;
 
 private:
   bit_range m_bits;