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, 8 insertions, 8 deletions

diff --git a/gcc/analyzer/sm-taint.cc b/gcc/analyzer/sm-taint.cc
index f72f194..6d28d1f 100644
--- a/gcc/analyzer/sm-taint.cc
+++ b/gcc/analyzer/sm-taint.cc
@@ -211,7 +211,7 @@ public:
     return OPT_Wanalyzer_tainted_array_index;
   }
 
-  bool emit (rich_location *rich_loc) final override
+  bool emit (rich_location *rich_loc, logger *) final override
   {
     diagnostic_metadata m;
     /* CWE-129: "Improper Validation of Array Index".  */
@@ -327,7 +327,7 @@ public:
     return OPT_Wanalyzer_tainted_offset;
   }
 
-  bool emit (rich_location *rich_loc) final override
+  bool emit (rich_location *rich_loc, logger *) final override
   {
     diagnostic_metadata m;
     /* CWE-823: "Use of Out-of-range Pointer Offset".  */
@@ -437,7 +437,7 @@ public:
     return OPT_Wanalyzer_tainted_size;
   }
 
-  bool emit (rich_location *rich_loc) override
+  bool emit (rich_location *rich_loc, logger *) override
   {
     /* "CWE-129: Improper Validation of Array Index".  */
     diagnostic_metadata m;
@@ -547,9 +547,9 @@ public:
     return "tainted_access_attrib_size";
   }
 
-  bool emit (rich_location *rich_loc) final override
+  bool emit (rich_location *rich_loc, logger *logger) final override
   {
-    bool warned = tainted_size::emit (rich_loc);
+    bool warned = tainted_size::emit (rich_loc, logger);
     if (warned)
       {
 	inform (DECL_SOURCE_LOCATION (m_callee_fndecl),
@@ -583,7 +583,7 @@ public:
     return OPT_Wanalyzer_tainted_divisor;
   }
 
-  bool emit (rich_location *rich_loc) final override
+  bool emit (rich_location *rich_loc, logger *) final override
   {
     diagnostic_metadata m;
     /* CWE-369: "Divide By Zero".  */
@@ -645,7 +645,7 @@ public:
     return OPT_Wanalyzer_tainted_allocation_size;
   }
 
-  bool emit (rich_location *rich_loc) final override
+  bool emit (rich_location *rich_loc, logger *) final override
   {
     diagnostic_metadata m;
     /* "CWE-789: Memory Allocation with Excessive Size Value".  */
@@ -800,7 +800,7 @@ public:
     return OPT_Wanalyzer_tainted_assertion;
   }
 
-  bool emit (rich_location *rich_loc) final override
+  bool emit (rich_location *rich_loc, logger *) final override
   {
     diagnostic_metadata m;
     /* "CWE-617: Reachable Assertion".  */