analyzer: add text-art visualizations of out-of-bounds accesses [PR106626]

This patch extends -Wanalyzer-out-of-bounds so that, where possible, it
will emit a text art diagram visualizing the spatial relationship between
(a) the memory region that the analyzer predicts would be accessed, versus
(b) the range of memory that is valid to access - whether they overlap,
are touching, are close or far apart; which one is before or after in
memory, the relative sizes involved, the direction of the access (read vs
write), and, in some cases, the values of data involved.  This diagram
can be suppressed using -fdiagnostics-text-art-charset=none.

For example, given:

int32_t arr[10];

int32_t int_arr_read_element_before_start_far(void)
{
  return arr[-100];
}

it emits:

demo-1.c: In function ‘int_arr_read_element_before_start_far’:
demo-1.c:7:13: warning: buffer under-read [CWE-127] [-Wanalyzer-out-of-bounds]
    7 |   return arr[-100];
      |          ~~~^~~~~~
  ‘int_arr_read_element_before_start_far’: event 1
    |
    |    7 |   return arr[-100];
    |      |          ~~~^~~~~~
    |      |             |
    |      |             (1) out-of-bounds read from byte -400 till byte -397 but ‘arr’ starts at byte 0
    |
demo-1.c:7:13: note: valid subscripts for ‘arr’ are ‘[0]’ to ‘[9]’

  ┌───────────────────────────┐
  │read of ‘int32_t’ (4 bytes)│
  └───────────────────────────┘
                ^
                │
                │
  ┌───────────────────────────┐              ┌────────┬────────┬─────────┐
  │                           │              │  [0]   │  ...   │   [9]   │
  │    before valid range     │              ├────────┴────────┴─────────┤
  │                           │              │‘arr’ (type: ‘int32_t[10]’)│
  └───────────────────────────┘              └───────────────────────────┘
  ├─────────────┬─────────────┤├─────┬──────┤├─────────────┬─────────────┤
                │                    │                     │
   ╭────────────┴───────────╮   ╭────┴────╮        ╭───────┴──────╮
   │⚠️  under-read of 4 bytes│   │396 bytes│        │size: 40 bytes│
   ╰────────────────────────╯   ╰─────────╯        ╰──────────────╯

and given:

  #include <string.h>

  void
  test_non_ascii ()
  {
    char buf[5];
    strcpy (buf, "文字化け");
  }

it emits:

demo-2.c: In function ‘test_non_ascii’:
demo-2.c:7:3: warning: stack-based buffer overflow [CWE-121] [-Wanalyzer-out-of-bounds]
    7 |   strcpy (buf, "文字化け");
      |   ^~~~~~~~~~~~~~~~~~~~~~~~
  ‘test_non_ascii’: events 1-2
    |
    |    6 |   char buf[5];
    |      |        ^~~
    |      |        |
    |      |        (1) capacity: 5 bytes
    |    7 |   strcpy (buf, "文字化け");
    |      |   ~~~~~~~~~~~~~~~~~~~~~~~~
    |      |   |
    |      |   (2) out-of-bounds write from byte 5 till byte 12 but ‘buf’ ends at byte 5
    |
demo-2.c:7:3: note: write of 8 bytes to beyond the end of ‘buf’
    7 |   strcpy (buf, "文字化け");
      |   ^~~~~~~~~~~~~~~~~~~~~~~~
demo-2.c:7:3: note: valid subscripts for ‘buf’ are ‘[0]’ to ‘[4]’

  ┌─────┬─────┬─────┬────┬────┐┌────┬────┬────┬────┬────┬────┬────┬──────┐
  │ [0] │ [1] │ [2] │[3] │[4] ││[5] │[6] │[7] │[8] │[9] │[10]│[11]│ [12] │
  ├─────┼─────┼─────┼────┼────┤├────┼────┼────┼────┼────┼────┼────┼──────┤
  │0xe6 │0x96 │0x87 │0xe5│0xad││0x97│0xe5│0x8c│0x96│0xe3│0x81│0x91│ 0x00 │
  ├─────┴─────┴─────┼────┴────┴┴────┼────┴────┴────┼────┴────┴────┼──────┤
  │     U+6587      │    U+5b57     │    U+5316    │    U+3051    │U+0000│
  ├─────────────────┼───────────────┼──────────────┼──────────────┼──────┤
  │       文        │      字       │      化      │      け      │ NUL  │
  ├─────────────────┴───────────────┴──────────────┴──────────────┴──────┤
  │                  string literal (type: ‘char[13]’)                   │
  └──────────────────────────────────────────────────────────────────────┘
     │     │     │    │    │     │    │    │    │    │    │    │     │
     │     │     │    │    │     │    │    │    │    │    │    │     │
     v     v     v    v    v     v    v    v    v    v    v    v     v
  ┌─────┬────────────────┬────┐┌─────────────────────────────────────────┐
  │ [0] │      ...       │[4] ││                                         │
  ├─────┴────────────────┴────┤│            after valid range            │
  │  ‘buf’ (type: ‘char[5]’)  ││                                         │
  └───────────────────────────┘└─────────────────────────────────────────┘
  ├─────────────┬─────────────┤├────────────────────┬────────────────────┤
                │                                   │
       ╭────────┴────────╮              ╭───────────┴──────────╮
       │capacity: 5 bytes│              │⚠️  overflow of 8 bytes│
       ╰─────────────────╯              ╰──────────────────────╯

showing that the overflow occurs partway through the UTF-8 encoding of
the U+5b57 code point.

There are lots more examples in the test suite.

It doesn't show up in this email, but the above diagrams are colorized
to constrast the valid and invalid access ranges.

gcc/ChangeLog:
	PR analyzer/106626
	* Makefile.in (ANALYZER_OBJS): Add analyzer/access-diagram.o.
	* doc/invoke.texi (Wanalyzer-out-of-bounds): Add description of
	text art.
	(fanalyzer-debug-text-art): New.

gcc/analyzer/ChangeLog:
	PR analyzer/106626
	* access-diagram.cc: New file.
	* access-diagram.h: New file.
	* analyzer.h (class region_offset): Add default ctor.
	(region_offset::make_byte_offset): New decl.
	(region_offset::concrete_p): New.
	(region_offset::get_concrete_byte_offset): New.
	(region_offset::calc_symbolic_bit_offset): New decl.
	(region_offset::calc_symbolic_byte_offset): New decl.
	(region_offset::dump_to_pp): New decl.
	(region_offset::dump): New decl.
	(operator<, operator<=, operator>, operator>=): New decls for
	region_offset.
	* analyzer.opt
	(-param=analyzer-text-art-string-ellipsis-threshold=): New.
	(-param=analyzer-text-art-string-ellipsis-head-len=): New.
	(-param=analyzer-text-art-string-ellipsis-tail-len=): New.
	(-param=analyzer-text-art-ideal-canvas-width=): New.
	(fanalyzer-debug-text-art): New.
	* bounds-checking.cc: Include "intl.h", "diagnostic-diagram.h",
	and "analyzer/access-diagram.h".
	(class out_of_bounds::oob_region_creation_event_capacity): New.
	(out_of_bounds::out_of_bounds): Add "model" and "sval_hint"
	params.
	(out_of_bounds::mark_interesting_stuff): Use the base region.
	(out_of_bounds::add_region_creation_events): Use
	oob_region_creation_event_capacity.
	(out_of_bounds::get_dir): New pure vfunc.
	(out_of_bounds::maybe_show_notes): New.
	(out_of_bounds::maybe_show_diagram): New.
	(out_of_bounds::make_access_diagram): New.
	(out_of_bounds::m_model): New field.
	(out_of_bounds::m_sval_hint): New field.
	(out_of_bounds::m_region_creation_event_id): New field.
	(concrete_out_of_bounds::concrete_out_of_bounds): Update for new
	fields.
	(concrete_past_the_end::concrete_past_the_end): Likewise.
	(concrete_past_the_end::add_region_creation_events): Use
	oob_region_creation_event_capacity.
	(concrete_buffer_overflow::concrete_buffer_overflow): Update for
	new fields.
	(concrete_buffer_overflow::emit): Replace call to
	maybe_describe_array_bounds with maybe_show_notes.
	(concrete_buffer_overflow::get_dir): New.
	(concrete_buffer_over_read::concrete_buffer_over_read): Update for
	new fields.
	(concrete_buffer_over_read::emit): Replace call to
	maybe_describe_array_bounds with maybe_show_notes.
	(concrete_buffer_overflow::get_dir): New.
	(concrete_buffer_underwrite::concrete_buffer_underwrite): Update
	for new fields.
	(concrete_buffer_underwrite::emit): Replace call to
	maybe_describe_array_bounds with maybe_show_notes.
	(concrete_buffer_underwrite::get_dir): New.
	(concrete_buffer_under_read::concrete_buffer_under_read): Update
	for new fields.
	(concrete_buffer_under_read::emit): Replace call to
	maybe_describe_array_bounds with maybe_show_notes.
	(concrete_buffer_under_read::get_dir): New.
	(symbolic_past_the_end::symbolic_past_the_end): Update for new
	fields.
	(symbolic_buffer_overflow::symbolic_buffer_overflow): Likewise.
	(symbolic_buffer_overflow::emit): Call maybe_show_notes.
	(symbolic_buffer_overflow::get_dir): New.
	(symbolic_buffer_over_read::symbolic_buffer_over_read): Update for
	new fields.
	(symbolic_buffer_over_read::emit): Call maybe_show_notes.
	(symbolic_buffer_over_read::get_dir): New.
	(region_model::check_symbolic_bounds): Add "sval_hint" param.  Pass
	it and sized_offset_reg to diagnostics.
	(region_model::check_region_bounds): Add "sval_hint" param, passing
	it to diagnostics.
	* diagnostic-manager.cc
	(diagnostic_manager::emit_saved_diagnostic): Pass logger to
	pending_diagnostic::emit.
	* engine.cc: Add logger param to pending_diagnostic::emit
	implementations.
	* infinite-recursion.cc: Likewise.
	* kf-analyzer.cc: Likewise.
	* kf.cc: Likewise.  Add nullptr for new param of
	check_region_for_write.
	* pending-diagnostic.h: Likewise in decl.
	* region-model-manager.cc
	(region_model_manager::get_or_create_int_cst): Convert param from
	poly_int64 to const poly_wide_int_ref &.
	(region_model_manager::maybe_fold_binop): Support type being NULL
	when checking for floating-point types.
	Check for (X + Y) - X => Y.  Be less strict about types when folding
	associative ops.  Check for (X + Y) * CST => (X * CST) + (Y * CST).
	* region-model-manager.h
	(region_model_manager::get_or_create_int_cst): Convert param from
	poly_int64 to const poly_wide_int_ref &.
	* region-model.cc: Add logger param to pending_diagnostic::emit
	implementations.
	(region_model::check_external_function_for_access_attr): Update
	for new param of check_region_for_write.
	(region_model::deref_rvalue): Use nullptr rather than NULL.
	(region_model::get_capacity): Handle RK_STRING.
	(region_model::check_region_access): Add "sval_hint" param; pass it to
	check_region_bounds.
	(region_model::check_region_for_write): Add "sval_hint" param;
	pass it to check_region_access.
	(region_model::check_region_for_read): Add NULL for new param to
	check_region_access.
	(region_model::set_value): Pass rhs_sval to
	check_region_for_write.
	(region_model::get_representative_path_var_1): Handle SK_CONSTANT
	in the check for infinite recursion.
	* region-model.h (region_model::check_region_for_write): Add
	"sval_hint" param.
	(region_model::check_region_access): Likewise.
	(region_model::check_symbolic_bounds): Likewise.
	(region_model::check_region_bounds): Likewise.
	* region.cc (region_offset::make_byte_offset): New.
	(region_offset::calc_symbolic_bit_offset): New.
	(region_offset::calc_symbolic_byte_offset): New.
	(region_offset::dump_to_pp): New.
	(region_offset::dump): New.
	(struct linear_op): New.
	(operator<, operator<=, operator>, operator>=): New, for
	region_offset.
	(region::get_next_offset): New.
	(region::get_relative_symbolic_offset): Use ptrdiff_type_node.
	(field_region::get_relative_symbolic_offset): Likewise.
	(element_region::get_relative_symbolic_offset): Likewise.
	(bit_range_region::get_relative_symbolic_offset): Likewise.
	* region.h (region::get_next_offset): New decl.
	* sm-fd.cc: Add logger param to pending_diagnostic::emit
	implementations.
	* sm-file.cc: Likewise.
	* sm-malloc.cc: Likewise.
	* sm-pattern-test.cc: Likewise.
	* sm-sensitive.cc: Likewise.
	* sm-signal.cc: Likewise.
	* sm-taint.cc: Likewise.
	* store.cc (bit_range::contains_p): Allow "out" to be null.
	* store.h (byte_range::get_start_bit_offset): New.
	(byte_range::get_next_bit_offset): New.
	* varargs.cc: Add logger param to pending_diagnostic::emit
	implementations.

gcc/testsuite/ChangeLog:
	PR analyzer/106626
	* gcc.dg/analyzer/data-model-1.c (test_16): Update for
	out-of-bounds working.
	* gcc.dg/analyzer/out-of-bounds-diagram-1-ascii.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-1-debug.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-1-emoji.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-1-json.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-1-sarif.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-1-unicode.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-10.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-11.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-12.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-13.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-14.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-15.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-2.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-3.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-4.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-5-ascii.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-5-unicode.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-6.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-7.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-8.c: New test.
	* gcc.dg/analyzer/out-of-bounds-diagram-9.c: New test.
	* gcc.dg/analyzer/pattern-test-2.c: Update expected results.
	* gcc.dg/analyzer/pr101962.c: Update expected results.
	* gcc.dg/plugin/analyzer_gil_plugin.c:  Add logger param to
	pending_diagnostic::emit implementations.

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

1 files changed, 9 insertions, 0 deletions

diff --git a/gcc/analyzer/store.h b/gcc/analyzer/store.h
index 7ded650..af6cc7e 100644
--- a/gcc/analyzer/store.h
+++ b/gcc/analyzer/store.h
@@ -350,6 +350,15 @@ struct byte_range
 		      m_size_in_bytes * BITS_PER_UNIT);
   }
 
+  bit_offset_t get_start_bit_offset () const
+  {
+    return m_start_byte_offset * BITS_PER_UNIT;
+  }
+  bit_offset_t get_next_bit_offset () const
+  {
+    return get_next_byte_offset () * BITS_PER_UNIT;
+  }
+
   static int cmp (const byte_range &br1, const byte_range &br2);
 
   byte_offset_t m_start_byte_offset;