analyzer: out-of-bounds checker [PR106000]

This patch adds an experimental out-of-bounds checker to the analyzer.

The checker was tested on coreutils, curl, httpd and openssh. It is mostly
accurate but does produce false-positives on yacc-generated files and
sometimes when the analyzer misses an invariant. These cases will be
documented in bugzilla.
Regression-tested on Linux x86-64, further ran the analyzer tests with
the -m32 option.

2022-08-11  Tim Lange  <mail@tim-lange.me>

gcc/analyzer/ChangeLog:

	PR analyzer/106000
	* analyzer.opt: Add Wanalyzer-out-of-bounds.
	* region-model.cc (class out_of_bounds): Diagnostics base class
	for all out-of-bounds diagnostics.
	(class past_the_end): Base class derived from out_of_bounds for
	the buffer_overflow and buffer_overread diagnostics.
	(class buffer_overflow): Buffer overflow diagnostics.
	(class buffer_overread): Buffer overread diagnostics.
	(class buffer_underflow): Buffer underflow diagnostics.
	(class buffer_underread): Buffer overread diagnostics.
	(region_model::check_region_bounds): New function to check region
	bounds for out-of-bounds accesses.
	(region_model::check_region_access):
	Add call to check_region_bounds.
	(region_model::get_representative_tree): New function that accepts
	a region instead of an svalue.
	* region-model.h (class region_model):
	Add region_model::check_region_bounds.
	* region.cc (region::symbolic_p): New predicate.
	(offset_region::get_byte_size_sval): Only return the remaining
	byte size on offset_regions.
	* region.h: Add region::symbolic_p.
	* store.cc (byte_range::intersects_p):
	Add new function equivalent to bit_range::intersects_p.
	(byte_range::exceeds_p): New function.
	(byte_range::falls_short_of_p): New function.
	* store.h (struct byte_range): Add byte_range::intersects_p,
	byte_range::exceeds_p and byte_range::falls_short_of_p.

gcc/ChangeLog:

	PR analyzer/106000
	* doc/invoke.texi: Add Wanalyzer-out-of-bounds.

gcc/testsuite/ChangeLog:

	PR analyzer/106000
	* g++.dg/analyzer/pr100244.C: Disable out-of-bounds warning.
	* gcc.dg/analyzer/allocation-size-3.c:
	Disable out-of-bounds warning.
	* gcc.dg/analyzer/memcpy-2.c: Disable out-of-bounds warning.
	* gcc.dg/analyzer/pr101962.c: Add dg-warning.
	* gcc.dg/analyzer/pr96764.c: Disable out-of-bounds warning.
	* gcc.dg/analyzer/pr97029.c:
	Add dummy buffer to prevent an out-of-bounds warning.
	* gcc.dg/analyzer/realloc-5.c: Add dg-warning.
	* gcc.dg/analyzer/test-setjmp.h:
	Add dummy buffer to prevent an out-of-bounds warning.
	* gcc.dg/analyzer/zlib-3.c: Add dg-bogus.
	* g++.dg/analyzer/out-of-bounds-placement-new.C: New test.
	* gcc.dg/analyzer/out-of-bounds-1.c: New test.
	* gcc.dg/analyzer/out-of-bounds-2.c: New test.
	* gcc.dg/analyzer/out-of-bounds-3.c: New test.
	* gcc.dg/analyzer/out-of-bounds-container_of.c: New test.
	* gcc.dg/analyzer/out-of-bounds-coreutils.c: New test.
	* gcc.dg/analyzer/out-of-bounds-curl.c: New test.

1 files changed, 9 insertions, 0 deletions

diff --git a/gcc/analyzer/store.h b/gcc/analyzer/store.h
index 9b54c7b..ac8b685 100644
--- a/gcc/analyzer/store.h
+++ b/gcc/analyzer/store.h
@@ -310,6 +310,15 @@ struct byte_range
 	    && m_size_in_bytes == other.m_size_in_bytes);
   }
 
+  bool intersects_p (const byte_range &other,
+		     byte_size_t *out_num_overlap_bytes) const;
+
+  bool exceeds_p (const byte_range &other,
+		  byte_range *out_overhanging_byte_range) const;
+
+  bool falls_short_of_p (byte_offset_t offset,
+			 byte_range *out_fall_short_bytes) const;
+
   byte_offset_t get_start_byte_offset () const
   {
     return m_start_byte_offset;